An Analysis of Path Planning Algorithms Focusing on A* and D*

Date of Award

2019

Degree Name

M.S. in Electrical Engineering

Department

Department of Electrical and Computer Engineering

Advisor/Chair

Advisor: Eric Balster

Abstract

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.

Keywords

Electrical Engineering, Engineering, path planning, search algorithms

Rights Statement

Copyright © 2019, author

Link to Full Text

Share

COinS