Как найти кратчайший путь в динамической ситуации - PullRequest
11 голосов
/ 18 февраля 2012

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

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

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

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

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

Ответы [ 2 ]

5 голосов
/ 19 февраля 2012

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

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

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

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

0 голосов
/ 19 февраля 2012

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

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

...