Shortest Dubins path for forward moving robots

• Main Author: Chan, Chor Cheng
• Other Authors: Huang Shell Ying
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2023
• Subjects: Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
• Online Access: https://hdl.handle.net/10356/172007
• Institution: Nanyang Technological University

Given the increasing emphasis on developing autonomous vehicles, it is of value to continuously improve the path planning aspect which is considered a key of the autonomy of autonomous vehicles. Considering the path planning problem of determining the shortest path a forward-moving vehicle can take between 2 points with initial and terminal directions in a 2-dimensional plane, the classical solution of Dubins paths where the paths can be classified into 6 different path types was developed. Widespread applications of utilising the shortest Dubins paths has sparked the need for an algorithm that is faster than exhaustively determining the shortest Dubins path and that can be generalised for any points and directions in the 2-dimensional plane. Hence, this paper seeks to implement a hybrid algorithm that combines a classification method and the exhaustive method, alongside studying the computational cost of normalisation for generalisation before using the hybrid algorithm. The accuracy of the hybrid algorithm in determining the shortest Dubins path was verified with test cases developed to achieve optimal decision coverage. The performance of the hybrid algorithm was measured and pitted against the exhaustive method, where the hybrid algorithm performed better overall. The computational cost of normalisation was relatively larger when paired with the hybrid algorithm than that of the exhaustive method.