Adaptive mapping and navigation by teams of simple robots

We present a technique for mapping an unknown environment and navigating through it using a team of simple robots. Minimal assumptions are made about the abilities of the robots on a team. We assume only that robots can explore the environment using a random walk, detect the goal location, and communicate among themselves by transmitting a single small integer over a limited distance and in a direct line of sight; additionally, one designated robot, the navigator, can track toward a team member when it is nearby and in a direct line of sight. We do not assume that robots can determine their absolute (x, y) positions in the environment to be mapped, determine their positions relative to other team members, or sense anything other than the goal location and the transmissions of their teammates. In spite of these restrictive assumptions, we show that for moderate-sized teams in complex environments the time needed to construct a map and then navigate to a goal location can be competitive with the time needed to navigate to the goal along an optimal path formed with perfect knowledge of the environment. In other words, collective mapping enables navigation in an unmapped environment with only modest overhead. This basic result holds over a wide range of assumptions about robot reliability, sensor range, tracking ability.

We then describe an extended mapping algorithm that allows an existing map to be efficiently corrected when a goal location changes. We show that a robot team using the algorithm is adaptive, in the sense that its performance will improve over time, whenever navigation goals follow certain regular patterns.     

Lifelong Adaptation in Heterogeneous Multi-Robot Teams: Response to Continual Variation in Individual Robot Performance

Generating teams of robots that are able to perform their tasks over long periods of time requires the robots to be responsive to continual changes in robot team member capabilities and to changes in the state of the environment and mission. In this article, we describe the L-ALLIANCE architecture, which enables teams of heterogeneous robots to dynamically adapt their actions over time. This architecture, which is an extension of our earlier work on ALLIANCE, is a distributed, behavior-based architecture aimed for use in applications consisting of a collection of independent tasks. The key issue addressed in L-ALLIANCE is the determination of which tasks robots should select to perform during their mission, even when multiple robots with heterogeneous, continually changing capabilities are present on the team. In this approach, robots monitor the performance of their teammates performing common tasks, and evaluate their performance based upon the time of task completion. Robots then use this information throughout the lifetime of their mission to automatically update their control parameters. After describing the L-ALLIANCE architecture, we discuss the results of implementing this approach on a physical team of heterogeneous robots performing proof-of-concept box pushing experiments. The results illustrate the ability of L-ALLIANCE to enable lifelong adaptation of heterogeneous robot teams to continuing changes in the robot team member capabilities and in the environment.     

A case-based approach for coordinated action selection in robot soccer

Designing coordinated robot behaviors in uncertain, dynamic, real-time, adversarial environments, such as in robot soccer, is very challenging. In this work we present a case-based reasoning approach for cooperative action selection, which relies on the storage, retrieval, and adaptation of example cases. We focus on cases of coordinated attacking passes between robots in the presence of the defending opponent robots. We present the case representation explicitly distinguishing between controllable and uncontrollable indexing features, corresponding to the positions of the team members and opponent robots, respectively. We use the symmetric properties of the domain to automatically augment the case library. We introduce a retrieval technique that weights the similarity of a situation in terms of the continuous ball positional features, the uncontrollable features, and the cost of moving the robots from the current situation to match the case controllable features. The case adaptation includes a best match between the positions of the robots in the past case and in the new situation. The robots are assigned an adapted position to which they move to maximize the match to the retrieved case. Case retrieval and reuse are achieved within the distributed team of robots through communication and sharing of own internal states and actions. We evaluate our approach, both in simulation and with real robots, in laboratory scenarios with two attacking robots versus two defending robots as well as versus a defender and a goalie. We show that we achieve the desired coordinated passing behavior, and also outperform a reactive action selection approach.     

Distributed multirobot exploration, mapping, and task allocation

We present an integrated approach to multirobot exploration, mapping and searching suitable for large teams of robots operating in unknown areas lacking an existing supporting communications infrastructure. We present a set of algorithms that have been both implemented and experimentally verified on teams—of what we refer to as Centibots—consisting of as many as 100 robots. The results that we present involve search tasks that can be divided into a mapping stage in which robots must jointly explore a large unknown area with the goal of generating a consistent map from the fragment, a search stage in which robots are deployed within the environment in order to systematically search for an object of interest, and a protection phase in which robots are distributed to track any intruders in the search area. During the first stage, the robots actively seek to verify their relative locations in order to ensure consistency when combining data into shared maps; they must also coordinate their exploration strategies so as to maximize the efficiency of exploration. In the second and third stages, robots allocate search tasks among themselves; since tasks are not defined a priori, the robots first produce a topological graph of the area of interest and then generate a set of tasks that reflect spatial and communication constraints. Our system was evaluated under extremely realistic real-world conditions. An outside evaluation team found the system to be highly efficient and robust.     

Coordinated multi-robot exploration

In this paper, we consider the problem of exploring an unknown environment with a team of robots. As in single-robot exploration the goal is to minimize the overall exploration time. The key problem to be solved in the context of multiple robots is to choose appropriate target points for the individual robots so that they simultaneously explore different regions of the environment. We present an approach for the coordination of multiple robots, which simultaneously takes into account the cost of reaching a target point and its utility. Whenever a target point is assigned to a specific robot, the utility of the unexplored area visible from this target position is reduced. In this way, different target locations are assigned to the individual robots. We furthermore describe how our algorithm can be extended to situations in which the communication range of the robots is limited. Our technique has been implemented and tested extensively in real-world experiments and simulation runs. The results demonstrate that our technique effectively distributes the robots over the environment and allows them to quickly accomplish their mission.     

Millibots

Concerns the development of a framework and algorithms for a distributed heterogeneous robot team. Team members exchange sensor information, collaborate to track and identify targets, or even assist each other to scale obstacles. As for sensing, by coordinating its members a team can exploit information derived from multiple disparate viewpoints. A single robot, even though equipped with a large array of different sensing modalities, is limited at any one time to a single viewpoint, but a team of robots can simultaneously collect information from multiple locations. This article describes the design and construction of a team of 7 /spl times/ 7 /spl times/ 7-cm robots called "millibots". We show how the team can exploit collaboration to perform missions such as mapping, exploration, surveillance, and eventually support rescue operations.     

A PATH PLANNING METHOD BASED ON CELLULAR AUTOMATA FOR COOPERATIVE ROBOTS

A Cellular Automaton-based technique suitable for solving the path planning problem in a distributed robot team is outlined. Real-time path planning is a challenging task that has many applications in the fields of artificial intelligence, moving robots, virtual reality, and agent behavior simulation. The problem refers to finding a collision-free path for autonomous robots between two specified positions in a configuration area. The complexity of the problem increases in systems of multiple robots. More specifically, some distance should be covered by each robot in an unknown environment, avoiding obstacles found on its route to the destination. On the other hand, all robots must adjust their actions in order to keep their initial team formation immutable. Two different formations were tested in order to study the efficiency and the flexibility of the proposed method. Using different formations, the proposed technique could find applications to image processing tasks, swarm intelligence, etc. Furthermore, the presented Cellular Automaton (CA) method was implemented and tested in a real system using three autonomous mobile minirobots called E-pucks. Experimental results indicate that accurate collision-free paths could be created with low computational cost. Additionally, cooperation tasks could be achieved using minimal hardware resources, even in systems with low-cost robots.     

Generalized measuring-worm algorithm: high-accuracy mapping and movement via cooperating swarm robots

Recently, many extensive studies have been conducted on robot control via self-positioning estimation techniques. In the simultaneous localization and mapping (SLAM) method, which is one approach to self-positioning estimation, robots generally use both autonomous position information from internal sensors and observed information on external landmarks. SLAM can yield higher accuracy positioning estimations depending on the number of landmarks; however, this technique involves a degree of uncertainty and has a high computational cost, because it utilizes image processing to detect and recognize landmarks. To overcome this problem, we propose a state-of-the-art method called a generalized measuring-worm (GMW) algorithm for map creation and position estimation, which uses multiple cooperating robots that serve as moving landmarks for each other. This approach allows problems of uncertainty and computational cost to be overcome, because a robot must find only a simple two-dimensional marker rather than feature-point landmarks. In the GMW method, the robots are given a two-dimensional marker of known shape and size and use a front-positioned camera to determine the marker distance and direction. The robots use this information to estimate each other’s positions and to calibrate their movement. To evaluate the proposed method experimentally, we fabricated two real robots and observed their behavior in an indoor environment. The experimental results revealed that the distance measurement and control error could be reduced to less than 3 %.     

Robot Teams for Intervention in Confined and Structured Environments

Safety, security, and rescue robotics can be extremely useful in emergency scenarios such as mining accidents or tunnel collapses where robot teams can be used to carry out cooperative exploration, intervention, or logistic missions. Deploying a multirobot team in such confined environments poses multiple challenges that involve task planning, motion planning, localization and mapping, safe navigation, coordination, and communications among all the robots. To complete their mission, robots have to be able to move in the environment with full autonomy while at the same time maintaining communication among themselves and with their human operators to accomplish team collaboration. Guaranteeing connectivity enables robots to explicitly exchange information needed in the execution of collaborative tasks and allows operators to monitor and teleoperate the robots and receive information about the environment. In this work, we present a system that integrates several research aspects to achieve a real exploration exercise in a tunnel using a robot team. These aspects are as follows: deployment planning, semantic feature recognition, multirobot navigation, localization, map building, and real‐time communications. Two experimental scenarios have been used for the assessment of the system. The first is the Spanish Santa Marta mine, a large mazelike environment selected for its complexity for all the tasks involved. The second is the Spanish‐French Somport tunnel, an old railway between Spain and France through the Central Pyrenees, used to carry out the real‐world experiments. The latter is a simpler scenario, but it serves to highlight the real communication issues.     

Map merging for multiple robots using Hough peak matching

Navigation in a GPS-denied environment is an essential requirement for increased robotics autonomy. While this is in some sense solved for a single robot, the next challenge is to design algorithms for a team of robots to be able to map and navigate efficiently.The key requirement for achieving this team autonomy is to provide the robots with a collaborative ability to accurately map an environment. This problem is referred to as cooperative simultaneous localization and mapping (SLAM). In this research, the mapping process is extended to multiple robots with a novel occupancy grid map fusion algorithm. Map fusion is achieved by transforming individual maps into the Hough space where they are represented in an abstract form. Properties of the Hough transform are used to find the common regions in the maps, which are then used to calculate the unknown transformation between the maps.Results are shown from tests performed on benchmark datasets and real-world experiments with multiple robotic platforms.     

Efficient exploration of unknown indoor environments using a team of mobile robots

Whenever multiple robots have to solve a common task, they need to coordinate their actions to carry out the task efficiently and to avoid interferences between individual robots. This is especially the case when considering the problem of exploring an unknown environment with a team of mobile robots. To achieve efficient terrain coverage with the sensors of the robots, one first needs to identify unknown areas in the environment. Second, one has to assign target locations to the individual robots so that they gather new and relevant information about the environment with their sensors. This assignment should lead to a distribution of the robots over the environment in a way that they avoid redundant work and do not interfere with each other by, for example, blocking their paths. In this paper, we address the problem of efficiently coordinating a large team of mobile robots. To better distribute the robots over the environment and to avoid redundant work, we take into account the type of place a potential target is located in (e.g., a corridor or a room). This knowledge allows us to improve the distribution of robots over the environment compared to approaches lacking this capability. To autonomously determine the type of a place, we apply a classifier learned using the AdaBoost algorithm. The resulting classifier takes laser range data as input and is able to classify the current location with high accuracy. We additionally use a hidden Markov model to consider the spatial dependencies between nearby locations. Our approach to incorporate the information about the type of places in the assignment process has been implemented and tested in different environments. The experiments illustrate that our system effectively distributes the robots over the environment and allows them to accomplish their mission faster compared to approaches that ignore the place labels.     

Value-based action selection for observation with robot teams using probabilistic techniques

We present an approach for directing next-step movements of robot teams engaged in mapping objects in their environment: Move Value Estimation for Robot Teams (MVERT). Resulting robot paths tend to optimize vantage points for all robots on the team by maximizing information gain. At each step, each robot selects a movement to maximize the utility (in this case, reduction in uncertainty) of its next observation. Trajectories are not guaranteed to be optimal, but team behavior serves to maximize the team's knowledge since each robot considers the observational contributions of team mates. MVERT is evaluated in simulation by measuring the resulting uncertainty about target locations compared to that obtained by robots acting without regard to team mate locations and to that of global optimization over all robots for each single step. Additionally, MVERT is demonstrated on physical teams of robots. The qualitative behavior of the team is appropriate and close to the single-step optimal set of trajectories.     

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.     

多移动机器人的组队规划研究

研究了多移动机器人在组队时目标点的优化选取与避障控制问题。依据最近距离最大值优先获得目标点的规则,提出建立机器人与目标位置距离矩阵,并对矩阵进行映射分析,使机器人快速准确地确定对应目标点。采用模糊控制理论,依据经验制定模糊规则,使机器人灵活地避开障碍,仿真实验证明了算法的有效性。     

Physical Path Planning Using a Pervasive Embedded Network

We evaluate a technique that uses an embedded network deployed pervasively throughout an environment to aid robots in navigation. The embedded nodes do not know their absolute or relative positions and the mobile robots do not perform localization or mapping. Yet, the mobile robot is able to navigate through complex environments effectively. First, we present an algorithm for physical path planning and its implementation on the Gnats, a novel embedded network platform. Next, we investigate the quality of the computed paths. We present quantitative results collected from a real-world embedded network of 60 nodes. Experimentally, we find that, on average, the path computed by the network is only 24% longer than the optimal path. Finally, we show that the paths computed by the network are useful for a simple mobile robot. Results from a network of 156 nodes in a static environment and a network of 60 nodes in a dynamic environment are presented.     

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.     

Concurrent localization of multiple robots

A concurrent localization method for multiple robots using ultrasonic beacons is proposed. This method provides a high-accuracy solution using only low-price sensors. To measure the distance of a mobile robot from a beacon at a known position, the mobile robot alerts one beacon to send out an ultrasonic signal to measure the traveling time from the beacon to the mobile robot. When multiple robots requiring localization are moving in the same block, it is necessary to have a schedule to choose the measuring sequence in order to overcome constant ultrasonic signal interference among robots. However, the increased time delay needed to estimate the positions of multiple robots degrades the localization accuracy. To solve this problem, we propose an efficient localization algorithm for multiple robots, where the robots are in groups of one master robot and several slave robots. In this method, when a master robot calls a beacon, all the group robots simultaneously receive an identical ultrasonic signal to estimate their positions. The effectiveness of the proposed algorithm has been verified through experiments.     

Distributed Algorithms for Multi-Robot Observation of Multiple Moving Targets

An important issue that arises in the automation of many security, surveillance, and reconnaissance tasks is that of observing the movements of targets navigating in a bounded area of interest. A key research issue in these problems is that of sensor placement—determining where sensors should be located to maintain the targets in view. In complex applications involving limited-range sensors, the use of multiple sensors dynamically moving over time is required. In this paper, we investigate the use of a cooperative team of autonomous sensor-based robots for the observation of multiple moving targets. In other research, analytical techniques have been developed for solving this problem in complex geometrical environments. However, these previous approaches are very computationally expensive—at least exponential in the number of robots—and cannot be implemented on robots operating in real-time. Thus, this paper reports on our studies of a simpler problem involving uncluttered environments—those with either no obstacles or with randomly distributed simple convex obstacles. We focus primarily on developing the on-line distributed control strategies that allow the robot team to attempt to minimize the total time in which targets escape observation by some robot team member in the area of interest. This paper first formalizes the problem (which we term CMOMMT for Cooperative Multi-Robot Observation of Multiple Moving Targets) and discusses related work. We then present a distributed heuristic approach (which we call A-CMOMMT) for solving the CMOMMT problem that uses weighted local force vector control. We analyze the effectiveness of the resulting weighted force vector approach by comparing it to three other approaches. We present the results of our experiments in both simulation and on physical robots that demonstrate the superiority of the A-CMOMMT approach for situations in which the ratio of targets to robots is greater than 1/2. Finally, we conclude by proposing that the CMOMMT problem makes an excellent domain for studying multi-robot learning in inherently cooperative tasks. This approach is the first of its kind for solving the on-line cooperative observation problem and implementing it on a physical robot team.     

Large scale multiple robot visual mapping with heterogeneous landmarks in semi-structured terrain

This paper addresses the cooperative localization and visual mapping problem with multiple heterogeneous robots. The approach is designed to deal with the challenging large semi-structured outdoors environments in which aerial/ground ensembles are to evolve. We propose the use of heterogeneous visual landmarks, points and line segments, to achieve effective cooperation in such environments. A large-scale SLAM algorithm is generalized to handle multiple robots, in which a global graph maintains the relative relationships between a series of local sub-maps built by the different robots. The key issue when dealing with multiple robots is to find the link between them, and to integrate these relations to maintain the overall geometric consistency; the events that introduce these links on the global graph are described in detail. Monocular cameras are considered as the primary extereoceptive sensor. In order to achieve the undelayed initialization required by the bearing-only observations, the well-known inverse-depth parametrization is adopted to estimate 3D points. Similarly, to estimate 3D line segments, we present a novel parametrization based on anchored Plücker coordinates, to which extensible endpoints are added. Extensive simulations show the proposed developments, and the overall approach is illustrated using real-data taken with a helicopter and a ground rover.     

异质多移动机器人协同技术研究的进展

随着移动机器人应用的领域和范围的不断扩展，多移动机器人由于其单个机器人无法比拟的优越性已经越来越受到重视．从体系结构、协作与协调、协作环境感知与定位、重构及机器学习几个重要课题对多移动机器人协同技术进行了综述，尤其侧重于各种技术如何处理和包容团队中的异质性，并分析了本领域中的研究难点问题，最后展望了异质多移动机器人研究的前景与发展趋势．