In this paper we present an extension to the hybrid A* (HA*) path planner. This extension allows autonomous underwater vehicle (AUVs) to plan paths in 3-dimensional (3D) environments. The proposed approach enables the robot to operate in a safe manner by accounting for the vehicle’s motion constraints, thus avoiding collisions and ensuring that the calculated paths are feasible. Secondly, we propose an improvement for operations in unexplored or partially known environments by endowing the planner with a tree pruning procedure, which maintains a valid and feasible search-tree during operation. When the robot senses new obstacles in the environment that invalidate its current path, the planner prunes the tree of branches which collides with the environment. The path planning algorithm is then initialised with the pruned tree, enabling it to find a solution in a lower time than replanning from scratch. We present results obtained through simulation which show that HA* performs better in known underwater environments than compared algorithms in regards to planning time, path length and success rate. For unknown environments, we show that the tree pruning procedure reduces the total planning time needed in a variety of environments compared to running the full planning algorithm during replanning.

This paper presents a novel approach to planning vehicle paths under kinodynamic constraints in a leader follower scenario where the follower vehicle has to track and follow the leader. This problem is important in the maritime domain where Autonomous Underwater Vehicles (AUVs) can greatly benefit from an Autonomous Surface Vehicle (ASV) acting as a Communication Relay (CR) and/or a Navigational Aid (NA), typically using acoustic communication. The proposed approach is an extension of Hybrid-A*(HA*), a hybrid version of A* which enables the derivation of paths that are obstacle free and feasible by the vehicle. The proposed algorithm finds a solution, if it exists, for scenarios where the leader and the follower operate under the same kinematic constraints as well as when they differ. Various simulations using multiple configurations and scenarios are presented to validate the approach. Whilst the work presented here has a focus on the maritime environment, the algorithm is applicable to other domains.