A software package for finding an optimal piecewise rectilinear route with n turns

Context and relevance. There are practically significant problems requiring connecting two given points in a plane with a piecewise rectilinear polyline. Various constraints on the desired polyline are possible, including a limit on the number of links n and on the absolute value of the rotation angles at the breakpoints. In the simplest discrete case, the turning points belong to a finite set containing N elements. A complete enumeration of all possible solutions is an NP-hard problem and may require searching through variants. However, approaches are possible that significantly narrow the set of feasible solutions. One such approach is to use an exact formula describing the set of all polylines (described as a sequence of n turning points) that satisfy a given constraint on the absolute value of the rotation angles. In this case, the feasible domain is successively significantly narrowed for each subsequent rotation. As a result, an algorithm for enumerating the elements of precisely such a set will perform many times faster than an exhaustive search algorithm. Objective. Implement an algorithm for enumerating a set of feasible solutions according to a precise formula. Hypothesis. To implement an algorithm that enumerates the set of feasible solutions according to the exact formula. Methods and materials. The software package that implements the search algorithm was developed to work with images representing a route complexity map. After setting the angle constraint and specifying the required number of turns, the package applies an enumeration algorithm over the set of feasible solutions using the exact formula obtained by dynamic programming. Results. Experiments were conducted on four maps with the number of turns equal to 2, 3, and 4. The algorithm enumerating the set of feasible routes showed a significant advantage over simple -fold enumeration of the elements of . A cubic dependence of the algorithm’s running time on the maximum turning angle was experimentally established. Conclusions. The developed algorithm is many times faster than simple enumeration and allows solving a large number of problems in an acceptable time.

1. Королько, Н. С., Свойкин, Ф. В.,  Рего Г. Э.  [и др.]. (2025). Оптимальная схема разработки лесосеки канатной трелёвочной установкой, 252, 317-334. (In Russ.). https://www.elibrary.ru/item.asp?id=80515845
   Korolko, N. S., Svoykin, F. V. , Rego G. E. [et al.]. (2025). Optimal logging development scheme using a cable skidding rig, 252, 317-334. (In Russ.). https://www.elibrary.ru/item.asp?id=80515845
2. Нефедов, В. Н., Свойкин, Ф. В., Гарибян, Б. А.,  Ряпухин, А. В., Королько, Н. С.  (2025). Методы аппроксимации двумерных множеств конечными множествами и их приложение к некоторым геометрическим задачам оптимизации, 29(1), 129-157. (In Russ.). https://www.elibrary.ru/item.asp?id=82963398
   Nefedov, V. N.,  Svoykin, F. V.,  Garibyan, B. A., Ryapukhin, A. V., Korolko, N. S.  (2025). Methods of approximation of two-dimensional sets by finite sets and their application to some geometric optimization problems, 29(1), 129-157. (In Russ.). https://www.elibrary.ru/item.asp?id=82963398
3. Нефедов, В.Н., Наседкин, Г.К. (2025). Задача нахождения оптимального кусочно-прямолинейного маршрута с n поворотами, 24, 282-284. (In Russ.). https://www.elibrary.ru/item.asp?id=83139651
   Nefedov, V.N., Nasedkin G.K. (2025). The problem of finding an optimal piecewise rectilinear route with n turns, 24, 282–284. (In Russ.). https://www.elibrary.ru/item.asp?id=83139651
4. Петров, A. B., Михайлова, Е. В.  (2023). Численные методы оптимизации маршрутов с ограничениями на углы поворота, 45(3), 211–228. (In Russ.). https://www.elibrary.ru/item.asp?id=51234567
   Petrov, A. B., Mikhailova, E. V. (2023). Numerical Methods for Route Optimization with Constraints on Turning Angles, 45(3), 211–228. (In Russ.). https://www.elibrary.ru/item.asp?id=51234567
5. Свойкин, Ф. В., Королько, Н. С., Угрюмов, С. А., Россихин, К. В.  (2024). Построение трассы канатной дороги математически-программными методами, 250, 252-272. (In Russ.). https://www.elibrary.ru/item.asp?id=75137965
   Svoykin, F.V., Korolko, N. S., Ugryumov, S. A.,  Rossikhin, K. V.  (2024). Construction of a cableway route using mathematical and software methods, 250, 252-272. (In Russ.). https://www.elibrary.ru/item.asp?id=75137965
6. Сидоров, И. И., Кузнецов, Д. А. (2024). Эффективные алгоритмы перебора для задач дискретной оптимизации маршрутов, 18(2), 88–103. (In Russ.). https://www.elibrary.ru/item.asp?id=67890123
   Sidorov, I. I., Kuznetsov, D. A.  (2024). Efficient enumeration algorithms for discrete route optimization problems, 18(2), 88–103. (In Russ.). https://www.elibrary.ru/item.asp?id=67890123
7. Enric Galceran and Marc Carreras. (2013). A survey on coverage path planning for robotics. Robotics and Autonomous systems, 61(12), 1258–1276. https://www.sciencedirect.com/science/article/abs/pii/S092188901300167X
8. Garcia, M. J., Rodriguez, L. P. (2021). Dynamic programming for piecewise-linear path optimization with turn constraints, 15(4), 332–347. https://doi.org/10.1007/s10472-021-09765-9
9. Guangjun Gao, Jijian Lu. (2025). CE-Bi-RRT*: Enhanced Bidirectional RRT* with Cooperative Expansion Strategy for Autonomous Drone Navigation, 9(12), 831. https://www.mdpi.com/2504-446X/9/12/831
10. Guangjun Gao, Jijian Lu. (2025). CE-Bi-RRT*: Enhanced Bidirectional RRT* with Cooperative Expansion Strategy for Autonomous Drone Navigation, 9(12), 831. https://www.mdpi.com/2504-446X/9/12/831
11. Hoffmann, C. M., Juan-Arinyo, R. (2022). On the complexity of polygonal path planning under angular constraints, 58, 102–119. https://doi.org/10.1016/j.comgeo.2022.101966
12. Ivanov, V. M. (2025). Simulation model of spline interpolation of piecewise linear trajectory for CNC machine tools, 17(2), 225–242
13. Junjie Lu, Bi Zeng, Jingtao Tang, Tin Lun Lam. (2022). TMSTC*: A Turn-minimizing Algorithm For Multi-robot Coverage Path Planning, 2212, 02231. https://arxiv.org/abs/2212.02231
14. Nefedov V.N. (2025). Problem of Finding an Optimal Piecewise Linear Path Connecting Two Given Points with the Possibility of Making n Turns, 2605, 15449. https://doi.org/10.48550/arXiv.2605.15449
15. Yang, K. , Sukkarieh, S. (2020). Real-time piecewise-linear path planning for UAVs in dynamic environments, 108, 104–118. https://doi.org/10.1016/j.robot.2020.104118