Проблема плотных сред и тупиков
Алгоритм LaCAM (Lifelong Conflict-Based Search) является полным решателем для задачи поиска путей множества агентов (MAPF). Он использует поиск в глубину по совместным конфигурациям, применяя алгоритм PIBT для генерации следующих шагов. Однако на картах с высокой плотностью агентов (60–90% занятых клеток) LaCAM часто сталкивается с тупиками. Для выхода из них требуется скоординированное движение нескольких агентов, часто в сторону, противоположную их целям. Стандартный жадный алгоритм PIBT редко предлагает такие ходы, а LaCAM вынужден перебирать ограничения по одному агенту, что крайне неэффективно.
Решение: Goal-Branching LaCAM
Авторы Stephen Chang и Daniel Harabor предлагают метод Goal-Branching. Суть заключается в том, что агенты, блокирующие путь другим, получают временные цели. Каждая такая временная цель добавляется как отдельная ветвь в поиск LaCAM. Исследователи протестировали случайные и специализированные (коридорно-ориентированные) правила выбора этих целей, доказав, что полнота алгоритма сохраняется при любом правиле.
Результаты бенчмарков
Эксперименты проводились на картах типа «лабиринт» (maze) и «комната» (room) с высокой плотностью агентов. Ниже приведено сравнение эффективности новой версии с оригинальным LaCAM*:
| Метрика | Goal-Branching LaCAM | LaCAM* | Примечание |
|---|---|---|---|
| Доля решенных задач (плотные карты) | 89% | 44% | На картах с 60-90% занятых клеток |
| Скорость поиска первого решения (maze-32-32-2) | 10-14x быстрее | База | На задачах, решаемых обоими алгоритмами |
| Медианное время (room-32-32-4, 75% плотность) | ~200x быстрее | База | Критическое ускорение в узких местах |
| Рост стоимости решения (cost) | +15-22% | База | Небольшое увеличение длины пути ради скорости |
| Производительность на открытых картах | Без потери качества | База | Стоимость решений не выше, скорость не медленнее на 3% |
Значение для индустрии
Результаты показывают, что введение временных целей позволяет обойти ограничения жадных стратегий в сложных сценариях. Для логистических роботов, дронов и автономных транспортных средств, работающих в плотных потоках, этот метод предлагает значительный прирост производительности. При этом на стандартных открытых картах (полный набор MovingAI) алгоритм сохраняет сопоставимость с оригиналом, не ухудшая показатели.
Источник: arXiv cs.AI ↗