Abstract
In the field of mobile robotics, the study of multi-robot systems (MRSs) has grown significantly in size and importance in recent years. Having made great progress in the development of the basic problems concerning single-robot control, many researchers shifted their focus to the study of multi-robot coordination. This paper presents a systematic survey and analysis of the existing literature on coordination, especially in multiple mobile robot systems (MMRSs). A series of related problems have been reviewed, which include a communication mechanism, a planning strategy and a decision-making structure. A brief conclusion and further research perspectives are given at the end of the paper.
1. Introduction
Multi-robot systems (MRSs) are an important part of robotics research. In the late 1980s, a group of scientists began investigating this direction of research. A series of projects have been realized successfully, such as ACTRESS [1], GOFER [2], CEBOT [3], ALLIANCE [4], M+ [5], MURDOCH [6] and ASyMTRe [7]. One of the major challenges for MRSs is to design appropriate coordination strategies between the robots that enable them to perform operations efficiently in terms of time and working space.
Most of today's robots fall into one of three primary categories, namely manipulators, mobile robots and humanoid robots. This paper focuses on multiple mobile robot systems (MMRSs), in which robots should work together to accomplish a given task by moving around in the environment. We should be careful not to confuse MRSs with multi-agent system (MASs) and distributed artificial intelligence (DAIs), because MAS usually refers to the traditional distributed computer system in which individual nodes are stationary, and the DAI field is primarily concerned with problems involving software agents. In contrast, the area of MRS involves mobile robots that can move in the physical world and must interact with each other physically [9].
So far, a number of papers have been published regarding the research review, taxonomy and survey analysis for MRS. Dudek et al. [8] presented a taxonomy that classifies MASs according to communication, computational capacity and certain other capabilities. They also presented additional results concerning the MAS to illustrate the usefulness of the taxonomy and demonstrate that a collective can be more powerful than a single unit of the collective. Cao et al. [9] gave a critical survey of the cooperative mobile robotics literature up to the mid-1990s. They synthesized five research axes that were: group architecture, resource conflict, origin of cooperation, learning and geometric problems. They also discussed the constraints arising from technological limitations and possible lacunae in existing works. Stone and Veloso [10] presented four multi-agent scenarios: homogeneous non-communicating agents, heterogeneous non-communicating agents, homogeneous communicating agents and heterogeneous communicating agents. They illustrated the scenarios by using the pursuit domain and described existing works in the field. The techniques presented are biased towards machine learning approaches. Arai et al. [11] identified seven primary research topics within the MRS: biological inspirations, communication, architectures, localization / mapping / exploration, object transport and manipulation, motion coordination, and reconfigurable robots. They also discussed a number of special issue articles and suggested several additional research issues. Farinelli et al. [12] presented a survey of works up to the early 2000s in the area of cooperation and coordination in MRS. Moreover, they proposed a taxonomy for classification focused on coordination that is characterized by two groups of dimensions: coordination dimensions and system dimensions. Other works on the review of the MRS include [13] [14] [15] [16] [17].
The main contributions of this paper are threefold: 1) a systematic review about the problems of multi-robot coordination is conducted and the relationship between them is clearly indicated; 2) a detailed classification and comparison is conducted for each related problem; 3) an analysis of the coordination problems, especially from the perspective of multi-robot task planning and motion planning, is conducted.
The remainder of the paper is organized as follows: Section 2 describes MRSs as compared with single-robot systems; Section 3 describes two multi-robot environments: cooperative and competitive; Section 4 discusses the inherent problem of MRSs: resource conflict; Section 5 discusses the key to gaining the benefits of MRSs: coordination; Section 6 presents two types of communication mechanism: explicit and implicit; Section 7 discusses the problem of planning based on coordination, which includes task planning and motion planning; Section 8 presents two decision-making mechanisms: centralized and decentralized; the paper is concluded with a discussion in 9.
2. Robotic Systems: Single-robot Versus Multi-robot
A single-robot system contains only one individual robot that is able to model itself, the environment and their interaction [10]. Several individual robots are well known, such as RHINO [18], ASIMO [19], MER-A [20], BigDog [21], NAO [22] and PR2 [147]. The robot in a single-robot system is often designed to deal with a task on its own account. Such robots are usually integrated with multiple sensors, which themselves need a complex mechanism and an advanced intelligent control system. Although a single-robot system give have a relatively strong performance, some tasks may be inherently too complex or even impossible for it to perform, such as spatially separate tasks. For example, Dudek et al. [8] gave an example of a missile launch task that requires some sort of synchronization: there are two keys separated by a large distance in space that need to be activated simultaneously. Hence, an inherent restriction to the single-robot system is that it is spatially limited.
A MRS contains more than one individual robot, whether group homogeneous or heterogeneous. Using a MRS can have several potential advantages over a single-robot system:
A MRS has a better spatial distribution.
A MRS can achieve better overall system performance. The performance metrics could be the total time required to complete a task [23] or the energy consumption of the robots [24].
A MRS introduces robustness that can benefit from data fusion and information sharing among the robots, and fault-tolerance that can benefit from information redundancy. For example, multiple robots can localize themselves more efficiently if they exchange information about their position whenever they sense each other [25] [26] [27].
A MRS can have a lower cost. Using a number of simple robots can be simpler (to program), cheaper (to build) than using a single powerful robot (that is complex and expensive) to accomplish a task.
A MRS can exhibit better system reliability, flexibility, scalability [161] and versatility. Robots with diverse abilities can be combined together to deal with complex task, and one or several robots may fail without affecting the task completion.
A MRS can be homogeneous or heterogeneous. In homogeneous robot teams, the capabilities of the individual robots are identical (physical structures do not need to be the same). Some works considering the use of homogeneous robot teams include [28] [29] [30] [31] [24]. In heterogeneous robot teams, the capabilities of robots are different, whereby robots can be specialized for specific tasks. Some works considering the use of heterogeneous robot teams include [1] [4] [6] [27] [32] [159] [167]. In general, heterogeneous systems are more complex than homogeneous systems because the task planning becomes more difficult (see Section 7.1 below for more details).
3. Multi-robot Environment: Cooperative Versus Competitive
Like human society, there is collective behaviour in multi-robot environments. Popenoe [33] defined collective behaviour as follows: collective behaviour is behaviour that occurs in response to a common influence or stimulus in relatively spontaneous, unpredictable, unstructured and unstable situations. The collective behaviour includes cooperative behaviour and competitive behaviour. In other words, multi-robot environments can be cooperative or competitive [34]. Cooperation refers to a situation whereby multiple robots need to interact together in order to complete a task while increasing the total utility of the system. Alternatively, cooperation is the interaction between the robots, which work towards a common interest or reward [35]. The cooperative robots have a joint goal, which gives rise to various sub-goals. This subject involves the multi-robot planning problem, which we will discuss in more detail in Section 7. There are several representative examples of multi-robot cooperation, such as multi-robot localization [25] [26] [27] [36] [149] [161], multi-robot exploration [23] [37] [29] [38] [39] [40] [41] [42] [43] [44] [159] [164], multi-robot search and rescue [45] [46] [47] [30], and multi-robot transportation [48] [28] [24] [49] [59].
Competition refers to a situation whereby robots compete against each other to best fulfil their own self-interest. Alternatively, robots with conflicting utility functions are in competition with each other [34]. The competitive behaviour is the opposite of cooperative behaviour. Typical examples of multi-robot competition are two-player zero-sum games such as chess [50] and robot soccer leagues, such as RoboCup [51]. A multi-robot environment, cooperative or competitive, will need some sort of consensus (a communication mechanism, see Section 6) and a decision-making mechanism (see Section 8). This paper only discusses the problem of cooperation. The problem of competition is beyond the scope of this paper.
Robots might be selfish from the sociological point of view, because a single robot tends to make decisions motivated by self-preservation. For instance, consider two robots moving in opposite directions and wanting to cross a narrow passage, but where only one may cross at a time. If the two robots move simultaneously, a congestion or collision will occur. The cooperation can overcome groupthink and individual cognitive bias, and this requires some form of coordination. Such coordination can be achieved by communication, which is often used as a rational behaviour in multi-robot environments. The paper will discuss the coordination in detail in Section 5, and the communication in Section 6.
4. Inherent Problem: Resource Conflict
Generally, if multiple requests targeting the same resource arrive simultaneously, resource conflict will occur. This issue has been studied in many forms. A well-known case of a general resource conflict problem is the mutual exclusion problem [52] in distributed computing systems or multi-access networks, where only a single resource is available. In MMRS, resource conflict arises when multiple robots need to share space, manipulable object or communication media. To deal with this problem, we need to coordinate the robots. This coordination can be reflected in a plan (i.e., task planning and motion planning).
As previously mentioned, communication is important for a MRS because it can help robots to be cooperative by learning information that is observed or inferred by others. Explicit communication (another means is implicit communication) must use communication media. However, the communication media cannot always be shared, therefore it is necessary for the robots to obtain exclusive access to them. The problem of communication media sharing is often associated with bandwidth limitation. Ye et al. [53] presented a method to evaluate control and communication strategies for a group of wireless-networked robots. In this method, they used a network simulator [148] to handle the bandwidth limitation problem, which took into account protocol characteristics and propagation conditions. Rybski et al. [54] described a distributed software control architecture designed for the control of multiple robots over a low-bandwidth communications channel. In this architecture, robots share communication bandwidth by using the time slot (time-division multiplexing). They also showed how sharing bandwidth affects the performance of the robots when they are used in a surveillance task. Nerurkar et al. [149] presented a hybrid estimation framework for the problem of multi-robot cooperative localization under a very low bandwidth. Their framework allows each robot to communicate only a single bit per real-valued (analogue) measurement. Other works include [55] [56] [57] [150].
Another resource conflict arises when multiple robots need to manipulate the same object. A well-studied topic for object sharing is the multi-robot box-pushing problem, in which robots should work together to transport a box to a destination. Matarić et al. [58] addressed the problem of cooperative box-pushing with two autonomous six-legged robots. They presented a strategy whereby the robots need to communicate with each other to take turns controlling the actions at each time step in order to coordinate the delivery of the box to the goal. Kube and Bonabeau [59] presented empirical observations of cooperative transport in ants and robots, and described a case study of pushing a box with a swarm of robots that are controlled by using a finite-state machine (FSM). Coordination is achieved without any direct inter-robot communication. Gerkey and Matarić [60] presented a box-pushing experiment with a heterogeneous robot team by using an auction-based task-allocation system called MURDOCH. This system is able to allocate and coordinate manipulation tasks in a fault-tolerant manner, showing a tightly coupled cooperation among the robots. Miyata et al. [61] proposed a task assignment method for cooperative transport by multiple mobile robots in an unknown static environment. This method divides a robot's actions into small units of work to perform and assign tasks by considering whether an adequate number of robots is available for cooperation, and whether the time-space distributions of the task instances and the robots are adequate. Wang and Silva [151] employed two types of multi-agent reinforcement learning algorithms, single-agent Q-learning and team Q-learning, for a multi-robot box-pushing task. They showed that single-agent Q-learning does a better job than team Q-learning in a complicated and unknown environment with many obstacles. Other works include [62] [63] [64] [65] [66].
The third type of resource conflict is the space sharing problem, which has been studied mainly in relation to multi-robot motion planning collision, congestion and deadlock avoidance problems (a detailed discussion is given in Section 7.2). Jäger and Nebel [67] described a decentralized method for coordinating the independently planned trajectories of multiple mobile robots to avoid collisions and deadlocks among them. Their idea is: for the collision, when the distance between two robots drops below a certain value, they will exchange information about their planned trajectories and determine whether they are in danger of a collision or not. If a potential collision is detected, they will monitor their movements and, if necessary, insert time gaps between certain segments of their trajectories to avoid collision. For the deadlock, when a deadlock is detected, the trajectory planners of each robot involved are successively asked to plan an alternative trajectory until the deadlock is resolved. Marcolino and Chaimowicz [69] proposed a decentralized coordination algorithm to control the traffic of a swarm of robots while avoiding congestion situations when large groups of robots move in opposite directions. The proposed algorithm allows the robots to perceive the possibility of collision and warn their teammates through local sensing and communication, following which the group's members change their trajectories to avoid congestion. They also proposed another coordination algorithm for the control of traffic when robots try to reach the same target, where the robots control their actions by using a probabilistic finite state machine and continuously rely on local sensing and communication to coordinate themselves [70]. Tuna and Bekris [71] proposed a graph-based algorithm for multi-robot path planning problems in which there are at most n-2 robots in a connected graph of n vertices. The proposed algorithm uses two primitives: “push”, where a robot moves toward its goal until no progress can be made, and “swap”, which allows two robots to swap positions without altering the position of any other robot. Other works include [68] [72] [73] [74] [75] [76] [77] [78] [152] [153] [154] [157].
Our latest investigations focus on the space sharing problem. A very common situation in motion planning for a group of mobile robots is when multiple robots move to the same waypoint, leading to collision, congestion and deadlock. We have defined this kind of dynamic standstill of a system caused by waypoint conflict as a waiting situation problem. This is because, in solving this problem, a robot should wait until the others pass the waypoint first or else all the robots should wait for the planner to re-plan their trajectories. However, these solutions may compromise the MRS system's performance.
In our previous work, we focused on how to alleviate the waiting situation problems by planning separate kinematic paths for mobile robots. We presented a method involving the iterative sampling of an occupancy grid map to construct a separate topological graph for robots [43]. We also presented another method by using a probabilistic roadmap (PRM) based on adaptive cross-sampling (ACS) [79]. This method, which we called ACS-PRM, includes three steps: C-space sampling roadmap building and motion planning. Firstly, an adequate number of points should be generated in the C-space on an occupancy grid map by using an ACS method. Secondly, a separated roadmap should be built while the milestones are extracted by post-processing the result of sampling. Finally, robots plan their motion by querying the constructed roadmap.
5. Coordination: Static Versus Dynamic
Multi-robot coordination is the core task of MRSs. The overall system performance can be directly affected by the quality of coordination and control. Coordination can be static or dynamic. Static coordination (also known as deliberative coordination [14] or offline coordination [13]) generally refers to the adoption of a convention prior to engaging in the task. For example, some rules in traffic control problems include “keep right”, “stop at intersection” and “keep sufficient space between yourself and the robot in front of you” [80]. Dynamic coordination (also known as reactive coordination [14] or online coordination [13]) occurs during the execution of a task, and is generally based on the analysis and synthesis of information. The information can be obtained through the means of communication.
Dynamic coordination can also be divided into two categories: explicit coordination and implicit coordination. Gerkey and Matarić [81] defined explicit coordination as techniques employing intentional communication and collaboration methods, much like those employed in MAS (which is often used to deal with comparatively more sophisticated robots), and implicit coordination as those techniques employing the dynamics of interaction among the robots and the environment in order to achieve the desired collective performance, which is often in the form of designed emergent behaviour. Explicit coordination is usually associated with explicit communication, which is produced by a robot's active behaviour. Implicit coordination is usually associated with implicit communication, which requires the robot to perceive, model and reason others' behaviour. Fusing explicit and implicit information appropriately could improve the coordination performance of the whole robotic system. Both explicit and implicit communications will be discussed in detail in Section 6.
The static method can handle complex tasks, but its real-time controlling might be poor. The dynamic method can well meet the capability of real-time, but it has difficulty in dealing with more complex tasks. For MMRS, the external environment where the robots are placed may be too complex. It would be difficult to use only one method coping with all tasks. In our opinion, it would be best to use it by combining both the static and dynamic methods appropriately, based on the specific characteristics of the task at hand.
Current research on the theoretical aspects of the multi-robot coordination is not numerous. Agmon et al. [155] discussed three coordination mechanisms in the problem of a multi-robot patrol, including no coordination, loose coordination and tight coordination. They showed that an uncoordinated patrol performed better than a loosely coordinated patrol in terms of the average waypoint visitation frequency, and that tight coordination is theoretically optimal but it is not practical in practice. Kaminka et al. [166] presented a reinforcement learning approach to multi-robot coordination algorithm selection. They defined a reward function in the approach - called an effectiveness index - which can reduce the time and resources spent coordinating and maximize the time between conflicts that require coordination.
6. Communication: Explicit Versus Implicit
Communication, as a means of coordination, often emerges as a rational behaviour in multi-robot environments. In fact, the communication is a mode of interaction between robots. By this interaction, on the one hand, robots can share position information, the state of the environment and sensor data with others in the system; on the other hand, an individual robot can get information as to the intentions, goals and actions of other robots.
Cao et al. [9] classified the communication structure into three types according to the mode of interaction, which includes: interaction via the environment, interaction via sensing and interaction via explicit communications. Farinelli et al. [12] distinguished two different types of communication depending on the way in which the robots exchange information, which includes direct and indirect communication. In this paper, we follow the taxonomy based on the information transfer modes, namely explicit and implicit communication.
Explicit communication refers to the means for the direct exchange of information between the robots, which can be made in the form of unicast or broadcast intentional messages. This often requires a dedicated on-board communication module. Existing coordination methods are mainly based on the use of explicit communication. Balch and Arkin [82] presented a behaviour-based formation control strategy for multi-robot teams. In order to communicate with the formation's unit-centre, each robot communicates its position to the other over a wireless network. Gerkey and Matarić [83] presented a general framework of inter-robot communication for dynamic task allocation for teams of cooperative mobile robots. Klavins [84] introduced a notion of communication complexity as a means to investigate the scalability of multi-robot algorithms in terms of how much coordination they require. Madhavan et al. [27] described an extended Kalman filter-based algorithm for the localization of a team of robots through a wireless local area network. Nett and Schemmer [85] presented an architecture based on wireless communication to schedule the intersection of two paths in real-time so that mobile robots could cross the intersection efficiently without collisions. Wang et al. [86] presented an ad hoc robot wireless communication scheme for a large system with many mobile robots to exchange information. Pimentel and Campos [87] developed an algorithm that enables a group of cooperating mobile robots to establish and maintain a wireless ad hoc network to exchange task-related data. Rekleitis et al. [88] examined the problem of multi-robot coverage path planning for a team of robots with limited communication, where the robots operate under the restriction that communication between two robots is only available when they are within the line of sight of each other. Berna-Koes et al. [89] focused on an agent communication language (ACL) and described a two-tiered communication architecture. Rooker and Birk [90] presented an approach for multi-robot exploration that took the constraints of wireless networking into account. Bicchi et al. [32] proposed a platform for decentralized multi-robot traffic control with secure communication among vehicles by using cryptographic keys and rekeying policies. Bayram and Bozma [91] presented an approach for the navigation of dynamically communicating robots via a bidirectional interaction model between the robot network and the continuous states. Other works based on explicit communication include [92] [93] [94] [95] [96] [97] [98] [158] [161].
Implicit communication refers to the way in which the robot gets information about other robots in the system through the environment. This should be achieved by embedding different kinds of sensors in the robot. Implicit communication can also be divided into two categories: active implicit communication (e.g., interaction via the environment) and passive implicit communication (e.g., interaction via sensing). Active implicit communication refers to the fact that the robots communicate by collecting the remaining information of others in the environment. The use of this form is generally related to the field of biomimetics, and is usually inspired by the collective behaviour of bees and ants. Passive implicit communication refers to the fact that the robots communicate by perceiving a change of environment through the use of sensors. For example, a robot needs to compute the context information (e.g., position and attitude) of others by modelling and reasoning based on the perceived data in order to cooperate with them. Pagello et al. [99] presented an approach for coordinating a team of soccer playing robots through implicit communication where the cooperation between the robots was based on the form of the observed behaviour of other robots. Stulp et al. [100] presented a computational model for implicit coordination and applied it to a typical coordination task of robotic soccer: regaining ball possession. Yamada and Saito [63] described an adaptive action selection method without explicit communication for dynamic multi-robot box-pushing. Pereira et al. [65] addressed the problem of coordinating multiple mobile robots for a box-carrying task by using only local sensor information. Hollinger et al. [101] presented an approximation algorithm using implicit coordination to solve the multi-robot efficient search path-planning problem in indoor environments with a known floor plan. Other works based on implicit communication include [58] [102].
The use of explicit communication can ensure the accuracy of the exchange of information between robots. However, the communication load of a system will increase as the number of robots increases. This may cause a decrease in system performance or else lead to an overall system failure in extreme cases. In using implicit communication, and although the information obtained by a robot is not completely reliable, the stability, reliability and fault tolerance of the whole MRS are better than in using an explicit pattern. Therefore, applying both explicit and implicit methods in practice can make the two methods complement each other.
7. Planning: Task Planning and Motion Planning
The task of coming up with a sequence of actions that will achieve a goal is called ‘planning’ [34]. In MRS, planning can be used to coordinate robots in accomplishing the team mission. Unfortunately, the optimal planning for a MRS is typically an NP-hard problem. Therefore, the current challenge is to ensure tractable planning that produces good solutions [103]. Multi-robot planning is usually divided into two aspects: task planning and motion planning. Task planning is primarily designed to solve the problem of which robot should execute which task. This involves task decomposition and task allocation. Motion planning is primarily designed to generate the path of each robot. In addition, a robot should take into account the paths of others in order to avoid any collision, congestion or deadlock that may come along.
There is a key characteristic of robotics problems: uncertainty, which arises from the partial observability of the environment and from the stochastic (or unmoulded) effects of the robot's actions [34]. This is why the benchmarking of robotics research is inherently difficult (especially for MRSs).
7.1 Task Planning
Multi-robot task planning (MRTP) includes two aspects: task decomposition and task allocation. So far, the research on task planning for MRSs has been mainly concentrated on the task allocation problem, with relatively little on the task decomposition problem. In fact, task decomposition is an important research topic because the effect of task allocation could be directly influenced by it.
Multi-robot task decomposition (MRTD) mainly refers to how the team mission to be completed is decomposed into several single subtasks that can be completed by a robot independently, according to the characteristics, requirements and resource allocation of the team mission itself [104]. Stone and Veloso [105] achieved collaboration between agents through the introduction of formations, which decompose the task space defining a set of roles with associated behaviours. Botelho and Alami [5] presented a decentralized system to describe and perform task planning, decomposition and allocation in multi-robot environments called the M+ protocol. This work was developed from an early European project called MARTHA [48]. Zlot and Stentz [46] focused on complex tasks that can be decomposed into multiple inter-related subtasks. They addressed the task decomposition problem by generalizing tasks to task trees within a peer-to-peer trading market. Tang and Parker [7] considered that, in typical approaches to multi-robot team working, the decomposition of the team's task into subtasks is defined by the human designer in advance of the robot team's performance, and that this pattern also outlines the available multi-robot task solutions in advance of the mission. As such, they described a methodology for automatically synthesizing task solutions for heterogeneous multi-robot teams. Other relevant works on MRTD include [106].
In our previous work, we considered task allocation and also took task decomposition into account. In [43] [44], we first decomposed the whole multi-robot exploration mission into several subtasks (i.e., the exploration of several unknown regions), which can be identified by topologizing the grid map of the environment. Next, we discussed how to assign the subtasks to each individual robot in a reasonable manner.
Multi-robot task allocation (MRTA) can be considered as an instance of the well-known optimal assignment problem, whereby the general form of this problem can be expressed as follows:
There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task in such a way that the total cost of the assignment is minimized.
In those domains where group dynamics have a significant effect on group performance, MRTA is known to be NP-hard [15] [31]. The task allocation in a MRS generally undertakes assigning robots to tasks (or tasks to robots) so as to maximize the expected overall system performance. However, because MRTA becomes a dynamic decision problem - which varies in time with environmental changes - the static assignment method is no longer applicable. Thus, an alternative solution is to iteratively solve the static assignment problem over time.
Gerkey and Matarić [107] [15] gave a formal analysis and domain-independent taxonomy of MRTA problems, in which the MRTA problems have been classified into seven categories according to the ability of the robot to perform tasks, the number of robots required for a task, and the manner of the task assignment. They also analysed and compared some iterated assignment architectures: ALLIANCE [4], BLE [108], and M+ [5] and some online assignment architectures: MURDOCH (auction-based MRTA) [60], first-price auctions (market-based MRTA) [109] and dynamic role assignment [110], for MRTA, respectively.
The contract net protocol (CNP) [111] has been developed to achieve task assignment with distributed control by a negotiation process in multi-agent systems. So far, most methods for MRTA are based on the CNP model. Botelho and Alami [5] presented the M+ system, which used a scheme for multi-robot cooperation through negotiated task allocation and achievement. This system is the first CNP-based approach to MRTA. Stentz and Dias [109] presented the ideas of a free market architecture for coordinating a group of robots to achieve a given objective (the market-based approach). This architecture defines revenue and cost functions across a range of possible plans for executing a specified task. The task is accomplished by dividing it into sub-tasks and allowing the robots to bid and negotiate to carry out these subtasks. The objective is achieved by individual robots cooperating and competing with each other to further their own self-interest. Zlot et al. [29] applied these ideas to the multi-robot mapping and exploration problem. Their work borrows a market architecture, which seeks to maximize the benefit while minimizing the cost, thus aiming to maximize the utility. The benefit is the information gained by visiting a goal point, the cost is the estimated distance travelled to reach the goal (by using the D* algorithm), and then the utility is the difference between the benefit and the cost. It is worth pointing out that the market-based coordination architecture has been applied to a Mars exploration scenario (combined with the D* algorithm for robot motion planning). Gerkey and Matarić [60] presented the first online assignment architecture called MURDOCH, which uses a first-price auction to assign each task (an auction-based approach). The auction proceeds in five steps: task announcement, metric evaluation, bid submission, close of auction and progress monitoring / contract renewal. The MURDOCH system has been tested in two different domains: a tightly coupled multi-robot physical manipulation task, and a loosely coupled multi-robot experiment involving long-term autonomy. The major differences between an auction-based approach and a market-based approach are that: 1) an auction-based approach uses bids based on estimated costs, but a market-based approach takes into account both costs and benefits; 2) an auction-based approach does not allow task reassignment, but a market-based approach allows for later reassignments.
We developed a lightweight and robust MRTA approach based on trade rules in a market economy (a trade-based approach) [44]. This approach is designed to simulate the relationship between buyers and sellers in a business system and to achieve dynamic task allocation by using a mechanism of unsolicited bids. A comparison between market-based, auction-based and trade-based approaches is given in Table 1.
A Comparison of Three CNP-based Online Multi-robot Task Allocation Approaches
In addition to the above CNP-based approaches, there are many other interesting strategies. Dahl et al. [31] presented an algorithm for task allocation in groups of homogeneous robots that is based on vacancy chains, a resource distribution strategy common in human and animal societies. This algorithm uses local task selection, reinforcement learning for the estimation of task utility, and reward structures based on the vacancy chain framework. Hanna [112] proposed an approach that allows robots to take into account the uncertainty of task execution. They decomposed the MRTA problem into two stages. In the first stage, each robot selects its own tasks based on the expected benefit by using a Markov decision process (MDP). In the second stage, an auction-based mechanism is applied to assign tasks to the robots. Michael et al. [113] proposed a distributed market-based coordination algorithm in which agents are able to bid for task assignment with the assumption that the agents have knowledge of all the tasks and the maximum number of agents that can be assigned to every individual task. Each auction is performed among neighbouring groups of agents and requires only local communication. They verified their algorithm in a multi-robot formation control problem. Shiroma and Campos [114] proposed a framework called CoMutaR, which is designed to tackle both task allocation and task coordination problems in MRS. This framework enables a single robot to perform multiple tasks concurrently by periodically checking and updating task-related information during implementation. It was tested and evaluated in the simulation of object transportation, area surveillance and multi-robot box-pushing problems. Wawerla and Vaughan [24] presented two task allocation strategies for a multi-robot transportation system. One is based on a centralized planner that uses domain knowledge to solve the assignment problem in linear time. The other enables individual robots to make individual task allocation decisions by only using locally-obtainable information and single value communication. Other relevant works on MRTA include [48] [115] [116] [46] [117] [156] [160] [164] [167].
Moreover, the task allocation for heterogeneous and homogeneous systems may be different. In heterogeneous systems, task allocation may be determined by each robot's individual capabilities. However, in homogeneous systems robots have no preference for roles, and they may then need to differentiate into different roles at design-time, or dynamically at run-time [44]. Parker [118] introduced the concept of task coverage, which measures the ability of a given team member to achieve a given task. This parameter can be used as an index to organize a robot team from the available pool of heterogeneous robots in order to perform a mission. The task coverage reaches the maximum value in homogeneous teams and decreases as teams become more heterogeneous.
7.2 Motion Planning
In robotics, the motion planning problem involves producing a continuous robot motion from one configuration to another in a configuration space while avoiding collision with obstacles. Motion planning is eminently necessary for mobile robots since, by definition, a robot accomplishes tasks by moving in the real world [119].
Multi-robot motion planning (MRMP) should consider not only any obstacles (whether static or dynamic) in the environment, but also any possible interference between robots. This is because, when robots in a team are used to perform independent tasks in a shared workspace, each one will become a mobile obstacle for the others. Therefore, the motion planning of each individual robot in the team should take into account the movement of others. One well-studied example of MRMP is the multi-robot space sharing problem (see Section 4).
A multi-robot environment must definitely be dynamic, in which robot motion planning is inherently difficult. Even for a simple case in two dimensions, the problem is NP-hard and not solvable in polynomial time [120]. Among existing MRMP methods, the environment for an autonomous mobile robot is usually represented by an occupancy grid map, and the robot is reduced to a point in a two-dimensional plane (i.e., the workspace). Next, the motion is represented as a path in the workspace space.
Most of the existing approaches to MRMP are expanded from the results of a single-robot system. Three major families of approaches are the cell decomposition, potential field and roadmap approaches. They all reduce the continuous motion planning problem to a discrete graph search problem by identifying some canonical states and paths within the free space.
The cell decomposition approach decomposes the free space into a finite number of contiguous regions, called cells. This approach is often applied for the multi-robot area coverage problem. Bennewitz et al. [121] presented a strategy based on the A* path planning algorithm [122] to optimize the priorities of the decoupled and prioritized path planning methods for groups of mobile robots. The proposed approach is a randomized method, which repeatedly reorders the robots to find a sequence for which a plan can be computed and to minimize the overall path lengths. Guo and Parker [120] proposed a strategy based on the D* path planning algorithm [123], which contains two modules: path planning and velocity planning. The detailed process can be described as follows: initially, each robot plans its own path independently and then a coordination diagram is constructed based on collision checks among all the robots' paths. Hazon et al. [128] presented an online robust multi-robot spanning tree coverage (ORMSTC) algorithm based on an approximate cellular decomposition for covering an unknown environment. The algorithm is online because the robots do not have prior knowledge of the work area, and it is robust and complete because so long as a single robot is able to move, the coverage will be completed. Other works based on the cell decomposition approach include [129] [88] [130] [131].
The potential field approach generates a path by combining repulsion from obstacles with attraction to a goal. This approach is extensively used in the multi-robot formation control problem. Tanner and Kumar [124] presented a strategy based on an artificial potential field, which can ensure the near-global asymptotic convergence of the robots on a particular oriented formation shape while guaranteeing collision avoidance in the process. Other works based on the potential field approach include [125] [126] [127].
The roadmap approach reduces the robot's free space to a set of one-dimensional curves connecting a set of nodes, called a roadmap. A typical roadmap approach is a Voronoi diagram, which specifies the set of all points equidistant from two or more closest obstacles. Following the Voronoi diagram may not give the shortest path, but the resulting paths tend to maximize clearance [34]. The Voronoi diagram is often applied to the problem of robotic exploration. Wurm et al. [40] presented a strategy for coordinating a team of exploring robots by using the Voronoi diagram for the segmentation of the environmental map. The strategy extracts the critical points [132] as the targets to assign them to the robots for task allocation. The critical points are those nodes in the Voronoi diagram at which the distance to the closest obstacle in the map is a local minimum. Other works based on the Voronoi diagram include [39] [41] [42].
Another roadmap approach is the probabilistic roadmap (PRM) [133], which has been widely used for robot arms in engineering and manufacturing. This method randomly generates a large number of collision-free configurations and achieves motion planning by connecting some of them. Several studies address multi-robot coordination based on PRM, but focus on manipulator arms [134] [135]. As for the application of MMRS, Švestka and Overmars [136] presented a PRM-based approach for multiple non-holonomic car-like robots' motion planning in the same static workspace in which the roadmaps for the composite robot are derived from roadmaps for the underlying simple robots, and the roadmaps for the simple robots are computed by a probabilistic single-robot learning method. Kumar and Chakravorty [165] proposed a multi-agent generalized PRM (MAGPRM) method to solve MRMP problems in stochastic maps with uncertainty in the motion model. This method can construct a roadmap between every pair of start and goal locations for each robot by using an adaptive sampling technique. Other works based on the PRM include [92] [137].
Another probabilistic method is the rapidly-exploring random tree (RRT) [138], which takes the motion planning as a tree search problem. The tree is constructed incrementally in such a way that any random configuration in the free space is added by connecting it to the closest configuration already in the tree. Bruce and Veloso [139] described a RRT-based method for MRMP, called extended RRT (ERRT), in which the mechanism of a waypoint cache was implemented to store the knowledge of where a plan might again be found in the near future, and another mechanism of an adaptive beta search was used as well, where the planner adaptively modified a parameter to help it find shorter paths. Wagner et al. [163] applied a technique called subdimensional expansion in order to enhance the performance of probabilistic planners (RRTs and PRMs) for multi-robot path planning. This technique can construct a search space while being explored by a planner, the partial results of which are used to guide the construction of the search space. They showed that the technique could decrease the time required to find a solution by more than an order of magnitude, especially for systems of four or more robots.
It is worth pointing out that both PRM and RRT are sampling-based methods, both of which are currently considered state-of-the-art for motion planning in high-dimensional configurations or geometrically complex spaces. This is because, unlike with the cell decomposition, potential field and Voronoi diagram approaches (these approaches are difficult to apply to high-dimensional problems), the running time of the sampling-based methods does not grow exponentially with the dimension of the configuration space; they are also easier to implement. In addition, the sampling-based methods are probabilistically complete, meaning that sometimes they fail to find a solution even if one exists. A comparison of three major families of MRMP approaches is given in Table 2.
A Comparison of Three Major Families of Multi-robot Motion Planning Approaches
The existing motion planning methods have their own strengths and weaknesses. Using only one method may entail difficulties in dealing with complex environments, such as the MRS. Combining multiple methods together is more coincident with the MRS requirements of reliability, flexibility, scalability and versatility [43]. This notion of a hybrid approach has been mentioned several times in the previous text (see Section 5 and 6). Schwager et al. [140] introduced a unifying optimization framework for multi-robot deployment that brings together several different existing strategies, including geometric, probabilistic and potential field approaches. Other relevant works on MRMP include [141] [66] [142] [143] [162].
In addition, and for the purpose of dealing with problems about limited communication, computational speed and complex environments in MMRS, various MRMP approaches have been proposed based on wireless sensor networks (WSNs). Clark et al. [92] presented a framework for multiple mobile robots' motion planning by using dynamic networks that are capable of: 1) forming dynamically whenever communication and sensing capabilities permit; 2) sharing world models and robot goals within each network; and 3) constructing on-the-fly coordinated trajectories for all robots in each network using a fast, centralized motion planner. Other related works include [144] [137] [145].
8. Decision-making: Centralized Versus Decentralized
Decision-making can be regarded as a cognitive process resulting in the selection of a course of action among several alternative scenarios. Every decision-making process produces a final choice. In MRS, the decision-making guided by planning can be centralized or decentralized in accordance with the group architecture of the robots.
There is a central control agent in centralized architectures that has the global information about the environment as well as all information about the robots, and which can communicate with all the robots to share them. The central control agent could be a computer or a robot. The advantage of the centralized architecture is that the central control agent has a global view of the world, whereby the globally optimal plans can be produced. Nevertheless, this architecture: 1) is typical for a small number of robots and ineffectual for large teams with more robots; 2) is not robust in relation to dynamic environments or failures in communications and other uncertainties; 3) produces a highly vulnerable system, and if the central control agent malfunctions a new agent must be available or else the entire team is disabled. A typical MRS using a centralized architecture is GOFER [2], in which there is a central task planning and scheduling system with a global view of the tasks to be performed in the environment and the availability of robots to perform the tasks. Certain studies outlined in the previous sections belonging to the centralized architecture approach include [66] [92] [7] [124] [40] [71] [43] [49].
Decentralized architectures can be further divided into two categories: distributed architectures and hierarchical architectures. There is no central control agent in distributed architectures, such that all the robots are equal with respect to control and are completely autonomous in the decision-making process. In hierarchical architectures, there exist one or more local central control agents which organize robots into clusters. The hierarchical architecture is a hybrid architecture, intermediate between a centralized architecture and a distributed architecture. In contrast to a centralized architecture, a decentralized architecture can better respond to unknown or changing environments, and usually has better reliability, flexibility, adaptability and robustness. Nevertheless, the solutions they reach are often suboptimal. Feddema et al. [146] have focused on input / output reachability, structural observability, system controllability and connection stability for decentralized control systems. They also show how these theories are applicable to multi-robot formation control, perimeter surveillance and (
9. Conclusion
In this paper, we systematically surveyed and analysed the key research problems in the field of MMRS, focusing on those approaches involving multi-robot coordination. We started by surveying the potential advantages of MRSs in contrast to single-robot systems. Afterwards, we discussed two multi-robot environments, namely cooperative and competitive environments. Next, we analysed three aspects of the problem of resource conflict in MMRS, including communication media sharing, object sharing and space sharing. Next, we discussed multi-robot coordination in two respects, including static and dynamic, and communication as a means of coordination. Following this, we made a special effort to investigate and study the multi-robot planning problem, including task planning and motion planning, which is inseparable from multi-robot coordination. Finally, we identified two decision-making architectures including centralized and decentralized approaches.
The investigation of the related literature shows that considerable progress has been made in multi-robot localization / mapping / exploration and search and rescue, as well as intelligent transportation. However, these problems are still not fully resolved. In the previous sections, we identified several key open research challenges and presented a number of existing methods that are popular or interesting. There remain many other challenges, such as:
How to enable the MRS to handle more complex tasks like human beings? This means that we need more a powerful coordination scheme, especially in the process of MRTP. A simple two-layer task planning scheme (MRTD and MRTA) may no longer be suitable. A multi-layer scheme including task analysis, task negotiation, task execution and task supervision becomes important [167] [168].
How to ensure the reliability of the motion of a physical MRS in the real world? As we know, there are still a lot of problems to be solved in MRMP, such as collision, congestion and deadlock. In complex and dynamic environments like MMRSs, rule-based and graph-based methods are difficult to deal with. A high-level coordination concept combined with reactive control for robots should be more efficient [169] [170].
How to fuse and analyse the information acquired by each individual robot more rationally (and then make the decision more efficient)? A decision-making architecture for a MRS - centralized or decentralized - has a requirement for information sharing because a robot in the team can only perceive local information. Effective data fusion may help us to produce an effective plan and then conduct multi-robot coordination [171] [172].
How to make humans to easily intervene MRSs according to what is needed? Currently, many tasks are still too complex for robots, and coordination between humans and robots needs to be explored [173] [174] [175]. Human-machine interactions are ubiquitous in today's world, although this paper focuses on the use of autonomous mobile robots.
Moreover, on the basis of our review some promising avenues for future research become apparent:
So far, much more attention has been paid to coordination for the same types of robot (homogeneous and heterogeneous). Coordination between different types of robots, such as UUV, UGV and UAV, would present a very interesting challenge. MASs with rich diversity should be more efficient.
Energy must be the single most important problem that we confront today. Therefore, energy consumption as a system performance metric should be given more consideration.
The sampling-based algorithm is a very important and useful approach to robot motion planning. It is widely used in manufacturing environments with industrial robots, but there is greater development potential in MMRSs.
The centralized and distributed decision-making structures have their own strengths and weaknesses. For the near future, an effective way is to build a hybrid mechanism (i.e., a hierarchical architecture).