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. This paper presents a method to explore an unknown environment by multiagent robots, which is a parallelization of the SRT (Sensor-based Random Tree method). Several coordination strategies to solve the cooperative exploration problem were proposed, in particular we focused our attention in the cooperative policy strategy. This policy is completely decentralized, as each robot decides its own motion by applying some rules only on the locally available information. Simulation results show the practicality of the approach.
The advantages of collaborative behavior have been examined extensively in the context of biological systems. In the ¯eld of robotics, research on multi-robot systems is gaining popularity because the multi-robot approach provides distinct advantages over a single robots such as scalability, robustness and speed. On the other hand it increases the complexity of the system by adding more parameters into the problem space. Exploration using multiple robots is characterized by techniques that avoid tightly coordinated behavior.
Many studies have examined the utility of communication for the purpose
of behavior coordination. Some ¯nd that communication is bene¯cial [
Agent coordination and communication are important issues in designing decentralized agent systems. Since exploration task requires cooperation and coordination among robots, the achievement of the task will be accidental if robots work independently. This task can not be done unless robots cooperate and coordinate their behaviors. Therefore, it is necessary to have cooperation strategies that allow multiple robots to help each other in the problem solving process. The proposed cooperative policy is detailed in Section II. Simulation results in di®erent environments are discussed in Section III. Finally, conclusion and future work are detailed in Section IV. 2
Frazzoli et al., proposed a novel policy for steering multiple vehicles [
The proposed spatially decentralized control policy is based on a number of discrete modes of operation. Next the operation modes of the policy are described and later the properties.
{ Reserved region: This policy is based on a concept of reserved region, over
which active robot claims exclusive ownership.
{ Constraints: A su±cient condition to ensure safety is that the interiors of the
reserved regions are disjoint at all times; if such a condition is met, con°icts
can be avoided if robots hold their reserved ¯xed regions, and move within
them.
{ Holding: The robot can be stopped at any time, by setting the bounded
signed curvature. One can say that the robot is in the hold state.
{ Right-turn-only steering policy: The concept for decentralized con°ict-free
coordination is based on maintaining the interiors of reserved regions disjoint.
{ Rolling on a stationary neighboring reserved region: If the path of the
reserved region to its position at the target is blocked by another reserved
region, a possible course of action is represented by rolling in a pre-speci¯ed
direction.
{ Nonstationary neighbors: The reserved regions of a robot will not necessarily
remain stationary while a robot is rolling on it.
{ Generalized roundabout policy: The policy followed by each mobile robot is
based on four distinct modes of operation, each assigning a constant value
to the control input. The behavior of an individual robot can be modeled as
a hybrid system (see [
The problem of certifying the admissibility of a requested plan can de dealt with most e®ectively by decoupling the safety and liveness aspects of current and ¯nal con¯gurations. Indeed, for a given policy », one can consider the following two properties.
P1: A con¯guration set G = fgi; i = 1; :::; ng is unsafe for the policy » if there exist a set of target con¯gurations Gf = fgf ; i = 1; :::; ng such that application » leads to a collision.
P2: A target con¯guration set fgf ; i = 1; :::; ngis blocking for the policy » if there exist a set of con¯gurations G = fgi; i = 1; :::; ng from which the application of » leads to a dead-lock or live-lock.
A plan (G(t); Gf ) is admissible if it veri¯es the predicate :P1(G(t))^:P2(Gf ). Simple tests to check both properties are needed for the generalized roundabout policy.
We can mention the following properties of the proposed policy, which can guarantee to the system to be collision-free.
{ Admissibility. One can consider a framework in which new robots may issue a request to enter the scenario at an arbitrary time and with an arbitrary `plan', consisting of an start and goal con¯guration. It is important to have conditions to e±ciently decide on the acceptability of a new request, in other words, whether the new proposed plan is compatible with safety and liveness of the overall system. { Well-posedness. One can verify that the generalized roundabout policy leads to a well-posed dynamical system, i.e., a solution exists and is unique, for all initial conditions within a given set. { Safety. Within each state, the feedback control policy has been chosen so that reserved discs (a geometrical form created from its sensors) never overlap: a transition is always enabled to the hold state, which stops the reserved disk instantaneously. Since the robots are always contained within their reserved disk, at a certain distance from its boundary, safety is ensured. { Liveness. It is necessary the de¯nition of a condition concerning the separation of reserved discs associated with target con¯gurations. In other words, any circle of radius ½(m), with 1 < m · n, can contains at most m ¡ 1 reserved disk centers of targets. 3
The SRT method, is an exploration method based on the random generation of
robot con¯gurations within the local safe area detected by the sensors [
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 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 polygon1 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 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. For more details of the approach, one
can consult the work [
BUILD Multi-SRT(qinit) 1 T :init(qinit) 2 BUILD SRT(qinit:T ); 3 SUPPORT OTHERS(qinit);
Fig. 1. The Multi-SRT algorithm. 1 Polygonal models make it possible to e±ciently compute geometric properties, such as areas and visibility regions.
In this work, several strategies were utilized to solve multi-robot exploration
tasks. The two originally proposed strategies in the work presented in [
The tests were performed on a Celeron °c 430 processor-based PC running at 1.80 Ghz with 2 GB RAM. The strategies were implemented in Visual C++, taking advantage of the MSL library's structure and its graphical interface2. The GPC library developed by Alan Murta was used to simulate the sensors perception systems3. The polygonal representation facilitates the use of the GPC library for the perception algorithm's simulation. Figures 3 and 4 illustrate the Multi-SRT and explored regions with clustered and scattered starts respectively. We can see the di®erence when the robots are evenly distributed at the start of are clustered. At the end of the exploration process, the environment has been completely explored and the SRTs have been built. In these ¯gures, one can observe that each robot built its own SRT and when one of them ¯nished, this entered the support others phase. 2 http://msl.cs.uiuc.edu/msl/ 3 http://www.cs.man.ac.uk/»toby/alan/software/
Exploration time for teams of di®erent cardinality are shown in Figures 5 and 6, both in the clustered and scattered starts. The graphics generated with the exploration times, show that for those environments with a scatter initial con¯guration, the communication strategies more e±cient are the limited communication with messages and the limited communication with no messages. The disadvantage of the limited communication without messages strategy, is that it will require more re-exploration in the presence of more robots in the environment, increasing the exploration time, unlike the limited communication with messages that prevents re-exploration. In the case of the initial cluster con¯guration, it can be seen that, as more sophisticated and less centralized is the communication between the robots, as more optimal are the results corresponding to the exploration and the con°icts resolution.
The analysis of the results obtained for the case of the initial con¯guration in cluster shows that any communication strategy either limited or unlimited is useful for resolving disputes related to collisions and to carry out the exploration e±ciently. The communication strategy with blackboard tends to be sluggish when the number of robots in the environment is increased, because the structure used as a board is shared and only one robot at a time can access it; if more than a robot wants to access the board at the same time, it must wait in line for a turn.
The cooperative policy shows the best results, even in those environments considered di±cult to explore. From a particular point of view the good performance of this policy is because, it initially performs a quick exploration of the environment. This can be veri¯ed after analyzing the implementation of our approach with all the coordination strategies, and compare their performance in the graphics obtained with the cooperative policy strategy, in the relief phase that the robots use to complement the exploration.
Single robots can not produce accurate maps like multi-robots. The only advantage of using a single robot is the minimization of the repeated coverage. 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 coordination strategies (the cooperative policy and the coordination through replanning) were compared through simulations. We used the same environment to prove the e±ciency of the cooperative policy over the replanning strategy and the same free parameters, see Figure 7. 3.1
Discussion An appropriate task for the study of communication's utility will require agents to work directly together; if agents can complete the task individually without ever interacting with others, it will be unsurprising to ¯nd that communication is not useful, whereas if they require the aid of others (even if it is only to improve performance), communication may be adaptive. Ideally, the task should be parameterized to allow the degree of reliance on other agents (and hence the amount of coordination required) to be varied, making it possible to probe the limits of communications utility (e.g., what is the lowest coordination requirement at which communication proves bene¯cial?). However, care must be taken to ensure that the task is not tailored too speci¯cally to the search for communication.
The multi-agent and multi-robot research communities have each developed their own methods for perception, reasoning, and action in individual agents (or robots). Therefore, at the level of explicit coordination among multiple individuals, the di®erences between techniques used in multi-agent systems (MAS) and those used in multi-robot systems (MRS) are in fact very few. This is not to say that MAS and MRS are equivalent in any fundamental way, but rather that although robotics researchers employ sophisticated specialized techniques of various sorts (e.g., control theoretic, probabilistic among others) when designing single-robot control systems, they have so far tended to use techniques that are already well-known in the agent community when designing explicitly coordinated MRS.
It remains an open question as to how much bene¯t can be derived from using sophisticated coordination methods in MRS, because of an important underlying issue, which we suggest is one of the primary challenges facing MRS (and MAS): utility. In any case, since coordination is achieved by maximizing utility (or, equivalently, minimizing cost), the utility measure must account for all state information that is relevant to the task. All information that a®ects task performance but is not captured in the utility measure is captured in what economists refer to as externalities, the e®ects of which can be disastrous.
One of the fundamental challenges in mobile robotics is to explore the unknown environment e±ciently and e®ectively. The e±ciency and e®ectiveness of the exploration are typically measured by the map coverage, map accuracy and exploration time. To e±ciently explore an unknown environment with a team of robots, a coordinated strategy that maximizes the exploration area is required. Exploration of an unknown environment is one of the major applications of Multi-Robot Systems. Many works have proposed multi-robot coordination algorithms to accomplish exploration missions based on multi-agent systems techniques.
The implemented policy gives rise to a hybrid system, which can be shown to be well posed and safe, if the initial con¯gurations satisfy a rather nonrestrictive condition. Through the examples, we can a±rm that the policy is spatially decentralized and its complexity is bounded regardless of the number of agents. It can be concluded that the integration of a communication strategy in the robots, as a way of coordination to avoid con°icts, is very useful in the task of environment exploration, because it can help them to share information in order to avoid con°icts related to collisions and, in some cases, to prevent re-exploration areas in the most important phase, when a good communication strategy can contribute in reducing the exploration time.
Exploration and localization are two of 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 simultaneously. 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.