Как найти кратчайший путь в динамической ситуации

Несколько дней назад кто-то спрашивает меня: "Если у нас есть какие-то агенты в нашей среде, и они хотят перейти из своих источников в свои пункты назначения, как мы можем найти общий кратчайший путь для всех из них, чтобы у них не было конфликты во время их прогулки.

Точка проблемы - это все агенты, которые одновременно ходят в среде (которая может быть смоделирована неориентированным взвешенным графом), и мы не должны столкнуться. Я думал об этом, но я не мог найти оптимальный путь для всех. Но уверен, что для этой проблемы слишком много эвристических идей.

Предположим, что ввод - это граф G (V, E), m агентов, которые находятся в: S 1, S 2,..., S m узлов графика при запуске, и они должны перейти в узлы D 1,... D m в конце. Также может быть конфликт в узлах S i или D i,... но эти конфликты не являются важно, чтобы у них не было конфликтов, когда они находились в своих внутренних узлах своего пути.

Если их путь не должен иметь такой же внутренний node, он будет выглядеть как k-disjoint paths проблема, которая является NPC, но в этом случае пути могут иметь одинаковые узлы, но агент не должен быть таким же node в одно и то же время. Я не знаю, могу ли я сказать точное утверждение проблемы или нет. Если запутать, скажите мне в комментариях, чтобы отредактировать его.

Существует ли какой-либо оптимальный и быстрый алгоритм (по оптимальному я означает, что сумма длины всех путей максимально мала, а по-быстрому - хороший алгоритм хорошего полиномиального времени).

Ответы

Ответ 1

Поиск в Google показывает две ссылки, которые могут быть полезны:

Изменить: В главе книги (первая ссылка):

Существуют различные подходы к планированию маршрутов в многопользовательской системе [sic], однако, оптимальное решение NP-hard. Hopcraft et al. (1984) упрощают задачу планирования для проблема перемещения прямоугольников в прямоугольном контейнере. Они доказали NP-твердость нахождение плана от заданной конфигурации до конфигурации цели с наименьшим количеством шаги. Следовательно, все возможные подходы к планированию пути являются компромиссом между эффективностью и точность результата.

Я не могу найти оригинальную бумагу Hopcroft онлайн, но, учитывая эту цитату, я подозреваю, что проблема, с которой они уменьшили задачу навигации, похожа на Rush Hour, который является PSPACE-полным.

Ответ 2

Если это просто вопрос перехода от точки a к точке b для каждого робота, вы можете просто использовать алгоритм поиска, например A * (A Star) или Best-First.

Дайте ему простую эвристику, такую ​​как сумма расстояний от цели.