Paper Info
Title
Approximate characterization of multi-robot swarm “shapes” in sublinear-time
Abstract
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.
Year
DOI
Venue
2011
10.1109/ICRA.2011.5980411
ICRA
Keywords
Field
DocType
differential geometry,multirobot swarm shape approximate characterization,bearing communication,topological properties,distributed algorithm,geodesic distance estimation,multi-robot systems,computational geometry,range communication,one-way message traversals,greedy algorithms,geometric properties,euclidean distance,greedy method,sublinear-time,approximation algorithms,robot kinematics,geodesic distance,shape,distance metric
Approximation algorithm,Mathematical optimization,Swarm behaviour,Control theory,Euclidean distance,Computational geometry,Robot kinematics,Algorithm,Greedy algorithm,Distributed algorithm,Robot,Mathematics
Conference
Volume
Issue
ISSN
2011
1
1050-4729
ISBN
Citations 
PageRank 
978-1-61284-386-5
5
0.49
References 
Authors
8
4
Name
Order
Citations
PageRank
Lantao Liu115716.49
Benjamin T. Fine2162.54
Dylan A. Shell333447.94
Andreas Klappenecker430437.23