Untitled

Алгоритм 1: Поиск на высоком уровне в CBS.
Вход: Представление среды, начальные и конечные ячейки агентов
Результат: Оптимальное решение без столкновений

R.constraints ← ∅
R.paths ← найти независимые пути для всех агентов с использованием a_star()
R.collisions ← обнаружить_столкновения(R.paths)
R.cost ← получить_сумму_стоимости(R.paths)
вставить R в OPEN
пока OPEN не пустой делать
P ← узел из OPEN с наименьшей стоимостью
если P.collisions = ∅ тогда
вернуть P.paths // P - целевой узел
collision ← одно столкновение в P.collisions
constraints ← стандартное_разделение(collision)
для каждого constraint в constraints делать
Q ← новый узел
Q.constraints ← P.constraints ∪ {constraint}
Q.paths ← P.paths
ai ← агент в constraint
path ← a_star(ai, Q.constraints)
если path не пустой тогда
Заменить путь агента ai в Q.paths на path
Q.collisions ← обнаружить_столкновения(Q.paths)
Q.cost ← получить_сумму_стоимости(Q.paths)
Вставить Q в OPEN
Вернуть 'Нет решений'