Hybrid A* based Path Planner for Obstacle Avoidance

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.
Hybrid_A_star
Hybrid A* planner(left) compared to conventional A* and D* [7]

Implementation

HybridA_vehicle
Vehicle: Unmanned Solution UMS ERP42 V3.0
LiDAR: LMS151
Camera: Logitech C920 Webcam * 4
PC: Asus FX502V (Intel i7 6700HQ / Nvidia GTX1050Ti)
  • 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.

6 Comments

  1. how choose a target point ?I can not understand.

    Like

    1. Target point is always set to be center of the lane (excluding obstacles) of the furthest boundary of Roi.

      Like

  2. Do you use CG to smooth path about curvature term?

    Like

    1. Sorry for the late reply. For the details of the smoothing algorithm, please refer to Reference [7] or [9].

      Like

  3. Rushikesh Rajendra Kharade

    how did you generate child nodes for a state?

    Like

    1. The child nodes are sampled from the kinematically feasible future states. Sorry for the late reply.

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s