Zhi Yan

Nicolas Jouandeau

Arab Ali-Chérif

Multi-robot Heuristic Goods Transportation

In this paper, we consider the issue of transporting a certain number of goods by a team of mobile robots. The target is to minimize the total transportation time and keep a low energy consumption of the intelligent agents on assuring security and quality during the transportation process. The pivotal issue needs to be solved is how to assign tasks to individual robots in a more reasonable and efficient way. We present a novel solution by using an empirical-based heuristic planning strategy for the goods transportation by multiple robots. In contrast to previous approaches, this strategy is designed to plan the transportation task for each individual robot by estimating the production rate of goods based on multi-robot coordination. Our approach has been implemented and evaluated in simulation. The experimental results demonstrate that the completion time of the whole transportation mission can be significantly reduced and the energy consumption of robots can be kept at a low level of our heuristic planning strategy compared with the previous approach.

I. INTRODUCTION

The goods transportation system is an important application for autonomous mobile robot research, which can be used in various environments, such as warehouses, factories, container ports, or hospitals. Generally, how to complete the transportation mission with high efficiency and low cost is the first priority. On the one hand, in contrast to single robot, using a collaborative team of robots has the potential to accomplish the transportation mission more efficiently [START_REF] Cao | Cooperative mobile robotics: Antecedents and directions[END_REF], [START_REF] Dudek | A taxonomy for multiagent robotics[END_REF]. But on the other hand, we also hope to reduce the overall energy consumption of the fleet of mobile robots. Therefore, during the whole transportation process, the following two issues should be considered:

• For the purpose of multi-robot coordination, how to plan the motion for each individual robot of the team, which handles path planning, obstacle avoidance, collision avoidance, grip action and drop action. • For the purpose of high efficiency and low cost, how to assign the transportation task to each individual robot reasonably. The transportation task could be the delivery of goods from one location to another location. In this paper, we consider a multi-robot goods transportation system in which goods must be transported from their place of production to the location of the consumers. The scenario details like this: the source location and the sink location are known and fixed, the production rate of goods is unknown, given the source location cannot store more than one unit at a time, all robots must be placed in a depot at the beginning of Fig. 1. Four robots implement a transportation mission cooperatively. The dark blue piece signifies the goods to be transported. The gray zone represents the depot for the robots, the green zone represents the source location where the goods are produced, and the zone in orange color represents the location where the goods should be delivered by the mobile robot.

the mission, and they can return to the depot in their free time during the whole transportation mission. Here, suppose that the robot will not consume any energy when it stays in the depot waiting for the task. On the contrary, also suppose the energy consumption for motion, computation and sensing increases at a constant rate during the task implementation process. For example, 10 seconds of task will consume 10 units of energy. The objective of robots is to complete the whole transportation mission in coordination but the implementation time should be minimized and the energy consumption should be limited to a low level. Figure 1 shows a screenshot of our implementation on the simulator Stage [START_REF] Gerkey | The player/stage project: Tools for multi-robot and distributed sensor systems[END_REF], in which the red robot stays in the depot on standby, the green robot is moving to load a goods, the orange robot is transporting a goods to the sink location, and the blue robot is on its way back after completing a transportation task.

In contrast to previous research, we do not just simply focus on high efficiency (reduce the total mission runtime) or low cost (reduce robots' energy consumption), but combine both to find an optimized solution. The core idea of this solution is to estimate the production rate of goods by a heuristic function based on an empirical model, and then assign the goods transportation task to the individual robot reasonably by a centralized decision making system. In our research, the high efficiency evaluation metric is the total time required to complete a transportation mission, and the low cost evaluation metric is the sum of energy consumption of the robots. Through simulation experiments with a group of robots and compared with the centralized replanner method, the results show that the total transportation time is significantly reduced and the energy consumption is kept at a low level of our approach.

This paper is organized as follows. In Section II, we give an overview of some related work. Subsequently, we briefly discuss the requirements of a multi-robot goods transportation system in Section III. Then we present our heuristic planning strategy in Section IV. Finally, we describe the experimental results obtained with our approach in Section V, and conclude with Section VI.

II. RELATED WORK

The problems of goods transportation can be divided into two categories according to the existing literature:

• Multiple robots transport a single object cooperatively. A typical problem in this category is the multi-robot boxpushing problem, in which robots should share manipulation tasks. • Multiple robots transport multiple objects cooperatively. This is one of the sub-problems of foraging. The foraging problems are usually studied by combining the energy autonomy. The core issues concerning both the two categories are the decomposition and allocation of transportation tasks, as well as the motion coordination for multiple robots.

This paper focuses on the second category. Alami et al. [START_REF] Alami | Multi-robot cooperation in the MARTHA project[END_REF] presented a general concept for the control of a large fleet of autonomous mobile robots which has been developed, implemented and validated in the framework of MARTHA (Multiple Autonomous Robots for Transport and Handling Applications). They proposed an approach called plan-merging paradigm for multi-robot cooperation, which has been tested in both simulation and real world. Vaughan et al. [START_REF] Vaughan | LOST: Localization-space trails for robot teams[END_REF] described a method (LOST) that enables a team of robots to navigate between places of interest in an initially unknown environment using a trail of landmarks. They applied this method to an example "resource transportation" task, in which multiple autonomous robots find and repeatedly traverse a path in an unknown environment between a known "home" and a supply of resource at an initially unknown position.

Tang and Parker [START_REF] Tang | ASyMTRe: Automated synthesis of multirobot task solutions through software reconfiguration[END_REF] described an approach for automatically synthesizing task solutions for heterogeneous multi-robot teams which is called ASyMTRe. This approach is built upon schema and information invariants theories, it enables the robot team to dynamically connect schemas within and across robots to accomplish a task. They also validated this approach in two different scenarios: multi-robot transportation and multi-robot box pushing. Dahl et al. [START_REF] Dahl | Multi-robot task allocation through vacancy chain scheduling[END_REF] presented an algorithm for task allocation in groups of homogeneous robots based on vacancy chains. Through the experiments in simulation, they showed that the vacancy chain algorithm performs better than random and static task allocation algorithms when individual robots are prone to distractions or breakdowns, or when task priorities change. They also defined the prioritized transportation problem (PTP) as an extension of the basic transportation problem where the sources and sinks, the targets of the transportation, are divided into sets of different priority also called circuits.

Shiroma and Campos [START_REF] Shiroma | CoMutaR: A framework for multi-robot coordination and task allocation[END_REF] proposed a framework called CoMutaR, which is designed to both tackle task allocation and coordination problems in multi-robot system. This framework enables the single robot to perform multiple tasks concurrently by periodically checking and updating task-related information during implementation. It has been tested and evaluated in simulation in object transportation, area surveillance, and multi-robot box pushing problem. Wawerla and Vaughan [START_REF] Wawerla | A fast and frugal method for teamtask allocation in a multi-robot transportation system[END_REF] introduced 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 using only locally obtainable information and single value communication. They used the energy expended by robots as performance evaluation standard. The computational complexity of these two strategies is small, but the performance is good.

In contrast with previous research, firstly, the basic object of our investigation is not just a task decomposition or allocation problem, but a goods transportation problem. Secondly, our simulation experiment is based on low level concepts. We try to represent the goods transportation in the real world with closer physical model, including grip action, drop action, and security of goods in transport. Finally, we introduce the energy consumption unit of the robot as one of the performance metrics, combined with the mission completion time, to evaluate the overall system.

III. MULTI-ROBOT GOODS TRANSPORTATION SYSTEM

In multi-robot systems, there is a basic issue known as coordination. The target of coordination is to fulfill the predefined mission better. In the goods transportation scenario, in order to establish such a system, two practical issues should be considered: robot navigation and task allocation.

Mobile robot navigation contains three fundamental problems: map learning, localization and path planning. In a given environment, a robot should be able to determine a collision free path from its current location to a desired goal location, this is known as path planning. To compute the path, a map of the environment should be known, which is built from a set of sensor data acquired by the mobile robot, this problem of map learning is commonly referred as simultaneous localization and mapping (SLAM). During the path following process, the mobile robot needs to know its exact position and orientation in the environment at all times, this is known as localization.

A multi-robot navigation system should also deal with the possible interference between robots. For instance, a robot should take into account the motion of other robots to avoid congestion or collision [START_REF] Yan | Sampling-based multi-robot exploration[END_REF].

Task allocation is an essential requirement for multi-robot systems. It's designed to find: which robot should implement which work? The object of work could be the location for environment exploration or a crate for goods transportation. The core ideology of multi-robot task allocation (MRTA) systems is to iterate the assignment, in order to deal with changes in the tasks, the robots, and the environment [START_REF] Gerkey | A formal analysis and taxonomy of task allocation in multi-robot systems[END_REF].

Moreover, a goods transportation system using a coordinated team of autonomous mobile robots should also meet the following requirements:

• The map of the environment is known, in which there exist unknown and possibly moving obstacles like goods and robots. Robots must traverse this given environment for transporting goods from the source to the sink. • A transportation mission is composed of a series of tasks.

The objective is to allocate the subset of these tasks to each robot reasonably in order to minimize the time needed to accomplish the mission. This problem is known as N P-hard [START_REF] Gerkey | A formal analysis and taxonomy of task allocation in multi-robot systems[END_REF].

• The quality and security of transportation should be assured. In this paper, a good transport quality refers to that the total mission runtime for each trial should be close to the average, and the transport security means that the robot should avoid damage or loss of goods caused by collisions with obstacles or other robots.

IV. HEURISTIC PLANNING STRATEGY

A major reason for the low efficiency of transportation in a known space is the unknown production rate. A regular estimate of this rate is the key to solve the problem. Using heuristic approach is a natural thinking [START_REF] Hwang | A heuristic task assignment algorithm to maximize reliability of a distributed system[END_REF], [START_REF] Ogawara | Estimation of essential interactions from multiple demonstrations[END_REF], [START_REF] Pardowitz | Incremental acquisition of task knowledge applying heuristic relevance estimation[END_REF].

The production rate, denoted by T n , refers to the elapsed time between the disappearance of the n-th goods (be carried away) and the appearance of the (n + 1)-th goods. T n can be regarded as a sequence of independent and identically distributed random variables. The law of variables is unknown, which can be determined by the method of hypothesis testing. The heuristic value h(n) can be obtained by the distribution function:

h(n) = E(T n+1 |T 1 , . . . , T n ) (1)
Equation ( 1) means the elapsed time since the removal of the n-th goods until the appearance of the (n + 1)-th goods by our prediction. Given T n as an uniform distribution, then:

h(n) = 1 n n i=1 T i (2)
In effect, the whole issue is a limited decision making. For each robot R i(i=0,...,m) , the decision space for each step (also denoted R i ) is finite. For example, R i =

R = m i=0 R i (3)
Suppose there are N goods, then the centralized planner's decision space is R N , every decision r ∈ R N is defined by r(n) ∈ R(n = 1, . . . , N ).

We set the total time X(n) for when the n-th goods has been carried away by a robot, then:

X(n + 1) = X(n) + min t∈R f (t, h(n), r n ) (4)
Here, f is a function to calculate the interval time between the n-th and the (n + 1)-th goods were carried away. t represents the current decision making. Moreover, t can be taken as r(n) when it makes f the minimum. r n signifies the current location information of each robot. For instance, t refers to that let a robot in depot move to the source location of goods, then f (t, h(n), r n ) = max(h(n), T DepotT oSource ).

We notice that a greedy algorithm is used in [START_REF] Alami | Multi-robot cooperation in the MARTHA project[END_REF]. It can guarantee to get the minimum of the total time to complete the mission, but it cannot guarantee the low level of the energy consumption. For instance, consider the situation shown in Figure 2. Robot0 and robot1 are two free robots. The red segment and blue segment represent two kinds of task plans (denoted red plan and blue plan) respectively. The red plan represents that robot0 moves to the depot and robot1 moves to the source. The blue plan represents robot0 moves to the source and robot1 moves to the depot. The red plan uses the greedy algorithm, i.e., let the robot the nearest from the source (in the case of the figure, robot1) to load the goods. However, the red plan requires more energy than the blue plan: 13.0 units for the red plan and 10.4 units for the blue plan.

As a result, (4) cannot guarantee that the global optimal solution would be found. Thus, in order to reduce the total mission runtime and to keep a low energy consumption, we use a heuristic method based on an empirical model to replace the function min t∈R f (t, h(n), r n ) to get the current strategy. The details of our implementation are given in Algorithm 1.

Algorithm 1 Heuristic task allocation based on an empirical model

1: if the n-th goods has been carried away by a robot then 2:

Calculate h(n) by using (2).

3:

for all robot i which is outside of the depot and not in the task do if h(n) < T toSource (i) and h(n) > 1 2 T toSource (i) then 5:

Robot i accepts the task and go to the source. if there is no robot which has accepted the task and there is a robot in the depot then 10:

Calculate the waiting time for the robot in depot by using T wait = max(0, h(n) -T DepotT oSource ).

11:

After T wait time, wake up the robot in depot and assign the task to it.

12:

end if 13: end if T toSource (i) indicates the time required for robot i to travel from its current location to the source location. We found that, in Algorithm 1, T toSource (i) and T DepotT oSource are two estimated values and they are unknown at the beginning of the mission. Nevertheless, after a robot has completed a task (i.e., it moves from the depot location to the source location, then transports a unit of goods from the source location to the sink location), we can get two reference values: T DepotT oSource and T SourceT oSink , then T toSource (i) and T DepotT oSource can be estimated via these two reference values.

In our system, we use reactive control technique for robotic software architecture. Five behaviors are defined for each robot. The relationships between them are illustrated in Figure 3. Here, STANDBY behavior represents that the robot is in the depot waiting for a new task. MOVE behavior means that the robot is in the mobile navigation process. SENSE behavior signifies the robot is in the process of sensing the depot location to position itself, the source location to grip the goods, or the sink location to drop the goods. GRIP and DROP behaviors denote that the robot is in the grip or the drop action process.

Moreover, each robot has information about all other robots. In this way, we can try to avoid the collision, the congestion and all the other problems of waiting situation when we handle the multi-robot motion planning.

V. EXPERIMENTS

Our approach has been implemented and evaluated in Stage [START_REF] Gerkey | The player/stage project: Tools for multi-robot and distributed sensor systems[END_REF], which is a fast and scalable 2D multi-robot simulator. The simulation experiments were conducted by using a group of Pioneer 2-DX robots equipped with a laser range finder providing 361 samples with 180 degrees field of view and a Fig. 3. Relationships between five behaviors in robot control Fig. 4. A typical Pioneer 2-DX robot with the gripper maximum range of 8 meters. Each robot can localize itself based on an abstract localization device which models the implementation of GPS or SLAM. In order to transport goods, the robots are equipped with a gripper to enable them to sense the goods, pick it up, and put it down. The carrying capacity of each robot is limited to one unit. Figure 4 shows a typical Pioneer 2-DX robot with the gripper.

Our simulation experiments are conducted in an enclosed space with 16 meters long and 16 meters wide, which also contains several fixed obstacles. The ratio between real world time and simulation time is about 1:5. We assumed that the mobile robots share a common occupancy grid map with information about the structure of the environment, which is used for path planning and obstacle avoidance in real time. In our implementation, we have used the wavefront propagation algorithm [START_REF] Latombe | Robot Motion Planning[END_REF] for global path planning and the nearness diagram algorithm [START_REF] Minguez | Nearness diagram (ND) navigation: Collision avoidance in troublesome scenarios[END_REF] for goal seeking and local obstacle avoidance. We also assumed that there exists a central planning component which is able to communicate with all robots and assign the transportation tasks to each one.

In order to evaluate our approach, we designed four different simulation experimental environments, which are shown in Figure 5. The different environments are divided according to the distance relationship between the depot (denoted by D), the source (denoted by S) and the sink (denoted by K), i.e., KD > KS > SD, KD > SD > KS, KS > KD > SD and KS > SD > KD. Actually, there are also another two relationships: SD > KD > KS and SD > KS > KD. However, these two are not interesting situations because the longest distance is that between the depot and the source.

We used a small team of robots to conduct several experi- ments, and compared our heuristic approach to the replanner approach [START_REF] Wawerla | A fast and frugal method for teamtask allocation in a multi-robot transportation system[END_REF]. The production rate of goods is varied independently from 4 seconds to 12 seconds. The experimental results are shown in Figure 6. All experiments reported in this paper were carried out on a system with an Intel Core 2 Duo E8400 3.00GHz processor, an Intel Q43 Express chipset and two DDR2 800MHz 1024MB dual channel memory.

Figure 6 shows the results of simulation experiments obtained in a mission of four robots to transport fifty goods cooperatively. The four histograms correspond to the results of the four different simulation environments. Each histogram contains two sets of experimental data corresponding to the total transportation time and the sum of energy consumption of robots by the heuristic approach and the replanner approach respectively. Each set of data contains ten trial results. Figure 6 shows that the transportation time is significantly reduced by our heuristic approach compared to the replanner approach, and the energy consumption obtained by using our approach is still maintained at a low level.

Furthermore, another important advantage of our heuristic approach is making the energy consumption evenly distributed, without concentrating on a few robots. Through a series of experiments, we found that, there are mainly two factors which affect the performance of a goods transportation system:

• The relationship between the location of the depot, the source and the sink. If the source and the sink are fixed, then setting the location of a depot reasonably has the potential to improve the performance. For example, in Figure 6, the histogram A (KD > KS > SD) shows a result which has less transportation time and less energy consumption than the histogram B (KD > SD > KS). • The team size of robots. In the experiment, we found that, the energy consumption of each robot is different at the end of mission even sometimes the difference between them is considerable. Actually, when the quantity of robots is too small in a mission, it will extend the total mission runtime. Contrarily, when the quantity of robots is too large in a mission, it will cause a waste of the resource. Therefore, reasonably controlling the number of robots is also an important consideration.

Finally, Figure 6 shows that, the total transportation time for each trial is close to the average in each histogram, in other words, our algorithm provides a moderately good transportation quality. Moreover, in our experiments, we found that if the speed of the robot is too fast, in some instances, a separation of goods and gripper will happen. Therefore, in order to ensure the transport security, i.e., to avoid the damage or the loss of goods caused by the collisions with the obstacles or the other robots, the speed of each robot was limited to 1.0 meters/sec in our simulation.

VI. CONCLUSION

In this paper, we consider the following problem: a set of autonomous mobile robots should work together to accomplish a transport mission efficiently, the mission refers to delivery of a certain amount of goods from sources to sinks, and the objective is to complete the mission as soon as possible and keep the energy consumption as low as possible, which is equivalent to minimize the total mission completion time and limit the sum of energy consumption of robots to a low level. Because the production rate of goods is unknown at the source location, we designed to assign the transportation task to each robot by estimating the time appearance of goods reasonably. Hence, we proposed a novel heuristic approach based on the empirical model for multi-robot goods transportation. The proposed approach has been implemented and evaluated in simulation. The experimental results demonstrated that our approach shows a good performance in the environment close enough to the real world.

The current experiments are conducted on the basis of small goods production rate variation. A large rate variation requires more complex heuristic strategy. Our next work will vary the rate of goods production in a wide time interval to improve our approach. We will also test our approach on large scale problems with more robots and more goods.

Fig. 2 .

 2 Fig. 2. Comparison of two plans for task allocation

Fig. 5 .

 5 Fig. 5. Four different simulation experimental environments. The gray area represents the depot (D), the green area represents the source (S), and the orange area represents the sink (K). The environment A corresponds to case KD > KS > SD, the environment B corresponds to case KD > SD > KS, the environment C corresponds to case KS > KD > SD, and the environment D corresponds to case KS > SD > KD.

Fig. 6 .

 6 Fig. 6. Experimental results of performance comparison of the two methods (heuristic and replanner): four robots implement a transportation mission of fifty goods cooperatively. Number of trials is plotted on the x-axis, and transportation time (in seconds) and energy consumption on the y-axis.


Zhi Yan

Arab Nicolas Jouandeau

Ali Cherif

Arab Ali Cherif

ACS-PRM: Adaptive Cross Sampling Based Probabilistic Roadmap for Multi-robot Motion Planning

Keywords: multi-agent system, motion planning, multi-robot coordination, sampling-based approach

whether they are published or not. The documents may come

L'archive ouverte

INTRODUCTION

Motion planning is a fundamental problem in robotics. It could be explained as producing a continuous motion for an agent, that connects a start configuration and a goal configuration, and avoid collision with any static obstacles or other agents in an environment. The agent and obstacle geometry are generally described in a 2D or 3D workspace, and the motion could be represented as a path in configuration space. Motion planning algorithms are widely applied in many fields, such as bioinformatics, robotic surgery, industrial automation, planetary exploration and intelligent transportation system.

The multi-agent system (MAS) is proposed to deal with some problems that are difficult or impossible to be solved by a single agent, or to improve the system implementation efficiency in some missions completed by multi-agent rather than a single agent [START_REF] Cao | Cooperative mobile robotics: Antecedents and directions[END_REF], [START_REF] Dudek | A taxonomy for multi-agent robotics[END_REF]. The biggest challenge for the MAS is coordination. Without coordination, it will not only lower the system's efficiency, but also lead to the failure of the entire system in extreme cases. Figure 1 shows an example of multi-agent coordination, four robots implement a transportation mission cooperatively, the red robot is delivering a goods, the green robot is on its way back after completing a transportation task, the yellow robot is moving to load a goods, and the orange robot is transporting a goods to the destination location. The coordination of these four robots is obtained by assigning them to different room.

In this paper, we consider the issue of coordinated motion planning for a homogeneous team of autonomous mobile robots in structured environments such as office building, warehouse and container terminal. The larger context of the research is to establish a multi-robot goods transportation system with security, reliability and efficiency. Most of the proposed approaches for multi-robot motion planning usually have the problem of congestion and collision [START_REF] Solanas | Coordinated multi-Robot exploration through unsupervised clustering of unknown space[END_REF], [START_REF] Wurm | Coordinated multi-robot exploration using a segmentation of the environment[END_REF]. Because of the transportation issue, a desirable result is that robots need more time to replan their individual local path, thus limit the transportation efficiency, an undesirable result is that the robots are blocked or the goods are lost or damaged and thus fail the transportation mission. We arrange these cases to the waiting situation problem [START_REF] Yan | Sampling-based multi-robot exploration[END_REF]. To handle this practical problem, this paper present a novel approach for multi-robot motion planning by using a probabilistic roadmap planner (PRM) which is based on a manner of adaptive cross sampling (ACS). This approach called ACS-PRM is decomposed into 3 main steps:

• Firstly, we sample an adequate number of points in C-space on an occupancy grid map by using the adaptive cross sampling method.

• Secondly, we build the roadmap by connecting the potential targets and the milestones extracted by second learning the result of sampling.

• Thirdly, we plan the motion of mobile robots by querying the constructed roadmap based on multi-robot coordination.

The rest of the paper is organized as follows: Section 2 describes an overview of some related works; Section 3 discusses the problem of waiting situation; subsequently, Section 4 describes our ACS-PRM approach; Section 5 presents the experimental results obtained with our approach; and the paper is concluded in Section 6 at last.

RELATED WORK

Švestka and Overmars [START_REF] Švestka | Coordinated motion planning for multiple car-like robots using probabilistic roadmaps[END_REF] presented an approach for multiple nonholonomic car-like robots motion planning in the same static workspace by using probabilistic roadmaps, in which the roadmaps for the composite robot are derived from roadmaps for the underlying simple robots, and the latter is computed by a probabilistic single-robot learning method. The authors introduced the notion of super-graphs for multi-robot path planning, and their implementation covered the construction of the simple roadmap and the super-graphs. This approach is probabilistically complete because a given problem could be solved within a finite amount of time.

Moors et al. [START_REF] Moors | A probabilistic approach to coordinated multi-robot indoor surveillance[END_REF] presented a graph-based algorithm for coordinate multi-robot motion planning in 2D indoor environments. The scenario of this research is multi-robot indoor surveillance. The proposed approach takes the limitations and uncertainties of sensors into account, and generates the coordinated motion plan for multiple robots by using A* search algorithm. The authors also introduced a framework based on realistic probabilistic sensor models and worst case assumptions on the intruder's motions in order to compare different approaches and evaluate the coordination performance of the proposed approach.

Clark [START_REF] Clark | Probabilistic road map sampling strategies for multi-robot motion planning[END_REF] presented a multi-robot motion planning strategy based on the probabilistic roadmap within a dynamic robot network (DRN) coordination platform. The DRN platform is an ad hoc network, in which a single-query PRM is queried as a centralized planner to plan trajectories for all robots. The PRM planner is optimized to speed queries for multi-robot motion planning by using new sampling strategies. At first, a method of sampling PRM milestones is identified to enable fast coverage of the configuration space. Then, a method of generating PRM milestones is introduced to decrease the planning time. Finally, a endgame region is defined to improve the likelihood of finding solutions when goal configurations are highly constrained. [START_REF] Saha | Multi-robot motion planning by incremental coordination[END_REF] presented a strategy for decoupled multi-robot motion planning. The proposed strategy, which aims at improving the reliability of the basic decoupled planning approach, partially merge the two phases of the basic approach. The first phase is to computing a collision-free path to avoid the obstacles in the environment and the other robots, the second phase is coordinating the individual robot motions so that only one robot at a time may enter the area of potential inter-robot interference. The proposed approach searches for motions for a robot and coordination of motions of robots along paths already planned while ignoring the robots whose motions have not been planned simultaneously. This approach is inherently incomplete.

Saha and Isto

Besides, there are some other approaches developed with various policies [START_REF] Burgard | Collaborative multi-robot exploration[END_REF], [START_REF] Buck | Multi-robot path planning for dynamic environments: a case study[END_REF], [START_REF] Solanas | Coordinated multi-Robot exploration through unsupervised clustering of unknown space[END_REF], [START_REF] Regele | Cooperative multi-robot path planning by heuristic priority adjustment[END_REF], [START_REF] Wurm | Coordinated multi-robot exploration using a segmentation of the environment[END_REF].

In our previous work [START_REF] Yan | Sampling-based multi-robot exploration[END_REF], we considered the issue of using separate topological graphs to coordinated multi-robot motion planning for exploration mission. This work aims at solving the waiting situations in the process of the robot motion planning. In particular, if all the robots take the same topological graph derived from grid map, then they might follow the same exploration path partly or wholly, and this contributes to the problem of waiting situation. We proposed an approach based on sampling environment map iteratively to support the coordinated multi-robot exploration. This research is related to the approach proposed in this paper, even if the methodology is substantially different. Compared to our previous approach, we obtain a significantly reduced mapping time by this approach.

Our recent research focuses on the issue of multi-robot goods transportation. The objective is to complete the transportation mission with high efficiency and low cost. We proposed a heuristic method based on empirical model, which aim at planning the transportation task for each individual robot by estimating the production rate of goods based on multi-robot coordination, so as to improve the system performance. In the module of robot motion planning, we used the wavefront propagation algorithm [START_REF] Latombe | Robot Motion Planning[END_REF] to global path planning and the nearness diagram algorithm [START_REF] Minguez | Nearness diagram (ND) navigation: Collision avoidance in troublesome scenarios[END_REF] to goal seeking and local obstacle avoidance. Nevertheless, in the experiment, one important reason which influences the system performance is still the waiting situation. Furthermore, if the speed of robot is too fast, then the goods would be damaged or lost in transit because of the collisions with obstacles or others robots.

We limited the speed of robot to handle this problem, whereas this strategy limited the efficiency of the whole transportation system as well. Therefore, in this paper we discuss the substance of the problem and propose a novel approach to address such problems in this paper.

WAITING SITUATION PROBLEM

Multi-agent environments can be cooperative or competitive [START_REF] Russell | Artificial Intelligence: A Modern Approach (2nd Edition)[END_REF]. To every agent in a team, the other agents can be considered as teammates (cooperative) or movable obstacles (competitive). One of the most important reasons which limit the efficiency of the multi-robot motion planning is the waiting situation such as the congestion and collision between robots. The core of the problem can be considered as the waypoint mutex. Figure 2 depicts a typical waypoint mutex. Two robots move to the same waypoint simultaneously: the red robot move from the top left towards the right and the blue robot move from the right towards the bottom left. Because the waypoint can be assigned only to one robot at a time, then the mutex of the waypoint happens.

Generally, there are two ways to deal with the waypoint mutex as shown in Figure 3. One (Figure 3(a)) is to let robots pass the waypoint one by one [START_REF] Švestka | Coordinated motion planning for multiple car-like robots using probabilistic roadmaps[END_REF]. The weakness of this strategy is that one robot must wait for another robot to pass. Another way (Figure 3(b)) is to replan the local path in real time for each robot by using some goal seeking obstacle avoidance algorithms such as Vector Field Histogram (VFH+) [START_REF] Ulrich | VFH+: Reliable obstacle avoidance for fast mobile robots[END_REF] or Nearness Diagram (ND) Navigation [START_REF] Minguez | Nearness diagram (ND) navigation: Collision avoidance in troublesome scenarios[END_REF]. The weakness of this strategy is that robots need some time to replan their new trajectory. Consequently, the two ways both extend the time of the motion planning and limit the system efficiency.

If we can plan separate kinematic paths for multiple robots, then the waiting situation caused by waypoint mutex will be significantly reduced. In addition, the problem of multi-robot task allocation (MRTA) [START_REF] Gerkey | A formal analysis and taxonomy of task allocation in multi-robot systems[END_REF] should also be considered. Our focus in this paper is on the multi-robot motion planning in structured environments. For instance, an office building could be simply divided into three clusters:

corridor, doorway and room. The doorway usually connects the corridor with the room, it is a suitable object for task allocation. Therefore, on the one hand, the problem of waiting situation (especially at the corridors) caused by one path for all robots should be solved. On the other hand, a simple and effective way to coordinate multi-robot motion is to assign different robots to different rooms reachable from the corridors. Besides, more complex environments may require more sophisticated methods such as hand labeled training data [START_REF] Brunskill | Topological mapping using spectral clustering and classification[END_REF], [START_REF] Friedman | Voronoi Random Fields: Extracting the Topological Structure of Indoor Environments via Place Labeling[END_REF] or more complex reasoning [START_REF] Beeson | Towards autonomous topological place detection using the extended voronoi graph[END_REF], [START_REF] Zivkovic | Hierarchical map building and planning based on graph partitioning[END_REF].

Because of the complexity of multi-agent systems (MAS) [START_REF] Burgard | Collaborative multi-robot exploration[END_REF], [START_REF] Gerkey | Sold!: Auction methods for multirobot coordination[END_REF], the target of this paper is not to completely avoid the problem of waiting situation (waypoint mutex), but to minimize the probability of appearance of the waiting situation by using our ACS-PRM approach. Therefore, the coincidence of the waypoint in the plan of two or more robots should be reduced so as to improve the multi-robot motion planning efficiency.

ACS-PRM: ADAPTIVE CROSS SAMPLING PROBABILIS-TIC ROADMAP

There are usually two ways to handle the issue of robot motion planning based on the grid representation of the environment in low dimensional space. One is to use the incremental heuristic search algorithm such as A* [START_REF] Hart | A formal basis for the heuristic determination of minimum cost paths[END_REF] or D* [START_REF] Stentz | Optimal and efficient path planning for partially-known environments[END_REF]. Another is to use the topological map [START_REF] Thrun | Learning metric-topological maps for indoor mobile robot navigation[END_REF] generated on top of the grid-based map such as Voronoi diagram and straight skeleton. Nevertheless, the number of grids increases rapidly when the size of the environment expends, which make these methods inappropriate for complex and extensive environments. Moreover, these methods are hard to deal with the multi-robot motion planning and always increase the computational load as well.

Sampling-based approaches have been proposed to improve the computational efficiency for robot motion planning. The main idea is to avoid the explicit construction of the obstacle region in the C-space (C obs ). Unlike the incremental heuristic search and the topological map methods, the sampling-based approaches work well for complex environments and high-dimensional configuration spaces, and they are generally easier to implement. The probabilistic roadmap planner is one of the typical sampling-based approaches. The original PRM technique is introduced by Kavraki et al. [START_REF] Kavraki | Probabilistic roadmaps for path planning in high-dimensional configuration spaces[END_REF], which has been shown

to perform well in a variety of situations. On the basis of this method, different extensions have been proposed [START_REF] Amato | OBPRM: An obstacle-based PRM for 3D workspaces[END_REF], [START_REF] Wilmarth | MAPRM: A probabilistic roadmap planner with sampling on the medial axis of the free space[END_REF], [START_REF] Song | Randomized motion planning for car-like robots with C-PRM[END_REF], [START_REF] Jouandeau | Algorithmique de la planification de mouvement probabiliste pour un robot mobile[END_REF]. The approach described in this paper is also an extension of PRM, which is aim at performing multi-robot motion planning efficiently.

To deal with the problem of waiting situation in multi-robot motion planning as mentioned in the last section by using the PRM approach, there are substantially two options:

• In the manner of single-query: when two or more robots need to pass the same waypoint simultaneously, each robot resamples the adjacent region and take the motion of the others into account, then generate a novel local roadmap for local replanning.

• In the manner of multi-query: construct a rich roadmap at the beginning to allow robots to plan a different trajectory from others later.

C-space Sampling

The ACS-PRM approach presented in this paper is a multi-query approach. The first step is C-space sampling, in which an adequate number of points should be generated to represent the free space of the environment. The main idea of this step is to let a random point p retracts to a position P (q) with the distance d to the obstacle C obs along horizontal and vertical directions (cross direction).

For autonomous nonholonomic mobile robots, in two dimensions, there are three representational degrees of freedom (DOFs) which are one rotational DOF and two translational DOFs (along or across), but only two controllable DOFs which only move by a forward motion and a steering angle, the configu-

ration space C is the special Euclidean group SE(2) = R 2 ×SO(2)
where SO( 2) is the special orthogonal group of 2D rotations. To avoid the collision caused by the point retracts too close to the obstacle, we

d = r + w, (w > 0) (1)
The set of w is to deal with the negative influence of sensor error and it should be adjusted in practical applications.

C obs represents the set of the obstacle, ∀q ∈ C obs define a direction r q , then determine a symmetry point S(q) which is an intersection of the open-ray with end q direction r q and another C obs :

S(q) = {q + t - → r q |t > 0} ∩ C obs (2)
where, if {q + t -→ r q |t > 0} ∩ C obs = {q}, then define S(q) = ∞. Let dist(x, y) represent the distance between point x and point y, then the retraction function can be described as:

P (q) =      q + d - → r q if dist(q, S(q)) ≥ 2d q+S(q) 2 otherwise ( 3
)
where P (q) is the position for the point p to retract. In this way, the random points are adapted around to the obstacle (see 4(b)), then:

ACS-PRM = {P (q)}|q ∈ C obs } (4)
The implementation of this step is summarized in Algorithm 1. Where the time complexity is O(n)

and the space complexity is O(1). This step corresponds the learning phase of classic implementation of PRM.

Roadmap Building

The second step is roadmap building, in which the potential targets and the milestones should be extracted and connected to the roadmap. In the previous step C-space sampling, if there are sufficient Algorithm 1 Adaptive cross sampling Require: N , the adequate number of points to generate.

Ensure: N points in C f ree by adaptive cross sampling.

1: repeat 2:
Generate a uniformly random point p in C-space.

3:

if p is free then

4:
for horizontal and vertical directions do 5:

find q ∈ C obs the nearest distance from p.

6:

if dist(p, q) ≥ d then p retracts to q + d -→ r q .

8:

else 9:
find {S(q)} = -→ qp ∩ C obs .

10:

p retracts to q+S(q) 2 .

11:

end if 12:
end for 13:

end if 14: until N points have been generated.

points generated, then the points will gather into segments. The main idea of this step is second learning the graph resulted from the previous step while identifying three types of point as follow:

• In the previous step, if dist(p, q) < d, then p will retract to q+S(q) 2 and be labeled as medial axis. Therefore, we find those medial axis segments with length l a small fixed value (in our implementation, we took the thickness of obstacle), and the midpoints of segment are marked as potential target. Figure 4(c) shows the extracted potential targets which are precisely doorways of the structured environment.

• For those segments without containing the potential target, we extract both of the endpoints and mark them as milestone (see Figure 4(d)).

• The points of intersection between two segments are also extracted and marked as milestone (see Figure 4(d)). These milestones have not been used in our experiments, but they will be required for the exploration problem.

This step also corresponds the learning phase of classic implementation of PRM. Figure 4 illustrates the process of generating a roadmap for an example occupancy grid map by using our approach with 200,000 random samples.

Motion Planning

The third step is motion planning, in which each individual robot's kinematic path should be planned by querying the constructed roadmap. The main idea of this step includes the following three points:

• The potential targets {t i } are considered as the goal nodes for path planning and the objects for task allocation as well. Then the individual {r i } robots are assigned to different potential target:

{r i } → {t i }.
• To maximize the difference between the paths, we assign the potential target which is the closest from the robot but further from the previous assigned target to the current individual robot:

t = f urther(closest({t i }, r), t i-1
).

• Similar to the classic PRM, we use the fast local planning method (the straight line planner) for the global path planning, except that we choose the path with the minimal number of milestones for the robots invariably.

This step corresponds the query phase of classic implementation of PRM.

EXPERIMENTS

To evaluate our ACS-PRM approach, we conducted a series of simulation experiments with the wellknown 2D multi-robot simulator Stage [START_REF] Gerkey | The player/stage project: Tools for multi-robot and distributed sensor systems[END_REF]. The experiment is to transport a certain amount of goods from one origination to divers destinations by a fleet of mobile robots. The simulated robot is the Pioneer 2-DX robot equipped with a laser range finder providing 361 samples with 180 degrees field of view and a maximum range of 8 meters. Each robot can localize itself based on an abstract localization device which models the implementation of GPS or SLAM. To transport goods, the robots are equipped with a gripper that enable them to sense, pick up and put down the goods, and the carrying capacity is limited to one unit per robot. Figure 5 shows a typical prototype of Pioneer 2-DX robot with gripper.

We used a different number of robots to conduct several experiments in various environments. Two maps (Figure 6) were used in our simulation which are both structured environment. For each map, the green area signifies the original position of goods, and the yellow area signifies the destinations which are always placed in the rooms. For instance, map A has 8 rooms thus 8 destinations, map B has 7 rooms thus 7 destinations. The transportation team size is varied from 2 to 8 robots. On each team size, The ratio between real-world time and simulation time is about 1:1. We also compared our approach to the commonly used Voronoi-based approach [START_REF] Thrun | Learning metric-topological maps for indoor mobile robot navigation[END_REF] in which a topological map is built on top of the grid map by using the Voronoi diagram and the critical points are extracted like milestones for mobile robot motion planning. All experiments reported in this paper were carried out on a system with an Intel Core 2 Duo E8400 3.00GHz processor, an Intel Q43 Express chipset and two DDR2 800MHz 1024MB dual channel memory.

In the experiments, we assumed that there exists a central server which is able to communicate with all mobile robots and assign the transportation tasks to each individual robot. The transportation task is to transport the goods from the original position to the destination. We also assumed that all the mobile robots share a common grid map and every one has full information about all others so as to implement path planning and obstacle avoidance in real time coordinately. The ACS-PRM is designed to (but not limited to) plan the kinematic path for nonholonomic mobile robots, and in order to get an objective evaluation of the proposed approach, the drive mode of mobile robot is set to differential-steer, furthermore, the strategy of one pass after the other is applied to deal with the possible waypoint mutex problem.

The results of our experiments are given in Figure 7. We measured the transportation time gained by our approach and compared to the Voronoi-based approach. In each plot, the abscissa denotes the team size of the mobile robots, the ordinate denotes the percentage of the transportation time in the total transportation time, and the error bar indicates the confidence interval of each corresponding gain of robot team size with the 0.95 confidence level. Figure 7 shows that, a transportation time saving of 6.7% to 12.2% in map A and 6.1% to 12.0% in map B is obtainable under our ACS-PRM approach compared to the Voronoi-based approach. These results proved that our technique could significantly improve the system planning efficiency.

Moreover, we mentioned earlier that our ACS-PRM approach is more effective than our previous approach because the ACS-PRM spends much less time for the learning phase. The experiments shows that, with the new approach, the mapping time are respectively 0.321 seconds and 0.329 seconds for We also counted the average number of the occurrences of waypoint mutex in each map as shown in Table 1. This table shows that the problem of waiting situation is significantly reduced by using our ACS-PRM approach, because our approach is able to plan separate paths for robots, especially in the corridor, whereas we have only one path for all robots with the Voronoi-based approach.

In fact, the technique proposed in this paper also works well with irregular environments (see Figure 8), just need more complex algorithm to extract the milestones.

CONCLUSIONS

In this paper, we presented a novel approach for coordinated motion planning of multiple robots by using the probabilistic roadmap planner based on a manner of adaptive cross sampling, which we called ACS-PRM. The basic thought of the proposed approach is to build separate kinematic paths for multiple robots to minimize the problem of waiting situation such as collision and congestion caused by waypoint mutex in an effective way, thus to improve the efficiency of automated planning and scheduling. The ACS-PRM mainly consists of three steps: C-space sampling, roadmap building and motion planning. In the first step, an adequate number of points are generated to represent the free space of the environment. In the second step, the potential targets and the milestones are extracted and connected to the roadmap by second learning the graph resulted from the previous step. In the third step, the robot's motion planning is done by querying the constructed roadmap. The first two steps correspond the learning phase of classic implementation of PRM, and the last steps corresponds the query phase of classic implementation of PRM.

In consideration of the context about the issue of multi-robot goods transportation, the experiments were conducted to transport a certain amount of goods by a fleet of mobile robots in structured environments. The experimental results demonstrate that, by using our ACS-PRM approach, the total time needed to complete the transportation mission has been significantly reduced compared to the Voronoi-based approach.

In our future work, we will expand our approach to the irregular environments, not just the structured environments. Furthermore, the proposed work in this paper can be also used in some other applications such as exploration mission, automated surveillance, and search and rescue operations. They are our future consideration as well.

Figure 1 :

 1 Figure 1: Four robots implement a transportation mission cooperatively. The dark blue piece signifies the goods to be transported. The green area represents the original position of goods, and the yellow area represents the destination, which corresponds to every room, where the goods should be delivered to by the mobile robot.

Figure 2 :

 2 Figure 2: A typical waypoint mutex. The black dot represents the waypoint, the gray segment represents the path, and the red and blue arrow represent the direction of the motion of the corresponding color robots respectively.

Figure 3 :

 3 Figure 3: Two ways to deal with the waypoint mutex. The colored lines represent the motion plan for the corresponding color robots respectively. (a) The two robots pass the waypoint in order, the blue robot pass first and the red robot pass later. (b) The two robots take each other as an obstacle and replan its trajectories in real time.

Figure 4 :

 4 Figure 4: Generation of the roadmap based on ACS-PRM. (a) The original gridmap, (b) adaptive cross C-space sampling, (c) the potential targets (doorways) extracted, and (d) the milestones extracted.

Figure 5 :

 5 Figure 5: A typical prototype of Pioneer 2-DX robot with gripper

Figure 6 :

 6 Figure 6: Two environment maps used in our simulation.

Figure 7 :

 7 Figure 7: Transportation time gained by using our ACS-PRM approach compared with the Voronoibased approach.

Figure 8 :

 8 Figure 8: Irregular environment experiment based on ACS-PRM. (a) The original gridmap, (b) adaptive cross C-space sampling.

Table 1 :

 1 Statistics of The Number of Occurrences of The Waypoint Mutex

			(a) map A
	#robots	2	3	4	5	6	7	8
	ACS-PRM	1.6	3.1	6.4	7.5 10.0 11.1 16.2
	Voronoi-based 15.3 18.7 26.0 26.8 19.9 23.7 27.2
			(b) map B
	#robots	2	3	4	5	6	7	8
	ACS-PRM	3.8	4.3	7.1 14.9 12.8 10.3 16.7
	Voronoi-based 17.1 19.2 19.0 26.5 27.4 27.0 29.9
	map A and map B with 200,000 random samples, which are averages of the 10 runs.


Zhi Yan

Nicolas Jouandeau

Arab Ali Cherif

Towards a Probabilistic Roadmap for Multi-robot Coordination

Keywords: Multi-robot system, motion planning, multi-robot coordination, sampling-based approach

In this paper, we discuss the problem of multirobot coordination and propose an approach for coordinated multi-robot motion planning by using a probabilistic roadmap (PRM) based on adaptive cross sampling (ACS). The proposed approach, called ACS-PRM, is a samplingbased method and consists of three steps including Cspace sampling, roadmap building and motion planning. In contrast to previous approaches, our approach is designed to plan separate kinematic paths for multiple robots to minimize the problem of congestion and collision in an effective way so as to improve the system efficiency. Our approach has been implemented and evaluated in simulation. The experimental results demonstrate the total planning time can be obviously reduced by our ACS-PRM approach compared with previous approaches.

Introduction

Motion planning is a fundamental problem in robotics. It could be explained as producing a continuous motion for a robot, that connects a start configuration and a goal configuration, and avoid collision with any static obstacles or other robots in an environment. The robot and obstacle geometry are generally described in a 2D or 3D workspace, and the motion could be represented as a path in configuration space. Motion planning algorithms are widely applied in many fields, such as bioinformatics, robotic surgery, industrial automation, planetary exploration, and intelligent transportation system.

The multi-robot system (MRS) is proposed to deal with some problems that are difficult or impossible to be solved by a single robot, or to improve the system implementation efficiency in some missions completed by multi-robot rather than a single robot [START_REF] Cao | Cooperative mobile robotics: Antecedents and directions[END_REF], [START_REF] Dudek | A taxonomy for multi-agent robotics[END_REF]. The biggest challenge for the MRS is coordination. Without coordination, it will not only lower the system efficiency, but also lead to the failure of the entire system in extreme cases. Figure 1 shows an example of multi-robot coordination, four robots implement a transportation mission cooperatively, the red robot is delivering a goods, the green robot is on its way back after completing a transportation task, the yellow robot is moving to load a Fig. 1: Four robots implement a transportation mission cooperatively. The dark blue piece signifies the goods to be transported. The green area represents the original position of goods, and the yellow area represents the destination, which corresponds to every room, where the goods should be delivered to by the mobile robot. goods, and the orange robot is transporting a goods to the destination location. The coordination of these four robots is obtained by assigning them to different room.

In this paper, we consider the issue of coordinated motion planning for a homogeneous team of autonomous mobile robots in structured environments such as office building, warehouse, and container terminal. The larger context of the research is to establish a multi-robot goods transportation system with security, reliability and efficiency. Most of the proposed approaches for multi-robot motion planning usually have the problem of resource conflict such as congestion and collision [START_REF] Solanas | Coordinated multi-robot exploration through unsupervised clustering of unknown space[END_REF], [START_REF] Wurm | Coordinated multi-robot exploration using a segmentation of the environment[END_REF]. For the transportation issue, a desirable result is that robots replan their individual local path to avoid collision and congestion events, however this fashion often needs additional time and thus limit the transportation efficiency. An undesirable result is that robots are blocked, or the goods are lost or damaged, and thus fail the transportation mission. Therefore, we arranged these cases to the waiting situation problem [START_REF] Yan | Sampling-based multi-robot exploration[END_REF]. To handle this practical problem, this paper presents a novel approach to multi-robot motion planning by using a probabilistic roadmap (PRM) planner which is based on manner of adaptive cross sampling (ACS). This approach called ACS-PRM is decomposed into 3 main steps:

• Firstly, a sufficient number of points should be generated in C-space on an occupancy grid map by using an adaptive cross sampling method. • Secondly, a roadmap should be built while the potential targets and milestones are extracted by post-processing the result of sampling. • Finally, the motion of robots should be planned by querying the constructed roadmap. The rest of the paper is organized as follows: Section 2 describes an overview of some related works; Section 3 discusses the problem of waiting situation; subsequently, Section 4 describes our ACS-PRM approach; Section 5 presents the experimental results obtained with our approach; and the paper is concluded in Section 6 at last.

Related Work

Multi-robot motion planning has been extensively studied for more than a decade during which a wide variety of planning frameworks and solutions have been proposed.

Švestka and Overmars [START_REF] Švestka | Coordinated motion planning for multiple car-like robots using probabilistic roadmaps[END_REF] presented an approach for multiple nonholonomic car-like robots motion planning in the same static workspace by using probabilistic roadmaps, in which the roadmaps for the composite robot are derived from roadmaps for the underlying simple robots, and the latter is computed by a probabilistic single-robot learning method. The authors introduced the notion of super-graphs for multirobot path planning, and their implementation covered the construction of the simple roadmap and the super-graphs. This approach is probabilistically complete because a given problem could be solved within a finite amount of time.

Moors et al. [START_REF] Moors | A probabilistic approach to coordinated multi-robot indoor surveillance[END_REF] presented a graph-based algorithm for coordinate multi-robot motion planning in 2D indoor environments. The scenario of this research is multi-robot indoor surveillance. The proposed approach takes the limitations and uncertainties of sensors into account, and generates the coordinated motion plan for multiple robots by using A* search algorithm. The authors also introduced a framework based on realistic probabilistic sensor models and worst case assumptions on the intruder's motions in order to compare different approaches and evaluate the coordination performance of the proposed approach.

Clark [START_REF] Clark | Probabilistic road map sampling strategies for multirobot motion planning[END_REF] presented a multi-robot motion planning strategy based on the probabilistic roadmap within a dynamic robot network (DRN) coordination platform. The DRN platform is an ad hoc network, in which single-query PRM is queried as a centralized planner to plan trajectories for all robots. The PRM planner is optimized to speed queries for multirobot motion planning by using new sampling strategies. At Fig. 2: A typical waypoint mutex. The black dot represents the waypoint, the gray segment represents the path, and the red and blue arrow represent the direction of the motion of the corresponding color robots respectively. first, a method of sampling PRM milestones is identified to enable fast coverage of the configuration space. Then, a method of generating PRM milestones is introduced to decrease the planning time. Finally, an endgame region is defined to improve the likelihood of finding solutions when goal configurations are highly constrained.

Saha and Isto [START_REF] Saha | Multi-robot motion planning by incremental coordination[END_REF] presented a strategy for decoupled multi-robot motion planning. The proposed strategy, which aims at improving the reliability of the basic decoupled planning approach, partially merges the two phases of the basic approach. The first phase is to compute a collision-free path to avoid the obstacles in the environment and the other robots, the second phase is coordinating the individual robot motions so that only one robot at a time may enter the area of potential inter-robot interference. The proposed approach searches for motions for a robot and coordination of motions of robots along paths already planned while ignoring the robots whose motions have not been planned simultaneously. This approach is inherently incomplete.

Besides, there are some other approaches developed with various strategies [START_REF] Burgard | Collaborative multi-robot exploration[END_REF], [START_REF] Solanas | Coordinated multi-robot exploration through unsupervised clustering of unknown space[END_REF], [START_REF] Regele | Cooperative multi-robot path planning by heuristic priority adjustment[END_REF], [START_REF] Wurm | Coordinated multi-robot exploration using a segmentation of the environment[END_REF].

Waiting Situation Problem

Multi-agent environments can be cooperative or competitive [START_REF] Russell | Artificial Intelligence: A Modern Approach (2nd Edition)[END_REF]. Of every agent in a team, the other agents can be considered as teammates (cooperative) or movable obstacles (competitive). One of the most important reasons which limit the efficiency of the multi-robot motion planning is the waiting situation such as the congestion and collision between robots. The core of the problem can be considered as the waypoint mutex in multi-robot motion planning. Figure 2 depicts a typical waypoint mutex. Two robots move to the same waypoint simultaneously: the red robot moves from the top left towards the right and the blue robot moves from the right towards the bottom left. Because of the waypoint can be assigned only to one robot at a time, then the mutex of the waypoint happens.

Generally, there are two ways to deal with the waypoint mutex as shown in Figure 3. One (Figure 3(a)) is to let robots pass the waypoint one by one [START_REF] Švestka | Coordinated motion planning for multiple car-like robots using probabilistic roadmaps[END_REF]. The weakness of this strategy is that one robot must wait for another robot to pass. Another way (Figure 3(b)) is to replan the local path in real time for each robot by using some goal seeking obstacle avoidance algorithms such as Vector Field Histogram (VFH+) [START_REF] Ulrich | VFH+: Reliable obstacle avoidance for fast mobile robots[END_REF] or Nearness Diagram (ND) Navigation [START_REF] Minguez | Nearness diagram (ND) navigation: Collision avoidance in troublesome scenarios[END_REF]. The weakness of this strategy is that robots need some time to replan their new trajectory. Consequently, the two ways both extend the time of the motion planning and limit the system efficiency.

If we can plan separate kinematic paths for multiple robots, then the waiting situation caused by waypoint mutex will be obviously reduced. In addition, the problem of multi-robot task allocation (MRTA) [START_REF] Gerkey | A formal analysis and taxonomy of task allocation in multi-robot systems[END_REF] should also be considered. Our focus in this paper is on the multi-robot motion planning in structured environments. For instance, an office building could be simply divided into three clusters: corridor, doorway and room. The doorway usually connects the corridor with the room, it is a suitable object for task allocation. Therefore, on the one hand, the problem of waiting situation (especially at the corridors) caused by one path for all robots should be solved. On the other hand, a simple and effective way to coordinate multi-robot motion is to assign different robots to different rooms reachable from the corridors. Besides, more complex environments may require more sophisticated methods such as hand labeled training data [START_REF] Brunskill | Topological mapping using spectral clustering and classification[END_REF], [START_REF] Friedman | Voronoi random fields: Extracting the topological structure of indoor environments via place labeling[END_REF] or more complex reasoning [START_REF] Beeson | Towards autonomous topological place detection. using the extended voronoi graph[END_REF], [START_REF] Zivkovic | Hierarchical map building and planning based on graph partitioning[END_REF].

Because of the complexity of multi-robot systems [START_REF] Burgard | Collaborative multi-robot exploration[END_REF], [START_REF] Gerkey | Sold!: Auction methods for multirobot coordination[END_REF], the target of this paper is not to completely avoid the problem of waiting situation (i.e., waypoint mutex), but to minimize the probability of appearance of the waiting situation by using our ACS-PRM approach. Therefore, the coincidence of the waypoint in the plan of two or more robots should be reduced so as to improve the multi-robot motion planning efficiency.

ACS-PRM: Adaptive Cross Sampling Based Probabilistic Roadmap

There are usually two ways to handle the issue of robot motion planning based on the grid representation of the environment in low dimensional space. One is to use the incremental heuristic search algorithm such as A* [START_REF] Hart | A formal basis for the heuristic determination of minimum cost paths[END_REF] or D* [START_REF] Stentz | Optimal and efficient path planning for partially-known environments[END_REF]. Another is to use the topological map [START_REF] Thrun | Learning metric-topological maps for indoor mobile robot navigation[END_REF] generated on top of the grid-based map such as Voronoi diagram and straight skeleton. Nevertheless, the number of grids increases rapidly when the size of the environment expands, which make these methods inappropriate for complex and extensive environments. Moreover, these methods are hard to deal with the multi-robot motion planning and always increase the computational load.

Sampling-based approaches have been proposed to improve the computational efficiency for robot motion planning. The main idea is to avoid the explicit construction of the obstacle region in the C-space (C obs ). Unlike the incremental heuristic search and the topological map methods, the sampling-based approaches work well for complex environments and high-dimensional configuration spaces, and they are generally easier to implement. The probabilistic roadmap (PRM) planner1 is one of the typical samplingbased approaches. The original PRM technique is introduced by Kavraki et al. [START_REF] Kavraki | Probabilistic roadmaps for path planning in high-dimensional configuration spaces[END_REF], which has been shown to perform well in a variety of situations. On the basis of this method, different extensions have been proposed [START_REF] Amato | OBPRM: An obstacle-based prm for 3d workspaces[END_REF], [START_REF] Wilmarth | MAPRM: A probabilistic roadmap planner with sampling on the medial axis of the free space[END_REF], [START_REF] Song | Randomized motion planning for car-like robots with C-PRM[END_REF]. The approach described in this paper is also an extension of PRM, which is aimed at performing multi-robot motion planning efficiently.

To deal with the problem of waiting situation in multirobot motion planning as mentioned in the last section by using the PRM approach, there are substantially two options:

• In the manner of single-query: when two or more robots need to pass the same waypoint simultaneously, each robot resamples the adjacent region and takes the motion of the others into account, then generate a novel local roadmap for local replanning. • In the manner of multi-query: construct a rich roadmap at the beginning to allow robots to plan a different trajectory from others later.

C-space Sampling

The ACS-PRM approach presented in this paper is a multi-query approach. The first step is C-space sampling, in which a sufficient number of points should be generated to represent the free space of the environment. The main idea of this step is to let a random point p retracts to a position P (q) with the distance d to the obstacle C obs along horizontal and vertical directions (i.e., cross direction).

For autonomous nonholonomic mobile robots, in two dimensions, there are three representational degrees of freedom (DOFs) which are one rotational DOF and two translational DOFs (along or across), but only two controllable DOFs which only move by a forward motion and a steering angle, the configuration space C is the special Euclidean group SE(2) = R 2 × SO(2) where SO(2) is the special orthogonal group of 2D rotations. To avoid the collision caused by the point retracts too close to the obstacle, we set the distance d as the sum of the positive number w and the radius r of the minimum circle to cover the robot with centering at the rotation center of the robot:

d = r + w, (w > 0) (1)
The set of w is to deal with the negative influence of sensor error and it should be adjusted in practical applications. C obs represents the set of the obstacle, ∀q ∈ C obs define a direction r q , then determine a symmetry point S(q) which is an intersection of the open-ray with end q direction r q and another C obs :

S(q) = {q + t - → r q |t > 0} ∩ C obs (2)
where, if {q + t -→ r q |t > 0} ∩ C obs = {q}, then define S(q) = ∞. Let dist(x, y) represent the distance between point x and point y, then the retraction function can be described as:

P (q) = q + d - → r q if dist(q, S(q)) ≥ 2d q+S(q) 2 otherwise (3)
where P (q) is the position for the point p to retract. In this way, the random points are adapted around to the obstacle (see Figure 4(b)), then:

ACS-PRM = {P (q)}|q ∈ C obs } (4)
The implementation of this step is summarized in Algorithm 1, where the time complexity is O(n) and the space complexity is O(1). This step corresponds the learning phase of classic implementation of PRM.

Roadmap Building

The second step is roadmap building, in which the potential targets and the milestones should be extracted and connected to the roadmap. In the previous step C-space sampling, if there are sufficient points generated, then the points will gather into segments. The main idea of this step is post-processing the graph resulted from the previous step while identifying three types of point as follows:

• In the previous step, if dist(p, q) < d, then p will retract to q+S(q) 2 and be labeled as the medial axis. Therefore, we find those medial axis segments with length l a small fixed value (in our implementation, we took the thickness of obstacle), and the midpoints of segments are marked as potential target for task allocation. Figure 4(c) shows the extracted potential targets which are precisely doorways of the structured environment.

Algorithm 1 Adaptive cross sampling

Require: N , the sufficient number of points to generate. Ensure: N points in C f ree by adaptive cross sampling.

1: repeat 2:

Generate a uniformly random point p in C-space.

3:

if p is free then

4:
for horizontal and vertical directions do 5:

Find q ∈ C obs the nearest distance from p.

6:

if dist(p, q) ≥ d then p retracts to q + d -→ r q .

8:

else 9:
Find {S(q)} = -→ qp ∩ C obs .

10:

p retracts to q+S(q) 2 .

11:

end if 12:
end for 13:

end if 14: until N points have been generated.

• For those segments without containing the potential target, we extract both of the endpoints and mark them as milestone (see Figure 4(d)). • The points of intersection between two segments are also extracted and marked as milestone (see Figure 4(d)). These milestones have not been used in our experiments, but they will be required for the exploration problem. This step also corresponds the learning phase of classic implementation of PRM. Figure 4 illustrates the process of generating a roadmap for an example occupancy grid map by using our approach with 200,000 random samples.

Motion Planning

The third step is motion planning, in which each individual robot's kinematic path should be planned by querying the constructed roadmap. The main idea of this step includes the following three points:

• The potential targets {t i } are considered as the goal nodes for path planning and the objects for task allocation as well. Then, the individual {r i } robots are assigned to different potential target:

{r i } → {t i } (5)
• To maximize the difference between the paths, we assign the potential target which is the closest from the robot but further from the previously assigned target to the current individual robot:

t = f urther(closest({t i }, r), t i-1 ) (6)
• Similar to the classic PRM, we use the fast local planning method (i.e., the straight line planner) for the global path planning, except that we choose the path with the minimum number of milestones for the robots invariably. This step corresponds the query phase of classic implementation of PRM.

Experiments

To evaluate our ACS-PRM approach, we conducted a series of simulation experiments with the well-known 2D multi-robot simulator Stage [START_REF] Gerkey | The player/stage project: Tools for multi-robot and distributed sensor systems[END_REF]. The experiment is to transport a certain amount of goods from one origination to divers destinations by a fleet of mobile robots. The simulated robot is the Pioneer 2-DX robot equipped with a laser range finder providing 361 samples with 180 degrees field of view and a maximum range of 8 meters. Each robot can localize itself based on an abstract localization device which models the implementation of GPS or SLAM. To transport goods, the robots are equipped with a gripper that enable them to sense, pick up and put down the goods, and the carrying capacity is limited to one unit per robot. Figure 5 shows a typical prototype of Pioneer 2-DX robot with gripper. We used a different number of robots to conduct several experiments in various environments. Two maps (Figure 6) were used in our simulation which are both structured environments. For each map, the green area signifies the original position of goods, and the yellow areas represent the destinations which are always placed in the rooms. For instance, map A has 8 rooms thus 8 destinations, map B has 7 rooms thus 7 destinations. The transportation team size is varied from 2 to 8 robots. On each team size, 10 experimental runs are performed for a transportation mission of 50 goods. The mission objective is to transport the goods to every room equally.

The ratio between real-world time and simulation time is about 1:1. We also compared our approach to the commonly used Voronoi-based approach [START_REF] Thrun | Learning metric-topological maps for indoor mobile robot navigation[END_REF] in which a topological map is built on top of the grid map by using the Voronoi diagram, and the critical points are extracted like milestones for mobile robot motion planning. All experiments reported in this paper were carried out on a system with an Intel Core 2 Duo E8400 3.00GHz processor, an Intel Q43 Express chipset and two DDR2 800MHz 1024MB dual channel memory.

In the experiments, we assumed that there exists a central server which is able to communicate with all mobile robots and assign the transportation tasks to each individual robot. The transportation task is to transport the goods from the original position to the destination. We also assumed that all the mobile robots share a common grid map and everyone has full information about all others so as to implement path planning and obstacle avoidance in real time coordinately.

The ACS-PRM is designed to (but not limited to) plan the kinematic path for nonholonomic mobile robots, and in order to get an objective evaluation of the proposed approach, the drive mode of mobile robot is set to differential-steer, furthermore, the strategy of one pass after the other is applied to deal with the possible waypoint mutex problem. The results of our experiments are given in Figure 7. We measured the transportation time gained by our approach and compared to the Voronoi-based approach. In each plot, the abscissa denotes the team size of the mobile robots, the ordinate denotes the percentage of the transportation time in the total transportation time, and the error bar indicates the confidence interval of each corresponding gain of robot team size with the 0.95 confidence level. Figure 7 shows that, a transportation time saving of 6.7% to 12.2% in map A and 6.1% to 12.0% in map B is obtainable under our ACS-PRM approach compared to the Voronoi-based approach. These results proved that our technique could obviously improve the system of planning efficiency.

Moreover, we mentioned earlier that our ACS-PRM approach is more effective than our previous approach because the ACS-PRM spends much less time for the learning phase. The experiments show that, with the new approach, the mapping times are respectively 0.321 seconds and 0.329 seconds for map A and map B with 200,000 random samples, which are averages of the 10 runs.

We also counted the average number of occurrences of waypoint mutex in each map as shown in Table 1. This table shows that the problem of waiting situation is obviously reduced by using our ACS-PRM approach, because our approach is able to plan separate paths for robots, especially in the corridor. Unlike the Voronoi-based approach, there is only one path for all robots.

In fact, the technique proposed in this paper also works well with irregular environments. Figure 8 illustrates an example with 20,000 random samples.

Conclusion

In this paper, we presented a novel approach for coordinated motion planning of multiple robots by using the probabilistic roadmap planner based on a manner of adaptive cross sampling, which we called ACS-PRM. The basic thought of the proposed approach is to build separate kinematic paths for multiple robots to minimize the problem of waiting situation such as collision and congestion caused by waypoint mutex in an effective way, thus to improve the efficiency of automated planning and scheduling. The ACS-PRM mainly consists of three steps: C-space sampling, roadmap building and motion planning. In the first step, a sufficient number of points are generated to represent the free space of the environment. In the second step, the potential targets and the milestones are extracted and connected to the roadmap by post-processing the graph resulted from the previous step. In the third step, the robot's motion planning is done by querying the constructed roadmap. The first two steps correspond the learning phase of classic implementation of PRM, and the last step corresponds the query phase of classic implementation of PRM.

In consideration of the context of the issue of multirobot goods transportation, the experiments were conducted to transport a certain amount of goods by a fleet of mobile robots in structured environments. The experimental results demonstrate that, by using our ACS-PRM approach, the total time needed to complete the transportation mission has been obviously reduced compared to the Voronoi-based approach.

In our future work, we will expand our experiments to various irregular environments, not just the structured environments. Furthermore, the proposed work in this paper can be also used in some other applications such as exploration mission, automated surveillance, and search and rescue operations. They are our future consideration as well.

Fig. 3 :

 3 Fig. 3: Two ways to deal with the waypoint mutex. The colored lines represent the motion plan for the corresponding color robots respectively. (a) The two robots pass the waypoint in order, the blue robot pass first and the red robot pass later. (b) The two robots take each other as an obstacle and replan its trajectories in real time.

Fig. 4 :

 4 Fig. 4: Generation of the roadmap based on ACS-PRM. (a) The original gridmap, (b) adaptive cross sampling in Cspace, (c) the extracted potential targets (doorways), (d) the extracted milestones, (e) the roadmap coverage of environment, and (f) an instance of path.

Fig. 5 :Fig. 6 :

 56 Fig. 5: A typical prototype of Pioneer 2-DX robot with gripper.

Fig. 7 :

 7 Fig. 7: Transportation time gained by using our ACS-PRM approach compared with the Voronoi-based approach.

Fig. 8 :

 8 Fig. 8: Irregular environment experiment based on ACS-PRM. (a)Adaptive cross sampling in C-space, (b) the extracted milestones.

Table 1 :

 1 Statistics of The Number of Occurrences of The

	Waypoint Mutex
			(a) map A
	#robots	2	3	4	5	6	7	8
	ACS-PRM	1.6	3.1	6.4	7.5	10.0	11.1	16.2
	Voronoi-based 15.3	18.7	26.0	26.8	19.9	23.7	27.2
			(b) map B
	#robots	2	3	4	5	6	7	8
	ACS-PRM	3.8	4.3	7.1	14.9	12.8	10.3	16.7
	Voronoi-based 17.1	19.2	19.0	26.5	27.4	27.0	29.9

A reference implementation of this method in C++ is available online at: http://www.ai.univ-paris8.fr/ yz


Zhi Yan

Nicolas Jouandeau

Arab Ali Cherif

ON THE PROBLEM OF TASK PLANNING IN MULTI-ROBOT SYSTEMS

Keywords: Task planning, multi-robot systems, coordination

Multi-robot task planning (MRTP) is one of the fundamental problems for multi-robot systems. An important question facing this research topic is, which robot should execute which task so as the expected overall system performance can be maximized? Many approaches have been proposed for such a purpose. This paper investigates the existing works in the field. The approaches have been surveyed and some representatives are compared with detailed results. A brief discussion and further research perspectives are also given at the end of the paper.

INTRODUCTION

The task of coming up with a sequence of actions that will achieve a goal is called planning [START_REF] Russell | Artificial Intelligence: A Modern Approach[END_REF]. In multi-robot systems (MRS), planning can be used to coordinate robots to accomplish the team mission. Unfortunately, optimal planning for MRS is typically an N P -hard problem. The challenge then is to have tractable planning that produces good solutions [START_REF] Dias | Market-based multirobot coordination: A survey and analysis[END_REF]. Multi-robot planning is usually divided into two aspects: task planning and motion planning. Task planning involves task decomposition and task allocation. So far, research on task planning of MRS is concentrated on task allocation problem, and relatively little on task decomposition problem. In fact, the task decomposition is an important research topic because the effect of task allocation could be directly influenced by it.

MULTI-ROBOT TASK DECOMPOSITION

The problem of multi-robot task decomposition (MRTD) mainly refers to that the total mission to be completed is decomposed into several single subtasks which can be completed independently by a robot separately, according to the characteristic, requirement and resource allocation of the total mis-sion itself [START_REF] Chen | Research on the approach of task decomposition in soccer robot system[END_REF]. [START_REF] Stone | Task decomposition, dynamic role assignment, and low-bandwidth communication for real-time strategic teamwork[END_REF] achieved collaboration between agents through the introduction of formations which decomposes the task space defining a set of roles with associated behaviors. [START_REF] Botelho | M+: A scheme for multi-robot cooperation through negotiated task allocation and achievement[END_REF] presented a decentralized system to describe and perform task planning, decomposition and allocation in multi-robot environments, called M+ protocol. [START_REF] Zlot | Complex task allocation for multiple robots[END_REF] 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. [START_REF] Tang | Asymtre: Automated synthesis of multi-robot task solutions through software reconfiguration[END_REF] considered that, in typical approaches to multi-robot team working, the decomposition of the team task into subtasks is defined by the human designer in advance of the robot team performance, and this pattern also outlines the available multi-robot task solutions in advance of the mission. So they described a methodology for automatically synthesizing task solutions for heterogeneous multi-robot teams.

MULTI-ROBOT TASK ALLOCATION

The problem of multi-robot task allocation (MRTA) can be considered as an instance of the well-known optimal assignment problem (OAP). In domains where the group dynamics have a significant effect on group performance, MRTA is known to be N Phard [START_REF] Gerkey | A formal analysis and taxonomy of task allocation in multi-robot systems[END_REF]) [START_REF] Dahl | Multi-robot task allocation through vacancy chain scheduling[END_REF]. This is the most common case in MRS. The task allocation in MRS is generally undertaken to assign robots to tasks (or tasks to robots) so as to maximize the expected overall system performance. However, because MRTA becomes a dynamic decision problem that 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. [START_REF] Gerkey | A formal analysis and taxonomy of task allocation in multi-robot systems[END_REF] gave a formal analysis and domain-independent taxonomy of MRTA problems, in which the MRTA problems have been classified into seven categories according to ability of robot to perform tasks, number of robots required for a task, and manner of the task assignment. They also analyzed and compared some iterated assignment architectures: ALLIANCE (Parker, 1994a), BLE [START_REF] Werger | Broadcast of local eligibility for multi-target observation[END_REF], and M+ [START_REF] Botelho | M+: A scheme for multi-robot cooperation through negotiated task allocation and achievement[END_REF], and some online assignment architectures: MURDOCH (auction-based) [START_REF] Gerkey | Sold!: Auction methods for multirobot coordination[END_REF], first-price auctions (market-based) [START_REF] Stentz | A free market architecture for coordinating multiple robots[END_REF], and dynamic role assignment [START_REF] Chaimowicz | Dynamic role assignment for cooperative robots[END_REF], for MRTA, respectively.

The contract net protocol (CNP) has been developed by [START_REF] Smith | The contract net protocol: Highlevel communication and control in a distributed problem solver[END_REF], which aims to achieve task assignment with distributed control by a negotiation process in multi-agent systems. So far, most methods of MRTA are based on the CNP model. [START_REF] Botelho | M+: A scheme for multi-robot cooperation through negotiated task allocation and achievement[END_REF] presented M+ system, a scheme for multi-robot cooperation through negotiated task allocation and achievement, which is the first CNP-based approach to MRTA. [START_REF] Stentz | A free market architecture for coordinating multiple robots[END_REF] presented the ideas of free market architecture for coordinating a group of robots to achieve a given objective (marketbased approach). This architecture defines revenue and cost functions across the possible plans for executing a specified task. The task is accomplished by dividing it into subtasks 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-interests. [START_REF] Zlot | Multi-robot exploration controlled by a market economy[END_REF] applied these ideas to multi-robot mapping and exploration problem. This work borrows the market architecture which seeks to maximize benefit while minimizing cost, thus aiming to maximize utility. The benefit is information gained by visiting a goal point, the cost is the estimated distance traveled to reach the goal (by using D* algorithm [START_REF] Stentz | Optimal and efficient path planning for partially-known environments[END_REF]), then the utility is the difference between the benefit and the cost. The market-based coordination architecture has been applied to a Mars exploration scenario (combined with D* algorithm for robot motion planning). [START_REF] Gerkey | Sold!: Auction methods for multirobot coordination[END_REF] presented the first online assignment architecture MURDOCH, which uses a first-price auction to assign each task (auction-based approach). The auction proceeds in five steps: task announcement, metric evaluation, bid submission, close of auction, and progress monitoring/contract renewal. The MUR-DOCH system has been tested in two different domains: a long-term loosely coupled task domain and a short-term tightly coupled box-pushing task. The major differences between auction-based approach and market-based approach are that, 1) auction-based approach uses the bid based on the estimated cost, but market-based approach takes into account both cost and benefit, 2) auction-based approach does not allow task reassignment, but market-based approach allows later reassignment.

In addition, [START_REF] Dahl | Multi-robot task allocation through vacancy chain scheduling[END_REF] presented an algorithm for task allocation in groups of homogeneous robots, which is based on vacancy chains, a resource distribution strategy common in human and animal societies. This algorithm uses local task selection, reinforcement learning for estimation of task utility, and reward structures based on the vacancy chain framework. [START_REF] Hanna | Decentralized approach for multirobot task allocation problem with uncertain task execution[END_REF] proposed an approach which 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 using Markov decision process (MDP). In the second stage, an auction-based mechanism is applied to assign tasks to robots. [START_REF] Michael | A Comparison of Three CNP-based Online Multi-robot Task Allocation Methods[END_REF] proposed a distributed market-based coordination algorithm where agents are able to bid for task assignment with the assumption that agents have knowledge of all tasks as well as the maximum number of agents that can be assigned to every individual task. Each auction is performed among neighboring groups of agents and requires only local communication. They verified their algorithm in multi-robot formation control problem. [START_REF] Shiroma | Co-MutaR: A framework for multi-robot coordination and task allocation[END_REF] proposed a framework called CoMutaR, which is designed to both tackle task allocation and coordination problems in MRS. This framework enables the single robot to perform multiple tasks concurrently by periodically checking and updating task-related information during implementation. It has been tested and evaluated in simulation in object transportation, area surveillance, and multi-robot box pushing problem. [START_REF] Wawerla | A fast and frugal method for team-task allocation in a multi-robot transportation system[END_REF] 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 using only locally obtainable information and single value communication. [START_REF] Yan | Multi-robot decentralized exploration using a trade-based approach[END_REF] developed a lightweight and robust decentralized approach based on trade rules for coordinated multi-robot exploration (trade-based approach). This approach is designed to simulate the relationship between buyers and sellers in a business system, to achieve dynamic task allocation by using a mechanism of unsolicited bid. A comparison between market-based, auctionbased and trade-based approaches is given in Table 1.

Eventually, the task allocation for heterogeneous and homogeneous systems may be different. In heterogeneous systems, task allocation may be determined by individual capabilities. [START_REF] Parker | Heterogeneous Multi-Robot Cooperation[END_REF] 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 to perform a mission from the available pool of heterogeneous robots. Task coverage reaches the maximum value in homogeneous teams, and decreases as teams become more heterogeneous. But in homogeneous systems, agents may need to differentiate into different roles at design time or dynamically at run time [START_REF] Yan | Multi-robot decentralized exploration using a trade-based approach[END_REF].

CONCLUSION

In this paper, we have briefly discussed the existing works on the problem of multi-robot task planning (MRTP). Two important aspects, multi-robot task decomposition (MRTD) and multi-robot task allocation (MRTA), were identified. Three online MRTA methods based on contract net protocol, market-based, auction-based and trade-based, were compared with detailed results. Because there is no common benchmarking platform and planning problems, thus the purpose of the comparison is not to point out which method is the best, but give an overview to improve our understanding. Different strategies might be suited to different planning scenarios.

We believe that the following are some promising avenues for future research:

• The task decomposition can directly affect the efficiency of task allocation. A more complete theory should be achieved.

• Environments where robots work in are usually dynamic. Due to the unpredictability and uncertainty of the environment, the revenue and cost functions for task allocation will be difficult to define. For the purpose of maximizing system per-formance, robust definitions and metrics for various scenarios should be developed. • The motion of the robot is also an important factor influencing task achievement. A future challenge is to combine both task and motion planning reasonably, in order to make the multi-robot systems can be situated to more complex tasks in more complex environments.