A METHOD FOR PLANNING ROBOTIC MOVEMENTS IN COMPLEX CONFLICT ENVIRONMENTS WITH POLYGONAL OBSTACLES
Abstract
When developing algorithms for real-time robot path planning, the problem of performance limitations of the corresponding classical algorithms arises. This paper considers a method for planning robot movements in a two-dimensional complex conflict environment. For planning in complex environments, a hybrid planning algorithm is proposed, based on a combination and synthesis of the classical cellular decomposition algorithm and a recently proposed algorithm based on the characteristic visibility graph. This algorithm involves a preliminary analysis of the complexity of the obstacle scene, based on the results of which one of the two specified particular algorithms is selected. It is shown that this approach can significantly overcome the limitations of both of these algorithms. A disturbance avoidance method based on the apparatus of characteristic probability functions is described in a compact form, and its relationship with planning methods in complex environments is demonstrated when solving corresponding problems of global optimization of the probability of successful completion of a target trajectory. The developed approach examines the relationship between the probability of successful path completion in a source field and the corresponding risk function. To solve global robot motion planning problems in complex conflict environments, the proposed hybrid algorithm is first proposed for constructing a family of initial curves within the appropriate feasible motion corridors, ignoring sources. A family of local optimization problems is then solved within the feasible motion corridors, taking sources into account. Next, the trajectory with the maximum probability of successful completion or the normalized safe motion function is selected
References
1. Sleumer N.H., Tschichold-Gurman N. Exact cell decomposition of arrangements used for path planning in robotics, Zurich: Inst. of Theoretical Computer Science, 1999. DOI: 10.3929/ethz-a-006653440.
2. Koenig S., Likhachev M., Furcy D. Lifelong planning A*, Artificial Intelligence, 2004, Vol. 155,
No. 1-2, pp. 93-146. DOI: 10.1016/j.artint.2003.12.001.
3. Ferguson D., Stentz A. Using interpolation to improve path planning: The field D* algorithm, J. of Field Robotics, 2006, Vol. 23, No. 2, pp. 79-101. DOI: 10.1002/rob.20109.
4. Mohamed S. Marzouqi and Ray A. Jarvis. New visibility-based path-planning approach for covert robot-ic navigation, Robotica, 2006, Vol. 24, No. 6, pp. 759-773. doi: 10.1017/S0263574706002931.
5. Petereit J., Emter T. and Frey C. W. Safe mobile robot motion planning for waypoint sequences in a dynamic environment, Proc. 2013 IEEE International Conference on Industrial Technology (ICIT). Cape Town, South Africa, 2013, pp. 181-186. doi: 10.1109/ICIT.2013.6505669.
6. Wang S., Li Z., Wang B. and Li M. Collision Avoidance Motion Planning for Connected and Automat-ed Vehicle Platoon Merging and Splitting With a Hybrid Automaton Architecture, IEEE Transactions on Intelligent Transportation Systems, Feb. 2024, Vol. 25, No. 2, pp. 1445-1464. doi: 10.1109/TITS.2023.3315063.
7. Guangliang Liao, Chunyun Fu, Yinghong Yu, Kexue Lai, Beihao Xia , and Jingkang Xia. Decoupling Objectives for Segmented Path Planning: A Subtask-Oriented Trajectory Planning Approach, IEEE Transactions on Intelligent Transportation Systems, 2025, Vol. 26, No. 3, pp. 3960-3975.
8. Zhong W., Zheng S., Huang J., Zhou Z., Wu M. and Yu R. Integrating Global Path Information With Advanced Risk Assessment: An Enhanced Potential Field Method for Intelligent Connected Vehicles Local Path Planning, IEEE Sensors Journal, June, 2025, Vol. 25, No. 11, pp. 20309-20322. doi: 10.1109/JSEN.2025.3553534.
9. Kostyukov V.A., Medvedev M.Yu., Pshikhopov V.Kh. Algoritm planirovaniya traektoriy v dvumernoy srede s prepyatstviyami na klasse kusochno-lomanykh traektoriy [Algorithm for planning trajectories in a two-dimensional environment with obstacles on the class of piecewise-broken trajectories], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2023, No. 5 (235), pp. 34-48.
10. Kostyukov Vladimir, Medvedev Mikhail, Pshikhopov Viacheslav. Global Path Planning Algorithm in a Two-Dimensional Environment with Polygonal Obstacles on the Class of Piecewise Polygonal Trajecto-ries, Unmanned Systems, 2025. DOI: 10.1142/S2301385025500438.
11. Han-Pang Huang, Shu-Yun Chung. Dynamic visibility graph for path planning, IEEE-RSJ intern. conf. on intelligent robots and systems: IROS 2004 (Sendai, Japan, Sept. 28 - Oct. 2, 2004): Proc. N.Y.: IEEE, 2004, Vol. 3, pp. 2813-2818. DOI: 10.1109/IROS.2004.1389835.
12. Janet J.A., Luo R.C., Kay M.G. The essential visibility graph: An approach to global motion planning for autonomous mobile robots, IEEE International Conference on Robotics and Automation. Nagoya, Ja-pan, 1995, 2, pp. 1958-1963.
13. Zhaoying Li, Zhao Zhang, Hao Liu, Liang Yang. A new path planning method based on concave poly-gon convex decomposition and artificial bee colony algorithm, International Journal of Advanced Robot-ic Systems, 2020, pp. 1-15.
14. Habib M.K., Asama H. Efficient method to generate collision free paths for an autonomous mobile robot based on new free space structuring approach, IEEE/RSJ intern. workshop on intelligent robots and sys-tems: IROS'91 (Osaka, Japan, November 3-5, 1991): Proc. Vol. 2. N.Y.: IEEE, 1991, pp. 563-567. DOI: 10.1109/IROS.1991.174534.
15. Yufka A., Parlaktuna O. Performance comparison of the BUG’s algorithms for mobile robots, Proc. of International Symposium on Innovations in Intelligent Systems and Applications, Trabzon, Turkey, 2009, pp. 416-421.
16. Ng J., Braunl T. Performance comparison of bug navigation algorithms, Journal of Intelligent and Ro-botic Systems, 2007, 50(1), pp. 73-84.
17. Korepanov V.O., Novikov D.A. Zadacha o diffuznoy bombe [The problem of a diffuse bomb], Problemy upravleniya [Problems of Control], 2011, Vol. 5, pp. 66-73.
18. Kostyukov V.A., Medvedev M.Yu., Pshikhopov V.Kh. Protsedura optimizatsii traektorii mobil'nogo robota v pole istochnikov-repellerov [Procedure for optimizing the trajectory of a mobile robot in a field of source-repellers], Tr. SPIIRAN [Proceedings of SPIIRAS], 2021, Vol. 20(3), pp. 690-726 (Scopus, Web of Science Core Collection).
19. Rvachev V.L. Teoriya R-funktsiy i ee prilozheniya [Theory of R-functions and its applications]. Kiev: Naukova Dumka, 1982, 552 p.
20. Kostyukov V., Medvedev M., Pshikhopov V. A Probabilistic Functional-Based Trajectory Planning Meth-od in an Environment with Obstacles and Hazardous Areas, Unmanned Systems, 2025,
Vol. 12(3), pp. 1-22. DOI: https://doi.org/10.1142/S230138502750049X (Scopus, WoS, Q1).
21. Chou G. et al. Emergency evacuation paths for tank farm fires based on bi-objective dynamic planning, Rep., 2025, 15 8887. Available at: https://doi.org/10.1038/s41598-025-93567-4.
22. Fire Protection Association. Fire Safety and Risk Management: for the NEBOSH National Certificate in Fire Safety and Risk Management. 1st ed. Routledge, 2014. Available at: https://doi.org/10.4324/ 9781315858715.
