Decentralized Multirobot Control in Partially Known Environments with Dynamic Task Reassignment*

This paper provides a decentralized solution to multirobot coordination in partially-known environments where the problems of task assignment, trajectory planning and safe control are concurrently solved in the presence of communication constraints. We assume that the robots are homogeneous (any robot is capable of completing any assigned task), can localize themselves and have access to a known map of the environment, except for obstacles and hazards that cannot be circumvented and must be detected through local sensing. Second, we assume that only robots that are within a specified, known communication range can communicate. A group of communicating robots is able to reassign tasks within the group to refine and improve the resulting solution in terms of total time or energy required for traversal. The key contribution of this paper is an approach that concurrently solves the three typically separated problems of task assignment, path planning, and control under constraints with proofs of completeness and convergence. We illustrate the application of these ideas through simulations and experiments with applications to surveillance of multiple destinations.