Seminar: AUV Path Planning in Linear Time and Faster Single-Source Multiple-Goal Path Planning

Adam Murphy
Honours Presentation
Supervisor: Dr. Antonina Kolokolova

AUV Path Planning in Linear Time and Faster Single-Source Multiple-Goal Path Planning

Department of Computer Science
Tuesday, August 6, 1:00 p.m., Room EN-2022


A special challenge of the path planning problem for Autonomous Underwater Vehicles (AUVs) lies in the fact that there is no communication with the vehicle except for a few short windows of time. Due to the uncertainty associated with the movement of the AUVs, a glider can surface in a location different from the projected one, and its route may need to be recomputed within the few minutes it is on the surface waiting for a command. Thus, it is essential to have efficient algorithms for AUV path planning. Some of the standard algorithms for path planning include the classic Dijkstra's algorithm, Fast Marching algorithm, and their heuristic variants A* and FM*. However, as given the running time of those algorithms is O(n log(n)). In this work we augment existing algorithms, specifically FM*, with a Calendar Queue data structure, which has constant time add and remove operations under certain restrictions which are indeed met in the case of AUV path planning. The swapping of traditional priority queues in favor of calendar queues reduces the running time of path planning algorithms from O(n log(n)) to O(n). Additionally, when using heuristic algorithms, we make use of memoization to account for multiple goal exploration, which avoids unnecessarily exploration of entire maps when the number of destinations is significantly smaller than the number of tiles on the grid to which a path planning algorithm is being applied. This improved version of FM* has been implemented and will be used as a part of an AUV mission planning package.



Department of Computer Science

230 Elizabeth Ave, St. John's, NL, CANADA, A1B 3X9

Postal Address: P.O. Box 4200, St. John's, NL, CANADA, A1C 5S7

Tel: (709) 864-8000