Возможность реализации алгоритма кратчайшего пути с путевыми точками на веб-сайтах
В настоящее время я делаю проект с использованием Webots для создания мира трехмерного моделирования - контейнерного терминала, в котором несколько роботов (AGV) достигают назначенного пункта назначения для загрузки / выгрузки контейнеров.
Вот проблеск того, чем я занимаюсь последние несколько недель.
http://www.youtube.com/watch?v=Rt6NlGP9wpA
Круглые пузырьки, которые вы видите, действуют как беспроводной диапазон для отправки указаний на AGV.
Видя некоторые похожие потоки на алгоритме кратчайшего пути, такие как Dijkstra или A* Algorithms, я почти уверен, что это можно сделать, но я надеялся, что кто-нибудь мог бы предоставить некоторые идеи, возможно ли это? и какой алгоритм предпочтительнее использовать?
Спасибо и С уважением
2 ответа
Учитывая ваши разъяснения, вам нужно выбрать свою игру здесь. Самым простым решением действительно является выполнение алгоритма Дейкстры и построение кратчайших путей от любой путевой точки до любой другой путевой точки (это означает, что для каждой возможной исходной точки выполняется один алгоритм). Однако обратите внимание, что это делается только один раз (по крайней мере, пока какая-то путевая точка не будет перемещена или удалена). Кстати, здесь A* не имеет отношения, он предназначен для работы на деревьях решений / игр и поиска минимального / максимального оптимального пути (максимальное преимущество для вас, минимальное для противника), это другая история. Другой альтернативой является запуск Floyd-Warshall, который находит все пути за один проход.
В любом случае, после того, как вы это запустите, вы можете сохранить для каждой путевой точки таблицу, сообщив, какой будет следующий узел в кратчайшем пути для каждой конечной путевой точки. Вам не нужен весь путь, только следующая вершина. Как только робот попадает туда, ему говорят, куда идти дальше. Это в основном то же самое, что и в большинстве алгоритмов сетевой маршрутизации.
Теперь, если вы хотите продемонстрировать, как работают роботы, вы можете заставить их запустить этот алгоритм онлайн и рассчитать пути для себя, но тогда связь с путевыми точками будет довольно бессмысленной.
В любом случае, похоже, что вам будет весело на вашем пути, наслаждайтесь:-)
Хорошо, если бы у вас был определенный путь, который мы могли бы использовать в качестве примера, объяснение того, как будет работать алгоритм, было бы проще.
Но я все равно попытаюсь объяснить:
Учитывая, что у вас есть Начальная точка A и пункт назначения Z, который я буду представлять в этой Пирамиде:
. . . . 3 . . . .
. . . 7 4 . . .
. . 2 4 6 . .
. 8 5 9 3 .
В этой пирамиде мы попытаемся найти минимальную сумму пути, начиная с первой и до последней строки, выбрав любое из двух чисел, отличных от того, которое мы выбрали ранее.
На небольшом дереве было бы проще измерить все возможные решения и выбрать наименьшее. Это не эффективно на больших деревьях.
Чтобы решить эту проблему, нужно начать снизу и подняться, взять 8 и 5 и добавить наименьшее число к числу над ними (2 здесь), затем 5 и 9, затем 9 и 3. Вы повторяете процесс на линия выше, пока вы не достигнете верхней строки, и минимальная сумма пути.
Я надеюсь, что это немного проясняет узлы и минимальный путь. Хотя это может быть трудно для кода AGV-путей с несколькими путями и пересечениями узлов.
Простой способ, который я бы использовал, если бы у вас были координаты каждого узла AGV (точки остановки, соединяющей разные пути), состоял бы в том, чтобы нарисовать линию между пунктом назначения и началом и добавить узел за узлом самые близкие к этой линии, которые подключен к предыдущему узлу.
Удачи:)