Approximate Characterization of Multi-Robot Swarm “Shapes in Sublinear-Time
Many envisioned applications of multi-robot swarms involve the detection, production or maintenance of global structures through only local means. This paper introduces a scalable, distributed algorithm to approximately characterize important global geometric and topological properties. For a given spatial arrangement of robots, the algorithm estimates the longest network (geodesic) distance in any direction as well as the average Euclidean distance only using locally sensed information. In so doing, the robots need only to communicate with and sense (range and bearing) nearby robots. The algorithm uses a greedy method to approximate both distance metrics via parallel one-way message traversals. We provide a bound for the number of such traversals, showing a global characterization is produced in a running time that is sublinear in the total number of robots. Along with this analysis, we conduct simulations with hundreds of robots to validate the algorithm.
Lantao Liu Benjamin Fine Dylan Shell Andreas Klappenecker
Dept. of Computer Science and Engineering Texas A&M University,College Station,TX,USA
国际会议
2011 IEEE International Conference on Robotics and Automation(2011年IEEE世界机器人与自动化大会 ICRA 2011)
上海
英文
2886-2891
2011-05-09（万方平台首次上网日期，不代表论文的发表时间）