Paper Info
Title
Online 3-Dimensional Path Planning With Kinematic Constraints In Unknown Environments Using Hybrid A* With Tree Pruning
Abstract
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.
Year
DOI
Venue
2021
10.3390/s21041152
SENSORS
Keywords
DocType
Volume
hybrid A*, autonomous underwater vehicle, path planning, unknown environments, graph-search, online replanning, tree pruning
Journal
21
Issue
ISSN
Citations 
4
1424-8220
1
PageRank 
References 
Authors
0.34
0
5
Name
Order
Citations
PageRank
Jonatan Scharff Willners131.71
Daniel Gonzalez-Adell210.34
Juan David Hernández310.34
Èric Pairet411.70
Yvan Petillot514219.16