The trajectory planning for a fleet of automated guided vehicles (AGVs) on a roadmap is commonly referred to as the multi-agent path finding (MAPF) problem, the solution to which dictates each AGV's spatial and temporal location until it reaches its goal without collision. When executing MAPF plans in dynamic workspaces, AGVs can be frequently delayed, e.g., due to encounters with humans or third-party vehicles. If the remainder of the AGVs keeps following their individual plans, synchrony of the fleet is lost and some AGVs may pass through roadmap intersections in a different order than originally planned. Although this could reduce the cumulative route completion time of the AGVs, generally, a change in the original ordering can cause conflicts, such as deadlocks. In practice, synchrony is therefore often enforced by using a MAPF execution policy employing, e.g., an action dependency graph (ADG) to maintain ordering. To safely re-order without introducing deadlocks, we present the concept of the switchable action dependency graph (SADG). Using the SADG, we formulate a comparatively low-dimensional mixed-integer linear program that repeatedly re-orders AGVs in a recursively feasible manner, thus maintaining deadlock-free guarantees, while dynamically minimizing the cumulative route completion time of all AGVs. Various simulations validate the efficiency of our approach when compared to the original ADG method as well as robust MAPF solution approaches.

Several successful approaches exist for solving the complex problem of multi-robot planning and coordination. Due to the lack of adequate benchmarking tools, comparing these approaches and judging their suitability for use in realistic scenarios is currently difficult. Therefore, we propose an open-source benchmark suite that aims to close this gap. Unlike existing benchmarks, our approach uses full-stack multi-robot navigation systems in realistic 3D simulated environments from the intralogistic and household domains. Using the open-source frameworks ROS 2, Gazebo and RMF allows the user to add other robot platforms easily. The framework provides easy-to-use abstractions, typical metrics and interfaces to several established planning libraries for multi-robot systems. With all these features, our framework successfully aids practitioners and researchers in comparing multi-robot planning and coordination systems to the state of the art. Our experiments show how the proposed benchmark simplifies gaining insights on relevant close to real-life robotics use cases.

In this paper, we address the problem of detecting intruders in complex bidimensional environments with a team of robots arranged in line formations called sweep lines. Sweep lines are used to coordinate the motion of multiple robots and guarantee the detection of any number of arbitrarily fast intruders, even when each robot has a limited sensor footprint. We present a formalization of the problem, coined Line-Clear, which requires the computation of sweep schedules to coordinate the motion of multiple sweep lines using the fewest robots possible. We provide a proof of NP-hardness of the general Line-Clear problem based on results from graph searching. An algorithm to compute sweep schedules for simply connected environments, which additionally guarantees that the cleared area is connected and not recontaminated, is then presented. We analyze its complexity formally and in simulation experiments and present solutions for a number of subproblems required for an implementation of the algorithm. The analysis provides a formal criterion for when the algorithm runs in polynomial time and the experiments indicate that this criterion may be satisfied for most environments in practice.

We introduce RoomsSeg, a novel method for segmenting occupancy grid maps into regions that represent rooms and corridors in the real world. The segmentation is utilized for systematic room-by-room cleaning on autonomous vacuum cleaners running in private homes. RoomsSeg is based on automated clutter removal and watershed segmentation on grid maps. Segmented regions are merged into rooms by semantic decision rules. Presented experimental results clearly indicate the efficiency and accuracy of the approach when compared with state of the art methods. When deployed on cleaning robots, a substantial decrease in mission time can be achieved.

Abstract We propose a visualization system for incident commanders (ICs) in urban search and rescue scenarios that supports path planning in post‐disaster structures. Utilizing point cloud data acquired from unmanned robots, we provide methods for the assessment of automatically generated paths. As data uncertainty and a priori unknown information make fully automated systems impractical, we present the IC with a set of viable access paths, based on varying risk factors, in a 3D environment combined with visual analysis tools enabling informed decision making and trade‐offs. Based on these decisions, a responder is guided along the path by the IC, who can interactively annotate and reevaluate the acquired point cloud and generated paths to react to the dynamics of the situation. We describe visualization design considerations for our system and decision support systems in general, technical realizations of the visualization components, and discuss the results of two qualitative expert evaluation; one online study with nine search and rescue experts and an eye‐tracking study in which four experts used the system on an application case.

In this work we are investigating reactive avoidance techniques which can be used on board of a small quadcopter and which do not require absolute localization. We propose a local map representation which can be updated with proprioceptive sensors. The local map is centred around the robot and uses spherical coordinates to represent a point cloud. The local map is updated using a depth sensor, the Inertial Measurement Unit and a registration algorithm. We propose an extension of the Dynamic Window Approach to compute a velocity vector based on the current local map. We propose to use an OctoMap structure to compute a 2-pass A* which provide a path which is converted to a velocity vector. Both approaches are reactive as they only make use of local information. The algorithms were evaluated in a simulator which offers a realistic environment, both in terms of control and sensors. The results obtained were also validated by running the algorithms on a real platform.

In autonomous multirobot systems one of the concerns is how to prevent collisions between the individual robots. One approach to this problem involves finding coordinated trajectories from start to destination for all the robots and then letting the robots follow the preplanned coordinated trajectories. A widely used practical method for finding such coordinated trajectories is “classical” prioritized planning, where robots plan sequentially one after another. This method has been shown to be effective in practice, but it is incomplete (i.e., there are solvable problem instances that the algorithm fails to solve) and it has not yet been formally analyzed under what circumstances is the method guaranteed to succeed. Further, prioritized planning is a centralized algorithm, which makes the method unsuitable for decentralized multirobot systems.

Autonomous robot teams that simultaneously dispatch transportation tasks are playing a more and more important role in the industry. In this paper we consider the multi-robot motion planning problem in large robot teams and present a decoupled approach by combining decentralized path planning methods and swarm technologies. Instead of a central coordination, a proper behavior which is directly selected according to the context is used by the robot to keep cooperating with others and to resolve path collisions. We show experimentally that the quality of solutions and the scalability of our method are significantly better than those of conventional decoupled path planning methods. Furthermore, compared to conventional swarm approaches, our method can be widely applied in large-scale environments.

We consider the problem of computing trajectories for a team of of coordinated unmanned aerial vehicles (UAVs) in large and complex 2D and 2.5D environments to guarantee the detection of any evading target. Our approach is based on the coordination of 2D sweep lines that move through the environment to clear it from all contamination, representing the possibility of a target being located in an area, and thereby detecting all targets. The trajectories of the UAVs are computed from the motion of these sweep lines. Low cost coordination strategies of the UAV sweep lines are computed in 2D and simply-connected polygonal environments and then converted to strategies capable of clearing multiply-connected 2.5D environments. We present simulation experiments with maps of real and artificial environments and demonstrate the execution of strategies with simulated quadrotors using the Robot Operating System (ROS) framework. The algorithms used for the experiments are made available on a public repository.

In this paper we consider the problem of searching for an arbitrarily smart and fast evader in a large environment with a team of unmanned aerial vehicles (UAVs) while providing guarantees of detection. Our emphasis is on the fast execution of efficient search strategies that minimize the number of UAVs and the search time. We present the first approach for computing fast guaranteed search strategies utilizing additional searchers to speed up the execution time and thereby enabling large scale UAV search. In order to scale to very large environments when using UAVs one would either have to overcome the energy limitations of UAVs or pay the cost of utilizing additional UAVs to speed up the search. Our approach is based on coordinating UAVs on sweep lines, covered by the UAV sensors, that move simultaneously through an environment. We present some simulation results that show a significant reduction in execution time when using multiple UAVs and a demonstration of a real system with three AR.Drone 2.0.

Efficient task allocation with timing constraints to a team of possibly heterogeneous robots is a challenging problem with application, e. g., in search and rescue. In this paper a mixed-integer linear programming (MILP) approach is proposed for assigning heterogeneous robot teams to the simultaneous completion of sequences of tasks with specific requirements such as completion deadlines. For this purpose our approach efficiently combines the strength of state of the art mixed-integer linear programming (MILP) solvers with human expertise in mission scheduling. We experimentally show that simple and intuitive inputs by a human user have substantial impact on both computation time and quality of the solution. The presented approach can in principle be applied to quite general missions for robot teams with human supervision.

We address the problem of searching for moving targets in large outdoor environments represented by height maps. To solve the problem we present a complete system that computes from an annotated height map a graph representation and search strategies based on worst-case assumptions about all targets. These strategies are then used to compute a schedule and task assignment for all agents. We improve the graph construction from previous work and for the first time present a method that computes a schedule to minimize the execution time. For this we consider travel times of agents determined by a path planner on the height map. We demonstrate the entire system in a real environment with an area of 700,000m2in which eight human agents search for two intruders using mobile computing devices (iPads). To the best of our knowledge this is the first demonstration of a search system applied to such a large environment.

Robust and reliable localization is a fundamental prerequisite for many applications of mobile robots. Although there exist many solutions to the localization problem, structurally symmetrical or featureless environments can prevent different locations from being distinguishable given the data obtained with the robot's sensors. Such ambiguities typically make localization approaches more likely to fail. In this paper, we investigate how artificial landmarks can be utilized to reduce the ambiguity in the environment. We present a practical approach to compute a configuration of indistinguishable landmarks that decreases the overall ambiguity and thus increases the robustness of the localization process. We evaluate our approach in different environments based on real data and in simulation. Our results demonstrate that our approach improves the localization performance of the robot and outperforms other landmark selection approaches.

Autonomous robot teams that simultaneously dispatch transportation tasks are playing more and more an important role in present logistic centers and manufacturing plants. In this paper we consider the problem of robot motion planning for large robot teams in the industrial domain. We present adaptive road map optimization (ARMO) that is capable of adapting the road map whenever the environment has changed. Based on linear programming, ARMO computes an optimal road map configuration according to environmental constraints (including human whereabouts) and the demand for transportation tasks from loading stations in the plant. For detecting dynamic changes, the environment is described by a grid map augmented with a hidden Markov model (HMM). We show experimentally that ARMO outperforms decoupled planning in terms of computation time and time needed for task completion.

Autonomous robot navigation in out-door scenarios gains increasing importance in various growing application areas. Whereas in non-urban domains such as deserts the problem of successful GPS-based navigation appears to be almost solved, navigation in urban domains particularly in the close vicinity of buildings is still a challenging problem. In such situations GPS accuracy significantly drops down due to multiple signal reflections with larger objects causing the so-called multipath error. In this paper we contribute a novel approach for incorporating multipath errors into the conventional GPS sensor model by analyzing environmental structures from online generated point clouds. The approach has been validated by experimental results conducted with an all-terrain robot operating in scenarios requiring close-to-building navigation. Presented results show that positioning accuracy can significantly be improved within urban domains.

In this paper we present an approach for a pursuit-evasion problem that considers a 2.5d environment represented by a height map. Such a representation is particularly suitable for large-scale outdoor pursuit-evasion, captures some aspects of 3d visibility and can include target heights. In our approach we construct a graph representation of the environment by sampling strategic locations and computing their detection sets, an extended notion of visibility. From the graph we compute strategies using previous work on graph-searching. These strategies are used to coordinate the robot team and to generate paths for all robots using an appropriate classification of the terrain. In experiments we investigate the performance of our approach and provide examples including a sample map with multiple loops and elevation plateaus and two realistic maps, a village and a mountain range. To the best of our knowledge the presented approach is the first viable solution to 2.5d pursuit-evasion with height maps.

In this paper, we address the problem of creating an objective benchmark for comparing SLAM approaches. We propose a framework for analyzing the results of SLAM approaches based on a metric for measuring the error of the corrected trajectory. The metric uses only relative relations between poses and does not rely on a global reference frame. The idea is related to graph-based SLAM approaches in the sense that it considers the energy needed to deform the trajectory estimated by a SLAM approach to the ground truth trajectory. Our method enables us to compare SLAM approaches that use different estimation techniques or different sensor modalities since all computations are made based on the corrected trajectory of the robot. We provide sets of relative relations needed to compute our metric for an extensive set of datasets frequently used in the SLAM community. The relations have been obtained by manually matching laser-range observations. We believe that our benchmarking framework allows the user an easy analysis and objective comparisons between different SLAM approaches.

To coordinate a team of robots for exploration is a challenging problem, particularly in large areas as for example the devastated area after a disaster. This problem can generally be decomposed into task assignment and multi-robot path planning. In this paper, we address both problems jointly. This is possible because we reduce significantly the size of the search space by utilizing RFID tags as coordination points. The exploration approach consists of two parts: a stand-alone distributed local search and a global monitoring process which can be used to restart the local search in more convenient locations. Our results show that the local exploration works for large robot teams, particularly if there are limited computational resources. Experiments with the global approach showed that the number of conflicts can be reduced, and that the global coordination mechanism increases significantly the explored area.

To autonomously navigate on rough terrain is a challenging problem for mobile robots, requiring the ability to decide whether parts of the environment can be traversed or have to be bypassed, which is commonly known as obstacle negotiation (ON). In this video we show the robot's ability to map, detect and negotiate obstacles. The first part shows the robot exploring a test arena, that contains a pallet and a ramp, that have to be traversed. The second part demonstrates the autonomous stair climbing skill. The planning process uses a new concept called behavior maps, that has been developed to support planning while integrating obstacle negotiation.

To autonomously navigate on rough terrain is a challenging problem for mobile robots, requiring the ability to decide whether parts of the environment can be traversed or have to be bypassed, which is commonly known as Obstacle Negotiation (ON). In this paper, we introduce a planning framework that extends ON to the general case, where different types of terrain classes directly map to specific robot skills, such as climbing stairs and ramps. This extension is based on a new concept called behavior maps, which is utilized for the planning and execution of complex skills. Behavior maps are directly generated from elevation maps, i.e. two-dimensional grids storing in each cell the corresponding height of the terrain surface, and a set of skill descriptions. Results from extensive experiments are presented, showing that the method enables the robot to explore successfully rough terrain in real-time, while selecting the optimal trajectory in terms of costs for navigation and skill execution.

One primary goal in rescue robotics is to deploy a team of robots for coordinated victim search after a disaster. This requires robots to perform sub- tasks, such as victim detection, in real-time. Human detection by computationally cheap techniques, such as color thresholding, turn out to produce a large number of false-positives. Markov Random Fields (MRFs) can be utilized to combine the local evidence of multiple weak classifiers in order to improve the detection rate. However, inference in MRFs is computational expensive. In this paper we present a novel approach for the genetic optimizing of the building process of MRF models. The genetic algorithm determines offline relevant neighborhood relations with respect to the data, which are then utilized for generating efficient MRF models from video streams during runtime. Experimental results clearly show that compared to a Support Vector Machine (SVM) based classifier, the optimized MRF models significantly reduce the false-positive rate. Furthermore, the optimized models turned out to be up to five times faster then the non-optimized ones at nearly the same detection rate.

We consider the problem of Decentralized Simultaneous Localization And Mapping (DSLAM) for pedestrians in the context of Urban Search And Rescue (USAR). In this context, DSLAM is a challenging task. First, data exchange fails due to cut off communication links. Second, loop-closure is cumbersome due to the fact that firefighters will intentionally try to avoid performing loops when facing the reality of emergency response, e.g. while they are searching for victims. In this paper, we introduce a solution to this problem based on the non-selfish sharing of information between pedestrians for loop-closure. We introduce a novel DSLAM method which is based on data exchange and association via RFID technology, not requiring any radio communication. The approach has been evaluated in both semi-indoor and outdoor environments. The presented results show that sharing information between single pedestrians allows to optimize globally their individual paths, even if they are not able to communicate directly.

Robot search and rescue is a time critical task, i.e. a large terrain has to be explored by multiple robots within a short amount of time. The efficiency of exploration depends mainly on the coordination between the robots and hence on the reliability of communication, which considerably suffers under the hostile conditions encountered after a disaster. Furthermore, rescue robots have to generate a map of the environment which has to be sufficiently accurate for reporting the locations of victims to human task forces. Basically, the robots have to solve autonomously in real-time the problem of simultaneous localization and mapping (SLAM). This paper proposes a novel method for real-time exploration and SLAM based on RFID tags that are autonomously distributed in the environment. We utilized the algorithm of Lu and Milios for calculating globally consistent maps from detected RFID tags. Furthermore we show how RFID tags can be used for coordinating the exploration of multiple robots. Results from experiments conducted in the simulation and on a robot show that our approach allows the computationally efficient construction of a map within harsh environments, and coordinated exploration of a team of robots

For a robot situated in a dynamic real world environment the knowledge of its position and orientation is very advantageous and sometimes essential for carrying out a given task. Particularly, one would appreciate a robust, accurate and efficient self-localization method which allows a global localization of the robot. In certain polygonal environments a laser based localization method is capable of combining all these properties by correlating observed lines with an a priori line model of the environment [J. Gutmann et al., 2001]. However, often line features can rather be detected by a vision system than by a laser range finder. For this reason we propose an extension of the laser based approach for the simultaneous use with lines detected by an omni-directional camera. The approach is evaluated in the RoboCup domain and experimental evidence is given for its robustness, accuracy and efficiency, as well as for its capability of global localization.

Robotic soccer is a challenging research domain because many different research areas have to be addressed in order to create a successful team of robot players. The paper presents the CS Freiburg team, the winner in the middle-size league at RoboCup 1998, 2000, and 2001. The paper focuses on multiagent coordination for both perception and action. The contributions of the paper are new methods for tracking ball and players observed by multiple robots, team coordination methods for strategic team formation and dynamic role assignment; a rich set of basic skills allowing robots to respond to a large range of situations in an appropriate way, and an action-selection method based on behavior networks, as well as a method to learn the skills and their selection. As demonstrated by evaluations of the different methods and by the success of the team, these methods permit the creation of a multirobot group which is able to play soccer successfully. In addition, the developed methods promise to advance the state of the art in the multirobot field.