MultiRobot Task Allocation
OverviewImportant theoretical aspects of mechanisms for multirobot task allocation have, to date, been largely ignored. In this project, we are trying to address part of this negligence by formally studying the problem within an organizational framework developed in the Operations Research community. In particular, we are currently exploring multirobot task allocation as an instance of the wellknown Optimal Assignment Problem. In this light, we have recently analyzed and compared the algorithmic characteristics of several existing approaches to the problem. IntroductionSince the early 1990s, the problem of task allocation in multirobot systems has received significant and increasing interest in the research community. As researchers design, build, and use cooperative multirobot systems, they invariably encounter the question: "which robot should execute which task?" This question must be answered, even for relatively simple multirobot systems, and the importance of task allocation grows with the complexity, in size and capability, of the system under study. Even in the simplest case of homogeneous robots with fixed, identical roles, intelligent allocation of tasks is required for good system performance, if only to minimize physical interference. Of course, task allocation need not be explicit; it may instead emerge from the interactions of the robots (physical and otherwise), as is the case with coordination methods put forward by proponents of swarm robotics. Such an emergent system, when constructed skillfully, can be extremely effective and may provide the simplest and most elegant solution to a problem. However, it is a solution to a {\em specific} problem, and if robots are to be generally useful, we believe that they must be capable of solving a variety of problems. Over the years, a significant body of work has been done on explicit multirobot task allocation (MRTA), generally involving taskoriented interrobot communication. A variety of such architectures have been proposed; while they are sometimes evaluated experimentally, they are rarely subject to formal analysis. It is coordination architectures of this type on which we are currently focusing our analysis. Our aim is to address two key shortcomings of the MRTA work to date:
Problem StatementWe claim that multirobot task allocation can be reduced to an instance of the Optimal Assignment Problem (OAP), a wellknown problem from Operations Research. A recurring special case of particular interest in several fields of study, this problem can be formulated in many ways. Given our application domain, it is fitting to describe the problem in terms of jobs and workers. There are n workers, each looking for one job, and m available jobs, each requiring one worker. The jobs can be of different priorities, meaning that it is more important to fill some jobs than others. Each worker has a nonnegative skill rating estimating his/her performance for each potential job (if a worker is incapable of undertaking a job, then the worker is assigned a rating of zero for that job). The problem is to assign workers to jobs in order to maximize the overall expected performance, taking into account the priorities of the jobs and the skill ratings of the workers. Our multirobot task allocation problem can be posed as an assignment problem in the following way: given n robots, m prioritized (i.e., weighted) singlerobot tasks, and estimates of how well each robot can be expected to perform each task, assign robots to tasks so as maximize overall expected performance. However, because the problem of task allocation is a dynamic decision problem that varies in time with phenomena including environmental changes, we cannot be content with this static assignment problem. Thus we complete our reduction by iteratively solving the static assignment problem over time. Of course, the cost of running the assignment algorithm must be taken into account. At one extreme, a costless algorithm can be executed arbitrarily fast, ensuring an optimal assignment over time. At the other extreme, an expensive algorithm that can only be executed once will produce a static assignment that is only initially optimal and will degrade over time. Finally there is the question of how many tasks are considered for (re)assignment at each iteration. In order to create and maintain an optimal allocation, the assignment algorithm must consider (and potentially reassign) every task in the system. Such an inclusive approach can be computationally expensive and, indeed, some implemented approaches to MRTA use heuristics to determine a subset of tasks that will be considered in a particular iteration. Together, the cost of the static algorithm, the frequency with which it is executed, and the manner in which tasks are considered for (re)assignment will determine the overall computational and communication overhead of the system, as well as the solution quality. Thus it is these characteristics of MRTA architectures in which we are interested and that we are currently analyzing. UtilityUtility is a unifying, if sometimes implicit, concept in economics, game theory, and operations research, as well as multirobot coordination. The idea is that each individual can somehow internally estimate the value (or the cost) of executing an action. It is variously called fitness, valuation, and cost. Since the exact formulation varies from system to system, we now give an instructive and generic, yet practical, definition of utility for multirobot systems. We assume that each robot is capable of estimating its fitness for every task of which it is capable. This estimation includes two factors, both task and robotdependent:
The robots' utility estimates will be inexact for a number of reasons, including sensor noise, general uncertainty, and environmental change. These unavoidable characteristics of the multirobot domain will necessarily limit the efficiency with which coordination can be achieved. We treat this limit as exogenous, on the assumption that lowerlevel robot control has already been made as reliable, robust, and precise as possible and thus that we are incapable of improving it. When we later discuss "optimal" allocation solutions; we mean "optimal" in the sense that, given the union of all information available in the system (with the concomitant noise, uncertainty, and inaccuracy), it is impossible to construct a solution with higher overall utility. Note that although we have not discussed planning or learning, our definition of utility permits their introduction. The addition of a predictive model, for example, will (presumably) improve the accuracy of utility estimates by considering expected future events. To achieve the best system performance, such techniques should be used whenever possible. AnalysisHaving given a formal statement of the MRTA problem, we are now in a position to analyze some of the key task allocation architectures from the literature. We have recently analyzed six approaches to MRTA, focusing on three characteristics:
In part because of trends in the research community that stress the importance of experimental validation with physical robots, such theoretical aspects of multirobot coordination mechanisms have been largely ignored. However, they are vitally important to the study, comparison, and objective evaluation of the mechanisms. The largescale and longterm behavior of the system will be strongly determined by the fundamental characteristics of the underlying algorithm(s). Thus we endeavor to derive and explicate those characteristics here. Before we continue, however, it will be necessary to explain the methodology that we use in our analysis. MethodologyAs we stated earlier, the key to effective task allocation for multirobot systems is to iterate the assignment, in order to deal with changes in the tasks, the robots, and the environment. The architectures under study achieve this iteration in different ways, along two dimensions. First, while some approaches allow assignment and reassignment of all tasks at each iteration, some never reassign tasks (or at least only reassign them because of robot failure). Second, some approaches periodically consider all tasks simultaneously, while others consider single tasks sequentially as they are offered for (re)assignment. Thus, when we discuss complexities, we state them in terms of iterations, though the details of an "iteration" may vary across architectures. We determine computation requirements, or running time, in the usual way, as the number of times that some dominant operation is repeated. For our domain that operation is usually either a calculation or comparison of utility, and running time is stated as a function of n and m, the numbers of robots and tasks, respectively. Since modern robots have significant processing capabilities onboard and can easily work in parallel, we assume that the computational load is evenly distributed over the robots, and state the running time as it is for each robot. For example, if we need to find for each robot the task with the highest utility, then the running time is O(m), because each robot performs m comparisons, in parallel. We determine communication requirements as the total number of interrobot messages sent over the network. We do not consider message sizes, on the assumption that they are generally small (e.g., single scalar utility values) and approximately the same for different algorithms. We also assume that a perfect shared broadcast communication medium is in use and that messages are always broadcast, rather than unicast. So if, for example, each robot must tell every other robot its own highest utility value then the overhead is O(n), because each robot makes a single broadcast.ResultsSee the paper listed below.Relevant Publications
