Lifelong Planning A Star
1.简介
LPA*算法（全称Lifelong Planning A*算法）时Koenig和Likhachev在2004年提出的，是一种参考人工智能的增量搜索进行改进的A*算法。它被用来处理动态环境下从给定起始点到给定目标点的最短路径问题（划重点！！！起始点和目标点是固定的）。
A*算法的相关内容不再赘述，本文针对LPA*论文的相关内容进行分析。
2.符号表示
S：地形图中的路径节点的集合，s属于S
succ(s)：successors,节点s的后续节点集合，例如节点1，2，3\cdots i按顺序均已被搜索过，那么除了1~i的其它结点均属于succ(i)。
pred(s)：predecessors,类比上述，节点s的前代节点，与succ(s)的意义刚好相反。
c(s,s`)：两节点之间的代价函数。
g*(s)：节点s到起始点SStart的实际最短距离。
g(s)：节点s到起始点的预计最短距离，上面那个值是实际的最短距离，这个值是一个预计值，是随着算法求解进程不断变动的，当所有节点的g(s)=rhs(s)时，g(s)的值就是到起始点的实际最短距离，即g(s)=g*(s)。
rhs(s) ：right hand sides，为啥叫这名我也不知道，据说来自DynamicSWSF-FP算法。对于s的所有邻接节点，求它们到s的距离加上邻接节点自身的g值，其中最小的那个值作为s的 rhs 值。具体求法可以见下面的公式
U：同A*算法中的优先队列，依据每个节点的Key值进行排序。
Key[K1,K2]：优先队列排序依据的键值，包含两部分，K1与K2，优先比较K1，若相同则比较K2进行排序。K1等同于A*里的f(s)，K2等同于A*里的g(s)，K1与K2的计算方法见下面的图。
h(s) ：同A*中的类似，到目标点的估计距离，在论文中用的是到目标节点的绝对距离进行表示。
路径搜索的主要过程与A*类似，通过由优先队列里不断将Key最小的值取出来，通过相应的处理将相关邻接节点或者状态变动的节点加入到队列中，直到满足终止条件即可获得最短路径。具体搜索过程在后文介绍。
3.主要函数及公式
CalculateKey(s)：计算节点s的Key值。
Initialize()：初始化的函数。
UpdateVertex(u)：更新当前节点u的值。
ComputeShortestPath()：计算最短路径的函数。
Main()：主函数。
上图为rhs的计算方法。
上图为LPA*算法的伪代码。
节点状态定义：
局部连续（Locally Consistent）：g(s)=rhs(s)。当所有节点均为局部连续状态时，g(s)的值等于s到起始点的最短距离（注意，反向不成立）。这个概念很重要，当上述条件满足时，我们可以找到任意一点u到起始点的最短路径，假设当前位置为s,父辈节点s’(向着起始点前进的下一个节点)通过最小化(g(s’)+c(s,s’))来获得，不断重复直到到达sStart。然而，LPA*并不需要使所有节点均为局部连续状态，它通过启发式搜索将关注点放在搜索上，并且只更新那些与计算最短路径相关的节点的g值。
局部过连续（Locally Overconsistent）：g(s)>rhs(s)。当优先队列U中取出的节点为局部过连续状态时，意味着g(s)可以通过父辈节点使自己到起点的路径更短，此时将设置g(s)=rhs(s)，节点状态变为局部连续状态。
局部欠连续(Locally Underconsistent)：g(s)<rhs(s)。这种情况通常出现在父辈的某一节点突然变为障碍的情况下，造成父辈节点到起点的路径变大，从而需要修改g(s)的值，如果节点处于这种状态，则当它由优先队列中取出时，将其g值设置为无穷大，即将该节点状态变为局部过连续，而局部过连续的点将会被再次添加到优先队列中，这样就可以在它下次被取出时将其作为局部过连续状态处理，最终达到局部连续状态（如果这一节点与我们要搜索的最短路径相关的话）。
4.算法实际演示
论文中以二维平面网格地图作为演示对象，每一个网格与周围八个网格相连（相互之间可以直接到达），黑色网格为障碍。
第一次搜索：地形发生变动之前的路径搜索，与A*搜索基本相同。起点为右上角的点，目标点为左下角的点。第一张图描述了各点的到起始点的最短距离以及各点到目标点的h值。左侧为g*值，右侧为h值。最开始所有点rhs和g均设为无穷，然后由起始点开始，将起始点的rhs设置为0，然后如上图过程不断迭代，直到获得最短路径。
第二次搜索：当场景中地形状态发生变动，在该例子中，节点(D,1)变为障碍。首先对该节点进行更新，并将其后代节点置于优先队列中，该节点的变动对父辈节点的状态并无影响。同第一次搜索类似，不断进行迭代直到再次找到到目标位置的最短路径。
下图显示的是两次搜索的结果图，通过由目标位置开始不断选择最小的g+h值（即表格中的数值）直到到达起始点，来获得到起始点的最短路径。
5.总结
LPA*提出了一种解决动态环境下的最短路径搜索方法，但是它针对的是起始点和目标点固定的情况，如果在机器人按照搜索到的最短路径行走过程中，环境中某些节点发生变化，这时如果想获得新的路径，就得以机器人当前节点为起始点，重新用LPA*算法解算一次，这效率是很低的。针对这种情况，该论文的作者随后提出了D* Lite算法来作为处理动态环境最短路径问题的高效方法。