This paper tackles the problem of parallelizing heterogeneous computational tasks across a number of computational nodes (aka agents) where each agent may not be able to perform all the tasks and may have different computational speeds. An equivalent problem can be found in operations research, and it is known as scheduling tasks on unrelated parallel machines (also known as R∥Cmax). Given this equivalence observation, we present the spanning tree decentralized task distribution algorithm (ST-DTDA), the first decentralized solution to R∥Cmax. ST-DTDA achieves decomposition by means of the min–max algorithm, a member of the generalized distributive law family, that performs inference by message-passing along the edges of a graphical model (known as a junction tree). Specifically, ST-DTDA uses min–max to optimally solve an approximation of the original R∥Cmax problem that results from eliminating possible agent-task allocations until it is mapped into an acyclic structure. To eliminate those allocations that are least likely to have an impact on the solution quality, ST-DTDA uses a heuristic approach. Moreover, ST-DTDA provides a per-instance approximation ratio that guarantees that the makespan of its solution (optimal in the approximated R∥Cmax problem) is not more than a factor ρ times the makespan of the optimal of the original problem. In our empirical evaluation of ST-DTDA, we show that ST-DTDA, with a min-regret heuristic, converges to solutions that are between 78 and 95% optimal whilst providing approximation ratios lower than 3.

We introduce a novel distributed algorithm for multi-agent task allocation problems where the sets of tasks and agents constantly change over time. We build on an existing anytime algorithm (fast-max-sum), and give it significant new capa- bilities: namely, an online pruning procedure that simplifies the problem, and a branch-and-bound technique that reduces the search space. This allows us to scale to problems with hundreds of tasks and agents. We empirically evaluate our algorithm against established benchmarks and find that, even in such large environments, a solution is found up to 31% faster, and with up to 23% more utility, than state-of-the-art approximation algorithms. In addition, our algorithm sends up to 30% fewer messages than current approaches when the set of agents or tasks changes.

Emergency responders are faced with a number of significant challenges when managing major disasters. First, the number of rescue tasks posed is usually larger than the number of responders (or agents) and the resources available to them. Second, each task is likely to require a different level of effort in order to be completed by its deadline. Third, new tasks may continually appear or disappear from the environment, thus requiring the responders to quickly recompute their allocation of resources. Fourth, forming teams or coalitions of multiple agents from different agencies is vital since no single agency will have all the resources needed to save victims, unblock roads and extinguish the fires which might erupt in the disaster space. Given this, coalitions have to be efficiently selected and scheduled to work across the disaster space so as to maximize the number of lives and the portion of the infrastructure saved. In particular, it is important that the selection of such coalitions should be performed in a decentralized fashion in order to avoid a single point of failure in the system. Moreover, it is critical that responders communicate only locally given they are likely to have limited battery power or minimal access to long-range communication devices. Against this background, we provide a novel decentralized solution to the coalition formation process that pervades disaster management. More specifically, we model the emergency management scenario defined in the RoboCup Rescue disaster simulation platform as a coalition formation with spatial and temporal constraints (CFST) problem where agents form coalitions to complete tasks, each with different demands. To design a decentralized algorithm for CFST, we formulate it as a distributed constraint optimization problem and show how to solve it using the state-of-the-art Max-Sum algorithm that provides a completely decentralized message-passing solution. We then provide a novel algorithm (F-Max-Sum) that avoids sending redundant messages and efficiently adapts to changes in the environment. In empirical evaluations, our algorithm is shown to generate better solutions than other decentralized algorithms used for this problem.