Navigation, Localization, and Mapping

    Navigation is one of the most critical functionalities for robots. Robots typically rely on a given map to determine their location and plan a path to their target. However, this reliance assumes the map is accurate, which is often not the case. In many situations, maps are either unavailable or imprecise, making the task of building a map of the environment—whether known or unknown—an indispensable challenge in robotics.

    Simultaneously addressing localization and mapping presents a classic chicken-and-egg problem: accurate localization requires a reliable map, while building an accurate map depends on precise localization. To tackle this, several well-known approximation algorithms, such as particle filters and extended Kalman filters, have been developed. In my work, I explored the use of particle filters to implement Simultaneous Localization and Mapping (SLAM).

Mobile Robot Navigation System

    Course: Robotics, Department of Computer Science, National Taiwan University
    Date: Oct. 2012 - Jan. 2013

This was my first robotics project, where I collaborated with a classmate to control a pioneer-like mobile robot equipped with a Kinect sensor. The goal was to enable the robot to autonomously locate and approach a ball in dynamic environments. I developed the system to integrate mobility with perception-based estimations. Additionally, I designed a simple obstacle avoidance algorithm and implemented grid-based path planning to ensure efficient and safe navigation.

Localization and SLAM Competition

    Course: Robot Perception and Learning, Department of Computer Science, National Taiwan University
    Date: Oct. 2013 - Jan. 2014

In both competitions, we used an Xtion sensor and a manually controlled mobile robot to collect RGB, depth, and odometry data. My primary approach to solving the tasks was based on the Monte Carlo method (particle filter). As demonstrated in the video, red dots represent randomly generated particles, initialized using the given mean and standard deviation (sigma).

The localization task presented challenges, such as navigating through dark areas where RGB data became unreliable, and dealing with moving pedestrians, which often disrupted depth alignment. For the SLAM task, additional complexities included performing loop detection and addressing the loop closure problem to ensure accurate mapping.

The localization competition was conducted as an online demonstration, with the video showcasing results based on recorded images and odometry measurements. The localization process consists of four main steps:
  1. Prediction: Estimate the possible position distribution using odometry readings.
  2. Weighting and Correction: Assign weights to particles based on their distribution and refine some particles using depth information. (For real-time performance optimization, I used only a single row of the depth image, treating it as a simplified 2D scan.)
  3. Position Estimation: Calculate the most likely position by analyzing the correlation of the current RGB image with previous weighting results. To determine image correlation, I employed the SIFT feature detector to match keypoints and computed the weighting as the ratio of matched keypoints to all detected keypoints.
  4. Resampling: Resample particles to maintain an accurate distribution.


The SLAM videos were recorded on our RoboCup field, where measurements were captured to construct the map. To build the map, I utilized 2D scans and applied the Iterative Closest Point (ICP) algorithm for alignment. The localization process was then performed, and the estimated positions were used to further refine the robot's self-localization.

The difference between the two videos lies in the map refinement process: the right video includes a refinement step following loop detection, while the left video does not. One noticeable improvement in the right video is the alignment accuracy of the goal and goal zone. For example, the goal’s yellow pillar and the goal zone lines exhibit significantly fewer misaligned duplicates in the right video, indicating a more accurate map reconstruction based on the estimated positions.

WiFi-SLAM

    Course: Networks and Mobile Systems, Computer Science Department, New York University
    Date: Mar. 2017 - May 2017

The widespread deployment of wireless networks in indoor environments offers opportunities not only for localization but also for constructing wireless maps. When the locations of wireless landmarks are unknown, SLAM provides an effective solution to simultaneously build the map and perform localization. Based on the paper Efficient Probabilistic Range-Only SLAM and the tool Mobile Robot Programming Tool (MRPT), I developed a WiFi-SLAM system using a Raspberry Pi and an iRobot vacuum cleaner, which I tested in an office environment.

Since WiFi signals tend to be noisy and unstable when the robot is in motion, I implemented a bucket filter to stabilize signal strength. For the experiments, I deployed multiple Raspberry Pi devices, which were configured to both receive WiFi signals and act as hotspots.

Compared to the original odometer readings, the system demonstrated excellent practical performance in certain cases. However, I encountered challenges with the symmetry problem when the robot changed orientation. To address this intrinsic issue, I presented an unsuccessful result, highlighting the difficulty in accurately estimating orientation under these conditions.

    One should clearly distinguish between two aspects of the estimation problem:
  1. The theoretical aspect. Here interest centers on:
    (i) The general form of the solution.
    (ii) Conditions which guarantee a priori the existence, physical realizability, and stability of the optimal filter.
    (iii) Characterization of the general results in terms of some simple quantities, such as signal-to-noise ratio, information rate, bandwidth, etc...
  2. The computational aspect. The classical (more accurately, old-fashioned) view is that a mathematical problem is solved if the solution is expressed by a formula. It is not a trivial matter, however, to substitute numbers in a formula. The current literature on the Wiener problem is full of semi-rigorously derived formulas which turn out to be unusable for practical computation when the order of the system becomes even moderately large...

- Rudolf E. Kalman