First and foremost I offer my sincerest gratitude to my PhD supervisor, Prof. Abdelkader EL KAMEL, for his continuous support of my PhD study and research, for his patience, motivation, enthusiasm, and immense knowledge. His guidance helped me in all the time of research and writing of this thesis. I could not have imagined having a better tutor and mentor for my PhD study. He has provided his supervision, valuable guidance, continuous encouragement as well as given me extraordinary experiences through out the work. A special acknowledgement should be shown to Prof. Shaoping WANG, who always supported my thesis work during these three yeas with her helpful suggestions and discussions. My thanks to both Prof. EL KAMEL and Prof. WANG for having involved me in their research cooperation project and giving me this opportunity to study in France.

Besides my supervisor, I would like to thank Prof. Pierre BORNE for his kind acceptance to be the president of my PhD Committee, as well as Prof. Noureddine ELLOUZE and Prof. Dumitru POPESCU, who have kindly accepted the invitation to be reviewers of my PhD thesis, for their encouragement, insightful comments and hard questions. My gratitude to Prof. Olivier COLOT, for being the examiner of my thesis and for their kind acceptance to take part in the jury of the PhD defense.

I am also very grateful to the staff in Ecole Centrale de Lille. Vanessa FLEURY, Christine YVOZ, and Brigitte FONCEZ have helped me in the administrative work. Many thanks go also to Patrick GALLAIS, Gilles MARGUERITE, Jacques LASUE, for their kind help and hospitality. Special thanks go to Christine VION, Martine MOUVAUX for their support in my lodgement life at the dormitory "De Vinci".

My sincere thanks also goes to Dr. ZHENG Tian and Dr. YU Yue, for offering me the useful advices during my study in the laboratory as well as after their return to China. I would like to take the opportunity to express my gratitude and to thank my fellow workmates in LAGIS: XIA Chen, LIU Bing, SUN Qi and LIU Yihan for the stimulating discussions, for the hard teamwork, and for all the fun we have had in the last three years. Also I thank my friends in Beihang University: ZHANG Hongchang, DU Yu, ZHANG Wan. In particular, I am grateful to Prof. WANG Shaoping for enlightening me the first glance of research. They have given me support and encouragement in my thesis work.

Last but not least, I convey special acknowledgement to my family for supporting me to pursue this degree and to accept my absence for three years of living abroad: my parents TIAN Jinshun and ZHANG Yingchao, for giving birth to me at the first place and supporting me spiritually throughout my life. So as to my girlfriend LIU Lingshan, without whom I cannot finish my work in time. It is her who has always been supporting me by my side for the last two years. Thanks for everybody!

Abstract

In this Ph.D., we will present firstly an efficient single robot exploration method, then a decentralized cooperative exploration strategy for a team of mobile robots equipped with range finders. A two dimensional map of the explored area is built in the form of a pixel figure. This is expanded by the robots by using a randomized local planner that automatically realizes a decision between information gain and navigation cost. The coverage of the exploration has been defined as the visited area by at least one robot.

In our work, the map is reconstructed using a least-mean square method to reduce the errors of the sensor data.

Intelligent control is playing a more and more important role when dealing with Autonomous Mobile Robots in unstructured, unknown or partly unknown environments. In dividing the overall task into subtasks, the intelligent controller allows reducing the robots task complexity. But the fusion of different behaviors with different objectives may cause contradiction in the procedure and alter the stability of the system. Therefore, the issue of behavior coordination mechanisms is crucial in order to realize the non-collision safety-ensured movements. A method integrated by behavior coordination and command fusion is proposed. A new approach with five basic behaviors, which are respectively Route Following, Target Going, Wall Following, Obstacle Avoiding and Deadlock Disarming,for mobile robot navigation are discussed. show that the proposed approaches are effective and can be applied in real robots.

Declaration

I herewith declare that I have produced this paper without the prohibited assistance of third parties and without making use of aids other than those specified; notions taken over directly or indirectly from other sources have been identified as such. This paper has not previously been presented in identical or similar form to any other English or foreign examination board. Exploring an environment has always been a fundamental problem in mobile robotics.

It consists, in the most difficult cases, to discover an unknown environment or having been modified during the exploration and build a representation for the area. The resulting map is generally necessary for the robots to perform some more complex task autonomously, as exploration is how robots map new territory to discover characteristics. While exploring, the problem of coverage arises, which is how the robots move in the environment to observe exhaustively the whole area of the environment. Therefore this is a sub-problem of exploration. Coverage is complete when the entire environment is observed.

Exploring unknown environments requires the resolution of three sub-problems: the localisation of one or more robots, the map reconstruction of the observed area and the coverage in the discovery of an unknown space. In this thesis, we are interested

INTRODUCTION

in resolving all the three sub-problems. More precisely, we seek a strategy to allow multiple robots to map all visible parts of the environment as quickly as possible, then we need to get a map for the targeted navigation. In this context, the use of several robots has many advantages because it allows to increase the efficiency of time and accuracy of the coverage. However, as we will show below, the gain is determined by the level of cooperation between robots, which means the multi-agent performance is not always better, and we need to set a strategy for robotic teamwork. Therefore, implementation of a strategy of cooperation is essential for an efficient multi-robot mapping.

Issues of robotic exploration

With the development of the recent robotic technology, the robots in the controlled environment from the industrial domain come into being: they can perform more complicated tasks as long as we put more powerful motor, more precise sensors, more skillful mechanical arms, more durable battery etc. on them. Among these tasks, exploring environments may lead to the map building, the localisation problem and the identification of objects. After exploration, these maps can then be used by other robots in order to perform other tasks or serve human for the inaccessible, dangerous or hostile area. Many examples of applications exist, some of which are shown as following (in Figure 1.1).

Exploring unknown environment is very useful for remote environments such as Mars (Figure 1.1(a)), for search and rescue after some disasters for inspection of hazardous areas as radioactive zones (Figure 1.1(c)) and more generally for hostile environments such as underground mines (Figure 1.1(b)) and underwater environments (Figure 1.1(d)). Many applications of robotic exploration are also found in city, industrial buildings or house surveillance. There is also internet applications such as Google Maps, which started offering virtual tours of buildings such as historical monuments or shopping centers.

Motivation

The robotic exploration is a widely studied topic since the early days of mobile robotics, because it is considered one of the emblematic problems of mobile robotics. Research has focused primarily on exploration for one single robot (see section 2.1). The miniaturization of robotic components and their reduced costs nowadays allow the effective deployment of fleets of robots, to perform all the tasks by multi-agent robot activity as a real advantage. Thus, multi-agent robotic exploration has been the objective for much work due to its numerous advantages compared to one single robot: mainly in terms of efficiency and robustness (see section 1.4). However, the existing approaches

INTRODUCTION

are centralised and they rely a lot on communication between robots. The bandwidth of wireless communication devices is limited, which is the reason why these approaches do not pass to a large number of robots yet.

Therefore, the main motivation of this work is to propose a decentralised and distributed approach which naturally limits communications to enlarge the robot number.

The objective is to improve the performance time in current multi-agent exploration approaches by limiting their computational costs. Indeed, multi-agent systems are generally composed of simple robots, inexpensive and usually with a low computing capacity on board.

The experimentation and validation of the proposed approach are performed both in simulation and in actual robot. The context of this thesis is to map a structured environment and locate objects completely autonomously (without human intervention) and in a constrained time.

Robot exploration in an unknown environment

In this context, we are interested in exploring finite space by deploying a set of autonomous mobile robots with observation capabilities allowing them to establish a local map of the environment and to be located in the mentioned area. In practice, this is possible by equipping robots with a distance sensor (rangefinder for example) and using an external localisation system (ex. GPS for outdoor terrestrial environments)

or SLAM algorithm. To enable cooperation between robots, it is essential to provide them with means of communication. We will see later that this communication can not be perfect in practice (inherent losses in wireless communications).

The problem we are dealing with can be formulated as assigning each robot an area to explore in order to expand the knowledge possessed by the robot fleet in the unknown environment. The evolution of the map implies continuous reallocation of robots to explore newly identified area, so this is a dynamic problem.

Multi-robot approach

We present here the advantages and disadvantages of a multi-robot approach.

1.4 Multi-robot approach

Advantages

Our choice to study a multi-robot approach is based on the many advantages for exploration, among which are mainly the robustness of the algorithm, the decentralised and distributed approach, the fast exploration speed and the accuracy of the map.

robustness A robot may be subject to failures due to a malfunction of the batteries, motors, electronic cards or other components. It can also be blocked against an obstacle, or simply be lost. Their effects are the stoppage of a robot, the permanent loss of communication or total shutdown. In one single robot case, this usually means the failure of the mission and the need to repair the robot in order to continue the task. However, in multi-robot situation, loss of one or more robots does not cause the failure of the current mission, the remaining operating robots can still continue to work. Moreover, if a robot is blocked in a danger zone but continues to operate, it may prevent other robots from that kind of danger.

Decentralised and distributed approach From the point of view of robustness, a centralized approach of coordination and/or of collection/viewing of data puts the success of the mission on a single component. In comparison, a decentralized system has no node more important than others and the loss of one node does not affect the success of the mission. From the perspective of the calculation, distribution of problem to multiple nodes is more efficient and provides better scalability. The use of a distributed method of computing maps leads to greater computational efficiency and less memory usage. Indeed, all the robots does not need to visit and build an accurate map of the entire environment. However, the problem is global, it must have information to know which areas are being explored and which directions remain to be explored.

Fast exploration speed Using multiple robot can divide the exploration problem into several regions assigned to different robots. This simultaneous exploration of different areas allows multiple robots to explore each zone sequentially and to discover the environment faster than a single robot. We will see that the number of robots to be implemented depends on the kind of environment explored. For example, exploring a single long corridor from one end to the other does not require more than one robot, because additional robots cannot do more work

INTRODUCTION

than following the first robot. The benefit of adding robots is not systematic, on the contrary, potential interference and collision between robots may increase the exploration time.

The theoretical maximum gain of the exploration time using n robots, rather than one, is n. The theoretical exploration time with n robots is equal to the best exploration time with one single robot divided by n. However, the maximum gain will be achieved if and only if when all the n robots always observe different parts of the environment during the entire process. In reality, it is highly possible that they sometimes observe the same areas, then there will be some overlapped information. Although at this moment, multiple robots do not provide more information at the exploration, their contributions of information can improve the accuracy of the map of these already explored areas. In practice, the gain depends on the topology of the environment and the initial position of the robots.

Accuracy of the map As indicated above, the greater the amount of information gathered on the map is, the better accuracy of the reconstructed map we will get. Also, if the robots cooperate to localise themselves, this accuracy will be greater. For example, the robots may mutually observe and locate each other more precisely by triangulation or trilateration. The need to use these techniques depends on the precision of the multi-agent localisation information and the desired accuracy of the reconstructed map.

Disadvantages

The use of a multi-robot method also has a limited number of drawbacks described below.

More coordination work

The navigation of multiple robots in an environment requires a lot more of coordination because robots may visit the same areas and interfere each other, or even collide between themselves. The collision avoidance or resolution of interlock between the robots can cause detours during exploration.

Complication of the system

Mapping with multiple robots is more complex. Using the same type of sensor can cause interference distorting the observations. Furthermore, one robot observing another working robot can map it as an obstacle 1.5 Navigation while new obstacles presented as part of the environment. If the mapping is distributed, the loss of a robot may lead to the loss of information collected by this robot. The loss of communication with a robot may result in the need for other robots to re-explore the area discovered by the failed robot.

Global mapping problem A multi-robot system requires the construction of a global map of each robot to identify the remaining areas to explore, which requires matching the local map of each robot, and combining the global one. If robots start from the same area, the identification of a common reference and maps matching process are quite simple. In the absence of a common reference, we need to identify the transformations between the local map reference of each robot. There are some existing techniques for matching maps [START_REF] Birk | Merging occupancy grid maps from multiple robots[END_REF]. The result of an erroneous combination due to poor matching, can severely distort the resulting maps and block robots which may be either lost (not knowing their position) or blocked (all paths are virtually blocked).

From the above discussion, we can clearly see that it is reasonable to use the multiagent approach to solve the problem, because important advantages of multi-robot approach justify its choice for exploration, while disadvantages can be reduced to minimum by using a good exploration strategy.

Navigation while new obstacles presented

The exploration is to discover the environment with one or more sensors mounted on robots. Robots may not physically cover the whole environment, but must move in order to observe the entire environment and thus construct a complete map.

The environment and the robots are not modifiable parameters, they are supposed mostly fixed in the conjecture. Given the problem, we seek the best exploration strategy.

However, the environment is unknown, so the strategy must be generic enough to be applied to all types of environments. The environment is static, which means that it does not change over time. For one robot, only the other robots are the moving obstacles. There is an optimal number of robots to an environment for rapid exploration while avoiding conflicts between robots. If the environment is unknown, the number

INTRODUCTION

of robots should be maximum or selected based on an estimation of the area of the environment.

Contribution

The multi-robot exploration requires a strategy of good cooperation between robots.

The main contribution of this thesis is a strategy with good performances in total exploration time compared to the existing strategies. It is based on the relative position of a robot to a boundary compared to other robots. Thus, each robot moves towards the boundary which is in better position for itself. A variant of this strategy is also proposed. It is to assign borders to different robots using greedy algorithm, taking into account the position criterion to determine which part of boundary will be affected to which robot.

Implementations of these proposed strategies are very efficient. They are based on synchronized propagation of the wave front from the boundaries. These synchronized propagation significantly reduce the cost of computing distances between robots and the boundaries for task assignment.

We also propose a framework for implementation of these strategies on real robots.

Several contributions have been implemented within this framework:

-an frontier based exploration strategy using a group of robots, -an two dimensional map reconstruction method not depending on landmark, -a reactive navigation based on an A* algorithm path planning in two dimensions in a partially known environment using fuzzy control method, -a software architecture allowing each robot to operate independently during the exploration and simulating the process.

Plan of the thesis

This thesis consists of six chapters.

Chapter 1 has been introduced as a general presentation of the problem.

Chapter 2 presents the research context of the multi-robot exploration by describing the state of the art in this domain. In this chapter, the existing approaches are presented 1.7 Plan of the thesis in different aspects related to the objectives of exploration, to the working hypotheses and to the exploration methods.

In Chapter 3, we will firstly study the mono-robot activity in exploration, then carry out the algorithm from one single robot to multi-robot cooperation.

Chapter 4 presents the image processing class in c++, combining the local map of each robot to the global map using the triangulation to minimise the error, and augment the accuracy of the reconstructed map.

Chapter 5 describes the situation when the robot re-enters the explored area, even if there is new modifications (ex. new obstacles presented), it can still achieve its goal efficiently using the command fusion and fuzzy control method.

In the Chapter 6, we will show the experiment result, both in simulation and in real world, to present the advantages and disadvantages of our algorithm.

Finally, we will consists mainly the conclusion and the future work. The multi-robot exploration attracts a great deal of attention for the reasons cited in the introduction 1.2. In this chapter we will present the main existing approaches for the exploration in the unknown environment and we will classify them according to the objectives, assumptions and methods to use.

Heralds

The robotic exploration is an active domain of scientific research since the beginning of robotics in the middle of the 20th century. For example, Bristol Turtles, invented by W. G. Walter in 1949, behave like an animal able to explore its environment randomly in avoiding obstacles and to look for light sources. The history of robotic exploration of unknown environment is related to the problem of reconstructing maps in robotics.

Indeed, it is easier for a robot to explore an already visited environment with a map and vice versa it is difficult for a robot to imagine the map without exploring the environment. In the middle of 1980s, the development of robotic cartography (as grids [START_REF] Moravec | High resolution maps from wide angle sonar[END_REF], convex polygons [START_REF] Chatila | Position referencing and consistent world modeling for mobile robots[END_REF] or segments [START_REF] Crowley | Navigation for an intelligent mobile robot[END_REF]) helped to lead the exploration to unvisited area. Simultaneously, the development of behavior-based robotics [START_REF] Brooks | A robust layered control system for a mobile robot[END_REF] has achieved to fulfill a task too complex for computers of that time to calculate (exploration and mapping) by the interaction of several simple but intelligent behaviors.

Due to the inaccuracy of sensors and their inadequate acquisition speed, for a long time, there are many problems for localisation and mapping. Topological maps [START_REF] Kuipers | Modeling spatial knowledge[END_REF] help to solve this problem, which model the scene by the nodes of a graph and the paths between them by edges. The pioneering work [START_REF] Kuipers | A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations[END_REF] proposes to explore the hallway in combining reactive navigation behaviors on one hand, and on the other, identify and recognise the distinctive places (such as intersections). Their robot builds a topological map, in which the nodes are distinctive places. Each unvisited direction of the node is added to an agenda of exploration. The robot removes the direction of its agenda when it leaves the node in the corresponding direction or when it reaches the node from this direction. When his agenda is empty, the robot has finished exploring its environment.

In the early 1990s, the technological development of the hardware, communication and their increased availability stimulated an increasing interest in multi-robot approaches. Early researches using a multi-robot approach were purely reactive, because the map was constructed retrospectively from information collected by the robots. For example, the approach (López de Màntaras et al., 1997) uses small low-cost robots that explore the environment so randomly (turning ±45 • or ±90 • at random moments or when they detect an obstacle). Robots return to their starting points using the reverse path (with less loops) after some time of exploration. The map is constructed using sensory information of the robot back to the starting area. This may be noisy, so a filtered map is constructed by combining the near walls. Their map only includes the orthogonal walls. The work [START_REF] Duckett | Experiments in evidence-based localisation for a mobile robot[END_REF] shows that the robots using the wall-following technique explore faster than a random exploration. Their environment has unique unambiguous and recognisable landmarks by robots. The constructed map gives only the position of these landmarks. [START_REF] Yamauchi | A frontier-based approach for autonomous exploration[END_REF] offers one of the first approaches that directs the robots to the unexplored areas, introducing the concept of frontier. In this approach, robots build a common grid map, in which the cells are empty, occupied or unexplored. Robots are attracted to the frontier cells (empty cell adjacent to an unexplored cell) and update the global grid with the new information. The robots move towards the frontiers and thus collect new information on the unexplored zones of the environment. The successive and exhaustive exploration of frontiers lead to the full exploration of the environment

The multi-robot exploration has been discussed by the objectives, assumptions and different methods generating many models and architectures for very different systems.

These approaches can be classified into five types in the following sections.

Assortment by assumption

In this section, we will discuss the different assumptions on the environment and on the technical characteristics of robots (sensors and communications) for the multi-robot exploration.

Environment and initialisation

The environment influences the whole exploration strategy (objectives, coordination, communication and identification of targets). We have mainly two type of environment:

indoor and outdoor environments. Indoor environments are structured while outdoor environments have more empty spaces. The outdoors localisation is more difficult because there are fewer landmarks [START_REF] Panzieri | An outdoor navigation system using gps and inertial platform[END_REF]. To remedy this problem, outdoor robots are often equipped with a system of external localisation such as a Global Positioning System (GPS). With indoors and many other environments (for example, submarine, extraterrestrial, etc), the GPS is not available.

As we have seen in the introduction, in order to collaborate, robots have to identify the collected information. For this, the robots can use a common reference. When the robots start from a same area, it may have a common reference or define one. If they start from different areas without common reference, matching their respective local map can be done by finding the transformation between their local reference (for example, with the approach (Birk and Carpin, 2006) with occupancy grid), the use of common landmark, unique and unambiguous, or by observing the relative positions between the robots. The relative positions may be obtained by mutual observation with, e.g., color markers.

Characteristics of the robots

The computing power also influences the choice of the strategy [START_REF] Argyros | Semi-autonomous navigation of a robotic wheelchair[END_REF].

Strategy too expensive in calculation on a robot with respect to its capabilities requires pauses to calculate the next destination and the means to achieve it. The autonomy of the robot depends on the onboard energy and the consumption. On communication between the robots, several characteristics must be taken into account: the available bandwidth, range and reliability.

Sensors of the robot The nature of the sensors influences the cooperation strategy and the choice of targets to be assigned to robots [START_REF] Beom | A sensor-based navigation for a mobile robot using fuzzy logic and reinforcement learning[END_REF]. Precision and range can determine the objective, so if one single robot can map quite accurately with the desired resolution, then the approaches seeking to maximize accuracy will not be useful. The range of the sensors must be adapted to the extent of the free zones of the environment. When the environments are small enough to observe a position discriminating detail features of the environment, the localisation will be simpler. It is more difficult to obtain accurate metric information in large open environments without a wide-range sensor. Finally, the sensor noise also affects the mapping method. If it is desired to create a three-dimensional map, it is necessary to have the appropriate sensors to acquire 3D information. There are many characteristics for sensors: accuracy, resolution, acquisition rate, amount of data generated, etc. Each of these characteristics directly influence the methods of exploration, localisation and mapping.

Quantity of communicated information

The amount of communicable information between robots directly influences the choice of method of coordination [START_REF] Dudek | Experiments in sensing and communication for robot convoy navigation. In Intelligent Robots and Systems 95[END_REF]. Indeed, the bigger the number of robots is, the larger amount of exchanged information there will be, particularly if communications are based from robot to robot. In the entire networks, the bandwidth is limited, a strategy based on the communication of large amounts of information between robots will therefore not be applicable to a large number of robot. Thus, for scaling up of a large number of robots, it is necessary to use a strategy based on an exchange of restricted information. Reliability of the communication To account for the instability of wireless communications, the approaches based on the autonomous decision of the robot is preferable. In fact, if a robot is waiting for a communication to decide his next target or the next way point, but the information is lost, the robot will wait until the resumption of communications [START_REF] Dudek | Experiments in sensing and communication for robot convoy navigation. In Intelligent Robots and Systems 95[END_REF].

Range of the communication

Assortment by objectives

Exploration is defined as the discovery of an unknown environment, the objectives of the multi-robot exploration can be different depending on the applications. For example, to look for objects, persons in the fire accident, exploration will focus primarily on larger areas with better coverage to increase the probability of finding objects faster.

However, for surveillance, it will explore the entire environment several times [START_REF] Calisi | Multi-objective exploration and search for autonomous rescue robots[END_REF]. In other scenarios, the construction of an accurate map is desired without taking the exploration time into account, which is particularly true for robots using very noisy sensors.

Minimisation of the exploration time

Among the approaches that seek to minimize the exploration time, we can find two types of methods: those who try to cover the largest area in the unknown environment quickly and those who try to complete the exploration as soon as possible. The first insists on quick exploration of larger areas by priority; completeness intervening only at the end of the exploration as a secondary objective. The second method may, for example, try to explore the areas to avoid the return to the same region later. A problem similar to the complete coverage issue is the patrol of repeating the coverage in minimizing the time between visits to the same area [START_REF] Rekleitis | Multi-robot collaboration for robust exploration[END_REF]. It is a related problem which is usually addressed to the robots by providing them a map. If they do not know the map, the first time will be spent on its creation (of the map) and therefore the exploration. Coverage also means the static problem of the computation of the robots' configurations which allow the observation of the largest possible area (for example [START_REF] Renzaglia | Distributed coverage control for a multi-robot team in a non-convex environment[END_REF]). However, the latter problem is further away from the problem we address because it does not consider the total exploration of the environment.

Minimisation of the energy

Robots are equipped with a limited amount of energy. It is therefore important to limit the consumption for the exploration of large environments [START_REF] Mei | Energy-efficient mobile robot exploration[END_REF]. However, the use of the engines is generally the main source of energy consumption; in which case the energy consumed is proportional to the distance and also proportional to the exploration time.

Maximisation of the precision

The goal is to build the most accurate map using several robots. Two approaches are distinguished to achieve this goal.

The first is to improve the accuracy of the localisation and thus improve the precision of the map by localising the robots between each other. The approach [START_REF] Rekleitis | Multi-robot exploration of an unknown environment, efficiently reducing the odometry error[END_REF] covers the environment with a robot who stops and observes another moving one, the inside of the triangle formed between the point at which the first robot stopped, the departure point and the arrival point of the moving robot is marked as free. Exploration is performed locally by dividing the free space into stripes (see Figure 2.1(a)). Globally, these stripes are connected using a line of sight strategy between robots based on the corners in the form of acute angles (see Figure 2.1(b)). Thus the authors show that the exploration with multiple robots is faster and more accurate than the method with only one robot. This approach does not consider the limited communication distance between robots and a robot can only observe another moving robot. Rekleitis et al.

(2001) use the cooperation between robots capable of measuring their relative distances and angles: one or several robots stop and observe the movement of another robot. In this system, half of the robots in the fleet moves while the other half observes the position of the moving robots. Static robots are better localised and can transmit more precisely observed positions to the mobile robots. Robots alternate between these behaviors to advance in the environment. However, this approach has a big disadvantage because half of the fleet is always in the pause at any time, which greatly slows down the progression of exploration.

The second approach is to use the SLAM (Simultaneous Localization and Mapping) method with exploration. SLAM is a technique to construct a map of the environment while localising the robot in this map. This is done repetitively at every observation. These approaches are with one single robot but can be applied as multi-robot.

For example, [START_REF] Makarenko | An experiment in integrated exploration[END_REF] changes between exploration and return to the already-known areas in order to reduce uncertainty. [START_REF] Feder | Adaptive mobile robot navigation and mapping[END_REF] propose to guide the robot to the landmarks to reduce uncertainty. Finally, approaches such as Active SLAM force the robots to return to visited areas with a greater degree of certainty (2005), the closed loop (confirmation of the hypothesis that the robot has returned to an already-visited zone) continues while the uncertainty is higher than a certain threshold, before the exploration of new areas.

The approaches aiming to increase the accuracy of the map require abandoning the task of exploration in order to better localise the robots. Later, we will focus on the task of exploration. This requires the allocation of targets to robots so that they can discover the environment. The following section describes the different methods of identification of targets.

Assortment by identifying area to explore (target)

During exploration, identification of targets is strongly linked to the dimension of the representation of the environment (2D, 3D) and its type (topology map, occupancy grid, triangulation). Here we describe briefly the major target identification families.

We will see in more detail to identify them later.

Frontier approaches

The frontiers are areas of interest for exploration, which delimit the known and unknown areas. The assignment of robots to the frontiers requires that they coordinate so that the distribution of robots to the frontiers is the most appropriate (presented in Section The approach based on frontier is relatively easy to carry out efficiently.

Next Best View approaches

González-Banos and Latombe (2002) sample probabilistically the environment near the frontier to determine the Next Best Viewing position of the frontier.

Utility methods

The utility concept, originally proposed by [START_REF] Simmons | Coordination for multi-robot exploration and mapping[END_REF], is defined as the difference or ratio between the cost and the gain of information associated with an observation. It reduces for example the exploration of neighbor frontiers to those already assigned, as it only provides little information. Actually, a robot that observes a frontier also observe its neighborhood. Thus, the utility of a frontier exploration is inversely proportional to its distance from the assigned frontiers. The utility of the frontiers is reduced if they are visible (not separated by an obstacle and with a distance less than the perception radius) assigned from the border. If the frontiers are close enough, only one robot can explore them in one single observation. The utility method provides a better distribution of robots in the environment than the frontier-based approaches with no grouping neighbor frontier cells. The approach of Puig et al. (2011) performs a segmentation of the environment with the K-means algorithm as many zones as robots. Therefore, one zone will be explored by one robot. Figure 2.5 shows the segmentation. This method distributes the robots in the environment for faster exploration. Its disadvantage is that it needs to know the size of the environment before exploration. It does not take the topology of the environment into account, which will pose a lot of problems if the environment is structured as one robot will eventually visit the zone assigned to another robot before being able to access the zone that has been assigned to itself.

Other approaches

Assortment by assigning targets

The target can be assigned to the robots using different exploration methods, and we may summarise as below.

The nearest frontier

For one single robot, the method proposed by [START_REF] Yamauchi | A frontier-based approach for autonomous exploration[END_REF], assigning the nearest frontier to the robot, is the most efficient method among the frontier-based method (see [START_REF] Holz | Evaluating the efficiency of frontierbased exploration strategies[END_REF]).

Assortment by assigning targets

Yamauchi (1998) extends this method for the multi-robot case, and each robot goes to its nearest frontier. In the process, if the partially constructed map is shared, the implicit cooperation will be carried out (see the figure 2.6). However, it is limited, because the robots may choose the same frontiers, with no advantage by their number.

Greedy algorithm

The Greedy algorithm tries to optimize the total cost of exploration by setting the pair robot-frontier with the minimum cost at each iteration. As iteration is performed on the robot, the equilibrium distribution of the robots on the frontiers is ensured. This algorithm is usually applied in a centralised manner. However, each robot, if it has the travel costs of all robots to each frontier, can run the algorithm until we obtain the distribution of the exploration. at each frontier. Indeed, the algorithm is similar to greedy algorithm with updating the criterion after each assignment. The purpose of this approach is to minimize the exploration time by taking into account simultaneously the cost to reach the target and its ratio compared to the information gain [START_REF] Burgard | Collaborative exploration of unknown environments with teams of mobile robots[END_REF]. The general principle of the algorithm is as follows:

Greedy on the utility of frontiers

1. initialise the utility of each frontier to 1;

2. find the robot-frontier couple having the maximum utility-cost difference and assign the robot to the corresponding frontier;

3. reduce the utility of all the frontiers in function of their distance to the previously assigned frontier (the nearer the robot is to the frontier, the smaller the utility will be);

4. go back to the second step if there is the robot without frontier.

This method gives better distribution of the robots, but may be difficult to decentralise, because the assignment of a robot will affect that of another. Moreover, the assignment of all the robots must be done simultaneously, which will pose a problem of synchronisation.

Hungarian method

The Hungarian method [START_REF] Kuhn | The hungarian method for the assignment problem[END_REF]) is an optimal algorithm for task assignment. It

Optimal assignment

The minimisation of the sum of the cost by the greedy and Hungarian algorithm do not allow the optimal assignment of the robots on the frontiers (see Figure 2.8). To obtain better results, it is necessary to list the solutions because it is always a competitive problem.

When the number of robots is small (less than ten), it is capable to generate all the possible combinations robot/frontier and determine which is optimal. When the number is more and more important, the utilisation of the second algorithm in Burgard Evidently, the implementation of these methods of target assignment can be carried out without communication between the robots. So the following section will describe the communication methods.

Assortment by communication mode

The first robots incapable to communicate their coordination between robots are difficult to carry out a cooperative algorithm for exploration. The technological advance of the wireless communication allows developing better coordination strategies that we are going to study in this section.

Without communication

Communication is essential to ensure the completeness of coverage. Random exploration and wall following methods (see section 2.1) do not use communication but there is no cooperation between robots and they can not determine whether the exploration is completed. In practice, the method of López de Màntaras et al. (1997) uses a communication between robots which intersect to avoid losing data gathered by robots which do not return to the starting point. For the environment coverage, Howard et al.

(2002) use a technique based on potential fields [START_REF] Khatib | Real-time obstacle avoidance for manipulators and mobile robots[END_REF]. These fields push the robots between each other and the obstacles. A motor schema [START_REF] Arkin | Motor schemabased mobile robot navigation[END_REF]) is used

STATE OF ART

to generate an action in function of the potential fields in which the robot is placed.

The only assumption of the approach is that robots can perceive the distance and the angle of obstacles and robots around by their sensors. Starting from the same zone, the robots are dispersed into the environment to maximize the coverage (see Figure 2.9).

These methods do not build map simultaneously or construct map afterwards. They are not very effective for exploration, in fact, it is necessary to guide the robots to the unexplored zone. To do this in collaboration, the communication is essential. Robots that do not communicate have to explore the entire map respectively to determine if the exploration is completed.

Indirect communication

Approaches with no direct communication between robots are based on the markers of the environment, for example, with digital pheromone [START_REF] Glad | Self-organization of patrollingant algorithms[END_REF]) by using markers and tags. The environment which is often a graph in the form of a cell grid, robots leave marks containing a value in visited cells. The exploration is done with ant agents (very simple agents with very limited perception). For example, LRTA* methods (Learning Real-Time A*) [START_REF] Korf | Real-time heuristic search[END_REF]) and Node counting [START_REF] Wagner | Distributed covering by antrobots using evaporating traces[END_REF] use the same strategy: agents head to the neighbor cell with the lowest value.

These algorithms differ on how to update the values of the markers. LRTA* guide the robots to the nearest unexplored cells in a similar manner [START_REF] Yamauchi | Frontier-based exploration using multiple robots[END_REF]. With the Node counting algorithm, each cell of the environment maintains the number of times the cell has been visited by a robot, robots thus head to the nearest cell the most previously visited. [START_REF] Koenig | Efficient and inefficient ant coverage methods[END_REF] prove that LRTA* guarantees the exploration of the environment in polynomial time while Node counting method has a complexity in exponential time. These approaches are easy to simulate but difficult to implement in robots. Furthermore, the agents do not build maps but fill a grid; they can not check if exploration is completed (limited perception and no memory).

Explicit communication

The explicit communication of information and of data between the robots can use different forms. In fact, the robots can explicitly exchange information on the environment, which allows them to coordinate implicitly. And they can directly exchange the coordination information:

Share the map/Implicite cooperation In [START_REF] Yamauchi | Frontier-based exploration using multiple robots[END_REF], the coordination is implicit, because it does not use the exchange of the message for coordination between the robots, which leads to the construction of the global map. The robots share the collected local information in order that each of them produces a similar map, providing a list of similar frontiers. Each time one robot carries out an observation, it broadcasts the result to the entire fleet. There is no communication for the explicit coordination of the robots. It is a distributed system, where each robot decides its going direction autonomously.

STATE OF ART

Explicit communication for the coordination An explicit communication between several robot leads to the development of a number of methods, the principles of which are explained as below.

Auction system The auction systems operate in two stages: first an auction phase based on communication either between robots or with a central server will be carried out, followed by a phase of assignment. The robots autonomously choose their target but coordinate when targets or paths are in conflict. The coordination between robots is obliged when the inter-distance between their target is less than two times the radius of perception. Coordination is then made from the chain of robots satisfying the criterion of inter-distance as follows: during the coordination phase, the robots stop their movement, synchronise and decide in this subgroup of coordination strategy. If the paths to the target are in conflict, a group leader is elected and resolves the conflict by assigning targets or leaving some robots stopped. Figure 2.10 shows a group of robots coordinating.

Centralised approaches

Many approaches use a central unit to collect information from each robot, build the partial map, calculate the cost for each robot and finally distribute tasks to each robot [START_REF] Wurm | Coordinated multi-robot exploration using a segmentation of the environment[END_REF]. Thus, communication is centralised to the single and unique leader robot. During exploration, leadership can be attributed to different robots.

Other approaches distribute a part of the calculation. Thus, [START_REF] Simmons | Coordination for multi-robot exploration and mapping[END_REF] propose an approach based on frontier exploration and a simple auction system. Each robot evaluates the benefit of exploring each frontier by determining the travel cost and the estimation of the next ratio compared to the information gain. It sends then an auction on the frontiers, evaluated at a central agent who, once bids of all robots receive, assigns the frontiers to robots in a greedy manner, avoiding the overlapping of coverage of each robot. [START_REF] Stachniss | Efficient exploration of unknown indoor environments using a team of mobile robots[END_REF] use the same kind of approach but provide a priori information on the topology of the environment which allows to take the type of area to explore (corridor, room, etc) into account. Note that these approaches are partially centralized but they have the same fault with a centralized approach because they contain a centralisation point which can be a source of system failure.

Conclusion on the state of art

Conclusion on the state of art

The multi-robot exploration was discussed with different objectives: accuracy of the constructed map, maximum coverage and complete exploration in a minimum time.

STATE OF ART

Whatever the objective we are looking for, we have seen that to develop an effective exploration strategy, we have to consider the sensor range and communication range between robots. Centralized strategies enable efficient exploration through efficient co- The Exploration problem can be modeled as the travelling salesman problem (TSP)

or the shortest watchmen route problems. Since the original art gallery problem is non-deterministic polynomial complete [START_REF] Aggarwal | The art gallery theorem: its variations, applications and algorithmic aspects[END_REF] and always requires complete knowledge about the environment. As a matter of fact, mapping is an incremental process. Since the ranges of the sensors (ex. sonar or laser) are limited, measurements are inaccurate, and errors may occur along the process, that is why map building is usually performed by taking several measurements of environments at different positions and by integrating these measurements in a global map. Therefore to explore an unknown area is usually carried out in a reactive way. 3.1 Single robot method

Frontier-based exploration

The central idea behind frontier-based exploration is: to gain the most new information about the world, move to the boundary between open space and uncharted territory.

Frontiers are regions on the boundary between open space and unexplored space.

When a robot moves to a frontier, it can see into unexplored space and add the new information to its map. As a result, the mapped territory expands, pushing back the boundary between the known and the unknown. By moving to successive frontiers, the robot can constantly increase its knowledge of the world. We call this strategy frontier-based exploration.

If a robot with a perfect map could navigate to a particular point in space, that point is considered accessible. All accessible space is contiguous, since a path must exist from the robots initial position to every accessible point. Every such path will be at least partially in mapped territory, since the space around the robots initial location is mapped at the start. Every path that is partially in unknown territory will cross a frontier. When the robot navigates to that frontier, it will incorporate more of the space covered by the path into mapped territory. If the robot does not incorporate the entire path at one time, then a new frontier will always exist further along the path, separating the known and unknown segments and providing a new destination for exploration.

In this way, a robot using frontier-based exploration will eventually explore all of the accessible space in the worldassuming perfect sensors and perfect motor control.

The new information contributed by each new frontier decreases geometrically, which is theoretically possible (though highly unlikely), but even in such a case, the map will become arbitrary accurate in a finite amount of time [START_REF] Freda | Frontier-based probabilistic strategies for sensor-based exploration[END_REF].

The real question is how well frontier-based exploration will work using the noisy sensors and imperfect motor control of a real robot in the real world. This is the question that this research is intended to address.

Frontier detection

After a grid has been constructed, each cell in the grid is classified by comparing its occupancy probability to the initial (prior) probability assigned to all cells. This algorithm is not particularly sensitive to the specific value of this prior probability (A value of 0.5 was used in all of the experiments described in this paper.).

Each cell is placed into one of three classes:

• open: occupancy probability < prior probability

Navigation to frontiers

Once frontiers have been detected within a particular evidence grid, the robot attempts to navigate to the nearest accessible, unvisited frontier. The path planner uses a depthfirst search on the grid, starting at the robot's current cell and attempting to take the shortest obstacle-free path to the cell containing the goal location.

While the robot moves toward its destination, reactive obstacle avoidance behaviors prevent collisions with any obstacles not present while the evidence grid was constructed. In a dynamic environment, this is necessary to avoid collisions with, for example, people who are walking about. These behaviors allow the robot to steer around these obstacles and, as long as the world has not changed too drastically, return to follow its path to the destination.

When the robot reaches its destination, that location is added to the list of previously visited frontiers. The robot performs a 360 degree sensor sweep using laser-limited sonar and adds the new information to the evidence grid. Then the robot detects frontiers present in the updated grid and attempts to navigate to the nearest accessible, unvisited frontier.

If the robot is unable to make progress toward its destination, then after a certain amount of time, the robot will determine that the destination in inaccessible, and its location will be added to the list of inaccessible frontiers. The robot will then conduct a sensor sweep, update the evidence grid, and attempt to navigate to the closest remaining accessible, unvisited frontier.

Recording the explored area

We use the exploration matrix to remember the area explored by the robot, thus in visiting the environment, we can decide which zone to go and when to finish the exploration task.

Firstly, we will define the sensor number SN as the following equation 3.1 shown in the Figure 3.1:

SN = 90 + α -β (3.1)
Where α=getAngleDegree(co (x R ,y R ) , co (xsc,ysc) ) and β=getRobotAngle( ). Then we can use the following algorithm to record the visited area. In the Algorithm 1, we use M ,N to represent the total square number in column and row, and dm,dn the increment in number for M and N (here we suppose that dm and dn are equal to 1). SN is the sensor number as defined in the Equation 3.1.

We use a laser range finder with 0 to 180 degree wide range, so if the sensor number SN is in the interval [0, 180], then we can determine with its corresponding sensor value whether or not the grid can be considered as visited, which is

SN ∈ [0, 180] ⇒ 0 90 + α -β 180 ⇒ |α -β| 90 (3.2)
Where (p, q) is the integer coordinate in the matrix M pq , and (n sc , m sc ) is the integer coordinate of the square center in the (n sc , m sc ) reference, and (x sc , y sc ) is the real number coordinate of the square center in the robot reference.

Proposed exploration algorithm

We propose an efficient exploration algorithm. First we define an obstacle encountering region. In the Figure 3.3, the parabola is more suitable for the navigation reality, however, the rectangular area is a good approximate for the curve, and is easier to calculate with the respect to the laser rangefinders variant angle θ. And if we define θ 0 = arctan d 2 d 1 , then we can obtain the obstacle region function f (θ) in Equation 3.3

Algorithm 1 Recording the explored area.

1: for each p ∈ [0, N ); do 2:

for each q ∈ [0, M ); do 3:

n sc = N 2 -p; 4:
m sc = -M 2 + q;

5:

x sc = m sc -1 2 dm;

6:

y sc = n sc + 1 2 dn; 7:
Calculate dist = ---→

P sc P R = d((x R , y R ) → (x sc , y sc )) 8: if M p,q = 0 ∧ |α -β| 90 ∧ dist laserP roxy[SN ] then 9:
M p,q = 1 10:

end if 11:
end for 12: end for as shown in following figure:

f (θ) = d 1 , θ ≤ θ 0 d 2 tanθ , θ > θ 0 (3.3)
We also define the wall following behavior for the exploration algorithm. We will update the minimum distance between the obstacle and the robot in the FOV (Field Of Vision) detection zone, which is a 45 degree-wide sector of a circle in the Figure 3.4.

Thus the algorithm goes as shown in the Figure 3.5: if the robot does not meet any obstacle, which means that no obstacle enters in the rectangular region, the robot continues its way. However when there is some obstacle, it will firstly following the obstacle, then search in the cloister region as explained in the literature and choose a direction that is never visited before. Until the robot found no unknown area to go.

As we can see from the Figure 3.6, in this situation, the robot can only choose the direction of the green arrow, because the lower part of the unknown region is already explored.

Multi-agent approach

The goal of a multi-robot exploration process is to cover the whole environment in a minimum amount of time. Therefore, it is essential that the robots keep track of which areas of the environment have already been explored. Furthermore, the robots have Throughout this section we first assume that at every point in time both the map of the area explored so far and the positions of the robots in this map can be communicated between the robots. We will focus on the question of how to coordinate the robots in order to efficiently cover the environment. At the end of this section, we will consider the situation in which the robots have a limited communication range.

i matrix p q s n !" m p# M @ $ % @ $ % @ $ % sc sc sc sc p q n m x y ® ® &' y s x P N ( N - ) M 0 M - 123 24
Our system uses occupancy grid maps to represent the environment. Each cell of such an occupancy grid map contains a numerical value representing the posterior probability that the corresponding area in the environment is covered by an obstacle.

Since the sensors of real robots generally have a limited range and since often parts of the environment are blocked by objects, a map generally contains certain cells whose value is unknown since they have never been updated so far. Throughout this work, we assume that exploredness is a binary concept and we regard a cell as explored as soon as it has been intercepted by a sensor beam. At this point,we would like to mention that the approach presented here is not restricted to occupancy maps. The only requirement is that the underlying representation of the environment must allow the distinction between known and unknown areas and to compute travel costs for the individual robots. Therefore, our algorithm can also be applied to alternative representations like topological maps or coverage maps.

ROBOT EXPLORATION

When exploring an unknown environment we are especially interested in frontier cells. As a frontier cell we denote each already explored cell that is an immediate neighbor of an unknown, unexplored cell. If we direct a robot to such a cell, we can expect that it gains information about the unexplored area when it arrives at its target location. The fact that a map generally contains several unexplored areas raises the problem of how to assign exploration tasks represented by frontier cells to the individual robots. If multiple robots are involved, we want to avoid several of them moving to the same location. To deal with these problems and to determine appropriate target locations for the individual robots our system uses a decision theoretic approach. We simultaneously consider the cost of reaching a frontier cell and the utility of that cell.

For each robot, the cost of a cell is proportional to the distance between the robot and

Problem setting

Our multi-robot exploration method is presented under the following assumptions.

1. The robots move in a planar workspace W ⊆ R 2 .

2. Each robot is a disk of radius ρ, whose configuration q = (x R , y R ) is described by the cartesian position of its center.

3. Each robot's path is controllable, which means that it may follow any path in its configuration space with required accuracy. This assumption is verified for free-flying as well as (most) non-holonomic mobile robots.

4. The robots are equipped with an omnidirectional sensory system (in our simulation with a laser range finder and in real application for infrared sensors)that provides the Safe Region SR(q),which is a description of the free space surrounding the robot at p. The SR is a star-shaped subset of R 2 , whose maximum radius is bounded by the robot perception range R p ( see in the Figure 3.7). Many of these assumptions are only taken for simplicity and can be relaxed. The assumption of planar workspace is obviously not restrictive: three dimensional worlds are perfectly admissible as long as the sensory system allows the reconstruction of a planar SR for planning the robot motion. Assumption 2 implies that the configuration space of each robot is a copy of the workspace with the obstacles grown so as to allow for the robot size. This assumption is only taken for ease of presentation: the proposed method is readily applicable to robots with arbitrary shape (but for real application, the Robotino R robot is round). In Assumption 3, path controllability can be replaced with (simple) controllability provided that a regional path planner (i.e., an algorithm that generates feasible paths in a limited region) is available. Assumption 4, and in particular the star-shaped hypothesis, is consistent with the physics of the most At this stage, our exploration task can be informally defined as follows: the objective is to cooperatively cover the largest possible portion of the workspace with sensor perceptions. A more formal definition will be given in the following in connection with the termination condition for our method.

Cost function

To determine the cost of reaching the current frontier cells, we compute the optimal path from the current position of the robot to all frontier cells based on a deterministic variant of the value iteration, a popular dynamic programming algorithm. In the following, a tuple (x, y) corresponds to the x-th cell in the direction of the x-axis and the y-th cell in direction of the y-axis of the two-dimensional occupancy grid map. In our approach, the cost for traversing a grid cell (x; y) is proportional to its occupancy value P (occ xy ). The minimum-cost path is computed using the following two steps:

1. Initialization. The grid cell that contains the robot location is initialized with 0, 2. Update loop. For all grid cells (x, y) do:

V x,y ← min{V x+∆x,y+∆y + ∆x  + ∆y  • P (occ x+∆x,y+∆y ) |∆x, ∆y ∈ {-, , } ∧ P (occ x+∆x,y+∆y ) ∈ [, occ max ]} (3.5)
where occ max is the maximum occupancy probability value of a grid cell the robot is allowed to traverse. This technique updates the value of all grid cells by the value of their best neighbors, plus the cost of moving to this neighbor. Here, cost is equivalent to the probability P (occ x,y ) that a grid cell (x, y) is occupied times the distance to the cell. The update rule is repeated until convergence. Then each value V x,y corresponds to the cumulative cost of moving from the current position of the robot to (x, y). The convergence of the algorithm is guaranteed as long as the cost for traversing a cell is not negative and the environment is bounded. Both criteria are fulfilled in our approach.

Multi-agent approach

The resulting value function V can also be used to efficiently derive the minimum-cost path from the current location of the robot to arbitrary goal positions (x, y). This is done by steepest descent in V , starting at (x, y). We will show the resulting value functions for two different robot positions. The black rectangle indicates the target point in the unknown area with minimum travel cost. Note that the same target point is chosen in both situations. Accordingly, if the robots are not coordinated during exploration, they would move to the same position which obviously is not optimal.

Our algorithm differs from standard value iteration in that it regards all actions of the robots as deterministic, which seriously speeds up the computation. To incorporate the uncertainty of the robots' motions into the process and to benefit from the efficiency of the deterministic variant, we smooth the input maps by a convolution with a Gaussian kernel. This has a similar effect as generally observed when using the nondeterministic approach: It introduces a penalty for traversing narrow passages or staying close to obstacles. Therefore, the robots generally prefer target points in open spaces rather than behind narrow doorways. Note that the maps have not been smoothed to allow the reader to distinguish between walls (dark grey) and the values of the final value function (light grey).

Computing utilities of frontier cells

Estimating the utility of frontier cells is more difficult. In fact, the actual information that can be gathered by moving to a particular location is impossible to predict, since it very much depends on the structure of the corresponding area. However, if there already is a robot that moves to a particular frontier cell, the utility of that cell can be expected to be lower for other robots. But not only the designated target location has a reduced utility. Since the sensors of a robot typically cover a certain region around a particular frontier cell as soon as the robot arrives there, even the expected utility of frontier cells in the vicinity of the robot's target point is reduced.

In this section, we will present a technique that estimates the expected utility of a frontier cell based on the distance and visibility to cells that are assigned to other robots. Suppose in the beginning each frontier cell t has the utility U t which is equal for all frontier cells if no additional information about the usefulness of certain positions in the environment is available. Whenever a target point t ′ is selected for a robot, we reduce the utility of the adjacent frontier cells in distance d from t ′ according to the probability P (d) that the robot's sensors will cover cells in distance d. One can estimate P (d) by maintaining a posterior about the estimated distances to be measured. While the robot moves through the environment, this posterior is updated.

Thus, any cell t in distance d from the designated target location t ′ will be covered with probability P (d) when the robot reaches t ′ . Accordingly, we compute the utility U (t n |t 1 , . . . , t n-1 ) of a frontier cell t n given that the cells t 1 , . . . , t n-1 have already been assigned to the robots 1, . . . , n -1 as

U (t n |t 1 , . . . , t n-1 ) = U tn - n-1 i=1 P ( t n -t i ) (3.6)
According to Equation 3.6, the more robots move to a location from where tn is likely to be visible, the lower is the utility of t n . Note that we also take into account whether there is an obstacle between two frontier cells t and t ′ . This is achieved by a ray-casting operation on the grid map. If there is an obstacle between two frontier cells t and t ′ , we set P ( t -t ′ ) to zero.

In extensive experiments, we could not find a significant difference in the resulting exploration time depending on in which environment the posterior P (d) has been learned. We therefore use the following approximation:

P (d) = 1.0 - d maxrange , if d < max range 0, otherwise (3.7)

Target point selection

To compute appropriate target points for the individual robots we need to consider for each robot the cost of moving to a location and the utility of that location. In particular, for each robot i we trade-off the cost V t i to move to the location t and the utility U t of t.

To determine appropriate target points for all robots, we use an iterative approach.

In each round, we compute that tuple (i, t) where i the number of a robot and t is a frontier cell, which has the best overall evaluation U t -β • V i t . We then recompute the utilities of all frontier cells given the new and all previous assignments according to Equation 3.6. Finally, we repeat this process for the remaining robots. This results in Algorithm 2. The complexity of this algorithm is O(n 2 T ) where n is the number of robots and T is the number of frontier cells.

Algorithm 2 Goal Assignment for Coordinated Multi-Robot Exploration.

1: Determine the set of frontier cells. 2: Compute for each robot i the cost V i t for reaching each frontier cell t. 3: Set the utility U t of all frontier cells to 1. 4: while there is one robot left without a target point do

5:

Determine a robot i and a frontier cell t which satisfy:

(i, t) = argmax (i ′ ,t ′ ) (U t ′ -β • V i ′ t ′ ). 6:
Reduce the utility of each target point t ′ in the visibility area according to U t ′ ← U t ′ -P ( t -t ′ ).

7: end while

The quantity β > 0 determines the relative importance of utility versus cost. Experiments showed that the exploration time stays nearly constant if β ∈ [0.01, 50]. For bigger values of β the exploration time increases because the impact of the coordination is decreased. If β is close to 0 the robots ignore the distance to be traveled which also leads to an increased exploration time. Therefore,β generally is set to 1 in our current implementation.

We will illustrate the effect of our coordination technique. Whereas uncoordinated robots would choose the same target position, the coordinated robots select different frontier cells as the next exploration targets. When coordinating a team of robots during exploration one question is when to re-compute the target locations. In the case of unlimited communication, we compute new assignments whenever one robot has reached its designated target location or whenever the distance traveled by the robots or the time elapsed after computing the latest assignment exceeds a given threshold.

Coordination with limited communication range

In practice, one cannot assume that the robots can exchange information at any point in time. For example, the limited range of nowadays wireless networks can prevent robots from being able to communicate with other robots at a certain point in time. If the distance between the robots becomes too large so that not all robots can communicate with each other, a centralized approach as described above can no longer be applied.

However, our algorithm can easily be adapted to cope with a limited communication range. In our system, we apply our approach to each sub-team of robots which are able to communicate with each other. Obviously, this can, at least in the worst case, lead to a situation in which all robots individually explore the whole environment. In practical experiments, however, we found that this approach still results in a quite efficient exploration process, since the robots can quickly exchange necessary information and coordinate with each other again as soon a connection between them has been reestablished.

In the case of limited communication, we apply a slightly different strategy to determine when to compute new assignments. In our experiments, we found that the risk of redundant work is increased if the robots forget about the assignments of other robots as soon as the communication breaks down. Instead, if each robot stores the latest target locations assigned to other robots the overall performance is increased especially in situations in which the communication range has been exceeded, since the robots avoid going to places already explored by other robots. This approach turned out to be useful especially in the context of small robot teams.

Conclusion of robots exploration

We have proposed an efficient single robot exploration method (see the simulation results in the experimentation chapter) and besides this method, we use multi-robot cooperation to solve the mobile robot exploration problem. The utility computing approach of the frontier cell is crucial for the distribution of the exploration task.

4

Map reconstruction In this work, we present an effective map building method by using a least-mean square technique [START_REF] Tian | An efficient strategy for autonomous mobile robot exploration and map reconstruction[END_REF] to reduce the noise of the data collected by the laser range finder. This method builds a pixel map, with set of obstacle regions which are characterized by their own parameters.

Map representation

There are many ways to represent the map we have explored, among which we choose the cell decomposition method mainly due to its simplicity for our convenience.

Cell Decomposition

We will use the Cell decomposition method [START_REF] Choset | Topological simultaneous localization and mapping (slam): toward exact localization without explicit localization[END_REF] for the division of map, A star method to select the shortest road to goal, and the general perception

p = p b p t × 100% (4.1)
where p b is the number of the black pixels per cell, and p t is the number of the total pixels per cell.

Coefficient to choose

Here we change the coefficient p, and we get the different result of decomposition. From the experiment we made, we can see clearly that the obstacles become bigger when the coefficient p gets smaller, which coincides with our experience. Because we enlarge the criteria, we will miss some obstacle points. In the Figure 4.1, we can easily see that we must compromise for the cell occupation factor, if it is too small, the obstacles will become too large, and in contrast, we will get the problems with the safety navigation.

Data collection

We get laser range-finder and odometric data from the simulation and the real robot.

Reference transformation

We let M and N be respectively the absolute values of the point O p s abscissa and coordinate in the world reference (oxy) in Figure 4.2. In the robot world (oxy) r , the length unit is meter, and the pictures resolution is 500×500 pixels. We pose M = N = 20, which means that we work in a terrain of 400m 2 , and 1 pixel is equal to 4×4cm 2 in 4.2 Data collection the real world. The robot is a round mobile platform with a diameter of 30cm, which is equal to about 8 pixels in the picture.

We divide the map into 100×100 small cells (nb m = nb n = 100), so we have 5×5 pixels in a cell. For the picture of the format PNG, we use the numeration of the cells in the form of (m p , n p ) as the coordinates. Then we will use the following Equation 4.2

to change between the two reference systems, as shown in the Figure 4.2.

(m, n) = (- M 2 + M nb m m p , N 2 - N nb n n p ) = (- M 2 + 0.2m p , N 2

Safety navigation

Considering the size of the robot, we use a new algorithm inspire by [START_REF] Zhu | A new hybrid navigation algorithm for mobile robots in environments with incomplete knowledge[END_REF] to create the gray area for the robot to avoid the collision from the obstacles in the map. The robot is with a diameter of 30cm, and the cell is 20cm in each side. So we have to leave one cell (20cm superior than the radius 15cm) for the safety navigation of the robot.

We divide the map into small cells. In using the picture of the format PNG, we have the coordinate of the cells in the form of (m, n). From the experiment we made, we can see that the result is better when the coefficient p gets bigger.

Map reconstruction algorithm

We have defined a reference direction , and our robot coordinates are electromagnetic compass that is built inside the robot, the angle θ i , which is the ith sensors angle from the 1st sensor, can be simply obtained. As a matter of fact, if the angle θ s (the heading angle of the robot), is also measured, another sensors angle can be calculated as the Equation 4.3:

β i = θ s + θ i (4.3)
where i represents the angle to our coordinate center. The maximum number of the sensor group on the ring is n, and the radius is r. The distance from the origin to the center of the ring is R, and the reference angle to the center is R. The reference position of the ring (the robots center) is (x, y). The distance from the origin to the object which is measured by the ith sensor on the two dimensional plane is named R i .

Let us suppose dm i the measured value from the ith sensor of the robot. However, there is always an error between these values and the exact distance, which can be expressed as the Equation 4.4:

dm i = d i + ǫ i (4.4)
Naturally, we assume that ǫ i is a uniform random variable in the range of (-E, E).

Here E denotes the maximum error of distance measuring. Now our problem is, given x R , y R , θ 1 , θ 2 , ..., θ n , and dm 1 , dm 2 , ..., dm n to estimate the coordinate of the occupied cells and x i , y i , ie. R i in a most efficient method.

The equations relating to the detected obstacle can be written as

R 2 i = (x R + (r + d i )cosβ i ) 2 + (y R + (r + d i )sinβ i ) 2 (4.5) As x R = RcosΩ R , y R = RsinΩ R , we get R 2 i = R 2 + (r + d i ) 2 + 2R(r + d i )cos(Ω R -β i ) (4.6)
The equations involving the robot due to the object can be denoted as

R 2 = (x i -(r + d i )cosβ i ) 2 + (y i -(r + d i )sinβ i ) 2 (4.7)
If we define the objects positions as

P =    p 1 . . . p n    =        x 1 y 1 . . . x 1 y 1        (4.8)
where P is a 2n × 1 matrix, then we get

R 2 = R 2 i + (r + d i ) 2 -2(r + d i )[cosβ i , sinβ i ]p i (4.9)
After the introduction from Equation 4.6 to Equation 4.9, we have

(r + d i + Rcos(Ω R -β i ))  = [cosβ i , sinβ i ]p i (4.10)
Here again, n such equations are produced if we write in matrix form:

r + dm n + Rcos(Ω R -β n )    (4.12) [A] =    L(β 1 ) • • • Φ . . . . . . . . . Φ • • • L(β n )    (4.13)
Here if we perform the least squares estimate for P , we can obtain

(P lsq ) = (A T A) -1 A T m (4.14)
Hence we acquire the best least squares estimator of the obstacle positions. In real-time simulations we can see that the (P lsq ) value calculated is not in accord with R 2 i = (P lsq ) i which actually should. In this condition, a better estimation algorithm for the object positions can be described as (P e ) i = (P lsq ) i R i / (P lsq ) i Go-to-target, Route-follow and Avoid-obstacle, when the navigation situation is more complex, the robot may fall to some kind of traps and cannot get out again. That is why Jayasiri et al. use 5 behaviors. However, more behavior means the coordination is more complicated, to simplify the navigation task, we propose a simplified five-behavior method for navigation. As an effective method, the A star algorithm is used to calculate the shortest path to complete the route-following task [START_REF] Seo | An efficient hardware architecture of the a-star algorithm for the shortest path search engine[END_REF]. In using the general perception method, the wall following behavior is ensured (Braunstingl

et

The introduction of the five behaviors

We propose a five-behavior based algorithm, and these five behaviors are respectively:

Route Following (RF), Target Going (TG), Wall Following (WF), Obstacle Avoiding (OA) and Deadlock Disarming (DD). We can see the relationship between the different behaviors in Figure 5.1.

In our definition, -→ V 1 corresponding to the Route Following behavior, is the velocity vector directed to the nearest subgoal with respect to the current robots position.

-→ V 2 corresponding to the Target Going behavior, is the velocity vector directed to the second nearest subgoal with respect to the current robots position.

-→ V 3 corresponding to the Wall Following behavior, is the velocity vector that is normal to the direction of the resultant repulsive force obtained from the position vectors of obstacles, and it is biased towards the current orientation of the robot.

-→ V 4 corresponding to the Obstacle Avoiding behavior, is the velocity vector that is opposite to the direction of the resultant repulsive force obtained from the position vectors of obstacles, and it guides the robot to get away from the obstacles.

-→ V 5 corresponding to the Deadlock-Disarming behavior, is the velocity vector directed to the exit point from the deadlock with respect to the current robots position whenever one deadlock is detected, then a virtual wall will be put in the exit of the deadlock to make sure that the robot wont knock into it again.

θ t is the robot's previous heading direction.

Route Following (RF) behavior

This behavior focuses on the nearest subgoal point, and is used to help the robot to navigate through the coordinates in the calculated safe route. The RF divergence is calculated by the absolute angle difference between the robots previous heading direction and the direction suggested by the RF behavior. Thus we define the RF membership function as Table 5.1 : termination, which is to decide the turning angle to be 90 or 270 degree according to the directions of the next subgoal and the second nearest subgoal. We define the WF membership function in Table 5.3:

Obstacle Avoiding (OA) behavior

This behavior acts when the distance from the robot to the obstacle exceeds its limit and the robot will retreat, that is to say if the distance between the robot and obstacle is less than its minimum, it will get away from the obstacle. The OA divergence is calculated by the absolute angle difference between the robots previous heading direction and the direction suggested by the OA behavior (see in Table 5.4).

Deadlock Disarming (DD) behavior

This behavior is designed in order to carefully avoid the deadlock situations. When a deadlock is detected on the path, a Boolean variant is made True (i.e., = 1). Then, a virtual object is placed for the robot to follow until the robot has been moved away from the deadlock. The DD divergence is calculated by the absolute angle difference between the robots previous heading direction and the direction suggested by the DD behavior. Then we define the membership function in Table 5.5:

Implementation of the five behaviors

As we have defined the five behavior in the previous section, we need to find a way to apply them in practice.

Path planning

We use A-Star algorithm to calculate the shortest path to fulfil the navigation task [START_REF] Zeng | Finding shortest paths on real road networks: the case for a*[END_REF].

In computer science, A* (A star) is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between points, called nodes. Noted for its performance and accuracy, it enjoys widespread use. However, in practical travel-routing systems, it is generally outper-formed by algorithms which can pre-process the graph to attain better performance, although other work has found A* to be superior to other approaches.

A* uses a best-first search and finds a least-cost path from a given initial node to one goal node (out of one or more possible goals). As A* traverses the graph, it follows a path of the lowest expected total cost or distance, keeping a sorted priority queue of alternate path segments along the way.

It uses a knowledge-plus-heuristic cost function of node x (usually denoted f (x))

to determine the order in which the search visits nodes in the tree. The cost function is a sum of two functions:

• the past path-cost function, which is the known distance from the starting node to the current node x (usually denoted g(x))

• a future path-cost function, which is an admissible "heuristic estimate" of the distance from x to the goal (usually denoted h(x)).

The h(x) part of the f (x) function must be an admissible heuristic; that is, it must not overestimate the distance to the goal. Thus, for an application like routing, h(x) might represent the straight-line distance to the goal, since that is physically the smallest possible distance between any two points or nodes.

If the heuristic h satisfies the additional condition h(x) ≤ d(x, y) + h(y) for every edge (x, y) of the graph (where d denotes the length of that edge), then h is called monotone, or consistent. In such a case, A* can be implemented more efficientlyroughly speaking, no node needs to be processed more than once (see closed set below)and A* is equivalent to running Dijkstra's algorithm with the reduced cost d ′ (x, y) := d(x, y) + h(y) -h(x).

Wall Following and Obstacle Avoiding

We use the general perception method to realise the wall following behavior Braunstingl

et al. (2002).
It is a well known fact, that ultrasonic sensors have very poor directional resolution.

Although these sensors very accurately determine the distance to the nearest object giving back an echo, this object can be anywhere under a certain angle to the sensor's axis. Moreover, this angle depends on the nature of the object's surface,the distance and the tilt of the surface with regard to the sensor's axis. That is why it would be difficult to try to first gain a representation of the immediate surroundings from the sensor data, i.e. to try to model objects or to determine the exact contours of a wall in order to control the robot accordingly. The concept of general perception avoids these difficulties because it does not undertake any kind of modelling of the environment.

Instead, it aims at constructing a so-called general perception of the surroundings from the measuring data provided by all the sensors and representing it as a vector, called general perception vector.

For this purpose every ultrasonic sensor i of the mobile robot is assigned a perception vector p i . Its direction equals the orientation of the sensor's axis and its length is a function of the distance d i measured by this sensor:

p i = d max -d i d max -d min (5.1)
whereby d min and d max designate the shortest and longest distance respectively at which an object may be positioned to be reliably detected. p i is limited to 0 and 1 respectively as Equation 5.2:

p i = 0, f or d i > d max 1, f or 0 < d i < d min (5.2)
This perception vector is comparable to the obstacle vector of the Vector Field

Histogram, but is linked to the sensor and not to a cell of a grid. The general perception vector p is composed of all individual perceptions p i . Its direction equals the sum of the perceptions of all the sensors and its length equals the strongest individual perception:

p = p i,max p i | p i | (5.3)
We use the vector perpendicular to the general perception vector p to realise the wall following behavior and the vector opposite to p for the obstacle avoiding behavior.

How to find a Deadlock

We propose an algorithm to determine if one obstacle contains a deadlock or not, the key is to detect the abrupt variation of distance data in one scan in the laser range finder. We define as the percentage of augmentation in the distance p d in the following the advancing angle, which means that the robot is not deviated from the exit, then it should continue in this way. On the contrary, if the angles are in the completely different direction, which means the robot is going deeply in a deadlock, and then it has to retreat and mark the obstacle, and never come back in the obstacle again.

How to disarm the deadlock

= d 1 -d 2 = l 1 cosθ 1 -l 2 cosθ 2
to test if the robot can pass through. If is bigger than the diameter of the robot, then it is passable. The virtual wall will be created when the robot moves away from the goal. This is identified by the distance of the robot position towards the goal. The increasing distance means that the robot moves away from the goal. On the other hand, if the distance is decreasing it means that the robot moves towards the goal. The creation of the virtual wall will be activated only when the robot reaches the exit point.

To disarm the deadlock, we put a virtual wall in the place of the deadlock, in order to avoid the future block in the cul-de-sac. Using this method, we can detect a deadlock and retreat from it more easily, in order to accomplish the navigation task (see the Figure 5.5).

Where α 1 and α 3 are the angles formed by the robot and the obstacle edges, and α 2 is the average angle of α 1 and α 3 , that is α 2 = 1 2 (α 1 + α 3 ), and R = M ax(l 1 , l 2 ). Then we can get the coordinate of the retreating point is (x, y), where x = x robot + Rcosα 2 , y = y robot + Rsinα 2 .

Behavior coordination and command fusion

As we have already seen in the Figure 5.1 in the first subsection in this chapter, we will use behavior coordination and command fusion method to get the result velocity vector for the mobile robot. be improved by adding modeled blocks, such as gyroscope, camera, etc [START_REF] Karras | Mobile robotics in education and research of logistics[END_REF].

¡¢£ ¤¥¦ §¥¢£ subgoal 2nd nearest subgoal Nearest obstacle V V © V V ª V V « V V ¬ §¥®¯°¢±² ³¥¦´®¤µ direction ¶ §´¤¥¦ §¥¢£ subgoal Exit point • V V q ¹® §£°¦± º¦±±
The omnidirectional drive consists of three Mecanum wheels, all of which are individually controllable. These wheels are arranged at angles of 120 • . Robotino R has a bumper sensor around its circumference, infrared distance sensors, a color camera with VGA resolution, optical wheel encoders, power measurement for the entire system and the various motors, as well as a battery voltage monitor. Moreover, as optional additional sensors, Robotino R can be equipped with a precise laser scanner, a gyroscope, and an indoor positioning system (created by Evolution Robotics). Robotino R is equipped with a camera system. Its height and inclination can be adjusted. The camera makes it possible to display live images with the help of Robotino R

View. Robotino R View also offers a number of image processing options, which can be used to evaluate camera images for the Robotino R controller. A segmenter locates surfaces of like colour within a given image, and can determine the position and size of any segment. Lines in video images can be detected. Results can be utilised for pinpointing objects, as well as for path and object tracking.

A wide range of accessories is available such as sensors, e.g. optical, inductive, cameras, gyroscopes and laser range finders, plus handling devices, e.g. electrical grippers, arms and lifting devices. Moreover, users are able to integrate their own custom devices into Robotino R by making use of various interfaces. Player is one of the most popular robot interfaces in research and post-secondary education. Player supports a wide variety of hardware, and also contains client library support for most programming languages. Stage is a simulator which tends to be very simple and task-specific (Owen, 2010).

Player

Player is a network server for robot control. Running on your robot, Player provides a clean and simple interface to the robot's sensors and actuators over the IP network. A simulation is composed of three parts:

• Your code: This talks to Player.

• Player: This takes your code and sends instructions to a robot. From the robot it gets sensor data and sends it to your code. Stage). It also tells Player how to talk to the driver, and how to interpret any data from the driver so that it can be presented to your code.

• a .inc file, which follows the same syntax and format of a .world file but it can be included, which is easily reusable. Interfaces, Drivers and Device

We present the three main part of the software:

• Interface: A specification of how to interact with robotic hardware. The interface defines the syntax and semantics of all messages that can be exchanged with entities in the same class.

• Driver: A piece of software (usually written in C++) that talks to hardware and translates its inputs and outputs to conform to one or more interfaces.

• Device: A driver bound to an interface so that Player can talk to it directly.

Example: Consider the laser interface. This interface defines a format in which a planar range-sensor can return range readings (basically a list of ranges, with some meta-data). Now consider the sicklms200 driver, which controls a SICK LMS200 laser.

The sicklms200 driver knows how to communicate with the laser hardware and retrieve data from it. It also knows how to translate the retrieved data to make it conform to the format defined by the laser interface. The sicklms200 driver can be bound to the laser interface to create a device, which might have the following address: localhost: 6665:laser:0......

Player talks to the robot using ports (the default port is 6665). Player and Stage communicate through these ports (even if theyre running on the same computer). The above line tells Player which port to listen to and what kind of data to expect. In the example, its laser data which is being transmitted on port 6665 of the computer that Player is running on (localhost).

Stage

Stage simulates a population of mobile robots, sensors and objects in a two-dimensional bitmapped environment. Stage is designed to support research into multi-agent autonomous systems, so it provides fairly simple, computationally cheap models of lots of devices rather than attempting to emulate any device with great fidelity. We have found this to be a useful approach.

Stage is often used a a Player plugin module, providing populations of virtual devices for Player. Users write robot controllers and sensor algorithms as 'clients' to the Player 3. Increase the perception angle, with the same result of the enlarging the perception range.

Exploration

We will test our algorithm with single and multiple robots. As a matter of fact, we reconstruct the map in the same time.

We obtain the first result of exploration, then can reconstruct the environment map from the position and laser range data.

We start from (-7.6, 6.7) and go to (6,7) directly. Reconstruction result is shown as the Figure 6.3. We can see it is very close to the reality. We still start from (-7.6, 6.7) and go to (6,6), but this time, we smooth the trajectory using the random walk method we propose, then we can see that the reconstruction result is even better than the previous one: closer to the reality (see the Figure 6.4). We start from (-2, 6.7) and go to (8, -8). Reconstruction result is shown below (Figure 6.5). The effect is relatively good.

We start from (-4, -1.8) and go to (7.5, -5.8) using our method, then we get the following reconstruction result, see the Figure 6.6. The effect is better.

We start from (-8.6, 8) and we can see from reconstruction image that when there

Recorded area

In using the Play/Stage platform, we record the explored area of the grided map in a matrix, where 0 is for the unexplored area, and 1 for the explored environment.

Multi-robot exploration

We can see from the simulation result that the result is more rapid in terms of time, compared to the single robot exploration. The three robots start at the same time in the same region (in the left lower part of the map), but we can see in the experimentation that the robot making the longest journey dominates the total time of exploration (in our case, the robot 3 use the longest time), which means the bottleneck of the exploration issue.

And we can see the reconstruction result of the multi-agent exploration.

And here in an integrated map generated by the multi-agent exploration method.

As we will see in another situation, if the robots begin the exploration at the center of the environment, ideally the robots spread in all directions, and they may get to every corner of the area simultaneously, thus there is no significant dominating exploration time among the robots.

Navigation

In this section, we will test the robot in several scenarios to see if the robot can fulfil the navigation task.

Test of behaviors

We use the General Perception method to reduce the error and have a good result when the edge of the wall is very shape.

We can find out that with the U or V shape trap, the robot can easily get rid of the traps and follow the exit point to return to the calculated route.

Navigation tests

We start at (1.5, -4) and finish our navigation at (5,0). This picture shows us the effectiveness of our proposed method for robot navigational tasks. The proposed ap-

Performance analysis

We spend 4min 30sec for the complete coverage (70m in total distance), while the existing frontier based method needs 4min 50sec (73m in total distance). However, for the map reconstruction, our method is not in real time (10min 12sec in total), which is our shortcoming. We will change the structure of the data to improve the performance

Synthesis of the contribution

We have presented a reasonable frontier based SLAM algorithm for one single robot.

This algorithm is able to maintain maps, providing robust and accurate mapping without dealing with the global map all the time. And the algorithm does not assume the presence of predetermined landmarks or assume away the data association problem created by the use of landmarks, which greatly simplifies the map reconstruction process.

Then in this work, we propose a multi-robot exploration coordination method using the previously mentioned mono-robot exploration behavior, which is a decentralized strategy for cooperative robot exploration. A map of the explored area is built in the form of a compact data structure. This consists in an appropriate definition of the Local Frontier, by which each robot plans its motion toward areas that appear to be unexplored by the rest of the team on the basis of the available information.

Local coordination guarantees that the collective motion of the team does not lead to collisions. Simulation and experimental results on a team of real robots have shown the satisfactory performance of the method both in ideal and practical conditions, even in the case of limited communication range. We also propose a least-mean square method to reduce the error of the sensor data. A simple and efficient decentralized cooperation mechanism is at the core of our method. Our algorithm has been tested in simulation,

where it has produced maps of good quality in a close environment with the block obstacles.

Finally we present a framework for behavior based robot navigational tasks using behavior coordination and command fusion based on fuzzy control method. The proposed approach resolves a command-fusion and behavior coordination conflict. It is observed that the proposed algorithm is able to provide a successful and goal-oriented navigation with smooth trajectory even in unstructured environments. And we have proved the five-behavior method to be efficient, quick than the former FDES method and capable to fulfill the navigation task.

Perspectives

We are currently working toward several objectives, among which we mention the following:

1. to improve the map reconstruction performance because of the non real-time issue during the exploration;

2. to implement the proposed algorithm in mono-robot and multiple robots;

3. to perform a quantitative study of the robustness and scalability properties of the method.

These three points will be my future work. La carte est construite en utilisant la méthode des moindres carrés pour réduire les erreurs des données des capteurs. En divisant la tâche globale en sous-tâches, un contrôleur intelligent permet de réduire la complexité. Cependant, la fusion des différents comportements ayant des objectifs différents peut entraîner des contradictions et modifier ainsi la stabilité du système. Par conséquent, la question du mécanisme de coordination de comportements est essentielle pour réaliser un mouvement sécurisé sans collisions. Une méthode intégrée par la coordination des comportements et de commande par fusion est proposée dans le présent travail. Une nouvelle approche basée sur cinq comportements de base pour la navigation de robots mobiles est discutée.

Résumé Étendu en Français

Player/Stage est un projet de logiciel open-source pour la recherche sur la robotique. Ses composants comprennent le serveur de réseau et les simulateurs de robot pour plusieurs types de platesformes de robots. Nous utilisons principalement la simulation sous Player/Stage pour tester nos algorithmes en exploration mono-agents/multi-agents, en cartographie et en navigation. Les résultats obtenus montrent que les solutions proposées sont efficaces et peuvent être utilisées dans des robots réels.

Mots-clés: optimisation, cartographie, navigation, robots mobiles coopératifs

Cooperative Mobile Robots Optimal Mapping and Navigation

Abstract: In this Ph.D., we will present firstly a single robot exploration method, then a decentralized cooperative exploration strategy for a team of mobile robots equipped with range finders. A two dimensional map of the explored area is built in the form of a pixel figure. This is expanded by the robots by using a randomized local planner that automatically realizes a decision between information gain and navigation cost. In our work, the map is reconstructed using a least-mean square method to reduce the errors of the sensor data. In dividing the overall task into subtasks, the intelligent controller allows reducing the robots task complexity. But the fusion of different behaviors with different objectives may cause contradiction in the procedure and alter the stability of the system. Therefore, the issue of behavior coordination mechanisms is crucial in order to realize the non-collision safety-ensured movements. A method integrated by behavior coordination and command fusion is proposed. A new approach with five basic behaviors for mobile robot navigation is discussed.

Player/Stage is an open-source software project for research in robotics and sensor systems. Its components include the Player network server and the Stage robot platform simulators providing a hardware abstraction layer to several popular robot platforms. Player is one of the most popular robot interfaces in research. We mainly use Player/Stage simulation to test our algorithms in monoagent/multi-agent exploration, map reconstruction and robot navigation. Obtained results show that the proposed approaches are effective and can be applied in real robots.

Keywords: optimization, map reconstruction, navigation, cooperative mobile robots.

  Player/Stage is an open-source software project for research into robotics and sensor systems. Its components include the Player network server and the Stage robot platform simulators providing a hardware abstraction layer to several popular robot platforms. Player is one of the most popular robot interfaces in research and post-secondary education. We mainly use Player/Stage simulation to test our algorithms in mono-agent/multi-agent exploration, map reconstruction and robot navigation. All these results

6 . 4 7 Conclusion 7 . 1 x 2 1. 2 3 1. 3 4 1. 4 5 1. 4 . 2 6 1. 5 7 1. 6

 647712233445426576 Abbreviations xvii

1. 2

 2 Figure 1.1: Examples of using AMRs to explore hostile environments to humans

  Some techniques use rendezvous for confirmation of reference coordinate. This requires the abandonment of the current actions (De Hoog et al., 2010; Roy and Dudek, 2001), and other techniques constrain robots to stay within communication range (Vazquez and Malcolm, 2004), which limit the dispersion of the robots in the environment and limit their exploration to different areas. Some robots must then play the role of relay to maintain a chain between all robots (Le et al., 2010).

Figure 2 . 1 :

 21 Figure 2.1: Local and global strategy (Rekleitis et al., 1997)

2. 5 )

 5 . The frontiers are defined as a set of contiguous cells. With a representation of the map in the form of grids, the identification of frontier is done by grouping the neighbor frontier cells into one single frontier[START_REF] Balakirsky | Towards heterogeneous robot teams for disaster mitigation: Results and performance metrics from robocup rescue[END_REF]. Approaches based on a topological representation of the map identify a frontier by a topological node, as shown in Figure2.2.These approaches, like these based on the utility (see in the section 2.4.3), focus on guiding the robots separately to the nearby frontiers.

Figure 2 . 2 :

 22 Figure 2.2: Sensor-based random graph exploration in simulation (Franchi et al., 2009)

  Figure 2.3 shows the evaluation of a candidate position. This method is impractical in multi-robot because it requires sampling several positions to evaluate. This process is already time-consuming for one single robot, not to speak the complexity of the combinatorial analysis for the sampled positions. Furthermore, Holz et al. (2010) estimate that monorobot this approach is less effective in exploration time than frontier-based approaches.

Figure 2 . 3 :

 23 Figure 2.3: Evaluation of a candidate position as frontier of exploration target. The visible area outside the explored areas is evaluated by ray radiating from the candidate position (González-Banos and Latombe, 2002)

  Approaches of Wurm et al. (2008) and Gossage et al. (2006) discretise the map partially constructed in Voronoi cells and assign the frontier cells to robots. Figure 2.4 illustrates the construction of topological graph based on Voronoi discretization. The nodes of the topological map are the nodes associated to the Voronoi cells. Robots are assigned to the unexplored cells. These methods are close to the methods using the utility and grouping frontier cells because they also avoid assigning multiple robots to the neighbor frontiers.

Figure 2 . 4 :

 24 Figure 2.4: Graph based on the discretization of Voronoi (Gossage et al., 2006). The triangle represents the robot, the squares are the unexplored nodes and disks are explored nodes. The dotted lines show the perception of the robot.

Figure 2 . 5 :

 25 Figure 2.5: Segmentation of the environment with K-means algorithm, with K equal to the number of the robots (Puig et al., 2011).

Figure 2 . 6 :

 26 Figure 2.6: Implicit coordination: three robots leave the explored corridor in the lower part of the figure, and separate in a balanced way before the crossing. The frontiers are in red, and the robot are in blue. Each robot goes to its nearest frontier.

Figure 2 .

 2 7 shows an allocation of the frontiers with greedy algorithm. Most frontier allocation approaches are based on this algorithm (Burgard et al., 2005), (Simmons et al., 2000) and (Zlot et al., 2002).

Figure 2 . 7 :

 27 Figure 2.7: Illustration of the assignment of the frontiers with the greedy algorithm. The robot-frontier couple are assigned by the order of the cost from the lowest to the highest.

Burgard

  et al. (2005) use the greedy algorithm by adding a criterion of importance

  runs directly on a cost matrix. It finds optimally the minimisation of the sum of the exploration cost of each task. Its complexity is O(n 3 ) where n is the maximum number between the number of robots and the number of frontiers. It is suitable for assigning frontiers to the robots and has often been used for multi-robot exploration[START_REF] Ko | A practical, decisiontheoretic approach to multi-robot mapping and exploration[END_REF][START_REF] Wurm | Coordinated multi-robot exploration using a segmentation of the environment[END_REF].

  et al.(2005) is preferable, which consist of a random research combined to a local optimisation method. However, the number of the robots must stay reasonable, depending on the calculation power of the central computer; according to the authors, this method calculates the assignment of twenty robots in seconds and more than a minute for forty robots.

  (a) Robot 1 tries to avoid robot 2 in the beginning, which takes longer time for robot 2 to finish the exploration task (b) Robot 1 goes straight without contouring the robot 2 at first place, which reduces the trajectory of robot 2

Figure 2 . 8 :

 28 Figure 2.8: Comparison of two ways for robot 1 moving to point a and robot 2 to point b (Burgard et al., 2005)

  (a) Initial network configuration. (b) Final configuration after 300 seconds. (c) Occupancy grid generated for the final configuration.

Figure 2 .

 2 Figure 2.9: A proto-typical deployment experiment for a 100-node network (Howard et al., 2002).

Figure 2 .

 2 Figure 2.10: Example of GPA/GEA construction. Top: The GPA of robot 4 consists of robots 1, 3, 4, and 7: robot 1 is still moving toward its target point,while robots 3, 4, and 7 are stationary. The perception areas of the robots (prospective in the case of robot 1) overlap in pairs. Bottom: Once the LSR have been computed, only robots 3, 4, and 7 belong to the GEA of robot 4 since their LSRs overlap in pairs (Franchi et al., 2009).

  Over the last decades, different exploration strategies have been proposed in the literature. Maps may be reconstructed incrementally by integrating measurements on the basis of the (probabilistic) estimated positions of the robot Thrun et al. (1998) or of the geometrical features of the maps Amigoni et al. (2006). Another group of exploration method is Frontier-Based exploration Yamauchi (1997), where occupancy grids are used to detect the boundary between explored and unexplored cells (called frontiers) and then a grid-based path planning technique such as A star algorithm Holz et al. (2010) is applied to guide the robot to each frontier. In addition, similar approaches such as Voronoi-Graph-Based exploration Choset and Nagatani (2001) uses Voronoi Graph to explore unknown nodes in the graph and feature-based exploration Chong and Kleeman (1999) uses exploration paths that are dictated by mapped geometric features to explore environments. Other exploration strategies have been proposed Amigoni and Gallo (2005); Burgard et al. (2005); Sim and Roy (2005); Stachniss and Burgard (2003).Comparative evaluations of different strategies are made in[START_REF] Lee | Quantitative evaluation of the exploration strategies of a mobile robot[END_REF] and[START_REF] Amigoni | Experimental evaluation of some exploration strategies for mobile robots[END_REF].

•

  unknown: occupancy probability = prior probability • occupied: occupancy probability > prior probability A process analogous to edge detection and region extraction in computer vision is used to find the boundaries between open space and unknown space. Any open cell adjacent to an unknown cell is labeled a frontier edge cell. Adjacent edge cells are grouped into frontier regions. Any frontier region above a certain minimum size (roughly the size of the robot) is considered a frontier.

Figure 3 . 1 :

 31 Figure 3.1: Schema for the calculation of the sensor number SN .

Figure 3 . 2 :

 32 Figure 3.2: Reference transformation from the image to the matrix

Figure 3 . 3 :

 33 Figure 3.3: Obstacle encountering region

Figure 3 . 4 :

 34 Figure 3.4: Detection zone of minimum distance

Figure 3 . 5 :

 35 Figure 3.5: Algorithm of exploration

Figure 3 . 6 :

 36 Figure 3.6: When the robot encounters an obstacle, it will choose a non-visited direction to continue its way, but in this situation, we can only choose the green arrow pointed direction

Figure 3 . 7 :

 37 Figure 3.7: Perception range of the Robotino R in simulation

Contents 4 . 1 49 4. 2 51 4. 3

 41492513 Map representation . . . . . . . . . . . . . . . . . . . . . . . . 49 4.1.1 Cell Decomposition . . . . . . . . . . . . . . . . . . . . . . . . 49 4.1.2 Coefficient to choose . . . . . . . . . . . . . . . . . . . . . . . Data collection . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.2.1 Reference transformation . . . . . . . . . . . . . . . . . . . . 50 4.2.2 Safety navigation . . . . . . . . . . . . . . . . . . . . . . . . . Map reconstruction algorithm . . . . . . . . . . . . . . . . . . 53 4.4 Conclusion of the map reconstruction . . . . . . . . . . . . . 55 Exploration and map reconstruction are very important for autonomous mobile robots (known as AMR) operating in initially unknown or dynamic area. The Exploration problem can be modeled as the travelling salesman problem (TSP) or the shortest watchmen route problems. Since the original art gallery problem is non-deterministic polynomial complete Aggarwal (1984) and always requires complete knowledge about the environment. As a matter of fact, mapping is an incremental process. Since the ranges of the sensors (ex. sonar or laser) are limited, measurements are inaccurate, and errors may occur along the process, that is why map building is usually performed by taking several measurements of environments at different positions and by integrating these measurements in a global map. Therefore to explore an unknown area is usually carried out in a reactive way. Over the last decades, different exploration strategies have been proposed in the literature. Maps may be reconstructed incrementally by integrating measurements on the basis of the (probabilistic) estimated positions of the robot Thrun et al. (1998) or of the geometrical features of the maps Amigoni et al. (2006). Another group of exploration method is Frontier-Based exploration Yamauchi (1997), where occupancy grids are used to detect the boundary between explored and unexplored cells (called frontiers) and then a grid-based path planning technique such as A star algorithm Holz et al. (2010) is applied to guide the robot to each frontier. In addition, similar approaches such as Voronoi-Graph-Based exploration Choset and Nagatani (2001) uses Voronoi Graph to explore unknown nodes in the graph and feature-based exploration Chong and Kleeman (1999) uses exploration paths that are dictated by mapped geometric features to explore environments. Other exploration strategies have been proposed Amigoni and Gallo (2005); Burgard et al. (2005); Sim and Roy (2005); Stachniss and Burgard (2003). Comparative evaluations of different strategies are made in Lee and Recce (1997) and Amigoni (2008). As for the map reconstruction issue, the research are dated to the work by Smith and Cheesman Smith and Cheeseman (1986) and Durrant-Whyte Durrant-Whyte (1988).The conceptual break-through came with the realization that the combined mapping and localisation problem, once formulated as a single estimation problem, was actually convergent. Most importantly, it was recognised that the correlations between landmarks, that most researchers had tried to minimize, were actually the critical part of the problem and that, on the contrary, the more these correlations grew, the better the solution. The structure of the SLAM problem, the convergence result and the coining of the acronym SLAM was first presented in a mobile robotics survey paper presented at the 1995 International Symposium on Robotics Research Durrant-Whyte et al.(1996). The essential theory on convergence and many of the initial results were developed by[START_REF] Csorba | Simultaneous localisation and map building[END_REF]. Several groups already working on mapping and localisation, notably at MIT[START_REF] Leonard | A computationally efficient method for largescale concurrent mapping and localization[END_REF], Zaragoza Castellanos et al. (1998), the ACFR at Sydney Guivant et al. (2000); Williams et al. (2000) and others Chong and Kleeman (1999); Deans and Hebert (2001), began working in earnest on SLAM applications in indoor, outdoor and sub-sea environments. Recently, a number of key papers were produced, establishing a statistical basis for describing relationships between landmarks Sola et al. (2012) and manipulating geometric uncertainty Häme and Hakula (2013). A key element of this work was to show that there must be a high 4.1 Map representation degree of correlation between estimates of the location of different landmarks in a map and that indeed these correlations would grow with successive observations.

  method for the wall following behavior Braunstingl et al. (2002). And we would like to add a dead-end-disarming behavior in the Huq et al. (2006) using the notion in the Ganapathy et al. (2009); Qing-yong et al. (2009), and modify fuzzy rules of the 5 behaviors in our algorithm. We propose the cell occupation function to precede the cell decomposition for the robots static map split, with the Equation 4.1:

Figure 4 . 1 :

 41 Figure 4.1: Determination of p for cell decomposition

Figure 4 . 2 :

 42 Figure 4.2: Reference transformation between the image and the real world

( a )

 a Original image of map under grid (b) Map after the process of cell decomposition (c) Map after the safety navigation process (region in gray are considered as obstacles) (d) Path planning

Figure 4 . 3 :

 43 Figure 4.3: Process for the robot navigation

  introduce new matrix as [Φ] = [, ] and [L(β i )] = [cosβ i , sinβ i ], then the n × 1 matrix [m] and n × 2n matrix [A] can be denoted as [m] =    r + dm 1 + Rcos(Ω R -β  ). . .

  (4.15) command fusion method by[START_REF] Saffiotti | Fuzzy logic in autonomous robotics: behavior coordination[END_REF];[START_REF] Yen | A fuzzy logic based extension to payton and rosenblatt's command fusion method for mobile robot navigation[END_REF].The former one can only choose one behavior at a time, whereas the later can combine the weighted behaviors at each time iteration. As the notion of Discrete Event System is first used in the work of Cassandras and Lafortune (2008), and is developed by several scientists Lin and Ying (2002); Qiu (2005), there are more researchers who use the fuzzy logic control in this kind of system, the Fuzzy Discrete Event System. Huq et al. (2006) use a priority based arbitration system to cope with one behavior at a time, which is the normal arbitration methods shortcoming, then combine the weighted behavior to carry out the response to the sensory information. However, Jayasiri et al. (2011) highlight the aspect of supervisory control of FDES. Huq et al. use three behaviors:

  al., 2002). Besides, a new obstacle detection function and a subway point recording function are proposed to fulfill the obstacle-avoiding and route-following behavior. The visualization of the map reconstruction and the shortest path are accomplished by the C++ image processing class. In this section, we will introduce a 5-behavior navigation algorithm as our work studied in Tian et al. (2014) and Tian and El Kamel (2014a).

Figure 5 . 1 :

 51 Figure 5.1: Relationship between the 5 behaviors.

3 Figure 5 . 3 :

 353 Figure 5.3: Determination of p 0 in experimentation

This figure below 5 . 4

 54 shows how we can calculate the passability of the robot in a navigation behavior, where l 1 and l 2 are the distance to the obstacle edge, θ 1 and θ 2 are the angle formed with the horizontal line, d 1 and d 2 is the distance between the obstacles. Then we can use the distance d defined by d

Figure 5 . 4 :

 54 Figure 5.4: Passability of the deadlock

Figure 5 . 6 :

 56 Figure 5.6: Vector schema of the 5 behaviors.

  (a) Robotino R in the laboratory (b) Robotino R in the laboratory

Figure 6 . 1 :

 61 Figure 6.1: Robotino R in the laboratory

6. 2

 2 Simulator: Player/Stage Player/Stage is an open-source software project for research into robotics and sensor systems. Its components include the Player network server and the Stage robot platform simulators providing a hardware abstraction layer to several popular robot platforms.

  Your client program talks to Player over a TCP socket, reading data from sensors, writing commands to actuators, and configuring devices on the fly.Player supports a variety of robot hardware. The original Player platform is the ActivMedia Pioneer 2 family, but several other robots and many common sensors are supported. Player's modular architecture makes it easy to add support for new hardware, and an active user/developer community contributes new drivers.

'

  server'. Typically, clients cannot tell the difference between the real robot devices and their simulated Stage equivalents (unless they try very hard). We have found that Player clients developed using Stage will work with little or no modification with the real robots and vice versa. Thus Stage allows rapid prototyping of controllers destined for real robots. Stage also allows experiments with realistic robot devices you don't happen to have. Various sensors and actuator models are provided, including rangefinders (sonar, SICK and Hokuyo laser scanners, IR), vision (color blob detection), 3D depth-map camera, odometry (with drift error model), and a differential steer robot base.

  (a) Robot exploration of the higher part of the map (b) Reconstruction of the higher part of the map

Figure 6 . 3 :

 63 Figure 6.3: Map reconstruction using Algorithm I (higher part)

  (a) Robot exploration of the higher part of the map (b) Reconstruction of the higher part of the map

Figure 6 . 4 :

 64 Figure 6.4: Map reconstruction using our algorithm (higher part)

  (a) Robot exploration of the lower part of the map (b) Reconstruction of the lower part of the map

Figure 6 . 5 :

 65 Figure 6.5: Map reconstruction using Algorithm I (lower part)

Figure 6 . 6 :

 66 Figure 6.6: Map reconstruction using our algorithm (lower part)

  (a) Original map (b) Reconstructed map

Figure 6 . 9 :

 69 Figure 6.9: Map reconstruction comparison

( a )

 a Robot position in the simulation (b) One sample time before recording (c) One sample time after recording

Figure 6 . 10 :Figure 6 . 11 :

 610611 Figure 6.10: Record of the explored area

3 Figure 6 . 12 :Figure 6 . 13 :

 3612613 Figure 6.12: Respective reconstruction of the three robots

Figure 6 . 14 :Figure 6 . 15 :

 614615 Figure 6.14: Test for the Wall Following behavior

Figure 6 . 16 :

 616 Figure 6.16: Test for the failed navigation(blocked in the unstructured obstacle) from Huq et al. (2006)

Figure 7 . 2 :

 72 Figure 7.2: Algorithme d'exploration monorobot

  (a) Environnement à explorer (b) Carte construite

Figure 7 . 3 :Figure 7 . 4 : 2 .

 73742 Figure 7.3: Construction de la carte d'une zone explorée

  operation, but they are difficult to apply with a large number of robots. The approaches with no communication or indirect communication allow the cooperation but can not build map, and can not guarantee the completeness of exploration. Strategies based on explicit coordination induce a communication cost which does not allow to apply with a large number of robots. The implicit coordination proposed by Yamauchi (1998) is a

good compromise between communication and cooperation, but its performance is far below the approaches using explicit coordination. In this thesis, we are interested to complete exploration of environments in a minimum time and we propose a strategy based on implicit coordination, with a performance similar to the approaches of explicit coordination.

The above problem is very rich in variants and constraints. In the next section we specify the problem statement and its variants. 3 Robot exploration Contents 3.1 Single robot method . . . . . . . . . . . . . . . . . . . . . . . . 32 3.1.1 Frontier-based exploration . . . . . . . . . . . . . . . . . . . . 3.1.2 Frontier detection . . . . . . . . . . . . . . . . . . . . . . . . 3.1.3 Navigation to frontiers . . . . . . . . . . . . . . . . . . . . . . 3.1.4 Recording the explored area . . . . . . . . . . . . . . . . . . . 3.1.5 Proposed exploration algorithm . . . . . . . . . . . . . . . . . 3.2 Multi-agent approach . . . . . . . . . . . . . . . . . . . . . . . 36 3.2.1 Problem setting . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Cost function . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Computing utilities of frontier cells . . . . . . . . . . . . . . . 3.2.4 Target point selection . . . . . . . . . . . . . . . . . . . . . . 3.2.5 Coordination with limited communication range . . . . . . .

3.3 Conclusion of robots exploration . . . . . . . . . . . . . . . . 46

Table 5 . 3 :

 53 The Combined Membership Function for WF behavior.

	Distance to the nearest obstacle WF divergence |θ t -∡	--→ W F |	β 3
		Small		Medium
	Near	Medium		Medium-Big
		Big		Big
		Small		Small-Medium
	Medium	Medium		Medium
		Big		Medium-Big
		Small		Small
	Far	Medium		Small-Medium
		Big		Medium

Table 5 . 4 :

 54 The Combined Membership Function for OA behavior.

	Distance to the nearest obstacle OA divergence |θ t -∡	-→ OA|	β 4
		Small		Medium
	Near	Medium		Medium-Big
		Big		Big
		Small		Small-Medium
	Medium	Medium		Medium
		Big		Medium-Big
		Small		Small
	Far	Medium		Small-Medium
		Big		Medium

Table 5 . 5 :

 55 The Combined Membership Function for DD behavior.

	Distance to the exit point OA divergence |θ t -∡	-→ OA|	β 5
		Small		Small
	Near	Medium		Small-Medium
		Big		Medium
		Small		Small-Medium
	Medium	Medium		Medium
		Big		Medium-Big
		Small		Medium
	Far	Medium		Medium-Big
		Big		Big

•

  Stage: It receives instructions from Player and moves a simulated robot in a simulated world, it gets sensor data from the robot in the simulation and sends this to Player. Basically, there are three important file types, and we have to understand: • a .world file tells Player/Stage what things are available to put in the world. You describe your robot, any items which populate the world and the layout of the world.

	• a .cfg (configuration) file is what Player reads to get all the information about
	the robot that you are going to use. This file tells Player which drivers it needs to
	use in order to interact with the robot (if you use simulation, the driver is always

Table 6 . 2 :

 62 The parameters of the Robotino R 's size in our simulation.

	Enneagon Degree( • ) Radius(m) x(m)	y(m)
	1	10	0.171	0.168 0.030
	2	30	• • •	0.148 0.086
	3	50	• • •	0.110 0.131
	4	70	• • •	0.058 0.161
	5	90	• • •	0	0.171
	6	110	• • •	-0.058 0.161
	7	130	• • •	-0.110 0.131
	8	150	• • •	-0.148 0.086
	9	170	• • •	-0.168 0.030
	10	190	• • •	-0.168 -0.030
	11	210	• • •	-0.148 0.086
	12	230	• • •	-0.110 0.131
	13	250	• • •	-0.058 -0.161
	14	270	• • •	0	-0.171
	15	290	• • •	0.058 -0.161
	16	310	• • •	0.110 -0.131
	17	330	• • •	0.148 -0.086
	18	350	0.171	0.168 -0.030
	2. Increase the number of the captors, making the robot's dead angle smaller ( 1 2 of
	the previous one), which enlarges the perception range;

Table 6 . 3 :

 63 Comparison of the existing algorithm to the proposed algorithms (RT = Real Time)

	Comparison	Time	Trajectory length Mapping quality
	Single robot 2 times of RT	-3m	Good
	Multi-robot	≈ RT	--	Good

7.1 Synthesis of the contribution . . . . . . . . . . . . . . . . . . 89 7.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

  est multiplié par n si tous les robots observent durant toute l'exploration des parties différentes de l'environnement.En revanche, quand ils observent les mêmes zones, les robots n'apportent pas plus d'information au niveau de l'exploration mais leurs apports d'information peuvent améliorer la précision de la carte sur ces zones déjà explorées. En pratique, le gain dépend de la topologie de l'environnement et de la position initiale des robots.Précision de la carte Comme indiqué dans la partie "rapidité dexploration", plus la quantité d'informations récoltées sur la carte est importante, plus la précision de la carte construite sera grande. Aussi, si les robots coopèrent pour se localiser, cette précision peut encore augmenter. Les robots peuvent, par exemple, mutuellement s'observer afin de se localiser plus précisément par triangulation. La nécessité d'utiliser ces techniques dépend de la précision de la localisation des robots et de la précision voulue de la carte à construire.

	hostiles, comme les mines souterraines (figure 7.1(b)) et les environnements sous-marins Leurs effets sont l'immobilisation d'un robot, la perte définitive de communica-
	(figure 7.1(d)). Les applications de l'exploration robotique sont nombreuses également tion ou l'arrêt total du système. En monorobot une panne signifie généralement
	pour la surveillance des villes, des bâtiments industriels ou des maisons. Il y a aussi l'échec de la mission et la nécessaire réparation du robot afin de pouvoir contin-
	des applications sur internet tels que Google Maps qui commence à proposer des visites uer. En multirobot, la perte d'un ou plusieurs robots n'entraîne pas l'échec de la
	virtuelles de bâtiments comme des monuments historiques ou des centres commerciaux. mission en cours, les robots encore opérationnels pouvant continuer. Aussi, si un
	L'exploration robotique est un sujet largement étudié depuis les débuts de la robo-robot est bloqué à cause d'une zone dangereuse mais continue de fonctionner, il
	tique mobile car considéré comme un des problèmes emblématique de la robotique mo-pourra prévenir les autres robots du danger.
	bile autonome. Les recherches se sont d'abord concentrées sur l'exploration mono-robot.
	Motivation de la recherche La miniaturisation des composants robotiques et la diminution de leurs coûts permet
	aujourd'hui d'envisager le déploiement effectif de flottilles de robots, pour réaliser toutes
	les tâches pour lesquelles l'utilisation de plusieurs robots constitue un réel avantage.
	Rapidité d'exploration L'utilisation de plusieurs robots permet de diviser l'exploration
	en plusieurs régions assignées à des robots différents. Cette exploration simultanée
	de différentes zones permet de découvrir plus rapidement l'environnement qu'avec
	Dans cette thèse, nous nous intéressons particulièrement à ce dernier problème. Plus un seul robot qui devra explorer séquentiellement chaque zone. Nous verrons que
	précisément, nous cherchons une stratégie permettant plusieurs robots de cartographier le nombre de robots à mettre en oeuvre dépend du type d'environnement exploré.
	toutes les parties visibles de l'environnement dans un délai relativement moins court Par exemple, l'exploration d'un seul long couloir en partant d'une extrémité ne
	et le plus précisément possible. Dans ce contexte, l'utilisation de plusieurs robots est avantageuse car elle permet d'augmenter l'efficacité en temps et en précision de la nécessite pas plus d'un robot; les robots supplémentaires ne pouvant que suivre le Avantages et inconvénients premier. Le bénéfice apporté par l'ajout de robots n'est pas systématique, en ef-
	couverture. Cependant, comme nous le montrerons dans la suite, le gain est conditionné Nous présentons, tout dabord, les avantages d'une approche multirobot. fet, les gênes potentielles entre robots peuvent augmenter le temps d'exploration.
	par le niveau de coopération entre les robots. La mise en oeuvre d'une stratégie de Le gain maximal théorique sur le temps d'exploration de l'utilisation de n robots,
	coopération est donc primordiale pour une cartographie multirobot efficace. Robustesse Un robot peut être sujet à des pannes à cause d'un mauvais fonction-plutôt qu'un seul, est de n. Le temps d'exploration théorique avec n robots est
	Les avancées technologiques récentes ont permis d'utiliser les robots mobiles au-
	tonomes non seulement dans des environnements contrôlés pour les travaux simples,

L'exploration d'un environnement est un problème fondamental en robotique mobile. Elle consiste à découvrir un environnement inconnu ou évolutif et à en construire une représentation. La carte de lenvironnement qui en résulte est en général nécessaire aux robots pour accomplir une tâche complexe de façon autonome. Ainsi l'exploration doit déterminer comment les robots cartographient un terrain inconnu pour en découvrir les caractéristiques. Pendant l'exploration, le problème de la couverture se pose. Celle-ci consiste à déterminer comment les robots se déplacent dans l'environnement afin d'observer exhaustivement toute la zone de l'environnement; c'est donc un sousproblème de l'exploration. La couverture est complète si la totalité de l'environnement a été observée. Initialement, l'exploration d'environnements inconnus nécessite la résolution de trois sous-problèmes : la localisation d'un ou plusieurs robots, la cartographie des zones observées et la couverture du terrain, au sens de la découverte d'un espace inconnu. Ainsi, l'exploration multirobot fait l'objet de nombreux travaux car les avantages par rapport au monorobot sont nombreux; principalement au niveau de l'efficacité et de la robustesse. Les approches existantes sont cependant centralisées et elles reposent fortement sur la communication entre robots. La bande passante des dispositifs de communication sans fil étant limitée, ces approches ne passent pas à l'échelle d'un grand nombre de robots. C'est pourquoi la principale motivation de ce travail est de proposer une approche décentralisée et distribuée qui limite naturellement les communications. L'objectif est ainsi d'accroître les performances en temps d'exploration des approches multirobot actuelles tout en limitant leurs coûts de calcul. En effet, les systèmes multirobot sont, en général, composés de robots simples, peu coûteux et possédant une faible capacité de calcul. L'expérimentation et la validation de l'approche proposée ont été effectuées en simulation. Le contexte de cette thèse est le défi robotique à cartographier un environnement structuré et à y localiser des obstacles de manière complètement autonome (sans intervention humaine) et dans un temps contraint. nement des batteries, des moteurs, des cartes électroniques ou des autres composants. Il peut aussi être bloqué contre un obstacle ou simplement être perdu. Approche décentralisée et distribuée Du point de vue de la robustesse, une approche centralisée de la coordination et/ou de la collection/consultation de données fait reposer le succès de la mission sur un seul composant. En comparaison, un système décentralisé ne comporte pas de noeuds plus importants que d'autres et la perte d'un noeud ne compromet pas le succès de la mission. Du point de vue calcul, la distribution sur plusieurs noeuds du problème est plus efficace et permet un meilleur passage à l'échelle. L'utilisation d'un calcul distribué pour la cartographie permet une plus grande efficacité de calcul et une moins grande utilisation de la mémoire. En effet, chaque robot n'a pas besoin de visiter et de construire une carte précise de tout l'environnement. Toutefois, le problème étant global, il doit disposer d'une information permettant de savoir quelles zones sont explorées et quelles sont les directions restant à explorer. donc égal au mieux au temps d'exploration avec un robot divisé par n. En effet, le gain d'information par l'utilisation de n robots

Acknowledgements

The PhD work presented in this thesis has been realized in Ecole Centrale de Lille, at "Laboratoire d'Automatique, Génie Informatique et Signal" (LAGIS), from September 2011 to December 2014. I am extremely grateful to China Scholarship Council (CSC) who financed this work.

Abbreviations

AMR -Autonomous Mobile Robot

AUV -Autonomous Underwater Vehicle

GPS -Global Positionning System

SLAM -Simultaneous Localisation And Mapping

Conclusion of the map reconstruction

In this chapter, we use a least-mean square method for the map reconstruction in order to reduce the errors of the sensor data. The mathematical deduction is quite accurate, and the implementation can be carried out in almost every platform. [START_REF] Sacerdoti | A structure for plans and behavior[END_REF]. And then many research work related to the behavior decomposition has been done, as the Hierarchical Transition Network by [START_REF] Belker | Learning to optimize mobile robot navigation based on htn plans[END_REF]. A fundamental competency for mobile robot navigation is the ability to plan and execute collision free motion through unknown environments in real time [START_REF] Lee | Mobile robot navigation with reactive free space estimation[END_REF]. The existing behavior coordination system can be divided into two groups: behavior arbitration method by [START_REF] Simmons | Structured control for autonomous robots[END_REF] and

Target Going (TG) behavior

This behavior is interested in the 2nd nearest subgoal and the current robot orientation, and is used for path optimization. The TG divergence is calculated by the absolute angle difference between the robots previous heading direction and the direction suggested by the TG behavior. We also define the TG membership function in Table 5.2:

Wall Following (WF) behavior

This behavior rotates the robot to a direction, perpendicular to the line connecting both the robot and obstacle. Here we use the intelligent wall following direction de-Equation 5.4, which is the criterion for the determination of the deadlock or the exit (see the description in the following Algorithm 3).

(5.5)

2 is equal to zero, and if not, then β ′ 5 is equal to zero as explained in the Figure 5.1.

conclusion of the robot navigation

In this chapter, we proposed a five-behavior fuzzy control based navigation algorithm, which use behavior coordination and command fusion to determine the mobile robot's action according to the sensors' data during the navigation task. We will see the simulation results in the experimentation chapter.

Simulation model in Player/Stage

In this part, we will introduce you the simulation model of the robot Robotino R . We have thus the advantages for the simulation, compared to the real Robotino R .

1. Augment the perception distance, then the robot in simulation has more reaction time to fulfil the dynamic avoidance in the multi-robot cooperative exploration; are more data in the same area, the robot may be confused for the edges. That is the problem dealing with the reconstruction confusion with the low level map (local map)

and the high level (global map). We have the global reconstruction map in Figure 6.9(a), from which we can see the result is relatively good with respect to the original map, except some mapping confusions in the upper left area due to repeated visits. The darker area represents the 6.5 Performance analysis Figure 6.17: Test for the successful navigation in the future.