Towards Better Navigation: optimizing mapping, localization and planning algorithms

Abstract:

When navigation algorithms realize their potential, autonomous driving will usher a new era of mobility, providing cheaper and safer mobility to the elderly, the disabled and the young. To realize this potential, navigation problem needs to be solved efficiently.

Navigation is often addressed in two parts: mapping and planning. We focus on grid based mapping algorithms that divide the space into grid cells. The state of the art (SOTA) grid based mapping algorithms use slow sampling based methods like Metropolis Hastings. We instead use modern inference methods like Belief Propagation and Dual Decomposition which not only converge up to two times faster but also lead to more accurate maps. We also improve mutual localization of robots so that they can divide and conquer the mapping task.

A special class of planning algorithms, called Goal-conditioned reinforcement learning (RL), is applied to cases when the goal location can change for every trial. The SOTA algorithms in Goal-conditioned RL use redundant ways to specify the goal which leads redundant computation. We extend Floyd-Warshall RL to deep neural networks which leads to removal of this redundant information and computation. Our algorithm requires only half the samples as the SOTA algorithms.