简介

LPA*算法，即Lifelong Planning A*算法，该算法于2001年由Sven Koenig和Maxim Likhachev提出，是一种增量启发式搜索版本的A*算法，这种路径规划算法适用于随着时间改变导致有限栅格地图上的边缘代价c(s1,s2)改变的问题，也就是随着时间改变障碍物增多或减少，网格点发生增删等，在许多场合下比再利用A*重新搜索更高效。

启发式搜索和增量式搜索的区别在于，启发式搜索是利用启发函数来对搜索进行指导，从而实现高效的搜索，启发式搜索是一种“智能”搜索，典型的算法例如A*算法、遗传算法等。增量搜索是对以前的搜索结果信息进行再利用来实现高效搜索，大大减少搜索范围和时间，典型的例如LPA*、D* Lite算法等。

和A*算法一样，LPA*算法采用非负、一致性的启发函数 h(s) 表示当前位置网格点 s 到目标点 Gool 的距离的估计， h(s) 一致性体现在服从以下三角不等式，可以由简单的三角形几何性质可以推出：

[公式]

图1

1.succ(s)或children(s)，表示网格点 s 下一时刻将要移动到的点，相当于 s 点的继承点，对于 Goal点，有succ(Goal)=∅ ；

2. pred(s)或parent(s)，表示前一时刻移动到当前位置 s 点来的网格点，相当于 s 点的前辈点，对于 Start 点，有pred(Start)=∅ ；

3. g*(s) ，表示Start点到当前 s 点的最短路径距离， g(s) 是对 g*(s) 值的估计， g*(s) 定义如下：

[公式]

4. rhs(s)被定义为：

[公式]

图2

在图2的a)中，

[公式]

[公式]

此时属于“正常情况”，即g(s)=rhs(s) ，此时 s 点为局部一致(locally consistent)；

在图2的b)中，如果边缘代价函数值c(s',s)由于环境发生改变从 B 变为 ∞ (即自由网格点 s 被障碍物占据)，则有

[公式]

[公式]

这种情况有g(s)≠rhs(s)，此时 s 点为局部不一致(locally inconsistent)。

局部不一致又分为过一致(Overconsistent)和欠一致(Subconsistent)。

当 g(s)>rhs(s)被称为局部过一致，即 s' 点到 s 点的边缘代价函数 c(s,s') 值变低，代表网格上障碍物被清除(例如c值从 ∞ 变为 B )或搜索到一条更短的“捷径”。

当 g(s)<rhs(s)被称为局部欠一致，当 s 点欠一致时，即 s' 点到 s点的边缘代价函数c值变高，代表着自由网格被障碍物所占据，这时 s 点的信息需要被重置，这时候就需要重新搜索计算最短路径。

5. Openlist或priority queue，和A*算法一样，表示被搜索网格点的集合，用 key(s) 来对这些网格点进行排序，值得注意的是所有Openlist的点都局部不一致，所有局部不一致的点都在列表上。

6. key(s)，代表着优先级队列中网格点选择的优先权，key值用于处理局部不一致的网格点， key(s) 由两个元素组成， key(s) 被定义为：

key(s)=[k1(s);k2(s)]

其中：

k1(s)=min{g(s),rhs(s)}+h(s,Goal)

k2(s)=min{g(s),rhs(s)}

key值之间的比较方式如下：

if k1(s)<= k1(s') or (k1(s)=k1(s') and k2(s)<= k2(s'))

k(s)<= k(s')

end

key值越小，其优先权越高，该点就越先被搜索。

伪代码

For each s in Graph
    s.g(x)=rhs(x)=∞;局部一致
end for each
startNode.rhs=0;局部过一致
Forever
    While(OpenList.Top().key < goal.key OR goal is incosistent)
    当OpenList中最优先点的key值小于目标点的key值或者目标点局部不一致时
        currentNode=OpenList.Pop()
        当前点为OpenList中最优先点，并将U中最优先的网格点删除
        if (currentNode is overconsistent)
        如果当前点局部过一致，代表网格上障碍物被清除或搜索到更短的“捷径”
            currentNode.g(x)=currentNode.rhs(x);
            令当前点的g(x)=rhs(x)，使其局部一致
        else
        否则
            currentNode.g(x)=∞;
            局部过一致g(s)>rhs(s)或一致g(s)=rhs(s)
        end if
        for each s in currentNode.Children[]
            update s.rhs(x);
            局部过一致g(s)>rhs(s)或一致g(s)=rhs(s)
        end for each
    End while
    Wait for changes in Graph
    For each connection (u,v) with changed cost
        Update connection(u,v);
        Make v locally inconsistent;
    end for each
End forever

请批评指正，谢谢 ～