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.     

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.     

Optimal surveillance coverage for teams of micro aerial vehicles in GPS-denied environments using onboard vision

This paper deals with the problem of deploying a team of flying robots to perform surveillance-coverage missions over a terrain of arbitrary morphology. In such missions, a key factor for the successful completion of the mission is the knowledge of the terrain’s morphology. The focus of this paper is on the implementation of a two-step procedure that allows us to optimally align a team of flying vehicles for the aforementioned task. Initially, a single robot constructs a map of the area using a novel monocular-vision-based approach. A?state-of-the-art visual-SLAM algorithm tracks the pose of the camera while, simultaneously, autonomously, building an incremental map of the environment. The map generated is processed and serves as an input to an optimization procedure using the cognitive, adaptive methodology initially introduced in Renzaglia et?al. (Proceedings of the IEEE international conference on robotics and intelligent system (IROS), Taipei, Taiwan, pp.?3314–3320, 2010). The output of this procedure is the optimal arrangement of the robots team, which maximizes the monitored area. The efficiency of our approach is demonstrated using real data collected from aerial robots in different outdoor areas.     

Bridging the gap between feature- and grid-based SLAM

One important design decision for the development of autonomously navigating mobile robots is the choice of the representation of the environment. This includes the question of which type of features should be used, or whether a dense representation such as occupancy grid maps is more appropriate. In this paper, we present an approach which performs SLAM using multiple representations of the environment simultaneously. It uses reinforcement to learn when to switch to an alternative representation method depending on the current observation. This allows the robot to update its pose and map estimate based on the representation that models the surrounding of the robot in the best way. The approach has been implemented on a real robot and evaluated in scenarios, in which a robot has to navigate in- and outdoors and therefore switches between a landmark-based representation and a dense grid map. In practical experiments, we demonstrate that our approach allows a robot to robustly map environments which cannot be adequately modeled by either of the individual representations.     

Scalable formation control in stealth with limited sensing range

In this paper, a protocol and a control law are designed for a single robot so that a team of such robots can interact and cooperate to reach the displacements from an eligible reference formation. Each robot is equipped with displacement sensors of limited sensing ranges. Communication channels are assumed to be unavailable to the team, and each robot works in stealth mode. The team is scalable such that new robots can be recruited, and existing robots can be dismissed. In order for the team size to be scalable, the extended formation based on relative displacement is established as the reference formation. Thus, using the extended formation as a reference, the control law and the protocol could be flexible. As potential conflicts deflect the robot team from the desired formation, the control law is designed to expose the conflicts to the involved neighboring robots such that the protocol can resolve them. A numerical example is given to illustrate how an extended formation is designed, and a simulation example is conducted to demonstrate the performance and merits of the proposed techniques. Copyright © 2016 John Wiley & Sons, Ltd.     

Autonomous navigation for mobile service robots in urban pedestrian environments

This paper presents a fully autonomous navigation solution for urban, pedestrian environments. The task at hand, undertaken within the context of the European project URUS, was to enable two urban service robots, based on Segway RMP200 platforms and using planar lasers as primary sensors, to navigate around a known, large (10,000 m²), pedestrian‐only environment with poor global positioning system coverage. Special consideration is given to the nature of our robots, highly mobile but two‐wheeled, self‐balancing, and inherently unstable. Our approach allows us to tackle locations with large variations in height, featuring ramps and staircases, thanks to a three‐dimensional, map‐based particle filter for localization and to surface traversability inference for low‐level navigation. This solution was tested in two different urban settings, the experimental zone devised for the project, a university campus, and a very crowded public avenue, both located in the city of Barcelona, Spain. Our results total more than 6 km of autonomous navigation, with a success rate on go‐to requests of nearly 99%. The paper presents our system, examines its overall performance, and discusses the lessons learned throughout development. © 2011 Wiley Periodicals, Inc.     

Information based indoor environment robotic exploration and modeling using 2-D images and graphs

As the autonomy of personal service robotic systems increases so has their need to interact with their environment. The most basic interaction a robotic agent may have with its environment is to sense and navigate through it. For many applications it is not usually practical to provide robots in advance with valid geometric models of their environment. The robot will need to create these models by moving around and sensing the environment, while minimizing the complexity of the required sensing hardware. Here, an information-based iterative algorithm is proposed to plan the robot's visual exploration strategy, enabling it to most efficiently build a graph model of its environment. The algorithm is based on determining the information present in sub-regions of a 2-D panoramic image of the environment from the robot's current location using a single camera fixed on the mobile robot. Using a metric based on Shannon's information theory, the algorithm determines potential locations of nodes from which to further image the environment. Using a feature tracking process, the algorithm helps navigate the robot to each new node, where the imaging process is repeated. A Mellin transform and tracking process is used to guide the robot back to a previous node. This imaging, evaluation, branching and retracing its steps continues until the robot has mapped the environment to a pre-specified level of detail. The set of nodes and the images taken at each node are combined into a graph to model the environment. By tracing its path from node to node, a service robot can navigate around its environment. This method is particularly well suited for flat-floored environments. Experimental results show the effectiveness of this algorithm.     

Simplified map representation and map learning system for autonomous navigation of mobile robots

Autonomous mobile robots need environmental maps to navigate to specific destinations, but there are difficulties in generating and acquiring efficient maps for them. Map learning systems and map representation for autonomous robot navigation are highly interrelated and need a total system design that combines these two factors. This study considers a combined simple map representation and map learning system. The proposed map representation includes geometrical relationships between important places and grid maps for these places, but not a total grid map of the environment. In particular, the study focuses on the ability to recognize places based on image features. Successful experiments on autonomous navigation with the proposed map representation using an actual mobile robot are described.     

Optimal Robot Localization in Trees

The problem of localization, that is, of a robot finding its position on a map, is an important task for autonomous mobile robots. It has applications in numerous areas of robotics ranging from aerial photography to autonomous vehicle exploration. In this paper we present a new strategy LPS (Localize-by-Placement-Separation) for a robot to find its position on a map, where the map is represented as a geometric tree of bounded degree. Our strategy exploits to a high degree the self-similarities that may occur in the environment. We use the framework of competitive analysis to analyze the performance of our strategy. In particular, we show that the distance traveled by the robot is at most O( ) times longer than the shortest possible route to localize the robot, where n is the number of vertices of the tree. This is a significant improvement over the best known previous bound of O(n^2/3). Moreover, since there is a lower bound of Ω( ), our strategy is optimal up to a constant factor. Using the same approach we can also show that the problem of searching for a target in a geometric tree, where the robot is given a map of the tree and the location of the target but does not know its own position, can be solved by a strategy with a competitive ratio of O( ), which is again optimal up to a constant factor.     

Perceptive whole‐body planning for multilegged robots in confined spaces

Legged robots are exceedingly versatile and have the potential to navigate complex, confined spaces due to their many degrees of freedom. As a result of the computational complexity, there exist no online planners for perceptive whole‐body locomotion of robots in tight spaces. In this paper, we present a new method for perceptive planning for multilegged robots, which generates body poses, footholds, and swing trajectories for collision avoidance. Measurements from an onboard depth camera are used to create a three‐dimensional map of the terrain around the robot. We randomly sample body poses then smooth the resulting trajectory while satisfying several constraints, such as robot kinematics and collision avoidance. Footholds and swing trajectories are computed based on the terrain, and the robot body pose is optimized to ensure stable locomotion while not colliding with the environment. Our method is designed to run online on a real robot and generate trajectories several meters long. We first tested our algorithm in several simulations with varied confined spaces using the quadrupedal robot ANYmal. We also simulated experiments with the hexapod robot Weaver to demonstrate applicability to different legged robot configurations. Then, we demonstrated our whole‐body planner in several online experiments both indoors and in realistic scenarios at an emergency rescue training facility. ANYmal, which has a nominal standing height of 80 cm and a width of 59 cm, navigated through several representative disaster areas with openings as small as 60 cm. Three‐meter trajectories were replanned with 500 ms update times.     

Motion strategies for exploration and map building under uncertainty with multiple heterogeneous robots

In this paper, we present a multi-robot exploration strategy for map building. We consider an indoor structured environment and a team of robots with different sensing and motion capabilities. We combine geometric and probabilistic reasoning to propose a solution to our problem. We formalize the proposed solution using stochastic dynamic programming (SDP) in states with imperfect information. Our modeling can be considered as a partially observable Markov decision process (POMDP), which is optimized using SDP. We apply the dynamic programming technique in a reduced search space that allows us to incrementally explore the environment. We propose realistic sensor models and provide a method to compute the probability of the next observation given the current state of the team of robots based on a Bayesian approach. We also propose a probabilistic motion model, which allows us to take into account errors (noise) on the velocities applied to each robot. This modeling also allows us to simulate imperfect robot motions, and to estimate the probability of reaching the next state given the current state. We have implemented all our algorithms and simulations results are presented.     

Real-Time Active SLAM and Obstacle Avoidance for an Autonomous Robot Based on Stereo Vision

Abstract

In this article, the problem of real-time robot exploration and map building (active SLAM) is considered. A single stereo vision camera is exploited by a fully autonomous robot to navigate, localize itself, define its surroundings, and avoid any possible obstacle in the aim of maximizing the mapped region following the optimal route. A modified version of the so-called cognitive-based adaptive optimization algorithm is introduced for the robot to successfully complete its tasks in real time and avoid any local minima entrapment. The method’s effectiveness and performance were tested under various simulation environments as well as real unknown areas with the use of properly equipped robots.     

Effective landmark placement for accurate and reliable mobile robot navigation

Being able to navigate accurately is one of the fundamental capabilities of a mobile robot to effectively execute a variety of tasks including docking, transportation, and manipulation. As real-world environments often contain changing or ambiguous areas, existing features can be insufficient for mobile robots to establish a robust navigation behavior. A popular approach to overcome this problem and to achieve accurate localization is to use artificial landmarks. In this paper, we consider the problem of optimally placing such artificial landmarks for mobile robots that repeatedly have to carry out certain navigation tasks. Our method aims at finding the minimum number of landmarks for which a bound on the maximum deviation of the robot from its desired trajectory can be guaranteed with high confidence. The proposed approach incrementally places landmarks utilizing linearized versions of the system dynamics of the robot, thus allowing for an efficient computation of the deviation guarantee. We evaluate our approach in extensive experiments carried out both in simulations and with real robots. The experiments demonstrate that our method outperforms other approaches and is suitable for long-term operation of mobile robots.     

未知环境下多机器人搜捕策略研究

针对在未知环境下多机器人围捕入侵者所存在的问题,提出了基于occupancy grid方法构造并合成环境地图指导单个机器人以分散搜索、抛物线模型预测并追踪入侵者、以及多机器人基于leader的可重构队形结构进行围捕的策略,使未知环境的地图构造和对入侵者追踪搜索过程得以同步完成,降低了机器人团队对环境的依赖,对未知环境具有较高的适应能力.最后通过仿真实验验证了该策略的正确性、有效性和鲁棒性.     

Heterogeneous Teams of Modular Robots for Mapping and Exploration

In this article, we present the design of a team of heterogeneous, centimeter-scale robots that collaborate to map and explore unknown environments. The robots, called Millibots, are configured from modular components that include sonar and IR sensors, camera, communication, computation, and mobility modules. Robots with different configurations use their special capabilities collaboratively to accomplish a given task. For mapping and exploration with multiple robots, it is critical to know the relative positions of each robot with respect to the others. We have developed a novel localization system that uses sonar-based distance measurements to determine the positions of all the robots in the group. With their positions known, we use an occupancy grid Bayesian mapping algorithm to combine the sensor data from multiple robots with different sensing modalities. Finally, we present the results of several mapping experiments conducted by a user-guided team of five robots operating in a room containing multiple obstacles.     

Multi-robot olfactory search in structured environments

This paper presents a cooperative distributed approach for searching odor sources in unknown structured environments with multiple mobile robots. While searching and exploring the environment, the robots independently generate on-line local topological maps and by sharing them with each other they construct a global map. The proposed method is a decentralized frontier based algorithm enhanced by a cost/utility evaluation function that considers the odor concentration and airflow at each frontier. Therefore, frontiers with higher probability of containing an odor source will be searched and explored first. The method also improves path planning of the robots for the exploration process by presenting a priority policy. Since there is no global positioning system and each robot has its own coordinate reference system for its localization, this paper uses topological graph matching techniques for map merging. The proposed method was tested in both simulation and real world environments with different number of robots and different scenarios. The search time, exploration time, complexity of the environment and number of double-visited map nodes were investigated in the tests. The experimental results validate the functionality of the method in different configurations.     

Dynamic multi-robot team reconfiguration using weighted voting games

We consider the problem of dynamic reconfiguration of robot teams when they encounter obstacles while navigating in formation, in an initially unknown environment. We have used a framework from coalition game theory called weighted voting games to analyse this problem and proposed two heuristics that can appropriately partition a robot team into sub-teams. We have experimentally verified our technique on teams of e-puck robots of different sizes and with different obstacle geometries, both on the Webots simulator and on physical robots. We have also shown that our technique performs faster and generates considerably fewer partitions than an existing robot coalition formation algorithm.     

Path planning of wheeled mobile robot with simultaneous free space locating capability

This paper presents a hybrid path planning algorithm for the design of autonomous vehicles such as mobile robots. The hybrid planner is based on Potential Field method and Voronoi Diagram approach and is represented with the ability of concurrent navigation and map building. The system controller (Look-ahead Control) with the Potential Field method guarantees the robot generate a smooth and safe path to an expected position. The Voronoi Diagram approach is adopted for the purpose of helping the mobile robot to avoid being trapped by concave environment while exploring a route to a target. This approach allows the mobile robot to accomplish an autonomous navigation task with only an essential exploration between a start and goal position. Based on the existing topological map the mobile robot is able to construct sub-goals between predefined start and goal, and follows a smooth and safe trajectory in a flexible manner when stationary and moving obstacles co-exist.     

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.     

Research into the application of AI robots in community home leisure interaction

This paper focuses on comprehensive application of artificial intelligence robots for community-based leisure interaction. We propose a multiple-layer perceptron network to design and implement the intelligent interactive home robot system, which includes establishment of an environment map, autonomous navigation, obstacle-avoidance control and human–machine interaction, to complete the positioning and perception functions required by the robot in the home environment. With this system, community residents use an interactive interface to manipulate robots remotely and create an environmental map. In order for the robot to adapt in this changing environment, the robot needs to have a completely autonomous navigation and obstacle-avoidance-control system. In this study, a long-distance obstacle-avoidance fuzzy system and a short-distance anti-fall obstacle-avoidance fuzzy system were used to enable the robot to accommodate unforeseen changes. This technology proved itself capable of navigating a home environment, ensuring that the robot could instantaneously dodge nearby obstacles and correcting the robot’s path of travel. At the same time, it could prevent the robot from falling off a high dropping point and thereby effectively control the robot’s movement trajectory. After combining the above-mentioned multi-sensor and image recognition functions, the intelligent interactive home robot showed that it clearly has the ability to integrate vision, perception and interaction, and we were able to verify that the robot has the necessary adaptability in changing environments and that the design of such interactive robots can be an asset in the home.