Метод построения быстрейших маршрутов без столкновений в среде с динамическими препятствиями

А. Л. Казаков^a, А. А. Лемперт^a, Т. В. Чан<sup>b

a</sup> Институт динамики систем и теории управления имени В.М. Матросова Сибирского отделения Российской академии наук, г. Иркутск
^b Иркутский национальный исследовательский технический университет

Аннотация: В статье рассматривается задача построения оптимальных по времени маршрутов для одного или нескольких подвижных объектов в динамической среде с препятствиями. Предлагается подход, основанный на оптико-геометрической аналогии и принципах Ферма и Гюйгенса, который сводит задачу к решению уравнения эйконала. Разработана серия алгоритмов (включая модификации метода "быстрого марша), позволяющих строить траектории без столкновений и перепланировать их при изменении обстановки. Эффективность предложенных методов подтверждена вычислительными экспериментами, и показано их превосходство по длине маршрута и времени расчета в сравнении с существующими подходами, такими как CFM, PRIMAL и DHC.

Ключевые слова: задача маршрутизации, динамическая среда, оптико-геометрический подход, уравнение эйконала, алгоритм быстрого марша.

УДК: 519.853.6, 517.958

MSC: 05B40, 52C17, 35A18

Поступила в редакцию: 15.10.2025
Исправленный вариант: 21.10.2025
Принята в печать: 27.10.2025

DOI: 10.21538/0134-4889-2025-31-4-115-131

Реферативные базы данных:

•