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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 11: Строка 11:
 
Аналогично множество <tex>Pred(s) \in V</tex> как множество вершин, входящих в вершину <tex>s</tex>.  
 
Аналогично множество <tex>Pred(s) \in V</tex> как множество вершин, входящих в вершину <tex>s</tex>.  
  
Функция <tex>0 \lessgtr с(s, s') \lessgtr +\infty</tex> будет возвращать стоимость перехода из вершины <tex>s</tex> в вершину <tex>s'</tex>. При этом <tex>s' \in Succ(s)</tex>.
+
Функция <tex>0 \leqslant с(s, s') \leqslant +\infty</tex> будет возвращать стоимость перехода из вершины <tex>s</tex> в вершину <tex>s'</tex>. При этом <tex>s' \in Succ(s)</tex>.
  
 
Функция <tex>g(s)</tex> будет возвращать последнее известное (и самое минимальное) значение расстояния от вершины <tex>s_{start}</tex> до <tex>s</tex>.
 
Функция <tex>g(s)</tex> будет возвращать последнее известное (и самое минимальное) значение расстояния от вершины <tex>s_{start}</tex> до <tex>s</tex>.
Строка 18: Строка 18:
 
:<tex dpi="120">rhs(s) = 0</tex>
 
:<tex dpi="120">rhs(s) = 0</tex>
 
Иначе  
 
Иначе  
:<tex dpi="120">rhs(s) = min_{s' \in pred(s)}(g(s') + c(s', s)</tex>
+
:<tex dpi="120">rhs(s) = min_{s' \in Pred(s)}(g(s') + c(s', s)</tex>
  
 
Вершина <tex>s</tex> может быть 3-х видов:
 
Вершина <tex>s</tex> может быть 3-х видов:
Строка 96: Строка 96:
 
Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь между вершинами <tex>s_{start}</tex> и <tex>s_{goal}</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за <tex>O(n^2 \dot log(n))</tex>. Улучшим эту оценку с помощью алгоритма D* lite.
 
Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь между вершинами <tex>s_{start}</tex> и <tex>s_{goal}</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за <tex>O(n^2 \dot log(n))</tex>. Улучшим эту оценку с помощью алгоритма D* lite.
  
'''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку О(n*log(n)).
+
'''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку О(n \dot log(n)).
  
 
== Алгоритм D* ==
 
== Алгоритм D* ==
 +
Пока что был описан только алгоритм LPA*. Он способен неоднократно определять кратчайшее расстояние между начальной и конечной вершинами при любом изменении данного графа. Его первоначальный поиск полностью совпадает с алгоритмом A*, но последующие итерации способны использовать информацию из предыдущих поисков.
 +
 +
=== Постановка задачи ===
 +
Теперь на основе LPA* опишем алгоритм D*, который способен определять расстояние между текущей вершиной <tex>s_{start}</tex>, в которой, допустим, находится курсор/робот, и конечной вершиной <tex>s_{goal}</tex> при каждом изменении графа в то время, как наш робот движется вдоль найденного пути.
 +
 +
=== Описание ===
 +
Опишем первую версию алгоритма D*. Очевидно, что большинство вершин в процессе движения робота остаются неизменными, поэтому мы можем применить алгоритм LPA*.
 +
 +
'''Примечание''': Большинство функций переходят в данный алгоритм без изменений, поэтому опишем только измененные части.
 +
 +
Для начала мы поменяем направление поиска в графе.
 +
 +
Теперь функция g(s) хранит минимальное известное расстояние от <tex>s_{goal}</tex> до <tex>s</tex>. Свойства остаются прежними.
 +
 +
Эвристическая функция h(s,s') теперь должна быть неотрицательная и обратно-устойчивая, т.е.
 +
<tex>h(s_{start},s_{start}) = 0</tex> и <tex>h(s_{start}, s) <= h(s_{start},s') + c(s',s)</tex> для всех <tex>s \in S</tex> и <tex>s' \in Pred(s)</tex>. Очевидно, что при движении робота <tex>s_{start}</tex> изменяется, поэтому данные свойства должны выполняться для всех <tex>s_{start} \in S</tex>.
 +
 +
Дополнительное условие выхода также меняется, т.е. при <tex>g(s_{start}) = +\infty</tex> путь не найден на данной итерации. Иначе путь найден и робот может проследовать по нему.
  
 
=== Псевдокод (Первая версия) ===
 
=== Псевдокод (Первая версия) ===
 +
При такой постановке задачи псевдокод не сильно меняется. Но функция '''Main''' все-таки претерпевает значительные изменения.
 +
 
   '''CalcKey'''(s):
 
   '''CalcKey'''(s):
 
     return [<tex>\min(g(s);rhs(s)) + h(s_{start};s)</tex>;<tex>\min(g(s); rhs(s))</tex>];
 
     return [<tex>\min(g(s);rhs(s)) + h(s_{start};s)</tex>;<tex>\min(g(s); rhs(s))</tex>];
Строка 112: Строка 132:
  
 
   '''UpdateVertex'''(u):
 
   '''UpdateVertex'''(u):
     if (<tex>u != s_{goal}</tex>)  
+
     if (<tex>u \ne s_{goal}</tex>)  
 
       rhs(u) = min_{s' \in Succ(u)}(c(u,s')+g(s'));
 
       rhs(u) = min_{s' \in Succ(u)}(c(u,s')+g(s'));
 
     if (<tex>u \in U</tex>)  
 
     if (<tex>u \in U</tex>)  
 
       U.Remove(u);
 
       U.Remove(u);
     if (<tex>g(u) != rhs(u)</tex>)  
+
     if (<tex>g(u) \ne rhs(u)</tex>)  
 
       U.Insert(u; CalcKey(u));
 
       U.Insert(u; CalcKey(u));
  
Строка 138: Строка 158:
 
       <tex>s_{start}</tex> = такая вершина s', что <tex>min_{s' \in Succ(s_{start})}(c(s_{start}, s') + g(s'))</tex>
 
       <tex>s_{start}</tex> = такая вершина s', что <tex>min_{s' \in Succ(s_{start})}(c(s_{start}, s') + g(s'))</tex>
 
       Передвинулись вдоль найденного пути и изменили вершину <tex>s_{start}</tex>;
 
       Передвинулись вдоль найденного пути и изменили вершину <tex>s_{start}</tex>;
       Ждем каких-либо изменений в графе или убеждаемся, что граф остается прежним.
+
       Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним.
 
       if (если граф изменился)
 
       if (если граф изменился)
 
         for всех ориентированных ребер <tex>(u; v)</tex> с измененными весами:
 
         for всех ориентированных ребер <tex>(u; v)</tex> с измененными весами:

Версия 00:42, 3 января 2014

Алгоритм 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]Succ(s) \in V[/math] как множество вершин, исходящих из вершины [math]s[/math].

Аналогично множество [math]Pred(s) \in V[/math] как множество вершин, входящих в вершину [math]s[/math].

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

Функция [math]g(s)[/math] будет возвращать последнее известное (и самое минимальное) значение расстояния от вершины [math]s_{start}[/math] до [math]s[/math].

Если [math]s = s_{start}[/math]

[math]rhs(s) = 0[/math]

Иначе

[math]rhs(s) = min_{s' \in Pred(s)}(g(s') + c(s', s)[/math]

Вершина [math]s[/math] может быть 3-х видов:

  • насыщена, если [math]g(s) = rhs(s)[/math]
  • переполнена, если [math]g(s) \gt rhs(s)[/math]
  • ненасыщена, если [math]g(s) \lt rhs(s)[/math]

Очевидно, что если все вершины насыщены, то мы можем найти расстояние от стартовой вершины до любой.

Функция [math]key(s)[/math], где [math]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]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]);
     }
   }
 }

Теперь опишем составные элементы подробнее

 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]));
 }
 ComputeShortestPath():
 {
   while (U.TopKey() < CalcKey([math]s_{goal}[/math]) OR rhs([math]s_{goal}) \ne g(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 \dot log(n))[/math]. Улучшим эту оценку с помощью алгоритма D* lite.

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

Алгоритм D*

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

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

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

Описание

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

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

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

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

Эвристическая функция h(s,s') теперь должна быть неотрицательная и обратно-устойчивая, т.е. [math]h(s_{start},s_{start}) = 0[/math] и [math]h(s_{start}, s) \lt = 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 S[/math].

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

Псевдокод (Первая версия)

При такой постановке задачи псевдокод не сильно меняется. Но функция 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) = min_{s' \in Succ(u)}(c(u,s')+g(s'));
   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();

Ссылки