The article addresses the problem of constructing time-optimal routes for one or several moving objects in a dynamic environment with obstacles. We propose an approach based on the optical-geometrical analogy and the principles of Fermat and Huygens, which reduces the problem to solving the eikonal equation. A series of algorithms (including modifications of the fast marching method) is developed. They allow one to construct collision-free trajectories and correct them when the situation changes. The effectiveness of the proposed methods is confirmed by computational experiments, demonstrating their superiority in route length and computation time compared to existing approaches such as CFM, PRIMAL, and DHC.
Keywords: routing problem, dynamic environment, optical-geometric approach, eikonal equation, fast marching method
Received October 15, 2025
Revised October 21, 2025
Accepted October 27, 2025
Funding Agency: A.A. Lempert’s research is supported by the Russian Science Foundation, project no. 24-21-00264, https://rscf.ru/project/24-21-00264.
Aleksandr Leonidovich Kazakov, Dr. Phys.-Math. Sci., Matrosov Institute for System Dynamics and Control Theory of the Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia, e-mail: kazakov@icc.ru
Anna Ananievna Lempert, Cand. Sci. (Phys.-Math.), Matrosov Institute for System Dynamics and Control Theory of the Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia, e-mail: lempert@icc.ru
Tuan Viet Tran, Irkutsk National Research Technical University, Irkutsk, 664074 Russia, e-mail: ttviet@ictu.edu.vn
REFERENCES
1. Teotia V.S. Impact of delivery speed on customer satisfaction in online shopping: a focus on quick commerce. Inter. J. Sci. Res. Engin. Manag. (IJSREM), 2025, vol. 9, no. 5, pp. 1–9. https://doi.org/10.55041/IJSREM49149
2. Demir E., Syntetos A., Van Woensel T. Last mile logistics: research trends and needs. IMA J. Manag. Math., 2022, vol. 33, no. 4, pp. 549–561. https://doi.org/10.1093/imaman/dpac006
3. Gutin G., Punnen A.P. The traveling salesman problem and its variations. Ser. Combinatorial Optimization (COOP). Vol. 12. NY, Springer, 2007, 830 p. https://doi.org/10.1007/b101971
4. Gimadi E.Kh., Khachai M.Yu. Ekstremal’nyye zadachi na mnozhestvakh perestanovok [Extremal problems on permutation sets]. Yekaterinburg, Izd-vo UMTS UPI, 2016, 220 p. ISBN: 978-8-8295-0497-7 .
5. Beresneva E., Avdoshin S. Analysis of mathematical formulations of capacitated vehicle routing problem and methods for their solution. Proc. Inst. System Programm. RAS, 2018, vol. 30, no. 3, pp. 233–250. https://doi.org/10.15514/ISPRAS-2018-30(3)-17
6. Youakim D., Ridao P. Motion planning survey for autonomous mobile manipulators underwater manipulator case study. Robot. Auton. Syst., 2018, vol. 107, pp. 20–44. https://doi.org/10.1016/j.robot.2018.05.006
7. Shin Y.W., Abebe M., Noh Y., Lee S., Lee I., Kim D., Bae J., Kim K.C. Near-optimal weather routing by using improved A* algorithm. Appl. Sci., 2020, vol. 10, no. 17, art. no. 6010. https://doi.org/10.3390/app10176010
8. Naderi K., Rajamaki J., Hamalainen P. RT-RRT*: a real-time path planning algorithm based on RRT*. In: Proc. of the 8th ACM SIGGRAPH Conf. Motion in Games (MIG’15), 2015, pp. 113–118. https://doi.org/10.1145/2822013.2822036
9. Dijkstra E.W. A note on two problems in connexion with graphs. Numer. Math., 1959, vol. 1, no. 1, pp. 269–271. https://doi.org/10.1007/BF01386390
10. Floyd R.W. Algorithm 97: shortest path. Commun. ACM, 1962, vol. 5, no. 6, p. 345. https://doi.org/10.1145/367766.368168
11. Matthews J. Basic A* pathfinding made simple. In: Rabin S. (ed.) AI game programming wisdom. Boston, Charles River Media, 2002, pp. 105–113.
12. Stentz A. Optimal and efficient path planning for partially-known environments. In: Proc. 1994 IEEE Inter. Conf. Robotics and Automation, San Diego, CA, USA, 1994, pp. 3310–3317. https://doi.org/10.1109/ROBOT.1994.351061
13. Injarapu V.A.S.H.H., Gawre S.K. A survey of autonomous mobile robot path planning approaches. In: Proc. Inter. Conf. Recent innovations in signal processing and embedded systems (RISE 2017), Bhopal, India, 2017, pp. 624–628. https://doi.org/10.1109/RISE.2017.8378228
14. Pennino S., Gaglione S., Innac A., Piscopo V., Scamardella A. Development of a new ship adaptive weather routing model based on seakeeping analysis and optimization. J. Mar. Sci. Eng., 2020, vol. 8, no. 4, pp. 270. https://doi.org/10.3390/jmse8040270
15. Vemula A., Muelling K., Oh J. Path planning in dynamic environments with adaptive dimensionality. In: Proc. Ninth Internat. Symp. on Combinatorial Search (SoCS’16), NY, 2016, vol. 9, no. 1, pp. 107–116. https://doi.org/10.1609/socs.v7i1.18386
16. Sarapulov A.V. Methods for solving the problem of constructing a trajectory for an unmanned aerial vehicle in a dynamic environment. Raketno-kosmicheskaya Tekhnika, 2017, vol. 1, no. 2. pp. 92–99 (in Russian).
17. Ulyanov S., Bychkov I., Maksimkin N. Event-based path-planning and path-following in unknown environments for underactuated autonomous underwater vehicles. Appl. Sci., 2020, vol. 10, no. 21, art. no. 7894. https://doi.org/10.3390/app10217894
18. Zheng H., Xu W., Ma D., Qu F. Dynamic rolling horizon scheduling of waterborne AGVs for inter terminal transportation: mathematical modeling and heuristic solution. In: IEEE Transactions on Intelligent Transportation Systems. 2022, vol. 23, no. 4, pp. 3853–3865.
https://doi.org/10.1109/TITS.2021.3102998
19. Liu C., Chu X., Wu W., Li S., He Z., Zheng M. Human–machine cooperation research for navigation of maritime autonomous surface ships: A review and consideration. Ocean Eng., 2022, vol. 246, art. no. 110555. https://doi.org/10.1016/j.oceaneng.2022.110555
20. He Z., Liu C., Chu X., Negenborn R.R., Wu Q. Dynamic anti-collision A-star algorithm for multi-ship encounter situations. Appl. Ocean Res., 2022, vol. 118, art. no. 102995. https://doi.org/10.1016/j.apor.2021.102995
21. Ushakov V.N., Lavrov N.G., Ushakov A.V. Construction of solutions in an approach problem of a stationary control system. Trudy Inst. Mat. i Mekh. UrO RAN, 2014, vol. 20, no. 4, pp. 277–286 (in Russian).
22. Ushakov V.N., Ershov A.A., Matviychuk A.R., Ushakov A.V. Some problems of target approach for nonlinear control system at a fixed time moment. Izv. Inst. Mat. i Inf. Udm. Gos. Univ., 2023, vol. 62, pp. 125–155 (in Russian). https://doi.org/10.35634/2226-3594-2023-62-09
23. Ushakov V.N., Ershov A.A. On the construction of solutions to a game problem with a fixed end time. Trudy Inst. Mat. i Mekh. UrO RAN, 2024, vol. 30, no. 3, pp. 255–273 (in Russian). https://doi.org/10.21538/0134-4889-2024-30-3-255-273
24. Samokhina M.A., Galyaev A.A. Constructing a map of locally optimal paths for a controlled moving object in a threat environment. Contr. Sci., 2014, no. 1, pp. 75–85. https://doi.org/10.25728/cs.2024.1.8
25. Kunz T., Hutchinson S. Real-time path planning for a robot arm in changing environments. In: Proc. IEEE/RSJ Inter. Conf. Intelligent Robots and Systems (IROS’10), Taipei, Taiwan, 2010, pp. 5906–5911. https://doi.org/10.1109/IROS.2010.5653275
26. Kazakov A.L., Lempert A.A. An approach to optimization in transport logistics. Autom. Remote Control, 2011, vol. 72, no. 7, pp. 1398–1404. https://doi.org/10.1134/S0005117911070071
27. Bukharov D.S., Kazakov A.L. “VIGOLT” system for solving transport logistics optimization problems. Vych. Met. Prog., 2012, vol. 13, no. 3, pp. 65–74 (in Russian).
28. Kazakov A.L., Lempert A.A. On the route construction in changing environments using solutions of the eikonal equation. Izv. Inst. Mat. i Inf. Udm. Gos. Univ., 2021, vol. 58, pp. 59–72. https://doi.org/10.35634/2226-3594-2021-58-04
29. Feynman R.P., Leighton R.B., Sands M. Feynman lectures on physics. Vol. 3. Addison Wesley, 1971, 379 p. ISBN-10: 0201021188 . Translated to Russian under the title Feinmanovskie lektsii po fizike. Tom 3. Izluchenie. Volny. Kvanty, Moscow, Editorial URSS, 2004, 240 p.
30. Borovskikh A.V. The two-dimensional eikonal equation. Sib. Math. J., 2006, vol. 47, no. 5, pp. 813–834. https://doi.org/10.1007/s11202-006-0091-9
31. Huptych M., Röck S. Real-time path planning in dynamic environments for unmanned aerial vehicles using the curve-shortening flow method. Inter. J. Adv. Robotic Syst., 2021, vol. 18, no. 6, pp. 1–16. https://doi.org/10.1177/1729881420968687
32. Sartoretti G., Kerr J., Shi Y., Wagner G., Kumar T.K.S., Koenig S., Choset H. PRIMAL: pathfinding via reinforcement and imitation multi-agent learning. In: IEEE Robotics and Autom. Letters, 2019, vol. 4, no. 3, pp. 2378–2385. https://doi.org/10.1109/LRA.2019.2903261
33. Ma Z., Luo Y., Ma H. Distributed heuristic multi-agent path finding with communication. In: Proc. 2021 IEEE Inter. Conf. Robotics and Automation (ICRA), Xi’an, China, 2021, pp. 8699–8705. https://doi.org/10.1109/ICRA48506.2021.9560748
Cite this article as: A.L. Kazakov, A.A. Lempert, T.V. Tran. On constructing the fastest collision-free routes in dynamic environments with moving obstacles. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2025, vol. 31, no. 4, pp. 115–131.
