Online 3-dimensional path planning with kinematic constraints in unknown environments using hybrid A* with tree pruning

Scharff Willners, Jonatan, Gonzalez-Adell, Daniel, Hernández, Juan David ORCID: https://orcid.org/0000-0002-9593-6789, Pairet, Eric and Petillot, Yvan 2021. Online 3-dimensional path planning with kinematic constraints in unknown environments using hybrid A* with tree pruning. Sensors 21 (4) , 1152. 10.3390/s21041152

Preview

PDF - Published Version Available under License Creative Commons Attribution. Download (4MB) | Preview

Abstract

In this paper we present an extension to the hybrid A* (HA*) path planner. This extension allows autonomous underwater vehicles (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.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
Publisher:	MDPI
ISSN:	1424-8220
Date of First Compliant Deposit:	8 February 2021
Date of Acceptance:	4 February 2021
Last Modified:	05 May 2023 16:38
URI:	https://orca.cardiff.ac.uk/id/eprint/138312

Citation Data

Cited 9 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item