Планирование пути (path planning) — это расчёт маршрута робота от текущего положения до цели. Зная карту окружения и своё место на ней, робот должен проложить траекторию, которая приведёт его в нужную точку, не задев препятствий. Планирование пути — одна из ключевых задач навигации: без неё робот знал бы, где он и куда надо, но не знал бы, как туда добраться.

Обычно задача сводится к поиску пути на карте, где отмечены препятствия (непроходимые зоны) и свободное пространство. Пространство представляют в удобном для расчёта виде (например, разбивают на ячейки-сетку или строят граф проходимых точек), после чего применяют алгоритмы поиска маршрута. Наиболее известные:

  • A* (A-star) — классический оптимальный алгоритм поиска кратчайшего пути по графу; использует эвристику (например, расстояние до цели), чтобы искать быстрее. Его частный случай — алгоритм Дейкстры.
  • RRT (быстрорастущие случайные деревья) — строит маршрут, случайно «прорастая» дерево путей в пространстве; хорошо работает для сложных конфигураций и манипуляторов.
  • D* и другие — умеют перепланировать маршрут «на лету» при появлении новых препятствий.

Планирование принято делить на два уровня. Глобальное планирование строит общий маршрут по заранее известной карте (например, от склада к точке выгрузки). Локальное планирование корректирует движение в реальном времени по данным датчиков — объезжает препятствия, которых не было на карте, и сглаживает траекторию. На практике эти уровни комбинируют: глобальный планировщик задаёт «куда двигаться в целом», локальный — «как проехать прямо сейчас».

Планирование пути применяют и для мобильных роботов (маршрут по помещению или местности), и для манипуляторов (траектория движения «руки», чтобы не задеть препятствия и себя). Оно тесно связано с локализацией и картографированием: чтобы проложить путь, нужно знать карту и своё положение на ней. Хороший планировщик ищет не любой, а оптимальный маршрут — короткий, быстрый и безопасный.

Источники:

  1. Задача планирования движения // Университет ИТМО, Wiki кафедры КТ. URL:https://neerc.ifmo.ru/wiki/index.php?title=Задача_планирования_движения
  2. Автономная навигация мобильных роботов // НТИ Up Great. URL:https://upgreat.one/media-center/knowledge/avtonomnaya-navigatsiya-mobilnykh-robotov