Market-Based Multirobot Coordination: A Comprehensive Survey and Analysis

Abstract

As robotic technology improves, we charge robots with increasingly varied and difficult tasks. Many of these tasks can potentially be completed better by a team of robots working together than by individual robots working alone. Coordination can lead to faster task completion, increased robustness, higher-quality solutions, and the completion of tasks impossible for single robots. Nevertheless, effective coordination can be difficult to achieve because of a range of adverse real-world conditions including dynamic events, changing task demands, resource failures, and limited deliberation time. The desire to overcome these challenges and harness the benefits of robot teams has made multirobot coordination a vital field in robotics research. Of the resulting wealth of research, market-based multirobot coordination approaches in particular have received significant attention and are growing in popularity within the community. These approaches harness the principles of market economies—which have successfully governed human coordination for thousands of years—and use them to enable robot coordination. In market-based approaches, robots on the team act as self-interested agents operating in a virtual economy in which tasks and team resources are exchanged over the market in pursuit of individual profit. The essence of market-based approaches is that the process of robots trading tasks and resources with one another to maximize their wealth simultaneously improves the efficiency of the team. Market-based approaches to multirobot coordination inherit many of the benefits associated with market economies, including flexibility, efficiency, responsiveness, robustness, scalability, and generality. In practice, they have been successfully implemented in a variety of domains ranging from mapping and exploration to robot soccer. The research literature on market-based approaches to coordination has now reached a critical mass that warrants a survey and analysis. This paper meets this need in three ways. First, it provides a tutorial on market-based approaches by discussing the motivating philosophy, defining the requirements and tradeoffs inherent in such approaches, analyzing their strengths and weaknesses, and placing them appropriately in the context of the larger set of approaches to multirobot coordination. Second, this paper surveys and analyzes the relevant literature. Third, it inspires and directs future research on this topic through a discussion of remaining challenges.