The PRM-A* Path Planning Algorithm For UUVs: An Application To Navy Mission Planning

This paper presents a novel path planning algorithm for unmanned underwater vehicles (UUVs) that arises by combining two well-known algorithms in such a way as to exploit their respective advantages while mitigating their deficiencies. The two algorithms are A-star (A*) and Probabilistic Road Map (PRM). The operational environment is given as a portion of open sea interspersed with various obstacles. The free space is the portion not occupied by obstacles. A* employs heuristic search to explore the free space for a path from the start to the goal. This algorithm always returns the shortest (optimal cost) path. A drawback is that the path sometimes runs dangerously close to an obstacle. In addition, the computed path can have sharp turns that are difficult for the UUV to negotiate. PRM starts with a random sampling of the points in the free space. Once some predetermined number of such points are chosen, each point is paired with some of it's free space neighbors, and these pairs are recorded in what is called a road map. Then Dijkstra's algorithm is applied to the road map using nearest neighbor information to find a path from the start node to the goal. This has the advantage that the resulting path is smooth (no sharp turns) and stays safely away from the obstacles. It has the drawback that the path is not optimal; it can be much longer than necessary. The idea presented in this paper is to first run both A* and PRM on the given operational environment. Then take the region bounded by these two lines as a new (smaller) operational environment, and rerun PRM. This produces a new path that more closely approximates the A* path while at the same time is smooth and, with proper monitoring, is assured to keep a safe distance from the obstacles. This procedure can be repeated as many times as desired, each time producing a better approximation of the optimal A* path. While the focus here has been on UUVs, the same approach can be applied for unmanned surface vehicles (USVs),