{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:54:24Z","timestamp":1760151264088,"version":"build-2065373602"},"reference-count":41,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2022,2,25]],"date-time":"2022-02-25T00:00:00Z","timestamp":1645747200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-17-CE19-0005"],"award-info":[{"award-number":["ANR-17-CE19-0005"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We propose a novel algorithm to determine the Euclidean shortest path (ESP) from a given point (source) to another point (destination) inside a tubular space. The method is based on the observation data of a virtual particle (VP) assumed to move along this path. In the first step, the geometric properties of the shortest path inside the considered space are presented and proven. Utilizing these properties, the desired ESP can be segmented into three partitions depending on the visibility of the VP. Our algorithm will check which partition the VP belongs to and calculate the correct direction of its movement, and thus the shortest path will be traced. The proposed method is then compared to Dijkstra\u2019s algorithm, considering different types of tubular spaces. In all cases, the solution provided by the proposed algorithm is smoother, shorter, and has a higher accuracy with a faster calculation speed than that obtained by Dijkstra\u2019s method.<\/jats:p>","DOI":"10.3390\/a15030079","type":"journal-article","created":{"date-parts":[[2022,2,27]],"date-time":"2022-02-27T20:46:17Z","timestamp":1645994777000},"page":"79","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An Effective Algorithm for Finding Shortest Paths in Tubular Spaces"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7988-8457","authenticated-orcid":false,"given":"Dang-Viet-Anh","family":"Nguyen","sequence":"first","affiliation":[{"name":"FEMTO-ST Institute, University Bourgogne Franche-Comt\u00e9, CNRS, 25000 Besan\u00e7on, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e9r\u00f4me","family":"Szewczyk","sequence":"additional","affiliation":[{"name":"Institute for Intelligent Systems and Robotics (ISIR), Sorbonne University, CNRS, INSERM, 75005 Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5946-1889","authenticated-orcid":false,"given":"Kanty","family":"Rabenorosoa","sequence":"additional","affiliation":[{"name":"FEMTO-ST Institute, University Bourgogne Franche-Comt\u00e9, CNRS, 25000 Besan\u00e7on, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,2,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Li, F., and Klette, R. (2011). Euclidean shortest paths. Euclidean Shortest Paths, Springer.","DOI":"10.1007\/978-1-4471-2256-2"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"\u00d6zaslan, T., Shen, S., Mulgaonkar, Y., Michael, N., and Kumar, V. (2015). Inspection of penstocks and featureless tunnel-like environments using micro UAVs. Field and Service Robotics, Springer.","DOI":"10.1007\/978-3-319-07488-7_9"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"\u00d6zaslan, T., Mohta, K., Keller, J., Mulgaonkar, Y., Taylor, C.J., Kumar, V., Wozencraft, J.M., and Hood, T. (2016, January 9\u201314). Towards fully autonomous visual inspection of dark featureless dam penstocks using MAVs. Proceedings of the 2016 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), Daejeon, Korea.","DOI":"10.1109\/IROS.2016.7759734"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1740","DOI":"10.1109\/LRA.2017.2699790","article-title":"Autonomous navigation and mapping for inspection of penstocks and tunnels with MAVs","volume":"2","author":"Loianno","year":"2017","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/s10846-018-0791-y","article-title":"Autonomous MAV-based indoor chimney inspection with 3D laser localization and textured surface reconstruction","volume":"93","author":"Quenzel","year":"2019","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"2169","DOI":"10.1109\/LRA.2020.2970980","article-title":"A Robust UAV System for Operations in a Constrained Environment","volume":"5","author":"Vrba","year":"2020","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/j.robot.2015.09.012","article-title":"Application of robotics in onshore oil and gas industry\u2014A review Part I","volume":"75","author":"Shukla","year":"2016","journal-title":"Robot. Auton. Syst."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Chataigner, F., Cavestany, P., Soler, M., Rizzo, C., Gonzalez, J.P., Bosch, C., Gibert, J., Torrente, A., Gomez, R., and Serrano, D. (2020). Arsi: An aerial robot for sewer inspection. Advances in Robotics Research: From Lab to Market, Springer.","DOI":"10.1007\/978-3-030-22327-4_12"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"991","DOI":"10.2166\/wpt.2018.105","article-title":"A smart unmanned aerial vehicle (UAV) based imaging system for inspection of deep hazardous tunnels","volume":"13","author":"Tan","year":"2018","journal-title":"Water Pract. Technol."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1109\/LRA.2019.2892796","article-title":"Design optimization of sparse sensing array for extended aerial robot navigation in deep hazardous tunnels","volume":"4","author":"Tan","year":"2019","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"994","DOI":"10.1002\/rob.21640","article-title":"Toward autonomous exploration in confined underwater environments","volume":"33","author":"Mallios","year":"2016","journal-title":"J. Field Robot."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"03","DOI":"10.1002\/rob.20165","article-title":"Real-time SLAM with octree evidence grids for exploration in underwater tunnels","volume":"24","author":"Fairfield","year":"2007","journal-title":"J. Field Robot."},{"key":"ref_13","unstructured":"Gary, M., Fairfield, N., Stone, W.C., Wettergreen, D., Kantor, G., and Sharp, J.M. (2008, January 22\u201326). 3D Mapping and Characterization of Sistema Zacat\u00f3n from DEPTHX (DE ep P hreatic TH ermal e X plorer). Proceedings of the ASCE 11th Sinkhole Conference (KARST \u201908), Tallahassee, Florida."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Pidic, A., Aasb\u00f8e, E., Almankaas, J., Wulvik, A., and Steinert, M. (2018, January 26\u201329). Low-Cost Autonomous Underwater Vehicle (AUV) for Inspection of Water-Filled Tunnels During Operation. Proceedings of the International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, Quebec City, QC, Canada.","DOI":"10.1115\/DETC2018-85592"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1109\/JOE.2004.827837","article-title":"Evolutionary path planning for autonomous underwater vehicles in a variable ocean","volume":"29","author":"Alvarez","year":"2004","journal-title":"IEEE J. Ocean. Eng."},{"key":"ref_16","first-page":"221","article-title":"The shortest path planning for manoeuvres of UAV","volume":"10","author":"Gao","year":"2013","journal-title":"Acta Polytech. Hung."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Dang, T., Mascarich, F., Khattak, S., Nguyen, H., Nguyen, H., Hirsh, S., Reinhart, R., Papachristos, C., and Alexis, K. (2020, January 7\u201314). Autonomous search for underground mine rescue using aerial robots. Proceedings of the 2020 IEEE Aerospace Conference, Big Sky, Montana.","DOI":"10.1109\/AERO47225.2020.9172804"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"014501","DOI":"10.1115\/1.4034575","article-title":"Design, fabrication, and testing of a needle-sized wrist for surgical instruments","volume":"11","author":"Swaney","year":"2017","journal-title":"J. Med. Devices"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1109\/LRA.2021.3128685","article-title":"A Hybrid Concentric Tube Robot for Cholesteatoma Laser Surgery","volume":"7","author":"Nguyen","year":"2022","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Canny, J., and Reif, J. (, January 12\u201314). New lower bound techniques for robot motion planning problems. Proceedings of the 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), Los Angeles, CA, USA.","DOI":"10.1109\/SFCS.1987.42"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Sharir, A., and Baltsan, A. (1986, January 2\u20134). On shortest paths amidst convex polyhedra. Proceedings of the second annual symposium on Computational Geometry, Yorktown Heights, NY, USA.","DOI":"10.1145\/10515.10537"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1109\/70.56665","article-title":"Path planning in the presence of vertical obstacles","volume":"6","author":"Gewali","year":"1990","journal-title":"IEEE Trans. Robot. Autom."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Sharathkumar, R., and Yu, H. (2009, January 4\u20136). Approximate Euclidean shortest paths amid convex obstacles. Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, New York, NY, USA.","DOI":"10.1137\/1.9781611973068.32"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1016\/B978-044482537-7\/50016-4","article-title":"Geometric Shortest Paths and Network Optimization","volume":"334","author":"Mitchell","year":"2000","journal-title":"Handb. Comput. Geom."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/S1361-8415(01)00046-9","article-title":"Fast extraction of minimal paths in 3D images and applications to virtual endoscopy","volume":"5","author":"Deschamps","year":"2001","journal-title":"Med. Image Anal."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"962","DOI":"10.1109\/TPAMI.2002.1017622","article-title":"Digital curves in 3D space and a linear-time length estimation algorithm","volume":"24","author":"Bulow","year":"2002","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Li, F., and Klette, R. (2007, January 5\u20137). Rubberband algorithms for solving various 2D or 3D shortest path problems. Proceedings of the 2007 International Conference on Computing: Theory and Applications (ICCTA\u201907), Kolkata, India.","DOI":"10.1109\/ICCTA.2007.113"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1501\/Commua1_0000000669","article-title":"On the curvatures of tubular surface with Bishop frame","volume":"60","author":"Dogan","year":"2011","journal-title":"Commun. Fac. Sci. Univ. Ank. Ser. A1 Math. Stat."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/j.acha.2012.11.002","article-title":"Finding the shortest path by evolving junctions on obstacle boundaries (E-JOB): An initial value ODE\u015b approach","volume":"35","author":"Chow","year":"2013","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Elmokadem, T., and Savkin, A.V. (2021). A method for autonomous collision-free navigation of a quadrotor UAV in unknown tunnel-like environments. Robotica, 1\u201327.","DOI":"10.1017\/S0263574721000849"},{"key":"ref_31","first-page":"285","article-title":"The shortest path through a maze","volume":"1959","author":"Moore","year":"1959","journal-title":"Proc. Int. Symp. Switching Theory"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1017\/S0263574712000331","article-title":"Reactive and the shortest path navigation of a wheeled mobile robot in cluttered environments","volume":"31","author":"Savkin","year":"2013","journal-title":"Robotica"},{"key":"ref_34","first-page":"105","article-title":"The use of the 3D Smoothed parametric curve Path planning for Autonomous mobile robots","volume":"3","author":"Hachour","year":"2009","journal-title":"Int. J. Syst. Appl. Eng. Dev."},{"key":"ref_35","first-page":"81","article-title":"On tubular surfaces in computer graphics","volume":"50","author":"Blaga","year":"2005","journal-title":"Stud. Univ. Babes-Bolyai Inform."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1016\/j.comgeo.2011.05.006","article-title":"A survey of geodesic paths on 3D surfaces","volume":"44","author":"Bose","year":"2011","journal-title":"Comput. Geom."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"1033","DOI":"10.1109\/TRO.2011.2160469","article-title":"Statics and dynamics of continuum robots with general tendon routing and external loading","volume":"27","author":"Rucker","year":"2011","journal-title":"IEEE Trans. Robot."},{"key":"ref_39","unstructured":"Thangavelautham, J., Robinson, M.S., Taits, A., McKinney, T., Amidan, S., and Polak, A. (2017). Flying, hopping Pit-Bots for cave and lava tube exploration on the Moon and Mars. arXiv."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1109\/38.909011","article-title":"3D mapping of underwater caves","volume":"21","year":"2001","journal-title":"IEEE Comput. Graph. Appl."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Boyd, S., Boyd, S.P., and Vandenberghe, L. (2004). Convex Optimization, Cambridge University Press.","DOI":"10.1017\/CBO9780511804441"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/3\/79\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:27:55Z","timestamp":1760135275000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/3\/79"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,25]]},"references-count":41,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2022,3]]}},"alternative-id":["a15030079"],"URL":"https:\/\/doi.org\/10.3390\/a15030079","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,2,25]]}}}