Новый метод разложения задач MAPF на решаемые подзадачи

Эта статья представляет структурированную методологию для разложения экземпляров поиска пути для нескольких агентов (MAPF) на более мелкие, разрешимые подзадачи. Процесс начинается с определения зависимостей агентов и формирования кластеров посредством графов релевантности. Эти кластеры итеративно бипартицируются с помощью анализа неизбежных агентов для минимизации размера подзадачи при сохранении разрешимости. Дальнейшее уточнение вводит уровни на основе ограничений порядка решения, полученных из направленных графов и сильно связанных компонентов. Наконец, подход описывает, как независимо решать и безопасно объединять подзадачи с помощью последовательных или параллельных методов MAPF. Хотя не гарантируется достижение оптимального разложения, данная структура прогрессивно снижает сложность и сохраняет конфликтно-безопасную осуществимость.