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

[Paper]

[Video]

[Code]

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.

Please check out our Bayesian version of this mapping method here: https://thaipduong.github.io/sbkm/

Paper

Thai Duong, Nikhil Das, Michael Yip, Nikolay Atanasov

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

Accepted to ICRA, 2020.

[pdf]

OVERVIEW AND RESULTS

ADDITIONAL DETAILS

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

Code

[github]

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/.