Планирование на всю жизнь A*

Сорт	Алгоритм поиска
Структура данных	График

LPA* или Lifelong Planning A* — это инкрементальный эвристический алгоритм поиска, основанный на A* . Впервые он был описан Свеном Кенигом и Максимом Лихачевым в 2001 году. ^[1]

Описание

LPA* — это инкрементная версия A*, которая может адаптироваться к изменениям в графике без перерасчета всего графика, обновляя значения g (расстояние от начала) из предыдущего поиска во время текущего поиска, чтобы исправить их при необходимости. Как и A*, LPA* использует эвристику, которая является нижней границей стоимости пути от заданного узла до цели. Эвристика допустима, если она гарантированно неотрицательна (допустим ноль) и никогда не превышает стоимость самого дешевого пути к цели.

Предшественники и преемники

За исключением начального и целевого узла, каждый узел $n$ имеет предшественников и преемников :

Любой узел, от которого ребро ведет к $n,$ является предшественником $n$ .
Любой узел, к которому ведет ребро из $n,$ является преемником $n$ .

В последующем описании эти два термина относятся только к непосредственным предшественникам и преемникам, а не к предшественникам предшественников или преемникам преемников.

Оценка стартового расстояния

LPA* поддерживает две оценки начального расстояния $g *(n)$ для каждого узла:

$g (n)$ , ранее вычисленное значение g (начальное расстояние), как в A*
$rhs (n)$ — предварительное значение, основанное на g-значениях предшественников узла (минимум всех $g (n') + d (n', n)$ , где $n'$ — предшественник $n$ и $d (x, y)$ — стоимость ребра, соединяющего $x$ и $y$ )

Для начального узла всегда справедливо следующее:

rhs(start)=g(start)=0

Если $rhs (n)$ равно $g (n)$ , то $n$ называется локально согласованным . Если все узлы локально согласованы, то кратчайший путь можно определить, как и в случае с A*. Однако при изменении стоимости ребер локальную согласованность необходимо восстанавливать только для тех узлов, которые имеют отношение к маршруту.

Приоритетная очередь

Когда узел становится локально несогласованным (из-за изменения стоимости его предшественника или ребра, связывающего его с предшественником), он помещается в приоритетную очередь для повторной оценки. LPA* использует двумерный ключ:

k(n)={\begin{bmatrix}k_{1}(n)\\k_{2}(n)\\\end{bmatrix}}={\begin{bmatrix}min(g(n),rhs(n))+h(n,goal)\\min(g(n),rhs(n))\\\end{bmatrix}}

Записи упорядочены по $k 1$ (что соответствует непосредственно значениям f, используемым в A*), а затем по $k 2$ .

Расширение узла

Верхний узел в очереди расширяется следующим образом:

Если значение rhs узла равно его значению g, узел локально согласован и удаляется из очереди.
Если значение rhs узла меньше его значения g (известное как локально сверхсогласованный узел), значение g изменяется, чтобы соответствовать значению rhs, что делает узел локально согласованным. Затем узел удаляется из очереди.
Если значение rhs узла больше, чем его значение g (известное как локально несогласованный узел), значение g устанавливается равным бесконечности (что делает узел либо локально сверхсогласованным, либо локально согласованным). Если узел становится локально согласованным, он удаляется из очереди, в противном случае его ключ обновляется.

Поскольку изменение значения g узла может также изменить значения rhs его преемников (и, следовательно, их локальную согласованность), они оцениваются, и их членство в очереди и ключ при необходимости обновляются.

Расширение узлов продолжается со следующим узлом вверху очереди до тех пор, пока не будут выполнены два условия:

Цель локально непротиворечива и
Узел в верхней части приоритетной очереди имеет ключ, который больше или равен ключу цели.

Начальный запуск

Граф инициализируется путем установки значения rhs начального узла равным 0, а его значения g — бесконечности. Для всех остальных узлов предполагается, что и значение g, и значение rhs равны бесконечности, пока не будет присвоено иное. Первоначально это делает начальный узел единственным локально несогласованным узлом и, следовательно, единственным узлом в очереди. После этого начинается расширение узла. Таким образом, первый запуск LPA* ведет себя так же, как и A*, расширяя те же узлы в том же порядке.

Изменения стоимости

Когда стоимость ребра изменяется, LPA* проверяет все узлы, затронутые изменением, т. е. все узлы, в которых заканчивается одно из измененных ребер (если ребро можно пройти в обоих направлениях и изменение затрагивает оба направления, оба узла соединены край осматривается):

Значения rhs узлов обновляются.
Узлы, которые стали локально согласованными, удаляются из очереди.
Узлы, которые стали локально несогласованными, добавляются в очередь.
Ключи узлов, которые остаются локально несогласованными, обновляются.

После этого расширение узла возобновляется до тех пор, пока не будет достигнуто конечное условие.

Нахождение кратчайшего пути

После завершения расширения узла (т. е. выполнения условий выхода) оценивается кратчайший путь. Если стоимость цели равна бесконечности, пути с конечной стоимостью от начала до цели не существует. В противном случае кратчайший путь можно определить, двигаясь назад:

Начните с цели.
Перейдите к предшественнику $n'$ текущего узла $n,$ для которого $g (n') + d (n', n)$ является наименьшим (если наименьший балл используется несколькими узлами, каждый из них является допустимым решением, и любой из них может быть выбрано произвольно).
Повторяйте предыдущий шаг, пока не дойдете до начала. ^[2]

Псевдокод

Этот код предполагает приоритетную очередь queue, который поддерживает следующие операции:

topKey() возвращает (числовой) наименьший приоритет любого узла в очереди (или бесконечность, если очередь пуста)
pop() удаляет из очереди узел с наименьшим приоритетом и возвращает его
insert(node, priority) вставляет узел с заданным приоритетом в очередь
remove(node) удаляет узел из очереди
contains(node) возвращает true, если очередь содержит указанный узел, и false, если нет

void   main  ()   {    инициализировать  ();    в то время как   (  истина  )   {      computeShortestPath  ();      while   (  !  hasCostChanges  ())        спать  ;      для   (  край   :   getChangedEdges  ())   {          край  .  setCost  (  getNewCost  (  край  ));          updateNode  (  край  .  endNode  );      }    }  }  void   инициализировать  ()   {    очередь   =   новый   PriorityQueue  ();    для   (  узел   :   getAllNodes  ())   {      узел  .  г   =   БЕСКОНЕЧНОСТЬ  ;      узел  .  правая   =   БЕСКОНЕЧНОСТЬ  ;    }    начинать  .  правая часть   =   0  ;    очередь  .  вставить  (  начать  ,   рассчитать ключ  (  начать  ));  }  /** Расширяет узлы в приоритетной очереди. */  void   ComputeShortestPath  ()   {    while   ((  queue  .  getTopKey  ()   <   calculKey  (  цель  ))   ||   (  цель  .  rhs   ! =   цель  .  g  ))   {      узел   =   очередь  .  поп  ();      если   (  узел  .  г   >   узел  .  rhs  )   {        узел  .  г   =   узел  .  резс  ;      }   Еще   {        узел  .  г   =   БЕСКОНЕЧНОСТЬ  ;        updateNode  (  узел  );      }      for   (  преемник   :   node  .  getSuccessors  ())        updateNode  (  преемник  );    }  }  /** Пересчитывает rhs для узла и удаляет его из очереди.  * Если узел стал локально несогласованным, он (повторно) вставляется в очередь с новым ключом. */  void   updateNode  (  узел  )   {    if   (  узел   !=   старт  )   {      узел  .  правая   =   БЕСКОНЕЧНОСТЬ  ;      for   (  предшественник  :   node  .  getPredecessors  ())        node  .  rhs   =   min  (  узел  .  rhs  ,   предшественник  .  г   +   предшественник  .  getCostTo  (  узел  ));      если   (  очередь  .  содержит  (  узел  ))        очередь  .  удалить  (  узел  );      если   (  узел  .  g   !=   узел .  рхс  )        очередь  .  вставить  (  узел  ,   CalculationKey  (  узел  ));    }  }  int  []   CalculateKey  (  узел  )   {    возвращение   {  мин  (  узел  .  g  ,   узел  .  rhs  )   +   узел  .  getHeuristic  (  цель  ),   мин  (  узел  .  g  ,   узел  .  rhs  )};  }

^[2]

Характеристики

Будучи алгоритмически похожим на A*, LPA* разделяет многие его свойства.

Каждый узел расширяется (посещается) не более двух раз за каждый запуск LPA*. Локально сверхсогласованные узлы расширяются не более одного раза за запуск LPA*, поэтому его первоначальный запуск (при котором каждый узел переходит в сверхсогласованное состояние) имеет производительность, аналогичную A*, который посещает каждый узел не более одного раза.
Ключи расширенных для каждого прохода узлов монотонно не убывают с течением времени, как и в случае с A*.
Чем более информативными (и, следовательно, более крупными) являются эвристики (при этом все еще удовлетворяющие критериям приемлемости), тем меньше узлов необходимо расширять.
Реализация очереди приоритетов оказывает существенное влияние на производительность, как и в случае A*. Использование кучи Фибоначчи может привести к значительному увеличению производительности по сравнению с менее эффективными реализациями.

Для реализации A*, которая разрывает связи между двумя узлами с одинаковыми значениями f в пользу узла с меньшим значением g (который нечетко определен в A*), также верны следующие утверждения:

Порядок раскрытия локально сверхсогласованных узлов идентичен A*.
Из всех локально сверхсогласованных узлов необходимо расширять только те, стоимость которых не превышает стоимости цели, как в случае с A*.

LPA* дополнительно обладает следующими свойствами:

При изменении затрат на периферию LPA* превосходит A* (при условии, что последний запускается с нуля), поскольку только часть узлов необходимо снова расширить.

Варианты

D* Lite , повторная реализация алгоритма D* на основе LPA* ^[3]

Ссылки

^ Кениг, Свен; Лихачев, Максим (2001), «Incremental A*» (PDF) , Материалы 14-й Международной конференции по нейронным системам обработки информации: естественным и синтетическим (NIPS'01) , MIT Press, стр. 1539–46
^ Перейти обратно: ^а ^б Кениг, Свен; Лихачев Максим (2003), "D* Lite" (PDF) , Учеб. Натл. Конф. об искусственном интеллекте, Эдмонтон, AB , стр. 476–483, ISBN. 978-0-262-51129-2
^ Кениг, С.; Лихачев, М. (2005), «Быстрое перепланирование навигации по неизвестной местности» (PDF) , IEEE Transactions on Robotics , 21 (3): 354–363, doi : 10.1109/TRO.2004.838026 , S2CID 15664344

[KoenigLikhachev2001-1] Кениг, Свен; Лихачев, Максим (2001), «Incremental A*» (PDF) , Материалы 14-й Международной конференции по нейронным системам обработки информации: естественным и синтетическим (NIPS'01) , MIT Press, стр. 1539–46

[KoenigLikhachev2002-2] Перейти обратно: ^а ^б Кениг, Свен; Лихачев Максим (2003), "D* Lite" (PDF) , Учеб. Натл. Конф. об искусственном интеллекте, Эдмонтон, AB , стр. 476–483, ISBN. 978-0-262-51129-2

[KoenigLikhachev2005-3] Кениг, С.; Лихачев, М. (2005), «Быстрое перепланирование навигации по неизвестной местности» (PDF) , IEEE Transactions on Robotics , 21 (3): 354–363, doi : 10.1109/TRO.2004.838026 , S2CID 15664344

[1]

[2]

[3]

v т и графов и деревьев Алгоритмы обхода
Поиск	α–β обрезка А* ИДА* МПА* СМА* Поиск по принципу «лучшее в первую очередь» Поиск луча Двунаправленный поиск Поиск в ширину Лексикографический Параллельно Б* Поиск в глубину Итеративное углубление Д* Граничный поиск Поиск точки прыжка Поиск по дереву Монте-Карло ССС*
Кратчайший путь	Беллман-Форд Дейкстры Флойд-Уоршалл Джонсонс Кратчайший путь быстрее Йен
Минимальное связующее дерево	Черника Крускала Prim's Обратное удаление
Список алгоритмов поиска по графу