Алгоритм D*

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

Алгоритм LPA*

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

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

Описание

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

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

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

Ясно, что обязано соблюдаться условие: [math]Succ(s) \subseteq V[/math] и [math]Pred(s) \subseteq V[/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]s_{start}[/math] до [math]s[/math] по следующим правилам: [math]rhs(s) = \begin{cases} 0,& \text{if } s = s_{start} \\ min_{s' \in Pred(s)}(g(s') + c(s', s),& \text{otherwise} \end{cases} [/math] Так как rhs-значение использует минимальное значение из минимальных расстояний от [math]s_{start}[/math] до вершин, входящих в данную вершину [math]s[/math], это будет нам давать информацию об оценочном расстоянии от [math]s_{start}[/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(s_{goal},s_{goal}) = 0[/math] и [math]h(s, s_{goal}) \leqslant c(s,s') + h(s',s_{goal})[/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, s_{goal})[/math] [math]k_2(s) = \min(g(s), rhs(s))[/math], где [math]s[/math] - вершина из множества [math]V[/math]

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

Псевдокод

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Описание

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

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

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

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

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

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

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

Псевдокод

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

 CalcKey(s):
   return [[math]\min(g(s);rhs(s)) + h(s_{start};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(s_{goal}) = 0[/math]
   U.Insert([math]s_{goal}[/math]; CalcKey([math]s_{goal}[/math]));

 UpdateVertex(u):
   if ([math]u \ne s_{goal}[/math]) 
     rhs(u) = [math]min_{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]s_{start}[/math]) OR [math]rhs(s_{start}) \ne g(s_{start})[/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]s_{start} \ne s_{goal}[/math])
     // if ([math]g(s_{start}) = \infty[/math]) тогда путь на данной итерации не найден.
     [math]s_{start}[/math] = такая вершина s', что [math]min_{s' \in Succ(s_{start})}(c(s_{start}, s') + g(s'))[/math]
     Передвинулись вдоль найденного пути и изменили вершину [math]s_{start}[/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(s_{start};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(s_{goal}) = 0[/math]
   U.Insert([math]s_{goal}[/math]; CalcKey([math]s_{goal}[/math]));

 UpdateVertex(u):
   if ([math]u \ne s_{goal}[/math]) 
     rhs(u) = [math]min_{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]s_{start}[/math]) OR [math]rhs(s_{start}) \ne g(s_{start})[/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} = s_{start}[/math]
   Initialize();
   ComputeShortestPath();
   while ([math]s_{start} \ne s_{goal}[/math])
     // if ([math]g(s_{start}) = \infty[/math]) тогда путь на данной итерации не найден.
     [math]s_{start}[/math] = такая вершина s', что [math]min_{s' \in Succ(s_{start})}(c(s_{start}, s') + g(s'))[/math]
     Передвинулись вдоль найденного пути и изменили вершину [math]s_{start}[/math];
     Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним.
     if (граф изменился)
       [math]K_m = K_m + h(s_{last}, h_{start})[/math];
       [math]s_{last} = s_{start}[/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