Китайская исследовательская группа предложила новую парадигму DPCN для многолетнего планирования путей

Репортаж от Wedoany，Китайская исследовательская группа предложила новую парадигму под названием DPCN (Decentralized-Planning-Centralized-Negotiation) для решения задачи многолетнего планирования путей (MAPF). Эта парадигма, сохраняя масштабируемость децентрализованных методов, эффективно обрабатывает динамические конфликты с помощью механизма централизованных переговоров, достигая на стандартных тестовых наборах производительности, превосходящей существующие методы обучения с подкреплением.

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

DPCN делит каждый временной шаг на два этапа: на этапе планирования каждый агент независимо генерирует намерение действия на основе локальной наблюдаемой информации o_i^t (обзор 3×3); на этапе переговоров система обнаруживает все потенциальные конфликты (включая конфликты вершин и обмена) и динамически объединяет агентов, вовлеченных в конфликт, в «суперагента». С помощью обучаемой сети PNSE (Pointer Network Special Edition) из конфликтующего набора выбирается один «победитель», который выполняет свое первоначальное намерение, в то время как остальные агенты остаются неподвижными или повторно выбирают новое действие.

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

Эксперименты проводились на стандартных тестовых наборах MAPF и случайных картах. Сравнение включало два типа централизованных планировщиков (ODrM*, BALANCE) и три передовых метода RL (SCRIMP, DCC, PICO). В экспериментах на случайных картах размер карт варьировался от 30×30 до 100×100, плотность препятствий — от 0% до 30%, количество агентов — от 32 до 256. Каждая конфигурация повторялась 200 раз, фиксировались показатель успешности и количество шагов для выполнения задачи. Результаты показали, что DPCN при высокой плотности препятствий (30%) и в крупномасштабных сценариях стабильно поддерживает высокий уровень успешности и низкое время выполнения задачи, значительно превосходя не только другие методы RL, но и централизованные планировщики.

При оценке способности к обобщению на структурированных картах в экспериментах использовались три типичных типа карт: многокомнатная среда размером 32×32 (размер комнат 3×3), среда аудитории размером 162×141 и складская среда размером 170×84 (ширина проходов между стеллажами всего 2 клетки). Каждая карта содержала 25 экземпляров задач. DPCN продемонстрировал способность эффективно координировать крупные группы агентов в этих сложных структурах.

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