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

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

LPA * или пожизненное планирование A * - это алгоритм возрастающего эвристического поиска , основанный на A * . Впервые он был описан Свеном Кенигом и Максимом Лихачевым в 2001 году.

Описание

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$ )

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Псевдокод

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

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

void main() {
  initialize();
  while (true) {
    computeShortestPath();
    while (!hasCostChanges())
      sleep;
    for (edge : getChangedEdges()) {
        edge.setCost(getNewCost(edge));
        updateNode(edge.endNode);
    }
  }
}

void initialize() {
  queue = new PriorityQueue();
  for (node : getAllNodes()) {
    node.g = INFINITY;
    node.rhs = INFINITY;
  }
  start.rhs = 0;
  queue.insert(start, calculateKey(start));
}

/** Expands the nodes in the priority queue. */
void computeShortestPath() {
  while ((queue.getTopKey() < calculateKey(goal)) || (goal.rhs != goal.g)) {
    node = queue.pop();
    if (node.g > node.rhs) {
      node.g = node.rhs;
      for (successor : node.getSuccessors())
        updateNode(successor);
    } else {
      node.g = INFINITY;
      updateNode(node);
      for (successor : node.getSuccessors())
        updateNode(successor);
    }
  }
}

/** Recalculates rhs for a node and removes it from the queue.
 * If the node has become locally inconsistent, it is (re-)inserted into the queue with its new key. */
void updateNode(node) {
  if (node != start) {
    node.rhs = INFINITY;
    for (predecessor: node.getPredecessors())
      node.rhs = min(node.rhs, predecessor.g + predecessor.getCostTo(node));
    if (queue.contains(node))
      queue.remove(node);
    if (node.g != node.rhs)
      queue.insert(node, calculateKey(node));
  }
}

int[] calculateKey(node) {
  return {min(node.g, node.rhs) + node.getHeuristic(goal), min(node.g, node.rhs)};
}

Свойства

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

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

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

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

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

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

Варианты

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

Languages

In other projects