Full Text:   <977>

Summary:  <1020>

CLC number: TP311

On-line Access: 2020-11-13

Received: 2020-04-30

Revision Accepted: 2020-09-20

Crosschecked: 2020-10-10

Cited: 0

Clicked: 1958

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Chi Hu

https://orcid.org/0000-0002-4314-5862

Wei Dong

https://orcid.org/0000-0002-8033-7943

Hao Shi

https://orcid.org/0000-0002-6318-9918

Fei Deng

https://orcid.org/0000-0002-0391-1569

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2020 Vol.21 No.11 P.1591-1606

http://doi.org/10.1631/FITEE.2000203


Decentralized runtime enforcement for robotic swarms


Author(s):  Chi Hu, Wei Dong, Yong-hui Yang, Hao Shi, Fei Deng

Affiliation(s):  College of Computer Science, National University of Defense Technology, Changsha 410073, China; more

Corresponding email(s):   huchi16@nudt.edu.cn, wdong@nudt.edu.cn, shihao14@nudt.edu.cn

Key Words:  Runtime enforcement, Multi-level property, D-time enforcement, Robotic swarm


Chi Hu, Wei Dong, Yong-hui Yang, Hao Shi, Fei Deng. Decentralized runtime enforcement for robotic swarms[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(11): 1591-1606.

@article{title="Decentralized runtime enforcement for robotic swarms",
author="Chi Hu, Wei Dong, Yong-hui Yang, Hao Shi, Fei Deng",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="21",
number="11",
pages="1591-1606",
year="2020",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.2000203"
}

%0 Journal Article
%T Decentralized runtime enforcement for robotic swarms
%A Chi Hu
%A Wei Dong
%A Yong-hui Yang
%A Hao Shi
%A Fei Deng
%J Frontiers of Information Technology & Electronic Engineering
%V 21
%N 11
%P 1591-1606
%@ 2095-9184
%D 2020
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.2000203

TY - JOUR
T1 - Decentralized runtime enforcement for robotic swarms
A1 - Chi Hu
A1 - Wei Dong
A1 - Yong-hui Yang
A1 - Hao Shi
A1 - Fei Deng
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 21
IS - 11
SP - 1591
EP - 1606
%@ 2095-9184
Y1 - 2020
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.2000203


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.

机器人集群的去中心化运行时强制方法


胡驰1,董威1,杨永辉2,史浩1,邓霏2
1国防科技大学计算机学院,中国长沙市,410073
2中国工程物理研究院计算机应用研究所,中国绵阳市,621999

摘要:机器人系统设计通常是自下而上的,这种开发方式使机器人群体很容易受到环境影响。具体来说,目前广泛使用的集群控制模型不能保证宏观上群体任务的正确性,也不能保证微观上机器人节点间交互的安全性。因此,为确保机器人行为在运行时的安全性,有必要考虑机器人集群系统在不确定环境下的复杂性质。运行时强制技术能确保状态序列始终满足给定性质,并且避免状态爆炸的问题。虽然在其他领域出现了一些运行时强制的工作,但目前还不能解决机器人集群问题。本文通过引入宏观/微观性质强制框架、防护器以及一个离散时间的强制机制(discrete-time enforcement,D-time强制)解决该问题。论述了领域规约语言和强制器合成算法,然后,将此方法应用到一个机器人集群仿真工具robotflocksim中合成强制器。以无人机集群任务为例实现了该方法,并对实验效果进行讨论。

关键词:运行时强制;多层级性质;D-time强制;机器人集群

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Bauer A, Falcone Y, 2016. Decentralised LTL monitoring. Form Meth Syst Des, 48(1-2):46-93.

[2]Bloem R, Chatterjee K, Greimel K, et al., 2014. Synthesizing robust systems. Acta Inform, 51(3-4):193-220.

[3]Brambilla M, Ferrante E, Birattari M, et al., 2013. Swarm robotics: a review from the swarm engineering perspective. Swarm Intell, 7(1):1-41.

[4]Chung SJ, Paranjape AA, Dames P, et al., 2018. A survey on aerial swarm robotics. IEEE Trans Robot, 34(4):837-855.

[5]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.

[6]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.

[7]Egerstedt M, Lee SG, Diaz-Mercado Y, et al., 2020. Control of Swarming Robots. US Patent 10 537 996.

[8]Fine BT, Shell DA, 2013. Unifying microscopic flocking motion models for virtual, robotic, and biological flock members. Auton Robot, 35(2-3):195-219.

[9]Floreano D, Wood RJ, 2015. Science, technology and the future of small autonomous drones. Nature, 521(7553):linebreak 460-466.

[10]Gökc ce F, c Sahin E, 2009. To flock or not to flock: the pros and cons of flocking in long-range “migration” of mobile robot swarms. Proc 8st Int Joint Conf on Autonomous Agents and Multiagent Systems, p.65-72.

[11]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.

[12]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.

[13]Könighofer B, Alshiekh M, Bloem R, et al., 2017. Shield synthesis. Form Meth Syst Des, 51(2):332-361.

[14]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.

[15]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.

[16]Nagavalli S, Chien SY, Lewis M, et al., 2015. Bounds of neglect benevolence in input timing for human interaction with robotic swarms. Proc 10st Annual ACM/linebreak IEEE Int Conf on Human-Robot Interaction, p.197-204.

[17]Parr T, 2013. The Definitive ANTLR 4 Reference. Pragmatic Bookshelf, Dallas, USA, p.21-33.

[18]Pinisetty S, Preoteasa V, Tripakis S, et al., 2017. Predictive runtime enforcement. Form Meth Syst Des, 51(1):154-199.

[19]Pnueli A, 1977. The temporal logic of programs. Proc 18st Annual Symp Foundations of Computer Science, p.46-57.

[20]Pugh J, Martinoli A, 2006. Multi-robot learning with particle swarm optimization. Proc 5st Int joint Conf on Autonomous Agents and Multiagent Systems, p.441-448.

[21]Rajkumar R, Lee I, Sha L, et al., 2010. Cyber-physical systems: the next computing revolution. Proc 47st Design Automation Conf, p.731-736.

[22]Raju D, Bharadwaj S, Topcu U, 2019. Online synthesis for runtime enforcement of safety in multi-agent systems. https://arxiv.org/abs/1910.10380

[23]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.

[24]Reinbacher T, Rozier KY, Schumann J, 2014. Temporal-logic based runtime observer pairs for system health management of real-time systems. Proc 20st Int Conf on Tools and Algorithms for the Construction and Analysis of Systems, p.357-372.

[25]Reynolds CW, 1987. Flocks, herds and schools: a distributed behavioral model. ACM SIGGRAPH Comput Graph, 21(4):25-34.

[26]c Sahin 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.

[27]Schwager M, McLurkin J, Rus D, 2006. Distributed coverage control with sensory feedback for networked robots. Proc Robotics: Science and Systems, p.117-132.

[28]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.

[29]Sinhuber M, van der Vaart K, Ouellette NT, 2019. Response of insect swarms to dynamic illumination perturbations. J Roy Soc Interf, 16(150):20180739.

[30]Standley T, Korf R, 2011. Complete algorithms for cooperative pathfinding problems. Proc 22nd Int Joint Conf on Artificial Intelligence, p.668-673.

[31]Turgut AE, c Celikkanat H, Gökc ce F, et al., 2008. Self-organized flocking in mobile robot swarms. Swarm Intell, 2(2-4):97-120.

[32]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.

[33]Williams K, Burdick JW, 2006. Multi-robot boundary coverage with plan revision. IEEE Int Conf on Robotics and Automation, p.1716-1723.

[34]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.

[35]Zhang X, Leucker M, Dong W, 2012. Runtime verification with predictive semantics. Proc 4th Int Symp on NASA Formal Methods, p.418-432.

[36]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.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE