center for robotics and embedded systems University of Southern California Viterbi School of Engineering

Existing task allocation and scheduling algorithms, including task-allocation algorithms for multi-robot systems, generally assume that tasks are independent.This assumption is often violated in groups of cooperative mobile robots, where the group dynamics can have a critical impact on performance. We present a multi-robot task allocation algorithm that is sensitive to group dynamics. Our algorithm is based on vacancy chains, a resource distribution process common in human and animal societies. We study the problem of cooperative transportation in simulation. We demonstrate through experiments in simulation that if robots keep local task utility estimates, and follow a greedy task selection policy, the interactions in the group cause the collection of learned policies to converge toward an optimal allocation pattern as defined by the vacancy chain framework. As the robots are continuously updating their individual utility estimates, the vacancy chain algorithm has the additional property of adapting automatically tochanges in the environment, e.g., robot breakdowns or changes in task values. Our experiments show that in the case of such changes, the vacancy chain algorithm consistently outperforms random and static task allocation algorithms.Finally, the vacancy chain algorithm uses no communication or unique roles, and as a result it is more likely to scale to large groups and will degrade gracefully in response to individual breakdowns.


Go Home
Maintained by webmaster