Найти статью
Алгоритм поиска D*
Алгоритм поиска D* — алгоритм поиска пути в графах, разработанный как расширение алгоритма A* и, соответственно, является прямым «потомком» алгоритма Дейкстры. В базовой форме как A*, так и алгоритм Дейкстры не обладают гибкостью и не способны реагировать на изменения графа во время или после обработки — в обоих случаях пользователю приходится начинать весь расчёт заново. Особенно такая ситуация характерна для работы с роботами или агентами в реальных условиях (ограниченная дальность сенсоров, неизвестная обстановка), где крупные карты постоянно обновляются[1].
Оригинальный алгоритм D* (от англ. Dynamic A* — «динамический A*») был представлен в 1994 году Энтони Стенцем из Университета Карнеги — Меллон[2]. Впоследствии были разработаны его ключевые модификации, такие как Focussed D* (1995)[3] и D* Lite (2002), последняя из которых получила широкое распространение благодаря своей простоте и эффективности[4].
История и развитие
Оригинальный D* и Focussed D* (1994—1995)
Концептуальные основы оригинального алгоритма D* были заложены в 1993 году в техническом отчёте Энтони Стенца «Optimal and Efficient Path Planning for Unknown and Dynamic Environments». Формальное представление алгоритма состоялось в 1994 году. Ключевой особенностью D* (от англ. Dynamic A* — «динамический A*») стала способность эффективно корректировать существующий маршрут в ответ на новую информацию об окружении, например, при обнаружении ранее неизвестных препятствий, без необходимости полного пересчёта пути с нуля. Алгоритм «ремонтирует» уже построенный план, распространяя информацию об изменении стоимости прохода только в затронутой части графа[5]. Это достигается за счёт использования состояний англ. RAISE (повышение стоимости) и англ. LOWER (понижение стоимости) для узлов графа и выполнения поиска в обратном направлении — от цели к стартовой точке[5].
В 1995 году Стенц представил усовершенствованную версию — Focussed D* (англ. Сфокусированный D*). Этот вариант объединил принципы работы оригинального D* и алгоритма A*. Focussed D* использует эвристику для того, чтобы сфокусировать процесс перепланирования на тех участках, которые наиболее релевантны для текущего положения агента. Такой подход позволил значительно сократить количество вычислений и ускорить обновление маршрута по сравнению с оригинальной версией.
D* Lite (2002)
В 2002 году Свен Кёниг и Максим Лихачёв представили D* Lite (англ. D Star Lite) — инкрементальный эвристический алгоритм поиска, работа над которым была опубликована на 18-й конференции AAAI по искусственному интеллекту. D* Lite был задуман как более простая и лёгкая для понимания версия оригинального D* Энтони Стенца. В его основе лежит другой алгоритм — Lifelong Planning A* (LPA*), который был адаптирован для навигации роботов по неизвестной местности.
Ключевое преимущество D* Lite заключается в его эффективности: вместо полного перепланирования маршрута с нуля при обнаружении новых препятствий, алгоритм инкрементально корректирует только затронутые участки существующего пути[6]. Благодаря своей эффективности и относительной простоте реализации, D* Lite и его вариации получили широкое распространение в области мобильной робототехники и навигации автономных транспортных средств[7].
Дальнейшие модификации (2005—2009)
После появления D* Lite фокус исследований сместился с создания принципиально новых алгоритмов на усовершенствование существующих, повышение качества пути и адаптацию для решения более сложных практических задач. В этот период были разработаны несколько ключевых модификаций.
Anytime D* (2005) — алгоритм, представляющий собой комбинацию ARA* (англ. Anytime Repairing A*) и D* Lite[8]. Он был разработан для планирования длинных и сложных манёвров, таких как парковка. Эта технология использовалась в автомобиле-роботе от Университета Карнеги — Меллон, который стал победителем в соревновании DARPA Urban Challenge[8].
Field D* (2005) — одна из наиболее значительных модификаций, предложенная Дейвом Фергюсоном и Энтони Стенцем[9]. В отличие от классических сеточных планировщиков, которые ограничивают движение заранее определёнными направлениями (например, 8 направлений на 2D-сетке) и создают неестественные, «зубчатые» пути, Field D* использует линейную интерполяцию для вычисления стоимости пути[10]. Это позволяет планировать маршрут с произвольными, непрерывными углами движения, в результате чего пути становятся более гладкими, короткими и естественными[10]. Алгоритм является расширением D* Lite и был успешно применён для навигации марсоходов НАСА «Спирит» и «Оппортьюнити»[11].
Incremental Phi* (2009) — алгоритм, объединивший преимущества двух подходов: способность строить пути под любым углом (англ. any-angle paths), заимствованную у алгоритма Theta*, и инкрементальный подход к перепланированию, характерный для семейства D*.
Развитие с 2010 года
С 2010-х годов развитие алгоритмов семейства D* сместилось с создания фундаментально новых концепций на повышение эффективности, адаптацию к сложным условиям и интеграцию с другими методами. Основные исследования коснулись улучшения качества пути, ускорения перепланирования и создания гибридных систем для решения комплексных задач в робототехнике.
Основное внимание было уделено D* Lite. Ключевыми направлениями его развития стали:
- Гибридизация с локальными планировщиками. Распространённым подходом стала комбинация D* Lite с такими методами, как англ. Dynamic Window Approach (DWA). В таких системах D* Lite отвечает за построение глобального маршрута, а DWA — за локальное маневрирование и обход внезапных препятствий с учётом кинематических ограничений робота[12].
- Оптимизация функций стоимости. Были предложены модификации, учитывающие не только расстояние, но и другие факторы, например, безопасность. В одной из версий 2024 года в функцию стоимости было интегрировано «значение риска», чтобы маршрут пролегал на безопасном расстоянии от препятствий[12].
- Адаптация для специфических задач. Алгоритм был адаптирован для навигации беспилотных надводных аппаратов (англ. USV)[13], подводных роботов[14] и для многоагентного планирования, где пути других роботов рассматриваются как динамические препятствия[15].
Одновременно продолжалось развитие Field D*. Важнейшим шагом стала его адаптация для трёхмерного пространства — 3D Field D*[16]. Эта версия позволяет применять алгоритм для планирования пути БПЛА и подводных аппаратов, где необходимо учитывать изменение высоты. Как и его 2D-аналог, 3D Field D* использует интерполяцию для построения прямых и экономичных траекторий в трёхмерном пространстве[16].
Принцип работы
Первая экспансия
Как и в алгоритме A*, в D* изначально выбирается маршрут от старта к цели. Однако, в отличие от A*, порядок поиска инвертирован: поиск ведётся от цели к старту. Это позволяет каждому расширенному узлу ссылаться на следующий узел, ведущий к цели, и знать точную стоимость пути к цели (после завершения экспансии).
В зависимости от используемой вспомогательной метрики (эвристики) и от того, прерывается ли работа после нахождения старта, может быть расширено больше или меньше узлов — они впоследствии поддерживают расчёт маршрута. Процесс экспансии аналогичен A*: если расширяется стартовый узел, алгоритм можно остановить. При этом структура OpenList не очищается.
Возникновение преграды
Когда возникает новая преграда, все связанные с ней узлы повторно добавляются в OpenList. При этом они отмечаются как Raise-узлы (оранжевые точки на карте). Прежде чем Raise-узел распространит увеличение стоимости на свои следующие узлы, он проверяет, есть ли среди его соседей такой, который мог бы уменьшить эту стоимость. После этого по всем затронутым узлам проходит волна Raise. За ней, если существует такая возможность, следует Lower-волна (зелёные точки), которая распространяет уменьшение стоимости. В примере крайний справа узел может привести к цели через альтернативного соседа; он становится Lower-состоянием и «следует» за Raise-волной. Это и есть основная идея D*: благодаря такому механизму обрабатываются только те узлы, которые действительно затронуты изменением стоимости.
Возникновение новой преграды
В данном случае обойти преграду просто не удаётся: ни один узел не сможет найти новый путь к цели через соседей. Поэтому повышение стоимости распространяется дальше, пока только вне блокады не находятся узлы, которые предоставляют маршрут к цели. В таком случае появляются две Lower-волны, которые для ранее недостижимых узлов раскрывают новую информацию о маршруте.
Алгоритм
while(openList.nichtLeer())
{
punkt = openList.erstesElement();
expandiere(punkt);
}
Функция: expandieren
void expandiere(aktuellerPunkt)
{
boolean istRaise = istRaise(aktuellerPunkt);
double kosten;
foreach(nachbar in aktuellerPunkt.getNachbarn())
{
if(istRaise)
{
if(nachbar.nächsterPunkt == aktuellerPunkt)
{
nachbar.setztNächstenPunktUndAktualisiereKosten(aktuellerPunkt);
openList.hinzufüge(nachbar);
}
else
{
kosten = nachbar.berechneKostenÜber(aktuellerPunkt);
if(kosten < nachbar.getKosten())
{
aktuellerPunkt.minimaleKostenAufAktuelleKostenSetzen();
openList.hinzufügen(aktuellerPunkt);
}
}
}
else
{
kosten=nachbar.berechneKostenÜber(aktuellerPunkt);
if(kosten < nachbar.getKosten())
{
nachbar.setztНächstenПунктUndAktualisiereKosten(aktuellerПunkt);
openList.hinzufüge(nachbar);
}
}
}
}
Проверка Raise-состояния
boolean istRaise(punkt)
{
double kosten;
if(punkt.getAktuelleKosten() > punkt.getMinimaleKosten())
{
foreach(nachbar in punkt.getNachbarn())
{
kosten = punkt.berechneKostenÜber(nachbar);
if(kosten < punkt.getAktuelleKosten())
{
punkt.setztНächstenПунктUndAktualisiereKosten(nachbar);
}
}
}
return punkt.getAktuelleKosten() > punkt.getMinimaleKosten();
}
Описание работы алгоритма
Все известные узлы заносятся в OpenList. Изначально туда добавляется только конечный узел (цель). Пока в OpenList остаются элементы, берётся первый из них, удаляется из списка и подвергается обработке (экспансии).
Расширение узлов
Сначала определяется, находится ли текущий обрабатываемый узел в состоянии Raise или Lower. Если он в Lower-состоянии, происходит аналогичная A* обработка: для всех соседей проверяется, можно ли их достигнуть из текущего узла с меньшей стоимостью, чем ранее. Если да, текущий узел становится их предшественником, осуществляется пересчёт их стоимости, они помещаются в OpenList. При Raise-состоянии увеличение стоимости немедленно распространяется на всех соседей, для которых узел ведёт к цели. Для других соседей проверяется, не может ли текущий узел быть точкой уменьшения стоимости. Если да, его минимальная стоимость устанавливается равной текущей, он переходит в Lower-состояние и добавляется в OpenList для последующего распространения оптимизации.
Выбор между Lower и Raise
Определение состояния узла (Raise или Lower) производится путём сравнения текущей и минимальной стоимости. Если стоимость текущего пути превышает минимальную, это Raise-состояние. Прежде чем это увеличение распределиться дальше, проверяется, нет ли соседа, который способен снизить стоимость; если найден — он выбирается как новый предшественник, стоимость пересчитывается. После проверки всех соседей снова анализируется, равны ли минимальная и текущая стоимость. Если так — теперь состояние Lower, иначе Raise и увеличение стоимости продолжается.
Минимальные и текущие стоимости
В D* важно разделять текущую стоимость узла и его минимальную стоимость. Текущая важна только в момент измерения; минимальная — критична, так как именно по ней сортируется OpenList. Минимальная стоимость всегда указывает на наименьшее значение, достигнутое узлом со времени первого добавления в список. При добавлении новой преграды важно следить за тем, чтобы минимальная стоимость была меньше текущей.
Оптимизация
OpenList
Реализация структуры OpenList (список открытых узлов) оказывает наибольшее влияние на скорость работы алгоритма. Время выполнения может быть сокращено с более 10 с (например, при использовании статического массива) до менее 100 мс (сбалансированное дерево). Однако реализовать это не так тривиально, как в A*: обычное сбалансированное дерево не устраивает, так как может быть несколько разных объектов с одинаковыми числовыми значениями, которые не эквивалентны. Кроме того, требуется выбирать из множества равных объектов специальный; стандартные реализации деревьев в Java или .NET для такого случая не подходят.
Даже применение специального B-дерева иногда не оптимально: во время первой фазы экспансии Raise-состояний нет; OpenList постепенно наполняется и очищается, дерево строит и разбирает свою структуру. При возникновении Raise- и Lower-волн часто меняются минимальные стоимости, из-за чего приходится помечать или удалять элементы и обратно их включать/перестраивать; это может замедлять работу. Решить проблему помогают разные структуры данных для Lower- и Raise-узлов либо иной принцип хранения/доступа.
Проверка узлов
Изложенный здесь вариант D* имеет проблему с недостижимыми узлами. Если новая преграда полностью отсечёт какую-либо область, алгоритм не завершится. Суть в реализации Raise-метода: он, прежде чем проверить актуальность Raise-состояния, ищет соседа с меньшей стоимостью, и Raise-узел ссылается на любого из них (кроме самой преграды), что может приводить к зацикливанию Raise-волн. Избежать этого можно двумя способами:
- Жёсткое ограничение сверху: вводится числовая граница стоимости, после которой узел считается недостижимым и не может быть маршрутом для соседей. Тогда бесконечные циклы обрываются, но это не самый элегантный выход.
- Проверка допустимости: прежде чем сделать соседа предшественником, нужен тест — не ведёт ли тот к циклу, не входит ли уже в OpenList, не остался ли без предшественников (кроме цели), не помечен ли как недостижимый или как преграда. При обнаружении одного из четырёх факторов узел игнорируется. Тест можно выполнять до цели, но достаточно проверить 2 следующих узла, чтобы избежать бесконечных циклов.
Фокусирующая метрика
Пока что о метрике (эвристике) не говорилось. В примерах используется «шаговая» метрика: все узлы равноправны, и экспансия развивается по кругу. Фокусирующая метрика (как в A* для географических задач) — количество шагов до цели плюс расстояние по прямой от узла до старта. Благодаря ней обработка концентрируется вокруг известного оптимального пути или вблизи старта. Хорошая метрика должна быстро считаться и обязательно недооценивать реальные затраты — иначе возможны ошибки. В отличие от A*, D* может необратимо испортиться из-за плохой эвристики: не удастся найти путь к цели.
Именно этот принцип лёг в основу усовершенствованной версии алгоритма — Focussed D*, представленной Энтони Стенцем в 1995 году.
«Скала в прибое»
Одна из проблем фокусирующих метрик — возникновение спонтанных волн Lower/Raise на краю карты. На рисунке справа видна Raise-волна (красным), из-за фокусировки метрики она распространяется преимущественно в одном направлении, а не кругом. Точка A расширяется первой, но её предшественники ещё не охвачены Raise-волной, значит — её стоимость считается валидной и возникает Lower-волна. Такое возможно, если узлы, удалённые от цели, расширяются раньше, чем более близкие; узел, который «неправильный» или в будущем будет изменён, выбирается как новый сосед. В результате Raise-переход идёт в Lower-состояние и распространяет обновлённую стоимость соседям. Потом возникают пульсации Lower-волн, за ними следуют Raise-внуи, пока не будет достигнута финальная коррекция стоимости.
Снизить частоту таких эффектов практически сложно; фокусировка метрики слишком ценна, чтобы ею пренебречь из-за подобных проблем. Допустимостью их тоже не устранить; даже глубокая проверка цепочки узлов не гарантирует отсутствие эффекта (а сильно замедляет расчёт).
Эвристика: для матрицы N×N проверка N/20 следующих узлов подавляет основную часть эффекта на первых 2/3 обрабатываемых точек.
Условия остановки
Скорость работы также повышается за счёт преждевременного останова, особенно при фокусирующей эвристике. Как и у A*, алгоритм можно завершить, когда стартовый узел расширен и — специфично для D* — он находится в Lower-состоянии (при чистой реализации). При этом OpenList нельзя очищать, иначе при появлении преграды маршруты в обход её будут не видны.
Однако, в отличие от A*, преждевременная остановка иногда замедляет реакцию D* на ошибку: полезнее заранее знать как можно больше альтернативных путей.
Многопоточность
Проблема остановки исчезает, если использовать платформу с поддержкой многопоточности. Обычно D* реализуется и применяется не ради «чистого интереса», а для управления роботами, агентами или целыми группами. При запуске устройств алгоритм запускается первым; чтобы не блокировать работу программы в ожидании, расчёт маршрута выносится в отдельный поток с высоким приоритетом. Это блокирует дополнительные задачи, отдавая все ресурсы поиску маршрута. Как только маршрут до стартовой точки найден (первая экспансия), другие потоки «уведомляются» о его наличии, а расчётный поток переводится на низший приоритет. Оставшиеся вычисления позволяют доработать карту (и найти все альтернативные пути) обычно до готовности устройства.
Аналогично — при пересчёте маршрута из-за появившейся преграды: вызывающий поток ждёт завершения поиска, а затем карта обрабатывается дальше, пока агент получает новые команды.
Области применения
Алгоритмы семейства D* (англ. D Star) и его популярные модификации, D* Lite и Field D*, являются фундаментальными инструментами для навигации автономных систем в динамических и частично неизвестных средах. Их способность быстро перепланировать маршрут при обнаружении новых препятствий без полного пересчёта всего пути делает их незаменимыми в широком спектre современных роботизированных систем.
D* Lite — это инкрементальный алгоритм, который является более простой и быстрой версией оригинального D*. Он эффективно обновляет путь робота по мере получения новой информации об окружении, корректируя только затронутые изменениями участки маршрута[17]. Основные области применения:
- Автономные наземные транспортные средства (AGV). D* Lite широко используется в складской логистике и на производстве, где роботы должны перемещаться в постоянно меняющихся условиях, избегая столкновений с людьми и другими объектами[18].
- Беспилотные летательные аппараты (БПЛА). В навигации БПЛА, особенно в сложных пространствах, D* Lite позволяет в реальном времени обходить препятствия. Алгоритм применяется как для отдельных дронов, так и для управления роем, обеспечивая их скоординированное движение[19][20].
- Подводная робототехника. Автономные подводные аппараты (АПА) применяют D* Lite для навигации в условиях ограниченной видимости, например, в мутной воде, и для обследования подводных структур[17].
Field D* является усовершенствованием D* Lite, ключевая особенность которого — использование линейной интерполяции для построения пути. В отличие от классических сеточных планировщиков, ограничивающих движение дискретными направлениями, Field D* позволяет прокладывать траектории под любым углом. Это приводит к созданию более коротких, плавных и естественных маршрутов, что снижает износ и энергопотребление робота[10]. Основные области применения:
- Планетарные и исследовательские роверы. Наиболее известным применением Field D* стала его интеграция в навигационную систему (англ. AutoNav) марсоходов НАСА «Спирит» и «Оппортьюнити» летом 2006 года[21]. Алгоритм позволил роверам строить более прямые и экономичные маршруты на поверхности Марса[21].
- Наземные роботы на пересечённой местности. Алгоритм эффективен для роботов, передвигающихся на открытом воздухе по сложным поверхностям с неоднородной стоимостью передвижения (например, асфальт, трава, грязь)[10].
- Воздушные и подводные аппараты. Существует трёхмерная версия (3D Field D*), разработанная для навигации БПЛА и подводных аппаратов в трёхмерном пространстве, где необходимо учитывать изменение высоты.
На практике D* Lite и Field D* часто комбинируются с локальными планировщиками, такими как англ. Dynamic Window Approach (DWA), где алгоритмы семейства D* отвечают за построение глобального маршрута, а локальный планировщик — за маневрирование с учётом кинематических ограничений робота.
Примечания
Ссылки
- Anthony Stentz: Оригинальная публикация (на англ.).