Distributed Cooperative Outdoor Multirobot Localization and Mapping

The subject of this article is a scheme for distributed outdoor localization of a team of robots and the use of the robot team for outdoor terrain mapping. Localization is accomplished via Extended Kalman Filtering (EKF). In the distributed EKF-based scheme for localization, heterogeneity of the available sensors is exploited in the absence or degradation of absolute sensors aboard the team members. The terrain mapping technique then utilizes localization information to facilitate the fusion of vision-based range information of environmental features with changes in elevation profile across the terrain. The result is a terrain matrix from which a metric map is then generated. The proposed algorithms are implemented using field data obtained from a team of robots traversing an uneven outdoor terrain.     

An Architecture for Distributed Environment Sensing with Application to Robotic Cliff Exploration

Future planetary exploration missions will use cooperative robots to explore and sample rough terrain. To succeed robots will need to cooperatively acquire and share data. Here a cooperative multi-agent sensing architecture is presented and applied to the mapping of a cliff surface. This algorithm efficiently repositions the systems' sensing agents using an information theoretic approach and fuses sensory information using physical models to yield a geometrically consistent environment map. This map is then distributed among the agents using an information based relevant data reduction scheme. Experimental results for cliff face mapping using the JPL Sample Return Rover (SRR) are presented. The method is shown to significantly improve mapping efficiency over conventional methods.     

Multirobot exploration for search and rescue missions: A report on map building in RoboCupRescue 2009

In the future, mobile robots may be able to assist rescue crews in search and rescue missions that take place in the dangerous environments that result from natural or man‐made disasters. In 2006, we launched a research project to develop mobile robots that can rapidly collect information in the initial stages of a disaster. One of our important objectives is three‐dimensional (3D) mapping, which can be a very useful tool for assisting rescue crews in strategizing rescue missions. To realize this 3D mapping, we identified five issues that we needed to address: (1) autonomous traversal of uneven terrain, (2) development of a system for the continuous acquisition of 3D data of the environment, (3) coverage path planning, (4) centralization of map data obtained by multiple robots, and (5) fusion of map data obtained by multiple robots. We solved each problem through our joint research. Each research institute in our group took charge of solving one of the above issues according to its area of expertise. We integrated these solutions to perform 3D mapping using our tracked vehicle, Kenaf. To validate our integrated autonomous 3D mapping system, we participated in RoboCupRescue 2009 and demonstrated our system using multiple robots on the RoboCupRescue field. In this paper, we introduce our mapping system and report the mapping results obtained at the RoboCupRescue event. © 2011 Wiley Periodicals, Inc.     

Coordinating heterogeneous teams of robots using temporal symbolic planning

The efficient coordination of a team of heterogeneous robots is an important requirement for exploration, rescue, and disaster recovery missions. In this paper, we present a novel approach to target assignment for heterogeneous teams of robots. It goes beyond existing target assignment algorithms in that it explicitly takes symbolic actions into account. Such actions include the deployment and retrieval of other robots or manipulation tasks. Our method integrates a temporal planning approach with a traditional cost-based planner. The proposed approach was implemented and evaluated in two distinct settings. First, we coordinated teams of marsupial robots. Such robots are able to deploy and pickup smaller robots. Second, we simulated a disaster scenario where the task is to clear blockades and reach certain critical locations in the environment. A similar setting was also investigated using a team of real robots. The results show that our approach outperforms ad-hoc extensions of state-of-the-art cost-based coordination methods and that the approach is able to efficiently coordinate teams of heterogeneous robots and to consider symbolic actions.     

Mobility characterization for autonomous mobile robots using machine learning

This paper presents a supervised learning approach to improving the autonomous mobility of wheeled robots through sensing the robot’s interaction with terrain ‘underfoot.’ Mobility characterization is cast as a hierarchical task, in which pre-immobilization detection is achieved using support vector machines in time to prevent full immobilization, and if a pre-immobilization condition is detected, the associated terrain feature affecting mobility is identified using a Hidden Markov model. These methods are implemented using a hierarchical, layered control scheme developed for the Yeti robot, a 73-kg, four-wheeled robot designed to perform autonomous medium-range missions in polar terrain. The methodology is motivated by the difficultly of visually recognizing terrain features that impact mobility in low contrast terrain. The efficacy of the approach is evaluated using data from a suite of proprioceptive sensors. Real-time implementation shows that Yeti can consistently detect pre-immobilization conditions, stop in time to avoid unrecoverable immobilization, identify the terrain feature presenting the mobility challenge, and execute an escape sequence to retreat from the condition.     

Geographical information systems for map based navigation in urban environments

In order to solve most of the existing mobile robotics applications, the robot needs some information about its spatial environment encoded in what it has been commonly called a map. The knowledge contained in such a map, whatever approach is used to obtain it, will mainly be used by the robot to gain the ability to navigate in a given environment. We are describing in this paper, a method that allows a robot or team of robots to navigate in large urban areas for which an existing map in a standard human understandable fashion is available. As detailed maps of most urban areas already exist, it will be assumed that a map of the zone where the robot is supposed to work is given, which has not been constructed using the robot’s own sensors. We propose in this paper, the use of an existing Geographical Information System based map of an urban zone so that a robot or a team of robots can connect to this map and use it for navigation purposes. Details of the implemented system architecture as well as a position tracking experiment in a real outdoor environment, a University Campus, are provided.     

Cooperative Large Area Surveillance with a Team of Aerial Mobile Robots for Long Endurance Missions

This paper proposes a distributed approach to solve long duration area surveillance missions with a team of aerial robots, taking into account communication constraints. The system, based on “one-to-one” coordination, minimizes the probability that any event happens in the area without being detected and ensures periodic communication between UAVs. A set of simulations are presented to validate the applicability of the approach and its most relevant features: convergence, robustness with dynamic teams, fault-tolerance and finite information sharing time. It is also shown that “one-to-one” coordination for all the pairs of neighbors allows to obtain an efficient coordination scheme for the whole team to accomplish the area surveillance mission without any central unit.     

High-level motion planning for CPG-driven modular robots

Modular robots may become candidates for search and rescue operations or even for future space missions, as they can change their structure to adapt to terrain conditions and to better fulfill a given task. A core problem in such missions is the ability to visit distant places in rough terrain. Traditionally, the motion of modular robots is modeled using locomotion generators that can provide various gaits, e.g. crawling or walking. However, pure locomotion generation cannot ensure that desired places in a complex environment with obstacles will in fact be reached. These cases require several locomotion generators providing motion primitives that are switched using a planning process that takes the obstacles into account. In this paper, we present a novel motion planning method for modular robots equipped with elementary motion primitives. The utilization of primitives significantly reduces the complexity of the motion planning which enables plans to be created for robots of arbitrary shapes. The primitives used here do not need to cope with environmental changes, which can therefore be realized using simple locomotion generators that are scalable, i.e., the primitives can provide motion for robots with many modules. As the motion primitives are realized using locomotion generators, no reconfiguration is required and the proposed approach can thus be used even for modular robots without self-reconfiguration capabilities. The performance of the proposed algorithm has been experimentally verified in various environments, in physical simulations and also in hardware experiments.     

One-to-One Coordination Algorithm for Decentralized Area Partition in Surveillance Missions with a Team of Aerial Robots

This paper presents a decentralized algorithm for area partition in surveillance missions that ensures information propagation among all the robots in the team. The robots have short communication ranges compared to the size of the area to be covered, so a distributed one-to-one coordination schema has been adopted. The goal of the team is to minimize the elapsed time between two consecutive observations of any point in the area. A grid-shape area partition strategy has been designed to guarantee that the information gathered by any robot is shared among all the members of the team. The whole proposed decentralized strategy has been simulated in an urban scenario to confirm that fulfils all the goals and requirements and has been also compared to other strategies.     

Using Virtual Pheromones and Cameras for Dispersing a Team of Multiple Miniature Robots

To safely and efficiently guide personnel of search and rescue operations in disaster areas, swift gathering of relevant information such as the locations of victims, must occur. Using the concept of ‘repellent virtual pheromones’ inspired by insect colony coordination behaviors, miniature robots can be quickly dispersed to survey a disaster site. Assisted by visual servoing, dispersion of the miniature robots can quickly cover an area. An external observer such as another robot or an overhead camera is brought into the control loop to provide each miniature robot estimations of the positions of all of the other near-by robots in the robotic team. These miniature robots can then move away from the other near-by robots on the team, resulting in the robot collective becoming swiftly distributed through the local area. The technique has been simulated with differing pheromone persistence levels and implemented using the miniature Scout robots, developed by the Center for Distributed Robotics at the University of Minnesota, which are well-suited to surveillance and reconnaissance missions.     

Multi-robot exploration under the constraints of wireless networking

A multi-robot system can be highly beneficial for exploration, which is a core robotics task. Application domains include, for example, surveillance, reconnaissance, planetary exploration or rescue missions. When using a team of robots, the overall performance can be much faster and more robust. In this article, an approach to multi-robot exploration is presented that takes the constraints of wireless networking into account. An algorithm is introduced based on a population that samples the possible moves of all robots and a utility to select the best one in each time step. Results from two scenarios are presented. In the first one, a team of robots explores its environment while permanently maintaining an ad hoc network structure with each other as well as a base station at a fixed location. In the second one, the robots move freely as a pack while maintaining communication with each other.     

Multi-robot exploration and terrain coverage in an unknown environment

Terrain exploration and coverage are required for a variety of applications such as mine clearing, intrusion detection and other humanitarian missions like search and rescue operations, for example, fire or blast in a building. During an emergency situation within a building it is crucial to explore the area as fast as possible in order to search and find the wounded people and other hazards. On account of the prevailing breakdown of communication in indoor environments in some situations, it is suggested that the robots can communicate indirectly with the use of markings in the environment. The Spanning Tree Coverage (STC) method, proposed for this problem, suffers in environments that have partially occupied cells and narrow door openings between rooms. In this paper, we consider an extension of the Simultaneous Multiple STC (S-MSTC) algorithm, which we proposed in our previous work on multiple autonomous robots used in exploration and coverage in an unknown terrain. The proposed extended S-MSTC (ES-MSTC) uses ant-type robots to cover the terrain leaving marks on the terrain, which can be sensed by the robots and allow them to cover the terrain, similar to the nature of ants. This algorithm can handle partially occupied cells and narrow door openings in the terrain and performs a complete coverage of the surface regardless of the shape of the environment by constructing multiple spanning trees simultaneously. We present a simulation study and compare the performance of the ES-MSTC algorithm with other existing algorithms.     

Sequencing of multi‑robot behaviors using reinforcement learning

Given a collection of parameterized multi-robot controllers associated with individual behaviors designed for particular tasks, this paper considers the problem of how to sequence and instantiate the behaviors for the purpose of completing a more complex, overarching mission. In addition, uncertainties about the environment or even the mission specifications may require the robots to learn, in a cooperative manner, how best to sequence the behaviors. In this paper, we approach this problem by using reinforcement learning to approximate the solution to the computationally intractable sequencing problem, combined with an online gradient descent approach to selecting the individual behavior parameters, while the transitions among behaviors are triggered automatically when the behaviors have reached a desired performance level relative to a task performance cost. To illustrate the effectiveness of the proposed method, it is implemented on a team of differential-drive robots for solving two different missions, namely, convoy protection and object manipulation.     

Trafficability Assessment of Deformable Terrain through Hybrid Wheel‐Leg Sinkage Detection

Off‐road ground mobile robots are widely used in diverse applications, both in terrestrial and planetary environments. They provide an efficient alternative, with lower risk and cost, to explore or to transport materials through hazardous or challenging terrain. However, nongeometric hazards that cannot be detected remotely pose a serious threat to the mobility of such robots. A prominent example of the negative effects these hazards can have is found on planetary rover exploration missions. They can cause a serious degradation of mission performance at best and complete immobilization and mission failure at worst. To tackle this issue, the work presented in this paper investigates the novel application of an existing enhanced‐mobility locomotion concept, a hybrid wheel‐leg equipped by a lightweight micro‐rover, for in situ characterization of deformable terrain and online detection of nongeometric hazards. This is achieved by combining an improved vision‐based approach and a new ranging‐based approach to wheel‐leg sinkage detection. In addition, the paper proposes an empirical model, and a parametric generalization, to predict terrain trafficability based on wheel‐leg sinkage and a well‐established semiempirical terramechanics model. The robustness and accuracy of the sinkage detection methods implemented are tested in a variety of conditions, both in the laboratory and in the field, using a single wheel‐leg test bed. The sinkage‐trafficability model is developed based on experimental data using this test bed and then validated onboard a fully mobile robot through experimentation on a range of dry frictional soils that covers a wide spectrum of macroscopic physical characteristics.     

OctoMap: an efficient probabilistic 3D mapping framework based on octrees

Three-dimensional models provide a volumetric representation of space which is important for a variety of robotic applications including flying robots and robots that are equipped with manipulators. In this paper, we present an open-source framework to generate volumetric 3D environment models. Our mapping approach is based on octrees and uses probabilistic occupancy estimation. It explicitly represents not only occupied space, but also free and unknown areas. Furthermore, we propose an octree map compression method that keeps the 3D models compact. Our framework is available as an open-source C++ library and has already been successfully applied in several robotics projects. We present a series of experimental results carried out with real robots and on publicly available real-world datasets. The results demonstrate that our approach is able to update the representation efficiently and models the data consistently while keeping the memory requirement at a minimum.     

Online terrain parameter estimation for wheeled mobile robots with application to planetary rovers

Future planetary exploration missions will require wheeled mobile robots ("rovers") to traverse very rough terrain with limited human supervision. Wheel-terrain interaction plays a critical role in rough-terrain mobility. In this paper, an online estimation method that identifies key terrain parameters using on-board robot sensors is presented. These parameters can be used for traversability prediction or in a traction control algorithm to improve robot mobility and to plan safe action plans for autonomous systems. Terrain parameters are also valuable indicators of planetary surface soil composition. The algorithm relies on a simplified form of classical terramechanics equations and uses a linear-least squares method to compute terrain parameters in real time. Simulation and experimental results show that the terrain estimation algorithm can accurately and efficiently identify key terrain parameters for various soil types.     

A Graph Theoretic Approach for Modeling Mobile Robot Team Formations

This paper addresses a new approach for modeling and control of multiple teams of mobile robots navigating in a terrain with obstacles, while maintaining a desired formation and changing formations when required. We model each team as a triple, (g,r, ?? ), consisting of a group element, g∈SE(2), that describes the gross position of the lead robot, a set of shape variables, r, that describe the relative positions of robots, and a control graph, ??, that describes the behaviors of the robots in the formation. We assume that all the robots are equipped with the appropriate sensors to detect and avoid other robots and obstacles in the environment. Our framework enables the representation and enumeration of possible control graphs, and the coordination of transitions between any two control graphs. Further, we describe an algorithm that allows each team of robots to move between any two formations, while avoiding obstacles. As the number of robots increases, the number of possible control graphs increases. However, because the control computations are decentralized, the algorithms scale with the number of robots. We present examples to illustrate the control graphs and the algorithm for transitioning between them in the presence and absence of sensor noise. © 2002 Wiley Periodicals, Inc.     

Multi-agent Rapidly-exploring Pseudo-random Tree

Real-time motion planning and control for groups of heterogeneous and under-actuated robots subject to disturbances and uncertainties in cluttered constrained environments is the key problem addressed in this paper. Here we present the Multi-agent Rapidly-exploring Pseudo-random Tree (MRPT), a novel technique based on a classical Probabilistic Road Map (PRM) algorithm for application in robot team cooperation. Our main contribution lies in the proposal of an extension of a probabilistic approach to be used as a deterministic planner in distributed complex multi-agent systems, keeping the main advantages of PRM strategies like simplicity, fast convergence, and probabilistic completeness. Our methodology is fully distributed, addressing missions with multi-robot teams represented by high nonlinear models and a great number of Degrees of Freedom (DoFs), endowing each agent with the ability of coordinating its own movement with other agents while avoiding collisions with obstacles. The inference of the entire team’s behavior at each time instant by each individual agent is the main improvement of our method. This scheme, which is behavioral in nature, also makes the system less susceptible to failures due to intensive traffic communication among robots. We evaluate the time complexity of our method and show its applicability in planning and executing search and rescue missions for a group of robots in S E3 outdoor scenarios and present both simulated and real-world results.     

Hybrid mission planning with coalition formation

The increase in robotic capabilities and the number of such systems being used has resulted in opportunities for robots to work alongside humans in an increasing number of domains. The current robot control paradigm of one or multiple humans controlling a single robot is not scalable to domains that require large numbers of robots and is infeasible in communications constrained environments. Robots must autonomously plan how to accomplish missions composed of many tasks in complex and dynamic domains; however, mission planning with a large number of robots for such complex missions and domains is intractable. Coalition formation can manage planning problem complexity by allocating the best possible team of robots for each task. A limitation is that simply allocating the best possible team does not guarantee an executable plan can be formulated. However, coupling coalition formation with planning creates novel, domain-independent tools resulting in the best possible teams executing the best possible plans for robots acting in complex domains.     

The giving tree: constructing trees for efficient offline and online multi-robot coverage

This paper discusses the problem of building efficient coverage paths for a team of robots. An efficient multi-robot coverage algorithm should result in a coverage path for every robot, such that the union of all paths generates a full coverage of the terrain and the total coverage time is minimized. A method underlying several coverage algorithms, suggests the use of spanning trees as base for creating coverage paths. However, overall performance of the coverage is heavily dependent on the given spanning tree. This paper focuses on the challenge of constructing a coverage spanning tree for both online and offline coverage that minimizes the time to complete coverage. Our general approach involves building a spanning tree by growing sub-trees from the initial location of the robots. This paper first describes a polynomial time tree-construction algorithm for offline coverage. The use of this algorithm is shown by extensive simulations to significantly improve the coverage time of the terrain even when used as a basis for a simple, inefficient, coverage algorithm. Second, this paper provides an algorithm for online coverage of a finite terrain based on spanning-trees, that is complete and guarantees linear time coverage with no redundancy in the coverage. In addition, the solutions proposed by this paper guarantee robustness to failing robots: the offline trees are used as base for robust multi-robot coverage algorithms, and the online algorithm is proven to be robust.