Computer Science – Robotics
Scientific paper
2007-03-14
Computer Science
Robotics
2007 ACC paper including proofs; Corrected typos
Scientific paper
We are given an equal number of mobile robotic agents, and distinct target locations. Each agent has simple integrator dynamics, a limited communication range, and knowledge of the position of every target. We address the problem of designing a distributed algorithm that allows the group of agents to divide the targets among themselves and, simultaneously, leads each agent to reach its unique target. We do not require connectivity of the communication graph at any time. We introduce a novel assignment-based algorithm with the following features: initial assignments and robot motions follow a greedy rule, and distributed refinements of the assignment exploit an implicit circular ordering of the targets. We prove correctness of the algorithm, and give worst-case asymptotic bounds on the time to complete the assignment as the environment grows with the number of agents. We show that among a certain class of distributed algorithms, our algorithm is asymptotically optimal. The analysis utilizes results on the Euclidean traveling salesperson problem.
Bullo Francesco
Smith Stephen L.
No associations
LandOfFree
Target assignment for robotic networks: asymptotic performance under limited communication does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Target assignment for robotic networks: asymptotic performance under limited communication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Target assignment for robotic networks: asymptotic performance under limited communication will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-715739