An Analysis of Path Planning Algorithms Focusing on A* and D*
Date of Award
M.S. in Electrical Engineering
Department of Electrical and Computer Engineering
Advisor: Eric Balster
Unmanned aerial vehicles (UAVs) have many uses arranging from domestic use to military surveillance. Path planning algorithms are one of the many tools available to control UAVs to help make flights more autonomic and decrease pilot involvement. A* and D* are two different algorithms used to solve a wide range of problems from traffic patterns to circuit board layouts. Both algorithms have advantages and disadvantages. This thesis presents a new test environment for path planning algorithms in matrix laboratory (MATLAB) to compare algorithm complexity and path lengths. By comparing algorithm complexity and path lengths, the advantages and disadvantages are explored between the two algorithms.The results in this thesis demonstrates that A* is a good solution for simple problem while D* is a more robust algorithm but has complex computation. The next step is combining the best traits of both A* and D* into a hybrid algorithm. The hybrid algorithm results are on par with A* and D* algorithms leading to the algorithms do not have to compromise on speed to get accurate results.
Electrical Engineering, Engineering, path planning, search algorithms
Copyright 2019, author
Reeves, Megan Clancy, "An Analysis of Path Planning Algorithms Focusing on A* and D*" (2019). Graduate Theses and Dissertations. 6681.