Alexander Kleiner

ICRA Conference 2023 Conference Paper

A Benchmark for Multi-Robot Planning in Realistic, Complex and Cluttered Environments

• Simon Schaefer
• Luigi Palmieri
• Lukas Heuer
• Rüdiger Dillmann
• Sven Koenig
• Alexander Kleiner

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.

IROS Conference 2017 Conference Paper

A solution to room-by-room coverage for autonomous cleaning robots

• Alexander Kleiner
• Rodrigo Baravalle
• Andreas Kolling
• Pablo Pilotti
• Mario Munich

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.

ICAPS Conference 2015 Conference Paper

Complete Decentralized Method for On-Line Multi-Robot Trajectory Planning in Well-formed Infrastructures

• Michal Cáp
• Jirí Vokrínek
• Alexander Kleiner

We consider a system consisting of multiple mobile robots in which the user can at any time issue relocation tasks ordering one of the robots to move from its current location to a given destination location. In this paper, we deal with the problem of finding a trajectory for each such relocation task that avoids collisions with other robots. The chosen robot plans its trajectory so as to avoid collision with other robots executing tasks that were issued earlier. We prove that if the destination of each task is an endpoint in a so-called well-formed infrastructure, then this mechanism is guaranteed to always succeed and provide a trajectory for the robot that reaches the destination without any collisions. The time-complexity of the approach is only quadratic in the number of robots. We demonstrate the applicability of the presented method on several real-world maps and compare its performance against a popular reactive approach that attempts to solve the collisions locally. Besides being dead-lock free, the presented approach generates trajectories that reach the goal significantly faster (up to 48% improvement) than the trajectories resulting from local collision avoidance.

ICRA Conference 2014 Conference Paper

Behavior-based multi-robot collision avoidance

• Dali Sun
• Alexander Kleiner
• Bernhard Nebel

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.

IROS Conference 2013 Conference Paper

Fast guaranteed search with unmanned aerial vehicles

• Andreas Kolling
• Alexander Kleiner
• Piotr Rudol

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.

IROS Conference 2013 Conference Paper

Fast task-sequence allocation for heterogeneous robot teams with a human in the loop

• Karen Petersen
• Alexander Kleiner
• Oskar von Stryk

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.

ICRA Conference 2013 Conference Paper

Guaranteed search with large teams of unmanned aerial vehicles

• Alexander Kleiner
• Andreas Kolling

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.

AAMAS Conference 2013 Conference Paper

RMASBench: A Benchmarking System for Multi-Agent Coordination in Urban Search and Rescue

• Fabio Maffioletti
• Riccardo Reffato
• Alessandro Farinelli
• Alexander Kleiner
• Sarvapali Ramchurn
• Bing Shi

This demonstration paper illustrates RMASBench, a new benchmarking system based on the RoboCup Rescue Agent simulator. The aim of the system is to facilitate benchmarking of coordination approaches in controlled settings for dynamic rescue scenarios. In particular, the key features of the systems are: i) programming interfaces to plug-in coordination algorithms without the need for implementing and tuning low-level agents’ behaviors, ii) implementations of state-of-the art coordination approaches: DSA and Max- Sum, iii) a large scale crowd simulator, which exploits GPUs parallel architecture, to simulate the behaviour of thousands of agents in real time.

AAMAS Conference 2013 Conference Paper

RMASbench: Benchmarking Dynamic Multi-Agent Coordination in Urban Search and Rescue

• Alexander Kleiner
• Alessandro Farinelli
• Sarvapali Ramchurn
• Bing Shi
• Fabio Maffioletti
• Riccardo Reffato

IJCAI Conference 2011 Conference Paper

A Mechanism for Dynamic Ride Sharing Based on Parallel Auctions

• Alexander Kleiner
• Bernhard Nebel
• Vittorio Amos Ziparo

Car pollution is one of the major causes of green-house emissions, and traffic congestion is rapidly becoming a social plague. Dynamic Ride Sharing (DRS) systems have the potential to mitigate this problem by computing plans for car drivers, e. g. commuters, allowing them to share their rides. Existing efforts in DRS are suffering from the problem that participants are abandoning the system after repeatedly failing to get a shared ride. In this paper we present an incentive compatible DRS solution based on auctions. While existing DRS systems are mainly focusing on fixed assignments that min- imize the totally travelled distance, the presented approach is adaptive to individual preferences of the participants. Furthermore, our system allows to tradeoff the minimization of Vehicle Kilometers Travelled (VKT) with the overall probability of successful ride-shares, which is an important fea- ture when bootstrapping the system. To the best of our knowledge, we are the first to present a DRS solution based on auctions using a sealed-bid second price scheme.

IROS Conference 2011 Conference Paper

ARMO: Adaptive road map optimization for large robot teams

• Alexander Kleiner
• Dali Sun
• Daniel Meyer-Delius

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.

ICRA Conference 2011 Conference Paper

Computing and executing strategies for moving target search

• Andreas Kolling
• Alexander Kleiner
• Michael Lewis 0001
• Katia P. Sycara

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, 000m 2 in 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.

ICRA Conference 2011 Conference Paper

Using artificial landmarks to reduce the ambiguity in the environment of a mobile robot

• Daniel Meyer-Delius
• Maximilian Beinhofer
• Alexander Kleiner
• Wolfram Burgard

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.

AAMAS Conference 2010 Conference Paper

Decentralized Hash Tables For Mobile Robot Teams Solving Intra-Logistics Tasks

• Dali Sun
• Alexander Kleiner
• Christian Schindelhauer

Although a remarkably high degree of automation has beenreached in production and intra-logistics nowadays, humanlabor is still used for transportation using handcarts andforklifts. High labor cost and risk of injury are the undesirable consequences. Alternative approaches in automatedwarehouses are fixed installed conveyors installed either overhead or floor-based. The drawback of such solutions is thelack of flexibility, which is necessary when the productionlines of the company change. Then, such an installation hasto be re-built. In this paper, we propose a novel approach of decentralized teams of autonomous robots performing intra-logisticstasks using distributed algorithms. Centralized solutionssuffer from limited scalability and have a single point of failure. The task is to transport material between stations keeping the communication network structure intact and mostimportantly, to facilitate a fair distribution of robots amongloading stations. Our approach is motivated by strategiesfrom peer-to-peer-networks and mobile ad-hoc networks. Inparticular we use an adapted version of distributed heterogeneous hash tables (DHHT) for distributing the tasks andlocalized communication. Experimental results presented inthis paper show that our method reaches a fair distributionof robots over loading stations.

ICRA Conference 2010 Conference Paper

Improved GPS sensor model for mobile robots in urban terrain

• Daniel Maier 0001
• Alexander Kleiner

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.

IROS Conference 2010 Conference Paper

Pursuit-evasion in 2. 5d based on team-visibility

• Andreas Kolling
• Alexander Kleiner
• Michael Lewis 0001
• Katia P. Sycara

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.

IROS Conference 2009 Conference Paper

A comparison of SLAM algorithms based on a graph of relations

• Wolfram Burgard
• Cyrill Stachniss
• Giorgio Grisetti
• Bastian Steder
• Rainer Kümmerle
• Christian Dornhege
• Michael Ruhnke
• Alexander Kleiner

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.

IROS Conference 2007 Conference Paper

Behavior maps for online planning of obstacle negotiation and climbing on rough terrain

• Christian Dornhege
• Alexander Kleiner

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.

IROS Conference 2007 Conference Paper

Decentralized SLAM for pedestrians without direct communication

• Alexander Kleiner
• Dali Sun

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.

IROS Conference 2007 Conference Paper

Fully autonomous planning and obstacle negotiation on rough terrain using behavior maps

• Christian Dornhege
• Alexander Kleiner

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.

IROS Conference 2007 Conference Paper

Genetic MRF model optimization for real-time victim detection in search and rescue

• Alexander Kleiner
• Rainer Kümmerle

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.

ICRA Conference 2007 Conference Paper

RFID-Based Exploration for Large Robot Teams

• Vittorio A. Ziparo
• Alexander Kleiner
• Bernhard Nebel
• Daniele Nardi

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.

IROS Conference 2006 Conference Paper

RFID Technology-based Exploration and SLAM for Search And Rescue

• Alexander Kleiner
• Johann Prediger
• Bernhard Nebel

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

IROS Conference 2003 Conference Paper

Self-localization in dynamic environments based on laser and vision data

• Erik chulenburg
• Thilo Weigel
• Alexander Kleiner

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.