Dynamic Multi-Goal Motion Planning with Range Constraints for Autonomous Underwater Vehicles Following Surface Vehicles
James McMahon, Erion Plaku · 2021
Autonomous underwater vehicles (AUVs) are often required to reach multiple goal locations while staying within the communication range of a surface vehicle. The goals, which could be dispersed throughout the environment, are dynamically discovered by the surface vehicle as it moves along a predefined trajectory. As the goals are discovered, they are communicated to the AUV. This paper develops an efficient multi-layered planner that generates collision-free and dynamically-feasible trajectories that enable the AUV to reach as many goals as possible while always staying within the communication range of the surface vehicle. The planner relies on a roadmap to capture the connectivity of the environment in order to facilitate navigation. The high-level layer is based on discrete search to find paths over the roadmap that increase the sum of the rewards to the known goals while maintaining the range constraints. The low-level layer relies on sampling-based motion planning to expand a tree of feasible motions along paths computed by the discrete layer. These layers interact with each other to update the planned motions as new goals are dynamically discovered. Experiments using 3D environments, second-order AUV models, and an increasing number of goals, demonstrate the efficiency of the planner to solve dynamic multi-goal motion-planning problems with range constraints.