Алгоритм D*

2014-01-04T14:04:46Z

95.55.188.216:

'''Алгоритм D*''' {{---}} алгоритм поиска кратчайшего пути во взвешенном ориентированном графе, где структура графа неизвестна заранее или постоянно подвергается изменению. Разработан Свеном Кёнигом и Максимом Лихачевым в 2002 году.

== Алгоритм LPA* ==

=== Постановка задачи ===
Дан [[Основные определения теории графов|взвешенный ориентированный граф]] <tex> G(V, E) </tex>. Даны вершины <tex>s_{start}</tex> и <tex>s_{goal}</tex>. Требуется после каждого изменения графа <tex>G</tex> уметь вычислять функцию <tex>g(s)</tex> для каждой известной вершины <tex>s \in V</tex>

=== Описание ===
Функция <tex>g(s)</tex> будет возвращать последнее известное (и самое минимальное) значение расстояния от вершины <tex>s_{start}</tex> до <tex>s</tex>.

Обозначим множество <tex>Succ(s) \in V</tex> как множество вершин, исходящих из вершины <tex>s</tex>.

Аналогично множество <tex>Pred(s) \in V</tex> как множество вершин, входящих в вершину <tex>s</tex>.

Функция <tex>0 \leqslant c(s, s') \leqslant +\infty</tex> будет возвращать стоимость перехода из вершины <tex>s</tex> в вершину <tex>s'</tex>. При этом <tex>s' \in Succ(s)</tex>.

Если <tex>s = s_{start}</tex>
:<tex dpi="120">rhs(s) = 0</tex>
Иначе
:<tex dpi="120">rhs(s) = min_{s' \in Pred(s)}(g(s') + c(s', s)</tex>

Вершина <tex>s</tex> может быть 3-х видов:
* насыщена, если <tex>g(s) = rhs(s)</tex>
* переполнена, если <tex>g(s) > rhs(s)</tex>
* ненасыщена, если <tex>g(s) < rhs(s)</tex>

Очевидно, что если все вершины насыщены, то мы можем найти расстояние от стартовой вершины до любой. Такой граф будем называть устойчивым (насыщенным).

Функция <tex>key(s)</tex>, где <tex>s</tex> - вершина, возвращает вектор из 2-ух значений <tex>k_1(s)</tex>, <tex>k_2(s)</tex>.
* <tex>k_1(s) = min(g(s), rhs(s)) + h(s, s_{goal})</tex>.
* <tex>k_2(s) = min(g(s), rhs(s))</tex>.

Если в конце поиска пути <tex>g(s_{goal}) = +\infty</tex>, то мы не смогли найти путь от <tex>s_{start}</tex> до <tex>s_{goal}</tex> на текущей итерации. Но после следующего изменения графа путь вполне может найтись.

=== Псевдокод ===

Основная функция, описывающая алгоритм
'''Main'''():
{
'''Initialize'''();
while (true)
{
'''ComputeShortestPath'''();
В данный момент мы знаем кратчайший путь из <tex>s_{start}</tex> в <tex>s_{goal}</tex>.
Ждем каких-либо изменений графа.
for всех ориентированных ребер <tex>(u; v)</tex> с измененными весами:
{
Обновляем результат функции <tex>c(u; v)</tex>;
'''UpdateVertex'''(<tex>v</tex>);
}
}
}

Теперь опишем составные элементы подробнее

'''Initialize'''():
{
//Заведем приоритетную очередь <tex>U</tex>, в которую будем помещать вершины. Сортировка будет производиться по функции <tex>key(s)</tex>.
<tex>U = \varnothing;</tex>
for <tex>s \in S</tex>
<tex>rhs(s) = g(s) = \infty;</tex>
<tex>rhs(s_{start}) = 0;</tex>
U.Insert(<tex>s_{start}</tex>; CalcKey(<tex>s_{start}</tex>));
}

//Функция <tex>key(s)</tex>. Возвращаемые значения сортируются в лексографическом порядке, т.е. сначала <tex>k_1(s)</tex>, потом <tex>k_2(s)</tex>
'''CalcKey'''(s):
{
return [<tex>\min(g(s); rhs(s)) + h(s; s_{goal})</tex>; <tex>\min(g(s); rhs(s))</tex>];
}

'''UpdateVertex'''(<tex>u</tex>):
{
if (<tex>u \ne s_{start}</tex>)
<tex>rhs(u) = min_{s' \in Pred(u)}(g(s') + c(s',u));</tex>
if (<tex>u \in U</tex>)
U.Remove(u);
if (<tex>g(u) \ne rhs(u)</tex>)
U.Insert(<tex>u</tex>; CalcKey(<tex>u</tex>));
}

// Функция неоднократно перерасчитывает значение <tex>g(s)</tex> у ненасыщенных вершин. Такой перерасчет значения <tex>g(s)</tex> будем называть ''расширением'' вершины.
'''ComputeShortestPath'''():
{
while (U.TopKey() < CalcKey(<tex>s_{goal}</tex>) OR rhs(<tex>s_{goal}) \ne g(s_{goal}</tex>))
u = U.Pop();
if (g(u) > rhs(u))
g(u) = rhs(u);
for <tex>s \in Succ(u)</tex>
UpdateVertex(s);
else
g(u) = <tex>+\infty</tex>;
for <tex>s \in Succ(u) \cup \{u\}</tex>
UpdateVertex(s);
}

Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь между вершинами <tex>s_{start}</tex> и <tex>s_{goal}</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за <tex>O(n^2 \cdot log(n))</tex>. Улучшим эту оценку с помощью алгоритма D* lite.

'''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку <tex>O(n \cdot log(n))</tex>.

== Алгоритм D* ==
Пока что был описан только алгоритм LPA*. Он способен неоднократно определять кратчайшее расстояние между начальной и конечной вершинами при любом изменении данного графа. Его первоначальный поиск полностью совпадает с алгоритмом A*, но последующие итерации способны использовать информацию из предыдущих поисков.

=== Постановка задачи ===
Теперь на основе LPA* опишем алгоритм D*, который способен определять расстояние между текущей вершиной <tex>s_{start}</tex>, в которой, допустим, находится курсор/робот, и конечной вершиной <tex>s_{goal}</tex> при каждом изменении графа в то время, как наш робот движется вдоль найденного пути.

=== Описание ===
Опишем первую версию алгоритма D*. Очевидно, что большинство вершин в процессе движения робота остаются неизменными, поэтому мы можем применить алгоритм LPA*.

'''Примечание''': Большинство функций переходят в данный алгоритм без изменений, поэтому опишем только измененные части.

Для начала мы поменяем направление поиска в графе.

Теперь функция g(s) хранит минимальное известное расстояние от <tex>s_{goal}</tex> до <tex>s</tex>. Свойства остаются прежними.

Эвристическая функция h(s,s') теперь должна быть неотрицательная и обратно-устойчивая, т.е.
<tex>h(s_{start},s_{start}) = 0</tex> и <tex>h(s_{start}, s) <= h(s_{start},s') + c(s',s)</tex> для всех <tex>s \in S</tex> и <tex>s' \in Pred(s)</tex>. Очевидно, что при движении робота <tex>s_{start}</tex> изменяется, поэтому данные свойства должны выполняться для всех <tex>s_{start} \in S</tex>.

Дополнительное условие выхода также меняется, т.е. при <tex>g(s_{start}) = +\infty</tex> путь не найден на данной итерации. Иначе путь найден и робот может проследовать по нему.

'''Примечание''': Так же следует отметить, что функция '''Initialize''' не обязана инициализировать абсолютно все вершины перед стартом алгоритма. Это важно, так как в на практике число вершин может быть огромным и только немногие будут пройдены робот в процессе движения. Так же это дает возможность добавления/удаления ребер без потери устойчивости всех подграфов данного графа.

=== Псевдокод (Первая версия) ===
При такой постановке задачи псевдокод не сильно меняется. Но функция '''Main''' все-таки претерпевает значительные изменения.

'''CalcKey'''(s):
return [<tex>\min(g(s);rhs(s)) + h(s_{start};s)</tex>;<tex>\min(g(s); rhs(s))</tex>];

'''Initialize'''():
U = <tex>\varnothing</tex>;
for <tex>s \in S</tex>
<tex>rhs(s) = g(s) = +\infty</tex>
<tex>rhs(s_{goal}) = 0</tex>
U.Insert(<tex>s_{goal}</tex>; CalcKey(<tex>s_{goal}</tex>));

'''UpdateVertex'''(u):
if (<tex>u \ne s_{goal}</tex>)
rhs(u) = <tex>min_{s' \in Succ(u)}(c(u,s')+g(s'));</tex>
if (<tex>u \in U</tex>)
U.Remove(u);
if (<tex>g(u) \ne rhs(u)</tex>)
U.Insert(u; CalcKey(u));

'''ComputeShortestPath'''():
while (U.TopKey() < CalcKey(<tex>s_{start}</tex>) OR <tex>rhs(s_{start}) \ne g(s_{start})</tex>)
u = U.Pop();
if (g(u) > rhs(u))
g(u) = rhs(u);
for <tex>s \in Pred(u)</tex>
UpdateVertex(s);
else
g(u) = <tex>+\infty</tex>;
for <tex>s \in Pred(u) \cup \{u\}</tex>
UpdateVertex(s);

'''Main'''():
'''Initialize'''();
'''ComputeShortestPath'''();
while (<tex>s_{start} \ne s_{goal}</tex>)
// if (<tex>g(s_{start}) = \infty</tex>) тогда путь на данной итерации не найден.
<tex>s_{start}</tex> = такая вершина s', что <tex>min_{s' \in Succ(s_{start})}(c(s_{start}, s') + g(s'))</tex>
Передвинулись вдоль найденного пути и изменили вершину <tex>s_{start}</tex>;
Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним.
if (если граф изменился)
for всех ориентированных ребер <tex>(u; v)</tex> с измененными весами:
Обновляем результат функции <tex>c(u; v)</tex>;
'''UpdateVertex'''(u);
for <tex>s \in U</tex>
U.Update(<tex>s</tex>; '''CalcKey'''(<tex>s</tex>));
ComputeShortestPath();

{{Теорема
|author=Свен Кёниг
|about=Об устойчивой насыщенности вершин
|statement=Функция '''ComputeShortestPath''' в данной версии алгоритма ''расширяет'' вершину максимум 2 раза, а именно 1 раз, если вершина ненасыщена, и максимум 1 раз, если она перенасыщена.
}}

==Ссылки==
* [http://en.wikipedia.org/wiki/D* Wikipedia:D*]
* [http://idm-lab.org/project-a.html Sven Koenig` web page]
* [http://pub1.willowgarage.com/~konolige/cs225b/dlite_tro05.pdf]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах ]]

Викиконспекты - Вклад участника [ru]

Алгоритм D*