Современная складская логистика характеризуется интенсивным внедрением средств автоматизации [3]. Ключевым элементом таких комплексов выступают автоматически управляемые тележки (AGV), обеспечивающие автономное перемещение грузов [11]. Устойчивый рост масштабов применения AGV-систем выдвигает повышенные требования к алгоритмам управления их движением.

Центральной задачей навигации AGV является планирование маршрута [1, 3]. Классические методы поиска пути, такие как алгоритм A* [9], эффективно решают данную задачу в статической среде. Однако реальный склад представляет собой динамическое пространство, в котором присутствуют движущиеся объекты: персонал, другая погрузочная техника, смежные AGV [5, 14]. Отсутствие механизмов упреждающего планирования приводит к практическим проблемам: частым остановкам робота при сближении с объектами, неэффективности маршрутов и рискам столкновений [14].

Проблематика навигации в изменяющихся средах имеет обширную теоретическую базу. Для адаптации к обновлению карты применяются инкрементальные алгоритмы перепланирования D [16] и D Lite [12]. В пространствах высокой размерности используются вероятностные методы: быстро исследующее случайное дерево (RRT — Rapidly-exploring Random Tree) [13] и вероятностная дорожная карта (PRM — Probabilistic Roadmap) [10]. Явное моделирование динамики преград реализовано в таких подходах, как препятствия в пространстве скоростей (VO) [7], оптимальный взаимный алгоритм избегания столкновений (ORCA) [17] и пространственно-временное планирование [15].

Несмотря на разнообразие методов, вопрос интеграции прогнозирования движения препятствий непосредственно в функцию стоимости глобального планировщика остаётся недостаточно проработанным [3, 14]. Большинство алгоритмов либо обладают высокой вычислительной сложностью, либо работают на реактивном уровне, либо требуют централизованной кооперации агентов, что неприменимо к неконтролируемому персоналу склада [55].

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

Задача планирования пути заключается в определении последовательности допустимых состояний, переводящих мобильного робота из начальной точки в целевую при обходе препятствий [1, 2]. В складских системах навигации рабочее пространство, как правило, представляется в виде сетки занятости (occupancy grid) — дискретного разбиения пространства на ячейки, помечаемые как свободные или занятые [1]. Данное представление обеспечивает простую интеграцию с данными систем одновременной локализации и построения карты (SLAM — Simultaneous Localization and Mapping) [3].

Алгоритм Дейкстры [2] предназначен для поиска кратчайших путей во взвешенном графе с неотрицательными весами рёбер. Алгоритм гарантирует оптимальность решения, однако не использует информации о расположении цели, что приводит к исследованию значительной части графа и снижает эффективность в задачах направленного поиска.

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

Для работы в частично известной или изменяющейся среде разработаны инкрементальные алгоритмы перепланирования D [16] и D Lite [12]. Данные методы эффективны при обновлении информации о статических препятствиях, однако не учитывают прогнозируемое движение подвижных объектов.

В пространствах высокой размерности применяются вероятностные методы планирования: быстро исследующее случайное дерево (RRT) [13] и метод вероятностных дорожных карт (PRM) [10].

Преимуществом данных подходов является хорошая масштабируемость, однако базовый RRT не гарантирует оптимальности (в отличие от его модификации RRT*, обеспечивающей асимптотическую оптимальность), а построение PRM требует значительных вычислительных ресурсов. Для плоской навигации AGV их преимущества менее выражены по сравнению с графовыми алгоритмами.

Сравнительные характеристики рассмотренных алгоритмов применительно к задаче навигации AGV в складской среде систематизированы в таблице 1.

Таблица 1

Сравнительный анализ классических алгоритмов планирования пути

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

Алгоритмы, рассмотренные выше, оперируют статическим представлением среды. В реальных складских условиях робот функционирует в окружении подвижных объектов (персонала, погрузочной техники, других AGV). Учёт динамических препятствий требует моделирования их движения и интеграции этой информации в процесс управления [14]. В зависимости от уровня принятия решений выделяют реактивные методы (выбор мгновенного управляющего воздействия) и глобальные (построение полного пути).

Метод искусственных потенциальных полей [11] основан на аналогии с физическими силами. Он обеспечивает простое реактивное управление и допускает естественное расширение на динамические препятствия: отталкивающий потенциал пересчитывается на каждом шаге с учётом текущего положения объектов.

Основным ограничением метода является проблема локальных минимумов: в определённых конфигурациях среды результирующая сила обращается в ноль, и робот останавливается, не достигнув цели [11]. Кроме того, метод не строит глобального маршрута, что может приводить к выбору неэффективных траекторий.

Метод динамического окна (DWA — Dynamic Window Approach) [8] является одним из наиболее распространённых локальных планировщиков в практических системах навигации, в частности в рамках программного обеспечения ROS (Robot Operating System). К достоинствам метода относится явный учёт кинематических ограничений робота. Однако DWA, как и метод потенциальных полей, является реактивным: горизонт планирования ограничен одним шагом, и метод не способен упреждающе обходить опасные зоны.

Концепция препятствий в пространстве скоростей (VO — Velocity Obstacles) [7] позволяет определить множество скоростей робота, при выборе которых произойдёт столкновение с движущимся объектом. Достоинством VO является формальный учёт скоростей препятствий в реальном времени. Ограничение состоит в том, что метод определяет лишь допустимые скорости на текущем шаге, требуя интеграции с алгоритмом глобального планирования [3].

Алгоритм оптимального взаимного избегания столкновений (ORCA — Optimal Reciprocal Collision Avoidance) [17] расширяет концепцию VO для многоагентных систем. К достоинствам ORCA относятся децентрализованность и масштабируемость. Существенным ограничением, специфичным именно для данного метода, является строгое требование кооперативного поведения: алгоритм предполагает, что все подвижные объекты используют ORCA. Данное допущение не выполняется для неконтролируемых объектов (персонала, ручных погрузчиков), поведение которых не подчиняется формализованным правилам [5, 14].

Подход пространственно-временного планирования рассматривает время как дополнительное измерение конфигурационного пространства [15]. Дискретизация временного измерения (пространственно-временной A*) приводит к экспоненциальному росту числа состояний в графе. Алгоритм SIPP (Safe Interval Path Planning) [15] снижает эту вычислительную сложность до полиномиальной, группируя безопасные моменты времени в интервалы и сокращая число раскрываемых состояний. Тем не менее, SIPP по-прежнему требует полного знания траекторий всех объектов на горизонте планирования и неустойчив к отклонениям реального поведения препятствий от прогноза [4, 14].

Таблица 2

Сравнительный анализ методов учёта динамических препятствий

Из таблицы 2 следует, что рассмотренные методы делятся на реактивные и глобальные. Реактивные подходы обеспечивают быстрое локальное избегание столкновений, но не формируют целенаправленного маршрута. Глобальное пространственно-временное планирование учитывает полные траектории, но предъявляет высокие требования к ресурсам и информации. Таким образом, промежуточный подход — интеграция прогноза движения препятствий непосредственно в классический глобальный планировщик на плоскости (x,y)— в рассмотренных методах не реализован.

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

Мировой рынок складских роботов характеризуется переходом от систем с фиксированными маршрутами (AGV с магнитной или оптической навигацией) к автономным мобильным роботам со свободной навигацией [3]. Одним из пионеров массового внедрения мобильных роботов является компания Amazon Robotics. В работе [18] описана централизованная система координации сотен транспортных средств, перемещающих стеллажи к станциям комплектации по QR-кодам на полу. Данный подход обеспечивает высокую точность, однако требует специальной инфраструктуры и полного контроля над всеми подвижными объектами [18].

Современные решения зарубежных компаний (Geek+, Fetch Robotics, Locus Robotics, MiR) ориентированы на навигацию в неструктурированных средах в присутствии людей. Используются алгоритмы одновременной локализации и построения карты (SLAM) с применением лидаров и камер глубины [6].

Российский рынок складской робототехники находится на этапе активного формирования [6]. Отечественные компании (Ronavi Robotics, Aripix Robotics, ГК «Роботикс» и др.) предлагают решения, сопоставимые по базовому функционалу с зарубежными аналогами: роботы используют лазерную навигацию и способны функционировать в условиях склада с присутствием персонала. Однако масштабы внедрений в России пока уступают мировым лидерам и представлены преимущественно пилотными проектами [3].

Таблица 3

Сравнительный анализ особенностей систем навигации промышленных складских роботов

Анализ показывает, что ограничения в работе с динамическими препятствиями носят системный характер для всей отрасли. И зарубежные, и отечественные решения опираются на реактивную стратегию: обнаружение → остановка → локальный обход. Это свидетельствует о том, что алгоритмическая задача интеграции прогноза движения препятствий в глобальный планировщик остаётся нерешённой не только в теоретическом, но и в прикладном отношении.

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

Статичность классических алгоритмов. Алгоритм A [9] и алгоритм Дейкстры [2] обеспечивают оптимальность в статической среде, но их функции стоимости не содержат компонентов, отражающих движение объектов. Инкрементальные алгоритмы D и D* Lite [12, 16] эффективно адаптируются к появлению или исчезновению статических препятствий, однако не моделируют их траектории, рассматривая динамику как последовательность независимых изменений карты [14].

Локальность реактивных методов. Метод динамического окна (DWA) [8] и препятствия в пространстве скоростей (VO) [7] обеспечивают быстрое реагирование, но не формируют глобального маршрута. Алгоритм ORCA [17], помимо этого, предполагает кооперативное поведение всех агентов — ограничение, специфичное именно для методов взаимного избегания и неприменимое к неконтролируемому персоналу склада [5].

Вычислительная сложность пространственно-временного подхода. Пространственно-временной A* характеризуется экспоненциальным ростом пространства поиска при добавлении временного измерения. Алгоритм SIPP [15] снижает эту сложность до полиномиальной, однако по-прежнему требует полного знания траекторий всех объектов на горизонте планирования [4].

Преобладание реактивных стратегий в промышленности. Как зарубежные, так и отечественные системы [3, 11] используют многоуровневую архитектуру, где глобальный планировщик работает со статической картой, а динамические объекты обрабатываются локальным уровнем остановки и ожидания. Это снижает пропускную способность склада.

Недостаточная разработанность подхода «прогнозирование + A». Систематический поиск в базах данных научной литературы (eLibrary.ru, cyberleninka.ru Scopus, IEEE Xplore) по запросам «A penalty function dynamic obstacles», «A prediction cost function», «штрафная функция A динамические препятствия» выявляет лишь единичные работы, рассматривающие изменение весов рёбер или узлов на основе информации о препятствиях [3, 14]. Комплексный подход, предусматривающий введение штрафного слагаемого, зависящего от расстояния до прогнозируемых зон риска динамических объектов, в виде устоявшегося алгоритма в литературе практически отсутствует. Именно это подтверждает тезис о недостаточной проработанности данного направления.

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

Интеграция прогнозирования в функцию стоимости. Недостаточно разработан систематический подход к введению штрафной функции в алгоритм A*, учитывающей прогнозируемые позиции динамических препятствий без увеличения размерности пространства поиска (в отличие от пространственно-временного планирования). Модификация функции стоимости вида: где зависит от расстояния до прогнозируемых зон риска, позволила бы сочетать оптимальность A* с превентивным избеганием опасных участков [3, 14].

Открытый теоретический вопрос. При этом следует отметить, что введение зависящего от прогнозируемого движения штрафа делает стоимость узла динамической. Открытым остаётся принципиальный теоретический вопрос о сохранении свойств допустимости (admissibility) и консистентности (consistency) эвристики при наличии такого временного штрафа, поскольку без этих свойств алгоритм A* не гарантирует оптимальности. Формализация условий, при которых не нарушает математических гарантий оптимального поиска, представляет собой самостоятельную исследовательскую задачу.

Гибридные архитектуры. Комбинирование глобального планировщика (с учётом прогноза) с локальным реактивным методом (например, DWA) позволит обеспечить целенаправленность маршрута при сохранении способности к оперативному реагированию на отклонения прогноза [1, 5].

Формализация критериев перепланирования. Разработка комплексных условий инициации перепланирования — не только при физическом блокировании пути, но и при превышении порога опасности или пересечении с прогнозируемой зоной риска — позволит повысить адаптивность без постоянного перевычисления маршрута [5]. Результаты анализа обобщены в таблице 4.

Таблица 4

Соответствие выявленных пробелов перспективным направлениям

Из таблицы 4 следует, что наиболее значимым пробелом является недостаточная проработанность подходов к интеграции прогнозирования движения препятствий непосредственно в функцию стоимости алгоритма A*. Данное направление представляет интерес как в теоретическом плане (формализация штрафной функции, анализ влияния на свойства допустимости и консистентности эвристики), так и в прикладном (повышение эффективности навигации AGV на складах за счёт сокращения числа вынужденных остановок).

Заключение

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

Установлено, что классические алгоритмы ориентированы на статическую среду; методы VO, ORCA и DWA обеспечивают локальное реактивное избегание столкновений, но не формируют глобального маршрута; алгоритм SIPP, несмотря на полиномиальную сложность, требует полного знания траекторий на горизонте планирования. Промышленные системы преимущественно используют стратегию остановки при обнаружении препятствий, что снижает эффективность складских операций.

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

Литература:

1. Гайдук, А. Р. Методы планирования пути мобильных роботов: монография / А. Р. Гайдук, И. А. Каляев, В. М. Лохин [и др.]. — М.: Физматлит, 2020. — 320 с. — ISBN 978–5–9221–1876–3.
2. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. — 3-е изд. — М.: Вильямс, 2013. — С. 487–521.
3. Лю, В. Методы планирования пути в среде с препятствиями (обзор) / В. Лю // Математика и математическое моделирование. — 2018. — № 1. — С. 15–58. — DOI: 10.24108/mathm.0118.0000098.
4. Павлов, А. С. Методика планирования траектории движения группы мобильных роботов в неизвестной замкнутой среде с препятствиями / А. С. Павлов // Системы управления, связи и безопасности. — 2021. — № 3. — С. 1–25.
5. Пшихопов, В. Х. Управление мобильными роботами в недетерминированных средах / В. Х. Пшихопов, М. Ю. Медведев. — Ростов-на-Дону: ДГТУ, 2019. — 245 с. — ISBN 978–5–7890–1678–9.
6. Татаринов, И. В. Анализ рынка складской робототехники и перспективы развития / И. В. Татаринов, А. В. Лукьянова // XI Международная научно-практическая заочная конференция «ЭТАП-2024»: сб. тр. — Набережные Челны: Казанский (Приволжский) федеральный университет, 2024. — С. 1129–1136.
7. Fiorini, P. Motion Planning in Dynamic Environments Using Velocity Obstacles / P. Fiorini, Z. Shiller // International Journal of Robotics Research. — 1998. — Vol. 17, No. 7. — P. 760–772.
8. Fox, D. The Dynamic Window Approach to Collision Avoidance / D. Fox, W. Burgard, S. Thrun // IEEE Robotics & Automation Magazine. — 1997. — Vol. 4, No. 1. — P. 23–33.
9. Hart, P. E. A Formal Basis for the Heuristic Determination of Minimum Cost Paths / P. E. Hart, N. J. Nilsson, B. Raphael // IEEE Transactions on Systems Science and Cybernetics. — 1968. — Vol. 4, No. 2. — P. 100–107.
10. Kavraki, L. E. Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces / L. E. Kavraki, P. Švestka, J.-C. Latombe, M. H. Overmars // IEEE Transactions on Robotics and Automation. — 1996. — Vol. 12, No. 4. — P. 566–580.
11. Khatib, O. Real-Time Obstacle Avoidance for Manipulators and Mobile Robots / O. Khatib // International Journal of Robotics Research. — 1986. — Vol. 5, No. 1. — P. 90–98.
12. Koenig, S. D* Lite / S. Koenig, M. Likhachev // Proceedings of the AAAI Conference on Artificial Intelligence. — 2002. — P. 476–483.
13. LaValle, S. M. Rapidly-Exploring Random Trees: A New Tool for Path Planning: Tech. Report 98–11 / S. M. LaValle. — Iowa State University, 1998.
14. Mohanan, M. G. A Survey of Robotic Motion Planning in Dynamic Environments / M. G. Mohanan, A. Salgoankar // Robotics and Autonomous Systems. — 2018. — Vol. 100. — P. 171–185.
15. Phillips, M. SIPP: Safe Interval Path Planning for Dynamic Environments / M. Phillips, M. Likhachev // Proceedings of the IEEE International Conference on Robotics and Automation. — 2011. — P. 5628–5635.
16. Stentz, A. Optimal and Efficient Path Planning for Partially-Known Environments / A. Stentz // Proceedings of the IEEE International Conference on Robotics and Automation. — 1994. — P. 3310–3317.
17. van den Berg, J. Reciprocal n-Body Collision Avoidance / J. van den Berg, S. J. Guy, M. Lin, D. Manocha // Proceedings of the International Symposium on Robotics Research. — 2011. — P. 3–19.
18. Wurman, P. R. Coordinating Hundreds of Cooperative, Autonomous Vehicles in Warehouses / P. R. Wurman, R. D'Andrea, M. Mountz // AI Magazine. — 2008. — Vol. 29, No. 1. — P. 9–20.