Робототехника является одной из наиболее активно развивающихся областей науки и техники в настоящее время. При этом фокус специалистов в этой области смещается от создания телеуправляемых систем к разработке роботов, способных функционировать автономно. Такое автономное функционирование невозможно без обеспечения самостоятельной навигации мобильного робота, т.е. возможности перемещения из одного положения в другое. Известно множество подходов к автоматизации навигации, один из которых заключается в построении т.н. опорной траектории и следования вдоль неё. При этом входными данными для планирования траектории зачастую выступают карты занятости (occupancy maps), которые являются графами регулярной декомпозиции, вложенными в метрическое пространство. Соответственно задача построения опорной траектории сводится к задаче поиска пути на таких графах. Методы и алгоритмы поиска пути при этом должны учитывать различные ограничения, возникающие из контекста задачи. Среди них можно отметить: необходимость учета прогнозной динамики окружающей среды (выражающейся в динамическом изменении проходимости вершин и ребер графа), косвенный учет кинематических ограничений робота (для того, чтобы следование вдоль построенной траектории было безопасным), поддержка много-агентного сценария (когда опорные траектории необходимо спланировать для группы роботов, действующих кооперативно в общем пространстве), повышенные требования к вычислительной эффективности алгоритмов поиска. Для решения задач планирования, учитывающих вышеуказанные ограничения, был разработан ряд оригинальных методов и алгоритмов, о которых и пойдёт речь в докладе.
Watch presentation at the official RuTube channel (in Russian):
Konstantin Yakovlev. Heuristic Search Methods on Special Graph Structures and Their Application in Trajectory Planning // Problems of Artificial Intelligence seminar (Moscow, December 24, 2025).