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
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.
Binary Occupancy Grid Map + Hybrid A Star Planner
- Binary occupancy grid map was used for the local path planning, with lozenged padding applied to the obstacle points for safe collision avoidance.
- Hybrid A* planner – which does A* search on continuous vehicle state candidates with subsequent path smoothing – has been applied for the local path planner.
- 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.
- The vehicle follows the path based on pure pursuit algorithm.
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.
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).
 Bojarski, Mariusz, et al. “End to end learning for self-driving cars.” arXiv preprint arXiv:1604.07316 (2016).
 Levinson, Jesse, et al. “Towards fully autonomous driving: Systems and algorithms.” Intelligent Vehicles Symposium (IV), 2011 IEEE. IEEE, 2011.
 Thrun, Sebastian, Wolfram Burgard, and Dieter Fox. Probabilistic robotics. MIT Press, 2005.
 Ryou, Gilhyun, et al. “Applying Asynchronous Deep Classification Network and Gaming Reinforcement Learning-Based Motion Planner to a Mobile Robot.“
 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.
 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.
 Dolgov, Dmitri, et al. “Practical search techniques in path planning for autonomous driving.” Ann Arbor 1001.48105 (2008): 18-80.
 Montemerlo, Michael, et al. “Junior: The Stanford entry in the urban challenge.” Journal of Field Robotics 25.9 (2008): 569-597.
 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).
 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.
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.
how choose a target point ？I can not understand.
Target point is always set to be center of the lane (excluding obstacles) of the furthest boundary of Roi.
Do you use CG to smooth path about curvature term?
Sorry for the late reply. For the details of the smoothing algorithm, please refer to Reference  or .
how did you generate child nodes for a state?
The child nodes are sampled from the kinematically feasible future states. Sorry for the late reply.
Have you published any paper regarding to this work?
This was my undergrad thesis, however, the paper is in Korean and is not public. The code for the project is developed based on the open source in the following link: https://github.com/karlkurzer/path_planner
Great Jobs! Would you share the paper or github repository? I wanna take a look the detailed elements
Hi, thank you for your interest in my work. Unfortunately, this was my undergrad project and the code quality was really poor so we did not publish the code. However, we implemented our work based upon the open source from Karl Kurzer: https://github.com/karlkurzer/path_planner
Hope this is useful for your reference.