AUV path planning: an A* approach to path planning with consideration of variable vehicle speeds and multiple, overlapping, time-dependent exclusion zones

Abstract

The authors describe an implementation of a path planner suitable for an autonomous underwater vehicle (AUV). The path planning unit is capable of maintaining a quadtree database of depth information, obstacles, and exclusion zones: verifying a previously planned path; generating a new path between successive goal points; and generating a path to the nearest point of a safe region. If a path does not exist within the given constraints, the path planner returns a reason for the failure. The path planner attempts to find a 3D corridor that does not intersect any nonentry zones. An A* algorithm is used to generate path corridors along great circle routes. The path planner's real-time performance in open, constricted, and real-world situations is discussed. Additional factors affecting performance such as the number of different vehicle speeds, the quadtree resolution, and the number of nonentry zones blocking the goal are considered.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>