Towards Better Navigation: Optimizing Algorithms for Mapping, Localization and Planning

Abstract

Navigation is the problem of going from one place to another. It is an important problem in the areas of autonomous driving, mobile robotics and robotic manipulation. When navigation algorithms realize their potential, autonomous driving will lead to a new era of mobility, enabling greater independence for the disabled and greater convenience for all. It will reduce car ownership, increase fuel efficiency and reduce traffic jams.

The navigation problem needs to be solved efficiently. It is well understood that slow reaction time in driving can be fatal. For self-driving cars to be safe, the navigation algorithms have to be optimized without compromising accuracy. In this thesis, we focus on optimizing algorithms in the navigation domain.

Navigation is often addressed in three parts: mapping, localization and planning. Mapping is the problem of building a representation (a map) of the environment from noisy observations. Mapping is the slowest step in the navigation pipeline because the set of possible maps grows exponentially with the size of the map. This makes optimizing mapping crucial for optimizing navigation. We focus on grid based mapping algorithms that divide the space into grid cells. The state of the art (SOTA) grid based mapping algorithms have either of two limitations. They either make a limiting assumption of each grid-cell being independent of its neighboring cells or they use slow sampling based methods like Gibbs sampling and Metropolis Hastings. Although the sampling based methods are guaranteed to converge, they are slow in practice because they do not fully utilize the relationships among random variables. We avoid the independent cell assumption and use modern inference methods like Belief Propagation and Dual Decomposition, instead of sampling based methods. These modern methods not only converge up to two times faster but also lead to more accurate maps.

Localization, another part of navigation, is the problem of finding the robot's position with respect to the environment or the map. It is usually carried out under two restrictive assumptions: (1) there is only one robot in the environment (2) the map (or its estimate) is known. We relax the former assumption by recognizing the fact that robots can cooperatively map the environment faster. We propose a polynomial root-finding based mutual localization algorithm that uses observations from two robots. Our algorithm depends upon only a few fiducial markers instead of external landmarks, used by methods like Bundler, which makes it faster.

The final step of navigation, called planning, is the problem of taking actions based on the map, the robot's position and desired destination. Reinforcement learning (RL) is a popular algorithm for planning, when the effect of actions on the environment are not easily modeled. A special class of RL algorithms, called Goal-conditioned RL, is applied to cases when the goal location can change for every trial. The SOTA algorithms in Goal-conditioned RL specify the goal location in multiple, redundant ways. Due to this redundant information, algorithms like Hindsight Experience Replay re-samples rewards which makes them slow. We propose a deep extension to Floyd-Warshall Reinforcement Learning which removes of this redundant information thus avoiding rewards re-sampling. The resultant algorithm requires only half the reward samples as required by the baselines.