• English
• Deutsch

• Albert-Ludwigs-Universität Freiburg
• Technische Fakultät
• Institut für Informatik

Diese Seite ist nur auf Englisch verfügbar.

Alexander Kleiner – Publications

Also see detailed publication list

(Show all abstracts) (Hide all abstracts)

2016

• Christian Dornhege, Alexander Kleiner, Andreas Hertle and Andreas Kolling.
  Multirobot Coverage Search in Three Dimensions.
  Journal of Field Robotics 33 (4), pp. 537-558. 2016.
  (Show abstract) (Hide abstract) (PDF)
  

  Searching for objects and observing parts of a known environment efficiently is a fundamental problem in many real-world robotic applications, e.g., household robots searching for objects, inspection robots searching for leaking pipelines, and rescue robots searching for survivors after a disaster. We consider the problem of identifying and planning sequences of sensor locations from which robot sensors can observe and cover complex three-dimensional (3D) environments while traveling only short distances. Our approach is based on sampling and ranking a large number of sensor locations for a 3D environment represented by an OctoMap. The visible area from these sensor locations induces a minimal partition of the 3D environment that we exploit for planning sequences of sensor locations with short travel times efficiently. We present multiple planning algorithms designed for single robots and for multirobot teams. These algorithms include variants that are greedy, optimal, or based on decomposing the planning problem into a set cover and traveling salesman problem. We evaluated and compared these algorithms empirically in simulation and real-world robot experiments with up to four robots. Our results demonstrate that, despite the intractability of the overall problem, computing and executing effective solutions for multirobot coverage search in real 3D environments is feasible and ready for real-world applications.

2014

• Dali Sun, Alexander Kleiner and Bernhard Nebel.
  Behavior-based Multi-Robot Collision Avoidance.
  In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA-14), pp. 1668-1673. 2014.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Autonomous robot teams that simultaneously disatch 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.

2013

• Christian Dornhege, Alexander Kleiner and Andreas Kolling.
  Coverage Search in 3D.
  In Proceedings of the Symposium on Safety Security and Rescue Robotics (SSRR). 2013.
  (PDF) (BIB)
  

• Christian Dornhege and Alexander Kleiner.
  A Frontier-Void-Based Approach for Autonomous Exploration in 3D.
  Advanced Robotics 27 (6). 2013.
  (BIB)
  

2011

• Christian Dornhege and Alexander Kleiner.
  A Frontier-Void-Based Approach for Autonomous Exploration in 3D.
  In Proceedings of the IEEE International Symposium on Safety, Security and Rescue Robotics (SSRR). 2011.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  We consider the problem of an autonomous robot searching for objects in unknown 3d space. Similar to the well known frontier-based exploration in 2d, the problem is to determine a minimal sequence of sensor viewpoints until the entire search space has been explored. We introduce a novel approach that combines the two concepts of voids, which are unexplored volumes in 3d, and frontiers, which are regions on the boundary between voids and explored space. Our approach has been evaluated on a mobile platform equipped with a manipulator searching for victims in a simulated USAR setup. First results indicate the real-world capability and search efficiency of the proposed method.

• Alexander Kleiner, Dali Sun and D. Meyer-Delius.
  ARMO: Adaptive Road Map Optimization for Large Robot Teams.
  In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS). 2011.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  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 in real time whenever the environment has changed. Based on linear programming, ARMO computes an optimal road map according to current environmental constraints (including human whereabouts) and the current demand for transportation tasks from loading stations in the plant. For detecting dynamic changes, the environment is describe 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.

• Alexander Kleiner, A. Kolling, K. Sycara and M. Lewis.
  Hierarchical Visibility for Guaranteed Search in Large-Scale Outdoor Terrain.
  Journal of Autonomous Agents and Multi-Agent Systems (JAAMAS). 2011.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Searching for moving targets in large environments is a challenging task that is relevant in several problem domains, such as capturing an invader in a camp, guarding security facilities, and searching for victims in large-scale search and rescue scenarios. The guaranteed search problem is to coordinate the search of a team of agents to guarantee the discovery of all targets. In this paper we present a self-contained solution to this problem in 2.5D real-world domains represented by digital elevation models (DEMs). We introduce hierarchical sampling on DEMs for selecting heuristically the close to minimal set of locations from which the entire surface of the DEM can be guarded. Locations are utilized to form a search graph on which search strategies for mobile agents are computed. For these strategies schedules are derived which include agent paths that are directly executable in the terrain. Presented experimental results demonstrate the performance of the method. The practical feasibility of our approach has been validated during a field experiment at the Gascola robot training site where teams of humans equipped with iPads successfully searched for adversarial and omniscient evaders. The field demonstration is the largest-scale implementation of a guaranteed search algorithm to date.

• Q. Hamp, L. Reindl and Alexander Kleiner.
  Lessons Learned from German Research for USAR.
  In Proc. of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR). 2011.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  We present lessons learned in USAR research within the framework of the German research project I-LOV. After three years of development first field tests have been carried out by professionals such as the Rapid Deployment Unit for Salvage Operations Abroad (SEEBA). We present results from evaluating search teams in simulated USAR scenarios equipped with newly developed technical search means and digital data input terminals developed in the I- LOV project. In particular, the bioradar, a ground-penetrating radar system for the detection of humanoid movements, a semi-active video probe for rubble pile exploration of more than 10 m length, and the decision support system FRIEDAA were evaluated and compared with conventional search methods. Results of this evaluation indicate that the developed technologies foster advantages in USAR, which are discussed in this paper.

• Alexander Kleiner, Bernhard Nebel and V.A. Ziparo.
  A Mechanism for Dynamic Ride Sharing based on Parallel Auctions.
  In Proc. of the 22th International Joint Conference on Artificial Intelligence (IJCAI). 2011.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  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. Ex- isting 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 minimize 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 feature 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.

• D. Meyer-Delius, M. Beinhofer, Alexander Kleiner and W. Burgard.
  Reducing the Ambiguity in the Environment by Placing Artificial Landmarks to Improve Mobile Robot Localization.
  In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA). 2011.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Robust and reliable localization is a fundamental prerequisite for successful robot navigation. Although there exist many solutions to the localization problem, environments can be inherently ambiguous so that different robot locations cannot to be distinguished using the sensors of the robot. This is particularly critical in comercial environments, for example in warehouses, containing long corridors and symmetric structures. This ambiguity makes localization approaches more likely to diverge or even prevent the pose of the robot from being uniquely estimated at all. In this paper we propose the utilization of artificial landmarks to reduce the inherent ambiguity in the environment, and present an efficient, localization-oriented approach to landmark placement. Our approach provides us with both the location and number of landmarks to be placed in order to improve the localization performance of the robot in a given environment. Experimental results show that by intelligently placing the landmarks we can improve the localization performance of the robot.

• A. Kolling, Alexander Kleiner, M. Lewis and K. Sycara.
  Computing and Executing Strategies for Moving Target Search.
  In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA). 2011.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  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,000m2 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.

• R. Kümmerle, B. Steder, Christian Dornhege, Alexander Kleiner, G. Grisetti and W. Burgard.
  Large Scale Graph-based SLAM using Aerial Images as Prior Information.
  Autonomous Robots 30, pp. 25-39. 2011.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  The problem of learning a map with a mobile robot has been intensively studied in the past and is usually referred to as the simultaneous localization and mapping (SLAM) problem. However, most existing solutions to the SLAM problem learn the maps from scratch and have no means for incorporating prior information. In this paper, we present a novel SLAM approach that achieves global consistency by utilizing publicly accessible aerial photographs as prior information. It inserts correspondences found between stereo and three-dimensional range data and the aerial images as constraints into a graph-based formulation of the SLAM problem. We evaluate our algorithm based on large real-world datasets acquired even in mixed in- and outdoor environments by comparing the global accuracy with state-of-the-art SLAM approaches and GPS. The experimental results demonstrate that the maps acquired with our method show increased global consistency.

2010

• Wei Mou and Alexander Kleiner.
  Online Learning Terrain Classification for Adaptive Velocity Control.
  In Proceedings of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR 2010). 2010.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Safe teleoperation during critical missions, such as urban search and rescue and bomb disposal, requires careful velocity control when different types of terrain are found in the scenario. This can particularly be challenging when mission time is limited and the operator’s field of view affected. This paper presents a method for online adapting robot velocities according to the terrain classification from vision and laser readings. The classifier adapts itself to illumination variations, and can be improved online given feedback from the operator.

• Andreas Kolling, Alexander Kleiner, Michael Lewis and Katia Sycara.
  Solving Pursuit-Evasion Problems on Height Maps.
  In IEEE International Conference on Robotics and Automation (ICRA 2010) Workshop: Search and Pursuit/Evasion in the Physical World: Efficiency, Scalability, and Guarantees (WSPE ICRA 2010). 2010.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  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. By allowing height information we not only capture some aspects of 3d visibility but can also consider target heights. In our approach we construct a graph representation of the environment by sampling points and their detection sets which extend the usual notion of visibility. Once a graph is constructed we compute strategies on this graph using a modification of previous work on graph-searching. This strategy is converted into robot paths that are planned on the height map by classifying the terrain appropriately. In experiments we investigate the performance of our approach and provide examples including a map of a small village with surrounding hills and a sample map with multiple loops and elevation plateaus. Experiments are carried out with varying sensing ranges as well as target and sensor heights. To the best of our knowledge the presented approach is the first viable solution to 2.5d pursuit-evasion with height maps.

• Daniel Maier and Alexander Kleiner.
  Improved GPS Sensor Model for Mobile Robots in Urban Terrain.
  In IEEE International Conference on Robotics and Automation (ICRA 2010), pp. 4385-4390. 2010.
  (Video).
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Autonomous robot navigation in outdoor 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 multi- path 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.

• Alexander Kleiner and Christian Dornhege.
  Mapping for the Support of First Responders in Critical Domains.
  Journal of Intelligent and Robotic Systems (JINT), pp. 1-29. 2010.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  In critical domains such as urban search and rescue (USAR), and bomb disposal, the deployment of teleoperated robots is essential to reduce the risk of first responder personnel. Teleoperation is a difficult task, particularly when controlling robots from an isolated safety zone. In general, the operator has to solve simultaneously the problems of mission planning, target identification, robot navigation, and robot control. We introduce a system to support teleoperated navigation with real-time mapping consisting of a two-step scan matching method that re-considers data associations during the search. The algorithm processes data from laser range finder and gyroscope only, thereby it is independent from the robot platform. Furthermore, we introduce a user-guided procedure for improving the global consistency of maps generated by the scan matcher. Globally consistent maps are computed by a graph-based maximum likelihood method that is biased by localizing crucial parts of the scan matcher trajectory on a prior given geo-tiff image. The approach has been implemented as an embedded system and extensively tested on robot platforms designed for teleoperation in critical situations, such as bomb disposal. Furthermore, the system was evaluated in a test maze by first responders during the Disaster City event in Texas 2008.

• Sören Schwertfeger, Adam Jacoff, Chris Scrapper, Johannes Pellenz and Alexander Kleiner.
  Evaluation of Maps using Fixed Shapes: The Fiducial Map Metric.
  In Proc. of the Int. Workshop on Performance Metrics for Intelligent Systems (PerMIS), pp. 344-351. NIST 2010.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Mapping is an important task for mobile robots. Assessing the quality of those maps is an open topic. A new approach on map evaluation is presented here. It makes use of artificial objects placed in the environment named "Fiducials". Using the known ground-truth positions and the positions of the fiducials identified in the map, a number of quality attributes can be assigned to that map. Depending on the application domain those attributes are weighed to compute a final score. During the 2010 NIST Response Robot Evaluation Exercise at Disaster City an area was populated with fiducials and different mapping runs were performed. The maps generated there are assessed in this paper demonstrating the Fiducial approach. Finally this map scoring algorithm is compared to other approaches found in literature.

• A. Kolling, Alexander Kleiner, M. Lewis and and K. Sycara.
  Pursuit-Evasion in 2.5d based on Team-Visibility.
  In Proceedings of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS 2010), pp. 4610-4616. 2010.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  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 points and computing detection sets, an extended notion of visibility. Moreover, the constructed graph captures overlaps of detection sets allowing for a coordinated team-based clearing of the environment with robots that move to the sampled points. Once a graph is constructed we compute strategies on it utilizing previous work on graph-searching. This is converted into robot paths that are planned on the height map by classifying the terrain appropriately. 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, one of a village and one of 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.

• Dali Sun, Alexander Kleiner and and C. Schindelhauer.
  Decentralized Hash Tables For Mobile Robot Teams Solving Intra-Logistics Tasks.
  In Proceedings of the 9th Int. Joint Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2010), pp. 923-930. 2010.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Although a remarkably high degree of automation has been reached in production and intra-logistics nowadays, human labor is still used for transportation using handcarts and forklifts. High labor cost and risk of injury are the undesirable consequences. Alternative approaches in automated warehouses are fixed installed conveyors installed either overhead or floor-based. The drawback of such solutions is the lack of flexibility, which is necessary when the production lines of the company change. Then, such an installation has to be re-built. In this paper, we propose a novel approach of decentralized teams of autonomous robots performing intra-logistics tasks using distributed algorithms. Centralized solutions suffer 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 most importantly, to facilitate a fair distribution of robots among loading stations. Our approach is motivated by strategies from peer-to-peer-networks and mobile ad-hoc networks. In particular we use an adapted version of distributed heterogeneous hash tables (DHHT) for distributing the tasks and localized communication. Experimental results presented in this paper show that our method reaches a fair distribution of robots over loading stations.

2009

• Alexander Kleiner, Chris Scrapper and Adam Jacoff.
  RoboCupRescue Interleague Challenge 2009: Bridging the gap between Simulation and Reality.
  In Proceedings of the Int. Workshop on Performance Metrics for Intelligent Systems (Permis 2009), pp. 123-129. NIST 2009.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Teleoperation is a difficult task, particularly when controlling robots from an isolated operator station. In general, the operator has to solve nearly blindly the problems of mission planning, target identification, robot navigation, and robot control at the same time. The goal of the proposed system is to support teleoperated navigation with real-time mapping. We present a novel scan matching technique that re-considers data associations during the search, enabling robust pose estimation even under varying roll and pitch angle of the robot enabling mapping on rough terrain. The approach has been implemented as an embedded system and extensively tested on robot platforms designed for teleoperation in critical situations, such as bomb disposal. Furthermore, the system has been evaluated in a test maze by first responders during the Disaster City event in Texas 2008. Finally, experiments conducted within different environments show that the system yields comparably accurate maps in real-time when compared to higher sophisticated offline methods, such as Rao-Blackwellized SLAM.

• Alexander Kleiner and Christian Dornhege.
  Operator-Assistive Mapping in Harsh Environments.
  In IEEE International Workshop on Safety, Security and Rescue Robotics (SSRR 2009), pp. 1-6. 2009.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Teleoperation is a difficult task, particularly when controlling robots from an isolated operator station. In general, the operator has to solve nearly blindly the problems of mission planning, target identification, robot navigation, and robot control at the same time. The goal of the proposed system is to support teleoperated navigation with real-time mapping. We present a novel scan matching technique that re-considers data associations during the search, enabling robust pose estimation even under varying roll and pitch angle of the robot enabling mapping on rough terrain. The approach has been implemented as an embedded system and extensively tested on robot platforms designed for teleoperation in critical situations, such as bomb disposal. Furthermore, the system has been evaluated in a test maze by first responders during the Disaster City event in Texas 2008. Finally, experiments conducted within different environments show that the system yields comparably accurate maps in real-time when compared to higher sophisticated offline methods, such as Rao-Blackwellized SLAM.

• Rainer Kümmerle, Bastian Steder, Christian Dornhege, Michael Ruhnke, Giorgio Grisetti, Cyrill Stachniss and Alexander Kleiner.
  On Measuring the Accuracy of SLAM Algorithms.
  Autonomous Robots 27 (4), pp. 387-407. 2009.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  In this paper, we address the problem of creating an objective benchmark for evaluating SLAM approaches. We propose a framework for analyzing the results of a SLAM approach based on a metric for measuring the error of the corrected trajectory. This metric uses only relative relations between poses and does not rely on a global reference frame. This overcomes serious shortcomings of approaches using a global reference frame to compute the error. Our method furthermore allows 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 robotics community. The relations have been obtained by manually matching laser-range observations to avoid the errors caused by matching algorithms. Our benchmark framework allows the user to easily analyze and objectively compare different SLAM approaches.

• Wolfram Burgard, Cyrill Stachniss, Giorgio Grisetti, Bastian Steder, Rainer Kümmerle, Christian Dornhege, Michael Ruhnke, Alexander Kleiner and Juan D. Tardos.
  A Comparison of SLAM Algorithms Based on a Graph of Relations.
  In Proceedings of the 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2009), pp. 2089-2095. IEEE 2009.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  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.

• Rainer Kümmerle, Bastian Steder, Christian Dornhege, Alexander Kleiner, Giorgio Grisetti and Wolfram Burgard.
  Large Scale Graph-based SLAM using Aerial Images as Prior Information.
  In Proceedings of 2009 Robotics: Science and Systems (RSS 2009). 2009.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  To effectively navigate in their environments and accurately reach their target locations, mobile robots require a globally consistent map of the environment. The problem of learning a map with a mobile robot has been intensively studied in the past and is usually referred to as the simultaneous localization and mapping (SLAM) problem. However, existing solutions to the SLAM problem typically rely on loop-closures to obtain global consistency and do not exploit prior information even if it is available. In this paper, we present a novel SLAM approach that achieves global consistency by utilizing publicly accessible aerial photographs as prior information. Our approach inserts correspondences found between three-dimensional laser range scans and the aerial image as constraints into a graph-based formulation of the SLAM problem. We evaluate our algorithm based on large real-world datasets acquired in a mixed in- and outdoor environment by comparing the global accuracy with state-of-the-art SLAM approaches and GPS. The experimental results demonstrate that the maps acquired with our method show increased global consistency.

• Dali Sun, Alexander Kleiner and T. M. Wendt.
  Multi-Robot Range-Only SLAM by Active Sensor Nodes for Urban Search and Rescue.
  In Robocup 2008: Robot Soccer World Cup XII, pp. 318-330. Springer 2009.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  To jointly map an unknown environment with a team of autonomous robots is a challenging problem, particularly in large environments, as for example the devastated area after a disaster. Under such conditions standard methods for Simultaneous Localization And Mapping (SLAM) are difficult to apply due to possible misinterpretations of sensor data, leading to erroneous data association for loop closure. We consider the problem of multi-robot range-only SLAM for robot teams by solving the data association problem with wireless sensor nodes that we designed for this purpose. The memory of these nodes is utilized for the exchange of map data between multiple robots, facilitating loop-closures on jointly generated maps. We introduce RSLAM, which is a variant of FastSlam, extended for range-only measurements and the multi-robot case. Maps are generated from robot odometry and range estimates, which are computed from the RSSI (Received Signal Strength Indication). The proposed method has been extensively tested in USARSim, which serves as basis for the Virtual Robots competition at RoboCup, and by real-world experiments with a team of mobile robots. The presented results indicates that the approach is capable of building consistent maps in presence of real sensor noise, as well as to improve mapping results of multiple robots by data sharing.

2008

• Alexander Kleiner, G. Steinbauer and F. Wotawa.
  Towards automated online diagnosis of robot navigation software.
  In Proc. of Int. Conf. on Simulation, Modeling and Programming for Autonomous Robots (SIMPAR), pp. 159-170. Springer 2008.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Control software of autonomous mobile robots comprises a number of software modules that typically interact in a very complex way. Their proper interaction and the robustness of each single module strongly influences the safety during navigation in the field. Particularly in unstructured environments, unforeseen situations are likely to occur, causing erroneous behaviors of the robot. The proper handling of such situations requires an understanding of cause and effect within the complex interactions of the system. In this paper we present an approach which is able to automatically derive a model of the communication behavior within a component-orientated control software. The model can be used for online diagnosis in order to increase system robustness during runtime. We demonstrate model learning and system diagnosis on three different robot systems which were controlled by software modules communicating based on the widely used IPC (Inter Process Communication) standard. The demonstrated learning and diagnosis was carried out without any a priori knowledge about the systems.

2007

• Christian Dornhege and Alexander Kleiner.
  Fully autonomous planning and obstacle negotiation on rough terrain using behavior maps.
  In Video Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2007). San Diego, California 2007.
  

• Christian Dornhege and Alexander Kleiner.
  Behavior maps for online planning of obstacle negotiation and climbing on rough terrain.
  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2007), pp. 3005-3011. 2007.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  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.

• Alexander Kleiner and R. Kümmerle.
  Genetic MRF model optimization for real-time victim detection in Search and Rescue.
  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2007), pp. 3025-3030. 2007.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  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 subtasks, 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.

• Alexander Kleiner and Christian Dornhege.
  Real-time Localization and Elevation Mapping within Urban Search and Rescue Scenarios.
  Journal of Field Robotics 24, pp. 723-745. 2007.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Urban Search And Rescue (USAR) is a time critical task. Rescue teams have to explore a large terrain within a short amount of time in order to locate survivors after a disaster. One goal in Rescue Robotics is to have a team of heterogeneous robots that explore autonomously, or partially guided by an incident commander, the disaster area. Their task is to jointly create a map of the terrain and to register victim locations, which can further be utilized by human task forces for rescue. Basically, the robots have to solve autonomously in real-time the problem of Simultaneous Localization and Mapping (SLAM), consisting of a continuous state estimation problem and a discrete data association problem. Extraordinary circumstances after a real disaster make it very hard to apply common techniques. Many of these have been developed under strong assumptions, for example, they require polygonal structures, such as typically found in office-like environments. Furthermore, most techniques are not deployable in real-time. In this paper we propose real-time solutions for localization and mapping, which all have been extensively evaluated within the test arenas of the National Institute of Standards and Technology (NIST). We specifically deal with the problems of vision-based pose tracking on tracked vehicles, the building of globally consistent maps based on a network of RFID tags, and the building of elevation maps from readings of a tilted Laser Range Finder (LRF). Our results show that these methods lead under modest computational requirements to good results within the utilized testing arenas.

• S. Balakirsky, S. Carpin, Alexander Kleiner, M. Lewis, A. Visser, J. Wang and V.A. Ziparo.
  Towards heterogeneous robot teams for disaster mitigation: Results and Performance Metrics from Robocup Rescue.
  Journal of Field Robotics 24, pp. 943-967. 2007.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Urban Search And Rescue is a growing area of robotic research. The RoboCup Federation has recognized this, and has created the new Virtual Robots competition to complement its existing physical robot and agent competitions. In order to successfully compete in this competition, teams need to field multi-robot solutions that cooperatively explore and map an environment while searching for victims. This paper presents the results of the first annual RoboCup Rescue Virtual competition. It provides details on the metrics used to judge the contestants as well as summaries of the algorithms used by the top four teams. This allows readers to compare and contrast these effective approaches. Furthermore, the simulation engine itself is examined and real-world validation results on the engine and algorithms are offered.

• V.A. Ziparo, Alexander Kleiner, L. Marchetti, A. Farinelli and and D. Nardi.
  Cooperative Exploration for USAR Robots with Indirect Communication.
  In Proceedings of the 6th IFAC Symposium on Intelligent Autonomous Vehicles (IAV 2007). 2007.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  To coordinate a team of robots for exploration is a challenging problem, particularly in unstructured areas, as for example post-disaster scenarios where direct communication is severely constrained. Furthermore, conventional methods of SLAM, e.g. those performing data association based on visual features, are doomed to fail due to bad visibility caused by smoke and fire. We use indirect communication (based on RFIDs), to share knowledge and use a gradient-like local search to direct robots towards interesting areas. To share a common frame of reference among robots we use a feature based SLAM approach (where features are RFIDs). The approach has been evaluated on a 3D simulation based on USARSim.

• Vittorio Ziparo, Alexander Kleiner, Bernhard Nebel and Daniele Nardi.
  RFID-Based Exploration for Large Robot Teams.
  In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2007), pp. 4606-4613. Rome, Italy 2007.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  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.

• Alexander Kleiner, Christian Dornhege and Dali Sun.
  Mapping disaster areas jointly: RFID -Coordinated SLAM by Humans and Robots.
  In Proceedings of the IEEE International Workshop on Safety, Security and Rescue Robotics (SSRR 2007), pp. 1-6. 2007.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  We consider the problem of jointly performing SLAM by humans and robots in Urban Search And Rescue (USAR) scenarios. In this context, SLAM is a challenging task. First, places are hardly re-observable by vision techniques since visibility might be affected by smoke and fire. Second, loop-closure is cumbersome due to the fact that firemen will intentionally try to avoid performing loops when facing the reality of emergency response, e.g.USAR, while they are searching for victims. Furthermore, there might be places that are only accessible to robots, making it necessary to integrate humans and robots into one team for mapping the area after a disaster. In this paper, we introduce a method for jointly correcting individual trajectories of humans and robots by utilizing RFID technology for data association. Hereby the poses of humans and robots are tracked by a PDR (Pedestrian Dead Reckoning), and slippage sensitive odometry, respectively. We conducted extensive experiments with a team of humans, and a human-robot team within a semi-outdoor environment. Results from these experiments show that the introduced method allows to improve single trajectories based on the joint graph, even if they do not contain any loop.

• H. Kenn and Alexander Kleiner.
  Towards the Integration of Real-Time Real-World Data in Urban Search and Rescue Simulation.
  In MobileResponse, pp. 106-115. Springer 2007.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  The coordinated reaction to a large-scale disaster is a challenging research problem. The Robocup rescue simulation league addresses this research problem but is currently lacking an interface to real-world real-time data to test the validity of both simulation and simulated reactions. In this paper, we describe a wearable-computing-based real world interface to the Robocup Resuce simulation software and provide some updated results of preliminary evaluations.

• Alexander Kleiner and Dali Sun.
  Decentralized SLAM for Pedestrians without direct Communication.
  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2007), pp. 1461-1466. 2007.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  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 fireman 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 within both outdoor and semi-indoor 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.

2006

• Alexander Kleiner, Johann Prediger and Bernhard Nebel.
  RFID Technology-based Exploration and SLAM for Search And Rescue.
  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2006), pp. 4054-4059. Beijing, China 2006.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  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 [8] 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.

• Alexander Kleiner, Christian Dornhege, Rainer Kuemmerle, Michael Ruhnke, Bastian Steder, Bernhard Nebel, Patrick Doherty, Mariusz Wzorek, Piotr Rudol, Gianpaolo Conte, S. Durante and D. Lundstrom.
  RoboCupRescue - Robot League Team RescueRobots Freiburg (Germany), Team Description Paper.
  In CDROM Proceedings of the International RoboCup Symposium '05. Bremen, Germany 2006.
  (Show abstract) (Hide abstract) (PDF)
  

  This paper describes the approach of the RescueRobots Freiburg team, which is a team of students from the University of Freiburg that originates from the former CS Freiburg team (RoboCupSoccer) and the ResQ Freiburg team (RoboCupRescue Simulation). Furthermore we introduce linkMAV, a micro aerial vehicle platform. Our approach covers RFID-based SLAM and exploration, autonomous detection of relevant 3D structures, visual odometry, and autonomous victim identification. Furthermore, we introduce a custom made 3D Laser Range Finder (LRF) and a novel mechanism for the active distribution of RFID tags.

• Alexander Kleiner and Vittorio Ziparo.
  RoboCupRescue - Simulation League Team RescueRobots Freiburg (Germany), Team Description Paper.
  In CDROM Proceedings of the International RoboCup Symposium '06. Bremen, Germany 2006.
  (PDF)
  

• Christian Dornhege and Alexander Kleiner.
  Visual Odometry for Tracked Vehicles.
  In Proceedings of the IEEE International Workshop on Safety, Security and Rescue Robotics (SSRR 2006). 2006.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Localization and mapping on autonomous robots typically requires a good pose estimate, which is hard to acquire if the vehicle is tracked. In this paper we describe a solution to the pose estimation problem by utilizing a consumer-quality camera and an Inertial Measurement Unit (IMU). The basic idea is to continuously track salient features with the KLT feature tracker over multiple images taken by the camera and to extract from the tracked features image vectors resulting from the robot's motion. Each image vector is taken for a voting that best explains the robot's motion. Image vectors vote according to a previously trained ^\m2102tile coding^\m2112 classificator that assigns to each possible image vector a translation probability. Our results show that the proposed single camera solution leads to sufficiently accurate pose estimates of the tracked vehicle.

• Alexander Kleiner, N. Behrens and H. Kenn.
  Wearable computing meets multiagent systems: A real-world interface for the RoboCupRescue simulation platform.
  In First International Workshop on Agent Technology for Disaster Management at AAMAS06, pp. 116-123. AAMAS Press 2006.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  One big challenge in disaster response is to get an overview over the degree of damage and to provide this information, together with optimized plans for rescue missions, back to teams in the field. Collapsing infrastructure, limited visibility due to smoke and dust, and overloaded communication lines make it nearly impossible for rescue teams to report the total situation consistently. This problem can only be solved by efficiently integrating data of ^\m2102many^\m2112 observers into a single consistent view. A Global Positioning System (GPS) device in conjunction with a communication device, and sensors or simple input methods for reporting observations, offer a realistic chance to solve the data integration problem. We propose preliminary results from a wearable computing device, acquiring disaster relevant data, such as locations of victims and blockades, and show the data integration into the RoboCupRescue Simulation platform, which is a benchmark for MAS within the RoboCup competitions. We show exemplarily how the data can consistently be integrated and how rescue missions can be optimized by solutions developed on the RoboCupRescue simulation platform. The preliminary results indicate that nowadays wearable computing technology combined with MAS technology can serve as a powerful tool for Urban Search and Rescue (USAR).

2005

• Alexander Kleiner, Michael Brenner, Tobias Braeuer, Christian Dornhege, Moritz Göbelbecker, Matthias Luber, Johann Prediger, Joerg Stueckler and Bernhard Nebel.
  Successful Search and Rescue in Simulated Disaster Areas.
  In Proceedings of the International RoboCup Symposium '05. Osaka, Japan 2005.
  (Show abstract) (Hide abstract) (PDF)
  

  RoboCupRescue Simulation is a large-scale multi-agent simulation of urban disasters where, in order to save lives and minimize damage, rescue teams must effectively cooperate despite sensing and communication limitations. This paper presents the comprehensive search and rescue approach of the ResQ Freiburg team, the winner in the RoboCupRescue Simulation league at RoboCup 2004. Specific contributions include the predictions of travel costs and civilian lifetime, the efficient coordination of an active disaster space exploration, as well as an any-time rescue sequence optimization based on a genetic algorithm. We compare the performances of our team and others in terms of their capability of extinguishing fires, freeing roads from debris, disaster space exploration, and civilian rescue. The evaluation is carried out with information extracted from simulation log files gathered during RoboCup 2004. Our results clearly explain the success of our team, and also confirm the scientific approaches proposed in this paper.

• Alexander Kleiner, Bastian Steder, Christian Dornhege, Daniel Hoefler, Daniel Meyer-Delius, Johann Prediger, Joerg Stueckler, Kolja Glogowski, Markus Thurner, Matthias Luber, Michael Schnell, Rainer Kuemmerle, Timothy Burk, Tobias Braeuer and Bernhard Nebel.
  RoboCupRescue - Robot League Team RescueRobots Freiburg (Germany), Team Description Paper.
  In CDROM Proceedings of the International RoboCup Symposium '05. Osaka, Japan 2005.
  (Show abstract) (Hide abstract) (PDF)
  

  This paper describes the approach of the RescueRobots Freiburg team. RescueRobots Freiburg is a team of students from the university of Freiburg, that originates from the former CS Freiburg team (RoboCupSoccer) and the ResQ Freiburg team (RoboCupRescue Simulation). Due to the high versatility of the RoboCupRescue competition we tackle the three arenas by a a twofold approach: On the one hand we want to introduce robust vehicles that can safely be teleoperated through rubble and building debris while constructing three-dimensional maps of the environment. On the other hand we want to introduce a team of autonomous robots that quickly explore a large terrain while building a two-dimensional map. This two solutions are particularly wellsuited for the red and yellow arena, respectively. Our solution for the orange arena will finally be decided between these two, depending on the capabilities of both approaches at the venue. In this paper, we introduce some preliminary results that we achieved so far from map building, localization, and autonomous victim identification. Furthermore we introduce a custom made 3D Laser Range Finder (LRF) and a novel mechanism for the active distribution of RFID tags. 1 Introduction RescueRobots Freiburg is a team of students from the university of Freiburg. The team originates from the former CS Freiburg team[6], which won three times the RoboCup world championship in the RoboCupSoccer F2000 league, and the ResQ Freiburg team[2], which won the last RoboCup world championship in the RoboCupRescue Simulation league. The team approach proposed in this paper is based on experiences gathered at RoboCup during the last six years. Due to the high versatility of the RoboCupRescue competition we tackle the three arenas by a twofold approach: On the one hand we want to introduce a vehicle that can safely be teleoperated through rubble and building debris while constructing threedimensional maps of the environment. On the other hand we want to introduce an autonomous team of robots that quickly explore a large terrain while building a twodimensional map. This two solutions are particularly well-suited for the red and yellow arena, respectively. Our solution for the orange arena will finally be decided between these two, depending on the capabilities of both approaches at the venue.

• Alexander Kleiner.
  Game AI: The shrinking gap between computer games and AI systems Ambient Intelligence.
  Ambient Intelligence:The evolution of technology, communication and cognition towards the future of human-computer interaction. 2005.
  (PDF)
  

2004

• Timo Nuessle, Alexander Kleiner and Michael Brenner.
  Approaching Urban Disaster Reality: The ResQ Firesimulator.
  In Proceedings of the International RoboCup Symposium '04. Lisbon, Portugal 2004.
  (PDF)
  

• Alexander Kleiner, Michael Brenner, Tobias Braeuer, Christian Dornhege, Moritz Göbelbecker, Matthias Luber, Johann Prediger and Joerg Stueckler.
  ResQ Freiburg: Team Description and Evaluation, Team Description Paper, Rescue Simulation League.
  In CDROM Proceedings of the International RoboCup Symposium '04. Lisbon, Portugal 2004.
  (PDF)
  

2003

• Erik Schulenburg, Thilo Weigel and Alexander Kleiner.
  Self-Localization in Dynamic Environments based on Laser and Vision Data.
  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS'03), pp. 998-1004. Las Vegas, USA 2003.
  (PS.GZ) (PDF)
  

• Alexander Kleiner and Thorsten Buchheim.
  A Plugin-Based Architecture For Simulation In The F2000 League.
  In Proceedings of the International RoboCup Symposium '03. Padova, Italy 2003.
  (PS.GZ) (PDF)
  

2002

• Alexander Kleiner, Markus Dietl and Bernhard Nebel.
  Towards a Life-Long Learning Soccer Agent.
  In Proceedings of the International RoboCup Symposium '02. Fukuoka, Japan 2002.
  (Show abstract) (Hide abstract) (PDF)
  

  One problem in robotic soccer (and in robotics in general) is to adapt skills and the overall behavior to a changing environment and to hardware improvements. We applied hierarchical reinforcement learning in an SMDP framework learning on all levels simultaneously. As our experiments show, learning simultaneously on the skill level and on the skill selection level is advantageous since it allows for a smooth adaption to a changing environment. Furthermore, the skills we trained turn also out to be quite competitive when run on the real robotic players of the players of our CS Freiburg team.

• Thilo Weigel, Jens-Steffen Gutmann, Markus Dietl, Alexander Kleiner and Bernhard Nebel.
  CS Freiburg: Coordinating Robots for Successful Soccer Playing.
  IEEE Transactions on Robotics and Automation 18 (5), pp. 685-699. 2002.
  (Show abstract) (Hide abstract) (PDF)
  

  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. This paper presents the CS Freiburg team, the winner in the middle size league at RoboCup 1998, 2000 and 2001. The paper focuses on multi-agent coordination for both perception and action. The contributions of this work 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 to respond to large range of situations in an appropriate way, 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 multi-robot group, which is able to play soccer successfully. In addition, the developed methods promise to advance the state of the art in the multi-robot field.

2001

• Thilo Weigel, Alexander Kleiner, Florian Diesch, Markus Dietl, Jens-Steffen Gutmann, Bernhard Nebel, Patrick Stiegeler and Boris Szerbakowski.
  CS Freiburg 2001.
  In International RoboCup Symposium 2001. 2001.
  (Show abstract) (Hide abstract) (PDF)
  

  The CS Freiburg team has become F2000 champion the third time in the history of RoboCup. The success of our team can probably be attributed to its robust sensor interpretation and its team play. In this paper, we will focus on new developments in our vision system, in our path planner, and in the cooperation component.

• Contact Legal Information