Alexander Kleiner's Publications

(List Chronological) (List Categorical)

2011

D. Meyer-Delius, M. Beinhofer, A. Kleiner, and W. Burgard.
Using artificial landmarks to reduce the ambiguity in the environment of a mobile robot.
In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), 2011.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
Alexander Kleiner and Christian Dornhege.
Mapping for the Support of First Responders in Critical Domains.
Journal of Intelligent and Robotic Systems (JIRS), 2011, 10.1007/s10846-010-9520-x.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
Q. Hamp, L. Reindl, and A. Kleiner.
Lessons Learned from German Research for USAR.
In Proc. of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR), 2011, Winner of the Young Author's Award.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
R. Kümmerle, B. Steder, C. Dornhege, A. Kleiner, G. Grisetti, and W. Burgard.
Large Scale Graph-based SLAM using Aerial Images as Prior Information.
Autonomous Robots, 2011.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
A. Kleiner, A. Kolling, M. Lewis, and K. Sycara.
Hierarchical Visibility for Guaranteed Search in Large-Scale Outdoor Terrain.
Journal of Autonomous Agents and Multi-Agent Systems (JAAMAS), 2011.
(PDF) (BIB) (DOI: 10.1007/s10458-011-9180-7) (Show abstract) (Hide abstract)

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.
A. Kolling, A. 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.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
A. Kleiner, D. 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.
(PDF) (BIB) (VIDEO WMV 8MB) (VIDEO FLV 8MB) (Show abstract) (Hide abstract)

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.
A. Kleiner, B. Nebel, and V. Ziparo.
A Mechanism for Dynamic Ride Sharing based on Parallel Auctions.
In Proc. of the 22th International Joint Conference on Artificial Intelligence (IJCAI), 2011.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
C. Dornhege and A. Kleiner.
A Frontier-Void-Based Approach for Autonomous Exploration in 3D.
In Proc. of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR), 2011, To appear.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.

2010

P. Velagapudi, A. Kleiner, N. Brooks, P. Scerri, M. Lewis, and K. Sycara.
RoboCupRescue - Virtual Robots Team STEEL (USA).
In RoboCup 2010 (CDROM Proceedings), Team Description Paper, Rescue Simulation League, 2010.
(PDF) (BIB) (Show abstract) (Hide abstract)

Abstract. 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.
C. Dornhege, J. Bendler, R. Bersan, P. Blohm, M. Gloderer, A. Hertle, T. Liebetraut, D. C. Puyol, A. Kleiner, and B. Nebel.
RoboCupRescue 2010 - Robot League Team RescueRobots Freiburg (Germany).
In RoboCup 2010 (CDROM Proceedings), Team Description Paper, Rescue Robot League, 2010.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
W. Mou and A. Kleiner.
Online Learning Terrain Classification for Adaptive Velocity Control.
In Proc. of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR), 2010.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
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), 2010.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
D. Sun, A. Kleiner, and C. Schindelhauer.
Decentralized Hash Tables For Mobile Robot Teams Solving Intra-Logistics Tasks.
In Proc. of the 9th Int. Joint Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2010), 2010.
(PDF) (BIB) (VIDEO 54MB) (Show abstract) (Hide abstract)

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.
A. Kolling, A. Kleiner, M. Lewis, and K. Sycara.
Pursuit-Evasion in 2.5d based on Team-Visibility.
In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), 2010.
(PDF) (BIB) (VIDEO 4MB) (Show abstract) (Hide abstract)

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.
A. Kolling, A. Kleiner, M. Lewis, and K. 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, 2010.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
D. Maier and A. Kleiner.
Improved GPS Sensor Model for Mobile Robots in Urban Terrain.
In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), 2010.
(PDF) (BIB) (VIDEO 4MB) (Show abstract) (Hide abstract)

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.

2009

A. Kleiner, C. Scrapper, and A. Jacoff.
RoboCupRescue Interleague Challenge 2009: Bridging the gap between Simulation and Reality.
In Proc. of the Int. Workshop on Performance Metrics for Intelligent Systems (PerMIS), 2009.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
A. Kleiner and C. Dornhege.
Operator-Assistive Mapping in Harsh Environments.
In Proc. of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR), 2009, (Best Paper Award Finalist).
(PDF) (BIB) (VIDEO 3MB) (Show abstract) (Hide abstract)

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.
R. Kümmerle, B. Steder, C. Dornhege, M. Ruhnke, G. Grisetti, C. Stachniss, and A. Kleiner.
On Measuring the Accuracy of SLAM Algorithms.
Autonomous Robots, 2009.
(PDF) (BIB) (LINK) (Show abstract) (Hide abstract)

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.
D. Sun, A. 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, 2009.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
W. Burgard, C. Stachniss, G. Grisetti, B. Steder, R. Kümmerle, C. Dornhege, M. Ruhnke, A. Kleiner, and Juan D. Tard�s.
A Comparison of SLAM Algorithms Based on a Graph of Relations.
In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), 2009.
(PDF) (BIB) (VIDEO 3MB) (Show abstract) (Hide abstract)

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.
R. Kümmerle, B. Steder, C. Dornhege, A. Kleiner, G. Grisetti, and W. Burgard.
Large Scale Graph-based SLAM using Aerial Images as Prior Information.
In Proceedings of Robotics: Science and Systems (RSS), 2009.
(PDF) (BIB) (VIDEO 58MB) (Show abstract) (Hide abstract)

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.

2008

A. 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), 2008.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
C. Dornhege, A. Kleiner, R. Kuemmerle, B. Steder, W. Burgard, and B. Nebel.
SP-Freiburg TechX Challenge Technical Paper.
In TechX Challenge, 2008, Finalist.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
A. Kleiner.
Mapping and Exploration for Search and Rescue with Humans and Mobile Robots.
Ph.D. dissertation, 2008.
(PDF) (BIB) (LINK) (Show abstract) (Hide abstract)

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.
Alexander Kleiner, Gerald Steinbauer, and Franz Wotawa.
Automated Learning of Communication Models for Robot Control Software.
In MBS 2008 - Workshop on Model-Based Systems, 18th European Conference on Artificial Intelligence (ECAI), 2008.
(PDF) (BIB) (Show abstract) (Hide abstract)

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

V.A. Ziparo, A. Kleiner, B. Nebel, and D. Nardi.
RFID-Based Exploration for Large Robot Teams.
In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), 2007.
(PDF) (BIB) (VIDEO 5MB) (Show abstract) (Hide abstract)

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.
H. Kenn and A. Kleiner.
Towards the Integration of Real-Time Real-World Data in Urban Search and Rescue Simulation.
In MobileResponse, 2007.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
S. Balakirsky, S. Carpin, A. 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, 2007.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
A. Kleiner and C. Dornhege.
Real-time Localization and Elevation Mapping within Urban Search and Rescue Scenarios.
Journal of Field Robotics, 2007.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
A. Kleiner, C. Dornhege, and D. Sun.
Mapping Disaster Areas Jointly: RFID-Coordinated SLAM by Humans and Robots.
In Proc. of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR), 2007.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
A. Kleiner and R. Kümmerle.
Genetic MRF Model Optimization for Real-Time Victim Detection in Search and Rescue.
In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), 2007.
(PDF) (BIB) (VIDEO 5MB) (Show abstract) (Hide abstract)

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.
C. Dornhege and A. Kleiner.
Fully Autonomous Planning and Obstacle Negotiation on Rough Terrain Using Behavior Maps.
In Video Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), 2007.
(PDF) (BIB) (VIDEO 49MB) (Show abstract) (Hide abstract)

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.
A. Kleiner and D. Sun.
Decentralized SLAM for Pedestrians without direct Communication.
In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), 2007.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
V.A. Ziparo, A. Kleiner, L. Marchetti, A. Farinelli, and D. Nardi.
Cooperative Exploration for USAR Robots with Indirect Communication.
In Proc. of 6th IFAC Symposium on Intelligent Autonomous Vehicles (IAV), 2007.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
C. Dornhege and A. Kleiner.
Behavior Maps for Online Planning of Obstacle Negotiation and Climbing on Rough Terrain.
In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), 2007.
(PDF) (BIB) (VIDEO 5MB) (Show abstract) (Hide abstract)

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.

2006

A. Kleiner and V.A. Ziparo.
RoboCupRescue - Simulation League Team RescueRobots Freiburg (Germany).
In RoboCup 2006 (CDROM Proceedings), Team Description Paper, Rescue Simulation League, 2006, (1st place in the competition).
(PDF) (BIB) (PPT) (VIDEO 32MB) (Show abstract) (Hide abstract)

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.
A. Kleiner, C. Dornhege, R. Kümmerle, M. Ruhnke, B. Steder, B. Nebel, P. Doherty, M. Wzorek, P. Rudol, G. Conte, S. Durante, and D. Lundstrom.
RoboCupRescue - Robot League Team RescueRobots Freiburg (Germany).
In RoboCup 2006 (CDROM Proceedings), Team Description Paper, Rescue Robot League, 2006, (1st place in the autonomy competition).
(PDF) (BIB) (PPT) (VIDEO 13MB) (Show abstract) (Hide abstract)

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.
A. Kleiner, J. Prediger, and B. Nebel.
RFID Technology-based Exploration and SLAM for Search And Rescue.
In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), 2006.
(PDF) (BIB) (VIDEO 13MB) (Show abstract) (Hide abstract)

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.
A. 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, 2006.
(PDF) (BIB) (PPT) (LINK) (Show abstract) (Hide abstract)

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).
C. Dornhege and A. Kleiner.
Visual Odometry for Tracked Vehicles.
In Proc. of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR), 2006.
(PDF) (BIB) (VIDEO 5MB) (Show abstract) (Hide abstract)

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.

2005

A. 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.
RoboCupRescue - Robot League Team RescueRobots Freiburg (Germany).
In RoboCup 2005 (CDROM Proceedings), Team Description Paper, Rescue Robot League, 2005, (1st place in the autonomy competition, 4th place in the teleoperation competition).
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
A. Kleiner, M. Brenner, T. Bräuer, C. Dornhege, M. Göbelbecker, M. Luber, J. Prediger, J. Stückler, and B. Nebel.
ResQ Freiburg: Team Description and Evaluation.
TR, 2005.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
A. Kleiner, M. Brenner, T. Bräuer, C. Dornhege, M. Göbelbecker, M. Luber, J. Prediger, J. Stückler, and B. Nebel.
Successful Search and Rescue in Simulated Disaster Areas.
In Robocup 2005: Robot Soccer World Cup IX, 2005.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
A. Kleiner.
Game AI: The Shrinking Gap Between Computer Games and AI Systems.
Ambient Intelligence: The Evolution of Technology, Communication and Cognition Towards the Future of Human-Computer Interaction, 2005.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.

2004

A. Kleiner and M. Göbelbecker.
Rescue3D: Making Rescue Simulation Attractive to the Public.
TR, 2004.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
A. Kleiner, M. Brenner, T. Bräuer, C. Dornhege, M. Göbelbecker, M. Luber, J. Prediger, and J. Stückler.
ResQ Freiburg: Team Description and Evaluation.
In RoboCup 2004 (CDROM Proceedings), Team Description Paper, Rescue Simulation League, 2004, (1st place in the competition).
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
T. A. Nüssle, A. Kleiner, and M. Brenner.
Approaching Urban Disaster Reality: The ResQ Firesimulator.
In RoboCup 2004: Robot Soccer World Cup VIII, 2004.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.

2003

E. Schulenburg, T. Weigel, and A. Kleiner.
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), 2003.
(PDF) (BIB) (VIDEO 3MB) (Show abstract) (Hide abstract)

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.
A. Kleiner and T. Buchheim.
A Plugin-Based Architecture for Simulation in the F2000 League.
In RoboCup 2003: Robot Soccer World Cup VII, 2003.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.

2002

T. Weigel, J.-S. Gutmann, M. Dietl, A. Kleiner, and B. Nebel.
CS Freiburg: Coordinating Robots for Successful Soccer Playing.
IEEE Transactions on Robotics and Automation, 2002.
(PDF) (BIB) (VIDEO 3MB) (Show abstract) (Hide abstract)

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.
A. Kleiner, M. Dietl, and B. Nebel.
Towards a Life-Long Learning Soccer Agent.
In RoboCup 2002: Robot Soccer World Cup VI, 2002.
(PDF) (BIB) (VIDEO 16MB) (Show abstract) (Hide abstract)

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.

2001

T. Weigel, A. Kleiner, F. Diesch, M. Dietl, J.-S. Gutmann, B. Nebel, P. Stiegeler, and B. Szerbakowski.
CS Freiburg 2001.
In RoboCup 2001 : Robot Soccer World Cup V, 2001.
(PDF) (BIB) (Show abstract) (Hide abstract)

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

A. Kleiner, B. Sharp, and O. Bittel.
Self Organising Maps for Value Estimation to Solve Reinforcement Learning Tasks.
In Proc. of the 2nd International Conference on Enterprise Information Systems (ICEIS 2000), 2000.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.
A. Kleiner and B. Sharp.
A New Algorithm for Learning Bayesian Classifiers from Data.
In Artificial Intelligence and Soft Computing, 2000.
(PDF) (BIB) (Show abstract) (Hide abstract)

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.

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.