Many successful robotic systems use maps of the environment to perform their tasks. In this paper, we propose a cooperative exploration strategy for multi-agent robots. This proposal is a parallelization of the basic SRT method, the following functionalities were added to it: cooperation to increase the e±ciency, coordination to avoid con°icts and communication to cooperate and to coordinate. The goal in robot exploration must be to minimize the overall exploration time, and multiple robots produce more accurate maps by merging overlapping information that helps to stabilize the sensor uncertainty and to reach the goal. We present simulation results to show the performance of the proposed technique.
Although most mobile robotic systems use a single robot that only operates in
its environment, a number of researchers have considered the advantages and
disadvantages of the potential use of a group of robots that cooperate for the
accomplishment of a required task [
The research domain of multi-agent robot systems can be divided into
subdomains according to the task given to the robot group [
In the ¯rst activity, a group of robots receives the order to explore/map an
unknown region. The goal is to obtain a detailed topography of the desired area.
In most exploration approaches, the boundary between know and unknown
territory (the frontier) is used in order to maximize the information gain. In [
Closely related to the exploring/mapping activity, the second one is called complete coverage, where the robots have to move over all of the free surface in the space.
Since exploration algorithms are already devised for a single robot it seems straightforward to divide the area to be explored into disjunct regions, each of which is assigned to a single robot. The robots communicate to each other the area they have explored so that no part of the free space will be explored twice unnecessarily. At no point during the task are the robots trying to form a ¯xed formation. Each robot explores a di®erent part of the unknown region and sends its ¯nding to a central device which combines the data received from the robots into one global map of the area.
This paper presents a strategy to explore an unknown environment by
multiagent robots. The strategy is a parallelization of the SRT (Sensor-based Random
Tree) method, which was presented in [
MAS may be comprised of homogeneous or heterogeneous agents, it is considered as crucial technology for the e®ective exploitation of the increasing availability of diverse of heterogeneous and distributed on-line information sources. MAS is a framework for building large, complex and robust distributed information processing systems which exploit the e±ciencies of organized behavior. Teamwork and communication are two important processes within multi-agent robots designed to act in a coherent and coordinated manner.
Consider a population of n identical robots. Each robot is equipped with a ring of range ¯nder sensor or a laser range ¯nder, the sensory system provides the local safe region (LSR) S(q). The robots move in a planar workspace, i.e., R2 or a connected subset of it; the assumption of planar workspace is not restrictive, 3D worlds are admissible as long as the sensory system allow the reconstruction of a planar LSR for planning the robot motion. Each robot is a polygon or another shape subject to non-holomic constraints. The robot also knows its con¯guration q, one can eliminate this assumption by incorporating a localization module in the method. The robots know its ID number and each robot can broadcast within a communication range Rc the information stored in its memory (or relevant portions of it) at any time. The robot ID number is included in the heading of any transmission. The robot is always open for receiving communication from other robots inside Rc.
The design of the cooperative exploration strategy proceeds from the parallelization of the basic SRT method, each robot builds one or more partial maps of the environment, organized in a collection of SRTs. Each node of an SRT represents a con¯guration q which was visited by at least one robot, together with the associated Local Safe Region S(q). An arc between two nodes represents a collision-free path. The tree is incrementally built by extending the structure in the most promising direction via a biased random mechanism. The presence of other robots in the vicinity is taken into account at this stage in order to maximize the information gain and guarantee collision avoidance.
The exploration algorithm for each robot is shown in Figure 1. First, the procedure BUILD SRT is executed, i.e., each robot builds its own SRT, T is rooted at its starting con¯guration qinit. This procedure terminates when the robot can not further expand T . Later, the robot executes the SUPPORT OTHERS procedure, this action contributes to the expansion of the SRTs that have been built by others robots. When this procedure ¯nishes, the robot returns to the root of its own tree and ¯nishes its exploration.
BUILD Multi-SRT(qinit) 1 T :init(qinit) 2 BUILD SRT(qinit:T ); 3 SUPPORT OTHERS(qinit);
The procedure BUILD SRT is shown in Figure 2. In each iteration of the BUILD SRT, the robot uses all available information (partially collected by itself and partially gained through the communication with other robots) to identify the group of engaged robots (GER), i.e. the other robots in the team with which cooperation and coordination are adequate. This is achieved by the construction of the ¯rst group of pre-engaged robots (GPR), or robots that are candidates to be members of the GER, and are synchronized with them (BUILD AND WAIT GPR). Then, the robot collects data through its sensory systems, it builds the current LSR (PERCEIVE) and updates its own tree T . The current GER can now be built (BUILD GER). At this point the robot processes its local frontier (the portion of its current LSR limit leads to areas that are still unexplored) on the basis of T as well as any other tree Ti gained through communication and stored in its memory (LOCAL FRONTIER).
If the local frontier is not empty, the robot generates a random con¯guration contained in the current LSR and headed towards the local frontier, if not, the target con¯guration is ¯xed to the node father with a backward movement (PLANNER). If the GER is composed only by the same robot, the robot moves directly to its target. Otherwise, the paths advanced by the robot in the GER are checked for mutual collisions, and classi¯ed in feasible and unfeasible paths (CHECK FEASIBILITY). If the subset Gu of robots with unfeasible paths is vacuum, a coordination stage takes place, perhaps, con¯rming or modifying the current target of the robot (COORDINATE). In particular, the motion of the robot can be banned by simply readjusting the target to the current con¯guration. Then, the function MOVE TO transfers the robot to the target (when this is di®erent from qact). The loop is repeated until the condition in the output line 15 is veri¯ed: the robot is unable to expand the tree T (no local frontiers remaining) and therefore it has to move back to the root of its SRT.
BUILD SRT(qinit; T ) 1 qact = qinit; 2 do 3 BUILD AND WAIT GPR(); 4 S(qact) à PERCEIVE(qact); 5 ADD(T ; (qact; S(qact))); 6 G ÃBUILD GER(); 7 F(qact) à LOCAL FRONTIER(qact; S(qact); T ; S Ti); 8 qtarget à PLANNER(qact; F(qact); qinit); 9 if qtarget 6= N U LL 10 if jGj > 1 11 (Gf ; Gu) à CHECK FEASIBILITY(G); 12 if Gu 6= ; 13 qtarget à COORDINATE(Gf ; Gu); 14 qact à MOVE TO(qtarget); 15 while qtarget 6= N U LL
We detail the most important stages of the BUILD SRT procedure [
Two robots are GPR-coupled if the distance between their target con¯gurations is less than 2Rp, i.e. twice the range of perception of the sensorial system. The GPR of the robot is then built by grouping together all robots and connecting a chain of coupled GPRs (see Figure 3, left). To achieve synchronization, the GPR is calculated and updated until all its members are stationary (BUILD AND WAIT GPR). The communication range, Rc, clearly plays an important role in the construction of the GPR; for this method two cases have been considered, according to the communication range: 1. Limited communication range. Since the maximum distance between the robot and any other robot GPR-coupled is 3Rp (the other robot can still be moving to its target, which however could not be further away than Rp of the current con¯guration) , it is su±cient to assume that Rc ¸ 3Rp to ensure that the GPR accounts for all the robots that are candidates to belong to the GER. 2. Unlimited communication range. Given the nature of this communication, the robot always knows the status of the other robots, and therefore will know which robots are candidates to be GPR-coupled; the distance to be GPR-coupled as in the above case will remain 3Rp. In this way, as in the previous case, it is ensured that the GPR accounts for all the robots that are candidates to belong to the GER.
The synchronization phase ensures that all robots in the GPR are stationary when the GER is processed. The GER is a symmetric structure, this is the same for all robots in the group. The GER is a cornerstone in our approach, as it identi¯es a group of robots that, in view of its vicinity, spontaneously agree to cooperate and coordinate with each other on a temporary basis. Frontier extraction. Once the robot has been synchronized with its GER, the procedure LOCAL FRONTIER is called to process the portion of the limits of the LSR S(qact), leading to areas that are unexplored according to the information available. To this end, the robot uses its own tree T as well as any other tree stored in its memory and received by present or past communications. To ¯nd promising directions in S(qact), its boundary is divided into arcs with obstacles, free arcs and frontier arcs (see Figure 4). Planner. The planner determines the new target con¯guration on the basis of the local an open frontiers associated to the current node. The open frontier of a tree (subtree) is the sum of the lengths of the local frontiers associated to its nodes. If the local frontier F (qact) of the current LSR is not empty, the planner generates a random con¯guration in the direction of F (qact). Thanks to synchronization done by the function BUILD AND WAIT GPR, all the robots in a GER plan at the same time, and therefore the cooperation mechanism intrinsic to the de¯nition of the local frontier is strengthened throughout the GER. This agreement attempt is performed without any centralized decision module.
The possibility that the robot is subject to non-holonomic constraints is considered by the function MOVE TO, which is responsible for generating feasible paths. The controllability of the robot ensures that any goal con¯guration in the LSR can be reached by paths that are feasible in the LSR. GER path feasibility check. Although the robot's local frontier can not belong to the LSR of another robot of the GER, the two prospective paths can still intersect. The function CHECK FEASIBILITY veri¯es whether the prospective paths of the robots in the GER G are all simultaneously feasible or not. To this end, all pairs of paths that intersect with others are identi¯ed, and the corresponding robots stored in the unfeasible subset Gu of the GER.
The remaining robots constitute the feasible subset Gf of the GER. Coordination. If the subset Gu of robots with unfeasible paths is not vacuum, the coordination function is invoked. The ¯rst step is to choose a master robot within G. This can be complemented in many ways through a deterministic procedure known by all the robots, for example, the robot with the highest ID number can be elected. Two cases are possible then: 1) If the robot is the master, it invokes an ORGANIZE function, whose task is to rearrange the vector Qg that contains the targets of the robots in the GER and obtain a feasible collective motion. Here, the change may mean whatever, simply accepting or readjusting the target of a robot to the current con¯guration (i.e., authorizing/prohibiting the motion) or adding a third option, for example, changing to a new target. 2) If the robot is not the master, it enters in a waiting phase, which ends with the receipt of a speci¯ed signal from the master.
The ¯nal operation is to retrieve and return the robot's (possibly modi¯ed) own target from Qg.
The procedure SUPPORT OTHERS (see Figure 5) can be divided into two major phases, which are repeated over and over again. In the ¯rst phase, the robot picks another robot to support it in his exploration, or, more precisely, another tree that helps it to expand (there may be more than one robot acting on a single tree). In the second phase, the selected tree is reached and the robot tries to expand it, tying subtrees constructed by the procedure BUILD SRT. The main cycle is repeated until the robot has received con¯rmation that all the other robots have completed their exploration.
The loop is repeated until the robot has received con¯rmation that all the other robots have ¯nished their exploration. At the beginning, the robot collects in a set I the trees belonging to S Ii that may require support for expansion. In particular, de¯ning the open frontier of a tree (subtree) as the sum of the lengths of local frontiers associated with its nodes, a tree Ti is put in I, if its open frontier is at least equal to a constant F¹ multiplied by the number of robots that are active in Ti, according to the most recent information available (ACTIVE ROBOTS). If I is not empty, the robot selects a particular tree Ts of I, according to some criterion (for example, the tree with the closest root, or the most recent update), and move to its root. Once there, the robot begins a subtree expansion using the BUILD SRT procedure. During this process, the robot keeps on trying to add subtrees to Ts until it has returned to the root of Ts and its open frontier is zero. At this point, the robot returns to the root of its own tree (i.e. its start con¯guration) and becomes available to support the expansion of other trees. This phase is only used when an unlimited communication range is handled, because the robot who is providing assistance can count with updated information of the other robots and its last states at any time, in contrast with a limited communication range with probably partial and not updated information.
SUPPORT OTHERS(qact) 1 do 2 for i = 1 to n 3 if OPEN FRONTIER(Ti) ¸ F¹¢ ACTIVE ROBOTS(Ti) 4 ADD(T ; Ti); 5 Ts à SELECT(T ); 6 if Ts 6= NULL 7 qact à TRANSFER TO(Ts:root); 8 BUILD SRT(qact; Ts); 9 qact à TRANSFER TO(T :root); 10 while EXPLORATION RUNNING()
Fig. 5. The SUPPORT OTHERS procedure. 3
In order to illustrate the behavior of the Multi-SRT exploration approach, we present two strategies, the Multi-SRT Radial and the Multi-SRT Star. The strategies were implemented in Visual C++ V. 6.0, taking advantage of the MSL library's1 structure and its graphical interface that facilitates to select the algorithms, to visualize the working environment and to animate the obtained path. The library GPC developed by Alan Murta was used to simulate the sensors perception systems2.
The tests were performed on an Intel °c Pentium D processor-based PC running at 2.80 GHz with 1 GB RAM. One can consider two possible initial deployments of the robots. In the ¯rst, the robots are initially scattered in the environment; and in the second, the exploration is started with the robots grouped in a cluster. Since the Multi-SRT approach is randomized, the results were averaged over 20 simulation runs. Figure 6 illustrates the environments used for the simulation part. The ¯rst is a square region with a garden-like layout, where each area can be reached from di®erent access points. The second is also a square, it contains many obstacles of di®erent shapes.
Exploration time for teams of di®erent cardinality are shown in Figure 7, both in the case of limited and unlimited communication range. In theory, when the number of robots increases, the exploration time would quickly have to decrease. This a±rmation is ful¯lled in the case of the scattered start; note however that, in the case of the clustered start, there are examples where this a±rmation is not veri¯ed. We consider that an increment of the number of evenly deployed robots corresponds to a decrement of the individual areas they must cover. In the case of a limited communication range, when the robots are far apart at the start, they can exchange very little information during the exploration process. 1 http://msl.cs.uiuc.edu/msl/ 2 http://www.cs.man.ac.uk/»toby/alan/software/
The total travelled distance increases with the number of robots because more robots try to support the others in their expansion.
However, even though repeated coverage among the robots decreases the mission's e±ciency, some amount of repeated coverage is a desirable situation for better e±ciency. Additionally, this better e±ciency can be achieved by coordination among robots.
The two strategies (Multi-SRT Star and Multi-SRT Radial) were compared through simulations. We used the same environment to prove the e±ciency of Multi-SRT Radial over Multi-SRT Star and the same free parameters.
The authors in [
Architectures for multi-robot exploration are usually classi¯ed as centralized and decentralized or distributed. In centralized architectures a central entity plans the actions of all the robot team, while in the decentralized approaches each robot makes use of local information to plan its exploration. Our approach is a decentralized cooperative exploration strategy for mobile robots, its coordination mechanisms are used to guarantee exploration e±ciency and avoid con°icts.
Decentralization causes serious problems, such as con°icts among the agents (robots) and their respective goals. This is because the knowledge contained in each agent might be incomplete, and goals of agents might be in con°ict. Therefore, con°ict resolution is a critical and implicit problem in MAS.
The local coordination procedure implemented in our work guarantees that the collective motion of the robots is feasible from the collision viewpoint. The approach does not need a central supervision. The selection of exploration actions by each robot is spontaneous and it is possible on the basis of the available information. 4
Multi-robot systems are emerging as a the new frontier in Robotics research, posing new challenges and o®ering new solutions to old problems. Multi-robot systems are not a collection of robots performing a once-for-ever ¯xed task in a settled and static environment. They are collections of interacting, cooperating autonomous agents with physical embodiment that impose restrictions on what they can do, but also give them power to do some speci¯c things. Thus the paradigms of Multi-Agent and Multi-robot systems are somehow related and the recognition of this parallelism may foster new avenues for research and solutions.
We have presented an interesting approach for cooperative exploration based on the SRT-Radial. The Multi-SRT considers two decentralized mechanisms of cooperation at di®erent levels. The ¯rst simply consists in making an appropriate de¯nition of the local frontier that allows each robot to plan its motion towards the areas apparently unexplored for the rest of the team. The second allows a robot that has ¯nished with its individual exploration phase, to support others robots in their exploration task. Additionally, we compared Multi-SRT Radial strategy with Multi-SRT Star strategy, the results obtained with our proposal are more interesting.
Exploration and localization are two of the capabilities necessary for mobile robots to navigate robustly in unknown environments. A robot needs to explore in order to learn the structure of the world, and a robot needs to know its own location in order to make use of its acquired spatial information. However, a problem arises with the integration of exploration and localization. A robot needs to know its own location in order to add new information to its map, but a robot may also need a map to determine its own location. Most exiting localization approaches refer to the single robot case. This means a posture of one robot is decided by its own sensor data, the robot should have an expensive sensor that can measure the robot pose in the global frame. If a robot can use the sensor data of other robots, a cheap sensor system can be used. This reveals the importance of cooperative localization which estimates the pose of each robot by fusing information obtained from the other robots.
The integration of a localization module into the exploration process based on SLAM techniques will be an interesting topic for a future research. We can also consider an extension of the Multi-SRT exploration method, where the robots constantly maintain a distributed network structure.