Алгоритм 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 всех ориентированных ребер [math](u, v)[/math] с измененными весами:
         Обновляем результат функции [math]c(u, v)[/math]
         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] не должны быть обязательно смежными. Такие свойства не противоречат свойствами из первой версии, а лишь усиливают их.

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

Будем называть [math]K_m[/math] ключевым модификатором. В нем мы и будет хранить сумму [math]h(s,s')[/math], которые нужно добавить ко всем вершинам из 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* (Вторая версия)

Описание

Псевдокод

Асимптотика

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

Ссылки

Навигация

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

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

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты