Abstract

The goal of this advanced tutorial is to address key research issues within the Simultaneous Localisation and map Building (SLAM) problem. These will span the issues of algorithmic complexity, implementation, environmental representation, loop closing and sensor data processing. Two thirds of the tutorial will be focused on computational cost problems in SLAM. In particular, new refinements to Covariance Intersection (CI) algorithms, which exploit partial cross correlation information, will be presented. This will be accompanied by in introduction to DenseSLAM which permits the fusion of all sensory data into an environmental representation yielding a detailed multi-dimensional description of a robot's surroundings, to aid navigation. Further, a solution to the SLAM problem with Rao-Blackwellized particle filters for the factorization of highly dimensional state spaces will be given. Information based SLAM algorithms, aimed at gaining a better understanding of sparse information based representations using the Thin Junction Tree Filter (TJTF) and Sparse Extended Information Filter (SEIF) will be presented with the aim of controlling the size of the information matrix in a consistent manner. A hierarchical mapping method for large scale SLAM that has a natural extension to multi-vehicle mapping will also be presented.

The remaining third of the tutorial will be devoted to SLAM implementation issues. The importance of observability and fast drifting inertial sensor errors in a real airborne application on an unmanned air vehicle (UAV), will be presented. This part of the tutorial will cover important areas such as the use of a complementary filter formulation for reducing computational complexity and joint compatibility methods to improve data association. Real SLAM implementations showing the issues involved in various sensing methods and new techniques for processing sensor data for the explicit improvement of SLAM will also be presented.

Copies of all presentation slides, relevant papers and references and a website, especially produced for the tutorial, containing relevant links to relevant SLAM data, demonstrations, papers and other information will be provided in this tutorial.

Tutorial Outline

Syllabus: Dealing with dense information; Particle filtering; Loop closing; Covariance Intersection; Sparse matrix information based representations; Metric and topological maps; UAV SLAM; Feature rich representations.

Summaries of Individual Presentations

Representation of Dense Information in Large Areas -- Juan Nieto, Eduardo Nebot
When a robot performs exploration without any absolute information it needs to perform SLAM. Most SLAM algorithms obtain a sparse representation of the environment, which eventually may not be enough to achieve tasks such as path planning. This section will address this problem, presenting an approach called DenseSLAM that permits the fusion and maintainance of all recorded sensor data into an environmental representation, obtaining a detailed multi-dimensional description of the robots surroundings. Finally it is shown how this DenseSLAM, detailed, multi-dimensional description of the environment can be used to improve the vehicle navigation process. Experimental results in outdoor environments will also be presented.

Rao-Blackwellized Particle Filters and Loop Closing -- Cyrill Stachniss, Wolfram Burgard
In this section, we will present the key ideas of particle filters and how Rao-Blackwellization can be used to efficiently factorize high-dimensional SLAM state spaces. We will then cover the FastSLAM algorithm, which represents the belief about the landmark poses with Gaussian distributions. We then apply this idea to occupancy grid maps. We will describe efficient ways to represent the maps and how to generate better proposal distributions in order to reduce the number of particles needed. We finally present a decision-theoretic approach to generate actions for actively closing loops during exploration.

Refinements to Covariance Intersection -- Simon Julier
As is well known, one of the greatest hurdles in deploying SLAM is the computational cost - the state space is proportional to the size of beacons and the computational and storage costs scale nonlinearily with the size of the state space. One family of algorithms which addresses this issue is that based on Covariance Intersection (CI). CI has the advantage that it requires no special structure or management that many other suboptimal SLAM algorithms need. However, in its raw form CI leads to extremely conservative estimates and is of limited use. In this section of the tutorial I shall provide an overview of the CI algorithms, beginning with the basic form and showing how a number of refinements can be made to significantly improve its performance.

Multivehicle Mapping in Large Environments -- Jose Neira, Carlos Estrada and Juan D. Tardos

Over the past few years there has been an increasing interest in reducing the computational time and memory requirements when performing SLAM in large areas. In this presentation we will discuss a hierarchical mapping method for large scale SLAM: the lower (or local) map level is composed of a set of local maps that are guaranteed to be statistically independent. The upper (or global) level is an adjacency graph whose arcs are labelled with the relative location between local maps. An estimation of these relative locations is maintained at this level in a relative stochastic map.

Its main advantage over previous proposals is the efficient maintenance of loop consistency, which allows to improve map precision. A robust, stable and local parametrization gives the method good numerical performance near the current state estimate. An additional advantage of this approach is its natural extension to multi-robot map building: several robots can contribute new local maps or refine previously built local maps.

We will present a new method to impose loop consistency that makes careful use of stochastic map techniques. Our representation introduces highly sparse matrices that can be exploited in the calculation process by means of specialized sparse methods. While maintaining independence at the local level, this method imposes consistency at the global level at a computational cost linear with the size of the loop. Experimental results validate our method: we obtain a close to optimal global map of a building with several big loops (in the 200m to 350m range) in less than one second. We have also carried out simulations that assert the accuracy of Hierarchical SLAM for loops up to 3.6km long.

Sparse Information Based Representations -- M. Walter, John Leonard
In this talk, I will detail a few of the more promising information-based SLAM algorithms, including the Thin Junction Tree Filter (TJTF), the Treemap implementation, and the Sparse Extended Information Filter (SEIF). I will pay particular attention to the different ways in which the estimators achieve exactly sparse approximations to the posterior and, in turn, to the consequences regarding the accuracy of the representations. Revealing the resulting inconsistency of the global SEIF map, I will then present alternative strategies for controlling the population of the information matrix in a consistent manner.

Combining Metric and Topological Maps -- A. Martinelli, Roland Siegwart
This section will present a multi-resolutional approach to SLAM, allowing high precision and distinctiveness into the map building process. The method combines the metric and topological paradigms. The metric approach is based on the extended Kalman filter and uses the concept of the relative map. In the topological framework, a fingerprint sequence approach is used. The first part of this section regards the relative map whose estimated state contains quantities invariant under shift and rotation. The problem of optimal exploratory paths will be discussed. The second part will demonstrate the concepts of finger printing. An algorithm for matching two finger prints to localize the robot from a topological point of view, will be discussed. In any multi-level representation, a crucial point is the linkage between the two maps of differing resolution. This section will present a possible solution to this, based on the relative map concept.

UAV Navigation: Airborne Inertial SLAM -- J. Kim, Salah Sukkarieh
This tutorial will address the current challenges in the implementation of SLAM on an unmanned air vehicle (UAV) platform. Airborne implementations impose several difficulties. This section will present an airborne SLAM algorithm based on an extended Kalman filter which incorporates an Inertial Measurement Unit (IMU) and a passive vision system. Then, a complementary filter formulation is provided to tackle the computational complexity, and a reliable data association method, based on a joint compatibility, will be shown. To understand the underlying structure in inertial SLAM, the observability is also analyzed and the issues in fusing global information such as GPS are addressed. Experimental results from the flight trials are also presented.

Rich Representations with RADAR and LADAR -- Martin Adams
A fundamental issue within SLAM algorithms is the correct interpretation of sensor data. Millimetre Wave RADAR provides a robust method for range detection in outdoor environments. In each sensed direction, a range bin is produced, providing the received power spectrum of the received signal as a function of range. This offers the fundamental advantage of the possibility of sensing multiple objects within the line-of-sight of the RADAR. This section will show new processing techniques, which are reliably able to estimate target presence probabilities based on estimated signal-to-noise power ratios. An augmented state SLAM formulation will be demonstrated which, as well as being able to estimate robot and feature coordinates, is able to estimate relative target RCSs and the power-range losses within the RADAR. A modified scale-space approach will also be presented which is able to produce robot pose invariant features from LADAR range data. This approach is able to successfully segment and smooth range data based on line segments, but leaves all other data (corners, curves, clutter) unaffected. Dominant features, which are able to survive different scales will be shown to provide truly pose invariant beacons, viable for SLAM.

Author Biographies

Juan Nieto
Juan Nieto received the Bachelor's degree in Electrical Engineering from the Universidad Nacional del Sur, (Argentina) in 2000. He started his PhD in 2001 in the Australian Centre for Field Robotics, University of Sydney under the supervision of Prof. Eduardo Nebot. He submitted his thesis on March 2005. The thesis’s title is “Detailed environment representation for the SLAM problem”. His main interest is in navigation systems, filtering, probabilistic modelling. In particular in the area of navigation and mapping in large outdoor environments.

Eduardo Mario Nebot received the Bachelor's degree in Electrical Engineering from the Universidad Nacional del Sur, (Argentina) and M.S. And PH.d. from Colorado State University USA. He is a Professor at the University of Sydney in the Department of Aeronautical Mechanical and Mechatronic Engineering. He has been a faculty member since 1992 and currently the director of the Australian Centre for Field Robotics. His current research contents Navigation and Guidance algorithms; Simultaneous navigation and mapping in large outdoor environments and Mining Automation. He has also been involved in different automation projects in the stevedoring, mining and cargo handling industries. Dr. Nebot is a Senior member of the Institute of Electrical and Electronic Engineering.

Wolfram Burgard
Wolfram Burgard is a professor for computer science at the University of Freiburg and head of the research lab for Autonomous Intelligent Systems. His areas of interest lie in artificial intelligence and mobile robots. Wolfram Burgard's research mainly focuses on the development of robust and adaptive techniques for state estimation and control. Over the past years, his group has developed a series of innovative probabilistic techniques for robot navigation and control. They cover different aspects such as localization, map-building, path-planning and exploration. Wolfram Burgard has also carried out several installations of mobile robots in public spaces such as museums and exhibitions. In 1997 he and his group deployed Rhino as the first interactive mobile tour-guide robot in the Deutsches Museum Bonn in Germany. Wolfram Burgard has published over 100 articles and papers at outstanding journals and conferences. He received eight outstanding paper awards.

Simon Julier
Simon Julier is the Acting Director of the 3D Virtual and Mixed Environments Research Centre at the Naval Research Laboratory in Washington DC. He received a DPhil in robotics from the Robotics Research Group at Oxford University in 1997. Since 1997 he has been working at the Naval Research Laboratory in a number of research areas including the development of mobile augmented reality for situation awareness and scalable fusion of disparate sources of information. He lead the development on the Battlefield Augmented Reality System (BARS). This project included research into the design of compact tracking systems capable of tracking a user's head in an outdoor environment.

Jose Neira

Jose Neira was born in Bogota, Colombia, in 1963. He received the M.S. degree in Computer Science from the Universidad de los Andes, Colombia, in 1986, and the Ph.D. degree in Computer Science from the University of Zaragoza, Spain, in 1993. He is Associate Professor with the Departamento de Informatica e Ingenieria de Sistemas, University of Zaragoza, where he is in charge of courses in Compiler Theory, Computer Vision and Simultaneous Localization and Mapping. His current research interests include autonomous robots, data association, and environment modelling. He has been invited speaker at the 2000 and 2002 IEEE ICRA workshops on Simultaneous Localization and Mapping in San Francisco and Washington respectively, and also lecturer at the 2004 SLAM Summer School in Toulouse, France. His complete list of publications is available at http://www.cps.unizar.es/~neira/

Matthew Walter (student of John Leonard)
Matthew Walter is currently a graduate student in the Computer Science and Artificial Intelligence Laboratory (CSAIL) at the Massachusetts Institute of Technology. A student of Professor John Leonard, he currently works on feature-based SLAM with particular interest in the issues related to scalability in regards to the size of the environment as well as the development of efficient strategies for performing cooperative SLAM. To that end, his recent research has focused on the canonical formulation of the SLAM problem in which scalability is achieved by deliberately controlling the population of the information matrix.

Agostino Martinelli (working with Roland Siegwart)
Dr. Martinelli is a senior researcher at the Autonomous Systems Laboratory (LSA), School of Engineering, EPFL Lausanne. He obtained his masters degree in theoretical physics at the University of Rome Tor Vergata in 1994, and his doctoral degree in Astrophysics at the University of Rome La Sapienza in 1999. His main research interests in mobile robotics are multisensor fusion for robot localisation, simultaneous localization and odometry error learning and SLAM.

Jonghyuk Kim (student of Salah Sukkarieh)
Dr. Jonghyuk Kim is a postdoctoral fellow in the Centre for Autonomous Systems. He obtained his PhD degree in Aerospace, Mechanical and Mechatronic engineering at the University of Sydney in 2004. He worked as a GPS system developer at Navicom Ltd, South Korea until 2000. He has developed a real-time airborne SLAM system for a fixed-wing UAV platform, and real-time GPS/INS navigation systems which were successfully used for a distributed feature-tracking demonstration across multiple UAVs. His research focuses are autonomous airborne navigation, simultaneous localisation and mapping, multi-sensor fusion, distributed and decentralized systems, and real-time embedded systems.

Dr. Salah Sukkarieh is a Senior Lecturer at the University of Sydney in the School of Aerospace, Mechanical and Mechatronic Engineering. He is also the Research Leader for Aerospace at the Australian Centre for Field Robotics in the Centre for Autonomous Systems. He obtained his PhD in 2000 at the University of Sydney researching in the area of inertial navigation. His current research areas include SLAM for airborne and ground platforms, cooperative control, and Systems of Systems Design.

Martin Adams
Martin Adams is an Associate Professor in the School of Electrical and Electronic Engineering, NTU, Singapore. He obtained his first degree in Engineering Science at the University of Oxford, U.K, in 1988 and continued to study for a D.Phil at the Robotics Research Group, University of Oxford, which he received in 1992. He continued his research in autonomous robot navigation as a project leader and part time lecturer at the Institute of Robotics, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland. He later served as a senior research scientist in robotics and control, in the field of semiconductor assembly automation, at the European Semiconductor Equipment Centre (ESEC), Switzerland. Dr. Adams is the author of Sensor Design, Modelling and Data Processing for Autonomous Navigation, a book released by World Scientific Publishers in 1999. He has been principle investigator of two robotics projects at NTU, one of which was in collaboration with SIMTech, and is currently leading a third, large research project which is coordinating researchers from NTU, SIMTech and NUS, in providing autonomous cleaning and surveillance vehicles to Sentosa and the Singapore Zoo.


Supporting Materials Offered
Copies of all presentation slides, relevant papers and references and a website, especially produced for the tutorial, containing relevant links to data, demonstrations, papers and other information.