Cyril Robin

Simon Lacroix

Taxonomy on Multi-robot Target Detection and Tracking

Target detection and tracking encompasses a variety of problems such as coverage, search, patrolling, observing, pursuit-evasion, etc. These problems are studied by several communities, that tackle them using diverse formulations, hypotheses and approaches. This variety and the fact that target related robotics problems are pertinent for a large spectrum of applications has motivated a large amount of contributions, which have mostly been surveyed according to one or another viewpoint. In this article, our objective is to go beyond the frontiers of specific communities and specific problems, and to enlarge the scope of prior surveys. We define classes of missions and problems, and relate the results from various communities according to a unifying taxonomy, and propose a transverse analysis of the approaches, models and lacks that are common through all the tackled problems, and isolate the current main research directions.

I. MOTIVATIONS

Detecting, localizing or following targets is at the core of numerous robotic applications, in both adversarial and cooperative contexts. Much work has been devoted in various research communities to such problems, which are often referred to as "pursuit-evasion" problems. This very evocative term actually encompasses a variety of scenarios that pertain either to monoor multi-robot contexts, considering either a single or multiple targets, and whose objective is either to detect, to capture or to track them. On the other hand, other similar problems are named differently and make use of specific vocabulary, e.g., surveillance, search or tracking. This is partly explained by the different application contexts considered (industrial, civilian or military), and by the fact that different communities tackle them with different standpoints (e.g., sensor data processing, symbolic or geometric task planning, task allocation, game theory, etc.)

The variety of target related robotics problems and proposed approaches has motivated a vast amount of contributions, and several surveys focused on specific problems are available [START_REF] Urrutia | Art gallery and illumination problems[END_REF], [START_REF] Alspach | Searching and sweeping graphs: a brief survey[END_REF], [START_REF] Chung | Search and pursuit-evasion in mobile robotics[END_REF], [START_REF] Rocha | A survey on multi-robot patrolling algorithms[END_REF], [START_REF] Nahin | Chases and Escapes: The Mathematics of Pursuit and Evasion (New in Paper)[END_REF], [START_REF] Stone | [END_REF]. In this article, our objective is to go beyond the frontiers of specific communities and specific problems, and to enlarge the scope of prior surveys. Target detection and target tracking, the two broad classes of scenarios related to targets, have a priori little to do one with another (and similarly the approaches to solve them), and are often executed in sequence. But in actual applications, these scenarios must be achieved by the same robots, and are sometimes tackled simultaneously: hence we believe it is relevant to analyse them together. This article introduces a coarse taxonomy and the associated vocabulary of the various robotics missions related to targets (Section II), so as to explicit how the researches carried on in different communities relate. It transversely analyses the approaches and models that are common through the various work related to the tackled problems (Section III), and it finally highlights open areas of research (Section IV). Note that due to a lack of space, this paper does not review the main work in each defined area -the interested reader may refer to [START_REF] Robin | Multi-robot Target Detection and Tracking: Taxonomy and Survey[END_REF].

II. TAXONOMY

Typical robotics target related scenarios are automated surveillance of secured areas, frontier patrolling, secured area clearing, target tracking or chasing, inter alia. In all these scenarios, the environment is mostly known, and exploring the environment is not considered. However, the availability of a prior map is not mandatory (although it could be a side effect of another condition, for instance in coverage), and the map criterion does not appear in our taxonomy. Besides, the targets may either be mobile or fixed, but we focus in this article on mobile targets, which are more challenging.

The taxonomy is summarized in Figure 1. It is organized as a tree, in which each branching is defined by a specific criterion. Each leaf refers to a class of problems, including possible variations in the formulation or assumptions. It defines coherent notations and definitions of the problems used throughout the article. Note that even though we try to comply with widely accepted vocabulary, there may be conflicts with definitions used by some authors. The names and definitions of the various problems are indeed not standardised, especially when considered in different communities: the same word may refer to different problems in the literature, and so we stick to the taxonomy vocabulary throughout the paper.

The first branching criterion of the taxonomy relates to prior knowledge on the target position, and yields the two main classes of problems, that often occur in sequence: detecting targets on the one hand, and tracking detected targets on the other hand.

A. Target Detection

Target detection problems consist in finding (detecting) a target in a given environment. They may concern one or several targets and may be tackled with one or multiple sensors, either by actively sweeping the environment with mobile sensors, or by monitoring signals emitted from fixed static sensors.

We refer to this later class of problems as coverage: they mainly involve sensor positioning strategies, which often come to partition the environment and accordingly distribute sensors within this environment. When mobile sensors are exploited, the problem is strongly related to path planning, and we refer to it as mobile search. Such problems can be addressed either locally or globally. Depending on the models, the assumptions and the approaches, some authors try to provide worst-case guarantees for the performance (capture), whereas some provide probabilistic guarantees (probabilistic search) and others do not provide any guarantee at all (hunting). The search may have a cyclic aspect (patrolling), although this presents no interest for capture or hunting. Note that for each of these problems, a variant that consists in "surrounding" the target in order to prevent its evasion is sometimes considered, instead of merely watching it, or catching it. a) Coverage: In coverage, the environment is necessarily known and the objective is to optimally position a set of fixed sensors. The traditional form of coverage is the famous Art Gallery problem which has been well studied and for which numerous results have been obtained [START_REF] Urrutia | Art gallery and illumination problems[END_REF]. Variants of coverage include mobile sensors, but the proposed solutions always focus on the sensor placement aspect (where to set the sensors?), and not on path planning (how to reach the selected positions?). b) Capture: In the capture problem, optimality and completeness are essential characteristics. The goal is to clear a given known area while providing a worst-case guarantee, meaning that if a target is inside the considered area, it will be found, no matter what. There is no prior knowledge or assumption on the target location, targets may even have "super abilities" (like infinite speed), and pursuers try to surround them. Capture is often referred to as a pursuit-evasion, but also as search and secure, or as the cops and robbers game, mostly when the solution rely on graph clearing [START_REF] Chung | Search and pursuit-evasion in mobile robotics[END_REF]. Work on this subject usually has strong mathematical foundations, and are developed following two main approaches [START_REF] Alspach | Searching and sweeping graphs: a brief survey[END_REF], [START_REF] Chung | Search and pursuit-evasion in mobile robotics[END_REF]: stating the problem as a graph clearing one, or as a purely geometric one, within 2D polygonal environments. Often, the objective is to assess the minimal number of pursuers required to provide a worst-case guarantee. c) Probabilistic Search: The main difference between capture and probabilistic search is the absence of worst-case guarantee in the latter, in which probabilities of detection are assessed [START_REF] Stone | [END_REF]. The reason is mainly a lack of resources (robots or time) to tackle the worst-case problem, but it can also be a compromise between efficiency and the probability of occurrence of particularly difficult situations.

Probabilistic Search exploits probability distributions over the model of the environment (of the target presence, of the target visibility, etc.) Most authors try to provide bounds on the probability of detecting/catching the target. The target model may either be adversarial or not, the latter being usually easier to deal with because of its lower algorithmic complexity. The non-adversarial target model is widely used in search and rescue scenarios, for which emergency and time constraints usually prevent performing an exhaustive search and impose priorities -which is well handled by probabilistic models. d) Patrolling: When the mobile search is cyclic, it is denoted by patrolling. Patrolling may be seen as a cyclic version of probabilistic search, as it involves analyses of statistical performance over time, and especially the time elapsed between two visits to the same point. It is a rather recent area of research, whose interest has risen over the last decade [START_REF] Rocha | A survey on multi-robot patrolling algorithms[END_REF]. The continuous formulation is related to the watchman route problem (WRP), which consists in finding the shortest closed path in a given polygon such that all points of this polygon are visible from at least one point in the path. e) Hunting: There are finally some cases where no guarantee at all is provided for detection or capture of the target, which we refer to as hunting. The absence of guarantee comes from the lack of resources (robots, time) or information -in the absence of which no useful probability models for the target location can be exploited, for instance. Hunting is often considered within a multi-robot context.

B. Target Tracking

The second major class of problems, target tracking, corresponds to the tasks that arise when one or several targets have been detected or assigned -often following the success of target detection tasks. Here, coping with a target may imply keeping it in sight, to provide information on it (mainly to localise it over time, but identifying it can also be an objective), or to catch it. In all cases tracker robots need to stay "close" to the targets, the required distance being zero when it comes to catch the targets. Coping with a single target may require one or more robots, depending on the context. It is for instance preferable to have multiple vantage points on each target to refine their locations. We refer to this latter class of problems as target localization problems. We also distinguish the one vs. one problems (following) from the multi-robot multi-target problems (observation).

f) Target Localization: The target localization problem consists in tracking a target with several robots in order to improve knowledge about the target, in particular the precision of its estimated position. It is most often a multi-robot problem, in which case solutions involve selecting different points of view to maximize the information gain. Of course, data fusion, cooperation, communication and multi-robot localization are issues to be considered. Several targets may be involved, and several observation points of view on each target are often required. Multi-robot target localization has naturally gained interest with the development of research on multirobot systems.

g) Following: The class of following problems is the traditional form of pursuit-evasion. [START_REF] Nahin | Chases and Escapes: The Mathematics of Pursuit and Evasion (New in Paper)[END_REF] present a survey and the history of the related work. Early work pertained to naval conflict scenarios, and the traditional pursuit problem is also known as Lion and Man. In the original version, a single purser (the Lion) is chasing a single evader (the Man) with the same speed. Many different versions of the problem have been defined, with different speeds, environment models, visibility conditions, etc. Following embraces all these variations, which are tracking problems involving only one pursuer and one evader.

h) Observation:

The observation problem is stated as follows: given several robots and several (moving) targets, how to control the robots in order to simultaneously observe all the targets, and if not possible, how to minimize the time during which any target is not observed by at least one of the robots. This problem has been rigorously specified by Parker in 1997 [START_REF] Parker | Cooperative Multi-Robot Observation[END_REF], who refers to it as the CMOMMT problem (Cooperative Multi-robot Observation of Multiple Moving Targets). One of the main challenges is to correctly allocate targets to robots and to decide how and when the observers should trade targets.

III. COMMON MODELS AND APPROACHES

Through the whole variety of problems gathered by our taxonomy, there are many comparable aspects, be it similar approaches, models, assumptions, validation processes, or flaws. Here, we try to highlight the ones which we consider important, namely the world and agents models, the main approaches, the current trends, and validation processes. This part relates to both the left and the right parts of our taxonomy, as similar platforms, formalisms and models are common to both the detection and tracking problems. In actual scenarios, the tracking may indeed directly follow the detection phase, or be performed in parallel: in a multi-robot context, once a target is detected, some robots track it while the others continue the detection task. Note that there is a large variety of models and approaches, but at the end results and the validation processes assess their validity a posteriori: we also discuss these validation processes.

A. Models

Models that represent the environment and the agents (the robots and the targets) are at the core of the decision process, and are required whichever the chosen approach. The combination of environment and agents models yields the ability to predict the outcome of the agents actions, i.e., what the agents are able to do and the expected consequences of the possible actions. Most of the encountered models are rather simple, and in our opinion often too simple. They provide a limited expressiveness, and if they ease the way to solve the problem (somehow by reducing its complexity), they are a too coarse abstraction of the reality, hardening the integration issues, and thus minimizing the realistic validation of the proposed approaches.

1) The environment: a) Beyond 2D models: Most of the authors use a 2D single-layer representation of the world, be it a grid [START_REF] Yu | Probabilistic path planning for cooperative target tracking using aerial and ground vehicles[END_REF], [START_REF] Flushing | GIS-based Mission Support System for Wilderness Search and Rescue with Heterogeneous Agents[END_REF], [START_REF] Robin | Failure anticipation in pursuit-evasion[END_REF] or more continuous models (using tessellation [START_REF] Fazli | Fault-Tolerant Multi-Robot Area Coverage with Limited Visibility[END_REF], [START_REF] Soltero | Decentralized path planning for coverage tasks using gradient descent adaptive control[END_REF], [START_REF] Bhattacharya | Motion Strategies for Surveillance[END_REF], [START_REF] Murrieta-Cid | Surveillance Strategies for a Pursuer with Finite Sensor Range[END_REF] or not [START_REF] Murrieta-Cid | A reactive motion planner to maintain visibility of unpredictable targets[END_REF], [START_REF] Bandyopadhyay | Stealth Tracking of an Unpredictable Target among Obstacles[END_REF]). This implies that obstacles to motions and observations are the same. Hence, realistic situations like areas that are obstacles for AGVs (Autonomous Ground Vehicles) but not for their sensors (e.g., ground holes or water ponds), or where AAVs (Autonomous Aerial Vehicles) can fly over but not observe under (e.g., undergrowth) can not be represented.

Along with the growing computation power, more complex models (2.5D [START_REF] Kolling | Pursuit-Evasion in 2.5D based on Team-Visibility[END_REF], 3D [START_REF] Bandyopadhyay | Motion planning for 3-d target tracking among obstacles[END_REF], or multi-layered models [START_REF] Flushing | GIS-based Mission Support System for Wilderness Search and Rescue with Heterogeneous Agents[END_REF], [START_REF] Robin | Failure anticipation in pursuit-evasion[END_REF]) have recently been proposed. Such models embody more information and are hence more realistic, allowing finer strategies. For instance, one is able to take advantage of higher vantage points to observe a larger viewshed [START_REF] Kolling | Pursuit-Evasion in 2.5D based on Team-Visibility[END_REF] or to distinguish areas that block motions from areas that block observations [START_REF] Robin | Failure anticipation in pursuit-evasion[END_REF].

Besides these more realistic models, some authors exploit highly abstract representations, as in [START_REF] Alexander | Pursuit and evasion in nonconvex domains of arbitrary dimensions[END_REF]. This often eases the finding of solutions, and allows to rigorously assess algorithmic complexity. However, the loss of information induced by the abstraction may impede the validity of the solutions when confronted to the real world.

b) Discrete Worlds: The discrete grid or tessellation models are widely used, as they straightforwardly define graphs, upon which algorithms exploiting graph theory can be built [START_REF] Parsons | Pursuit-evasion in a graph[END_REF], [START_REF] Murrieta-Cid | Surveillance Strategies for a Pursuer with Finite Sensor Range[END_REF]. However, it is difficult to transform a metrical model of the world into a meaningful topological model [START_REF] Moors | A probabilistic approach to coordinated multi-robot indoor surveillance[END_REF], and only few authors provide means to do so [START_REF] Hollinger | GSST: anytime guaranteed search[END_REF]: some directly assume that the graph is available (e.g., handmade [START_REF] Hollinger | Efficient Multirobot Search for a Moving Target[END_REF]) while others use "random" sampling as a compromise between the continuous world and a discrete model.

Discretization is also a workaround for the computational complexity of continuous numerical models, even when the algorithms are theoretically valid with continuous models [START_REF] Soltero | Decentralized path planning for coverage tasks using gradient descent adaptive control[END_REF]. As stated by Bhattacharya "While discretization invariably implies a certain level of approximation and deviation from the original metric space, in order to make any continuous problem computationally feasible it is an indispensable trade-off." [START_REF] Bhattacharya | Multi-robot coverage and exploration on Riemannian manifolds with boundaries[END_REF]. As a matter of fact, continuous models are mostly used for local reactive control or greedy decisions [START_REF] Murrieta-Cid | A reactive motion planner to maintain visibility of unpredictable targets[END_REF], [START_REF] Bandyopadhyay | Stealth Tracking of an Unpredictable Target among Obstacles[END_REF]. On the contrary, discrete models are often used for mathematical proofs in abstract representations [START_REF] Parsons | Pursuit-evasion in a graph[END_REF], [START_REF] Alexander | Pursuit and evasion in nonconvex domains of arbitrary dimensions[END_REF]. The assumption of continuity is appealing and eases guarantees and proofs, but it raises an issue: indeed there are discontinuities in the real world that impact both motions and visibility and that continuous abstract models may not handle [START_REF] Israel | Search for a mobile target by ground vehicle on a topographic terrain[END_REF]. c) Space-time manifold: Apart from the space representation, time representation is crucial, and can actually hardly be decorrelated from the space representation, especially in discretized models. Note that discrete time can be used with continuous space models [START_REF] Bandyopadhyay | Stealth Tracking of an Unpredictable Target among Obstacles[END_REF], but continuous time representations are also used [START_REF] Alexander | Pursuit and evasion in nonconvex domains of arbitrary dimensions[END_REF]. Time discretization is typically used to define a countable number of states, and as highlighted by LaValle [START_REF] Lavalle | Motion Strategies for Maintaining Visibility of a Moving Target[END_REF], "the next state x k+1 will usually not lie exactly at a discretized value" (be it temporal or spatial). This means that discretization will probably reduce the coherence between the real state and the modeled state, and one has to ensure that the algorithms are robust to such incoherences. However, to ease the mathematical proofs, the "one space unit travelled per one time unit" hypothesis is convenient, and often does not lead to any loss of generality [START_REF] Soltero | Decentralized path planning for coverage tasks using gradient descent adaptive control[END_REF]. But it may impact the quality of the resulting solutions. As a matter of fact, the relation between space and time is really sensitive when accurate coordination is required or assumed, or when a robot cannot "wait" for the others, for instance when pursuing a target [START_REF] Robin | Failure anticipation in pursuit-evasion[END_REF], [START_REF] Strom | Online probabilistic pursuit of adversarial evaders[END_REF]. In both cases, experiments will validate or not the assumptions about time, and therefore, one has to take a great care about how this validation step is led.

d) Environmental constraints:

The environment of the missions can challenge the algorithms by compromising some assumptions or by constraining or even preventing some actions. For instance, some algorithms take for granted that one can mark the environment in a way or an other [START_REF] Chu | Swarm approaches for the patrolling problem, information propagation vs. pheromone evaporation[END_REF], [START_REF] Glad | Influence of Different Execution Models on Patrolling Ant Behaviors: from Agents to Robots[END_REF]. In this case, one has to pay attention to the feasibility of such markings -and to their cost. The recent advent of RFIDs (Radio-Frequency Identification) offers an interesting technical solution to mark the environment [START_REF] Mamei | Spreading pheromones in everyday environments through RFID technology[END_REF], but they can hardly be used in every context -a difficulty overlooked by most simulators where marking can be easily emulated. As asserted by Glad et al., "Robotic systems come with their own hypotheses that are more restrictive than in simulation." Here, again, only realistic experiments should validate the approach. For instance, the RFID detection distance range can largely impact the performances [START_REF] Pugh | Inspiring and Modeling Multi-Robot Search with Particle Swarm Optimization[END_REF].

While most reviewed work tackle simple environments, i.e., 2D grounds or volumes with only no fly zones for AAVs, some authors tackle more challenging environments like water, which strongly impact the sensing, communication and motion abilities [START_REF] Ehlers | Multi-Robot Teamwork in Multistatic Sonar[END_REF].

2) The agents: The term "agent" stands here for the robots and the targets. For the scenarios considered in this article, the considered actions are the motions, the observations and the communications. A model of each of these capacities is required, and its choice is obviously strongly related to the choice of the environment model, as both are combined to assess the outcome of the actions. a) Motion model: The model accuracy of the motion capacities, and especially the kinematics and dynamic constraints, varies a lot. The more the world model is abstract, the more the motion model is. With graphs, the motion model only describes if a given node (area) can be reached by the agent or not, possibly with a cost (e.g., distance, time, energy...). It is largely assumed that this cost estimate is good, and how the agent should or will effectively move is not of the concern of the motion model in use. This assumption may be presumptuous, and only validation processes can assess its realism. Nowadays, accurate pattern-based motion models are used for (winged-)AAVs, and more rarely for AGVs [START_REF] Yu | Probabilistic path planning for cooperative target tracking using aerial and ground vehicles[END_REF]. Information on the environment geometry may also help to refine or constrain the agents motions [START_REF] Flushing | GIS-based Mission Support System for Wilderness Search and Rescue with Heterogeneous Agents[END_REF]. However, a precise or realistic motion model is not always required, especially for the target. For instance, assuming an infinite speed for the target yields the definition of conservative worst-caseguaranteed strategies [START_REF] Chung | Search and pursuit-evasion in mobile robotics[END_REF].

b) Sensor model: The sensor models are mainly used for the robots, except in the case of stealth tracking [START_REF] Bandyopadhyay | Stealth Tracking of an Unpredictable Target among Obstacles[END_REF] or when the authors also consider the evader point of view [START_REF] Markov | A cooperative distributed approach to target motion control in multirobot observation of multiple targets[END_REF]. Sensor models may be very basic: most often only distance matters. However, some authors explicitly consider the field of view and visibility constraints [START_REF] Murrieta-Cid | A reactive motion planner to maintain visibility of unpredictable targets[END_REF], [START_REF] Bhattacharya | Motion Strategies for Surveillance[END_REF], [START_REF] Vo | Visibility-Based Strategies for Tracking and Searching Unpredictable Coherent Targets Among Known Obstacles[END_REF], with an orientation, a maximum angle, and a distance. Finer models may also represent 2.5D or 3D information [START_REF] Kolling | Pursuit-Evasion in 2.5D based on Team-Visibility[END_REF], [START_REF] Bandyopadhyay | Motion planning for 3-d target tracking among obstacles[END_REF], or a multi-layered world [START_REF] Robin | Failure anticipation in pursuit-evasion[END_REF]. Most considered sensors are lightbased sensors, be it cameras or LIDARs and so most of visibility constraints are line-of-sight. c) Communication model: Although communication may be intuitively considered as very similar to sensing (when there is a visibility link, one may reasonably assume that there is a communication link), most of the authors use the full connectivity assumption. However convenient this assumption is, its realism is questionable and may strongly impact the efficiency of the approach. Indeed, accurate communication models are complex and expensive [START_REF] Mosteo | Multi-Robot Task Allocation for Service Robotics : from Unlimited to Limited Communication Range[END_REF]. This explains why some authors build their approaches upon the communication requirements and issues [START_REF] Hollinger | Multirobot Coordination With Periodic Connectivity: Theory and Experiments[END_REF], or specifically study its impact [START_REF] Pugh | Inspiring and Modeling Multi-Robot Search with Particle Swarm Optimization[END_REF]. d) Expected behaviour: Apart from the models of actions (motion, sensing, communicating), one may want to model the expected behaviour of the target or the other teammates. The target model is often a probabilistic motion model, be it random walk [START_REF] Strom | Online probabilistic pursuit of adversarial evaders[END_REF], [START_REF] Parker | Distributed Algorithms for Multi-Robot Observation of Multiple Moving Targets[END_REF], [START_REF] Hollinger | Multirobot Coordination With Periodic Connectivity: Theory and Experiments[END_REF] or more elaborate Bayesian or Markovian models [START_REF] Yu | Probabilistic path planning for cooperative target tracking using aerial and ground vehicles[END_REF], [START_REF] Hollinger | Efficient Multirobot Search for a Moving Target[END_REF], [START_REF] Bandyopadhyay | Motion Planning for People Tracking in Uncertain and Dynamic Environments[END_REF]. Predicting the target's behaviour and motion allows elaborating more sophisticated or less conservative strategies. Indeed, in the adversarial case, the target behaviour can be more accurately modeled with the game theory [START_REF] Murrieta-Cid | Surveillance Strategies for a Pursuer with Finite Sensor Range[END_REF], [START_REF] Murrieta-Cid | A complexity result for the pursuit-evasion game of maintaining visibility of a moving evader[END_REF], [START_REF] Vieira | Scalable and practical pursuit-evasion with networked robots[END_REF]. Various target models are also used as a metric to compare algorithms [START_REF] Sak | Probabilistic multiagent patrolling[END_REF]. Indeed, the model of the target's behaviour does matter, as finer strategies are possible when the model is correct, but they can turn to be counter-productive when the model is not adequate [START_REF] Yu | Probabilistic path planning for cooperative target tracking using aerial and ground vehicles[END_REF].

Modeling the teammates behaviour is also relevant: the main motivation is to reduce the need for communication, as implicit coordination built on the prediction of others motions can be achieved [START_REF] Grocholsky | Information Driven Coordinated Air-Ground Proactive Sensing[END_REF]. The models may be hard coded or learned [START_REF] Xu | Decentralised Coordination of Mobile Robots for Target Tracking with Learnt Utility Models[END_REF].

B. Approaches

Robotics being at the crossroads of numerous disciplines, the state of the art contains a large variety of approaches tackling similar -if not identical -problems. Among the numerous criteria that define an approach, we distinguish (a) the theoretical and analytical results from the experimental results, (b) the centralized systems from the decentralized ones, (c) the cooperative patterns from the "selfish" ones, considering both implicit and explicit cooperation, (d) the consideration of uncertainties, especially through probabilistic models, and (e) the planning processes from the optimization processes. Note that the selection of an approach obviously comes with the definition of the chosen models. a) Theory vs. Practice: Among every problem defined by our taxonomy, one can distinguish two trends: a large part of the contributions are focused on experimental results [START_REF] Kalra | Hoplites: A market-based framework for planned tight coordination in multirobot teams[END_REF], [START_REF] Bandyopadhyay | Stealth Tracking of an Unpredictable Target among Obstacles[END_REF], [START_REF] Strom | Online probabilistic pursuit of adversarial evaders[END_REF], while others provide theoretical results [START_REF] Lapaugh | Recontamination does not help[END_REF], [START_REF] Eaton | Optimal pursuit strategies in discrete-state probabilistic systems[END_REF]. This is a coarse partition, and some papers propose both kinds of results [START_REF] Hollinger | Multirobot Coordination With Periodic Connectivity: Theory and Experiments[END_REF], however we believe that this distinction does matter.

Theoretical results are essential as they light the way to efficient and practical solutions. Numerous theoretical results usefully state the complexity of a given class of problems [START_REF] Hollinger | Multirobot Coordination With Periodic Connectivity: Theory and Experiments[END_REF], [START_REF] Murrieta-Cid | A complexity result for the pursuit-evasion game of maintaining visibility of a moving evader[END_REF], [START_REF] Kolling | Pursuit-Evasion on Trees by Robot Teams[END_REF], [START_REF] Hollinger | Efficient Multirobot Search for a Moving Target[END_REF], [START_REF] Isler | Target Tracking with Distributed Sensors: The Focus of Attention Problem[END_REF]: in case of NP-difficult problems, one should probably focus on off-line computation, or suboptimal online solutions. Some papers also give hints on the solutions: for instance, LaPaugh proved that "recontamination" does not help for solving the capture problem [START_REF] Lapaugh | Recontamination does not help[END_REF].

Besides theoretical milestones, most analytical approaches are not applicable in real conditions considering the computational constraints. As stated by Parker about observation: "analytical techniques have been developed for solving this problem in complex geometrical environments. However, these previous approaches are very computationally expensiveat least exponential in the number of robots -and cannot be implemented on robots operating in real-time" [START_REF] Parker | Distributed Algorithms for Multi-Robot Observation of Multiple Moving Targets[END_REF]. This statement endorses experimental results, i.e., "solutions that works for real".

Although the approaches focusing on integration and experiments can be criticized, we stand for the importance of such work, that addresses what matters in the end: solutions that effectively solve real world problems. These approaches often rely on local considerations, and result in efficient and sometimes elegant systems [START_REF] Bandyopadhyay | Stealth Tracking of an Unpredictable Target among Obstacles[END_REF], [START_REF] Murrieta-Cid | A reactive motion planner to maintain visibility of unpredictable targets[END_REF], [START_REF] Grocholsky | Information Driven Coordinated Air-Ground Proactive Sensing[END_REF]. The associated algorithms are most of the time supported by validation processes, on which we comment further below.

b) Centralized and decentralized systems:

The target related problems considered in the literature are mainly multirobot problems, hence the question of centralized and decentralized systems arises. Many centralized algorithms have been proposed over the years: they are more convenient to provide global optimality. However, they face strong constraints in the real world: they often require full connectivity, are sensitive to dynamic environments, especially when solutions are computed off-line, and most of them hardly scale up, in particular with the number of robots [START_REF] Moors | A probabilistic approach to coordinated multi-robot indoor surveillance[END_REF].

Most target related problems are at least NP-hard, and one can face computational issues with centralized algorithms. Centralized approaches usually provide optimal or near-optimal solutions, where the computational requirements are not the issues. Otherwise, one should instead focus on the benefits brought by decentralized systems [START_REF] Hollinger | Multirobot Coordination With Periodic Connectivity: Theory and Experiments[END_REF]. The latter are more robust, generally scale well with the number of robots, and are more adapted to real world constraints (dynamic environment, communication constraints, etc.), easing the integration process [START_REF] Jung | Tracking Targets Using Multiple Robots: The Effect of Environment Occlusion[END_REF], [START_REF] Kalra | Hoplites: A market-based framework for planned tight coordination in multirobot teams[END_REF]. Decentralized approaches generally provide suboptimal solutions with only local optimality [START_REF] Chu | Swarm approaches for the patrolling problem, information propagation vs. pheromone evaporation[END_REF]. Still, they provide interesting performances, especially under realistic constraints, and constitute the current main research trend [START_REF] Parker | Cooperative Multi-Robot Observation[END_REF], [START_REF] Chu | Swarm approaches for the patrolling problem, information propagation vs. pheromone evaporation[END_REF].

c) The need for cooperation: Most of the surveyed problems require several robots to be solved adequately, and the quality of the solutions is generally improved as a team of robots allows more flexibility in the strategies. But there are many ways to organize robot teams. The robots may cooperate or simply perform their tasks independently, following a prior task allocation. The latter case is well illustrated by both the cycle-and partition-based patrolling schemes [START_REF] Rocha | A survey on multi-robot patrolling algorithms[END_REF] whose main advantage is that they do not require any communication, avoiding the associated issues. Their drawback is their weaker robustness to robot failures or changes in the environment of the mission definition, as they cannot modify the team strategy globally.

Online cooperation helps to solve problems efficiently, and is even required for some problems which required tight coordination (capture), or dynamic adaptation to the incoming data such as target observation (observation, target localization, probabilistic search). The benefits of coordination are tightly related to the structure of the environment: highly structured worlds like office environment benefit less from a tight coordination than open environments [START_REF] Amigoni | How much worth is coordination of mobile robots for exploration in search and rescue?[END_REF].

The cooperation can either be implicit or explicit. The latter allows to finely control the resulting system, because every decision and action are discussed and broadcasted through the whole team (or at least the surroundings agents). However, there are issues with the communication load and the combinatorial complexity of the decision processes. Explicit cooperation is often made through task allocation, where the goal is to allocate a set of tasks between several agents to optimize various criteria. The large literature about task allocation is beyond the scope of this article, but it is worth noticing that the target detection problem has often been used to compare or benchmark allocation algorithms [START_REF] Cai | Multi-robot Cooperative Pursuit Based on Task Bundle Auctions[END_REF], [START_REF] Kalra | Hoplites: A market-based framework for planned tight coordination in multirobot teams[END_REF]. d) Uncertain and dynamic environments: Robots face many uncertainties: sensors are prone to a variety of errors and noise, the agents behaviour can hardly be predicted accurately as results of actions are affected by sources of uncertainty, communications fail, inter alia. Ignoring these uncertainties will likely result in a defective system when facing the real world. Two main strategies, which can be coupled, help to prevent this: taking into account uncertainties at the modeling level, and re-planning on-line when the gap between the modeled state and the real state is too large. Probabilistic models have gained interested over the past 20 years in all robotic problems, including the ones considered here. This is explained by the need to improve the models on which planning rely and by the advent of computing performances which allows to handle these models. The trendy probabilistic models are, in a rough chronological order, classical probabilities [START_REF] Moors | A probabilistic approach to coordinated multi-robot indoor surveillance[END_REF], [START_REF] Strom | Online probabilistic pursuit of adversarial evaders[END_REF], Bayesian models [START_REF] Yu | Probabilistic path planning for cooperative target tracking using aerial and ground vehicles[END_REF], [START_REF] Hollinger | Efficient Multirobot Search for a Moving Target[END_REF], [START_REF] Rocha | Distributed multi-robot patrol: A scalable and fault-tolerant framework[END_REF], Markovian models (MDP) [START_REF] Yu | Probabilistic path planning for cooperative target tracking using aerial and ground vehicles[END_REF], and partially observed Markovian models (POMDP) [START_REF] Ehlers | Multi-Robot Teamwork in Multistatic Sonar[END_REF], [START_REF] Hollinger | Efficient Multirobot Search for a Moving Target[END_REF], [START_REF] Bandyopadhyay | Motion Planning for People Tracking in Uncertain and Dynamic Environments[END_REF]. The latter are the more appealing but their extensive computational cost has prevented their application to large instances of problems [START_REF] Bandyopadhyay | Motion Planning for People Tracking in Uncertain and Dynamic Environments[END_REF]. Yet recent improvements on decentralized POMDP using separability conditions increase considerably the scalability [START_REF] Dibangoye | Exploiting separability in multiagent planning with continuous-state MDPs[END_REF]. Probabilistic solutions tend to yield finer strategies but at a significant computational cost, and most importantly they remain sensitive to the modeling phase. For instance, determining the best order of Markovian models has a strong influence on performance, but is not trivial to achieve [START_REF] Yu | Probabilistic path planning for cooperative target tracking using aerial and ground vehicles[END_REF].

Numerous problems tackled here are NP-hard at least, and the computational cost is heavy with probabilistic models, which explains why many solutions are computed off-line for problem instances of reasonable size [START_REF] Bhattacharya | Multi-robot coverage and exploration on Riemannian manifolds with boundaries[END_REF], [START_REF] Kolling | Pursuit-Evasion on Trees by Robot Teams[END_REF], [START_REF] Moors | A probabilistic approach to coordinated multi-robot indoor surveillance[END_REF]. However, the real world is rarely static, and one often has to react to external events (like target motion) without being able to precompute strategies for each and every possible state (the state space being globally intractable). In such cases, on-line computing is required. It brings robustness as one is able to recompute a valid solution on demand, when needed. However, on-line computing often comes with local considerations and thus suboptimality. This dilemma is well illustrated by the following problem, which has been shown to be entirely decidable, but is NP-complete [START_REF] Murrieta-Cid | A complexity result for the pursuit-evasion game of maintaining visibility of a moving evader[END_REF]. This is why the efficient state-of-the-art solutions consider only local information and are computed on-line [START_REF] Murrieta-Cid | A reactive motion planner to maintain visibility of unpredictable targets[END_REF], [START_REF] Bandyopadhyay | Motion Planning for People Tracking in Uncertain and Dynamic Environments[END_REF]. They are not optimal, but perform well, even in difficult environments. e) Planning vs. Optimization: The detection and tracking problems tackled here roughly come to determine who does what, when, and where. Most of them are formulated either as planning problems or as optimization problems. While the underlying problem remains the same, the formulation differs a lot, and so do the solutions and the results.

Planning comes to simulate actions and their effects in order to decide the actions sequence to perform to reach a given state. Several formalisms exist to implement planners, and the critical stage is the modeling of the action space, the action effects and the world states. One of the many available planners will provide a solution on the basis of these models.

In the formalism of optimization, an objective function to optimize with respects to some constraints is defined. More than the choice of a solver, the critical stages are the quantification of the world states and actions, and the definition of the objective function.

One key difference is that optimization requires numerical values, while traditional planning work with qualitative statements. Correctly evaluating these numerical values may be straightforward (for instance when trying to minimise the idleness in patrolling), but also more complex for others (like capture). Optimization is close to raw data and commands while traditional planning is semantically expressive and allows a higher level of abstraction in the models, easing hierarchical planning (e.g., the Hierarchical Task Networks (HTN) [START_REF] Erol | Hierarchical Task Network Planning: Formalization, Analysis, and Implementation[END_REF]). Besides, a hierarchical decomposition allows to mix both traditional planning (e.g., to roughly define tasks) and optimization (to refine the local solution). Recently, thanks to the increase of computing power, stochastic optimization has been proven to be efficient in solving complex problems.

C. Results and validation process

Apart from the theoretical results, most papers propose one or several algorithms and associated models to solve a given problem. The algorithms may come with theoretical guarantees (complexity, optimality), but experiments are required to assess their applicability. For instance, Eaton and Zadeh "solved" the following problem in 1962 [START_REF] Eaton | Optimal pursuit strategies in discrete-state probabilistic systems[END_REF], but the proposed solution is actually not applicable, and to the best of our knowledge not been implemented on-board any robot: it operates in an abstract space which is not correlated to the real worldor at least no one provided a valid transformation between the real world and this abstract space. There have been much work on following since then: several approaches have good performances, but are far from Zadeh's solution.

This illustrates that algorithms can only be validated with integration: only testing them on-board robots in an actual context will assess that they can cope with the challenging issues that are uncertainties, non-determinism, asynchronous systems, etc. Not considering these common issues yields solutions that are not robust.

Yet, most papers lack actual validation. Of course authors usually try to provide a fair description of their experimental protocol (parameters, number of runs, description of the simulator, etc.) but very few present realistic testing environments. The proposed approaches are mostly validated with ad hoc simulations [START_REF] Kolling | Pursuit-Evasion in 2.5D based on Team-Visibility[END_REF], [START_REF] Isler | Target Tracking with Distributed Sensors: The Focus of Attention Problem[END_REF], [START_REF] Chu | Swarm approaches for the patrolling problem, information propagation vs. pheromone evaporation[END_REF], [START_REF] Vo | Visibility-Based Strategies for Tracking and Searching Unpredictable Coherent Targets Among Known Obstacles[END_REF], i.e., simulations that neglect to represent most of real world characteristics. These simulated worlds are often discretized in time and space by construction, and there are no or few uncertainties. In this context, the initial assumptions and simplifications that lead to the algorithms are introduced into the simulators, which can hardly exhibit the solution flaws. Experiments on-board robots may present the same limits when they twist the reality to fit the models (e.g., restraining the agents movements to an artificial grid-based space [START_REF] Yu | Probabilistic path planning for cooperative target tracking using aerial and ground vehicles[END_REF], [START_REF] Rocha | Distributed multi-robot patrol: A scalable and fault-tolerant framework[END_REF] or artificially enforcing the time discretization [START_REF] Strom | Online probabilistic pursuit of adversarial evaders[END_REF]). This gap between models and reality have been spotted and studied by several authors [START_REF] Jung | Tracking Targets Using Multiple Robots: The Effect of Environment Occlusion[END_REF], [START_REF] Glad | Influence of Different Execution Models on Patrolling Ant Behaviors: from Agents to Robots[END_REF], [START_REF] Rocha | Distributed multi-robot patrol: A scalable and fault-tolerant framework[END_REF].

The validation process often present other flaws as the lack of state-of-the-art comparisons -algorithms are often "benchmarked" against trivial solutions like random walkers or brute-force solutions [START_REF] Isler | Target Tracking with Distributed Sensors: The Focus of Attention Problem[END_REF], [START_REF] Israel | Search for a mobile target by ground vehicle on a topographic terrain[END_REF] -, or the lack of "culture of statistics" -results are rarely statistically significant. Some of these flaws are understandable: thorough validations call for a lot of engineering, numerous tests and a logistic out of reach of most researchers. Also, fair comparisons are restrained by the variety of robots and testing environments between teams and labs.

Nevertheless, some authors provide nice state-of-the-art comparisons [START_REF] Chu | Swarm approaches for the patrolling problem, information propagation vs. pheromone evaporation[END_REF], [START_REF] Markov | A cooperative distributed approach to target motion control in multirobot observation of multiple targets[END_REF], [START_REF] Vo | Visibility-Based Strategies for Tracking and Searching Unpredictable Coherent Targets Among Known Obstacles[END_REF] and others have recently introduced better statistic analysis [START_REF] Sak | Probabilistic multiagent patrolling[END_REF], [START_REF] Amigoni | How much worth is coordination of mobile robots for exploration in search and rescue?[END_REF] with standard deviations and p-values (Wilcoxon test, Shapiro-Wilk test). Besides, in real practical experiments, it is hard to obtain enough significant results to make a statistical evaluation. Efforts have also been made to homogenize the testing platforms or to reuse past testing environments or simulators to fairly compare algorithms [START_REF] Strom | Online probabilistic pursuit of adversarial evaders[END_REF]. Challenges like RoboCup (including the Rescue Virtual Robot Competition [START_REF] Balakirsky | Usarsim: a robocup virtual urban search and rescue competition[END_REF], [START_REF] Jacoff | Test arenas and performance metrics for urban search and rescue robots[END_REF]) play an important role to validate and compare the systems in similar environments and setups. Some papers also present benchmarks of various algorithms and compare them through a set of metrics [START_REF] Jacoff | Test arenas and performance metrics for urban search and rescue robots[END_REF], [START_REF] Sak | Probabilistic multiagent patrolling[END_REF], which offer references in the considered domains. Making the code publicly available to foster experimental reproducibility and comparison is also a good practice for the validation process.

We believe that realistic simulations is a key to tackle the validation issues, as they provide common testing environments with realistic conditions, while easing statistically significant experiments. They also ease the transfer of the results across different approaches without performing all the experiments again. Realistic simulators differ from ad hoc ones in the way they model reality: the simulated space and time are continuous, and they generally embed a physical engine which properly models the robots' dynamics. Sensors are at least geometrically modeled (e.g., ray-tracing), and noise can be introduced. The development of realistic simulators requires engineering efforts, but fortunately one can now easily find off-the-shelf open source simulators (e.g., Morse [START_REF] Echeverria | Simulating Complex Robotic Scenarios with MORSE[END_REF], Gazebo [START_REF] Koenig | Design and use paradigms for gazebo, an open-source multi-robot simulator[END_REF], or USARSim [START_REF] Balakirsky | Usarsim: a robocup virtual urban search and rescue competition[END_REF]). These simulators come with various robot models and environments, and using a common framework and a modular architecture (like ROS [START_REF] Quigley | ROS: an open-source Robot Operating System[END_REF]) would even allow to compare running strategies against one another (e.g., a pursuer strategy against an evader strategy elaborated by another team). Validations that involve open source codes and scenarios defined in realistic simulators can provide both reproducible experiments and statistically significant results and comparisons, and would also pool efforts in the communities.

IV. CONCLUDING REMARKS

This paper presents a unifying taxonomy of the various target related robotics problems. It goes beyond the frontiers of specific communities and specific problems, and enlarges the scope of prior surveys. We have identified transverse models and approaches that are common through all the tackled problems. From this overall analysis, we believe the three most important points on which one should put efforts are the modelling, the development of decentralized approaches, and the validation.

The finest models that have been recently been proposed embrace probabilistic considerations, multi-layered world models and hierarchical representations. These improved models are now tractable thanks to advances in sensing and increasing computational power. They meet the need in robotics to fill, or at least to reduce the gap between models and reality. The first results given by these finer models are promising, and one may wish and expect that they become the new state-of-theart standard. Communications remain however to be modeled (and considered) in a more realistic manner to allow valid approaches.

Besides, considering that many analysed problems are NP-hard at least, we think suboptimal yet efficient real-time algorithms are the key to solve the real cases scenarios while handling online the dynamics changes. One should focus on decentralized algorithms that scales well. Anytime algorithms may be a bridge between efficiency and optimality [START_REF] Hollinger | GSST: anytime guaranteed search[END_REF], especially when time matters as in search and rescue scenarios. Yet, most of the time only experimental bounds on the performances are given, and we yearn to see more theoretical bounds on the suboptimality of the resulting solutions.

Finally, there should be drastic changes in the validation processes of the proposed approaches. Following Portugal and Rocha's statement, "it is the authors belief that research in this field should be more oriented towards effective solutions with applicability in the real world" [START_REF] Rocha | Distributed multi-robot patrol: A scalable and fault-tolerant framework[END_REF]. Yet too many papers provide unrealistic test conditions which prevent the evaluation of such applicability. True validation should involve reproducible results, with a statistical analysis and a fair comparison to other state-of-the-art solutions. Modular architectures combined to realistic simulators as a validation platform, and used with common datasets, can provide all the tools required by a solid validation process. This would also ease the development of new algorithms and the adoption of breakthroughs from related communities.

Fig. 1 .

 1 Fig.1. Proposed taxonomy of the target management problems. Branchings correspond to criteria, here denoted by questions, each red leaf correspond to a specific problem analysed in the following sections.

ACKNOWLEDGMENTS

This research is partially funded by the DGA.


Pierrick Koch
email: pierrick.koch@laas.frsimon.lacroix@laas.fr

Simon Lacroix

Managing environment models in multi-robot teams

Multi-robot cooperation in a dynamic environment implies that each involved robot is able to create, update and exchange environment models -which are essential to the autonomy of mobile robots. The ability to exchange data, in other words to communicate, rely on the fact that robots share a common language and common frames in space and time.

In this paper we present an open-source architecture 1 dedicated to build a collection of environment models of a dynamic environment with multiple robots. This work is lead with air-ground cooperation scenarios in mind, such as the ones considered within the Action project 2 . Managing models during the mission means defining methods and protocols to transmit and merge models built from different sources and on different robots, while respecting time and bandwidth constraints and being robust to unavoidable inconsistencies between the models. Our first work builds upon GDAL, a well known standard in geographic information systems (GIS). The architecture is currently able to build models with different robots in simulation. Current work aims at detecting and solving inconsistencies between the various models, and at porting the architecture on-board real robots.

I. INTRODUCTION

The basic scheme to define autonomous operations of a robot is to predict the consequences of their actions, so as to select the ones that lead to the achievement of the given task ("decision"). Predicting actions consequences requires the application of the action models onto models of the environment, so the availability of environment models is therefore a key component of robots autonomy. In a partially unknown and dynamic world, such models must be derived from sensor data acquired by the robots, that are aggregated into the models to be made available to the decision processes.

A. A variety of environment models

In general numerous actions can be performed by robots, such as grasping objects, moving form one position to the other, gathering knowledge on a given area... We consider here the case of robots operating in large scale outdoor environments, to achieve exploration, patrolling or monitoring tasks. In such cases, the main actions come down to motions, observations, and communicationse.g. with the remote operators control station or between robots.

The variety of actions to plan and execute calls for a variety of environments models: it is indeed illusory to define a model structure that encodes all the information required to assess the outcome of all the considered actions. Instead, we favor the development of layered representations, each representation being dedicated to plan a given action (figure 1):

• Models that represent the geometry of the terrain are required to plan motions. A digital elevation model (DEM) is required for local mobility, achieved by a short term path planner that must be fast and realtime; a more abstract description of the world is needed for higher level of decision, as the mission planner, demanding lower resolution and less time constraints (traversability model);

• 3D models are required to evaluate the communication and visibility of an area from a given position

• Utility models encode the interest of observing areas, e.g. the probability that it contains an event to monitor (orthoimage);

• Dedicated models are required for localization, exhibiting characteristic elements in the environment (landmarks)

• ... Note that one can distinguish three main types of data structure to encode information on the environment in the models:

• raster structures represent continuous information (surfaces, volumes) on a discretized representation, either 2D or 3D [START_REF] Hornung | OctoMap: An efficient probabilistic 3D mapping framework based on octrees[END_REF];

• vector structures represent a set of discrete information (landmarks, particular elements), that are localized with the associated uncertainties;

• topological structures represent spatial relations between areas or elements, representing accessibility (navigation graph), inter visibility...

B. Motivations

The basic procedure to build any environment model on the basis of the data provided by the environment sensors consists in acquiring the data and then to merge it in the data structure that defines the environment model. This calls for an essential requirement: the robot must be well localized, so that the environment model is spatially consistent. A lot of work has been dedicated in robotics to the localization problem, yielding in particular featurebased Simultaneous Localization And Mapping approaches (SLAM), in which landmarks are detected and memorized (which defines a specific layer of environment model -of vector type). Nevertheless, one can never guarantee that a robot is precisely localized in the long term, an naively integrating data in raster type data structures as the robot is not properly localized lead to inconsistent models, whose consistency can't be recovered afterwards (figure 2). Besides, the environment may contain dynamic elements, that are often hardly detected in the acquired data, and whose introduction in the environment models may lead to temporally inconsistent models, e.g. by memorizing in the same data structure the presence of elements that had different positions at different time instants (figure 3).

These two issues become even more important when considering teams of robots operating under communication constraints. To cooperate, the robots must have the ability to share tasks to achieve goals and missions. For this purpose, they need a common language, they need to share the information they have acquired on the environment, and they need to know where they are with respect to each other. The inter-robot communications being not permanent and subject to environmental perturbations, no central approach can be efficient: each robot must build and manage its own Fig. 3. A car "ghost" on a parking lot map: points corresponding to the car have been perceived while it was moving, and have been merged in different map cells (the "trace" of the car can be seen starting in the center of the model, an going up-left). Here the resulting map is not temporally consistent, as it encodes time varying information gathered at different time instants.

environment representations, and data exchanges between the robots must be optimized.

Managing environment models in a multi-robot context also brings up additional issues with localization (the robots being not precisely localized one with respect to the others) and the presence of dynamic elements, the robots sharing information that may have been acquired at very different time instants.

C. Outline

We propose in this article a mean to manage raster-like environment models so that localization errors and dynamic elements do not corrupt them: each robot raster models are maintained as a series of "tiles", that is to say local environment models, whose spatial and time consistency can be guaranteed. When the robots move and/or exchange information, the spatial and time inconsistencies are actively detected and managed.

Section II presents digital elevation models, a basic data structure on which we have worked so far. Section III depicts our approach to manage such models over long ranges of time and distances. Finally section IV recaps our on-going and future work.

II. DIGITAL ELEVATION MODELS

A Digital Elevation Model is a raster representation that encodes the terrain geometry as a function z = f (x, y), estimated over a regular Cartesian grid: it is a 2.5D heightmap where each cell value represents an elevation. It is a very common data structure to represent the terrain geometry, which is for instance used to assess the terrain traversability, either to generate local motions of the robot to reach a goal avoiding obstacles, or to plan long term itineraries. Such a model is incrementally built by merging point clouds from the robot depth sensors (e.g. stereovision or LIDAR) into the raster. This process must run in real-time to enable the robot to continuously plan its trajectory [START_REF] Kleiner | Real-time localization and elevation mapping within urban search and rescue scenarios: Field reports[END_REF]. Merging is basically done by averaging height of points perceived at each cell in the map.

However, dynamic elements of the environment create "ghosts" that should be removed from the model (see Figure 3), and the presence of vertical elements is poorly encoded by this merging process.

To solve this problem, we check whether a cell encodes a vertical area, an area that can be modelled as a surface, or an area that contains a dynamic object. This is made by computing a local (in space and time) DEM using the latest point could acquired, and by analyzing the variance σz on the elevation z of each cell. Depending on whether this variance exceeds a fixed threshold T or not and on the state of the corresponding cell in the current model, the state of the model cells is updated according to the merge logic shown This graph does not show the specific case where both current and new cells are considered flat, but their height differs: cells can not be merged in this case, and are hence assessed as "dynamic", the current cell value is kept in a cache, and replaced by the new one.

Following a cell state allows to assess whether it contains a dynamic element or not. Such information is also relevant for map registration, in order to filter landmarks, keeping the most stable areas for model matching. This is an important point from the lifelong autonomy perspective: the model must be re-usable and adaptable, even though drastic changes occur in the environment (e.g. on a parking lot).

III. ATLAAS

We propose to use tiles to keep track of past modelled areas, so as to cope with robot localisation and environment dynamics issues, and also to ease the exchange of information between robots. This is achieved by subdividing space into a set of smaller maps, allowing to cache data, dump and load them as the robot moves to different areas.

A. Pile of tiles

A tile is composed by different layers, for each cell, we are currently storing the lowest and highest elevations perceived, the elevation mean and variance, the number of points it contains, and the timestamp of the last update.

The current implementation merges incoming point clouds in a map of 9 tiles (3 * 3). When the robot moves out of the central tile, we dump the ones out of the map and load existing if any, using a simple hysteresis threshold. For local path planning purposes, we build maps of 0.1 meter resolution, of size 40 × 40m3 : this size is selected so as to make sure each tile is spatially consistent, making the hypothesis that the robot localization drift is not exceeding the cell resolution over the tile size (we are using inertialvisual SLAM [START_REF] Roussillon | Rt-slam: A generic and real-time visual slam implementation[END_REF]). Each tile being spatially and temporally consistent, and can be treated as an independent dataset containing its own relative frame and the transformation to the global frame. This hierarchy [START_REF] Beeson | Factoring the mapping problem: Mobile robot map-building in the hybrid spatial semantic hierarchy[END_REF] gives the possibility to reshape the overall model as the robot position is updatede.g. after a loop closure detection and correction by the SLAM algorithms. The overall model is generated by composed tiles, hence can quickly be re-arranged.

Space subdivision is also a key for sharing data between robots, sending chunk of information on demand, and registering them in another robot frame using remote synchronization methods.

B. Position referencing

In order to share models in a multi-robot scenario, it is first necessary to rely on standard for sharing frames in space and time. We are using the Universal Transverse Mercator (UTM) coordinate system to refer the position of each of the tiles, to be consistent with GPS position estimations -and with existing maps.

A tile is one file, a multi-layer GeoTiff/Float32 saved using the Geospatial Data Abstraction Library (GDAL). We built a generic library wrapping GDAL I/O using modern C++11 STL containers for in-memory storage 4 .

We keep an history of past tiles for the same area and use registration based on "stable" cells by computing the probability of the dynamic of each cell. It is when tiles overlap that we will handle the issues, by properly "merging" tiles, after having registered them (either by directly correlating them [START_REF] Pham | Absolute map-based localization for a planetary rover[END_REF], or matching landmark maps associated to the tiles).

Furthermore, keeping only one frame of reference is not sufficient. It is desirable to have a model that is still fixed as the robot moves forward and when loop closure appears. Hence the track of local reference in the global model should be kept and transformed to local chunk of data to prevent corruption. Doing so while sharing models means that tiles with reference to the global frame and information about its potential error (covariance) must be memorized.

The architecture as it is today provides the foundation of tiles referencing, containing valuable information on all cells... We could test in simulation using the MORSE simulator [START_REF] Echeverria | Simulating complex robotic scenarios with morse[END_REF].

IV. DISCUSSION

We have sketched the foundation of a new architecture for environment raster models management. It is still in early stage development, being ported on multi-robots at the time of writing. It has proved to work in simulation, most of the work is now focusing on better handling of the dynamics, and better handling of the localizations update from loopclosures.

So far we have restricted its use to 2.5D raster models, which is a good compromise of level of detail versus computational time for our needs. But other data structure could be exploited, such a 3D hierarchized raster structures. Interesting framework have been proposed by the community, as in "octomap" [START_REF] Hornung | OctoMap: An efficient probabilistic 3D mapping framework based on octrees[END_REF] where using ray-tracing allow to clear cells between the sensors and every points perceived. Such method allow to take advantage of the sensor's characteristics. However such algorithm require a considerable amount of computation and time which are not available in many autonomous robotic system.

Further, one could also define tiles whose spatial consistency can be updated over time, as in the HYMM [START_REF] Nieto | The hybrid metric maps (hymms): A novel map representation for denseslam[END_REF] framework. This would allow to propagate SLAM corrections into the raster models.

We are also considering dividing sensor data in two categories, the close points are considered valid and use directly for local path planner in the real-time loop, and points above a certain threshold needs some filtering and re-localization using matching algorithm [START_REF] Pomerleau | Comparing icp variants on real-world data sets[END_REF], such points are not critic in the locomotion process thus can be treated in a parallel thread.

Upcoming challenges are a fine time management, allowing to come back in a past state. Bandwidth constraint,

Fig. 1 .

 1 Fig. 1. Various semantic layers of environment representations. Each layer is dedicated to a given type of information, dedicated to a given decisional of functional process.

Fig. 2 .

 2 Fig. 2. Inaccurate localization leads to model corruption: here the DEM integrates data acquired while the robot was not always properly localized: building walls are represented twice at different positions.

Fig. 4 .

 4 Fig. 4. Merge logic of the local instantaneous cell of the DEM with the current DEM. A cell is assessed "vertical" if σz > T , "flat" otherwise.

Fig. 5 .

 5 Fig. 5. Current map of 3 * 3 tiles with their layers. You can see the tiles delimitation in red, and in green the central "hysteresis" robot area (best view with colors).

https://github.com/pierriko/atlaas#atlaas

http://action.onera.fr

For 9 tiles of

* 40m, the memory footprint is 33 MB

http://trac.laas.fr/git/gdalwrap how to efficiently exchange data. And guarantee the global consistency, by registering externally loaded models.