Просмотр кода страницы Алгоритм поиска D*

{{о|алгоритме поиска|спецификации цифрового протокола голоса и данных|D-STAR|субатомной частице|Гексакварк}}
'''Алгоритм поиска D*''' (произносится как ''«Ди стар»'') — это любой из трёх связанных {{нп5|Инкрементный эвристический поиск|алгоритмов инкрементного поиска||Incremental heuristic search}}:
* '''Оригинальный алгоритм D*'''<ref>{{cite journal|author=Энтони Стенц|title='''Оптимальное и эффективное планирование пути для частично известных сред'''
|journal=Материалы Международной конференции по робототехнике и автоматизации|year=1994|pages=3310–3317|citeseerx=10.1.1.15.3683}}</ref> Энтони Стенца — это информированный алгоритм инкрементного поиска.
* '''Сфокусированный D*'''<ref name="Stentz1995">{{cite journal|author=Э. Стенц|title='''Сфокусированный алгоритм D* для перепланирования в реальном времени'''
|journal=Материалы Международной совместной конференции по искусственному интеллекту|year=1995|pages=1652–1659|citeseerx=10.1.1.41.8257}}</ref> — это алгоритм инкрементного эвристического поиска, разработанный Энтони Стенцем, который сочетает в себе идеи '''[[A*]]'''<ref>{{cite journal|author=Питер Эллиот Харт, Нильс Джон Нильссон, Бертрам Рафаэль|title='''Формальная основа для эвристического определения путей минимальной стоимости'''|journal=Транзакции [[Институт инженеров электротехники и электроники|IEEE]] по системной науке и кибернетике|volume=SSC-4|issue=2|pages=100–107|date=1968|doi=10.1109/TSSC.1968.300136}}</ref> и '''оригинального D*'''. '''Сфокусированный D*''' возник в результате дальнейшего развития '''оригинального D*'''.
* '''Облегчённый D*'''<ref>{{cite journal|author=Свен Кёниг, Максим Лихачёв|title='''Быстрое перепланирование навигации в неизвестной местности'''
|journal=Транзакции по робототехнике|volume=21|issue=3|pages=354–363|date=2005|doi=10.1109/tro.2004.838026|citeseerx=10.1.1.65.5979}}</ref> — это алгоритм инкрементального эвристического поиска, созданный Свеном Кёнигом и Максимом Лихачёвым, который основан на '''LPA*'''<ref name="Koenig2004">{{cite journal
|author=Свен Кёниг, Максим Лихачёв, Дэвид Фёрси|title='''Пожизненное планирование A*'''|journal=Искусственный интеллект|volume=155|issue=1–2|pages=93–146
|date=2004|doi=10.1016/j.artint.2003.12.001|doi-access=free}}</ref>, алгоритме инкрементального эвристического поиска, объединяющем идеи [[A*|алгоритма поиска '''A*''']] и динамического '''SWSF-FP'''<ref>{{cite journal|author=Г. Рамалингам, Томас В. Репс|title='''Инкрементальный алгоритм обобщения задачи поиска кратчайшего пути'''|journal=Журнал алгоритмов|volume=21|issue=2|date=1996|pages=267–305|doi=10.1006/jagm.1996.0046|citeseerx=10.1.1.3.7926}}</ref>.

Все три алгоритма поиска решают одни и те же основанные на предположениях {{нп5|Планирование движения|планирования пути||Motion planning}} проблемы, включая планирование с предположением о свободном пространстве<ref>{{cite journal|author=Свен Кёниг, Юрий Смирнов, Крейг Тови|title='''Границы производительности для планирования на неизвестной местности'''|journal=Искусственный интеллект|volume=147|issue=1–2|pages=253–279|date=2003|doi=10.1016/s0004-3702(03)00062-6}}</ref>, когда робот должен перемещаться к заданным координатам цели на неизвестной местности. Он делает предположения о неизвестной части местности (например, что на ней нет препятствий) и находит кратчайший путь от её текущих координат до координат цели при этих предположениях. Затем робот следует по пути. Когда он наблюдает новую информацию на карте (например, ранее неизвестные препятствия), он добавляет эту информацию на свою карту и, при необходимости, перепланировывает новый кратчайший путь от текущих координат к заданным координатам цели. Он повторяет процесс до тех пор, пока не достигнет координат цели или не определит, что координаты цели не могут быть достигнуты. При пересечении неизвестной местности могут часто обнаруживаться новые препятствия, поэтому это перепланирование должно быть быстрым. '''''Инкрементальные (эвристические) алгоритмы поиска''''' ускоряют поиск последовательностей похожих поисковых задач, используя опыт решения предыдущих проблем для ускорения поиска текущей. Если предположить, что координаты цели не меняются, все три алгоритма поиска более эффективны, чем повторные поиски '''A*'''.

'''D*''' и его варианты широко использовались для [[Мобильный робототехнический комплекс|мобильного робота]] и [[Беспилотный автомобиль|автономного транспортного средства]] [[Навигация|навигации]]. Современные системы обычно основаны на '''облегчённом''', а не на '''оригинальном''' или '''сфокусированном D*'''. Фактически, даже лаборатория Стенца в некоторых реализациях использует '''облегчённый''', а не '''оригинальный D*'''<ref>{{cite thesis|author=D. Wooden
|title='''Планирование пути для мобильных роботов на основе графов'''|publisher=[[Технологический институт Джорджии]]|date=2006}}</ref>. Такие навигационные системы включают в себя прототип системы, испытанный на марсоходах [[Оппортьюнити|Opportunity]] и [[Спирит (марсоход)|Spirit]], и навигационную систему победителя конкурса '''''DARPA Urban Challenge''''', оба разработанные в [[Университет Карнеги — Меллона|Университете Карнеги — Меллона]].

'''Оригинальный D*''' был представлен Энтони Стенцем в [[1994 год]]у. Название '''D*''' происходит от термина ''«'''D'''ynamic '''A*'''»'' ([[Русский язык|рус.]] ''«'''Д'''инамический '''A*'''»''), потому что алгоритм ведёт себя как '''A*'''<ref name="Stentz1995"/>, за исключением того, что стоимость дуги может изменяться по мере выполнения алгоритма.

== Операции ==
Основные операции '''D*''' описаны ниже.

Подобно [[Алгоритм Дейкстры|алгоритму Дейкстры]] и '''A*''', '''D*''' поддерживает список узлов для оценки, известный как '''ОТКРЫТЫЙ список'''. Узлы помечаются как имеющие одно из нескольких состояний:
* '''НОВЫЙ''', означает, что он никогда не помещался в '''ОТКРЫТЫЙ список'''.
* '''ОТКРЫТЫЙ''', означает, что он в настоящее время находится в '''ОТКРЫТОМ списке'''.
* '''ЗАКРЫТЫЙ''', означает, что его больше нет в '''ОТКРЫТОМ списке'''.
* '''ПОДНЯТЫЙ''', указывает на то, что его стоимость выше, чем в последний раз, когда он был в '''ОТКРЫТОМ списке'''.
* '''НИЖНИЙ''', указывает на то, что его стоимость ниже, чем в последний раз, когда он был в '''ОТКРЫТОМ списке'''.

=== Расширение ===
Алгоритм работает путём итеративного выбора узла из '''ОТКРЫТОГО списка''' и его оценки. Затем он распространяет изменения узла на все соседние узлы и помещает их в '''ОТКРЫТЫЙ список'''. Этот процесс распространения называется ''«расширением»''. В отличие от канонического '''A*''', который следует по пути от начала до конца, '''D*''' начинает поиск в обратном направлении от целевого узла. Каждый расширенный узел имеет обратный указатель, который относится к следующему узлу, ведущему к цели, и каждый узел знает точную стоимость для цели. Когда начальный узел является следующим расширяемым узлом, алгоритм выполнен, и путь к цели можно найти, просто следуя обратным указателям.

<gallery>
   D*-Algorithmus Expand.png|Расширение в процессе. Финишный узел (жёлтый) находится в середине верхнего ряда точек, начальный узел находится в середине нижнего ряда. Красный указывает на препятствие; чёрный/синий обозначает расширенные узлы (яркость обозначает стоимость). Зелёным обозначены узлы, которые расширяются.
   D*-Algorithmus Expand One.png|Расширение завершено. Путь указан голубым цветом.
</gallery>

=== Преодоление препятствий ===
Когда на заданном пути обнаруживается препятствие, все затронутые точки снова помещаются в '''ОТКРЫТЫЙ список''', на этот раз с пометкой '''ПОДНЯТЫЙ'''. Однако перед увеличением стоимости '''ПОДНЯТОГО узла''' алгоритм проверяет его соседей и исследует, может ли он снизить стоимость узла. В противном случае состояние '''ПОДНЯТЫЙ''' распространяется на всех потомков узлов, то есть узлы, на которые есть обратные указатели. Затем эти узлы оцениваются, и состояние '''ПОДНЯТЫЙ''' передаётся, формируя волну. Когда '''ПОДНЯТЫЙ узел''' может быть уменьшен, его обратный указатель обновляется и передаёт состояние '''НИЖНИЙ''' своим соседям. Эти волны состояний '''ПОДНЯТЫЙ''' и '''НИЖНИЙ''' являются сердцем '''D*'''.

К этому моменту волны не могут ''коснуться'' целого ряда других точек. Следовательно, алгоритм работал только с точками, на которые влияет изменение стоимости.

<gallery>
   D*-Algorithmus Blockade One.png|Препятствие добавлено (красный) и узлы отмечены как '''ПОДНЯТЫЕ''' (жёлтый).
   D*-Algorithmus Blockade One Running.png|Расширение в процессе. Жёлтым цветом обозначены узлы, отмеченные как '''ПОДНЯТЫЕ''', зелёным — узлы, отмеченные как '''НИЖНИЕ'''.
</gallery>

=== Ещё один тупик ===
На этот раз невозможно так элегантно выйти из тупика. Ни одна из точек не может найти новый маршрут через соседа к пункту назначения. Поэтому они продолжают распространять своё повышение стоимости. Можно найти только точки за пределами канала, которые могут привести к месту назначения по жизнеспособному маршруту. Так развиваются две '''НИЖНИЕ''' волны, которые расширяются в виде точек, отмеченных как недостижимые с новой информацией о маршруте.

<gallery>
   D*-Algorithmus Blockade Two.png|Канал заблокирован дополнительными препятствиями (красный).
   D*-Algorithmus Blockade Two running one.png|Расширение в процессе. '''ПОДНЯТАЯ''' волна (жёлтый), '''НИЖНЯЯ''' волна (зелёный).
   D*-Algorithmus Blockade Two running two.png|Найден '''НОВЫЙ''' путь (голубой).
</gallery>

== Псевдокод ==
<syntaxhighlight lang="java">
while (!openList.isEmpty()) {
    point = openList.getFirst();
    expand(point);
}
</syntaxhighlight>

=== Развернуть ===
<syntaxhighlight lang="java">
void expand(currentPoint) {
    boolean isRaise = isRaise(currentPoint);
    double cost;
    for each (neighbor in currentPoint.getNeighbors()) {
        if (isRaise) {
            if (neighbor.nextPoint == currentPoint) {
                neighbor.setNextPointAndUpdateCost(currentPoint);
                openList.add(neighbor);
            } else {
                cost = neighbor.calculateCostVia(currentPoint);
                if (cost < neighbor.getCost()) {
                    currentPoint.setMinimumCostToCurrentCost();
                    openList.add(currentPoint);
                }
            }
        } else {
            cost = neighbor.calculateCostVia(currentPoint);
            if (cost < neighbor.getCost()) {
                neighbor.setNextPointAndUpdateCost(currentPoint);
                openList.add(neighbor);
            }
        }
    }
}
</syntaxhighlight>

=== Проверить на поднятие ===
<syntaxhighlight lang="java">
boolean isRaise(point) {
    double cost;
    if (point.getCurrentCost() > point.getMinimumCost()) {
        for each(neighbor in point.getNeighbors()) {
            cost = point.calculateCostVia(neighbor);
            if (cost < point.getCurrentCost()) {
                point.setNextPointAndUpdateCost(neighbor);
            }
        }
    }
    return point.getCurrentCost() > point.getMinimumCost();
}
</syntaxhighlight>

== Варианты ==

=== Сфокусированный D* ===
Как следует из названия, '''сфокусированный D*''' является расширением '''D*''', которое использует эвристику, чтобы сфокусировать распространение '''ПОДНЯТОГО''' и '''НИЖНЕГО''' в направлении робота. Таким образом, обновляются только важные состояния, так же как '''A*''' вычисляет затраты только для некоторых узлов.

=== Облегчённый D* ===
'''Облегчённый D*''' не основан на исходном или '''сфокусированном D*''', но реализует то же поведение. Это проще для понимания и может быть реализовано меньшим количеством строк кода, отсюда и название '''«Облегчённый D*»'''. По производительности он не хуже '''сфокусированного D*'''. '''Облегчённый D*''' основан на '''LPA*'''<ref name="Koenig2004"/>, который был представлен Кёнигом и Лихачёвым несколькими годами ранее.
[http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf '''Облегчённый D*''']

== Минимальная стоимость по сравнению с текущей стоимостью ==
Для '''D*''' важно различать текущие и минимальные затраты. Первые важны только во время сбора, а последние решающие, потому что они сортируют '''ОТКРЫТЫЙ список'''. Функция, которая возвращает минимальную стоимость, всегда является наименьшей стоимостью для текущей точки, поскольку это первая запись в '''ОТКРЫТОМ списке'''.

== Примечания ==
{{примечания}}

== Ссылки ==
* [http://idm-lab.org/project-a.html Веб-страница Свена Кёнига]
* [https://web.archive.org/web/20161120074915/http://www.frc.ri.cmu.edu/~axs/dynamic_plan.html Веб-страница Энтони Стенца]

{{Алгоритмы поиска на графах}}

[[Категория:Робототехника]]
[[Категория:Алгоритмы поиска]]
[[Категория:Алгоритмы на графах]]