Методы эвристического поиска в задачах планирования траектории

Авторы

Яковлев К. С.

Аннотация

Задача планирования траектории естественным образом возникает во многих областях, среди которых особенно выделяется робототехника. Зачастую при планировании траектории для мобильных роботов требуется учитывать ряд ограничений, усложняющих задачу. Так, при планировании необходимо учитывать кинематические и динамические ограничения робота, динамику окружающей среды или траектории движения других роботов, если речь идёт о многоагентной постановке, и другие ограничения. Одним из универсальных подходов к учёту этих ограничений в частности и к решению задачи планирования в целом является её сведение к задаче поиска пути на графе, вершинам которого соответствуют различные конфигурации мобильного агента, а рёбрам — так называемые примитивы движения, т. е. короткие фрагменты траектории, следование по которым может быть обеспечено системой управления робота с достаточной точностью. В настоящем докладе будет рассмотрен ряд новых методов эвристического поиска пути на подобных графах, превосходящих аналоги по вычислительной эффективности и/или способных отыскивать доказуемо-оптимальные решения для классов задач, для которых ранее подобных методов не существовало. В частности, будет сделан акцент на новые методы безопасно-интервального планирования для решения задач планирования в средах с динамическими препятствиями и в многоагентных средах с централизованным планировщиком. Помимо этого, мы коснёмся вопросов геометрического планирования с косвенным учётом кинематических ограничений, а также применения современных нейросетевых моделей для автоматического получения задаче-ориентированных эвристических функций.

Внешние ссылки

Запись выступления на канале семинара «Проблемы искусственного интеллекта»:

Ссылка при цитировании

Яковлев К. С. Методы эвристического поиска в задачах планирования траектории // Совместный семинар «Проблемы искусственного интеллекта» Российской ассоциации искусственного интеллекта и Федерального исследовательского центра «Информатика и управление» Российской академии наук (Москва, Институт проблем информатики РАН, 31 мая 2023).