Distributed multi-robot task assignment and formation control
Nathan Michael, Michael M. Zavlanos, Vijay Kumar et al. · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · 2008
Distributed task assignment for multiple agents raises fundamental and novel problems in control theory and robotics. A new challenge is the development of distributed algorithms that dynamically assign tasks to multiple agents, not relying on a priori assignment information. We address this challenge using market-based coordination protocols where the agents are able to bid for task assignment with the assumption that every agent has knowledge of the maximum number of agents that any given task can accommodate. We show that our approach always achieves the desired assignment of agents to tasks after exploring at most a polynomial number of assignments, dramatically reducing the combinatorial nature of discrete assignment problems. We verify our algorithm through both simulation and experimentation on a team of non-holonomic robots performing distributed formation stabilization and group splitting and merging.
Cited by 223 works. doi:10.1109/robot.2008.4543197
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- The Hungarian method for the assignment problem
- Consensus Problems in Networks of Agents With Switching Topology and Time-Delays
- Coordination of groups of mobile autonomous agents using nearest neighbor rules
- The Player/Stage Project: Tools for Multi-Robot and Distributed Sensor Systems
- Flocking in Fixed and Switching Networks
- Robust Rendezvous for Mobile Autonomous Agents via Proximity Graphs in Arbitrary Dimensions
- Constrained coverage for mobile sensor networks
- Stabilization of Planar Collective Motion: All-to-All Communication
- A feedback stabilization and collision avoidance scheme for multiple independent non-point agents