Планирование пути в реальном времени

Эти методы отличаются, например, от робота-пылесоса Roomba, который способен реагировать на динамические препятствия, но не имеет заданной цели. Более показательный пример — Embark — автономные грузовики, которые имеют заданную конечную точку и способны адаптироваться к изменяющимся условиям окружающей среды.

Цели алгоритмов планирования пути не ограничиваются только координатами в пространстве: иногда требуется составить план для изменения позы неподвижного робота. Например, различные манипуляторы используют планирование пути для изменения позы без столкновения с собственными частями^[2].

Являясь подмножеством задач планирования движения, планирование пути в реальном времени является важной частью робототехники, так как позволяет находить оптимальный путь к цели. Эта способность важна также для других областей, например, для видеоигр и анализа генетических последовательностей.

Для создания пути от начальной точки к целевой необходимо классифицировать зоны в симулированной среде. Это позволяет строить путь в двумерном или трёхмерном пространстве с учётом возможности обхода препятствий.

В основе планирования пути лежит разделение пространства на несколько ключевых типов:

• Рабочее пространство (Workspace) — физическое, как правило, трёхмерное пространство, в котором находится и перемещается робот.
• Пространство конфигураций (Configuration Space, C-space) — абстрактное многомерное пространство, где каждая точка соответствует уникальной конфигурации (положению и ориентации) робота. В C-пространстве робот представляется точкой, а препятствия «раздуваются» с учётом его геометрии^[3].
• Свободное пространство (Free Space) — подмножество пространства конфигураций, где робот не сталкивается с препятствиями.
• Пространство препятствий (Obstacle Space) — подмножество, где происходит столкновение.

Задача планирования в классической постановке сводится к нахождению непрерывной траектории для точки-робота из начальной в целевую конфигурацию в пределах свободного пространства. Современные подходы выходят за рамки этого бинарного деления, обогащая классические концепции многослойными и осмысленными моделями пространства.

Семантическое обогащение пространства добавляет к геометрической карте слой «смысла». Робот не просто видит препятствие, а понимает, что это за объект или тип поверхности. Семантические карты (Semantic Maps) представляют собой многослойные модели, где на традиционную карту накладывается информация о семантических классах объектов: «дорога», «трава», «стол»^[4]. Это позволяет роботу принимать более осмысленные решения, например, двигаться по газону, но с большим «штрафом», чем по асфальту. Такой подход также способствует иерархическому планированию, где сначала строится высокоуровневый план («проехать через дверь в коридор»), а затем он детализируется в точный геометрический путь^[5]. Развитие получило и метрико-семантическое картирование, объединяющее точную геометрию среды с семантическими метками^[6].

Детальный анализ проходимости (Traversability Analysis) заменяет бинарную классификацию на непрерывную шкалу «стоимости» или «риска» передвижения. Стоимость проезда по участку определяется не только геометрией, но и на основе реальных данных об энергопотреблении, вибрации или проскальзывании робота на разных типах местности^[7]. Для шагающих роботов появилась концепция анализа разрушаемости (collapsibility) грунта: робот может физически «прощупывать» подозрительные участки (например, кучи листьев), чтобы определить, выдержит ли поверхность его вес, и добавить эту информацию на карту проходимости^[8].

В методах обучения с подкреплением (Reinforcement Learning, RL) представление пространства часто является неявным. Вместо построения явной карты агент изучает ценность (value) или оптимальную политику (policy) для каждого состояния. Например, нейронные потенциальные поля используют нейронные сети для создания более точных потенциальных полей, которые учитывают сложную кинематику робота и формируют гладкое и безопасное представление «опасных» и «свободных» зон^[9].

Рабочее пространство — это окружающая среда, содержащая робота и различные препятствия. Эта среда может быть как двумерной, так и трёхмерной^[10].

Конфигурация робота определяется его положением и позой. Пространство конфигураций — это множество всех возможных конфигураций робота. Содержа в себе все возможные состояния, оно также характеризует все преобразования, которые могут быть выполнены с роботом^[10].

Внутри пространства конфигураций алгоритмы выделяют дополнительные подмножества:

Свободное пространство — это множество всех конфигураций, в которых робот не сталкивается с препятствиями^[11].

Целевое пространство — это конфигурация, которую требуется достичь роботу.

Пространство препятствий — множество конфигураций, которые недоступны для движения робота.

Опасное пространство — множество конфигураций, через которые робот может пройти, но нежелательно. Обычно роботы избегают этих зон, если есть альтернативные пути или не ограничено время. Например, робот не захочет пройти через огонь, если есть возможность обойти его^[11].

Глобальное планирование пути подразумевает применение методов, которые требуют предварительных знаний об окружающей среде робота. Используя такую информацию, создаётся симулированная среда, в которой строится путь^[12].

После 2019 года в глобальном планировании наблюдается смещение акцента в сторону алгоритмов на основе искусственного интеллекта, способных эффективно работать в сложных и динамичных средах.

Наиболее значимой тенденцией стало применение глубокого обучения с подкреплением (Deep Reinforcement Learning, DRL), которое объединяет глубокое обучение для обработки сенсорных данных и обучение с подкреплением, где робот учится на основе «наград» и «штрафов»^[13]. DRL-методы позволяют роботам адаптироваться к неопределённым условиям в реальном времени и после обучения могут требовать меньше вычислительных ресурсов, чем традиционные алгоритмы^[14]. К популярным алгоритмам относятся Deep Q-Networks (DQN), Proximal Policy Optimization (PPO) и Soft Actor-Critic (SAC)^[13]. Тем не менее, они могут требовать длительного периода обучения и не всегда достигают необходимой точности для особо сложных задач^[14].

Помимо DRL, применяются и другие архитектуры нейронных сетей. Сети Хопфилда используются для построения гладких траекторий для групп роботов^[15], а свёрточные нейронные сети (CNN) — для обработки визуальных данных и идентификации препятствий^[16]. Также машинное обучение применяется для оценки проходимости рельефа, что позволяет роботу использовать полученные знания для ускорения поиска пути^[17].

Для преодоления недостатков отдельных подходов активно развиваются гибридные методы, комбинирующие классические и интеллектуальные алгоритмы^[18]. Примером может служить система, где улучшенный алгоритм A* используется для глобального планирования, а Q-обучение (разновидность обучения с подкреплением) — для локальной корректировки пути и обхода внезапных препятствий^[19].

Одновременно продолжается совершенствование традиционных подходов. Развиваются оптимизационные алгоритмы, такие как смешанное целочисленное линейное программирование (MILP), позволяющие находить гладкие и физически выполнимые пути с учётом динамических ограничений робота^[20]. Также предлагаются новые алгоритмы исследования, направленные на сокращение времени и пройденного расстояния в неизвестной среде^[21], и улучшаются сэмплирующие методы, например, RRT^[19].

Метод быстро растущих случайных деревьев (англ. Rapidly-exploring random tree, RRT) заключается в исследовании пространства конфигураций путём построения дерева из случайно выбираемых точек. Проходя через последовательности состояний, алгоритм строит путь от начальной конфигурации к целевой^[22].

После 2019 года развитие метода было сосредоточено на повышении его эффективности, оптимальности и адаптивности, особенно в сложных и динамических средах. Основные исследования направлены на улучшение стратегий выборки, создание гибридных алгоритмов и оптимизацию существующих вариантов, таких как RRT*^[23].

Улучшение стратегий выборки. Основной недостаток классического RRT — «слепая» случайная выборка, которая замедляет поиск оптимального пути. Современные подходы делают выборку более «умной». К ним относятся информированная выборка (англ. Informed Sampling), которая сужает область поиска на основе уже найденного решения^[24], и методы, использующие обратную связь от столкновений для корректировки последующих выборок^[25].

Гибридные алгоритмы. Для компенсации недостатков RRT его всё чаще комбинируют с другими методами. Например, RRT объединяют с методом искусственных потенциальных полей (APF) для эффективного локального обхода препятствий^[24]. Другой пример — алгоритм Informed-TRRT (2024 г.), который использует Theta* для быстрого нахождения первоначального пути, что значительно ускоряет сходимость RRT* к оптимальному решению^[26].

Улучшение сходимости и оптимальности. Ведётся работа над ускорением сходимости RRT* к оптимальному решению. Для этого применяются двунаправленный поиск (построение деревьев от начальной и целевой точек одновременно)^[24], оптимизация структуры дерева с помощью новых техник переподключения узлов (англ. rewiring) и «обрезки» (англ. pruning) избыточных ветвей^[26]. Алгоритмы, такие как F-RRT* (2021 г.), фокусируются на генерации более качественного начального пути, что также ускоряет общую сходимость^[26].

Локальное планирование пути использует поступающую в реальном времени информацию для формирования симулированного поля, в котором ищется путь. Такие методы позволяют находить маршруты с учётом динамических изменений среды.

После 2013 года развитие локальных методов ознаменовалось переходом от классических реактивных подходов к более сложным предиктивным, оптимизационным и обучаемым системам. Новые алгоритмы стремятся не просто избегать препятствий, а строить оптимальные, плавные и кинематически выполнимые траектории. Ключевым направлением стали оптимизационные методы, рассматривающие задачу как многокритериальную проблему. К ним относятся Timed Elastic Band (TEB) — популярный в ROS метод, представляющий локальный путь как «эластичную ленту» из последовательности поз робота^[27]. Алгоритм в реальном времени оптимизирует форму «ленты», учитывая кинодинамические ограничения (скорость, ускорение) и стараясь увеличить зазор до препятствий^[28]. Его дальнейшим развитием является Resilient TEB (RTEB), повышающий надёжность в загромождённых пространствах^[29]. Другой подход — модельно-предиктивное управление (MPC) — использует динамическую модель робота для предсказания его будущего поведения на коротком временном горизонте. На каждом шаге MPC решает задачу оптимизации для поиска наилучшей последовательности управляющих воздействий, минимизируя отклонение от глобального пути и близость к препятствиям^[30]. Способность «заглядывать в будущее» позволяет MPC эффективно справляться с движущимися препятствиями и генерировать более плавные траектории^[31].

Активное внедрение получили методы на основе машинного обучения. Обучение с подкреплением (RL) стало одним из ведущих направлений^[32]. В рамках этого подхода робот учится принимать оптимальные решения методом проб и ошибок. Алгоритмы глубокого обучения с подкреплением (DRL), такие как DQN и DDPG, позволяют обучать нейронную сеть, которая напрямую преобразует данные с сенсоров в управляющие команды, что даёт возможность адаптироваться к неизвестным и динамичным средам без явного программирования правил^[33][34]. Помимо RL, нейронные сети используются для вычисления более сложных полей рисков вокруг препятствий (нейронные потенциальные поля), которые затем применяются в оптимизационных планировщиках.

Продолжается и совершенствование классических подходов. Например, для решения проблемы локальных минимумов метод искусственных потенциальных полей (APF) комбинируют с MPC или RL^[35]. Также развиваются методы сглаживания траекторий на основе криволинейных систем координат (координат Френе)^[36]. Современная тенденция заключается в создании гибридных систем, объединяющих глобальное планирование с продвинутыми локальными планировщиками.

Метод вероятностных дорожных карт (англ. Probabilistic Roadmap, PRM) соединяет близкие конфигурации для построения пути от начальной к целевой. Работа метода разделена на две фазы: фазу предобработки и фазу запросов. На первом этапе в пространстве конфигураций генерируется набор случайных точек (конфигураций), которые проверяются на столкновения. Затем эти точки соединяются рёбрами, если между ними существует простой, свободный от столкновений путь. На второй фазе, при поступлении запроса на планирование, начальная и целевая конфигурации подключаются к построенной карте, после чего для поиска оптимального маршрута в графе используется алгоритм Дейкстры или A*^[37].

После 2016 года развитие метода было сосредоточено на преодолении его основного недостатка — медленной фазы предварительной обработки, которая делает классический PRM неэффективным в динамических средах с движущимися препятствиями^[38]. Современные подходы фокусируются на быстрой адаптации дорожной карты вместо её полного перестроения^[39]. Ключевые стратегии и новые варианты метода:

• Адаптация и обновление карты. Вместо полного перестроения карты современные подходы фокусируются на её быстром обновлении. Концепция динамических дорожных карт (англ. Dynamic Roadmaps, DRM) предполагает быструю корректировку заранее построенной карты путём определения и временного исключения участков, затронутых новыми препятствиями^[39]. Фундаментальным для систем реального времени стал подход «ленивой» оценки (англ. Lazy PRM), при котором трудоёмкая проверка столкновений откладывается до момента, когда потенциальный путь уже найден в графе^[40]. Его усовершенствованные версии, такие как EIRM, минимизируют вычисления за счёт повторного использования ранее проверенной информации о путях^[41].
• Временное измерение: Temporal PRM (T-PRM). Значительным нововведением стал метод англ. T-PRM, представленный в 2022 году^[42]. Он добавляет к карте временное измерение, строя граф в четырёхмерном пространстве (координаты + время), что позволяет планировать траектории, избегающие столкновений с движущимися объектами путём прогнозирования их положения^[38].
• Улучшенные стратегии выборки: OP-PRM. Для повышения эффективности в сложных пространствах, например, в узких коридорах, был предложен метод англ. OP-PRM (англ. Obstacle Potential field-Probabilistic Roadmap Method). Он использует потенциальное поле препятствий для генерации большего числа «полезных» точек выборки в критически важных областях^[43].
• Аппаратное ускорение. Существенный прирост производительности достигается за счёт аппаратного ускорения: использование GPU и SIMD-инструкций позволяет ускорить ключевые компоненты планировщика (включая проверку столкновений) более чем в 500 раз, делая даже сложные варианты PRM применимыми для задач реального времени^[44].
• Гибридные подходы. Развиваются гибридные методы, объединяющие PRM с искусственным интеллектом, в частности с обучением с подкреплением, для достижения большей адаптивности^[45].

Метод эволюционного искусственного потенциального поля сводится к использованию смеси искусственных отталкивающих и притягивающих сил для построения пути. Притягивающие силы исходят от цели, направляя к ней, а отталкивающие — от препятствий. Такой подход позволяет находить оптимальные траектории движения^[46].

Метод индикативного маршрута использует управляющий путь к цели и точку притяжения, расположенную на целевой позиции. Для построения управляющего пути часто применяются алгоритмы, обеспечивающие минимальное расстояние до препятствий. Следуя по управляющему пути, робот движется к цели, ориентируясь на точку притяжения^[47].

После 2010 года развитие метода индикативного маршрута (англ. Indicative Route Method, IRM) было сосредоточено на повышении реалистичности и адаптивности движения виртуальных агентов^[48]. Ключевым достижением стала разработка его усовершенствованной версии — модифицированных индикативных маршрутов и навигации (англ. Modified Indicative Routes and Navigation, MIRAN), представленной в 2013 году исследователями из Утрехтского университета. Главным нововведением MIRAN стала способность работать в неоднородных средах, позволяя назначать различным областям (например, тротуар, газон) веса, соответствующие «стоимости» или «предпочтительности» передвижения. Кроме того, метод исправил недостаток оригинального IRM, при котором агенты могли «срезать углы» и пропускать значительные участки маршрута в открытых пространствах.

Исследования в области IRM и MIRAN легли в основу коммерческого продукта. В 2018 году один из ключевых авторов метода, профессор Роланд Герартс, основал компанию uCrowds как ответвление Утрехтского университета^[49]. Компания разработала одноимённое программное обеспечение для высокопроизводительного моделирования толпы, которое применяется в городском планировании, симуляторах для экстренных служб и компьютерных играх. В архитектуре uCrowds индикативный маршрут остаётся центральным элементом для определения глобального пути агентов, управляя поведением десятков тысяч виртуальных персонажей в реальном времени с учётом их индивидуальных целей и предпочтений к типам местности^[50].

Метод модифицированных индикативных маршрутов и навигации (англ. Modified Indicative Routes and Navigation, MIRAN) был представлен в 2013 году исследователями из Утрехтского университета как усовершенствованная версия метода IRM^[51]. Главным нововведением MIRAN стала способность работать в неоднородных (гетерогенных) средах. Метод позволяет назначать различным областям карты (например, тротуар, газон) веса, соответствующие «стоимости» или «предпочтительности» передвижения. Таким образом, агент будет стремиться двигаться по маршруту с наименьшей стоимостью (например, по тротуару), но сможет пересечь область с большим весом (газон), если это необходимо, при этом его итоговый путь будет выглядеть естественно и логично^[51].

Кроме того, MIRAN исправил недостаток оригинального IRM, при котором агенты могли «срезать углы» и пропускать значительные участки заданного маршрута в широких открытых пространствах. Модифицированный алгоритм обеспечивает более точное следование индикативному маршруту, делая поведение более предсказуемым и управляемым^[51]. В результате метод создаёт плавные, визуально убедительные траектории, которые поддерживают безопасное расстояние до препятствий и избегают резких поворотов^[51].

Методы машинного обучения и искусственного интеллекта (ИИ) стали центральным элементом современного планирования пути, ознаменовав переход от жёстко запрограммированных правил к системам, способным обучаться на основе данных и опыта. Это позволяет роботам эффективно и безопасно действовать в сложных, динамичных и непредсказуемых средах.

Ключевым направлением стало обучение с подкреплением (RL), в рамках которого робот (агент) учится навигации методом проб и ошибок, получая «вознаграждение» за успешные действия^[52]. Наибольшее развитие получило глубокое обучение с подкреплением (DRL), где глубокие нейронные сети используются для обработки необработанных сенсорных данных (например, с лидара или камеры) и принятия решений о дальнейших действиях^[53]. Алгоритмы, такие как Deep Q-Networks (DQN), Proximal Policy Optimization (PPO) и Soft Actor-Critic (SAC), позволяют роботам адаптироваться к неизвестным условиям без явного программирования правил, хотя и могут требовать длительного периода обучения в симулированной среде^[54].

Помимо DRL, нейронные сети применяются и для других задач:

• Обработка сенсорных данных: Свёрточные нейронные сети (CNN) используются для идентификации препятствий и проходимых участков по изображениям с камер.
• Построение гладких траекторий: Сети Хопфилда применяются для планирования путей для групп роботов.
• Оценка рисков: Нейросети используются для создания нейронных потенциальных полей — более сложных и точных представлений «опасных» зон вокруг препятствий, учитывающих кинематику робота. Алгоритм Fastron использует машинное обучение для моделирования безопасного пространства движений, что ускоряет проверку на столкновения до 8 раз^[55].

На практике часто используются гибридные подходы, объединяющие сильные стороны классических и интеллектуальных методов. Например, глобальный маршрут может быть построен с помощью алгоритма A*, а локальная корректировка пути для обхода внезапных препятствий выполняется с помощью агента, обученного с подкреплением (например, на основе Q-learning).

Применение ИИ позволило развить новые концепции, такие как:

• Социально-ориентированная навигация, где робот учитывает не только физические препятствия, но и социальные нормы, стараясь двигаться предсказуемо и не создавать дискомфорта для людей.
• Обучение оценке проходимости, когда робот на основе полученного опыта учится определять сложность рельефа и использовать эти знания для ускорения поиска пути.

Высокая вычислительная стоимость планирования пути, особенно на этапе проверки столкновений, привела к развитию аппаратных решений, направленных на ускорение этих задач.

Одним из ключевых направлений стало создание специализированных процессоров. Компания Realtime Robotics, основанная на исследованиях Университета Дьюка, разработала процессор (изначально на базе FPGA, затем ASIC), предназначенный для ускорения планирования движения^[56]. Он выполняет проверку на столкновения в сотни и тысячи раз быстрее, чем универсальные процессоры^[57]. Это позволяет промышленным роботам, работающим в группе, мгновенно перепланировать свои траектории при появлении препятствий, избегая простоев и столкновений^[58].

Помимо специализированных чипов, активно используются и параллельные вычисления на стандартном оборудовании. Применение графических процессоров (GPU) и SIMD-инструкций позволяет ускорить ключевые компоненты планировщика, включая проверку столкновений, более чем в 500 раз. Это делает вычислительно-ёмкие алгоритмы, такие как PRM, применимыми для задач реального времени.

Другой подход заключается в создании алгоритмов, оптимизированных для аппаратного выполнения. Примером является алгоритм Fastron, разработанный в Калифорнийском университете в Сан-Диего. Он использует машинное обучение для моделирования безопасного пространства движений робота и работает до 8 раз быстрее аналогов, что критически важно для коллаборативных и хирургических роботов.

Для большинства роботов число степеней свободы не превышает трёх. Гуманоидные роботы же имеют сравнимое с человеческим телом количество степеней свободы, что значительно усложняет задачу планирования пути. Например, одна «нога» такого робота может иметь около 12 степеней свободы. Основная сложность заключается в высокой вероятности самопересечения деталей. Реализация планирования пути в реальном времени позволяет гуманоидным роботам координировать работу разных частей без аварийных столкновений^[59].

Например, человеческая рука может соприкасаться с плечом, но для робота это может привести к столкновению звеньев. Алгоритмы планирования пути необходимы для предотвращения таких ошибок.

Эта же проблема безопасности и адаптивности является ключевой для коллаборативных роботов (коботов), предназначенных для работы в непосредственной близости от человека без защитных ограждений^[60]. Такие роботы, применяемые для сборки, упаковки и контроля качества, используют динамическое планирование траектории, постоянно корректируя свой путь для предотвращения столкновений с человеком^[61].

Особое значение планирование в реальном времени приобретает в медицине. Примером является использование коботов для биопечати in situ — нанесения биоматериалов непосредственно на рану во время операции^[62]. В этом случае робот должен планировать траекторию движения печатающей головки вдоль сложной криволинейной поверхности живой ткани^[62]. Высокоскоростные алгоритмы обнаружения столкновений, такие как Fastron, критически важны для безопасности как коллаборативных, так и хирургических роботов, например, da Vinci^[55].

Беспилотные транспортные средства — разновидность мобильных роботов, использующих планирование пути в реальном времени. Обычно они вначале используют глобальное планирование для выбора маршрута на дорогах, а затем вынуждены постоянно корректировать его в зависимости от изменений в обстановке. Здесь применяются локальные методы, позволяющие динамически оптимизировать траекторию^[63].

Развитие автономного транспорта также связано с созданием специализированной инфраструктуры. Например, в России к 2026 году планируется развернуть для беспилотных автомобилей «Яндекса» сеть высокоточного позиционирования на базе технологии GNSS RTK. Эта система покроет тысячи километров федеральных трасс (М-4 «Дон», М-11 «Нева», М-12 «Восток») и обеспечит определение местоположения автомобиля с точностью до нескольких сантиметров. Внедрение интеллектуальных транспортных систем (ИТС) также является частью государственных программ, направленных на развитие беспилотного движения в городских агломерациях^[64].

Планирование пути в реальном времени является ключевой технологией для автономных беспилотных летательных аппаратов (БПЛА), или дронов. Искусственный интеллект используется для обхода препятствий, оптимизации маршрута и адаптации к погодным условиям^[65]. Разработаны системы, позволяющие дронам ориентироваться в условиях отсутствия сигнала GPS по визуальным ориентирам на местности (здания, дороги), сопоставляя изображения с камеры с имеющейся картой^[66]. Особое развитие получили алгоритмы управления роем дронов, которые позволяют группе аппаратов адаптироваться к динамичным условиям, избегать столкновений друг с другом и с неизвестными препятствиями, учитывая даже аэродинамические помехи от соседних дронов^[67]. Такие технологии применяются для мониторинга, аэрофотосъёмки, логистики и создания световых шоу^[68].

Во многих видеоиграх имеются различные неигровые персонажи, перемещающиеся по игровому миру и требующие планирования траекторий. Необходимо прокладывать путь для таких персонажей, чтобы они знали, куда и как двигаться.

Например, в игре Minecraft враждебные мобы выслеживают игрока, обходя препятствия. Если игрок добавляет препятствия, алгоритм пересчитывает путь, чтобы догнать цель.