AIICS

Alexander Kleiner

All Publications

Hide abstracts BibTeX entries
2013
[70] Robin Murphy and Alexander Kleiner. 2013.
A Community-Driven Roadmap for the Adoption of Safety Security and Rescue Robots.
In . IEEE conference proceedings.
Note: Accepted for Publication.

The IEEE Safety, Security, and Rescue Robotics community has created a roadmap for producing unmanned systems that could be adopted by the Public Safety sector within 10 years, given appropriate R&D investment especially in human-robot interaction and perception. The five applications expected to be of highest value to the Public Safety community, highest value first, are: assisting with routine inspection of the critical infrastructure, “chronic emergencies” such as firefighting, hazardous material spills, port inspection, and damage estimation after a disaster. The technical feasibility of the applications were ranked, with the most attractive scenario, infrastructure inspection, rated as the second easiest scenario; this suggests the maturity of robotics technology is beginning to match stakeholder needs. Each of the five applications were discussed in terms of the six broad enabling technology areas specified in the current National Robotics Initiative Roadmap (perception, human-robot interaction, mechanisms, modeling and simulation, control and planning, and testing and evaluation) and nine specific capabilities identified by the community as being essential to commercialization (communication, alerting, localization, fault tolerance, mapping, manpower needs, plug and play capabilities, multiple users, and multiple robots). The community believes that perception and human-robot interaction are the two biggest barriers to adoption, and require more research, given that their low technical maturity (3rd and 6th rank respectively). However, each of the specific capabilities needed for commercialization are being addressed by current research and could be achieved within 10 years with sustained funding.

[69] Christian Dornhege, Alexander Kleiner and Andreas Kolling. 2013.
Coverage Search in 3D.
In .
Note: Accepted for Publication.

Searching with a sensor for objects and to observe parts of a known environment efficiently is a fundamental prob- lem in many real-world robotic applications such as 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 efficient view point sequences for covering complex 3d environments. We compare empirically several variants of our algorithm that allow to trade-off schedule computation against execution time. Our results demonstrate that, despite the intractability of the overall problem, computing effective solutions for coverage search in real 3d environments is feasible.

[68] Gianpaolo Conte, Alexander Kleiner, Piotr Rudol, Karol Korwel, Mariusz Wzorek and Patrick Doherty. 2013.
Performance evaluation of a light weight multi-echo LIDAR for unmanned rotorcraft applications.
In International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Volume XL-1/W2.

The paper presents a light-weight and low-cost airborne terrain mapping system. The developed Airborne LiDAR Scanner (ALS) sys- tem consists of a high-precision GNSS receiver, an inertial measurement unit and a magnetic compass which are used to complement a LiDAR sensor in order to compute the terrain model. Evaluation of the accuracy of the generated 3D model is presented. Additionally, a comparison is provided between the terrain model generated from the developed ALS system and a model generated using a commer- cial photogrammetric software. Finally, the multi-echo capability of the used LiDAR sensor is evaluated in areas covered with dense vegetation. The ALS system and camera systems were mounted on-board an industrial unmanned helicopter of around 100 kilograms maximum take-off weight. Presented results are based on real flight-test data.

[67] Andreas Kolling, Alexander Kleiner and Piotr Rudol. 2013.
Fast Guaranteed Search With Unmanned Aerial Vehicles.
In Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2013), pages 6013–6018.
DOI: 10.1109/IROS.2013.6697229.

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 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 ARDrones.

[66] Karen Petersen, Alexander Kleiner and Oskar von Stryk. 2013.
Fast Task-Sequence Allocation for Heterogeneous Robot Teams with a Human in the Loop.
In Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2013), pages 1648–1655.
DOI: 10.1109/IROS.2013.6696570.

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.

[65] Andreas Kolling and Alexander Kleiner. 2013.
Multi-UAV Trajectory Planning for Guaranteed Search.
In Proc. of the 12th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2013), pages 79–86. ISBN: 978-1-4503-1993-5.

We consider the problem of detecting all moving and evading targets in 2.5D environments with teams of UAVs. Targets are assumed to be fast and omniscient while UAVs are only equipped with limited range detection sensors and have no prior knowledge about the location of targets. We present an algorithm that, given an elevation map of the environment, computes synchronized trajectories for the UAVs to guarantee the detection of all targets. The approach is based on coordinating the motion of multiple UAVs on sweep lines to clear the environment from contamination, which represents the possibility of an undetected target being located in an area. The goal is to compute trajectories that minimize the number of UAVs needed to execute the guaranteed search. This is achieved by converting 2D strategies, computed for a polygonal representation of the environment, to 2.5D strategies. We present methods for this conversion and consider cost of motion and visibility constraints. Experimental results demonstrate feasibility and scalability of the approach. Experiments are carried out on real and artificial elevation maps and provide the basis for future deployments of large teams of real UAVs for guaranteed search.

[64] Alexander Kleiner, A. Farinelli, S. Ramchurn, B. Shi, F. Maffioletti and R. Reffato. 2013.
RMASBench: Benchmarking Dynamic Multi-Agent Coordination in Urban Search and Rescue.
In Proc. of the 12th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2013), pages 1195–1196. ISBN: 978-1-4503-1993-5.

We propose RMASBench, a new benchmarking tool based on the RoboCup Rescue Agent simulation system, to easily compare coordination approaches in a dynamic rescue scenario. In particular, we offer simple interfaces to plug-in coordination algorithms without the need for implementing and tuning low-level agents behaviors. Moreover, we add to the realism of the simulation by providing a large scale crowd simulator, which exploits GPUs parallel architecture, to simulate the behavior of thousands of agents in real time. Finally, we focus on a specific coordination problem where fire fighters must combat fires and prevent them from spreading across the city. We formalize this problem as a Distributed Constraint Optimization Problem and we compare two state-of-the art solution techniques: DSA and MaxSum. We perform an extensive empirical evaluation of such techniques considering several standard measures for performance (e.g. damages to buildings) and coordination overhead (e.g., message exchanged and non concurrent constraint checks). Our results provide interesting insights on limitations and benefits of DSA and MaxSum in our rescue scenario and demonstrate that RMASBench offers powerful tools to compare coordination algorithms in a dynamic environment.

[63] H. Levent Akin, Nobuhiro Ito, Adam Jacoff, Alexander Kleiner, Johannes Pellenz and Arnoud Visser. 2013.
RoboCup Rescue Robot and Simulation Leagues.
The AI Magazine, 34(1):????. AAAI Press.
Link to journal: http://www.aaai.org/ojs/index.php/aimaga...

The RoboCup Rescue Robot and Simulation competitions have been held since 2000. The experience gained during these competitions has increased the maturity level of the field, which allowed deploying robots after real disasters (e.g. Fukushima Daiichi nuclear disaster). This article provides an overview of these competitions and highlights the state of the art and the lessons learned.

[62] Alexander Kleiner and Andreas Kolling. 2013.
Guaranteed Search With Large Teams of Unmanned Aerial Vehicles.
In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), pages 2977–2983. In series: Robotics and Automation (ICRA), 2013 IEEE International Conference on #??. IEEE conference proceedings. ISBN: 978-1-4673-5641-1.
DOI: 10.1109/ICRA.2013.6630990.

We consider the problem of detecting moving and evading targets by a team of coordinated unmanned aerial vehicles (UAVs) in large and complex 2D and 2.5D environments. 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 implicitly given by the motion of these sweep lines and their costs are determined by the number of UAVs needed. A novel algorithm that computes low cost coordination strategies of the UAV sweep lines in simply connected polygonal environments is presented. The resulting strategies are then converted to strategies clearing multiply connected and 2.5D environments. Experiments on real and artificial elevation maps with complex visibility constraints are presented and demonstrate the feasibility and scalability of the approach. The algorithms used for the experiments are made available on a public repository.

[61] Quirin Hamp, Omar Gorgis, Patrick Labenda, Marc Neumann, Thomas Predki, Leif Heckes, Alexander Kleiner and Leonard Reindl. 2013.
Study of eciency of USAR operations with assistive technologies.
Advanced Robotics, 27(5):337–350.
DOI: 10.1080/01691864.2013.763723.

This paper presents presents a study on eciency of Urban Search and Rescue (USAR) missions that has been carried out within the framework of the German research project I-LOV. After three years of development, first field tests have been carried out in 2011 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, USAR missions assisted by the “bioradar”, a ground-penetrating radar system for the detection of humanoid movements, a semi-active video probe of more than 10 m length for rubble pile exploration, a snake-like rescue robot, and the decision support system FRIEDAA were evaluated and compared with conventional USAR missions. Results of this evaluation indicate that the developed technologies represent an advantages for USAR missions, which are discussed in this paper.

[60] C. Dornhege and Alexander Kleiner. 2013.
A Frontier-Void-Based Approach for Autonomous Exploration in 3D.
Advanced Robotics, 27(6):459–468. Taylor and Francis.
DOI: 10.1080/01691864.2013.763720.
Note: Funding Agencies|Deutsche Forschungsgemeinschaft in the Transregional Collaborative Research Center|SFB/TR8|

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.

[59] Full text  Alexander Kleiner, A. Kolling, M. Lewis and K. Sycara. 2013.
Hierarchical Visibility for Guaranteed Search in Large-Scale Outdoor Terrain.
Autonomous Agents and Multi-Agent Systems, 26(1):1–36. Springer.
DOI: 10.1007/s10458-011-9180-7.

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.

2012
[58] Gerald Steinbauer and Alexander Kleiner. 2012.
Towards CSP-based mission dispatching in C2/C4I systems.
In Proc. of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR), pages 1–6. IEEE. ISBN: 978-1-4799-0164-7, 978-1-4799-0163-0, 978-1-4799-0165-4.
DOI: 10.1109/SSRR.2012.6523875.

One challenging problem in disaster response is to efficiently assign resources such as fire fighters and trucks to local incidents that are spatially distributed on a map. Existing systems for command and control (C2/C4I) are coming with powerful interfaces enabling the manual assignment of resources to the incident commander. However, with increasing number of local incidents over time the performance of manual methods departs arbitrarily from an optimal solution. In this paper we introduce preliminary results of building an interface between existing professional C2/C4I systems and Constraint Satisfaction Problem (CSP)-solvers. We show by using an example the feasibility of scheduling and assigning missions having deadlines and resource constraints.

[57] L. Marconi, C. Melchiorri, M. Beetz, D. Pangercic, R. Siegwart, S. Leutenegger, R. Carloni, S. Stramigioli, H. Bruyninckx, Patrick Doherty, Alexander Kleiner, V. Lippiello, A. Finzi, B. Siciliano, A. Sala and N. Tomatis. 2012.
The SHERPA project: Smart collaboration between humans and ground-aerial robots for improving rescuing activities in alpine environments.
In Proc. of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR), pages 1–4. IEEE. ISBN: 978-1-4799-0164-7, 978-1-4799-0163-0, 978-1-4799-0165-4.
DOI: 10.1109/SSRR.2012.6523905.

The goal of the paper is to present the foreseen research activity of the European project “SHERPA” whose activities will start officially on February 1th 2013. The goal of SHERPA is to develop a mixed ground and aerial robotic platform to support search and rescue activities in a real-world hostile environment, like the alpine scenario that is specifically targeted in the project. Looking into the technological platform and the alpine rescuing scenario, we plan to address a number of research topics about cognition and control. What makes the project potentially very rich from a scientific viewpoint is the heterogeneity and the capabilities to be owned by the different actors of the SHERPA system: the human rescuer is the “busy genius”, working in team with the ground vehicle, as the “intelligent donkey”, and with the aerial platforms, i.e. the “trained wasps” and “patrolling hawks”. Indeed, the research activity focuses on how the “busy genius” and the “SHERPA animals” interact and collaborate with each other, with their own features and capabilities, toward the achievement of a common goal.

[56] Bernhard Nebel and Alexander Kleiner. 2012.
Multi-Agenten-Systeme in der Intralogistik - Erster Teil: Gemeinsam denken.
IEE - Elektrische Automatisierung + Antriebstechnik, -(4):48–53. HĂŒthig Verlag.
Link to journal: http://www.iee-online.de/2012/

Nicht nur in der Logistik und in der Produktion setzt es sich immer mehr durch, die Steuerung und Überwachung von Aufgaben zu verteilen. Für eine solche Vorgehens- weise sind sogenannte Multi-Agenten-Systeme (MAS) geeignet, bei denen mehrere ei- genständige Systeme miteinander kommunizieren, sich koordinieren und kooperieren. Eine spezielle Form solcher MAS sind Multi-Roboter-Systeme.

[55] Bernhard Nebel and Alexander Kleiner. 2012.
Multi-Agenten-Systeme in der Intralogistik - Zweiter Teil: Effizient transportieren.
IEE - Elektrische Automatisierung + Antriebstechnik, -(5):34–37. HĂŒthig Verlag.
Link to journal: http://www.iee-online.de/2012/

In der Logisitk, in der Produktion und und in anderen Bereichen setzt es sich immer mehr durch, zentrale Instanzen zu vermeiden und die Steuerung und Überwachung von Aufgaben zu verteilen. FĂŒr eine solche Vorgehensweise sind so genannte Multi-Agenten-Systeme (MAS) ideal geeignet, bei denen mehrere eigenstĂ€ndige Systeme miteinander kommunizieren, sich koordinieren und kooperieren. Eine spezielle Form solcher MAS sind Multi-Roboter-Systeme, bei denen die einzelnen Agenten sich selbstĂ€ndig bewegende physikalische Einheiten sind, wie z.B. bei einer Gruppe von Reinigungsrobotern, einem Roboterfußballteam oder im Logistiksystem KARIS.

2011
[54] Full text  Alexander Kleiner and Christian Dornhege. 2011.
Mapping for the Support of First Responders in Critical Domains.
Journal of Intelligent and Robotic Systems, 64(1):7–31. Springer.
DOI: 10.1007/s10846-010-9520-x.

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.

[53] Full text  R. KĂŒmmerle, B. Steder, C. Dornhege, Alexander Kleiner, G. Grisetti and W. Burgard. 2011.
Large Scale Graph-based SLAM using Aerial Images as Prior Information.
Autonomous Robots, 30(1):25–39. Springer.
DOI: 10.1007/s10514-010-9204-1.

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.

[52] Full text  Alexander Kleiner, B. Nebel and V. Ziparo. 2011.
A Mechanism for Dynamic Ride Sharing based on Parallel Auctions.
In 22th International Joint Conference on Artificial Intelligence (IJCAI), pages 266–272.

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.

[51] Full text  Q. Hamp, L. Reindl and Alexander Kleiner. 2011.
Lessons Learned from German Research for USAR.
In IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR).
Note: Winner of the Young Author’s Award

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.

[50] Full text  A. Kolling, Alexander Kleiner, M. Lewis and K. Sycara. 2011.
Computing and Executing Strategies for Moving Target Search.
In IEEE Int. Conf. on Robotics and Automation (ICRA), pages 4246–4253. IEEE.
DOI: 10.1109/ICRA.2011.5980277.

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.

[49] Full text  D. Meyer-Delius, M. Beinhofer, Alexander Kleiner and W. Burgard. 2011.
Using artificial landmarks to reduce the ambiguity in the environment of a mobile robot.
In IEEE Int. Conf. on Robotics and Automation (ICRA), pages 5173–5178.
DOI: 10.1109/ICRA.2011.5980111.

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.

[48] Full text  Alexander Kleiner, D. Sun and D. Meyer-Delius. 2011.
ARMO - Adaptive Road Map Optimization for Large Robot Teams.
In IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 3276–3282. IEEE conference proceedings.
DOI: 10.1109/IROS.2011.6048339.

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.

2010
[47] Prasanna Velagapudi, Alexander Kleiner, Nathan Brooks, Paul Scerri, Michael Lewis and Katia Sycara. 2010.
RoboCupRescue - Virtual Robots Team STEEL (USA).
In RoboCup 2010 (CDROM Proceedings), Team Description Paper, Rescue Simulation League.

This paper describes the software system supporting the Carnegie Mellon/Univ. of Pittsburgh team of simulated search and rescue robots in the Robocup Rescue 2010 Virtual Robots competition. Building on the Machinetta agent software, robot command and control is decomposed into a hierarchy of subtasks managed by independent agents both on the robot and co-located with human operators. By encapsulating all robot and human operator interactions into interfaces to these agents, the system can perform with a high level of robustness and re-usability. As in previous years, the entire code base is portable and platform-independent, running entirely in Java.

[46] Christian Dornhege, Johannes Bendler, Roxana Bersan, Philipp Blohm, Martin Gloderer, Andreas Hertle, Thomas Liebetraut, Diego Cerdan Puyol, Alexander Kleiner and Bernhard Nebel. 2010.
RoboCupRescue 2010 - Robot League Team RescueRobots Freiburg (Germany).
In RoboCup 2010 (CDROM Proceedings), Team Description Paper, Rescue Robot League.

This paper describes the software and hardware system developed by the University of Freiburg team of search and rescue robots for the RoboCup Res- cue 2010 competition. This system is an extension to the software that finished in first place the 2005 and 2006 autonomy challenge, focusing on two key areas: autonomous navigation and manipulation. Our team, consisting mainly of students, originates from the former CS Freiburg team (RoboCupSoccer), the ResQ Freiburg team (RoboCupRescue Simulation), and RescueRobots Freiburg teams ñ€ℱ05 and ñ€ℱ06.

[45] Full text  Wei Mou and Alexander Kleiner. 2010.
Online Learning Terrain Classification for Adaptive Velocity Control.
In In Proc. of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR), pages 1–7.
DOI: 10.1109/SSRR.2010.5981563.

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.

[44] Full text  Sören Schwertfeger, Adam Jacoff, Chris Scrapper, Johannes Pellenz and Alexander Kleiner. 2010.
Evaluation of Maps using Fixed Shapes: The Fiducial Map Metric.
In Proc. of the Int. Workshop on Performance Metrics for Intelligent Systems (PerMIS), pages 344–351. NIST.

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.

[43] Full text  A. Kolling, Alexander Kleiner, M. Lewis and K. Sycara. 2010.
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. IEEE.

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.

[42] Full text  D. Maier and Alexander Kleiner. 2010.
Improved GPS Sensor Model for Mobile Robots in Urban Terrain.
In IEEE Int. Conf. on Robotics and Automation (ICRA), pages 4385–4390. IEEE. ISBN: 978-1-4244-5038-1.
DOI: 10.1109/ROBOT.2010.5509895.

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.

[41] Full text  A. Kolling, Alexander Kleiner, M. Lewis and K. Sycara. 2010.
Pursuit-Evasion in 2.5d based on Team-Visibility.
In IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 4610–4616. IEEE. ISBN: 978-1-4244-6674-0.
DOI: 10.1109/IROS.2010.5649270.

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.

[40] Full text  D. Sun, Alexander Kleiner and C. Schindelhauer. 2010.
Decentralized Hash Tables For Mobile Robot Teams Solving Intra-Logistics Tasks.
In 9th Int. Joint Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2010), pages 923–930. International Foundation for Autonomous Agents and.

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
[39] Full text  Alexander Kleiner, Chris Scrapper and Adam Jacoff. 2009.
RoboCupRescue Interleague Challenge 2009: Bridging the gap between Simulation and Reality.
In In Proc. of the Int. Workshop on Performance Metrics for Intelligent Systems (PerMIS), pages 123–129.

The RoboCupRescue initiative, represented by real-robot and simulation league, is designed to foster the research and development of innovative technologies and assistive capabilities to help responders mitigate an emergency response situation. This competition model employed by the RobocupRescue community has proven to be a propitious model, not only for fostering the development of innovative technologies but in the development of test methods used to quantitatively evaluate the performance of these technologies. The Interleague Challenge has been initiated to evaluate real-world performance of algorithms developed in simulation, as well as to drive the development of a common interface to simplify the entry of newcomer teams to the robot league. This paper will discuss the development of emerging test methods used to evaluate robotic-mapping, the development of a common robotic platform, and the development of a novel map evaluation methodology deployed during the RoboCupRescue competition 2009.

[38] Dali Sun, Alexander Kleiner and Thomas M. Wendt. 2009.
Multi-Robot Range-Only SLAM by Active Sensor Nodes for Urban Search and Rescue.
In Robocup 2008: Robot Soccer World Cup XII, pages 318–330.

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.

[37] Alexander Kleiner. 2009.
Mapping and Exploration for Search and Rescue with Humans and Mobile Robots.
Technical Report. University of Freiburg. 227 pages.
Note: This is a Ph.D. thesis originally defended at University of Freiburg.
Link to Thesis: http://www.google.se/url?sa=t&rct=j&q=ma...

Urban Search And Rescue (USAR) is a time critical task since all survivors have to be rescued within the first 72 hours. One goal in Rescue Robotics is to support emergency response by mixed-initiative teams consisting of humans and robots. Their task is to explore the disaster area rapidly while reporting victim locations and hazardous areas to a central station, which then can be utilized for planning rescue missions. To fulfill this task efficiently, humans and robots have to map disaster areas jointly while co- ordinating their search at the same time. Additionally, robots have to perform subproblems, such as victim detection and navigation, autonomously. In disaster areas these problems are extraordinarily challenging due to the unstructured environment and rough terrain. Furthermore, when communication fails, methods that are deployed under such conditions have to be decentralized, i.e. operational without a central station. In this thesis a unified approach joining human and robot resources for solving these problems is contributed. Following the vision of combined multi-robot and multi-human teamwork, core problems, such as position tracking on rough terrain, mapping by mixed teams, and decentralized team coordination with limited radio communication, are directly addressed. More specific, RFID-SLAM, a novel method for robust and efficient loop closure in large-scale environments that utilizes RFID technology for data association, is contributed. The method is capable of jointly improving multiple maps from humans and robots in a centralized and decentralized manner without requiring team members to perform loops on their routes. Thereby positions of humans are tracked by PDR (Pedestrian Dead Reckoning), and robot positions by slippage- sensitive odometry, respectively. The joint-graph emerging from these trajectories serves as an input for an iterative map optimization procedure. The introduced map representation is further utilized for solving the centralized and decentralized coordination of large rescue teams. On the one hand, a deliberate method for combined task assignment and multi-agent path planning, and on the other hand, a local search method using the memory of RFIDs for coordination, are proposed. For autonomous robot navigation on rough terrain and real-time victim detection in disaster areas an efficient method for elevation map building and a novel approach to genetic MRF (Markov Random Field) model optimization are contributed. Finally, a human in the loop architecture is presented that integrates data collected by first responders into a multi-agent system via wearable computing. In this context, the support and coordination of disaster mitigation in large-scale environments from a central-command-post-perspective are described. Methods introduced in this thesis were extensively evaluated in outdoor environments and official USAR testing arenas designed by the National Institute of Standards and Technology (NIST). Furthermore, they were an integral part of systems that won in total more than 10 times the first prize at international competitions, such as the RoboCup world championships.

[36] Full text  W. Burgard, C. Stachniss, G. Grisetti, B. Steder, R. KĂŒmmerle, C. Dornhege, M. Ruhnke, Alexander Kleiner and Juan D. TardĂłs. 2009.
A Comparison of SLAM Algorithms Based on a Graph of Relations.
In IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 2089–2095. IEEE conference proceedings.
DOI: 10.1109/IROS.2009.5354691.

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, namely to consider the energy that is needed to deform the trajectory estimated by a SLAM approach into 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 to avoid the errors caused by matching algorithms. Our benchmark framework allows the user an easy analysis and objective comparisons between different SLAM approaches.

[35] Full text  Alexander Kleiner and C. Dornhege. 2009.
Operator-Assistive Mapping in Harsh Environments.
In IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR), pages 1–6. IEEE. ISBN: 978-1-4244-5627-7.
DOI: 10.1109/SSRR.2009.5424159.
Note: (Best Paper Award Finalist)

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.

[34] Full text  R. KĂŒmmerle, B. Steder, C. Dornhege, Alexander Kleiner, G. Grisetti and W. Burgard. 2009.
Large Scale Graph-based SLAM using Aerial Images as Prior Information.
In Proceedings of Robotics Science and Systems (RSS). MIT Press.

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.

[33] Full text  R. KĂŒmmerle, B. Steder, C. Dornhege, M. Ruhnke, G. Grisetti, C. Stachniss and Alexander Kleiner. 2009.
On Measuring the Accuracy of SLAM Algorithms.
Autonomous Robots, 27(4):387–407. Springer.
DOI: 10.1007/s10514-009-9155-6.

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.

2008
[32] Christian Dornhege, Alexander Kleiner, Rainer KĂŒmmerle, Bastian Steder, Wolfram Burgard and Bernhard Nebel. 2008.
SP-Freiburg TechX Challenge Technical Paper.
In TechX Challenge.
Note: Finalist

In this paper we introduce our team’s approach to the TechX Challenge, which is based on experiences gathered at RoboCup during the last seven years and recent efforts in robotic research. We particularly focus on Multi-Level Surface (MLS) maps based localization, behavior map based path planning and obstacle negotiation, robot motion planning using a probabilistic roadmap planner, vision and 3D laser supported target detection, which all will be more detailed in the following sections.

[31] Full text  Alexander Kleiner, Gerald Steinbauer and Franz Wotawa. 2008.
Towards Automated Online Diagnosis of Robot Navigation Software.
In Proc. of Int. Conf. on Simulation, Modeling and Programming for Autonomous Robots (SIMPAR), pages 159–170. In series: Lecture Notes in Computer Science #5325. Springer.
DOI: 10.1007/978-3-540-89076-8_18.

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.

[30] Full text  Alexander Kleiner, Gerald Steinbauer and Franz Wotawa. 2008.
Automated Learning of Communication Models for Robot Control Software.
In MBS 2008 - Workshop on Model-Based Systems, 18th European Conference on Artificial Intelligence (ECAI).

Control software of autonomous mobile robots comprises a number of software modules which show very rich behaviors and interact in a very complex manner. These facts among others have a strong influence on the robustness of robot con- trol software in the field. In this paper we present an approach which is able to automatically derive a model of the structure and the behavior of the communication within a component- orientated control software. Such a model can be used for on-line model-based diagnosis in order to increase the robust- ness of the software by allowing the robot to autonomously cope with faults occurred during runtime. Due to the fact that the model is learned form recorded data and the use of the popular publisher-subscriber paradigm the approach can be applied to a wide range of complex and even partially un- known systems.

2007
[29] Christian Dornhege and Alexander Kleiner. 2007.
Fully Autonomous Planning and Obstacle Negotiation on Rough Terrain Using Behavior Maps.
In In Video Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 2561–2562. ISBN: 978-1-4244-0912-9.
DOI: 10.1109/IROS.2007.4399131.

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.

[28] Holger Kenn and Alexander Kleiner. 2007.
Towards the Integration of Real-Time Real-World Data in Urban Search and Rescue Simulation.
In MobileResponse, pages 106–115.

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.

[27] Full text  Stephen Balakirsky, Stefano Carpin, Alexander Kleiner, Michael Lewis, Arnoud Visser, Jijun Wang and Vittorio Amos Ziparo. 2007.
Towards Heterogeneous Robot Teams for Disaster Mitigation: Results and Performance Metrics from Robocup Rescue.
Journal of Field Robotics, 24(11):943–967.
DOI: 10.1002/rob.20212.

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.

[26] Full text  Alexander Kleiner and Christian Dornhege. 2007.
Real-time Localization and Elevation Mapping within Urban Search and Rescue Scenarios.
Journal of Field Robotics, 24(8-9):723–745. Wiley.
DOI: 10.1002/rob.20208.

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.

[25] Full text  Christian Dornhege and Alexander Kleiner. 2007.
Behavior Maps for Online Planning of Obstacle Negotiation and Climbing on Rough Terrain.
In In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 3005–3011. IEEE conference proceedings. ISBN: 978-1-4244-0912-9.
DOI: 10.1109/IROS.2007.4399107.

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.

[24] Full text  Alexander Kleiner, C. Dornhege and D. Sun. 2007.
Mapping Disaster Areas Jointly: RFID-Coordinated SLAM by Humans and Robots.
In IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR), pages 1–6. IEEE. ISBN: 978-1-4244-1569-4.
DOI: 10.1109/SSRR.2007.4381263.

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

[23] Full text  Alexander Kleiner and R. KĂŒmmerle. 2007.
Genetic MRF Model Optimization for Real-Time Victim Detection in Search and Rescue.
In IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 3025–3030. IEEE conference proceedings. ISBN: 978-1-4244-0912-9.
DOI: 10.1109/IROS.2007.4399006.

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.

[22] Full text  Alexander Kleiner and D. Sun. 2007.
Decentralized SLAM for Pedestrians without direct Communication.
In In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 1461–1466. IEEE conference proceedings. ISBN: 978-1-4244-0912-9.
DOI: 10.1109/IROS.2007.4399013.

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.

[21] Full text  V. A. Ziparo, Alexander Kleiner, A. Farinelli, L. Marchetti and D. Nardi. 2007.
Cooperative Exploration for USAR Robots with Indirect Communication.
In Proc. of 6th IFAC Symposium on Intelligent Autonomous Vehicles (IAV).

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.

[20] Full text  V. A. Ziparo, Alexander Kleiner, B. Nebel and D. Nardi. 2007.
RFID-Based Exploration for Large Robot Teams.
In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), pages 4606–4613. IEEE.
DOI: 10.1109/ROBOT.2007.364189.

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.

2006
[19] Alexander Kleiner, Christian Dornhege, Rainer KĂŒmmerle, Michael Ruhnke, Bastian Steder, Bernhard Nebel, Patrick Doherty, Mariusz Wzorek, Piotr Rudol, Gianpaolo Conte, Simone Duranti and David Lundström. 2006.
RoboCupRescue - Robot League Team RescueRobots Freiburg (Germany).
In RoboCup 2006 (CDROM Proceedings), Team Description Paper, Rescue Robot League.
Note: (1st place in the autonomy competition)

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.

[18] Alexander Kleiner, Nils Behrens and Holger Kenn. 2006.
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, pages 116–123.

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 many 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).

[17] Full text  Christian Dornhege and Alexander Kleiner. 2006.
Visual Odometry for Tracked Vehicles.
In In Proc. of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR).

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 tile coding 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.

[16] Full text  Alexander Kleiner, J. Prediger and Bernhard Nebel. 2006.
RFID Technology-based Exploration and SLAM for Search And Rescue.
In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 4054–4059. IEEE conference proceedings. ISBN: 1-4244-0258-1.
DOI: 10.1109/IROS.2006.281867.

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.

[15] Alexander Kleiner and V. A. Ziparo. 2006.
RoboCupRescue - Simulation League Team RescueRobots Freiburg (Germany).
In RoboCup 2006 (CDROM Proceedings), Team Description Paper, Rescue Simulation League.
Note: (1st place in the competition)

This paper describes the approach of the RescueRobots Freiburg Virtual League team. Our simulated robots are based on the two real robot types Lurker, a robot capable of climbing stairs and random stepfield, and Zerg, a lightweight and agile robot, capable of autonomously distributing RFID tags. Our approach covers a novel method for RFID-Technology based SLAM and exploration, allowing the fast and efficient coordination of a team of robots. Furthermore we utilize Petri nets for team coordination.

2005
[14] Alexander Kleiner. 2005.
Game AI: The Shrinking Gap Between Computer Games and AI Systems.
In G. Riva, F. Vatalaro, F. Davide, M. Alcañiz, editors, Ambient Intelligence: The evolution of technology, communication and cognition towards the future of human-computer interaction, pages 143–155. IOS Press.
Link: http://www.neurovr.org/emerging/volume6....

The introduction of games for benchmarking intelligent systems has a long tradition in AI (Artificial Intelligence) research. Alan Turing was one of the first to mention that a computer can be considered as intelligent if it is able to play chess. Today AI benchmarks are designed to capture difficulties that humans deal with every day. They are carried out on robots with unreliable sensors and actuators or on agents integrated in digital environments that simulate aspects of the real world. One example is given by the annually held RoboCup competitions, where robots compete in a football game but also fight for the rescue of civilians in a simulated large-scale disaster simulation. Besides these scientific events, another environment, also challenging AI, originates from the commercial computer game market. Computer games are nowadays known for their impressive graphics and sound effects. However, the latest generation of game engines shows clearly that the trend leads towards more realistic physics simulations, agent centered perception, and complex player interactions due to the rapidly increasing degrees of freedom that digital characters obtain. This new freedom requests another quality of the player’s environment, a quality of ambient intelligence that appears both plausible and in real time. This intelligence has, for example, to control more than $40$ facial muscles of digital characters while they interact with humans, but also to control a team of digital characters for the support of human players. This article emphasizes the current difference between AI systems and digital characters in commercial computer games and emphasizes the advantages that arise if shrinking the gap between them. We sketch some methods currently utilized in RoboCup and relates them to methods found in commercial computer games. We show how methods from RoboCup might contribute to game AI and improve both the performance and plausibility of its digital characters. Furthermore, we describe state-of-the-art game engines and discuss the challenge but also opportunity they are offering to AI research.

[13] Full text  Alexander Kleiner, Michael Brenner, Tobias BrĂ€uer, Christian Dornhege, Moritz Göbelbecker, Matthias Luber, Johann Prediger, Joerg StĂŒckler and Bernhard Nebel. 2005.
ResQ Freiburg: Team Description and Evaluation.
Technical Report. Institut fĂŒr Informatik, UniversitĂ€t Freiburg.

ResQ Freiburg is the world champion of the 2004 RoboCup competition in the Rescue simulation league. RoboCupRescue 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. To accomplish this, ResQ Freiburg introduced new methods for hierarchical path planning, death-time prediction of civilians, coordination of multi-agent city exploration, as well as an any-time rescue sequence optimization based on genetic algorithms. To evaluate the usefulness of these techniques we performed an extensive evaluation of the log files of the best participating teams in the competition. Our analysis explains the reasons for our team’s success, and thus could also provide an evaluation tool for future competitions.

[12] Alexander Kleiner, Michael Brenner, Tobias BrĂ€uer, Christian Dornhege, Moritz Göbelbecker, Matthias Luber, Johann Prediger, Jörg StĂŒckler and Bernhard Nebel. 2005.
Successful Search and Rescue in Simulated Disaster Areas.
In Robocup 2005: Robot Soccer World Cup IX, pages 323–334.

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 life-time, 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.

[11] T. A. NĂŒssle, Alexander Kleiner and M. Brenner. 2005.
Approaching Urban Disaster Reality: The ResQ Firesimulator.
In RoboCup 2004: Robot Soccer World Cup VIII, pages 474–482. In series: Lecture Notes in Computer Science #3276/2005.
DOI: 10.1007/978-3-540-32256-6_42.

The RoboCupRescue Simulation project aims at simulating large-scale disasters in order to explore coordination strategies for real-life rescue missions. This can only be achieved if the simulation itself is as close to reality as possible. In this paper, we present a new fire simulator based on a realistic physical model of heat development and heat transport in urban fires. It allows to simulate three different ways of heat transport (radiation, convection, direct transport) and the influence of wind. The protective effects of spraying water on non-burning buildings is also simulated, thus allowing for more strategic and precautionary behavior of rescue agents. Our experiments showed the simulator to create realistic fire propagations both with and without influence of fire brigade agents.

[10] Alexander Kleiner, B. Steder, C. Dornhege, D. Höfer, D. Meyer-Delius, J. Prediger, J. StĂŒckler, K. Glogowski, M. Thurner, M. Luber, M. Schnell, R. Kuemmerle, T. Burk, T. BrĂ€uer and B. Nebel. 2005.
RoboCupRescue - Robot League Team RescueRobots Freiburg (Germany).
In RoboCup 2005 (CDROM Proceedings), Team Description Paper, Rescue Robot League.
Note: (1st place in the autonomy competition, 4th place in the teleoperation competition)

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

2004
[9] Full text  Alexander Kleiner and Moritz Göbelbecker. 2004.
Rescue3D: Making Rescue Simulation Attractive to the Public.
Technical Report. Institut fĂŒr Informatik, UniversitĂ€t Freiburg.

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. The annually increasing number of teams participating in this league shows clearly that there is a high demand on research in this field. However, from our experience of participating at RoboCup as a team, but also from organizing RoboCupRescue as a public event, we learned about two strong limitations that arise practically during the competition: First, the current system offers only limited methods for comparing specific abilities of rescue teams. Second, the current presentation of the competition is only limited understandable for spectators. Within our effort in developing a new visualization of the rescue domain, we want to focus on these two limitations. We introduce a system for visualization that covers the demands of both developers and spectators.

[8] Alexander Kleiner, Michael Brenner, Tobias BrĂ€uer, Christian Dornhege, Moritz Göbelbecker, Matthias Luber, Johann Prediger and Joerg StĂŒckler. 2004.
ResQ Freiburg: Team Description and Evaluation.
In RoboCup 2004 (CDROM Proceedings), Team Description Paper, Rescue Simulation League.
Note: (1st place in the competition)

ResQ Freiburg is the world champion of the 2004 RoboCup competition in the Rescue simulation league. RoboCupRescue 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. To accomplish this, ResQ Freiburg introduced new methods for hierarchical path planning, death-time prediction of civilians, coordination of multi-agent city exploration, as well as an any-time rescue sequence optimization based on genetic algorithms. To evaluate the usefulness of these techniques we performed an extensive evaluation of the log files of the best participating teams in the competition. Our analysis explains the reasons for our team’s success, and thus could also provide an evaluation tool for future competitions.

2003
[7] Alexander Kleiner and T. Buchheim. 2003.
A Plugin-Based Architecture for Simulation in the F2000 League.
In In RoboCup 2003: Robot Soccer World Cup VII, pages 434–445.

Simulation has become an essential part in the development process of autonomous robotic systems. In the domain of robotics, developers often are confronted with problems like noisy sensor data, hardware malfunctions and scarce or temporarily inoperable hardware resources. A solution to most of the problems can be given by tools which allow the simulation of the application scenario in varying degrees of abstraction and the suppression of unwanted features of the domain (like e.g. sensor noise). The RoboCup scenario of autonomous mobile robots playing soccer is one such domain where the above mentioned problems typically arise.

[6] Full text  E. Schulenburg, T. Weigel and Alexander Kleiner. 2003.
Self-Localization in Dynamic Environments based on Laser and Vision Data.
In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 998–1004. IEEE. ISBN: 0-7803-7860-1.
DOI: 10.1109/IROS.2003.1250758.

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 selflocalization 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 [5] . 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.

2002
[5] Alexander Kleiner, M. Dietl and Bernhard Nebel. 2002.
Towards a Life-Long Learning Soccer Agent.
In In RoboCup 2002: Robot Soccer World Cup VI, pages 126–134.

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.

[4] Full text  T. Weigel, J. -S Gutmann, M. Dietl, Alexander Kleiner and B. Nebel. 2002.
CS Freiburg: Coordinating Robots for Successful Soccer Playing.
IEEE transactions on robotics and automation, 18(5):685–699. IEEE.
DOI: 10.1109/TRA.2002.804041.

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
[3] T. Weigel, Alexander Kleiner, F. Diesch, M. Dietl, J. -S Gutmann, B. Nebel, P. Stiegeler and B. Szerbakowski. 2001.
CS Freiburg 2001.
In RoboCup 2001 : Robot Soccer World Cup V, pages 26–38.

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.

2000
[2] Full text  Alexander Kleiner, Bernadette Sharp and Oliver Bittel. 2000.
Self Organising Maps for Value Estimation to Solve Reinforcement Learning Tasks.
In Proc. of the 2nd International Conference on Enterprise Information Systems (ICEIS 2000), pages 74–83.

Reinforcement learning has been applied recently more and more for the optimisation of agent behaviours. This approach became popular due to its adaptive and unsupervised learning process. One of the key ideas of this approach is to estimate the value of agent states. For huge state spaces however, it is difficult to implement this approach. As a result, various models were proposed which make use of function approximators, such as neural networks, to solve this problem. This paper focuses on an implementation of value estimation with a particular class of neural networks, known as self organizing maps. Experiments with an agent moving in a gridworld and the autonomous robot Khepera have been carried out to show the benefit of our approach. The results clearly show that the conventional approach, done by an implementation of a look-up table to represent the value function, can be out performed in terms of memory usage and convergence speed.

[1] Alexander Kleiner and Bernadette Sharp. 2000.
A New Algorithm for Learning Bayesian Classifiers from Data.
In Artificial Intelligence and Soft Computing, pages 191–197.

We introduce a new algorithm for the induction of classifiers from data, based on Bayesian networks. Basically this problem has already been examined from two perspectives: first, the induction of classifiers by learning algorithms for Bayesian networks, second, the induction of classifiers based on the naive Bayesian classifier. Our approach is located between these two perspectives; it eliminates the disadvantages of both while exploiting their advantages. In contrast to recently appeared refinements of the naive Bayes classifier, which captures single correlations in the data, we have developed an approach which captures multiple correlations and furthermore does a trade-off between complexity and accuracy. In this paper we evaluate the implementation of our approach with data sets from the machine learning repository and data sets artificially generated by Bayesian networks.