Heuristic Search Methods in Trajectory Planning

Authors

Yakovlev K.

Annotation

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

External links

Video at the Artificial Intelligence Problems seminar channel (in Russian):