Алгоритм 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](s;s')[/math]. При этом [math]c(s, s') = +\infty[/math] будет тогда и только тогда, когда ребра [math](s;s')[/math] не существует.

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

Будем называть rhs-значением (right-hand side value) такую функцию , которая будет возвращать потенциальное минимальное расстояние от до по следующим правилам:

Так как rhs-значение использует минимальное значение из минимальных расстояний от до вершин, входящих в данную вершину , это будет нам давать информацию об оценочном расстоянии от до .

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

Вершина называется насыщенной (locally consistent), если

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

Вершина называется переполненной (locally overconsistent), если

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

Вершина называется ненасыщенной (locally underconsistent), если

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

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

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

Будем называть ключом вершины такую функцию , которая возвращает вектор из 2-ух значений , .

,

где - вершина из множества

Если в конце поиска пути [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);

Асимптотика

Теорема (О монотонности изменения ключей):

В течение выполнения функции ComputeShortestPath вершины, взятые из очереди, монотонно не убывают.

Доказательство:

Доказательство [1]

Теорема (О необратимой насыщенности):

Если в функции ComputeShortestPath была взята переполненная вершина, то на следующей итерации она станет насыщенной.

Доказательство:

Доказательство [2]

Теорема:

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

Доказательство:

Доказательство [3]

Таким образом мы описали алгоритм LPA*. Он вычисляет длину кратчайшего пути между вершинами [math]f[/math] и [math]t[/math], используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за [math]O(n \cdot m \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*. Информация о серых клетках ему неизвестна до тех пор, пока они не попадут в его зону обзора. В данном примере зона обзора составляет 1 клетку в 8-ми направлениях.

Описание

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

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

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

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

Эвристическая функция [math]h(s,s')[/math] теперь должна быть неотрицательная и обратно-устойчивая, т.е. [math]h(f,f) = 0[/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 [min(g(s),rhs(s)) + h(f,s); min(g(s),rhs(s))];

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

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

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

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

Асимптотика

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

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

Доказательство:

Доказательство [4]

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

Описание

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

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

Допустим, что после того, как робот продвинется вдоль найденного пути на предыдущих итерациях, из вершины s в s', он обнаружит изменения в графе. Первая компонента ключей [math]k_1(s')[/math] может уменьшится максимум на [math]h(s,s')[/math] (по определению ключа). Вторая компонента не зависит от функции h. Аналогично первой версии алгоритма, мы должны уменьшить первую компоненту ключа у всех вершин в очереди U. Очевидно, что [math]h(s,s')[/math] будет одинаковым для всех вершин из U. Порядок в очереди не изменится, если произвести уменьшение. Следовательно уменьшение можно отложить, тем самым очередь не придется перестраивать на каждой итерации. Так же исходя из нового определения функции h, её значение будет всегда меньше, чем разность первых компонент ключей у соседних по приоритету вершин. Таким образом мы можем добавлять h(s,s') ко всем [math]k_1(s')[/math] у ключей вершин из U.

Будем называть [math]K_m[/math] ключевым модификатором. В нем мы и будет хранить сумму h(s,s'), которые нужно добавить ко всем вершинам из U.

Псевдокод

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

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

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

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

 Main():
   [math]s_{last} = f[/math]
   Initialize();
   ComputeShortestPath();
   while (f [math]\ne[/math] t)
     // if (g(f) = [math]+\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 всех ориентированных ребер (u; v) с измененными весами:
         Обновляем результат функции c(u; v);
         UpdateVertex(u);
       ComputeShortestPath();

Асимптотика

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

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


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

Ссылки

Алгоритм D*

Алгоритм LPA*

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

Описание

Псевдокод

Асимптотика

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

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

Описание

Псевдокод

Асимптотика

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

Описание

Псевдокод

Асимптотика

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

Ссылки

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты