Distributed multi-robot task assignment and formation control

TLDR

Distributed task assignment for multiple agents raises fundamental and novel problems in control theory and robotics. The study aims to develop distributed algorithms that dynamically assign tasks to multiple agents without prior assignment information. The authors use market‑based coordination protocols that allow agents to bid for tasks, assuming each knows the task capacity limits, and validate the algorithm via simulation and experiments on non‑holonomic robots performing formation stabilization and group splitting/merging. Their approach always achieves the desired assignment after exploring at most a polynomial number of assignments, dramatically reducing the combinatorial nature of discrete assignment problems.

Abstract

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.