Abstract
In this paper, an exact algorithm based on the method of orienting curves is developed for solving the convex non-differentiable optimization problem on the closed unit cube in a finite dimensional space: finding the shortest path joining two points going through a sequence of adjacent triangles in 3D. As a result, the global solution of the problem is determined successively by some orienting curves and final curve, which can be exactly constructed with ruler and compass. A detailed numerical example is presented.
Similar content being viewed by others
References
Agarwal, P.K., Har-Peled, S., Karia, M.: Computing approximate shortest paths on convex polytopes. Algorithmica 33, 227–242 (2002)
An, P. T., Le, N. T.: The method of multiple shooting for finding approximately shortest paths for autonomous robots in unknown environments in 2D (2022) (submitted). arXiv:2208.10386
An, P.T.: Finding shortest paths in a sequence of triangles in 3D by the method of orienting curves. Optimization 67, 159–177 (2018)
An, P.T., Hai, N.N., Hoai, T.V., Trang, L.H.: On the Performance of Triangulation-Based Multiple Shooting Method for 2D Shortest Path Problems. LNCS Transactions on Large Scale Data and Knowledge Centered Systems, pp. 45–56. Springer, Berlin (2014)
An, P.T., Trang, L.H.: An efficient convex hull algorithm for finite point sets in 3D based on the method of orienting curves. Optimization 62, 975–988 (2013)
An, P.T.: Method of orienting curves for determining the convex hull of a finite set of points in the plane. Optimization 59, 175–179 (2010)
Burkard, R.E., Rote, G., Yao, E.Y., Yu, Z.L.: Shortest polygonal paths in space. Computing 45, 51–68 (1990)
Chen, J., Han, Y.: Shortest paths on a polyhedron. Int. J. Comput. Geom. Appl. 6, 127–144 (1996)
Cheng, S., Jin, J.: Shortest paths on polyhedral surfaces and terrains. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, New York, pp. 373–382 (2014)
Cook, A.F., IV., Wenk, C.: Shortest path problems on a polyhedral surface. Algorithmica 69, 58–77 (2014)
Dinh, N., Phu, H.X.: Solving a class of regular optimal control problems with state constraints by the method of orienting curves. Optimization 25, 231–247 (1992)
Dinh, N., Phu, H.X.: Solving a class of optimal control problems which are linear in the control variable by the method of orienting curves. Acta Math. Vietnam 17, 115–134 (1992)
Dinh, N., Phu, H.X.: The method of orienting curves and its application to an optimal control problem of hydroelectric power plants. Vietnam J. Math. 20, 40–53 (1992)
Hai, N.N., An, P.T., Huyen, P.T.T.: Shortest paths along a sequence of line segments in Euclidean spaces. J. Convex Anal. 26(4), 1089–1112 (2019)
Hahmann, S., Belyaev, A., Busé, L., Elber, G., Mourrain, B., Roessl, C.: Shape interrogation. In: Mathematics and Visualization, pp. 1–57 (2007)
JavaView software (Interactive 3D Geometry and Visualization) at the link: http://www.javaview.de/
Lee, D.T., Preparata, F.P.: Euclidean shortest paths in the presence of rectilinear battiers. Networks 14, 393–410 (1984)
Lieutier, A., Thibert, B.: Geodesic as limit of geodesics on PL-surfaces. In: Chen, F., Jüttler, B. (eds.) Advances in Geometric Modeling and Processing. GMP 2008. Lecture Notes in Computer Science, vol. 4975. Springer, Berlin
Mitchell, J.S.B., Mount, D.M., Papadimitriou, C.H.: The discrete geodesic problem. SIAM J. Comput. 16, 647–668 (1987)
O’Rourke, J.: Unfolding face-neighborhood convex patches: counterexamples and positive results. In: Proceedings of the 25th Canadian Conference on Computational Geometry, Waterloo, Ontario, August 8–10 (2013)
Papadopoulos, A.: Metric Spaces, Convexity and Non-positive Curvature, IRMA Lectures in Mathematics and Theoretical Physics, vol. 6. European Mathematical Society (EMS), Zürich (2005)
Pham-Trong, V., Szafran, N., Biard, L.: Pseudo-geodesics on three-dimensional surfaces and pseudo-geodesic meshes. Numer. Algorithms 26(4), 305–315 (2001)
Phu, H.X.: Zur Lösung einer regulären Aufgabenklasse der optimalen Steuerung im Großen mittels Orientierungskurven. Optimization 18, 65–81 (1987)
Phu, H.X.: Ein konstruktives Lösungsverfahren für das Problem des Inpolygons kleinsten Umfangs von J. Steiner. Optimization 18, 349–359 (1987)
Phu, H.X.: Zur Lösung eines Zermeloschen Navigationsproblems. Optimization 18, 225–236 (1987)
Phu, H.X.: Method of orienting curves for solving optimal control problems with state constraints. Numer. Funct. Anal. Optim. 12, 173–211 (1991)
Phu, H.X., Bock, H.G., Schlöder, J.: The method of orienting curves and its application for manipulator trajectory planning. Numer. Funct. Anal. Optim. 18, 213–225 (1997)
Phu, H.X., Dinh, N.: Some remarks on the method of orienting curves. Numer. Funct. Anal. Optim. 16, 755–763 (1995)
Phu, H.X., Long, T.D.: Orienting method for obstacle problems. Zeitschrift für Analysis und ihre Anwendungen 21, 233–248 (2002)
Polthier, K., Schmies, M.: Straightest geodesics on polyhedral surfaces. In: Hege, H.C., Polthier, K. (eds.) Mathematical Visualization, pp. 135–150. Springer, Heidelberg (1998)
Sharir, M., Schorr, A.: On shortest paths in polyhedral spaces. SIAM J. Comput. 15, 193–215 (1986)
TurtleBot3 Burger robot https://www.robotis.us/turtlebot-3/
TurtleBot3 Burger robot, which has the exact vision range of 0.8m, finds a path avoiding obstacles to the goal that is a red wine box located in another room that is 14m far from the robot. The video https://www.youtube.com/watch?v=HYnNVsh7fpw &feature=youtu.be that captured this event was recorded at Institute of Mathematical and Computational Sciences - IMACS, Ho Chi Minh City University of Technology, in April 2022
Xin, S.-Q., Wang, G.-J.: Efficiently determining a locally shortest path on polyhedral surfaces. Comput. Aided Des. 39, 1081–1090 (2007)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The research of the first author was funded by Vietnam National University Ho Chi Minh City (VNU-HCM) under Grant Number T2022 - 20 -01. The second author was supported by the Vietnam Academy of Science and Technology under Grant Number NVCC01.02/22-23. They thank the reviewers for their value comments.
Appendix
Appendix
Connection of the results to the field of global optimization
In [22], to get a shortest path joining two points on a smooth surface (or “the shortest path problem on smooth surfaces", for short), Pham-Trong at al. trangulate the surface then solve the auxiliary problems of finding the globally shortest path joining two these points going through a sequence of selected adjacent triangles, in which the next sequence of selected adjacent triangles is chosen by a so-called pivot vertex (see Algorithm 4.3 [22]). Finally, the limit of solutions of such auxiliary problems is a locally shortest path joining two points on the smooth surface. Thus, although a local solution of an auxiliary problem is a global one (Corollary 2), for the shortest path problem on smooth surfaces, there can be many local optimal solutions which are not global.
To avoid this issue, we determine the number of all such auxiliary problems and then the globally shortest path on a triangulated surface is obtained from their minimum. For example, to get a globally shortest path joining two points \(p_0\) and \(p_5\) on the triangulated surface consisting of triangles 0, 0’, 1, 2, 3, 4, 5 and 5’ (see Fig. 6), we solve 4 following auxiliary problems: finding the globally shortest path joining two points \(p_0\) and \(p_5\) going through the sequence of triangles \((0, 1, 2, 3, 4, 5), ((0, 0', 3, 4, 5), (0, 1, 2, 5', 5)\), and \((0, 0', 3, 2, 5', 5)\), respectively).
Recall that the number of all such auxiliary problems can be reduced by pivot vertex technique mentioned above.
A real life application of the problem of finding the globally shortest path joining two points going through a sequence of selected adjacent triangles
The problem of finding the globally shortest path joining two points going through a sequence of selected adjacent triangles has been applied successfully in the following autonomous robot problem: A robot in with a limited vision range to find a path to a goal in the unknown environment of polygonal obstacles. To solve this problem, suitable sequences of adjacent triangles of the explored map are constructed then the robot finds the shortest paths between two locations on.
We experienced our approximate algorithms [2] and [4] on the autonomous robot TurtleBot3 Burger [32], which has the exact vision range of 0.8 m, in real environment [33]. During operations of the robot, suitable sequences of adjacent triangles of the explored map are constructed (this is displayed on the window on the upper right corner in the video [33]). The full video [33] that captured this event was recorded at our institute in April 2022, in which the robot finds a path avoiding obstacles to the goal that is a red wine box located in another room that is 14m far from the robot.
Our exact Algorithms 1–5 can be implemented in Python and integrated in autonomous robots moving on terrains. This will be the subject of another paper.
Rights and permissions
Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
An, P.T., Phu, H.X. Finding globally shortest paths through a sequence of adjacent triangles by the method of orienting curves. J Glob Optim 85, 1037–1063 (2023). https://doi.org/10.1007/s10898-022-01244-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-022-01244-x
Keywords
- Convex non-differentiable optimization
- Exact algorithm
- Global solution
- Path planning
- Planar unfolding
- Polyhedral surface
- Polytope
- Shortest path
- Straightest geodesic