NTU PAL Thesis Defense: Mobile Robot Localization in Large-scale Dynamic Environments

Mobile Robot Localization in Large-scale Dynamic Environments

Shao-Wen Yang

Doctoral Dissertation Defense

Department of Computer Science and Information Engineering

National Taiwan University

Time: Thursday, 19 May, 2011 at 8:00AM +0800 (CST)

Location: R542, Der-Tian Hall

Advisor: Chieh-Chih Wang

Thesis Committee:

Li-Chen Fu

Jane Yung-Jen Hsu

Han-Pang Huang

Ta-Te Lin

Chu-Song Chen, Sinica

Jwu-Sheng Hu, NCTU

John J. Leonard, MIT

Abstract:

Localization is the most fundamental problem to providing a mobile robot with autonomous capabilities. Whilst simultaneous localization and mapping (SLAM) and moving object tracking (MOT) have attracted immense attention in the last decade, the focus of robotics continues to shift from stationary robots in a factory automation environment to mobile robots operating in human-inhabited environments. State of the art relying on the static world assumption can fail in the real environment that is typically dynamic. Specifically, the real environment is challenging for mobile robots due to the variety of perceptual inconsistency over space and time. Development of situational awareness is particularly important so that the mobile robots can adapt quickly to changes in the environment.

In this thesis, we explore the problem of mobile robot localization in the real world in theory and practice, and show that localization can benefit from both stationary and dynamic entities.

The performance of ego-motion estimation depends on the consistency between sensory information at successive time steps, whereas the performance of localization relies on the consistency between the sensory information and the a priori map. The inconsistencies make a robot unable to robustly determine its location in the environment. We show that mobile robot localization, as well as ego-motion estimation, and moving object detection are mutually beneficial. Most importantly, addressing the inconsistencies serves as the basis for mobile robot localization, and forms a solid bridge between SLAM and MOT.

Localization, as well as moving object detection, is not only challenging but also difficult to evaluate quantitatively due to the lack of a realistic ground truth. As the key competencies for mobile robotic systems are localization and semantic context interpretation, an annotated data set, as well as an interactive annotation tool, is released to facilitate the development, evaluation and comparison of algorithms for localization, mapping, moving object detection, moving object tracking, etc.

In summary, a unified stochastic framework is introduced to solve the problems of motion estimation and motion segmentation simultaneously in highly dynamic environments in real time. A dual-model localization framework that uses information from both the static scene and dynamic entities is proposed to improve the localization performance by explicitly incorporating, rather than filtering out, moving object information. In the ample experiment, a sub-meter accuracy is achieved, without the aid of GPS, which is adequate for autonomous navigation in crowded urban scenes. The empirical results suggest that the performance of localization can be improved when handling the changing environment explicitly.

Download:

• Thesis draft: http://any.csie.ntu.edu.tw/thesis/yang_thesis-v1_0.pdf

Lab Meeting April 20, 2011 (fish60): Donut as I do: Learning from failed demonstrations

Title: Donut as I do: Learning from failed demonstrations In: 2011 IEEE International Conference on Robotics and Automation Authors: Grollman, Daniel (Ecole Polytechnique Federale de Lausanne), Billard, Aude (EPFL) Abstract The canonical Robot Learning from Demonstration scenario has a robot observing human demonstrations of a task or behavior in a few situations, and then developing a generalized controller. ... However, the underlying assumption is that the demonstrations are successful, and are appropriate to reproduce. We, instead, consider the possibility that the human has failed in their attempt, and their demonstration is an example of what not to do. Thus, instead of maximizing the similarity of generated behaviors to those of the demonstrators, we examine two methods that deliberately avoid repeating the human's mistakes. Link

Lab Meeting April 13, 2011 (Will): Hilbert Space Embeddings of Hidden Markov Models (ICML2010)

Titile: Hilbert Space Embeddings of Hidden Markov Model

In: ICML 2010

Authors: Le Song, Byron Boots, Sajid Siddiqi, Geoffrey Gordon, Alex Smola

Abstract

Hidden Markov Models (HMMs) are important tools for modeling sequence data. However, they are restricted to discrete latent states, and are largely restricted to Gaussian and discrete observations. And, learning algorithms for HMMs have predominantly relied on local search heuristics, with the exception of spectral methods such as those described below. We propose a nonparametric HMM that extends traditional HMMs to structured and non-Gaussian continuous distributions. Furthermore, we derive a local-minimum-free kernel spectral algorithm for learning these HMMs. We apply our method to robot vision data, slot car inertial sensor data and audio event classification data, and show that in these applications, embedded HMMs exceed the previous state-of-the-art performance.

[pdf]

Lab Meeting April 13, 2011 (Jimmy): WiFi-SLAM Using Gaussian Process Latent Variable Models (IJCAI2007)

Title: WiFi-SLAM Using Gaussian Process Latent Variable Models
In: IJCAI 2007
Authors: Brian Ferris, Dieter Fox, and Neil Lawrence

Abstract
WiFi localization, the task of determining the physical location of a mobile device from wireless signal strengths, has been shown to be an accurate method of indoor and outdoor localization and a powerful building block for location-aware applications. However, most localization techniques require a training set of signal strength readings labeled against a ground truth location map, which is prohibitive to collect and maintain as maps grow large. In this paper we propose a novel technique for solving the WiFi SLAM problem using the Gaussian Process Latent Variable Model (GPLVM) to determine the latent-space locations of unlabeled signal strength data. We show how GPLVM, in combination with an appropriate motion dynamics model, can be used to reconstruct a topological connectivity graph from a signal strength sequence which, in combination with the learned Gaussian Process signal strength model, can be used to perform efficient localization.

[pdf]

Lab Meeting March 30, 2011 (Chih-Chung): Progress Report

I will show my recent work of moving target tracking and following, using laser scanner and PIONEER3 robot.

Lab Meeting March 30, 2011 (Chung-Han): Progress Report

I will show the updated ground-truth annotation system with the newly collected data set.

Lab Meeting March 23, 2011 (David): Object detection and tracking for autonomous navigation in dynamic environments (IJRR 2010)

Title: Object detection and tracking for autonomous navigation in dynamic environments (IJRR 2010)

Authors: Andreas Ess, Konrad Schindler, Bastian Leibe, Luc Van Gool

Abstract:
We address the problem of vision-based navigation in busy inner-city locations, using a stereo rig mounted on a mobile platform. In this scenario semantic information becomes important: rather than modeling moving objects as arbitrary obstacles, they should be categorized and tracked in order to predict their future behavior. To this end, we combine classical geometric world mapping with object category detection and tracking. Object-category-specific detectors serve to find instances of the most important object classes (in our case pedestrians and cars). Based on these detections, multi-object tracking recovers the objects' trajectories, thereby making it possible to predict their future locations, and to employ dynamic path planning. The approach is evaluated on challenging, realistic video sequences recorded at busy inner-city locations.

Link

Lab Meeting March 23, 2011 (Shao-Chen): A Comparison of Track-to-Track Fusion Algorithms for Automotive Sensor Fusion (MFI2008)

Title: A Comparison of Track-to-Track Fusion Algorithms for Automotive Sensor Fusion (MFI2008, Multisensor Fusion and Integration for Intelligent Systems)

Authors: Stephan Matzka and Richard Altendorfer

Abstract:

In  exteroceptive  automotive  sensor  fusion,  sensor data are usually only available as processed, tracked object data and not as  raw sensor data. Applying a Kalman filter  to such data  leads  to  additional  delays  and  generally  underestimates the  fused  objects'  covariance  due  to temporal  correlations  of individual  sensor  data  as  well  as inter-sensor  correlations.  We compare the performance of a standard asynchronous Kalman filter applied to tracked sensor data to several algorithms for the track-to-track fusion  of sensor objects of unknown  correlation, namely covariance  union,  covariance  intersection,  and  use  of cross-covariance.  For  the  simulation  setup  used  in  this  paper, covariance  intersection  and  use  of  cross-covariance  turn  out to  yield  significantly  lower  errors  than  a  Kalman  filter  at  a comparable computational load.

Link

Lab Meeting March 16th, 2011 (Andi): 3D Deformable Face Tracking with a Commodity Depth Camera

Qin Cai , David Gallup , Cha Zhang and Zhengyou Zhang

Abstract: Recently, there has been an increasing number of depth cameras available at commodity prices. These cameras can usually capture both color and depth images in real-time, with limited resolution and accuracy. In this paper, we study the problem of 3D deformable face tracking with such commodity depth cameras. A regularized maximum

likelihood deformable model fitting (DMF) algorithm is developed, with special emphasis on handling the noisy input depth data. In particular, we present a maximum likelihood solution that can accommodate sensor noise represented by an arbitrary covariance matrix, which allows more elaborate modeling of the sensor’s accuracy. Furthermore, an 1 regularization scheme is proposed based on the semantics of the deformable face model, which is shown to be very effective in improving the tracking results. To track facial movement in subsequent frames, feature points in the texture images are matched across frames and integrated into the DMF framework seamlessly. The effectiveness of the proposed method is demonstrated with multiple sequences with ground truth information.

Full Paper

Lab Meeting March 9th, 2011(KuoHuei): progress report

I will present my progress on Neighboring Objects Interaction models and tracking system.

Lab Meeting March 9, 2011 (Wang Li): Real-time Identification and Localization of Body Parts from Depth Images (ICRA 2010)

Real-time Identification and Localization of Body Parts from Depth Images

Christian Plagemann
Varun Ganapathi
Daphne Koller
Sebastian Thrun

Abstract

We deal with the problem of detecting and identifying body parts in depth images at video frame rates. Our solution involves a novel interest point detector for mesh and range data that is particularly well suited for analyzing human shape. The interest points, which are based on identifying geodesic extrema on the surface mesh, coincide with salient points of the body, which can be classified using local shape descriptors. Our approach also provides a natural way of estimating a 3D orientation vector for a given interest point. This can be used to normalize the local shape descriptors to simplify the classification problem as well as to directly estimate the orientation of body parts in space.
Experiments show that our interest points in conjunction with a boosted patch classifier are significantly better in detecting body parts in depth images than state-of-the-art sliding-window based detectors.

Paper Link

Article: Perception beyond the Here and Now

by Albrecht Schmidt, Marc Langheinrich, and Kristian Kersting
Computer, February 2011, pp. 86–88

A multitude of senses provide us with information about the here and now. What we see, hear, and feel in turn shape how we perceive our surroundings and understand the world. Our senses are extremely limited, however, and ever since humans began creating and using technology, they have tried to enhance their natural perception in various ways. (pdf)

Lab Meeting March 2nd, 2011 (Jeff): Observability-based Rules for Designing Consistent EKF SLAM Estimators

Title: Observability-based Rules for Designing Consistent EKF SLAM Estimators

Authors: Guoquan P. Huang, Anastasios Mourikis, and Stergios I. Roumeliotis

Abstract:

In this work, we study the inconsistency problem of extended Kalman filter (EKF)-based simultaneous localization and mapping (SLAM) from the perspective of observability. We analytically prove that when the Jacobians of the process and measurement models are evaluated at the latest state estimates during every time step, the linearized error-state system employed in the EKF has an observable subspace of dimension higher than that of the actual, non-linear, SLAM system. As a result, the covariance estimates of the EKF undergo reduction in
directions of the state space where no information is available, which is a primary cause of the inconsistency. Based on these theoretical results, we propose a general framework for improving the consistency of EKF-based SLAM. In this framework, the EKF linearization points are selected in a way that ensures that the resulting linearized system model has an observable subspace of appropriate dimension. We describe two algorithms that are instances of this paradigm. In the first, termed observability constrained (OC)-EKF, the linearization points are selected so as to minimize their expected errors (i.e. the difference between the linearization point and the true state) under the observability constraints. In the second, the filter Jacobians are calculated using the first-ever available estimates for all state variables. This latter approach is termed first-estimates Jacobian (FEJ)-EKF. The proposed algorithms have been tested both in simulation and experimentally, and are shown to significantly outperform the standard EKF both in terms of accuracy and consistency.

Link:
The International Journal of Robotics Research(IJRR), Vol.5 April 2010
http://ijr.sagepub.com/content/29/5/502.full.pdf+html

Meka's M-1 Mobile Manipulator

Meka M1 Mobile Manipulator vimeo from Meka Robotics on Vimeo.

Lab Meeting February 14, 2011 (fish60): Feature Construction for Inverse Reinforcement Learning

Title: Feature Construction for Inverse Reinforcement Learning
Sergey Levine, Zoran Popović, Vladlen Koltun
NIPS 2010

Abstract:
The goal of inverse reinforcement learning is to find a reward function for a
Markov decision process, given example traces from its optimal policy. Current
IRL techniques generally rely on user-supplied features that form a concise basis
for the reward. We present an algorithm that instead constructs reward features
from a large collection of component features, by building logical conjunctions of
those component features that are relevant to the example policy. Given example
traces, the algorithm returns a reward function as well as the constructed features.

Link

Lab Meeting February 14, 2011 (Alan): Multibody Structure-from-Motion in Practice (PAMI 2010)

Title: Multibody Structure-from-Motion in Practice (PAMI 2010)
Authors: Kemal Egemen Ozden, Konrad Schindler, and Luc Van Gool

Abstract—Multibody structure from motion (SfM) is the extension of classical SfM to dynamic scenes with multiple rigidly moving objects. Recent research has unveiled some of the mathematical foundations of the problem, but a practical algorithm which can handle realistic sequences is still missing. In this paper, we discuss the requirements for such an algorithm, highlight theoretical issues and practical problems, and describe how a static structure-from-motion framework needs to be extended to handle real dynamic scenes. Theoretical issues include different situations in which the number of independently moving scene objects changes: Moving objects can enter or leave the field of view, merge into the static background (e.g., when a car is parked), or split off from the background and start moving independently. Practical issues arise due to small freely moving foreground objects with few and short feature tracks. We argue that all of these difficulties need to be handled online as structure-from-motion estimation progresses, and present an exemplary solution using the framework of probabilistic model-scoring.

Link

Lab Meeting January 17( KuenHan ), Moving Object Detection by Multi-View Geometric Techniques from a Single Camera Mounted Robot (IROS 2009)

Title: Moving Object Detection by Multi-View Geometric Techniques from a Single Camera Mounted Robot ( IROS 2009)
Author: Abhijit Kundu, K Madhava Krishna and Jayanthi Sivaswamy

Abstract:
The ability to detect, and track multiple moving
objects like person and other robots, is an important prerequisite
for mobile robots working in dynamic indoor environments.
We approach this problem by detecting independently moving
objects in image sequence from a monocular camera mounted
on a robot. We use multi-view geometric constraints to classify
a pixel as moving or static. The first constraint, we use, is the
epipolar constraint which requires images of static points to
lie on the corresponding epipolar lines in subsequent images.
In the second constraint, we use the knowledge of the robot
motion to estimate a bound in the position of image pixel along
the epipolar line. This is capable of detecting moving objects
followed by a moving camera in the same direction, a so-called
degenerate configuration where the epipolar constraint fails.
To classify the moving pixels robustly, a Bayesian framework
is used to assign a probability that the pixel is stationary
or dynamic based on the above geometric properties and
the probabilities are updated when the pixels are tracked in
subsequent images. The same framework also accounts for the
error in estimation of camera motion. Successful and repeatable
detection and pursuit of people and other moving objects in
realtime with a monocular camera mounted on the Pioneer
3DX, in a cluttered environment confirms the efficacy of the
method.

Link

Lab Meeting January 10th, 2011(Jimmy) : Accurate Image Localization Based on Google Maps Street View (ECCV 2010)

Title: Accurate Image Localization Based on Google Maps Street View
Authors: Amir Roshan Zamir, Mubarak Shah
In ECCV 2010

Abstract
Finding an image's exact GPS location is a challenging computer vision problem that has many real-world applications. In this paper, we address the problem of fi nding the GPS location of images with an accuracy which is comparable to hand-held GPS devices. We leverage a structured data set of about 100,000 images build from Google Maps Street View as the reference images. We propose a localization method in which the SIFT descriptors of the detected SIFT interest points in the reference images are indexed using a tree. In order to localize a query image, the tree is queried using the detected SIFT descriptors in the query image. A novel GPS-tag-based pruning method removes the less reliable descriptors. Then, a smoothing step with an associated voting scheme is utilized; this allows each query descriptor to vote for the location its nearest neighbor belongs to, in order to accurately localize the query image. A parameter called Confidence of Localization which is based on the Kurtosis of the distribution of votes is de fined to determine how reliable the localization of a particular image is. In addition, we propose a novel approach to localize groups of images accurately in a hierarchical manner. First, each image is localized individually; then, the rest of the images in the group are matched against images in the neighboring area of the found first match. The fi nal location is determined based on the Confidence of Localization parameter. The proposed image group localization method can deal with very unclear queries which are not capable of being geolocated individually.

[pdf]

Lab Meeting January 3rd, 2011(Will) : Neural Prothesis & Realtime Bayes Tracking

Topic: Neural Prothesis & Realtime Bayes Tracking

Neural prothesis is a field that use brain to control motors to help disable people.
I'll report my survey on the neural prothesis decoding algorithm.

Po-Wei

Lab Meeting January 3rd, 2011(David) :Vision-Based Behavior Prediction in Urban Traffic Environments by Scene Categorization (BMVC 2010)

Title: Vision-Based Behavior Prediction in Urban Traffic Environments by Scene Categorization (BMVC 2010)

Authors: Martin Heracles, Fernando Martinelli and Jannik Fritsch

Abstract:
We propose a method for vision-based scene understanding in urban traffic environments that predicts the appropriate behavior of a human driver in a given visual scene. The method relies on a decomposition of the visual scene into its constituent objects by image segmentation and uses segmentation-based features that represent both their identity and spatial properties. We show how the behavior prediction can be naturally formulated as scene categorization problem and how ground truth behavior data for learning a classifier can be automatically generated from any monocular video sequence recorded from a moving vehicle, using structure from motion techniques. We evaluate our method both quantitatively and qualitatively on the recently proposed CamVid dataset, predicting the appropriate velocity and yaw rate of the car as well as their appropriate change for both day and dusk sequences. In particular, we investigate the impact of the underlying segmentation and the number of behavior classes on the quality of these predictions

link