Autonomous Navigation in Unknown Environments using Sparse Kernel-based Occupancy Mapping

Thai Duong
Nikhil Das
Michael Yip
Nikolay Atanasov
Department of Electrical and Computer Engineering
University of California, San Diego
ICRA, 2020


This paper focuses on real-time occupancy mapping and collision checking onboard an autonomous robot navigating in an unknown environment. We propose a new map representation, in which occupied and free space are separated by the decision boundary of a kernel perceptron classifier. We develop an online training algorithm that maintains a very sparse set of support vectors to represent obstacle boundaries in configuration space. We also derive conditions that allow complete (without sampling) collision-checking for piecewise-linear and piecewise-polynomial robot trajectories. We demonstrate the effectiveness of our mapping and collision checking algorithms for autonomous navigation of an Ackermann-drive robot in unknown environments.


Thai Duong, Nikhil Das, Michael Yip, Nikolay Atanasov

Autonomous Navigation in Unknown Environments using Sparse Kernel-based Occupancy Mapping

Accepted to ICRA, 2020.




Map updates

Given a streaming local depth observation (e.g. lidar scan), we sample occupied and free points to generate a training dataset. The dataset is used to train a kernel perceptron model and the resulting support vectors are stored as a map. Upon receiving new observations, the map as a set of support vectors is updated.

Collision checking for linear and polynomial trajectories

Using the support vectors, we propose an "inflated boundary" of the obstacles. For line segments, the intersection with the inflated boundary can be computed efficiently regardless of the segment length. For polynomial curves, a safety ball can be calculated efficiently using the "inflated boundary" and collision checking is performed by iteratively placing safety balls along the curves.

Autonomous Navigation and Mapping

Autonomous mapping and navigation in an unknown simulated warehouse environment: Given the current kernel-based map, an A* planner is used with our collision-checking algorithms to generate a robot path. The robot follows the path for some time and updates the map estimate with new observations. Using the updated map, the robot re-plans the path and follows the new path instead. This process is repeated until the goal is reached




This webpage template was borrowed from