Abstract
Robotic swarms are usually designed in a bottom-up way, which can make robotic swarms vulnerable to environmental impact. It is particularly true for the widely used control mode of robotic swarms, where it is often the case that neither the correctness of the swarming tasks at the macro level nor the safety of the interaction among agents at the micro level can be guaranteed. To ensure that the behaviors are safe at runtime, it is necessary to take into account the property guard approaches for robotic swarms in uncertain environments. Runtime enforcement is an approach which can guarantee the given properties in system execution and has no scalability issue. Although some runtime enforcement methods have been studied and applied in different domains, they cannot effectively solve the problem of property enforcement on robotic swarm tasks at present. In this paper, an enforcement method is proposed on swarms which should satisfy multi-level properties in uncertain environments. We introduce a macro-micro property enforcing framework with the notion of agent shields and a discrete-time enforcing mechanism called D-time enforcing. To realize this method, a domain specification language and the corresponding enforcer synthesis algorithms are developed. We then apply the approach to enforce the properties of the simulated robotic swarm in the robotflocksim platform. We evaluate and show the effectiveness of the method with experiments on specific unmanned aerial vehicle swarm tasks.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bauer A, Falcone Y, 2016. Decentralised LTL monitoring. Form Meth Syst Des, 48(1–2):46–93. https://doi.org/10.1007/s10703-016-0253-8
Bloem R, Chatterjee K, Greimel K, et al., 2014. Synthesizing robust systems. Acta Inform, 51(3–4):193–220. https://doi.org/10.1007/s00236-013-0191-5
Brambilla M, Ferrante E, Birattari M, et al., 2013. Swarm robotics: a review from the swarm engineering perspective. Swarm Intell, 7(1):1–41. https://doi.org/10.1007/s11721-012-0075-2
Chung SJ, Paranjape AA, Dames P, et al., 2018. A survey on aerial swarm robotics. IEEE Trans Robot, 34(4):837–855. https://doi.org/10.1109/TRO.2018.2857475
Dong W, Zhao CZ, Shu SX, et al., 2012. Anticipatory active monitoring for safety- and security-critical software. Sci China Inform Sci, 55(12):2723–2737. https://doi.org/10.1007/s11432-012-4739-8
Dreossi T, Fremont DJ, Ghosh S, et al., 2019. VERIFAI: a toolkit for the formal design and analysis of artificial intelligence-based systems. Proc 31st Int Conf on Computer Aided Verification, p.432–442. https://doi.org/10.1007/978-3-030-25540-4_25
Egerstedt M, Lee SG, Diaz-Mercado Y, et al., 2020. Control of Swarming Robots. US Patent 10 537 996.
Fine BT, Shell DA, 2013. Unifying microscopic flocking motion models for virtual, robotic, and biological flock members. Auton Robot, 35(2–3):195–219. https://doi.org/10.1007/s10514-013-9338-z
Floreano D, Wood RJ, 2015. Science, technology and the future of small autonomous drones. Nature, 521(7553):460–466. https://doi.org/10.1038/nature14542
Gökçe F, Sahin E, 2009. To flock or not to flock: the pros and cons of flocking in long-range “migration” of mobile robot swarms. Proc 8th Int Joint Conf on Autonomous Agents and Multiagent Systems, p.65–72.
Hu C, Dong W, Yang YH, et al., 2020. Runtime verification on hierarchical properties of ROS-based robot swarms. IEEE Trans Reliab, 69(2):674–689. https://doi.org/10.1109/TR.2019.2923681
Khosla P, Brown B, Paredis C, et al., 2002. Millibot Report. Report on Millibot Project, DARPA Contract DABT63-97-1-0003, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA. Könighofer B, Alshiekh M, Bloem R, et al., 2017. Shield synthesis. Form Meth Syst Des, 51(2):332–361. https://doi.org/10.1007/s10703-017-0276-9
Ligatti J, Bauer L, Walker D, 2005. Edit automata: enforcement mechanisms for run-time security policies. Int J Inform Sec, 4(1–2):2–16. https://doi.org/10.1007/s10207-004-0046-8
Mondada F, Gambardella LM, Floreano D, et al., 2005. The cooperation of swarm-bots: physical interactions in collective robotics. IEEE Robot Autom Mag, 12(2):21–28. https://doi.org/10.1109/MRA.2005.1458313
Nagavalli S, Chien SY, Lewis M, et al., 2015. Bounds of neglect benevolence in input timing for human interaction with robotic swarms. Proc 10th Annual ACM/IEEE Int Conf on Human-Robot Interaction, p.197–204. https://doi.org/10.1145/2696454.2696470
Parr T, 2013. The Definitive ANTLR 4 Reference. Pragmatic Bookshelf, Dallas, USA, p.21–33.
Pinisetty S, Preoteasa V, Tripakis S, et al., 2017. Predictive runtime enforcement. Form Meth Syst Des, 51(1):154–199. https://doi.org/10.1007/s10703-017-0271-1
Pnueli A, 1977. The temporal logic of programs. Proc 18th Annual Symp Foundations of Computer Science, p.46–57. https://doi.org/10.1109/SFCS.1977.32
Pugh J, Martinoli A, 2006. Multi-robot learning with particle swarm optimization. Proc 5th Int joint Conf on Autonomous Agents and Multiagent Systems, p.441–448. https://doi.org/10.1145/1160633.1160715
Rajkumar R, Lee I, Sha L, et al., 2010. Cyber-physical systems: the next computing revolution. Proc 47th Design Automation Conf, p.731–736. https://doi.org/10.1145/1837274.1837461
Raju D, Bharadwaj S, Topcu U, 2019. Online synthesis for runtime enforcement of safety in multi-agent systems. https://arxiv.org/abs/1910.10380
Rasmussen S, Kingston D, Humphrey L, 2018. A brief introduction to unmanned systems autonomy services (UxAS). Int Conf on Unmanned Aircraft Systems, p.257–268. https://doi.org/10.1109/icuas.2018.8453287
Reinbacher T, Rozier KY, Schumann J, 2014. Temporal-logic based runtime observer pairs for system health management of real-time systems. Proc 20th Int Conf on Tools and Algorithms for the Construction and Analysis of Systems, p.357–372. https://doi.org/10.1007/978-3-642-54862-8_24
Reynolds CW, 1987. Flocks, herds and schools: a distributed behavioral model. ACM SIGGRAPH Comput Graph, 21(4):25–34. https://doi.org/10.1145/37401.37406
Şahin E, Girgin S, Bayindir L, et al., 2008. Swarm robotics. In: Blum C, Merkle D (Eds.), Swarm Intelligence. Natural Computing Series. Springer Berlin Heidelberg, p.87–100. https://doi.org/10.1007/978-3-540-74089-6_3
Schwager M, McLurkin J, Rus D, 2006. Distributed coverage control with sensory feedback for networked robots. Proc Robotics: Science and Systems, p.117–132. https://doi.org/10.15607/RSS.2006.II.007
Shi H, Dong W, Zhou G, et al., 2017. Monitor synthesis for parametric MTL properties in discrete control software. IEEE Int Conf on Software Quality, Reliability and Security Companion, p.355–362. https://doi.org/10.1109/QRS-C.2017.66
Sinhuber M, van der Vaart K, Ouellette NT, 2019. Response of insect swarms to dynamic illumination perturbations. J Roy Soc Interf, 16(150):20180739. https://doi.org/10.1098/rsif.2018.0739
Standley T, Korf R, 2011. Complete algorithms for cooperative pathfinding problems. Proc 22nd Int Joint Conf on Artificial Intelligence, p.668–673. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-118
Turgut AE, Çelikkanat H, Gökçe F, et al., 2008. Self-organized flocking in mobile robot swarms. Swarm Intell, 2(2–4):97–120. https://doi.org/10.1007/s11721-008-0016-2
Vásárhelyi G, Virágh C, Somorjai G, et al., 2018. Optimized flocking of autonomous drones in confined environments. Sci Robot, 3(20):eaat3536. https://doi.org/10.1126/scirobotics.aat3536
Williams K, Burdick JW, 2006. Multi-robot boundary coverage with plan revision. IEEE Int Conf on Robotics and Automation, p.1716–1723. https://doi.org/10.1109/ROBOT.2006.1641954
Wong C, Yang EF, Yan XT, et al., 2017. An overview of robotics and autonomous systems for harsh environments. Proc 23rd Int Conf on Automation and Computing, p.1–6. https://doi.org/10.23919/IConAC.2017.8082020
Zhang X, Leucker M, Dong W, 2012. Runtime verification with predictive semantics. Proc 4th Int Symp on NASA Formal Methods, p.418–432. https://doi.org/10.1007/978-3-642-28891-3_37
Zhang Y, Kim K, Fainekos G, 2014. DisCoF: cooperative pathfinding in distributed systems with limited sensing and communication range. In: Chong NY, Cho YJ (Eds.), Distributed Autonomous Robotic Systems, p.325–340. https://doi.org/10.1007/978-4-431-55879-8_23
Author information
Authors and Affiliations
Corresponding author
Additional information
Project supported by the National Natural Science Foundation of China (Nos. 62032019 and 61690203
Contributors
Chi HU, Wei DONG, and Yong-hui YANG designed the research. Chi HU, Hao SHI, and Fei DENG processed the data. Chi HU drafted the manuscript. Wei DONG helped organize the manuscript. Chi HU and Wei DONG revised and finalized the paper.
Compliance with ethics guidelines
Chi HU, Wei DONG, Yong-hui YANG, Hao SHI, and Fei DENG declare that they have no conflict of interest.
Rights and permissions
About this article
Cite this article
Hu, C., Dong, W., Yang, Yh. et al. Decentralized runtime enforcement for robotic swarms. Front Inform Technol Electron Eng 21, 1591–1606 (2020). https://doi.org/10.1631/FITEE.2000203
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1631/FITEE.2000203