Чем отличаются современные алгоритмы поиска путей для изменения графиков (D *, D * -Lite, LPA * и т. Д.)?

В последние годы было разработано множество алгоритмов поиска путей, которые могут вычислять лучший путь в ответ на изменения графика гораздо быстрее, чем A * - что это такое и чем они отличаются? Они для разных ситуаций, или некоторые устаревшие?

Это те, которые я смог найти до сих пор:

• Д * (1994)
• Сосредоточенный D * (1995)
• DynamicSWSF-FP (1996)
• LPA (1997)
• LPA * / Инкремент A * (2001)
• D * Lite (2002)
• SetA * (2002)
• HPA * (2004)
• В любое время D * (2005)
• PRA * (2005)
• Поле D * (2007)
• Тета * (2007)
• HAA * (2008)
• GAA * (2008)
• УЧЕБА (2009)
• BDDD * (2009 - я не могу получить доступ к этой статье: |)
• Инкрементальный Фи * (2009)
• GFRA * (2010)
• MTD * -Lite (2010)
• Дерево-АА * (2011)

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

Моя конкретная проблема: у меня есть сетка с началом, финишем и некоторыми стенами. В настоящее время я использую A *, чтобы найти лучший путь от начала до конца.

Затем пользователь переместит одну стену , и мне придется снова пересчитать весь путь. «Двигаться стена / пересчитывать-путь» шаг происходит много раз подряд, поэтому я ищу алгоритм , который будет иметь возможность быстро пересчитать наилучший путь без необходимости запуска полного итерации A *.

Хотя я не обязательно ищу изменение A * - это может быть совершенно отдельный алгоритм.

Итак, я пролистал бумаги, и это то, что я блестел. Если в предмете есть кто-то более осведомленный, пожалуйста, исправьте меня, если я ошибаюсь (или добавьте свой собственный ответ, и я приму его вместо этого!) .

Ссылки на каждый документ можно найти в вопроснике, выше.

• Простые пересчеты
  • D * (он же Dynamic A * ) (1994): На начальном этапе D * работает очень похоже на A *, находя оптимальный путь от начала до конца очень быстро. Тем не менее, когда юнит перемещается от начала до финиша, если график меняется, D * может очень быстро пересчитать лучший путь от позиции этого юнита до финиша, гораздо быстрее, чем просто запустить A * из позиции этого юнита снова. D *, однако, имеет репутацию чрезвычайно сложного и полностью устарел благодаря гораздо более простой D * -Lite.
  • Сосредоточенный D * (1995): улучшение к D *, чтобы сделать его более быстрым / «более реальным». Я не могу найти никаких сравнений с D * -Lite, но, учитывая, что он старше и о D * -Lite говорят гораздо больше, я предполагаю, что D * -Lite как-то лучше.
  • DynamicSWSF-FP (1996): Сохраняет расстояние от каждого узла до конечного узла. Имеет большую начальную настройку для расчета всех расстояний. После изменения графика он может обновлять только узлы, расстояния которых изменились. Не связано как с A *, так и с D *. Полезно, когда вы хотите найти расстояние от нескольких узлов до финиша после каждого изменения; в противном случае LPA * или D * -Lite обычно более полезны.
  • LPA * / Incremental A * (2001): LPA * (Планирование на протяжении всей жизни A *) , также известный как Incremental A * (а иногда, как ни странно, как «LPA», хотя он не имеет никакого отношения к другому алгоритму, названному LPA), является комбинация DynamicSWSF-FP и A *. При первом запуске он точно такой же, как A *. Однако после незначительных изменений в графике последующие поиски из той же пары начала / конца могут использовать информацию из предыдущих запусков, чтобы значительно сократить количество узлов, которые необходимо исследовать, по сравнению с A *. Это как раз моя проблема, так что звучит так, будто LPA * подойдет мне лучше всего. LPA * отличается от D * тем, что всегда находит лучший путь от одного и того же начала до одного и того же конца; не используется, когда начальная точка движется(например, юниты движутся по начальному лучшему пути) . Тем не мение...
  • D * -Lite (2002): этот алгоритм использует LPA * для имитации D *; то есть он использует LPA *, чтобы найти новый лучший путь для юнита, когда он движется по начальному лучшему пути, и график меняется. D * -Lite считается намного проще, чем D *, и, поскольку он всегда работает по крайней мере так же быстро, как D *, он полностью устарел D *. Таким образом, нет никакой причины использовать D *; используйте вместо этого D * -Lite.
• Движение под любым углом
  • Поле D * (2007): вариант D * -Lite, который не ограничивает движение в сетке; то есть, лучшая траектория может иметь единицу, движущуюся под любым углом, а не только на 45- (или 90-) градусов между точками сетки. Использовался НАСА для поиска марсоходов.
  • Тета * (2007): вариант A *, который дает лучшие (более короткие) пути, чем Поле D *. Однако, поскольку он основан на A *, а не на D * -Lite, он не обладает возможностями быстрой перепланировки, которые есть у Field D *. Смотрите также .
  • Incremental Phi * (2009): лучшее из обоих миров. Версия Theta *, которая является инкрементной (она также позволяет быстро перепланировать)
• Перемещение целевых точек
  • GAA * (2008): GAA * (обобщенный адаптивный A *) - это вариант A *, который обрабатывает движущиеся целевые точки. Это обобщение еще более раннего алгоритма под названием «Moving Target Adaptive A *»
  • GRFA * (2010): GFRA * (Обобщенный Fring -Retrieving A *) представляется (?) Обобщением GAA * для произвольных графов (т. Е. Не ограниченных 2D) с использованием методов из другого алгоритма, называемого FRA *.
  • MTD * -Lite (2010): MTD * -Lite (Moving Target D * -Lite) является «расширением D * Lite, которое использует принцип, лежащий в основе обобщенного Fringe-Retrieving A *», для выполнения быстрого перепланирования поиска движущейся цели.
  • Tree-AA * (2011): (???) Похоже, что это алгоритм поиска неизвестного ландшафта, но он основан на Adaptive A *, как и все другие алгоритмы в этом разделе, поэтому я поместил его здесь. Не уверен, как это сравнивается с другими в этом разделе.
• Fast / Sub-оптимальный
  • Anytime D * (2005): это вариант D * -Lite «в любое время» , осуществляемый путем объединения D * -Lite с алгоритмом, называемым Anytime Repairing A * . Алгоритм «В любое время» - это алгоритм, который может работать при любых ограничениях по времени - для начала он найдет очень неоптимальный путь, а затем улучшит этот путь, чем больше времени ему дадут.
  • HPA * (2004): HPA * (Hierarchical Path-Finding A *) предназначен для поиска пути большого количества юнитов на большом графике, например в видеоиграх RTS (стратегия в реальном времени) . Все они будут иметь разные начальные местоположения и потенциально разные конечные местоположения. HPA * разбивает график на иерархию, чтобы быстро находить «почти оптимальные» пути для всех этих блоков гораздо быстрее, чем запускать A * на каждом из них в отдельности. Смотрите также
  • PRA * (2005): Из того, что я понимаю, PRA * (частичное уточнение A *) решает ту же проблему, что и HPA *, но другим способом. Они оба имеют «одинаковые характеристики производительности».
  • HAA * (2008): HAA * (Иерархический аннотированный A *) является обобщением HPA *, которое допускает ограниченное прохождение некоторых юнитов по некоторым территориям (например, небольшой путь, по которому некоторые юниты могут проходить, но большие не могут; или дыру, которую могут пересечь только летающие единицы и т. д.)
• Другое / Unknown
  • LPA (1997): LPA (алгоритм поиска пути без петель) представляется алгоритмом маршрутизации, лишь незначительно связанным с проблемами, которые решают другие алгоритмы. Я упоминаю об этом только потому, что на эту статью в некоторых местах в Интернете вводят в заблуждение (и неправильно) ссылку на статью, в которой описывается LPA *, а это не так.
  • LEARCH (2009): LEARCH - это комбинация алгоритмов машинного обучения, используемых для обучения роботов тому, как самостоятельно находить почти оптимальные пути. Авторы предлагают объединить LEARCH с полем D * для лучших результатов.
  • БДДД * (2009): ??? Я не могу получить доступ к бумаге.
  • SetA * (2002): ??? Это, по-видимому, вариант A *, который ищет модель графа «диаграмма бинарных решений» (BDD)? Они утверждают, что в некоторых случаях он работает «на несколько порядков быстрее, чем A *» . Однако, если я правильно понимаю, это те случаи, когда каждый узел на графе имеет много ребер?

Учитывая все это, кажется, что LPA * лучше всего подходит для моей проблемы.

При использовании D *, D * -Lite или любого из дополнительных алгоритмов в этой категории есть большая оговорка (и стоит отметить, что эта оговорка редко упоминается в литературе). Эти типы алгоритмов используют обратный поиск. То есть они вычисляют затраты наружу от узла цели, как пульсация, распространяющаяся наружу. Когда цены на ребра изменяются (например, вы добавляете или удаляете стену в вашем примере), все они имеют различные эффективные стратегии для обновления только подмножества исследуемых (так называемых «посещенных») узлов, на которые влияют изменения.

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

Когда измененная информация о стоимости близка к периметру расширяющегося фронта поиска («посещенная» область), нужно изменить несколько путей, и постепенные обновления выполняются быстро. Уместным примером является мобильный робот с датчиками, прикрепленными к его телу. Датчики видят только мир рядом с роботом, и, следовательно, изменения происходят в этом регионе. Эта область является отправной точкой поиска, а не целью, и поэтому все работает хорошо, и алгоритмы очень эффективны при обновлении оптимального пути для исправления изменений.

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

Поскольку ваш примерный сценарий позволяет пользователю перемещать любую стену по своему усмотрению, вы столкнетесь с этой проблемой, если будете использовать D *, D * -Lite, LPA * и т. Д. Производительность вашего алгоритма во времени будет переменной, в зависимости от пользователя. вход. В общем, "это плохо" ...

Например, у группы Алонзо Келли в CMU была фантастическая программа под названием PerceptOR, которая пыталась объединить наземных роботов с воздушными роботами, и все они обменивались информацией о восприятии в режиме реального времени. Когда они попытались использовать вертолет для предоставления в реальном времени обновлений стоимости системы планирования наземного транспортного средства, они столкнулись с этой проблемой, поскольку вертолет мог лететь впереди наземного транспортного средства, видя изменения стоимости ближе к цели и, таким образом, замедляя вниз их алгоритмы. Обсуждали ли они это интересное наблюдение? В конце концов, лучшее, что им удалось, - это заставить вертолет летать прямо над наземным транспортным средством, что сделало его самой дорогой в мире мачтой для датчиков. Конечно, я мелкая Но это большая проблема, о которой никто не хочет говорить - и они должны,

Есть только несколько статей, которые обсуждают это, в основном я. Из работ, написанных авторами или студентами авторов оригинальных работ, перечисленных в этом вопросе, я могу вспомнить только одну, которая действительно затрагивает эту проблему. Лихачев и Фергюсон предлагают попытаться оценить масштаб требуемых обновлений и очистить сохраненную информацию, если предполагается, что добавочное обновление займет больше времени, чем новый старт. Это довольно разумный обходной путь, но есть и другие. Моя кандидатская диссертация обобщает аналогичный подход в широком спектре вычислительных задач и выходит за рамки этого вопроса, однако вы можете найти полезные ссылки, поскольку в ней содержится подробный обзор большинства из этих алгоритмов и многое другое. См. Http://db.acfr.usyd.edu.au/download.php/Allen2011_Thesis.pdf?id=2364. для деталей.

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

Кениг и Ликкачев, Быстрое перепланирование для навигации в неизвестной местности, IEEE Transactions on Robotics, Vol. 21, № 3, июнь 2005 года представляет D * Lite. Можно с уверенностью сказать, что D * устарел в том смысле, что D * Lite всегда так же быстр, как D *. Кроме того, D * является сложным, трудным для понимания, анализа и расширения. На рисунке 9 показан псевдокод для D * Lite, а в таблице 1 показаны экспериментальные результаты с D * Lite по сравнению с BFS, Backward A *, Forward A *, DynamicSWSF-P и D *.

Я не знаю новых алгоритмов, которые вы перечисляете (Anytime D *, Field D *, LEARCH). Совсем недавно я увидел робота, который использовал D * Lite для планирования в среде со случайными бродягами. В этом смысле я не думаю, что D * Lite отнюдь не устарела. Что касается вашей практической задачи, я думаю, что нет ничего плохого в том, чтобы пробовать обычный инженерный путь: используйте какой-то подход, а если он не соответствует вашим потребностям, попробуйте что-то другое (более сложное).

Я хотел бы добавить кое-что о быстро исследуемых рандомизированных деревьях или RRT. Основная идея хорошо обсуждается по всему Интернету, но, вероятно, можно начать со ссылок со страницы Википедии и с оригинальными статьями Куффнера и ЛаВалля по этой теме.

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

• http://en.wikipedia.org/wiki/Rapidly_exploring_random_tree
• http://swing.adm.ri.cmu.edu/pub_files/pub4/zucker_matthew_2007_1/zucker_matthew_2007_1.pdf

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

Если графики являются сетками (и, следовательно, плоскими), существуют некоторые динамические структуры данных (неясно, достаточно ли малы константы для рассматриваемого приложения):

Точные кратчайшие пути:

Jittat Fakcharoenphol, Satish Rao: плоские графики, отрицательные весовые ребра, кратчайшие пути и время, близкое к линейному. J. Comput. Сист. Sci. 72 (5): 868-889 (2006)

Примерные кратчайшие пути:

Филип Н. Клейн, Сайрам Субраманян: полностью динамическая схема приближения для кратчайших путей в плоских графах. Algorithmica 22 (3): 235-249 (1998)

Иттай Абрахам, Шири Чечик, Кирилл Гавойль: полностью динамические оракулы приблизительного расстояния для плоских графов через запрещенные метки расстояния. STOC 2012: 1199-1218

В школе я баловался с оптимизацией колонии муравьев . В некоторых текстах это рекламировалось как решение для непрерывно меняющихся графиков, маршрутизации сетей и т. Д. Это не инженерное решение, а адаптация от того, как муравьи перемещаются по препятствиям, распространяя феромоны для обозначения хороших и плохих путей. Я понятия не имею, работает ли это для вашей проблемы, но я думаю, что это интересная точка зрения.