Distributed Intelligence : Overview of the Field and its Application in Multi-Robot Systems <s> Contrasting Paradigms for a Typical Multi-Robot Challenge: Task Allocation <s> We present and discuss a distributed scheme for multi-robot cooperation. It integrates mission planning and task refinement as well as cooperative mechanisms adapted from the contract net protocol framework. We discuss its role and how it can be integrated as a component of a complete robot control system. We also discuss how it handles distributed task allocation and achievement as well as cooperative reaction to contingencies. Finally, we illustrate its use through a simulated system, which allows a number of robots to perform load transfer tasks in a route network environment. <s> BIB001 </s> Distributed Intelligence : Overview of the Field and its Application in Multi-Robot Systems <s> Contrasting Paradigms for a Typical Multi-Robot Challenge: Task Allocation <s> Despite more than a decade of experimental work in multi-robot systems, important theoretical aspects of multi-robot coordination mechanisms have, to date, been largely untreated. To address this issue, we focus on the problem of multi-robot task allocation (MRTA). Most work on MRTA has been ad hoc and empirical, with many coordination architectures having been proposed and validated in a proof-of-concept fashion, but infrequently analyzed. With the goal of bringing objective grounding to this important area of research, we present a formal study of MRTA problems. A domain-independent taxonomy of MRTA problems is given, and it is shown how many such problems can be viewed as instances of other, well-studied, optimization problems. We demonstrate how relevant theory from operations research and combinatorial optimization can be used for analysis and greater understanding of existing approaches to task allocation, and show how the same theory can be used in the synthesis of new approaches. <s> BIB002
Having explored three common paradigms in systems of distributed intelligence, we now briefly compare and contrast these paradigms in their approach to a common challenge in multi-robot systems -that of task allocation. As previously introduced, task allocation arises in many multi-robot applications in which the mission of the team is defined as a set of tasks that must be completed. Each task can usually be addressed by a variety of different robots; conversely, each robot can usually work on a variety of different tasks. Independent tasks can be achieved concurrently, while dependent tasks must be achieved according to their interdependence constraints. Once the set of tasks has been defined, the challenge is to determine the preferred mapping of robots to tasks that optimizes some objective function. This is the task allocation problem. The general task allocation problem is known to be NP-hard BIB002 , meaning that optimal solutions cannot be found quickly for large problems. Therefore, solutions to this problem are typically approximations that are acceptable in practice. Let us examine how each of the paradigms we have discussed would handle the multi-robot task allocation problem. First, the bioinspired approach to task allocation would typically assume large numbers of homogeneous robots that are all interchangeable. In this situation, any robot that is available and senses the need for a task to be performed can select to perform that task (i.e., the task is allocated to that robot). Because of stigmergy, robots do not have to explicitly communicate in order to determine which task to undertake. Robots that fail can be replaced by any other available robot. If all robots operate under this principle, then the entire mission is typically accomplished. Second, an organizational approach to task allocation would make use of roles, as we described previously for multi-robot soccer. Each role encompasses several specific tasks, and robots select roles that are best suited for their capabilities. In this case, robots need not be homogeneous, but instead can have a variety of different sensing, computation, and effector capabilities. An alternative organizational approach to task allocation is the market-based approach also mentioned previously. In these approaches, robots explicitly communicate to bid for tasks according to their expected contribution to those tasks. Assignments are typically made by greedily assigning each task to the robot that can perform it with the highest utility. The fundamental paradigm for interaction in this case is based upon the Contract Net Protocol  , which was the first to address the problem of how agents can negotiate to collectively solve a set of tasks. The use of a market-based approach specifically for multi-robot task allocation was first developed in the M+ architecture BIB001 . In the M+ approach, robots plan their own individual plans for the task they have been assigned. They then negotiate with other teammates to incrementally adapt their actions to suit the team as a whole, through the use of social rules that facilitate the merging of plans. Finally, the knowledge-based approach is also used for task allocation in multi-robot teams, through the modeling of teammate capabilities. Many variations are possible, such as in the ALLIANCE approach  , in which robots model the ability of team members to perform the tasks of the system by observing team member performance and collecting relevant task quality statistics, such as time to task completion. Robots then use these models to select tasks to perform that benefit the group as a whole. In this approach, explicit communication is not required for the selection of task assignments. Other techniques are also possible that make use of learned models of teammate capabilities. As we see through these task allocation examples, a specific problem in multi-robot systems can be addressed in many different ways, based upon the paradigm selected for abstracting the problem at hand. Each paradigm has its own advantages and disadvantages, which may be specific to the application. The paradigms are therefore not interchangeable for many applications, with the most suitable approach depending upon the relevant constraints and requirements of the application.