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

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

LPA * или же Планирование на всю жизнь A * является инкрементный эвристический поиск алгоритм на основе А *. Впервые он был описан Свеном Кенигом и Максимом Лихачевым в 2001 году.^[1]

Описание

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

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

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

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

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

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

LPA * поддерживает две оценки стартовой дистанции. $грамм *(п)$ для каждого узла:

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

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

{ displaystyle rhs (начало) = g (начало) = 0}

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

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

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

{ displaystyle 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-значение (известное как локально непоследовательный node), g-значение изменяется, чтобы соответствовать rhs-значению, делая узел локально согласованным. Затем узел удаляется из очереди.
Если rhs-значение узла больше, чем его g-значение (известное как локально непоследовательный узел), g-значение установлено на бесконечность (что делает узел либо локально сверхсогласованным, либо локально согласованным). Если узел локально согласован, он удаляется из очереди, иначе его ключ обновляется.

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

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

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

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

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

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

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

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

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

Поиск кратчайшего пути

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

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

Псевдокод

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

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

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

^[2]

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

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

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

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

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

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

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

Варианты

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