Autonomous Navigation in Unknown Environments with Sparse Bayesian Kernel-based Occupancy Mapping
Department of Electrical and Computer Engineering
University of California, San Diego
In Submission, 2020
|
This paper focuses on online occupancy mapping and real-time collision checking onboard an autonomous robot navigating in a large unknown environment. Commonly used voxel and octree map representations can be easily maintained in small environments but they have increasing memory requirements in large environments. We propose a fundamentally different approach for occupancy mapping, in which the boundary between occupied and free space is viewed as the decision boundary of a machine learning classifier. Our preliminary work developed a kernel perceptron model, which maintains a very sparse set of support vectors to represent the environment boundaries efficiently, and derived efficient collision checking algorithms. This work develops a probabilistic model, allowing robustness to measurement noise and localization errors as well as probabilistic occupancy classification, supporting autonomous navigation. The resulting sparse Bayesian map is updated via incremental Relevance Vector Machine training and supports efficient collision-checking of points and curves. The effectiveness of our mapping and collision checking algorithms is evaluated in tasks requiring autonomous robot navigation in unknown environments.
Paper
 |
Thai Duong, Michael Yip, Nikolay Atanasov
Autonomous Navigation in Unknown Environments using Sparse Bayesian Kernel-based Occupancy Mapping
In Submission, 2020.
[pdf]
|
Overview and Results
Additional Details
Settings
|
|
A ground robot equipped with a lidar is placed in an unknown environment. Its tasks are to build a probabilistic occupancy map of the environment and plan a trajectory from the current position to a goal region in the free space. The map should be built online along the way and the trajectory is re-planned accordingly.
|
|
Our map as sparse set of occupied and free relevance vectors (green and red dots, respectively) built from the laser scan above using our incremental Relevance Vector machine algorithm.
|
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 incrementally train a Relevance Vector Machine model and the resulting relevance vectors are stored as a map. Upon receiving new observations, the map as a sparse set of relevance vectors is updated.
|
Collision checking for linear and polynomial trajectories
|
|
Using the relevance vectors, we propose an "inflated boundary" of the obstacles. For line segments, the intersection with the inflated boundary can be computed efficiently in closed form regardless of the segment length. For polynomial curves, a safety ellipsoid is computed efficiently in closed form using the "inflated boundary". Collision checking is then performed by iteratively placing safety balls along the curves.
|
Code
Citation
If you find our papers/code useful for your research, please cite our work as follows.
1. T. Duong, M. Yip, N. Atanasov. Autonomous Navigation in Unknown Environments with Sparse Bayesian Kernel-based Occupancy Mapping. In Submission. 2020
@misc{duong2020autonomousbayesian,
title={Autonomous Navigation in Unknown Environments with Sparse Bayesian Kernel-based Occupancy Mapping},
author={Duong, Thai and Yip, Michael and Atanasov, Nikolay},
url = {https://thaipduong.github.io/sbkm},
pdf = {https://arxiv.org/pdf/2009.07207.pdf}
eprint={2009.07207},
archivePrefix={arXiv},
primaryClass={cs.RO}
year={2020}
}
2. T. Duong, N. Das, M. Yip, N. Atanasov. Autonomous Navigation in Unknown Environments using Sparse Kernel-based Occupancy Mapping. IEEE International Conference on Robotics and Automation (ICRA), 2020.
@inproceedings{duong2020autonomous,
title={Autonomous Navigation in Unknown Environments using Sparse Kernel-based Occupancy Mapping},
author={Duong, Thai and Das, Nikhil and Yip, Michael and Atanasov, Nikolay},
booktitle={IEEE International Conference on Robotics and Automation (ICRA)},
year={2020},
url = {https://thaipduong.github.io/kernelbasedmap},
pdf = {https://arxiv.org/pdf/2002.01921.pdf}
}
Acknowledgements
We gratefully acknowledge support from ARL DCIST CRA W911NF-17-2-0181 and ONR SAI N00014-18-1-2828.
This webpage template was borrowed from https://akanazawa.github.io/cmr/.
|