动态环境中的规划-课件

动态环境中的规划路径规划动态环境中的规划路径规划概要规划经常是一个反复过程，且要求快速。动态环境不精确的初始模型真体位置有误差基于A*的规划器类型：ARA*随时A*搜索输出亚优解能在有时间约束下使用D*与D*精简版递增A*搜索通过复用前次搜索结果来计算最佳解常常能显著加速反复规划随时D*(AD*)随时递增A*搜索输出亚优解能在有时间约束下使用常常能显著加速反复规划所有都基于ComputePathWithReuse函数概要规划经常是一个反复过程，且要求快速。动态环境中的自动真体ATRV机器人Segbot机器人2D地图3D地图动态环境中的自动真体ATRV机器人Segbot机器人2D地图规划（Planning）规划利用一个问题的结构来构造一个到达目的行动计划是以研究理性行动为己任的AI的核心部分路径规划：对求解问题的路径及其代价进行规划规划（Planning）规划基于搜索的规划离散化机器人对世界的认识规划图基于搜索的规划离散化机器人对世界的认识规划图基于搜索的规划离散化规划图转化成图形搜索图形得到一条从sstart到sgoal的最小代价路径8向连接网，为什么?机器人对世界的认识基于搜索的规划离散化规划图转化成图形搜索图形得到一条从sst基于高维搜索的规划2D（x,y）规划54千个状态规划快执行慢4D（x,y,,V）规划超过2千万个状态规划慢执行快基于高维搜索的规划2D（x,y）规划4D（x,y,,V）规基于高维搜索的规划6DOF机器人手臂>3x109个状态20DOF机器人手臂>1026个状态基于高维搜索的规划6DOF机器人手臂20DOF机器人手臂实际规划由于下面原因，需多次再规划环境变化导航时，有人在附近自动驾驶时，有其它车辆在路上环境模型不精确位置估计有误差需快速再规划，来满足时间约束。实际规划由于下面原因，需多次再规划实际规划由于下面原因，需多次再规划环境变化导航时，有人在附近自动驾驶时，有其它车辆在路上环境模型不精确位置估计有误差需快速再规划，来满足时间约束。用随时D*（即随时动态A*）来做4D规划实际规划由于下面原因，需多次再规划用随时D*（即随时动态A*实际规划用随时D*（即随时动态A*）来做3D停车规划用随时D*（即随时动态A*）来做4D规划实际规划用随时D*（即随时动态A*）来做3D停车规划用随时D实际规划随时规划算法，例如，A*的随时复用（复用加权）版，即ARA*快速找到第一个可能的亚优解，然后用其余时间来改进它。允许满足时间约束。再规划算法，例如，A*的递增版，也即D*与D*精简版复用以前规划来加速再规划很适合于动态和/或部分已知的环境。随时再规划算法，例如，随时递增A*，即随时D*结合上述两者的优点。实际规划随时规划算法，例如，A*的随时复用（复用加权）版，搜索最小代价路径计算相关态的g值g(s)：一条从sstart到s的最小代价路径的代价估值。最佳值满足：g(s)=mins”pred(s)(g(s”)+c(s”,s))由s3到sgoal边的代价c(s3,sgoal)搜索最小代价路径计算相关态的g值由s3到sgoal边的代价c搜索最小代价路径最小代价路经是由回溯（backtracking）获得的一条的贪婪路径从sgoal开始，并且从任一状态s移向其前任状态s’，使得：s’=argmins”pred(s)(g(s”)+c(s”,s))搜索最小代价路径最小代价路经是由回溯（backtrackinA*搜索计算相关态的最佳g值在某一时刻：g(s)h(s)目前找到的一条从sstart到s最短路径的代价一条从s到sgoal最短路径的代价的(低)估值A*搜索计算相关态的最佳g值g(s)h(s)目前找到的一条从A*搜索计算相关态的最佳g值主函数：g(sstart)=0；所有其它g值是无穷；OPEN={sstart}；ComputePath()；给出结果；ComputePath函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

扩展s；注：OPEN是扩展候选态的集。如果启发方式是一致性的，则每个扩展态的g(s)都是最佳的。A*搜索计算相关态的最佳g值注：A*搜索计算相关态的最佳g值ComputePath函数：while(sgoal没有被扩展过) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；注：CLOSED是已扩展状态的集。if体中重新给g(s’)(=)赋值，是试图用找到的从sstart到s的路径来降低g(s’)。A*搜索计算相关态的最佳g值注：A*搜索：例子计算相关态的最佳g值ComputePath函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；CLOSED={}OPEN={sstart}下一个扩展状态：sstartg(s2)>g(sstart)+c(sstart,s2)A*搜索：例子计算相关态的最佳g值CLOSED={}g(s2A*搜索：例子计算相关态的最佳g值ComputePath函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；CLOSED={sstart}OPEN={s2}下一个扩展状态：s2A*搜索：例子计算相关态的最佳g值CLOSED={sstarA*搜索：例子计算相关态的最佳g值ComputePath函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；CLOSED={sstart,s2}OPEN={s1,s4}下一个扩展状态：s1A*搜索：例子计算相关态的最佳g值CLOSED={sstarA*搜索：例子计算相关态的最佳g值ComputePath函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；CLOSED={sstart,s2,s1}OPEN={s4,sgoal}下一个扩展状态：s4A*搜索：例子计算相关态的最佳g值CLOSED={sstarA*搜索：例子计算相关态的最佳g值ComputePath函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；CLOSED={sstart,s2,s1,s4}OPEN={sgoal,s3}下一个扩展状态：sgoalA*搜索：例子计算相关态的最佳g值CLOSED={sstarA*搜索：例子计算相关态的最佳g值ComputePath函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；CLOSED={sstart,s2,s1,s4,sgoal}OPEN={s3}结束A*搜索：例子计算相关态的最佳g值CLOSED={sstarA*搜索：例子计算相关态的最佳g值ComputePath函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；对每个已扩展状态，g(s)是最佳的。对每个其它状态，g(s)是一个上限。现在能计算一条最小代价路径。A*搜索：例子计算相关态的最佳g值对每个已扩展状态，g(s)加权A*以f(s)=g(s)+h(s)(>1)为次序来扩展状态。亚优解：cost(解)cost(最佳解)。在解许多问题时，比A*快得多。加权A*以f(s)=g(s)+h(s)(>1)为次序来A*最佳解的性质f(s)=g(s)+h(s)为次序来扩展状态。C*为最佳路径的代价，A*搜索：将扩展f(s)<C*的所有结点可能扩展f(s)=C*的一些结点不扩展f(s)>C*的任何结点特例：h(s)=0，f(s)=g(s)UCS搜索，需扩展所有当前态的后续态h(s)=h*(s)，f(s)=g(s)+h*(s)，只扩展一个当前态的最佳后续态A*最佳解的性质f(s)=g(s)+h(s)为次序来加权A*：示例A*11,054次扩展代价=168,204=10的加权A*1,138次扩展代价=177,876加权A*：示例A*=10的加权A*构建随时搜索执行一系列降低的加权A*搜索：置为大值；while

1，并且仍留有时间来进行规划 执行加权A*搜索； 给出当前亚优解； 降低；=2.513次扩展解=11次移动=1.515次扩展解=11次移动=1.020次扩展解=10次移动构建随时搜索执行一系列降低的加权A*搜索：=2.5构建随时搜索执行一系列降低的加权A*搜索：=2.513次扩展解=11次移动=1.515次扩展解=11次移动=1.020次扩展解=10次移动效率低，这是因为：不同搜索循环之间的许多状态值保持不变。应复用上一次搜索的结果。构建随时搜索执行一系列降低的加权A*搜索：=2.5ARA*：有效随时(复用加权)搜索执行一系列降低的加权A*搜索。修改每次的加权A*搜索，使其复用上次搜索结果。持续保证亚优解。ARA*：有效随时(复用加权)搜索执行一系列降低的加权A复用加权A*搜索置所有的初值为无穷；ComputePath函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED；

(s)=g(s)； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；注：值是一个状态在其扩展过程中的值。g(s’)=mins”pred(s’)(v(s”)+c(s”,s’))OPEN：一个(s)(=)>g(s)（不一致性）状态的集。其它所有状态有(s)=g(s)（一致性）。复用加权A*搜索置所有的初值为无穷；注：复用加权A*搜索用所有的不一致性的状态来初值化OPEN；ComputePathWithReuse函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED；

(s)=g(s)； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；注：值是一个状态在其扩展过程中的值。g(s’)=mins”pred(s’)(v(s”)+c(s”,s’))OPEN：一个(s)>g(s)（不一致性）状态的集。其它所有状态有(s)=g(s)（一致性）。初始化OPEN时，使用上次搜索结果。复用加权A*搜索用所有的不一致性的状态来初值化OPEN；注：示例：复用A*（=1）CLOSED={}OPEN={s4,sgoal}下一个扩展状态：s4g(s’)=mins”pred(s’)(v(s”)+c(s”,s’))初始的OPEN包含所有不一致性的状态示例：复用A*（=1）CLOSED={}g(s’)=mi示例：复用A*（=1）CLOSED={s4}OPEN={sgoal,s3}下一个扩展状态：sgoal示例：复用A*（=1）CLOSED={s4}示例：复用A*（=1）CLOSED={s4,sgoal}OPEN={s3}结束现在能够计算一个最小代价路径当ComputePathWithReuse终止后，所有状态的g值都等于最终A*的g值。示例：复用A*（=1）CLOSED={s4,sgoal}回到实例执行一系列降低的加权A*搜索：=2.513次扩展，解=11次移动=1.515次扩展，解=11次移动=1.020次扩展，解=10次移动ARA*：执行一系列降低的ComputePathWithReuse函数：=2.513次扩展，解=11次移动=1.51次扩展，解=11次移动=1.09次扩展，解=10次移动回到实例执行一系列降低的加权A*搜索：=2.5=高维状态空间的ARA*规划0.05秒的ARA*规划90秒的ARA*规划高维状态空间的ARA*规划0.05秒的ARA*规划90秒的A增加再规划功能在动态环境下，边的代价会改变。如果边的代价减小，则可用与上面相同的ComputePathWithReuse函数来重新计算一条路径；如果边的代价增加，则可用类似的函数来计算。增加再规划功能在动态环境下，边的代价会改变。最佳再规划器：D*与D*精简版置为1；执行直到达到目标为止：

ComputePathWithReuse()； 公布当前亚优解路径； 沿着该路径移动直到探测到某种地图上没有的物体为止； 更新相应的边的代价；

置sgoal为真体的当前状态；参考文献：S.KoenigandM.Likhachev,“FastReplanningforNavigationinUnknownTerrain,”IEEETrans.Robotics,21,(3),354-363,2005最佳再规划器：D*与D*精简版置为1；最佳再规划器：D*与D*精简版置为1；执行直到达到目标为止：

ComputePathWithReuse()； 公布当前亚优解路径； 沿着该路径移动直到探测到某种地图上没有的物体为止； 更新相应的边的代价；

置sgoal为真体的当前状态；注： 搜索是向后进行的：sstart=真体的目标，sgoal=真体的当前状态，所有的边是反向的。这样，在两次叫ComputePathWithReuse之间，sstart总是不变的，并且g值也很可能不变。最佳再规划器：D*与D*精简版置为1；注： D*与D*精简版：示例初始知识与初始目标距离机器人移动之后的知识与目标距离灰色区域的g值改变D*与D*精简版：示例初始知识与初始目标距离机器人移动之后的D*与D*精简版：示例初次A*搜索初次D*精简版搜索二次A*搜索二次D*精简版搜索D*与D*精简版：示例初次A*搜索初次D*精简版搜索二次A*随时再规划器：随时D*置为大值；执行直到到达目标为止：

ComputePathWithReuse()； 公布当前亚优解路径； 沿着该路径移动直到探测到某种地图上没有的物体为止； 更新相应的边的代价；

置sgoal为真体的当前状态；

if

观察到重要的变化 增加或重新规划；

else

减小；随时再规划器：随时D*置为大值；随时D*规划3DOF机器人手臂操纵一个末端执行器穿越动态环境。在每步中有1秒钟的时间用于改善和（或）再规划。开始时，=20。随时D*规划3DOF机器人手臂操纵一个末端执行器穿越动态环境总结规划经常是一个反复过程，且要求快速。动态环境不精确的初始模型真体位置有误差基于A*的规划器类型：ARA*随时A*搜索输出亚优解能在有时间约束下使用D*与D*精简版递增A*搜索通过复用前次搜索结果来计算最佳解经常能显著加速反复规划随时D*(AD*)随时递增A*搜索输出亚优解能在有时间约束下使用经常能显著加速反复规划上述所有都基于ComputePathWithReuse函数总结规划经常是一个反复过程，且要求快速。演讲完毕，谢谢观看！演讲完毕，谢谢观看！动态环境中的规划路径规划动态环境中的规划路径规划概要规划经常是一个反复过程，且要求快速。动态环境不精确的初始模型真体位置有误差基于A*的规划器类型：ARA*随时A*搜索输出亚优解能在有时间约束下使用D*与D*精简版递增A*搜索通过复用前次搜索结果来计算最佳解常常能显著加速反复规划随时D*(AD*)随时递增A*搜索输出亚优解能在有时间约束下使用常常能显著加速反复规划所有都基于ComputePathWithReuse函数概要规划经常是一个反复过程，且要求快速。动态环境中的自动真体ATRV机器人Segbot机器人2D地图3D地图动态环境中的自动真体ATRV机器人Segbot机器人2D地图规划（Planning）规划利用一个问题的结构来构造一个到达目的行动计划是以研究理性行动为己任的AI的核心部分路径规划：对求解问题的路径及其代价进行规划规划（Planning）规划基于搜索的规划离散化机器人对世界的认识规划图基于搜索的规划离散化机器人对世界的认识规划图基于搜索的规划离散化规划图转化成图形搜索图形得到一条从sstart到sgoal的最小代价路径8向连接网，为什么?机器人对世界的认识基于搜索的规划离散化规划图转化成图形搜索图形得到一条从sst基于高维搜索的规划2D（x,y）规划54千个状态规划快执行慢4D（x,y,,V）规划超过2千万个状态规划慢执行快基于高维搜索的规划2D（x,y）规划4D（x,y,,V）规基于高维搜索的规划6DOF机器人手臂>3x109个状态20DOF机器人手臂>1026个状态基于高维搜索的规划6DOF机器人手臂20DOF机器人手臂实际规划由于下面原因，需多次再规划环境变化导航时，有人在附近自动驾驶时，有其它车辆在路上环境模型不精确位置估计有误差需快速再规划，来满足时间约束。实际规划由于下面原因，需多次再规划实际规划由于下面原因，需多次再规划环境变化导航时，有人在附近自动驾驶时，有其它车辆在路上环境模型不精确位置估计有误差需快速再规划，来满足时间约束。用随时D*（即随时动态A*）来做4D规划实际规划由于下面原因，需多次再规划用随时D*（即随时动态A*实际规划用随时D*（即随时动态A*）来做3D停车规划用随时D*（即随时动态A*）来做4D规划实际规划用随时D*（即随时动态A*）来做3D停车规划用随时D实际规划随时规划算法，例如，A*的随时复用（复用加权）版，即ARA*快速找到第一个可能的亚优解，然后用其余时间来改进它。允许满足时间约束。再规划算法，例如，A*的递增版，也即D*与D*精简版复用以前规划来加速再规划很适合于动态和/或部分已知的环境。随时再规划算法，例如，随时递增A*，即随时D*结合上述两者的优点。实际规划随时规划算法，例如，A*的随时复用（复用加权）版，搜索最小代价路径计算相关态的g值g(s)：一条从sstart到s的最小代价路径的代价估值。最佳值满足：g(s)=mins”pred(s)(g(s”)+c(s”,s))由s3到sgoal边的代价c(s3,sgoal)搜索最小代价路径计算相关态的g值由s3到sgoal边的代价c搜索最小代价路径最小代价路经是由回溯（backtracking）获得的一条的贪婪路径从sgoal开始，并且从任一状态s移向其前任状态s’，使得：s’=argmins”pred(s)(g(s”)+c(s”,s))搜索最小代价路径最小代价路经是由回溯（backtrackinA*搜索计算相关态的最佳g值在某一时刻：g(s)h(s)目前找到的一条从sstart到s最短路径的代价一条从s到sgoal最短路径的代价的(低)估值A*搜索计算相关态的最佳g值g(s)h(s)目前找到的一条从A*搜索计算相关态的最佳g值主函数：g(sstart)=0；所有其它g值是无穷；OPEN={sstart}；ComputePath()；给出结果；ComputePath函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

扩展s；注：OPEN是扩展候选态的集。如果启发方式是一致性的，则每个扩展态的g(s)都是最佳的。A*搜索计算相关态的最佳g值注：A*搜索计算相关态的最佳g值ComputePath函数：while(sgoal没有被扩展过) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；注：CLOSED是已扩展状态的集。if体中重新给g(s’)(=)赋值，是试图用找到的从sstart到s的路径来降低g(s’)。A*搜索计算相关态的最佳g值注：A*搜索：例子计算相关态的最佳g值ComputePath函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；CLOSED={}OPEN={sstart}下一个扩展状态：sstartg(s2)>g(sstart)+c(sstart,s2)A*搜索：例子计算相关态的最佳g值CLOSED={}g(s2A*搜索：例子计算相关态的最佳g值ComputePath函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；CLOSED={sstart}OPEN={s2}下一个扩展状态：s2A*搜索：例子计算相关态的最佳g值CLOSED={sstarA*搜索：例子计算相关态的最佳g值ComputePath函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；CLOSED={sstart,s2}OPEN={s1,s4}下一个扩展状态：s1A*搜索：例子计算相关态的最佳g值CLOSED={sstarA*搜索：例子计算相关态的最佳g值ComputePath函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；CLOSED={sstart,s2,s1}OPEN={s4,sgoal}下一个扩展状态：s4A*搜索：例子计算相关态的最佳g值CLOSED={sstarA*搜索：例子计算相关态的最佳g值ComputePath函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；CLOSED={sstart,s2,s1,s4}OPEN={sgoal,s3}下一个扩展状态：sgoalA*搜索：例子计算相关态的最佳g值CLOSED={sstarA*搜索：例子计算相关态的最佳g值ComputePath函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；CLOSED={sstart,s2,s1,s4,sgoal}OPEN={s3}结束A*搜索：例子计算相关态的最佳g值CLOSED={sstarA*搜索：例子计算相关态的最佳g值ComputePath函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；对每个已扩展状态，g(s)是最佳的。对每个其它状态，g(s)是一个上限。现在能计算一条最小代价路径。A*搜索：例子计算相关态的最佳g值对每个已扩展状态，g(s)加权A*以f(s)=g(s)+h(s)(>1)为次序来扩展状态。亚优解：cost(解)cost(最佳解)。在解许多问题时，比A*快得多。加权A*以f(s)=g(s)+h(s)(>1)为次序来A*最佳解的性质f(s)=g(s)+h(s)为次序来扩展状态。C*为最佳路径的代价，A*搜索：将扩展f(s)<C*的所有结点可能扩展f(s)=C*的一些结点不扩展f(s)>C*的任何结点特例：h(s)=0，f(s)=g(s)UCS搜索，需扩展所有当前态的后续态h(s)=h*(s)，f(s)=g(s)+h*(s)，只扩展一个当前态的最佳后续态A*最佳解的性质f(s)=g(s)+h(s)为次序来加权A*：示例A*11,054次扩展代价=168,204=10的加权A*1,138次扩展代价=177,876加权A*：示例A*=10的加权A*构建随时搜索执行一系列降低的加权A*搜索：置为大值；while

1，并且仍留有时间来进行规划 执行加权A*搜索； 给出当前亚优解； 降低；=2.513次扩展解=11次移动=1.515次扩展解=11次移动=1.020次扩展解=10次移动构建随时搜索执行一系列降低的加权A*搜索：=2.5构建随时搜索执行一系列降低的加权A*搜索：=2.513次扩展解=11次移动=1.515次扩展解=11次移动=1.020次扩展解=10次移动效率低，这是因为：不同搜索循环之间的许多状态值保持不变。应复用上一次搜索的结果。构建随时搜索执行一系列降低的加权A*搜索：=2.5ARA*：有效随时(复用加权)搜索执行一系列降低的加权A*搜索。修改每次的加权A*搜索，使其复用上次搜索结果。持续保证亚优解。ARA*：有效随时(复用加权)搜索执行一系列降低的加权A复用加权A*搜索置所有的初值为无穷；ComputePath函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED；

(s)=g(s)； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；注：值是一个状态在其扩展过程中的值。g(s’)=mins”pred(s’)(v(s”)+c(s”,s’))OPEN：一个(s)(=)>g(s)（不一致性）状态的集。其它所有状态有(s)=g(s)（一致性）。复用加权A*搜索置所有的初值为无穷；注：复用加权A*搜索用所有的不一致性的状态来初值化OPEN；ComputePathWithReuse函数：while(sgoal没有被扩展) 从OPEN中移去f(s)(=g(s)+h(s))最小的s；

把s插入CLOSED；

(s)=g(s)； 对s的每个不在CLOSED中的后续态s’

if

g(s’)>g(s)+c(s,s’)

g(s’)=g(s)+c(s,s’)； 把s’插入OPEN；注：值是一个状态在其扩展过程中的值。g(s’)=mins”pred(s’)(v(s”)+c(s”,s’))OPEN：一个(s)>g(s)（不一致性）状态的集。其它所有状态有(s)=g(s)（一致性）。初始化OPEN时，使用上次搜索结果。复用加权A*搜索用所有的不一致性的状态来初值化OPEN；注：示例：复用A*（=1）CLOSED={}OPEN={s4,sgoal}下一个扩展状态：s4g(s’)=mins”pred(s’)(v(s”)+c(s”,s’))初始的OPEN包含所有不一致性的状态示例：复用A*（=1）CLOSED={}g(s’)=mi示例：复用A*（=1）CLOSED={s4}OPEN={sgoal,s3}下一个扩展状态：sgoal示例：复用A*（=1）CLOSED={s4}示例：复用A*（=1）CLOSED={s4,sgoal}OPEN={s3}结束现在能够计算一个最小代价路径当ComputePathWithReuse终止后，所有状态的g值都等于最终A*的g值。示例：复用A*（=1）CLOSED={s4,