Алгоритм D*

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

Алгоритм LPA*

Постановка задачи

Дан взвешенный ориентированный граф [math] G(V, E) [/math]. Даны вершины: стартовая вершина [math]f[/math] и конечная вершина [math]t[/math]. Требуется после каждого изменения графа [math]G[/math] уметь вычислять функцию [math]g(s)[/math] для каждой известной вершины [math]s \in V[/math]

Описание

Функция [math]g(s)[/math] будет возвращать наименьшую стоимость пути из вершины [math]f[/math] в [math]s[/math]. Её значение для алгоритма будет почти аналогичным значению в алгоритме A*, за исключением того, что в данном алгоритме наc интересуют только [math]g(s)[/math]-значения известных вершин на данной итерации.

Будем поддерживать для каждой вершины два вида смежных с ней вершин:

• Обозначим множество [math]Succ(s) \subseteq V[/math] как множество вершин, исходящих из вершины [math]s[/math].
• Обозначим множество [math]Pred(s) \subseteq V[/math] как множество вершин, входящих в вершину [math]s[/math].

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

Определение:

Будем называть rhs-значением (right-hand side value) такую функцию [math]rhs(s)[/math], которая будет возвращать потенциальное минимальное расстояние от [math]f[/math] до [math]s[/math] по следующим правилам: [math]rhs(s) = \begin{cases} 0,& \text{if } s = f \\ \min\limits_{s' \in Pred(s)}(g(s') + c(s', s),& \text{otherwise} \end{cases} [/math] Так как rhs-значение использует минимальное значение из минимальных расстояний от [math]f[/math] до вершин, входящих в данную вершину [math]s[/math], это будет нам давать информацию об оценочном расстоянии от [math]f[/math] до [math]s[/math].

Определение:

Вершина [math]s[/math] называется насыщенной (locally consistent), если [math]g(s) = rhs(s)[/math]

Определение:

Вершина [math]s[/math] называется переполненной (locally overconsistent), если [math]g(s) \gt rhs(s)[/math]

Определение:

Вершина [math]s[/math] называется ненасыщенной (locally underconsistent), если [math]g(s) \lt rhs(s)[/math]

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

Эвристическая функция [math]h(s,s')[/math] теперь должна быть неотрицательная и выполнять неравенство треугольника, т.е. [math]h(t,t) = 0[/math] и [math]h(s, t) \leqslant c(s,s') + h(s',t)[/math] для всех [math]s \in V[/math] и [math]s' \in Succ(s)[/math]

Определение:

Будем называть ключом вершины такую функцию [math]key(s)[/math], которая возвращает вектор из 2-ух значений [math]k_1(s)[/math], [math]k_2(s)[/math]. [math]k_1(s) = \min(g(s), rhs(s)) + h(s, t)[/math] [math]k_2(s) = \min(g(s), rhs(s))[/math], где [math]s[/math] - вершина из множества [math]V[/math]

Если в конце поиска пути [math]g(t) = +\infty[/math], то мы не смогли найти путь от [math]f[/math] до [math]t[/math] на текущей итерации. Но после следующего изменения графа путь вполне может найтись.

Псевдокод

Основная функция, описывающая алгоритм

 Main():
   Initialize();
   while (true)
     ComputeShortestPath();
     //В данный момент мы знаем кратчайший путь из f в t.
     Ждем каких-либо изменений графа.
     for всех ориентированных ребер (u; v) с измененными весами:
       Обновляем результат функции c(u; v);
       UpdateVertex(v);

Теперь опишем составные элементы подробнее Функция инициализации исходного графа устанавливает для всех вершин кроме стартовой ([math]f[/math]) значения [math]g(s)[/math] и [math]rhs(s)[/math] равными бесконечности. Для стартовой [math]rhs(f)=0[/math]. Очевидно, что минимальное расстояние от стартовой вершины до самой себя должно быть равным 0, но [math]g(f)=+\infty[/math]. Это сделано для того, чтобы стартовая вершина была ненасыщенной и имела право попасть в приоритетную очередь.

 Initialize():
   //Заведем приоритетную очередь U, в которую будем помещать вершины. Сортировка будет производиться по функции key(s).
   U = [math]\varnothing[/math];
   for s [math]\in[/math] V
     rhs(s) = g(s) = [math]\infty;[/math]
   rhs(f) = 0;
   U.Insert(f; CalcKey(f));

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

 // Обновляет данные вершины в соответствие с данными выше определениями. Также поддерживает инвариант того, что в очереди U лежат только ненасыщенные вершины.
 UpdateVertex(u):
   if u [math]\ne[/math] f
     [math]rhs(u) = \min\limits_{s' \in Pred(u)}(g(s') + c(s',u));[/math]
   if u [math]\in[/math] U
     U.Remove(u);
   if g(u) [math]\ne[/math] rhs(u)
     U.Insert(u; CalcKey(u));

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

Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь между вершинами [math]f[/math] и [math]t[/math], используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за [math]O(n^2 \cdot \log(n))[/math]. Улучшим эту оценку с помощью алгоритма D* lite.

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

Алгоритм D* (Первая версия)

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

Постановка задачи

Дан взвешенный ориентированный граф [math] G(V, E) [/math]. Даны вершины [math]f[/math] и [math]t[/math]. Требуется в процессе движения по кратчайшему пути в графе [math]G[/math] обновлять значения функции [math]g(s)[/math] при поступлении новой информации о графе [math]G[/math].

Теперь на основе LPA* опишем алгоритм D*, который способен определять расстояние между текущей вершиной [math]f[/math], в которой, допустим, находится способный к сканированию местности "робот", и конечной вершиной [math]t[/math] при каждом изменении графа в то время, как наш "робот" движется вдоль найденного пути.

Схема движения "робота" в процессе работы алгоритма D*. Информация о серых клетках ему неизвестна до определенной итерации.

Описание

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

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

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

Теперь функция g(s) хранит минимальное известное расстояние от [math]t[/math] до [math]s[/math]. Свойства остаются прежними.

Эвристическая функция [math]h(s,s')[/math] теперь должна быть неотрицательная и обратно-устойчивая, т.е. [math]h(f,f) = 0[/math] и [math]h(f, s) \leqslant h(f,s') + c(s',s)[/math] для всех [math]s \in S[/math] и [math]s' \in Pred(s)[/math]. Очевидно, что при движении робота [math]f[/math] изменяется, поэтому данные свойства должны выполняться для всех [math]f \in V[/math].

Дополнительное условие выхода также меняется, т.е. при [math]g(f) = +\infty[/math] путь не найден на данной итерации. Иначе путь найден и "робот" может проследовать по нему.

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

Псевдокод

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

 CalcKey(s):
   return [[math]\min(g(s);rhs(s)) + h(f;s)[/math];[math]\min(g(s); rhs(s))[/math]];

 Initialize():
   U = [math]\varnothing[/math];
   for [math]s \in S[/math]
     [math]rhs(s) = g(s) = +\infty[/math]
   [math]rhs(t) = 0[/math]
   U.Insert([math]t[/math]; CalcKey([math]t[/math]));

 UpdateVertex(u):
   if ([math]u \ne t[/math]) 
     rhs(u) = [math]\min\limits_{s' \in Succ(u)}(c(u,s')+g(s'));[/math]
   if ([math]u \in U[/math]) 
     U.Remove(u);
   if ([math]g(u) \ne rhs(u)[/math]) 
     U.Insert(u; CalcKey(u));

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

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

Теорема (Свен Кёниг, Об устойчивой насыщенности вершин):

Функция ComputeShortestPath в данной версии алгоритма расширяет вершину максимум 2 раза, а именно 1 раз, если вершина ненасыщена, и максимум 1 раз, если она переполнена.

Алгоритм D* (Вторая версия)

Описание

В первой версии алгоритма была серьезная проблема в том, что для каждой вершины в приоритетной очереди нужно было обновлять ключ суммарно за [math]O(n \cdot \log(n))[/math]. Это дорогая операция, так как очередь может содержать огромное число вершин. Воспользуемся оригинальным методом поиска и изменим основной цикл, чтобы избежать постоянного перестроения очереди [math]U[/math].

Теперь эвристическая функция должна поддерживать неравенство треугольника для всех вершин [math]s,s',s'' \in V[/math], т.е. [math]h(s,s'') \leqslant h(s, s') + h(s',s'')[/math]. Так же должно выполняться свойство [math]h(s,s') \leqslant c^*(s,s')[/math], где [math]c^*(s,s')[/math] - стоимость перехода по кратчайшему пути из [math]s[/math] в [math]s'[/math], при этом [math]s[/math] и [math]s'[/math] не должны быть обязательно смежными. Такие свойства не противоречат свойствами из первой версии, а лишь усиливают их.

Псевдокод

 CalcKey(s):
   return [[math]\min(g(s);rhs(s)) + h(f;s) + K_m[/math];[math]\min(g(s); rhs(s))[/math]];

 Initialize():
   U = [math]\varnothing[/math];
   [math]K_m = 0[/math]
   for [math]s \in S[/math]
     [math]rhs(s) = g(s) = +\infty[/math]
   [math]rhs(t) = 0[/math]
   U.Insert([math]t[/math]; CalcKey([math]t[/math]));

 UpdateVertex(u):
   if ([math]u \ne t[/math]) 
     rhs(u) = [math]\min\limits_{s' \in Succ(u)}(c(u,s')+g(s'));[/math]
   if ([math]u \in U[/math]) 
     U.Remove(u);
   if ([math]g(u) \ne rhs(u)[/math]) 
     U.Insert(u; CalcKey(u));

 ComputeShortestPath():
   while (U.TopKey() < CalcKey([math]f[/math]) OR [math]rhs(f) \ne g(f)[/math])
     [math]K_{old} = U.TopKey()[/math];
     u = U.Pop();
     
     if ([math]K_{old}[/math] < CalcKey([math]u[/math]))
       U.Insert([math]u[/math]; CalcKey([math]u[/math]));
     
     if (g(u) > rhs(u))
       g(u) = rhs(u);
       for [math]s \in Pred(u)[/math] 
         UpdateVertex(s);
     else
       g(u) = [math]+\infty[/math];
       for [math]s \in Pred(u) \cup \{u\}[/math] 
         UpdateVertex(s);

 Main():
   [math]s_{last} = f[/math]
   Initialize();
   ComputeShortestPath();
   while ([math]f \ne t[/math])
     // if ([math]g(f) = \infty[/math]) тогда путь на данной итерации не найден.
     [math]f[/math] = такая вершина s', что [math]\min\limits_{s' \in Succ(f)}(c(f, s') + g(s'))[/math]
     Передвинулись вдоль найденного пути и изменили вершину [math]f[/math];
     Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним.
     if (граф изменился)
       [math]K_m = K_m + h(s_{last}, h_{start})[/math];
       [math]s_{last} = f[/math];
       for всех ориентированных ребер [math](u; v)[/math] с измененными весами:
         Обновляем результат функции [math]c(u; v)[/math];
         UpdateVertex(u);
       ComputeShortestPath();

Пример работы

Итерации в функции ComputeShortestPath на исходном графе.	Итерации в функции ComputeShortestPath после изменения графа. (Второй вызов функции)

Ссылки

• Wikipedia:D*
• Sven Koenig` web page
• LPA*
• D* lite