Abstract
Connectivity is an integral trait for swarm robotic systems to enable effective collaboration between the robots in the swarm. However, connectivity can be lost due to events that could not have been a priori accounted for. This paper presents a novel probabilistic connectivity-restoration strategy for swarms with limited communication capabilities. Namely, it is assumed that the swarm comprises a group of follower robots whose global connectivity to a base can only be achieved via a localized leader robot. In this context, the proposed strategy incrementally restores swarm connectivity by searching for the lost robots in regions-of-interest (RoIs) determined using probability theory. Once detected, newly found robots are either recruited to help the leader in the restoration process, or directly guided to their respective destinations through accurate localization and corrective motion commands. The proposed swarm-connectivity strategy, thus, comprises the following three stages: (i) identifying a discrete set of optimal RoIs, (ii) visitation of these RoIs, by the leader robot, via an optimal inter-region search path, and (iii) searching for lost robots within the individual RoIs via an optimal intra-region search path. The strategy is novel in its use of a probabilistic approach to guide the leader robot’s search as well as the potential recruitment of detected lost robots to help in the restoration process. The effectiveness of the proposed probabilistic swarm connectivity-restoration strategy is represented, herein, through a detailed simulated experiment. The significant efficiency of the strategy is also illustrated numerically via a comparison to a competing random-walk based method.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Barca, J.C., Sekercioglu, Y.A.: Swarm robotics reviewed. Robotica 31(3), 345–359 (2013)
Brambilla, M., Ferrante, E., Birattari, M., Dorigo, M.: Swarm robotics: A review from the swarm engineering perspective. Swarm Intell. 7(1), 1–41 (2013)
Şahin, E.: Swarm robotics: From sources of inspiration to domains of application. In: Şahin, E. and Spears, W.M. (eds.) Swarm Robotics. pp. 10–20 (2004)
Schranz, M., Umlauft, M., Sende, M., Elmenreich, W.: Swarm robotic behaviors and current applications, Front. Robot. AI 7, (2020)
Farid, M., Kamal, M.A.S., Egerton, S.: Search strategies and specifications in a swarm versus swarm context. Robotica 39(11), 1909–1925 (2021)
Abdelli, A., Yachir, A., Amamra, A., Khaldi, B.: Maximum likelihood estimate sharing for collective perception in static environments for swarm robotics”. Robotica 41(9), 1–20 (2023)
Couceiro, M.S., Portugal, D., Rocha, R.P., Ferreira, N.M.: Marsupial teams of robots: deployment of miniature robots for swarm exploration under communication constraints. Robotica 32(7), 1017–1038 (2014)
Stergiopoulos, Y., Tzes, A.: Decentralized swarm coordination: A combined coverage/connectivity approach. J. Intell. Robot. Syst. 64, 603–623 (2011)
Eshaghi, K., Li, Y., Kashino, Z., Nejat, G., Benhabib, B.: mROBerTO 2.0 – An autonomous millirobot with enhanced locomotion for swarm robotics. Robot. Autom. Let 5(2), 962–969 (2020)
Kim J.Y., Colaco, T., Kashino, Z., Nejat, G., Benhabib, B.: mROBerTO: A modular millirobot for swarm-behavior studies. In: IEEE/RSJ International Conference on Intelligent Robots and Systems. pp. 2109–2114. IEEE (2016)
Kim, J.Y., Kashino, Z., Colaco, T., Nejat, G., Benhabib, B.: Design and implementation of a millirobot for swarm studies – mROBerTO. Robotica 36(11), 1591–1612 (2018)
Kim, J.Y., et al.: A high-performance millirobot for swarm-behaviour studies: Swarm-topology estimation. Int. J. Adv. Robot. Syst. 16(6), 1–18 (2019)
Drisdelle, R., Kashino, Z., Nejat, G., Benhabib, B.: Motion control of a wheeled millirobot. In: International Conference of Control, Dynamic Systems, and Robotics. (2017)
Eshaghi, K., Kashino, Z., Yoon, H.J., Nejat, G., Benhabib, B.: An inchworm-inspired motion strategy for robotic swarms. Robotica 39(12), 2283–2305 (2021)
Chen, Z., Emami, M.R., Chen, W.: Connectivity preservation and obstacle avoidance in small multi-spacecraft formation with distributed adaptive tracking control. J. Intell. Robot. Syst. 101, 16 (2021)
Yang, P., Freeman, R.A., Gordon, G.J., Lynch, K.M., Srinivasa, S.S., Sukthankar, R.: Decentralized estimation and control of graph connectivity for mobile sensor networks. Automatica 46(2), 390–396 (2010)
Ji, M., Egerstedt, M.: Distributed coordination control of multiagent systems while preserving connectedness. IEEE Trans. Robot. 23(4), 693–703 (2007)
Luo, W., Yi, S., Sycara, K.: Behavior mixing with minimum global and subgroup connectivity maintenance for large-scale multi-robot systems. In: IEEE International Conference on Robotics and Automation. pp. 9845–9851. IEEE (2020)
Giordano, P.R., Franchi, A., Secchi, C., Bülthoff, H.H.: A passivity-based decentralized strategy for generalized connectivity maintenance. Int. J. Robot. Res. 32(3), 299–323 (2013)
Sabattini, L., Chopra, N., Secchi, C.: Decentralized connectivity maintenance for cooperative control of mobile robotic systems. Int. J. Robot. Res. 32(12), 1411–1423 (2013)
Shetty, A., Hussain, T., Gao, G.: Decentralized connectivity maintenance for multi-robot systems under motion and sensing uncertainties. J. Inst. Navig. 70(1), 1–20 (2023)
Schuresko, M., Cortés, J.: Distributed motion constraints for algebraic connectivity of robotic networks. J. Intell. Robot. Syst. 56, 99–126 (2009)
Fink, J., Ribeiro, A., Kumar, V.: Robust control for mobility and wireless communication in cyber–physical systems with application to robot teams. Proc. IEEE 100(1), 164–178 (2012)
Ghedini, C., Ribeiro, C.C.H., Sabattini, L.: A decentralized control strategy for resilient connectivity maintenance in multi-robot systems subject to failures. In: Springer Proceedings in Advanced Robotics 6. pp. 89–102. (2018)
Eshaghi, K., Rogers, A., Nejat, G., Benhabib, B.: Closed-loop motion control of robotic swarms – A tether-based strategy. IEEE Trans. Robot. 38(6), 3564–3581 (2022)
Eshaghi, K., Nejat, G., Benhabib, B.: A concurrent mission-planning methodology for robotic swarms using collaborative motion-control strategies. J. Intell. Robot. Syst. 108(2), 15 (2023)
Defoort, M., Veluvolu, K.C.: A motion planning framework with connectivity management for multiple cooperative robots. J. Intell. Robot. Syst. 75, 343–357 (2014)
Meng, Y., Nickerson, J., Gan, J.: Hierarchical multi-robot coordination - Aggregation strategies using hybrid communication. In: Proceedings of the International Conference on Informatics in Control, Automation, and Robotics. pp. 289–295. (2006)
Meng, Y., Nickerson, J.V., Gan, J.: Multi-robot aggregation strategies with limited communication. In: IEEE/RSJ International Conference on Intelligent Robots and Systems. pp. 2691–2696. IEEE (2006)
Derbakova, A., Correll, N., Rus, D.: Decentralized self-repair to maintain connectivity and coverage in networked multi-robot systems. In: IEEE International Conference on Robotics and AutomaTion. pp. 3863–3868. IEEE (2011)
Kunwar, F., Wong, F., Mrad, R.B., Benhabib, B.: Guidance-based on-line robot motion planning for the interception of mobile targets in dynamic environments. J. Intell. Robot. Syst. 47(4), 341–360 (2006)
Agah, F., Mehrandezh, M., Fenton, R.G., Benhabib, B.: On-line robotic interception planning using a rendezvous-guidance technique. J. Intell. Robot. Syst. 40(1), 23–44 (2004)
Borg, J.M., Mehrandezh, M., Fenton, R.G., Benhabib, B.: Navigation-guidance-based robotic interception of moving objects in industrial settings. J. Intell. Robot. Syst. 33(1), 1–23 (2002)
Mehrandezh, M., Sela, M.N., Fenton, R.G., Benhabib, B.: Robotic interception of moving objects using ideal proportional navigation guidance technique. Robot. Auton. Syst. 28(4), 295–310 (1999)
Engin, K., Isler, V.: Minimizing movement to establish the connectivity of randomly deployed robots. Proc. Int. Conf. Autom. Plan. Sched. 28, 451–458 (2018)
Varadharajan, V.S., St-Onge, D., Adams, B., Beltrame, G.: Swarm relays: Distributed self-healing ground-and-air connectivity chains. IEEE Robot. Autom. Lett. 5(4), 5347–5354 (2020)
Marchukov, Y., Montano, L.: Multi-robot coordination for connectivity recovery after unpredictable environment changes. IFAC-Pap. 52(8), 446–451 (2019)
Dutta, R., Kandath, H., Jayavelu, S., Xiaoli, L., Sundaram, S., Pack, D.: A decentralized learning strategy to restore connectivity during multi-agent formation control. Neurocomputing 520, 33–45 (2023)
Wagner A, Arkin R.: Multi-robot communication-sensitive reconnaissance. In: Proceedings of the IEEE International Conference on Robotics and Automation. pp. 4674–4681. IEEE (2004)
Liu, H., Chu, X., Leung, Y.-W., Du, R.: Simple movement control algorithm for bi-connectivity in robotic sensor networks. IEEE J. Sel. Areas Commun. 28(7), 994–1005 (2010)
Roy, N., Dudek, G.: Collaborative robot exploration and rendezvous: Algorithms, performance bounds and observations. Auton. Robots 11(2), 117–136 (2001)
Ulam, P., Arkin, R.C.: When good communication go bad: Communications recovery for multi-robot teams. In: Proceedings of the IEEE International Conference on Robotics and Automation. pp. 3727–3734. IEEE (2004)
Chaimowicz, L., Cowley, A., Gomez-Ibanez, D., Grocholsky, B., Hsieh, M.A., Hsu, H., Keller, J.F., Kumar, V., Swaminathan, R., Taylor, C.J.: Deploying air-ground multi-robot teams in urban environments. In: Multi-Robot Systems - From Swarms to Intelligent Automata. pp. 223–234. (2005)
Hansen, E., A., Nichele, S., Yazidi, A., Haugerud, H., Mofrad, A.A., Alcocer, A.: Achieving connectivity between wide areas through self-organising robot swarms using embodied evolution. In: IEEE Symposium Series on Computational Intelligence. pp. 875–883. (2018)
Baroudi, U., Aldarwbi, M., Younis, M.: Energy-aware connectivity restoration mechanism for cyber-physical systems of networked sensors and robots. IEEE Syst. J. 14(3), 3093–3104 (2020)
Lee, S., Younis, M., Lee, M.: Connectivity restoration in a partitioned wireless sensor network with assured fault tolerance”. Ad Hoc Netw. 24(A), 1–19 (2015)
Basu, P., Redi, J.: Movement control algorithms for realization of fault-tolerant ad hoc robot networks. IEEE Netw. 18(4), 36–44 (2004)
Abbasi, A., Younis, M., Akkaya, K.: Movement-assisted connectivity restoration in wireless sensor and actor networks. IEEE Trans. Parallel Distrib. Syst. 20(9), 1366–1379 (2009)
Haider, N., Imran, M., Saad, N.M.: CARE: Coverage-aware connectivity restoration algorithm for mobile actor/robot networks. In: Asia-Pacific Conference on Communications. pp. 439–444. (2013)
Mi, Z., Yang, Y., Yang, J.Y.: Restoring connectivity of mobile robotic sensor networks while avoiding obstacles. IEEE Sens. J. 15(8), 4640–4650 (2015)
Abbasi, A., Younis, M.F., Baroudi, U.A.: A least–movement topology repair algorithm for partitioned wireless sensor–actor networks. Int. J. Sens. Netw. 11(4), 250–262 (2012)
Mi, Z., Yang, Y., Liu, G.: HERO: A hybrid connectivity restoration framework for mobile multi-agent networks. In: IEEE International Conference on Robotics and Automation. pp. 1702–1707. IEEE (2011)
Bertuccelli, L.F., How, J.P.: UAV search for dynamic targets with uncertain motion models. In: Proceedings of the IEEE Conference on Decision and Control. pp. 5941–5946. IEEE (2006)
Luo, X.: A regional necessity based multi-agent target search strategy for post-earthquake rescue. In: Chinese Control Conference. pp. 4903–4908. (2022)
Meghjani, M., Manjanna, S., Dudek, G.: Multi-target rendezvous search. In: IEEE/RSJ. International Conference on Intelligent Robots and Systems. pp. 2596–2603. IEEE (2016)
Meghjani, M., Manjanna, S., Dudek, G.: Multi-target search strategies. In: IEEE International Symposium on Safety, Security, and Rescue Robotics. pp. 328–333. IEEE (2016)
Wang, P., Meghjani, M.: Lost at Sea: Multi-searcher multi-target search. In: Global Oceans 2020: Singapore – U.S. Gulf Coast. pp. 1–8. IEEE (2020)
Wang, P., Meghjani, M., Chen, G.: Marine trash collection: A multi-agent, multi-target search. In: OCEANS 2022, Hampton Roads. pp. 1–7. IEEE (2022)
Macwan A, Nejat G, Benhabib B.: Optimal deployment of robotic teams for autonomous wilderness search and rescue. In: IEEE/RSJ International Conference on Intelligent Robots and Systems. pp. 4544–4549. IEEE (2011)
Vilela, J., Kashino, Z., Ly, R., Nejat, G., Benhabib, B.: A dynamic approach to sensor network deployment for mobile-target detection in unstructured, expanding search areas. IEEE Sens. J. 16(11), 4405–4417 (2016)
Kashino, Z., Nejat, G., Benhabib, B.: Aerial wilderness search and rescue with ground support. J. Intell. Robot. Syst. 99(1), 147–163 (2020)
Woiceshyn, K., Kashino, Z., Nejat, G., Benhabib, B.: Vehicle routing for resource management in time-phased deployment of sensor networks. IEEE Trans. Autom. Sci. Eng. 16(2), 716–728 (2019)
Sheridan, P.K., Gluck, E., Guan, Q., Pickles, T., Balcıoglu, B., Benhabib, B.: The dynamic nearest neighbor policy for the multi-vehicle pick-up and delivery problem. Transp. Res. Part Policy Pract. 49, 178–194 (2013)
Kashino, Z., Nejat, G., Benhabib, B.: Multi-UAV based autonomous wilderness search and rescue using target iso-probability curves. In: International Conference on Unmanned Aircraft Systems. pp. 636–643. (2019)
Ku S.Y., Nejat, G., Benhabib, B.: Wilderness search for lost persons using a multimodal aerial-terrestrial robot team. Robotics 11(3), 64 (2022)
Kashino, Z., Kim, J.Y., Nejat, G., Benhabib, B.: Spatiotemporal adaptive optimization of a static-sensor network via a non-parametric estimation of target location likelihood. IEEE Sens. J. 17(5), 1479–1492 (2017)
Katoch, S., Chauhan, S.S., Kumar, V.: A review on genetic algorithm: Past, present, and future. Multimed. Tools Appl. 80(5), 8091–8126 (2021)
Acknowledgements
This work was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), and the Canada Research Chairs program (CRC).
Funding
This work was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), and the Canada Research Chairs program (CRC).
Author information
Authors and Affiliations
Contributions
Conceptualization: KE, DR, GN, and BB; Methodology: KE and NNS; Software: KE, NNS, and CH; Analysis: KE, NNS, and CH; Writing: KE, NNS, CH, GN, and BB.; Funding acquisition: GN and BB; Supervision: GN and BB. All authors read and approved the final manuscript.
Corresponding author
Ethics declarations
Competing Interests
Author Beno Benhabib is an Executive-Board Member for the Journal of Intelligent and Robotic Systems. The authors have no relevant funding, employment, financial interests to disclose.
Ethics approval
Not Applicable.
Consent to Participate
Not Applicable.
Consent to Publish
Not Applicable.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix A. Determining Iso-Probability Curves
Iso-probability curves have been used in several robotic wilderness search and rescue (WiSAR) works to model the estimated location of a lost person [59,60,61,62,63,64,65,66]. Each iso-probability curve is associated with a percentile \(p\) and in the WiSAR context it describes how far in a given direction the \({p}^{th}\) slowest percentile of the missing person would have moved at a given point in time. As \(p\) varies from 0 to 100%, the iso-probability curves provide a complete description of the missing person’s possible locations. In a more general sense, each iso-probability curve describes how far, from the center of the (closed-loop) curve, one would need to travel to have a \(p\) percent chance that the target be between that location and the center. In this a way, set of iso-probability curves provides a probabilistic description of the possible locations of a search target in a way that can conveniently describe the area where the target might be and how to cover that area with different curves.
Mathematical Formulation
The formulation for iso-probability curves presented in [65] provides a more rigorous mathematical description. It defines an iso-probability curve for a time varying probability density function in polar coordinates, \({\uprho }_{p}\left(r,\uptheta ,t\right)\), as follows:
where \({F}^{-1}\) is the inverse cumulative probability density in a given direction \(\theta\) at time \(t\). When evaluated for a given quantile \(p\), at all values of \(\theta\), this yields all points along the \({p}^{th}\) iso-probability curve. To compute the desired inverse cumulative density function \({F}^{-1}\), both the cumulative density function \(F\) and the probability density function \(f\) are computed from the polar density function as follows:
Estimation from Point Clouds
In this work, the estimation of robot position is to be estimated through a cloud of points, generated based on the robot’s motion model and its last known position. This point cloud estimation of the lost-robot position must be converted to a probability density estimate for use with the iso-probability curve formulation above. The approach shown in [66] uses a polar grid that is equally spaced in the angular and radial components to construct a histogram-based density estimate. Each point in the point cloud is binned to the closest point in the grid and divided by the total number in that direction, providing an estimate of the probability density in each direction, \(f\). Thereafter, the values at each point are summed in the radial direction providing an estimate of the cumulative density in each direction, \(F\). Interpolation can, then, be used to provide the values of \({F}^{-1}\) needed to construct each iso-probability curve.
Appendix B. Intra-Region Search-Path Planning
An intra-region search path is generated in this work over three steps. Firstly, the percentile (i.e., iso-probability curve) that should be searched is determined. Next, the polar-coordinate position of the search path on that curve is calculated. Finally, the polar-coordinate position of the path is converted into Cartesian coordinates to determine the intra-region path. Figure 25 shows the key information that is extracted from the Region-of-Interest (RoI) for use in determining the search path.
-
Step 1: Percentile Selection
The search method used in this work generates spiral search paths by relating the percentile of the polar distribution that is being searched at a point on the path to the cumulative time and resources that have been used searching up to that point on the path. In this case, the cumulative angular distance that the path has traveled is used as a measure of the time and resources used while searching. Namely, as the spiral path progresses around the center of a RoI, it will follow lower or higher percentile iso-probability curves in a manner that is proportional to the number of turns the spiral has made.
Formally, let us consider the cumulative angular distance that has been traveled, \(\theta \in \left[0,{\uptheta }_{max}\right]\). This cumulative distance can be measured in radians and would increase from 0, at the start point of the spiral search, to some maximum value, \({\theta }_{max}\), that corresponds to the number of turns in the desired spiral path. For example, the first spiral path inwards, while making two complete turns, would have a cumulative angle ranging from 0 to \(4\uppi\) and the starting point where the cumulative angle is zero would be where the initial search path meets the iso-probability curve for the upper bound of the RoI. This cumulative angle is, then, converted into the percentile \(p\) being searched at that point on the path using a linear relationship:
where \({p}_{s}\) is starting percentile for the search, and \(C\) is a constant progression rate controlling how quickly the path moves across different iso-probability curves. The spiral paths are defined between a starting percentile and a final percentile. For paths that spiral outwards, the starting percentile is the lower bound (i.e., \({p}_{s}={p}_{l}\)), the final percentile is the upper bound, and the progression rate is strictly positive (i.e., \(C>0\)). Conversely, for inwards spirals, the starting percentile is the upper bound (i.e., \({p}_{s}={p}_{u}\)), the final percentile is the lower bound, and the progression rate is strictly negative (i.e., \(C<0\)). The percentile bounds can also be used to calculate the maximum cumulative angular distance using:
-
Step 2: Polar-coordinates Path
Given the cumulative angle, \(\theta\), the starting angle of the path, \({\theta }_{s}\), the percentile being searched at that point, \(p\left(\theta \right),\) and the radial position of the \({p}^{th}\) iso-probability curve at a given angle, \({r}_{p\left(\theta \right)}\left(\theta +{\theta }_{s}\right)\), one can define the complete search path. This can be achieved by evaluating \({r}_{p\left(\theta \right)}\left(\theta +{\theta }_{s}\right)\), the radial position of the iso-probability curve for the percentile determined by Equation (B1) at \(\theta\), for values of \(\theta\) along the path, resulting in a path in polar coordinates in the frame centered on the RoI being searched.
-
Step 3: Cartesian-coordinates Path
The polar-coordinates path would need to be converted into Cartesian coordinates in the global frame to determine the intra-region search path. This is achieved using the standard transformation between polar and Cartesian coordinates and the translation of the reference frame. Using the center point of the RoI being searched, \(\left({x}_{RoI},{y}_{RoI}\right)\), the following transformation is obtained:
The above transformation can be applied to arbitrary points along the path yielding the desired intra- region search path, \(S\), as a collection of points in Cartesian-coordinates in the global frame that can be followed by the search team.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Eshaghi, K., Sari, N.N., Haigh, C. et al. Restoring Connectivity in Robotic Swarms – A Probabilistic Approach. J Intell Robot Syst 110, 90 (2024). https://doi.org/10.1007/s10846-024-02097-0
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10846-024-02097-0