Ученые из Московского авиационного института и Самарского государственного технического университета нашли способ математически описать все возможные маршруты, которые соединяют две точки на плоскости и состоят из отрезков прямых линий с заданным числом поворотов. Речь идет о траекториях, где в каждой точке излома угол поворота не превышает определенную величину, причем общее число таких поворотов ограничено так, что суммарный разворот не может составить полный круг.
Эта задача далеко не умозрительна. Представьте себе беспилотный автомобиль, который не может развернуться на месте, или робота-курьера, чья конструкция не позволяет делать резкие движения. Траектория прокладки инженерных коммуникаций, проектирование дорожных сетей или построение обходных маршрутов в стесненных условиях — везде требуется не просто соединить точки, а сделать это с учетом ограничений на «крутизну» каждого поворота. Именно для таких случаев и было разработано новое математическое описание.
Главная сложность заключалась в том, чтобы понять, где вообще могут находиться все промежуточные точки такого маршрута. Оказалось, что при соблюдении условия, что сумма всех углов поворота меньше 180 градусов, все внутренние вершины ломаной обязательно попадают в строго определенную область — так называемый круговой сегмент, построенный на начальной и конечной точках маршрута. Авторы работы строго доказали, что это условие является не только необходимым, но и достаточным: если точка лежит внутри этого сегмента, то через нее гарантированно можно провести допустимую ломаную с нужным числом звеньев.
Но на этом исследователи не остановились. Они пошли дальше и получили формулу, которая описывает не просто множество отдельных точек, а все возможные последовательности таких точек — то есть полный перечень всех допустимых траекторий. Это описание имеет рекуррентный вид: каждая следующая точка поворота выбирается из множества, которое зависит от предыдущей, причем доказано, что на каждом шаге такой выбор всегда возможен и не заведет в тупик.
Практическая ценность этого результата огромна. На его основе можно строить алгоритмы для компьютерного перебора всех допустимых маршрутов, что особенно актуально при поиске оптимального пути, когда нужно минимизировать не только длину дороги, но и «стоимость» каждого поворота, например, расход топлива или время на маневр. Если же на точки маршрута наложены дополнительные ограничения, скажем, они должны лежать внутри заданной области или на координатной сетке, то предложенная формула позволяет легко учесть и эти условия, просто пересекая допустимое множество с нужным множеством.
Полученное решение значительно упрощает подход к задачам аппроксимации сложных кривых ломаными линиями с ограничениями на углы. Оно позволяет вместо сложного поиска с проверкой огромного числа вариантов использовать четкое геометрическое описание, которое гарантирует существование маршрута. В дальнейшем авторы планируют распространить свой метод на трехмерное пространство и учесть дополнительные ограничения, такие как запрет на самопересечения траектории или фиксированная длина отдельных звеньев.
Исследование опубликовано в журнале «Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика»
Изображение на обложке: разработано Magnific
