February – May 2018

Undergraduate Research Project, Seoul National University

Main Advisor: Professor Sung-hoon Ahn

* Implemented system deployed for KASA Undergraduate Self-driving Contest, 2018

Motivation

Autonomous Vehicles frequently face unstructured and unpredictable environments. The objective of this project was to develop a one-shot local path planner for an autonomous vehicle capable of avoiding obstacles in a diverse distribution.

Method

Binary Occupancy Grid Map + Hybrid A Star Planner

1. Binary occupancy grid map was used for the local path planning, with lozenged padding applied to the obstacle points for safe collision avoidance.
2. Hybrid A* planner – which does A* search on continuous vehicle state candidates with subsequent path smoothing – has been applied for the local path planner.

Implementation

• Hybrid A Star automatically searches for a target point from the farthest free region.
• It takes 100~400ms(Nominal:200ms) for a single planning.
• The implementation is based on the supplementary source code from Karl Kurzer’s thesis work[9].
• The vehicle follows the path based on pure pursuit[10] algorithm.

Results

The acquired paths:

• made vehicle clear all obstacle-based missions in 2018 KASA International Student Car Competition.
• tend to attach to obstacle boundaries.
• are clearly not optimal.
• depend highly on the shape of obstacle paddings.

Conclusion

Hybrid A Star planner works reasonably well for unstructured environments. However, it may not be the most suitable planner for local path planning. Some clear defects are:

• obtained paths are not guaranteed to be collision-free.
• not optimal.
• long computational time (>100ms for 6m*6m space search).

References

[1] Bojarski, Mariusz, et al. “End to end learning for self-driving cars.” arXiv preprint arXiv:1604.07316 (2016).
[2] Levinson, Jesse, et al. “Towards fully autonomous driving: Systems and algorithms.” Intelligent Vehicles Symposium (IV), 2011 IEEE. IEEE, 2011.
[3] Thrun, Sebastian, Wolfram Burgard, and Dieter Fox. Probabilistic robotics. MIT Press, 2005.
[4] Ryou, Gilhyun, et al. “Applying Asynchronous Deep Classification Network and Gaming Reinforcement Learning-Based Motion Planner to a Mobile Robot.“
[5] González, David, et al. “A review of motion planning techniques for automated vehicles.” IEEE Transactions on Intelligent Transportation Systems 17.4 (2016): 1135-1145.
[6] Hart, Peter E., Nils J. Nilsson, and Bertram Raphael. “A formal basis for the heuristic determination of minimum cost paths.” IEEE Transactions on Systems Science and Cybernetics 4.2 (1968): 100-107.
[7] Dolgov, Dmitri, et al. “Practical search techniques in path planning for autonomous driving.” Ann Arbor 1001.48105 (2008): 18-80.
[8] Montemerlo, Michael, et al. “Junior: The Stanford entry in the urban challenge.” Journal of Field Robotics 25.9 (2008): 569-597.
[9] Kurzer, Karl. “Path Planning in Unstructured Environments: A Real-time Hybrid A* Implementation for Fast and Deterministic Path Generation for the KTH Research Concept Vehicle.” (2016).
[10] Coulter, R. Craig. Implementation of the pure pursuit path tracking algorithm. No. CMU-RI-TR-92-01. Carnegie-Mellon UNIV Pittsburgh PA Robotics INST, 1992.

Acknowledgements

This research was funded and supported by the Department of Mechanical Engineering(Seoul National University), Korea Automobile Testing & Research Institute, and Korea Auto-Vehicle Safety Association. The author would like to thank Dongwan Kim, Yoonkyung Cho and other members of SNU ZERO for sharing efforts to establish the autonomous drive system together. The author would also like to show gratitude to Xinlin Wang, Jongsik Moon, Gilhyun Ryou, Ilsu Park, Cong Jie CJ, and Gyuri Im for their valuable advice.