{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,18]],"date-time":"2026-04-18T16:32:36Z","timestamp":1776529956173,"version":"3.51.2"},"reference-count":45,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,2,6]],"date-time":"2021-02-06T00:00:00Z","timestamp":1612569600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>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\u2019s 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.<\/jats:p>","DOI":"10.3390\/s21041152","type":"journal-article","created":{"date-parts":[[2021,2,10]],"date-time":"2021-02-10T04:33:46Z","timestamp":1612931626000},"page":"1152","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":31,"title":["Online 3-Dimensional Path Planning with Kinematic Constraints in Unknown Environments Using Hybrid A* with Tree Pruning"],"prefix":"10.3390","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6549-7084","authenticated-orcid":false,"given":"Jonatan","family":"Scharff Willners","sequence":"first","affiliation":[{"name":"Institute of Sensors, Signals and Systems, Heriot-Watt University, Edinburgh EH14 4AS, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0478-4346","authenticated-orcid":false,"given":"Daniel","family":"Gonzalez-Adell","sequence":"additional","affiliation":[{"name":"Institute of Sensors, Signals and Systems, Heriot-Watt University, Edinburgh EH14 4AS, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9593-6789","authenticated-orcid":false,"given":"Juan David","family":"Hern\u00e1ndez","sequence":"additional","affiliation":[{"name":"Centre for Artificial Intelligence, Robotics and Human-Machine Systems (IROHMS), Cardiff University, Cardiff CF24 3AA, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3363-0426","authenticated-orcid":false,"given":"\u00c8ric","family":"Pairet","sequence":"additional","affiliation":[{"name":"Edinburgh Centre for Robotics, University of Edinburgh and Heriot-Watt University, Edinburgh EH14 4AS, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1596-289X","authenticated-orcid":false,"given":"Yvan","family":"Petillot","sequence":"additional","affiliation":[{"name":"Institute of Sensors, Signals and Systems, Heriot-Watt University, Edinburgh EH14 4AS, UK"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,6]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Robb, D., Lopes, J., Padilla, S., Laskov, A., Garcia, F.J.C., Liu, X., Willners, J.S., Valeyrie, N., Lohan, K., and Lane, D. (2019, January 23\u201328). Exploring Interaction with Remote Autonomous Systems using Conversational Agents. Proceedings of the DIS 2019\u20142019 ACM Designing Interactive Systems Conference, Diego, CA, USA.","DOI":"10.1145\/3322276.3322318"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Sato, Y., Maki, T., Masuda, K., Matsuda, T., and Sakamaki, T. (2017, January 21\u201324). Autonomous docking of hovering type AUV to seafloor charging station based on acoustic and visual sensing. Proceedings of the 2017 IEEE OES International Symposium on Underwater Technology (UT 2017), Busan, Korea.","DOI":"10.1109\/UT.2017.7890282"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"LaValle, S.M. (2006). Planning Algorithms, Cambridge University Press.","DOI":"10.1017\/CBO9780511546877"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1109\/TC.1983.1676196","article-title":"Spatial Planning: A Configuration Space Approach","volume":"C-32","year":"1983","journal-title":"IEEE Trans. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A Note on Two Problems in Connection with Graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_6","first-page":"100","article-title":"A Formal Basis for the Heuristic Determination of Minimum Cost Paths","volume":"4","author":"Hart","year":"1968","journal-title":"Syst. Sci. Cybern."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Tanakitkorn, K., Wilson, P.A., Turnock, S.R., and Phillips, A.B. (2014, January 6\u20139). Grid-based GA path planning with improved cost function for an over-actuated hover-capable AUV. Proceedings of the IEEE\/OES Autonomous Underwater Vehicles, Oxford, MS, USA.","DOI":"10.1109\/AUV.2014.7054426"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1109\/70.508439","article-title":"Probabilistic roadmaps for path planning in high-dimensional configuration spaces","volume":"12","author":"Kavraki","year":"1996","journal-title":"IEEE Trans. Robot. Autom."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1177\/02783640122067453","article-title":"Randomized kinodynamic planning","volume":"20","author":"LaValle","year":"2001","journal-title":"Int. J. Robot. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1177\/0278364911406761","article-title":"Sampling-based algorithms for optimal motion planning","volume":"30","author":"Karaman","year":"2011","journal-title":"Int. J. Robot. Res."},{"key":"ref_11","unstructured":"Yan, Z., Zhao, Y., Chen, T., and Deng, C. (2012, January 14\u201319). 3D path planning for AUV based on circle searching. Proceedings of the OCEANS 2012 MTS\/IEEE: Harnessing the Power of the Ocean, Hampton Roads, VA, USA."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Pivtoraiko, M., and Kelly, A. (2005, January 2\u20136). Generating near minimal spanning control sets for constrained motion planning in discrete state spaces. Proceedings of the 2005 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), Edmonton, AB, Canada.","DOI":"10.1109\/IROS.2005.1545046"},{"key":"ref_13","first-page":"18","article-title":"Practical search techniques in path planning for autonomous driving","volume":"1001","author":"Dolgov","year":"2008","journal-title":"Int. Symp. Comb. Search SoCS"},{"key":"ref_14","unstructured":"Hsu, D. (2000). Randomized Single-query Motion Planning in Expansive Spaces. [Ph.D. Thesis, Stanford University]."},{"key":"ref_15","unstructured":"Phillips, J.M., Bedrossian, N., and Kavraki, L.E. (May, January 26). Guided expansive spaces trees: A search strategy for motion- and cost-constrained state spaces. Proceedings of the IEEE International Conference on Robotics and Automation, New Orleans, LA, USA."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"497","DOI":"10.2307\/2372560","article-title":"On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents","volume":"79","author":"Dubins","year":"1957","journal-title":"Am. J. Math."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1002\/rob.21827","article-title":"Online motion planning for unexplored underwater environments using autonomous underwater vehicles","volume":"36","author":"Vidal","year":"2019","journal-title":"J. Field Robot."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Pairet, \u00c8., Hern\u00e1ndez, J.D., Lahijanian, M., and Carreras, M. (2018, January 1\u20135). Uncertainty-based Online Mapping and Motion Planning for Marine Robotics Guidance. Proceedings of the IEEE International Conference on Intelligent Robots and Systems, Madrid, Spain.","DOI":"10.1109\/IROS.2018.8593394"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Vidal, E., Moll, M., Palomeras, N., Hern\u00e1ndez, J.D., Carreras, M., and Kavraki, L.E. (2019, January 20\u201324). Online multilayered motion planning with dynamic constraints for autonomous underwater vehicles. Proceedings of the IEEE International Conference on Robotics and Automation, Montreal, QC, Canada.","DOI":"10.1109\/ICRA.2019.8794009"},{"key":"ref_20","unstructured":"Pairet, \u00c8., Hern\u00e1ndez, J.D., Petillot, Y., and Lahijanian, M. (2020). Online Mapping and Motion Planning under Uncertainty for Safe Navigation in Unknown Environments. arXiv."},{"key":"ref_21","unstructured":"Jian, X., Zou, T., Vardy, A., and Bose, N. (October, January 30). A hybrid path planning strategy of autonomous underwater vehicles. Proceedings of the IEEE\/OES Autonomous Underwater Vehicles Symposium, St. Johns, NL, Canada."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/978-3-540-48113-3_22","article-title":"Field D*: An interpolation-based path planner and replanner","volume":"28","author":"Ferguson","year":"2007","journal-title":"Springer Tracts Adv. Robot."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1109\/TRO.2004.838026","article-title":"Fast replanning for navigation in unknown terrain","volume":"21","author":"Koenig","year":"2005","journal-title":"IEEE Trans. Robot."},{"key":"ref_24","unstructured":"Likhachev, M., Ferguson, D., Gordon, G., Stentz, A., and Thrun, S. (2005, January 5\u201310). Anytime dynamic a*: An anytime, replanning algorithm. Proceedings of the 15th International Conference on Automated Planning and Scheduling, Monterey, CA, USA."},{"key":"ref_25","unstructured":"Petereit, J., Emter, T., Frey, C., Kopfstedt, T., and Beutel, A. (2012, January 21\u201322). Application of Hybrid A* to an Autonomous Mobile Robot for Path Planning in Unstructured Outdoor Environments. Proceedings of the ROBOTIK 2012\u20147th German Conference on Robotics, Munich, Germany."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1177\/0278364909359210","article-title":"Path planning for autonomous vehicles in unknown semi-structured environments","volume":"29","author":"Dolgov","year":"2010","journal-title":"Int. J. Robot. Res."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Heo, Y.J., and Chung, W.K. (November, January 30). RRT-based path planning with kinematic constraints of AUV in underwater structured environment. Proceedings of the 2013 10th International Conference on Ubiquitous Robots and Ambient Intelligence (URAI 2013), Jeju, Korea.","DOI":"10.1109\/URAI.2013.6677328"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Hernandez, J.D., Vidal, E., Vallicrosa, G., Galceran, E., and Carreras, M. (2015, January 26\u201330). Online path planning for autonomous underwater vehicles in unknown environments. Proceedings of the IEEE International Conference on Robotics and Automation, Seattle, WA, USA.","DOI":"10.1109\/ICRA.2015.7139336"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1109\/48.922790","article-title":"Underwater vehicle obstacle avoidance and path planning using a multi-beam forward looking sonar","volume":"26","author":"Petillot","year":"2001","journal-title":"IEEE J. Ocean. Eng."},{"key":"ref_30","first-page":"89","article-title":"Optimal and efficient path planning for unknown and dynamic environments","volume":"10","author":"Stentz","year":"1994","journal-title":"Int. J. Robot. Autom."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Bekris, K.E., and Kavraki, L.E. (2007, January 10\u201314). Greedy but safe replanning under kinodynamic constraints. Proceedings of the IEEE International Conference on Robotics and Automation, Roma, Italy.","DOI":"10.1109\/ROBOT.2007.363069"},{"key":"ref_32","unstructured":"Ferguson, D., Kalra, N., and Stentz, A. (2006, January 15\u201319). Replanning with RRTs. Proceedings of the IEEE International Conference on Robotics and Automation, Orlando, FL, USA."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Hern\u00e1ndez, J.D., Moll, M., Vidal, E., Carreras, M., and Kavraki, L.E. (2016, January 9\u201314). Planning feasible and safe paths online for autonomous underwater vehicles in unknown environments. Proceedings of the IEEE International Conference on Intelligent Robots and Systems, Daejeon, Korea.","DOI":"10.1109\/IROS.2016.7759217"},{"key":"ref_34","unstructured":"Carreras, M., Candela, C., Ribas, D., Palomeras, N., Magi\u00ed, L., Mallios, A., Vidal, E., Pairet, \u00c8., and Ridao, P. (2015). Testing SPARUS II AUV, an Open Platform for Industrial, Scientific and Academic Applications, Instrumentation Viewpoint."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1109\/JOE.2018.2792278","article-title":"Sparus II AUV\u2014A Hovering Vehicle for Seabed Inspection","volume":"43","author":"Carreras","year":"2018","journal-title":"IEEE J. Ocean. Eng."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1109\/TMECH.2011.2174065","article-title":"Girona 500 AUV: From survey to intervention","volume":"17","author":"Ribas","year":"2011","journal-title":"IEEE\/ASME Trans. Mechatron."},{"key":"ref_37","unstructured":"Russell, S., and Norvig, P. (2009). Artificial Intelligence: A Modern Approach, Prentice Hall Press. [3rd ed.]."},{"key":"ref_38","unstructured":"Pearl, J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley Longman Publishing Co. Inc."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1109\/MRA.2012.2205651","article-title":"The Open Motion Planning Library","volume":"19","author":"Sucan","year":"2012","journal-title":"IEEE Robot. Autom. Mag."},{"key":"ref_40","first-page":"99","article-title":"Simultaneous localization and mapping (SLAM): Part I The Essential Algorithms","volume":"2","author":"Bailey","year":"2006","journal-title":"Robot. Autom. Mag."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/s10514-012-9321-0","article-title":"OctoMap: An efficient probabilistic 3D mapping framework based on octrees","volume":"34","author":"Hornung","year":"2013","journal-title":"Auton. Robot."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Pan, J., Chitta, S., and Manocha, D. (2012, January 14\u201318). FCL: A general purpose library for collision and proximity queries. Proceedings of the IEEE International Conference on Robotics and Automation, Saint Paul, MN, USA.","DOI":"10.1109\/ICRA.2012.6225337"},{"key":"ref_43","first-page":"19","article-title":"ROS : An open-source Robot Operating System","volume":"15","author":"Quigley","year":"2009","journal-title":"IEEE Robot. Autom."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Manh\u00e3es, M.M.M., Scherer, S.A., Voss, M., Douat, L.R., and Rauschenbach, T. (2016, January 19\u201323). UUV Simulator: A Gazebo-based package for underwater intervention and multi-robot simulation. Proceedings of the OCEANS 2016 MTS\/IEEE Monterey, Monterey, CA, USA.","DOI":"10.1109\/OCEANS.2016.7761080"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/j.cag.2017.08.008","article-title":"A novel GPU-based sonar simulator for real-time applications","volume":"68","author":"Cerqueira","year":"2017","journal-title":"Comput. Graph."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/4\/1152\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:20:42Z","timestamp":1760160042000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/4\/1152"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,6]]},"references-count":45,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,2]]}},"alternative-id":["s21041152"],"URL":"https:\/\/doi.org\/10.3390\/s21041152","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,6]]}}}