Distributed multi-robot task assignment and formation control

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.

Authors

• Nathan Michael
• Michael M. Zavlanos
• Vijay Kumar 0001
• George J. Pappas

Keywords

• Robot kinematics
• Polynomials
• Distributed control
• Cost function
• Robotics and automation
• USA Councils
• Automatic control
• Control theory
• Distributed algorithms
• Protocols
• Formation Control
• Distributed Algorithm
• Assignment Problem
• Swarm Robotics
• Experimental Design
• Simulation Results
• Optimal Control
• Coded Based
• Experimental Environment
• Auction
• Final Design
• Limited Communication
• Task Environment
• Local Communication
• Network Delay
• Bidding Process
• Minimum Rule