A Complete Methodology for Generating Multi-Robot Task Solutions using ASyMTRe-D and Market-Based Task Allocation

This paper presents an approach that enables heterogeneous robots to automatically form groups as needed to generate both strongly-cooperative and weakly-cooperative multi-robot task solutions in the same application. The fundamental contribution of this work is the layering of our low-level coalition formation algorithm for generating strongly-cooperative task solutions, with high-level, traditional task allocation methods for weakly-cooperative task solutions. At the low level, coalitions that generate strongly-cooperative multi-robot task solutions are formed using our ASyMTRe-D approach that maps environmental sensors and perceptual and motor schemas to the required flow of information in the robot team, automatically reconfiguring the connections of schemas within and across robots to form efficient solutions. At the high level, a traditional task allocation approach is used to enable individual robots and/or coalitions to compete for weakly-cooperative task assignments through task allocation. We introduce the site clearing task to motivate the work, and then formalize the problem. We then present the approach of layering ASyMTRe-D with task allocation. We validate the approach on a team of robots with the site clearing task. We believe the resulting approach is a flexible system that can handle a broad range of realistic multi-robot applications beyond what is possible using other existing approaches.