Multi-Robot Coordination in Complex Environment with Task and Communication Constraints

The tasks would fail to be assigned to any robots in the task allocation phase as a consequence of the inherent communication constraints in multi-robot systems (MRS). This negative effect becomes even more serious in tasks with temporal constraints. We therefore propose the constraint-based approach (CoBA), a market-based task allocation approach to enable multi-robot coordination in domains with temporal constraints between subtasks of a complex task and network constraints between robots. We handle network constraints by having each robot maintain a dynamic acquaintance network of robots that it knows about, and allowing a robot to submit a bid on behalf of another robot during a task auction (indirect bidding). In order to model the complex task, we introduce the AND/OR task tree with temporal constraints. An auction-clearing routine, which supports the AND/OR task tree with temporal constraints and direct/indirect task auction, is proposed to enable effective multi-robot task allocation in spite of various constraints. The solution was validated in both simulation and physical environments by a series of experiments in disaster response domains. Specifically, we study the system performance by separately varying the number of robots, the expected rate of task issuance, the communication reliability factor, the compositions of MRS, as well as the acquaintance relationship parameter, in simulation experiments. The results suggest that our solution outperforms others, that is, robots were able to complete the tasks more promptly and effectively.