An Effective Algorithm for Finding Shortest Paths in Tubular Spaces
Abstract
:1. Introduction
1.1. Related Works
1.2. Contributions
2. ESP in Tubular Space
2.1. Problem Description
2.2. Directed Graph
3. Basics of Dijkstra’s Algorithm
Algorithm 1: Dijkstra’s algorithm. |
4. The ESP Searching Algorithm Based on Visibility
4.1. Geometric Properties of the ESP in Tubular Space
- ). is the plane that contains and the tangent at of . If is not tangent to , we can always find in a circle with center and radius small enough so that the entire circle can be seen by (as there is no obstacle between and this circle). Then, there exist points outside (which is part of the circle) that can be seen by . This contradicts the definition of . Thus, is tangent to . Let be the tangent point that is closest to and be the tangent plane of at . If , will divide into two subsets. However, as the line of sight of a visible point in must pass through the cross-section of the tube at , only then can one subset of be observed by . This contradicts the definition of . Thus, . We can then define a closed surface enclosed by , the cross-section at , and part of which contains (see Figure 7 Left).
- ). is the plane that contains and the tangent at of S. Then, is the closed surface containing and enclosed by , , and the cross-section of the tube at (see Figure 7 Right).
- Partition 1 (P1): Includes points that can see the destination . The direction at any point in this partition is always towards .
- Partition 2 (P2): Includes points that can see the ending cross-section , but cannot see . The direction at any point in this partition is always towards a visible point in the ending cross-section such that the angle between and is the smallest one.
- Partition 3 (P3): Includes points that cannot see the ending cross-section . The direction of at any point in this partition is the positive direction corresponding to the longest length of sight.
4.2. The Proposed Algorithm
Algorithm 2: Proposed method. |
4.3. Oriented Drilling Process
5. Computational Results
5.1. Computation Time
5.2. Accuracy and Smoothness
6. Discussion
6.1. Extended Applications
6.2. A Reactive Method
7. Conclusions
Author Contributions
Funding
Institutional Review Board Statement
Informed Consent Statement
Data Availability Statement
Conflicts of Interest
Appendix A
Appendix A.1. Proof of Lemma 2
Appendix A.2. Proof of Remark 1
- i.
- Case 1: P1( can see )
- ii.
- Case 2: P2( can see , but )
- iii.
- Case 3: P3( cannot see )
References
- Li, F.; Klette, R. Euclidean shortest paths. In Euclidean Shortest Paths; Springer: Berlin/Heidelberg, Germany, 2011; pp. 3–29. [Google Scholar]
- Özaslan, T.; Shen, S.; Mulgaonkar, Y.; Michael, N.; Kumar, V. Inspection of penstocks and featureless tunnel-like environments using micro UAVs. In Field and Service Robotics; Springer: Berlin/Heidelberg, Germany, 2015; pp. 123–136. [Google Scholar]
- Özaslan, T.; Mohta, K.; Keller, J.; Mulgaonkar, Y.; Taylor, C.J.; Kumar, V.; Wozencraft, J.M.; Hood, T. Towards fully autonomous visual inspection of dark featureless dam penstocks using MAVs. In Proceedings of the 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Daejeon, Korea, 9–14 October 2016; pp. 4998–5005. [Google Scholar]
- Özaslan, T.; Loianno, G.; Keller, J.; Taylor, C.J.; Kumar, V.; Wozencraft, J.M.; Hood, T. Autonomous navigation and mapping for inspection of penstocks and tunnels with MAVs. IEEE Robot. Autom. Lett. 2017, 2, 1740–1747. [Google Scholar] [CrossRef]
- Quenzel, J.; Nieuwenhuisen, M.; Droeschel, D.; Beul, M.; Houben, S.; Behnke, S. Autonomous MAV-based indoor chimney inspection with 3D laser localization and textured surface reconstruction. J. Intell. Robot. Syst. 2019, 93, 317–335. [Google Scholar] [CrossRef]
- Petrlík, M.; Báča, T.; Heřt, D.; Vrba, M.; Krajník, T.; Saska, M. A Robust UAV System for Operations in a Constrained Environment. IEEE Robot. Autom. Lett. 2020, 5, 2169–2176. [Google Scholar] [CrossRef]
- Shukla, A.; Karki, H. Application of robotics in onshore oil and gas industry—A review Part I. Robot. Auton. Syst. 2016, 75, 490–507. [Google Scholar] [CrossRef]
- Chataigner, F.; Cavestany, P.; Soler, M.; Rizzo, C.; Gonzalez, J.P.; Bosch, C.; Gibert, J.; Torrente, A.; Gomez, R.; Serrano, D. Arsi: An aerial robot for sewer inspection. In Advances in Robotics Research: From Lab to Market; Springer: Berlin/Heidelberg, Germany, 2020; pp. 249–274. [Google Scholar]
- Tan, C.H.; Ng, M.; Shaiful, D.S.B.; Win, S.K.H.; Ang, W.; Yeung, S.K.; Lim, H.; Do, M.N.; Foong, S. A smart unmanned aerial vehicle (UAV) based imaging system for inspection of deep hazardous tunnels. Water Pract. Technol. 2018, 13, 991–1000. [Google Scholar] [CrossRef]
- Tan, C.H.; bin Shaiful, D.S.; Ang, W.J.; Win, S.K.H.; Foong, S. Design optimization of sparse sensing array for extended aerial robot navigation in deep hazardous tunnels. IEEE Robot. Autom. Lett. 2019, 4, 862–869. [Google Scholar] [CrossRef]
- Mallios, A.; Ridao, P.; Ribas, D.; Carreras, M.; Camilli, R. Toward autonomous exploration in confined underwater environments. J. Field Robot. 2016, 33, 994–1012. [Google Scholar] [CrossRef] [Green Version]
- Fairfield, N.; Kantor, G.; Wettergreen, D. Real-time SLAM with octree evidence grids for exploration in underwater tunnels. J. Field Robot. 2007, 24, 03–21. [Google Scholar] [CrossRef] [Green Version]
- Gary, M.; Fairfield, N.; Stone, W.C.; Wettergreen, D.; Kantor, G.; Sharp, J.M., Jr. 3D Mapping and Characterization of Sistema Zacatón from DEPTHX (DE ep P hreatic TH ermal e X plorer). In Proceedings of the ASCE 11th Sinkhole Conference (KARST ’08), Tallahassee, Florida, 22–26 September 2008; pp. 202–212. [Google Scholar]
- Pidic, A.; Aasbøe, E.; Almankaas, J.; Wulvik, A.; Steinert, M. Low-Cost Autonomous Underwater Vehicle (AUV) for Inspection of Water-Filled Tunnels During Operation. In Proceedings of the International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, Quebec City, QC, Canada, 26–29 August 2018. [Google Scholar]
- Alvarez, A.; Caiti, A.; Onken, R. Evolutionary path planning for autonomous underwater vehicles in a variable ocean. IEEE J. Ocean. Eng. 2004, 29, 418–429. [Google Scholar] [CrossRef]
- Gao, X.Z.; Hou, Z.X.; Zhu, X.F.; Zhang, J.T.; Chen, X.Q. The shortest path planning for manoeuvres of UAV. Acta Polytech. Hung. 2013, 10, 221–239. [Google Scholar]
- Dang, T.; Mascarich, F.; Khattak, S.; Nguyen, H.; Nguyen, H.; Hirsh, S.; Reinhart, R.; Papachristos, C.; Alexis, K. Autonomous search for underground mine rescue using aerial robots. In Proceedings of the 2020 IEEE Aerospace Conference, Big Sky, Montana, 7–14 March 2020; pp. 1–8. [Google Scholar]
- Swaney, P.J.; York, P.A.; Gilbert, H.B.; Burgner-Kahrs, J.; Webster, R.J. Design, fabrication, and testing of a needle-sized wrist for surgical instruments. J. Med. Devices 2017, 11, 014501. [Google Scholar] [CrossRef] [PubMed] [Green Version]
- Nguyen, D.-V.-A.; Girerd, C.; Boyer, Q.; Rougeot, P.; Lehmann, O.; Tavernier, L.; Szewczyk, J.; Rabenorosoa, K. A Hybrid Concentric Tube Robot for Cholesteatoma Laser Surgery. IEEE Robot. Autom. Lett. 2022, 7, 462–469. [Google Scholar] [CrossRef]
- Canny, J.; Reif, J. New lower bound techniques for robot motion planning problems. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), Los Angeles, CA, USA, 12–14 October1987; pp. 49–60. [Google Scholar]
- Sharir, A.; Baltsan, A. On shortest paths amidst convex polyhedra. In Proceedings of the second annual symposium on Computational Geometry, Yorktown Heights, NY, USA, 2–4 June 1986; pp. 193–206. [Google Scholar]
- Gewali, L.P.; Ntafos, S.; Tollis, I.G. Path planning in the presence of vertical obstacles. IEEE Trans. Robot. Autom. 1990, 6, 331–341. [Google Scholar] [CrossRef]
- Agarwal, P.K.; Sharathkumar, R.; Yu, H. Approximate Euclidean shortest paths amid convex obstacles. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, New York, NY, USA, 4–6 January 2009; pp. 283–292. [Google Scholar]
- Mitchell, J.S. Geometric Shortest Paths and Network Optimization. Handb. Comput. Geom. 2000, 334, 633–702. [Google Scholar]
- Deschamps, T.; Cohen, L.D. Fast extraction of minimal paths in 3D images and applications to virtual endoscopy. Med. Image Anal. 2001, 5, 281–299. [Google Scholar] [CrossRef] [Green Version]
- Bulow, T.; Klette, R. Digital curves in 3D space and a linear-time length estimation algorithm. IEEE Trans. Pattern Anal. Mach. Intell. 2002, 24, 962–970. [Google Scholar] [CrossRef]
- Li, F.; Klette, R. Rubberband algorithms for solving various 2D or 3D shortest path problems. In Proceedings of the 2007 International Conference on Computing: Theory and Applications (ICCTA’07), Kolkata, India, 5–7 March 2007; pp. 9–19. [Google Scholar]
- Dogan, F.; Yayli, Y. On the curvatures of tubular surface with Bishop frame. Commun. Fac. Sci. Univ. Ank. Ser. A1 Math. Stat. 2011, 60, 59–69. [Google Scholar]
- Chow, S.N.; Lu, J.; Zhou, H.M. Finding the shortest path by evolving junctions on obstacle boundaries (E-JOB): An initial value ODEś approach. Appl. Comput. Harmon. Anal. 2013, 35, 165–176. [Google Scholar] [CrossRef]
- Elmokadem, T.; Savkin, A.V. A method for autonomous collision-free navigation of a quadrotor UAV in unknown tunnel-like environments. Robotica 2021, 1–27. [Google Scholar] [CrossRef]
- Moore, E.F. The shortest path through a maze. Proc. Int. Symp. Switching Theory 1959, 1959, 285–292. [Google Scholar]
- Dijkstra, E.W. A note on two problems in connexion with graphs. Numer. Math. 1959, 1, 269–271. [Google Scholar] [CrossRef] [Green Version]
- Savkin, A.V.; Hoy, M. Reactive and the shortest path navigation of a wheeled mobile robot in cluttered environments. Robotica 2013, 31, 323–330. [Google Scholar] [CrossRef]
- Hachour, O. The use of the 3D Smoothed parametric curve Path planning for Autonomous mobile robots. Int. J. Syst. Appl. Eng. Dev. 2009, 3, 105–116. [Google Scholar]
- Blaga, P.A. On tubular surfaces in computer graphics. Stud. Univ. Babes-Bolyai Inform. 2005, 50, 81–90. [Google Scholar]
- Hart, P.E.; Nilsson, N.J.; Raphael, B. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 1968, 4, 100–107. [Google Scholar] [CrossRef]
- Bose, P.; Maheshwari, A.; Shu, C.; Wuhrer, S. A survey of geodesic paths on 3D surfaces. Comput. Geom. 2011, 44, 486–498. [Google Scholar] [CrossRef] [Green Version]
- Rucker, D.C.; Webster, R.J., III. Statics and dynamics of continuum robots with general tendon routing and external loading. IEEE Trans. Robot. 2011, 27, 1033–1044. [Google Scholar] [CrossRef]
- Thangavelautham, J.; Robinson, M.S.; Taits, A.; McKinney, T.; Amidan, S.; Polak, A. Flying, hopping Pit-Bots for cave and lava tube exploration on the Moon and Mars. arXiv 2017, arXiv:1701.07799. [Google Scholar]
- am Ende, B. 3D mapping of underwater caves. IEEE Comput. Graph. Appl. 2001, 21, 14–20. [Google Scholar] [CrossRef]
- Boyd, S.; Boyd, S.P.; Vandenberghe, L. Convex Optimization; Cambridge University Press: Cambridge, UK, 2004. [Google Scholar]
, | ||
T.P = 0.76, T.D = 4.10 | ||
, | , | |
T.P = 0.96, T.D = 16.66 | T.P = 1.05, T.D = 15.77 | |
, | , | |
T.P = 1.63, T.D = 64.67 | T.P = 1.51, T.D = 60.19 | |
, | , | |
T.P = 3.03, T.D = 259.23 | T.P = 2.01, T.D = 219.82 |
1. Plane Parabolic Centerline | 2. Plane Elliptical Centerline | 3. Plane Hyperbolic Centerline |
L.P = 27.22, L.D = 27.29, L.E = 27.21 (cm) | L.P = 25.70, L.D = 25.74, L.E = 25.68 (cm) | L.P = 27.97, L.D = 28.10, L.E = 27.96 (cm) |
T.P = 0.68, T.D = 2.57 (s) | T.P = 1.02, T.D = 2.65 (s) | T.P = 0.73, T.D = 2.64 (s) |
4. Plane Sinusoidal Centerline | 5. Plane Evolvent of a Circle | 6. Wave-Shaped Torus on a Sphere |
L.P = 24.41, L.D = 24.53, L.E = 24.39 | L.P = 21.92, L.D = 21.94, L.E = 21.91 | L.P = 22.29, L.D = 25.12, L.E = 21.96 |
T.P = 1.36 (s), T.D = 2.66 | T.P = 1.16 (s), T.D = 2.57 | T.P = 1.26 (s), T.D = 2.74 |
7. Tubular Helical Surface | 8. Tubular Spiral Surface | 9. Complex Shape Tubular Surface |
L.P = 20.05, L.D = 20.31, L.E = 20.01 | L.P = 18.87, L.D = 19.02, L.E = 18.71 | L.P = 110.96, L.D = 111.22, L.E = 110.92 |
T.P = 1.00 (s), T.D = 2.74 | T.P = 1.17 (s), T.D = 2.88 | T.P = 5.90 (s), T.D = 11.29 |
RMSE | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|
Tube | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Avg. |
Dijkstra’s algorithm | 0.506% | 0.032% | 1.922% | 0.118% | 0.007% | 12.487% | 1.655% | 1.334% | 1.140% | 2.133% |
Proposed algorithm | 0.002% | 0.002% | 0.004% | 0.009% | 0.001% | 1.003% | 0.510% | 0.368% | 0.974% | 0.319% |
Maximum Error | ||||||||||
Tube | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Avg. |
Dijkstra’s algorithm | 4.343% | 0.628% | 11.812% | 1.136% | 0.226% | 28.121% | 8.556% | 11.942% | 12.017% | 8.753% |
Proposed algorithm | 0.012% | 0.016% | 0.026% | 0.105% | 0.015% | 4.774% | 2.077% | 2.039% | 3.782% | 1.427% |
Tube 6 | L.P (cm) | 22.28 | 22.35 | 22.29 | 22.27 | 22.32 | 22.37 | 22.44 | 22.26 |
L.D (cm) | 25.83 | 25.83 | 25.83 | 23.74 | 25.18 | 25.18 | 25.18 | 22.05 | |
(%) | 1.05 | 1.34 | 0.77 | 0.71 | 1.13 | 1.70 | 1.72 | 0.89 | |
(%) | 13.58 | 13.58 | 13.58 | 2.90 | 12.00 | 12.00 | 12.00 | 0.30 | |
T.P (s) | 0.45 | 0.78 | 1.18 | 1.82 | 0.86 | 1.70 | 2.73 | 17.01 | |
T.D (s) | 0.16 | 1.54 | 5.70 | 22.00 | 1.66 | 21.38 | 82.90 | 5582.00 | |
Tube 7 | L.P (cm) | 20.06 | 20.04 | 20.04 | 20.08 | 20.05 | 20.05 | 20.04 | 20.08 |
L.D (cm) | 20.82 | 20.82 | 20.82 | 20.82 | 20.32 | 20.32 | 20.32 | 20.09 | |
(%) | 0.62 | 0.14 | 0.30 | 0.73 | 0.55 | 0.17 | 0.20 | 0.59 | |
(%) | 2.92 | 2.92 | 2.92 | 2.92 | 1.61 | 1.61 | 1.61 | 0.06 | |
T.P (s) | 0.31 | 0.60 | 0.85 | 1.34 | 0.66 | 1.15 | 1.67 | 7.67 | |
T.D (s) | 0.15 | 1.52 | 5.58 | 21.82 | 1.63 | 21.89 | 84.34 | 5585.00 |
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. |
© 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
Share and Cite
Nguyen, D.-V.-A.; Szewczyk, J.; Rabenorosoa, K. An Effective Algorithm for Finding Shortest Paths in Tubular Spaces. Algorithms 2022, 15, 79. https://doi.org/10.3390/a15030079
Nguyen D-V-A, Szewczyk J, Rabenorosoa K. An Effective Algorithm for Finding Shortest Paths in Tubular Spaces. Algorithms. 2022; 15(3):79. https://doi.org/10.3390/a15030079
Chicago/Turabian StyleNguyen, Dang-Viet-Anh, Jérôme Szewczyk, and Kanty Rabenorosoa. 2022. "An Effective Algorithm for Finding Shortest Paths in Tubular Spaces" Algorithms 15, no. 3: 79. https://doi.org/10.3390/a15030079
APA StyleNguyen, D. -V. -A., Szewczyk, J., & Rabenorosoa, K. (2022). An Effective Algorithm for Finding Shortest Paths in Tubular Spaces. Algorithms, 15(3), 79. https://doi.org/10.3390/a15030079