Алгоритм D* — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (links)
м (Ссылки)
 
(не показано 49 промежуточных версий 3 участников)
Строка 1: Строка 1:
D* (pronounced "D star") is any one of the following three related incremental search algorithms.
+
'''Алгоритм D*''' {{---}} алгоритм поиска кратчайшего пути во [[Основные определения теории графов|взвешенном ориентированном графе]], где структура графа неизвестна заранее или постоянно подвергается изменению. Разработан Свеном Кёнигом и Максимом Лихачевым в 2002 году.
  
LPA*
+
== Алгоритм LPA* ==
Обозначим множество <tex>S</tex> как множество вершин графа.
 
Обозначим множество <tex>Succ(s) \in S</tex> как множество вершин, исходящих из вершины <tex>s</tex>.
 
Аналогично множество <tex>Pred(s) \in S</tex> как множество вершин, входящих в вершину <tex>s</tex>.
 
  
Функция <tex>0 <= с(s, s') <= +inf</tex> будет возвращать перехода из вершины <tex>s</tex> в вершину <tex>s'</tex>. При этом <tex>s' \in Succ(s)</tex>.
+
=== Постановка задачи ===
 +
Дан [[Основные определения теории графов|взвешенный ориентированный граф]] <tex> G(V, E) </tex>. Даны вершины: стартовая вершина <tex>f</tex> и конечная вершина <tex>t</tex>. Требуется после каждого изменения графа <tex>G</tex> уметь вычислять функцию <tex>g(s)</tex> для каждой известной вершины <tex>s \in V</tex>
  
Функция <tex>g(s) будет возвращать последнее известное значение расстояние от вершины <tex>s_{start}</tex> до <tex>s</tex>.
+
=== Описание ===
 +
Функция <tex>g(s)</tex> будет возвращать наименьшую стоимость пути из вершины <tex>f</tex> в <tex>s</tex>. Её значение для алгоритма будет почти аналогичным значению в [[Алгоритм A* | алгоритме A*]], за исключением того, что в данном алгоритме наc интересуют только <tex>g(s)</tex>-значения известных вершин на данной итерации.
  
Если <tex>s = s_{start}</tex>
+
Будем поддерживать для каждой вершины два вида смежных с ней вершин:
<tex>rhs(s) = 0</tex>
+
* Обозначим множество <tex>Succ(s) \subseteq V</tex> как множество вершин, исходящих из вершины <tex>s</tex>.
Иначе
+
* Обозначим множество <tex>Pred(s) \subseteq V</tex> как множество вершин, входящих в вершину <tex>s</tex>.
<tex>rhs(s) = min_{s' \in pred(s)}(g(s') + c(s', s)</tex>
 
  
Будем говорить, что вершина s насыщена @A vertex s is called locally consistent@, если <tex>g(s) = rhs(s)</tex>
+
Функция <tex>0 \leqslant c(s, s') \leqslant +\infty</tex> будет возвращать стоимость ребра <tex>(s, s')</tex>. При этом <tex>c(s, s') = +\infty</tex> будет тогда и только тогда, когда ребра <tex>(s, s')</tex> не существует.
переполнена
 
несыщена
 
Очевидно, что если все вершины "locally consistent", то мы можем найти расстояние от стартовой вершины до любой.
 
  
Функция <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>
+
{{Определение
 +
|definition=Будем называть '''rhs-значением''' (англ. ''right-hand side value'') такую функцию <tex>rhs(s)</tex>, которая будет возвращать потенциальное минимальное расстояние от <tex>f</tex> до <tex>s</tex> по следующим правилам:
 +
<tex>rhs(s) =
 +
\begin{cases}
 +
0,& \text{if } s = f \\
 +
\min\limits_{s' \in Pred(s)}(g(s') + c(s', s),& \text{otherwise}
 +
\end{cases}
 +
</tex>
 +
Так как rhs-значение использует минимальное значение из минимальных расстояний от <tex>f</tex> до вершин, входящих в данную вершину <tex>s</tex>, это будет нам давать информацию об оценочном расстоянии от <tex>f</tex> до <tex>s</tex>.
 +
}}
  
Если в конце поиска пути <tex>g(s_{goal}) = +inf</tex>, то мы не смогли найти путь от <tex>s_{start}</tex> до <tex>s_{goal}</tex>
+
{{Определение
 +
|definition=Вершина <tex>s</tex> называется '''насыщенной''' (англ. ''locally consistent''), если <tex>g(s) = rhs(s)</tex>
 +
}}
  
Псевдокод:
+
{{Определение
 +
|definition=Вершина <tex>s</tex> называется '''переполненной''' (англ. ''locally overconsistent''), если <tex>g(s) > rhs(s)</tex>
 +
}}
  
  '''CalcKey'''(s):
+
{{Определение
  {
+
|definition=Вершина <tex>s</tex> называется '''ненасыщенной''' (англ. ''locally underconsistent''), если <tex>g(s) < rhs(s)</tex>
    return [<tex>min(g(s); rhs(s)) + h(s;s_{goal})</tex>;<tex>min(g(s); rhs(s))</tex>];
+
}}
  }
 
  
  '''Initialize'''():
+
Очевидно, что если все вершины насыщены, то мы можем найти расстояние от стартовой вершины до любой. Такой граф будем называть устойчивым (насыщенным).
  {
 
    <tex>U = null;</tex>
 
    <tex>for all s \in S</tex>
 
      <tex>rhs(s) = g(s) = 1;</tex>
 
    <tex>rhs(s_start) = 0;</tex>
 
    <tex>U.Insert(s_{start};CalcKey(s_{start}));</tex>
 
  }
 
  
  '''UpdateVertex'''(<tex>u</tex>):
+
[[Эвристики для поиска кратчайших путей|Эвристическая функция]] <tex>h(s,s')</tex> теперь должна быть неотрицательная и выполнять неравенство треугольника, т.е.
  {
+
<tex>h(t,t) = 0</tex> и <tex>h(s, t) \leqslant c(s,s') + h(s',t)</tex> для всех <tex>s \in V</tex> и <tex>s' \in Succ(s)</tex>
    if (<tex>u != 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 (g(u) != rhs(u))
 
      U.Insert(<tex>u</tex>;CalcKey(<tex>u</tex>));
 
  }
 
  
  '''ComputeShortestPath'''():
+
{{Определение
  {
+
|definition=Будем называть '''ключом''' вершины такую функцию <tex>key(s)</tex>, которая возвращает вектор из 2-ух значений <tex>k_1(s)</tex>, <tex>k_2(s)</tex>.
    while (U.TopKey()< CalcKey(<tex>s_{goal}</tex>) OR rhs(<tex>s_{goal}) != g(s_{goal}</tex>))
+
* <tex>k_1(s) = \min(g(s), rhs(s)) + h(s, t)</tex>
      u = U.Pop();
+
* <tex>k_2(s) = \min(g(s), rhs(s))</tex>,
      if (g(u) > rhs(u))
+
где <tex>s</tex> - вершина из множества <tex>V</tex>
        g(u) = rhs(u);
+
}}
        for all s 2 Succ(u) UpdateVertex(s);
+
Если в конце поиска пути <tex>g(t) = +\infty</tex>, то мы не смогли найти путь от <tex>f</tex> до <tex>t</tex> на текущей итерации. Но после следующего изменения графа путь вполне может найтись.
      else
 
        g(u) = 1;
 
      for all <tex>s \in Succ(u) perec {u}</tex>
 
        UpdateVertex(s);
 
  }
 
  
  '''Main'''():
+
=== Псевдокод ===
  {
 
    Initialize();
 
    while (<tex>s_{start} != s_{goal}</tex>)
 
    {
 
      ComputeShortestPath();
 
      Wait for changes in edge costs;
 
      for all directed edges (u;v) with changed edge costs
 
      {
 
        Update the edge cost c(u;v);
 
        UpdateVertex(v);
 
      }
 
    }
 
  }
 
  
Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь между вершинами <tex>s_start</tex> и <tex>s_goal</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за <tex>O(n^2*log(n))</tex>. Улучшим эту оценку с помощью алгоритма D* lite.
+
Основная функция, описывающая алгоритм
 +
  '''function''' main():
 +
    initialize()
 +
    '''while''' ''true''
 +
      computeShortestPath()
 +
      <font color="green">// В данный момент мы знаем кратчайший путь из f в t.</font>
 +
      Ждем каких-либо изменений графа.
 +
      '''for''' всех ориентированных ребер (u, v) с измененными весами:
 +
        Обновляем результат функции c(u, v)
 +
        updateVertex(v)
  
'''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку О(n*log(n)).
+
Функция инициализации исходного графа устанавливает для всех вершин кроме стартовой вершины <tex>f</tex> значения <tex>g(s)</tex> и <tex>rhs(s)</tex> равными бесконечности. Для стартовой <tex>rhs(f)=0</tex>. Очевидно, что минимальное расстояние от стартовой вершины до самой себя должно быть равным 0, но <tex>g(f)=+\infty</tex>. Это сделано для того, чтобы стартовая вершина была ненасыщенной и имела право попасть в приоритетную очередь.
 +
  '''function''' initialize():
 +
    <font color="green">// Заведем [[Двоичная куча|приоритетную очередь]] U, в которую будем помещать вершины.</font>
 +
    <font color="green">// Сортировка будет производиться по функции key(s).</font>
 +
    U = <tex>\varnothing</tex>
 +
    '''for''' s <tex>\in</tex> V
 +
      rhs(s) = g(s) = <tex>+\infty</tex>
 +
    rhs(f) = 0
 +
    U.insert(f, calcKey(f))
  
== Алгоритм D* ==
+
Функция <tex>key(s)</tex>. Возвращаемые значения сортируются в лексографическом порядке, то есть сначала сортируется по <tex>k_1(s)</tex>, потом по <tex>k_2(s)</tex>
 +
  '''function''' calcKey(s):
 +
    '''return''' [min(g(s), rhs(s)) + h(s, t), min(g(s), rhs(s))]
  
   '''CalcKey'''(s):
+
Обновляет данные вершины в соответствие с данными выше определениями. Также поддерживает инвариант того, что в очереди U лежат только ненасыщенные вершины.
     return [<tex>min(g(s);rhs(s)) + h(sstart;s)</tex>;<tex>min(g(s); rhs(s))</tex>];
+
   '''function''' updateVertex(u):
 +
     '''if''' u <tex>\ne</tex> f
 +
      <tex>rhs(u) = \min\limits_{s' \in Pred(u)}(g(s') + c(s',u))</tex>
 +
    '''if''' u <tex>\in</tex> U
 +
      U.remove(u)
 +
    '''if''' g(u) <tex>\ne</tex> rhs(u)
 +
      U.insert(u, calcKey(u))
  
   '''Initialize'''():
+
Функция несколько раз перерасчитывает значение <tex>g(s)</tex> у ненасыщенных вершин в неубывающем порядке их ключей. Такой перерасчет значения <tex>g(s)</tex> будем называть ''расширением'' вершины.
     U = null;
+
   '''function''' computeShortestPath():
    for all <tex>s \in S</tex>
+
     '''while''' U.topKey() < calcKey(t) '''or''' rhs(t) <tex>\ne</tex> g(t)
      <tex>rhs(s) = g(s) = 1</tex>
+
      u = U.pop()
    <tex>rhs(s_{goal}) = 0</tex>
+
      '''if''' g(u) > rhs(u)
    U.Insert(sgoal;CalcKey(sgoal));
+
        g(u) = rhs(u)
 +
        '''for''' <tex>s</tex> <tex>\in</tex> Succ(u)
 +
          UpdateVertex(s)
 +
      '''else'''
 +
        g(u) = <tex>+\infty</tex>
 +
        '''for''' s <tex>\in</tex> Succ(u) <tex>\cup</tex> <tex>\{u\}</tex>
 +
          updateVertex(s)
  
  '''UpdateVertex'''(u):
+
=== Асимптотика ===
    if (u 6= s_{goal}) rhs(u) = mins02Succ(u)
 
(c(u;s
 
0
 
) + g(s
 
0
 
));
 
f07’g if (u 2 U) U.Remove(u);
 
f08’g if (g(u) 6= rhs(u)) U.Insert(u;CalcKey(u));
 
  
  '''ComputeShortestPath'''()
+
{{Теорема
    while (U.TopKey()<_ CalcKey(s_{start}) OR rhs(s_{start}) 6= g(s_{start}))
+
|about=О монотонности изменения ключей
      u = U.Pop();
+
|statement=В течение выполнения функции '''ComputeShortestPath''' вершины, взятые из очереди, монотонно не убывают.
      if (g(u) > rhs(u))
+
|proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf]
        g(u) = rhs(u);
+
}}
      for all s 2 Pred(u) UpdateVertex(s);
 
      else
 
        g(u) = 1;
 
      for all s 2 Pred(u) [ fug UpdateVertex(s);
 
  
  '''Main'''():
+
{{Теорема
    Initialize();
+
|about=О необратимой насыщенности
    ComputeShortestPath();
+
|statement=Если в функции '''ComputeShortestPath''' была взята переполненная вершина, то на следующей итерации она станет насыщенной.
    while (s_{start} 6= s_{goal})
+
|proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf]
      if (g(sstart) = 1) then there is no known path */
+
}}
      sstart = argmins02Succ(sstart)
 
(c(sstart;s
 
0
 
) + g(s
 
0
 
));
 
f22’g Move to sstart;
 
f23’g Scan graph for changed edge costs;
 
f24’g if any edge costs changed
 
f25’g for all directed edges (u;v) with changed edge costs
 
f26’g Update the edge cost c(u;v);
 
f27’g UpdateVertex(u);
 
f28’g for all s 2 U
 
f29’g U.Update(s;CalcKey(s));
 
f30’g ComputeShortestPath();
 
  
==Ссылки==
+
{{Теорема
 +
|statement=После выполнения функции '''ComputeShortestPath''' можно восстановить путь из <tex>f</tex> в <tex>t</tex>. Для этого, начиная с вершины <tex>t</tex>, нужно постоянно передвигаться к такой вершине <tex>s'</tex>, входящей в <tex>t</tex>, чтобы <tex>g(s') + c(s',s)</tex> было минимальным, до тех пора, пока не будет достигнута вершина <tex>f</tex>.
 +
|proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf]
 +
}}
 +
 
 +
Таким образом мы описали алгоритм LPA*. Он вычисляет длину кратчайшего пути между вершинами <tex>f</tex> и <tex>t</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за <tex>O(n \cdot m \cdot \log(n))</tex>. Улучшим эту оценку с помощью алгоритма D* lite.
 +
 
 +
'''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку <tex>O(n \cdot \log(n))</tex>.
 +
 
 +
== Алгоритм D* (Первая версия) ==
 +
Пока что был описан только алгоритм LPA*. Он находит кратчайшее расстояние между начальной и конечной вершинами при любом изменении данного графа. Его первоначальный поиск полностью совпадает с алгоритмом A*, но последующие итерации способны использовать информацию из предыдущих поисков.
 +
 
 +
=== Постановка задачи ===
 +
Дан [[Основные определения теории графов|взвешенный ориентированный граф]] <tex> G(V, E) </tex>. Даны вершины <tex>f</tex> и <tex>t</tex>. Требуется в процессе движения по кратчайшему пути в графе <tex>G</tex> обновлять значения функции <tex>g(s)</tex> при поступлении новой информации о графе <tex>G</tex>.
 +
 
 +
Теперь на основе LPA* опишем алгоритм D*, который способен определять расстояние между текущей вершиной <tex>f</tex>, в которой, допустим, находится способный к сканированию местности "робот", и конечной вершиной <tex>t</tex> при каждом изменении графа в то время, как наш "робот" движется вдоль найденного пути.
 +
 
 +
[[Файл:Схема_движения_робота_Dstar.png|350px|thumb|right|Схема движения "робота" в процессе работы алгоритма D*. Информация о серых клетках ему неизвестна до тех пор, пока они не попадут в его зону обзора. В данном примере зона обзора составляет 1 клетку в 8-ми направлениях.]]
 +
 
 +
=== Описание ===
 +
Опишем первую версию алгоритма D*. Так как при движении по кратчайшему пути путь может только сокращаться и происходит изменение только стартовой вершины, то можно применить идею из алгоритма LPA*.
 +
 
 +
'''Примечание''': Большинство функций переходят в данный алгоритм без изменений, поэтому опишем только измененные части.
 +
 
 +
Для начала мы поменяем направление поиска в графе.
 +
 
 +
Теперь функция g(s) хранит минимальное известное расстояние от <tex>t</tex> до <tex>s</tex>. Свойства остаются прежними.
 +
 
 +
[[Эвристики для поиска кратчайших путей|Эвристическая функция]] <tex>h(s,s')</tex> теперь должна быть неотрицательная и обратно-устойчивая, т.е.
 +
<tex>h(f,f) = 0</tex> и <tex>h(f, s) \leqslant h(f,s') + c(s',s)</tex> для всех <tex>s \in S</tex> и <tex>s' \in Pred(s)</tex>. Очевидно, что при движении робота <tex>f</tex> изменяется, поэтому данные свойства должны выполняться для всех <tex>f \in V</tex>.
 +
 
 +
Дополнительное условие выхода также меняется, т.е. при <tex>g(f) = +\infty</tex> путь не найден на данной итерации. Иначе путь найден и "робот" может проследовать по нему.
 +
 
 +
'''Примечание''':  Так же следует отметить, что функция '''Initialize''' не обязана инициализировать абсолютно все вершины перед стартом алгоритма. Это важно, так как на практике число вершин может быть огромным, и только немногие будут пройдены роботом в процессе движения. Так же это дает возможность добавления/удаления ребер без потери устойчивости всех подграфов данного графа.
 +
 
 +
=== Псевдокод ===
 +
При такой постановке задачи псевдокод не сильно меняется, но функция '''Main''' все-таки претерпевает значительные изменения.
 +
 
 +
  '''function''' calcKey(s):
 +
    '''return''' [min(g(s), rhs(s)) + h(f,s), min(g(s), rhs(s))]
 +
 
 +
  '''function''' initialize():
 +
    U = <tex>\varnothing</tex>
 +
    '''for''' s <tex>\in</tex> V
 +
      rhs(s) = g(s) = <tex>+\infty</tex>
 +
    rhs(t) = 0
 +
    U.insert(t, calcKey(t))
 +
 
 +
  '''function''' UpdateVertex(u):
 +
    '''if''' u <tex>\ne</tex> t
 +
      rhs(u) = <tex>\min\limits_{s' \in Succ(u)}(c(u,s')+g(s'))</tex>
 +
    '''if''' u <tex>\in</tex> U
 +
      U.remove(u)
 +
    '''if''' g(u) <tex>\ne</tex> rhs(u)
 +
      U.insert(u, calcKey(u))
 +
 
 +
  '''function''' ComputeShortestPath():
 +
    '''while''' U.topKey() < calcKey(f) or rhs(f) <tex>\ne</tex> g(f)
 +
      u = U.pop()
 +
      '''if''' (g(u) > rhs(u))
 +
        g(u) = rhs(u)
 +
        '''for''' s <tex>\in</tex> Pred(u)
 +
          updateVertex(s)
 +
      '''else'''
 +
        g(u) = <tex>+\infty</tex>
 +
        '''for''' <tex>s</tex> <tex>\in</tex> Pred(u) <tex>\cup</tex> {u}
 +
          updateVertex(s)
 +
 
 +
  '''function''' main():
 +
    initialize()
 +
    computeShortestPath()
 +
    '''while''' <tex>f \ne t</tex>
 +
      <font color="green">// '''if''' (g(f) = <tex>+\infty</tex>) тогда путь на данной итерации не найден.</font>
 +
     
 +
      <tex>f</tex> = такая вершина s', что <tex>\min\limits_{s' \in Succ(f)}(c(f, s') + g(s'))</tex>
 +
     
 +
      Передвинулись вдоль найденного пути и изменили вершину <tex>f</tex>
 +
      Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним.
 +
      '''if''' граф изменился
 +
        '''for''' всех ориентированных ребер <tex>(u, v)</tex> с измененными весами:
 +
          Обновляем результат функции <tex>c(u, v)</tex>
 +
          updateVertex(u)
 +
        '''for''' <tex>s</tex> <tex>\in</tex> U
 +
          U.update(s, CalcKey(s))
 +
        computeShortestPath()
 +
 
 +
=== Асимптотика ===
 +
 
 +
{{Теорема
 +
|author=Свен Кёниг
 +
|about=Об устойчивой насыщенности вершин
 +
|statement=Функция '''ComputeShortestPath''' в данной версии алгоритма ''расширяет'' вершину максимум 2 раза, а именно 1 раз, если вершина ненасыщена, и максимум 1 раз, если она переполнена.
 +
|proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf]
 +
}}
 +
 
 +
== Алгоритм D* (Вторая версия) ==
 +
 
 +
=== Описание ===
 +
В первой версии алгоритма была серьезная проблема в том, что для каждой вершины в приоритетной очереди нужно было обновлять ключ суммарно за <tex>O(n \cdot \log(n))</tex>. Это дорогая операция, так как очередь может содержать огромное число вершин. Воспользуемся оригинальным методом поиска и изменим основной цикл, чтобы избежать постоянного перестроения очереди <tex>U</tex>.
 +
 
 +
Теперь эвристическая функция должна поддерживать неравенство треугольника для всех вершин <tex>s,s',s'' \in V</tex>, т.е. <tex>h(s,s'') \leqslant h(s, s') + h(s',s'')</tex>. Так же должно выполняться свойство <tex>h(s,s') \leqslant c^*(s,s')</tex>, где <tex>c^*(s,s')</tex> - стоимость перехода по кратчайшему пути из <tex>s</tex> в <tex>s'</tex>, при этом <tex>s</tex> и <tex>s'</tex> не должны быть обязательно смежными. Такие свойства не противоречат свойствами из первой версии, а лишь усиливают их.
 +
 
 +
Допустим, что после того, как робот продвинется вдоль найденного пути на предыдущих итерациях, из вершины <tex>s</tex> в <tex>s'</tex>, он обнаружит изменения в графе. Первая компонента ключей <tex>k_1(s')</tex> может уменьшится максимум на <tex>h(s,s')</tex> (по определению ключа). Вторая компонента не зависит от функции h. Аналогично первой версии алгоритма, мы должны уменьшить первую компоненту ключа у всех вершин в очереди U. Очевидно, что <tex>h(s,s')</tex> будет одинаковым для всех вершин из U. Порядок в очереди не изменится, если произвести уменьшение. Следовательно уменьшение можно отложить, тем самым очередь не придется перестраивать на каждой итерации. Так же исходя из нового определения функции <tex>h</tex>, её значение будет всегда меньше, чем разность первых компонент ключей у соседних по приоритету вершин. Таким образом мы можем добавлять h(s,s') ко всем <tex>k_1(s')</tex> у ключей вершин из U.
 +
 
 +
Будем называть <tex>K_m</tex> ключевым модификатором. В нем мы и будет хранить сумму <tex>h(s,s')</tex>, которые нужно добавить ко всем вершинам из U.
 +
 
 +
=== Псевдокод ===
 +
 
 +
  '''function''' calcKey(s):
 +
    '''return''' [min(g(s), rhs(s)) + h(f, s) + <tex>K_m</tex>, min(g(s), rhs(s))]
 +
 
 +
  '''function''' initialize():
 +
    U = <tex>\varnothing</tex>
 +
    <tex>K_m = 0</tex>
 +
    '''for''' s <tex>\in</tex> V
 +
      rhs(s) = g(s) = <tex>+\infty</tex>
 +
    rhs(t) = 0
 +
    U.insert(t, CalcKey(t))
 +
 
 +
  '''function''' updateVertex(u):
 +
    '''if''' u <tex>\ne</tex> t
 +
      rhs(u) = <tex>\min\limits_{s' \in Succ(u)}(c(u,s')+g(s'))</tex>
 +
    '''if''' u <tex>\in</tex> U
 +
      U.remove(u)
 +
    '''if''' g(u) <tex>\ne</tex> rhs(u)
 +
      U.insert(u, calcKey(u))
 +
 
 +
  '''function''' computeShortestPath():
 +
    '''while''' U.topKey() < calcKey(f) '''or''' rhs(f) <tex>\ne</tex> g(f)
 +
      <tex>K_{old}</tex> = U.topKey()
 +
      u = U.pop()
 +
     
 +
      '''if''' <tex>K_{old}</tex> < calcKey(u)
 +
        U.insert(u, calcKey(u))
 +
     
 +
      '''if''' (g(u) > rhs(u))
 +
        g(u) = rhs(u)
 +
        '''for''' <tex>s</tex> <tex>\in</tex> Pred(u)
 +
          updateVertex(s)
 +
      '''else'''
 +
        g(u) = <tex>+\infty</tex>
 +
        '''for''' <tex>s</tex> <tex>\in</tex> Pred(u) <tex>\cup</tex> <tex>\{u\}</tex>
 +
          updateVertex(s)
 +
 
 +
  '''function''' main():
 +
    <tex>s_{last} = f</tex>
 +
    initialize()
 +
    computeShortestPath()
 +
    '''while''' f <tex>\ne</tex> t
 +
      <font color="green">// if (g(f) = <tex>+\infty</tex>) тогда путь на данной итерации не найден.</font>
 +
      <tex>f</tex> = такая вершина s', что <tex>\min\limits_{s' \in Succ(f)}(c(f, s') + g(s'))</tex>
 +
      Передвинулись вдоль найденного пути и изменили вершину <tex>f</tex>.
 +
      Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним.
 +
      '''if''' граф изменился
 +
        <tex>K_m = K_m + h(s_{last}, h_{start})</tex>
 +
        <tex>s_{last} = f</tex>
 +
        '''for''' всех ориентированных ребер (u, v) с измененными весами:
 +
          Обновляем результат функции c(u, v)
 +
          updateVertex(u)
 +
        computeShortestPath()
 +
 
 +
=== Асимптотика ===
 +
 
 +
С помощью введения ключевого модификатора <tex>K_m</tex> и отложенного обновления ключей вершин получилось убрать из итерации алгоритма <tex>O(n \cdot \log(n))</tex> операций, которые тратились на обновление очереди <tex>U</tex>. Очевидно, что на основе теорем, приведенных выше, алгоритм использовал <tex>O(2 \cdot n \cdot \log(n))</tex> операций. Итак, нам удалось уменьшить константу в 2 раза, что дает существенный рост производительности на практических задачах.
 +
 
 +
=== Пример работы ===
 +
{| class="wikitable"
 +
|-
 +
| style="width:50%;text-align:center;" | [[Файл:Схема_движения_робота_Dstarv2_1.png|400px]] || style="width:50%;text-align:center;" | [[Файл:Схема_движения_робота_Dstarv2_2.png|400px]]
 +
|-
 +
| style="width:50%;text-align:center;" | Итерации в функции '''ComputeShortestPath''' на исходном графе. || style="width:50%;text-align:center;" | Итерации в функции '''ComputeShortestPath''' после изменения графа. (Второй вызов функции)
 +
|}
 +
 
 +
==Источники информации==
 
* [http://en.wikipedia.org/wiki/D* Wikipedia:D*]
 
* [http://en.wikipedia.org/wiki/D* Wikipedia:D*]
 
* [http://idm-lab.org/project-a.html Sven Koenig` web page]
 
* [http://idm-lab.org/project-a.html Sven Koenig` web page]
 +
* [http://www.cs.cmu.edu/~maxim/files/aij04.pdf LPA*]
 +
* [http://pub1.willowgarage.com/~konolige/cs225b/dlite_tro05.pdf D* lite]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Кратчайшие пути в графах ]]
 
[[Категория: Кратчайшие пути в графах ]]

Текущая версия на 17:54, 16 сентября 2015

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

Псевдокод

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

 function 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]. Это сделано для того, чтобы стартовая вершина была ненасыщенной и имела право попасть в приоритетную очередь.

 function 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]

 function calcKey(s):
   return [min(g(s), rhs(s)) + h(s, t), min(g(s), rhs(s))]

Обновляет данные вершины в соответствие с данными выше определениями. Также поддерживает инвариант того, что в очереди U лежат только ненасыщенные вершины.

 function 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] будем называть расширением вершины.

 function 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 [math]s[/math] [math]\in[/math] Succ(u)
         UpdateVertex(s)
     else
       g(u) = [math]+\infty[/math]
       for s [math]\in[/math] Succ(u) [math]\cup[/math] [math]\{u\}[/math]
         updateVertex(s)

Асимптотика

Теорема (О монотонности изменения ключей):
В течение выполнения функции ComputeShortestPath вершины, взятые из очереди, монотонно не убывают.
Доказательство:
[math]\triangleright[/math]
Доказательство [1]
[math]\triangleleft[/math]
Теорема (О необратимой насыщенности):
Если в функции ComputeShortestPath была взята переполненная вершина, то на следующей итерации она станет насыщенной.
Доказательство:
[math]\triangleright[/math]
Доказательство [2]
[math]\triangleleft[/math]
Теорема:
После выполнения функции ComputeShortestPath можно восстановить путь из [math]f[/math] в [math]t[/math]. Для этого, начиная с вершины [math]t[/math], нужно постоянно передвигаться к такой вершине [math]s'[/math], входящей в [math]t[/math], чтобы [math]g(s') + c(s',s)[/math] было минимальным, до тех пора, пока не будет достигнута вершина [math]f[/math].
Доказательство:
[math]\triangleright[/math]
Доказательство [3]
[math]\triangleleft[/math]

Таким образом мы описали алгоритм 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]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 все-таки претерпевает значительные изменения.

 function calcKey(s):
   return [min(g(s), rhs(s)) + h(f,s), min(g(s), rhs(s))]
 function 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))
 function 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))
 function 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 [math]s[/math] [math]\in[/math] Pred(u) [math]\cup[/math] {u}
         updateVertex(s)
 function 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 [math]s[/math] [math]\in[/math] U
         U.update(s, CalcKey(s))
       computeShortestPath()

Асимптотика

Теорема (Свен Кёниг, Об устойчивой насыщенности вершин):
Функция ComputeShortestPath в данной версии алгоритма расширяет вершину максимум 2 раза, а именно 1 раз, если вершина ненасыщена, и максимум 1 раз, если она переполнена.
Доказательство:
[math]\triangleright[/math]
Доказательство [4]
[math]\triangleleft[/math]

Алгоритм 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] не должны быть обязательно смежными. Такие свойства не противоречат свойствами из первой версии, а лишь усиливают их.

Допустим, что после того, как робот продвинется вдоль найденного пути на предыдущих итерациях, из вершины [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.

Псевдокод

 function calcKey(s):
   return [min(g(s), rhs(s)) + h(f, s) + [math]K_m[/math], min(g(s), rhs(s))]
 function 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))
 function 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))
 function 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 [math]s[/math] [math]\in[/math] Pred(u) 
         updateVertex(s)
     else
       g(u) = [math]+\infty[/math]
       for [math]s[/math] [math]\in[/math] Pred(u) [math]\cup[/math] [math]\{u\}[/math] 
         updateVertex(s)
 function 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 раза, что дает существенный рост производительности на практических задачах.

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

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

Источники информации