We describe a probabilistic framework for synthesizing control policies for general multi-robot systems, given environment and sensor models and a cost function. Decentralized, partially observable Markov decision processes (Dec-POMDPs) are a general model of decision processes where a team of agents must cooperate to optimize some objective (specified by a shared reward or cost function) in the presence of uncertainty, but where communication limitations mean that the agents cannot share their state, so execution must proceed in a decentralized fashion. While Dec-POMDPs are typically intractable to solve for real-world problems, recent research on the use of macro-actions in Dec-POMDPs has significantly increased the size of problem that can be practically solved as a Dec-POMDP. We describe this general model, and show how, in contrast to most existing methods that are specialized to a particular problem class, it can synthesize control policies that use whatever opportunities for coordination are present in the problem, while balancing off uncertainty in outcomes, sensor information, and information about other agents. We use three variations on a warehouse task to show that a single planner of this type can generate cooperative behavior using task allocation, direct communication, and signaling, as appropriate.
Market-based approaches use traded value to establish an optimization framework for task allocation @cite_37 @cite_19 . These approaches have been used to solve real multi-robot problems @cite_15 , but are largely aimed to tightly-coupled tasks, where the robots can communicate through a bidding mechanism.
@cite_19 @cite_37 @cite_15
2899936862 42384017 2157488300 2138104929
In this paper we present a reformulation--framed as a constrained optimization problem--of multi-robot tasks which are encoded through a cost function that is to be minimized. The advantages of this approach are multiple. The constraint-based formulation provides a natural way of enabling long-term robot autonomy applications, where resilience and adaptability to changing environmental conditions are essential. Moreover, under certain assumptions on the cost function, the resulting controller is guaranteed to be decentralized. Furthermore, finite-time convergence can be achieved, while using local information only, and therefore preserving the decentralized nature of the algorithm. The developed control framework has been tested on a team of ground mobile robots implementing long-term environmental monitoring. Existing approaches to multirobot coordination separate scheduling and task allocation, but finding the optimal schedule with joint tasks and spatial constraints requires robots to simultaneously solve the scheduling, task allocation, and path planning problems. We present a formal description of the multirobot joint task allocation problem with heterogeneous capabilities and spatial constraints and an instantiation of the problem for the search and rescue domain. We introduce a novel declarative framework for modeling the problem as a mixed integer linear programming (MILP) problem and present a centralized anytime algorithm with error bounds. We demonstrate that our algorithm can outperform standard MILP solving techniques, greedy heuristics, and a market based approach which separates scheduling and task allocation. 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. This paper presents a comparative study between three multirobot coordination schemes that span the spectrum of coordination approaches; a fully centralized approach that can produce optimal solutions, a fully distributed behavioral approach with minimal planned interaction between robots, and a market approach which sits in the middle of the spectrum. Several dimensions for comparison are proposed based on characteristics identified as important to multirobot application domains. Furthermore, simulation results are presented for comparisons along two of the suggested dimension: Number of robots in the team and Heterogeneity of the team. Results spanning different team sizes indicate that the market method compares favorably to the optimal solutions generated by the centralized approach in terms of cost, and compares favorably to the behavioral method in terms of computation time. All three methods are able to improve global cost by accounting for the heterogeneity of the robot team.