5动态环境中的规划.pptx

动态环境中的规划动态环境中的规划路径规划路径规划概要概要规划经常是一个反复过程，且要求快速动态环境不精确的初始模型真体位置有误差基于A*的规划器类型：ARA*随时A*搜索输出 亚优解能在有时间约束下使用D*与D*精简版递增A*搜索通过复用前次搜索结果来计算最正确解常常能显著加速反复规划随时D*(AD*)随时递增A*搜索输出 亚优解能在有时间约束下使用常常能显著加速反复规划所有都基于ComputePathWithReuse函数动态环境中的自动真体动态环境中的自动真体ATRV机器人Segbot机器人2D地图3D地图规划规划Planning规划利用一个问题的结构来构造一个到达目的行动方案是以研究理性行动为己任的AI的核心局部路径规划：对求解问题的路径及其代价进行规划基于搜索的规划基于搜索的规划离散化机器人对世界的认识规划图基于搜索的规划基于搜索的规划离散化规划图转化成图形搜索图形得到一条从sstart到sgoal的最小代价路径8向连接网，为什么?机器人对世界的认识基于高维搜索的规划基于高维搜索的规划2Dx,y规划54千个状态规划快执行慢4Dx,y,V规划超过2千万个状态规划慢执行快基于高维搜索的规划基于高维搜索的规划6DOF机器人手臂3x109个状态20DOF机器人手臂1026个状态实际规划实际规划由于下面原因，需屡次再规划环境变化导航时，有人在附近自动驾驶时，有其它车辆在路上环境模型不精确位置估计有误差需快速再规划，来满足时间约束。

实际规划实际规划由于下面原因，需屡次再规划环境变化导航时，有人在附近自动驾驶时，有其它车辆在路上环境模型不精确位置估计有误差需快速再规划，来满足时间约束用随时D*即随时动态A*来做4D规划实际规划实际规划用随时D*即随时动态A*来做3D停车规划用随时D*即随时动态A*来做4D规划实际规划实际规划随时规划算法，例如， A*的随时复用复用加权版，即ARA*快速找到第一个可能的亚优解，然后用其余时间来改进它允许满足时间约束再规划算法，例如， A*的递增版，也即D*与D*精简版复用以前规划来加速再规划很适合于动态和/或局部的环境随时再规划算法，例如，随时递增A*，即随时D*结合上述两者的优点搜索最小代价路径搜索最小代价路径计算相关态的g值g(s)：一条从sstart到s的最小代价路径的代价估值最正确值满足： g(s)=minspred(s)(g(s)+c(s,s)由s3到sgoal边的代价c(s3,sgoal)搜索最小代价路径搜索最小代价路径最小代价路经是由回溯backtracking获得的一条的贪婪路径从sgoal开始，并且从任一状态s移向其前任状态s，使得：s=argminspred(s)(g(s)+c(s,s)A*搜索搜索计算相关态的最正确g值在某一时刻：g(s)h(s)目前找到的一条从sstart到s最短路径的代价一条从s到sgoal最短路径的代价的(低)估值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值ComputePath函数：while (sgoal没有被扩展过)从OPEN中移去f(s)( = g(s)+h(s)最小的s；把s插入CLOSED；对s的每个不在CLOSED中的后续态sif 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值ComputePath函数：while (sgoal没有被扩展)从OPEN中移去f(s)( = g(s)+h(s)最小的s；把s插入CLOSED；对s的每个不在CLOSED中的后续态sif 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值ComputePath函数：while (sgoal没有被扩展)从OPEN中移去f(s)( = g(s)+h(s)最小的s；把s插入CLOSED；对s的每个不在CLOSED中的后续态sif g(s)g(s)+c(s,s)g(s)=g(s)+c(s,s)；把s 插入OPEN；CLOSED=sstartOPEN=s2下一个扩展状态：s2A*搜索：例子搜索：例子计算相关态的最正确g值ComputePath函数：while (sgoal没有被扩展)从OPEN中移去f(s)( = g(s)+h(s)最小的s；把s插入CLOSED；对s的每个不在CLOSED中的后续态sif g(s)g(s)+c(s,s)g(s)=g(s)+c(s,s)；把s 插入OPEN；CLOSED=sstart,s2OPEN=s1,s4下一个扩展状态：s1A*搜索：例子搜索：例子计算相关态的最正确g值ComputePath函数：while (sgoal没有被扩展)从OPEN中移去f(s)( = g(s)+h(s)最小的s；把s插入CLOSED；对s的每个不在CLOSED中的后续态sif g(s)g(s)+c(s,s)g(s)=g(s)+c(s,s)；把s 插入OPEN；CLOSED=sstart,s2,s1OPEN=s4,sgoal下一个扩展状态：s4A*搜索：例子搜索：例子计算相关态的最正确g值ComputePath函数：while (sgoal没有被扩展)从OPEN中移去f(s)( = g(s)+h(s)最小的s；把s插入CLOSED；对s的每个不在CLOSED中的后续态sif g(s)g(s)+c(s,s)g(s)=g(s)+c(s,s)；把s 插入OPEN；CLOSED=sstart,s2,s1,s4OPEN=sgoal,s3下一个扩展状态：sgoalA*搜索：例子搜索：例子计算相关态的最正确g值ComputePath函数：while (sgoal没有被扩展)从OPEN中移去f(s)( = g(s)+h(s)最小的s；把s插入CLOSED；对s的每个不在CLOSED中的后续态sif g(s)g(s)+c(s,s)g(s)=g(s)+c(s,s)；把s 插入OPEN；CLOSED=sstart,s2,s1,s4,sgoalOPEN=s3结束A*搜索：例子搜索：例子计算相关态的最正确g值ComputePath函数：while (sgoal没有被扩展)从OPEN中移去f(s)( = g(s)+h(s)最小的s；把s插入CLOSED；对s的每个不在CLOSED中的后续态sif g(s)g(s)+c(s,s)g(s)=g(s)+c(s,s)；把s 插入OPEN；对每个已扩展状态，g(s)是最正确的。

对每个其它状态，g(s)是一个上限现在能计算一条最小代价路径加权加权A*以f(s)= g(s)+h(s)(1)为次序来扩展状态亚优解：cost(解) cost(最正确解)在解许多问题时，比A*快得多A*最正确解的性质最正确解的性质f(s) = g(s) + h(s)为次序来扩展状态为次序来扩展状态C*为最正确路径的代价，为最正确路径的代价，A*搜索：搜索：将扩展将扩展f(s) C*的任何结点的任何结点特例：特例：h(s) = 0，f(s) = g(s) UCS搜索，需扩展所有当搜索，需扩展所有当前态的后续态前态的后续态h(s) = h*(s)，f(s) = g(s) + h*(s)，只扩展一个当，只扩展一个当前态的最正确后续态前态的最正确后续态加权加权A*：例如：例如A*11,054次扩展代价=168,204 =10的加权A*1,138次扩展代价=177,876构建随时搜索构建随时搜索执行一系列降低的加权A*搜索：置为大值；while 1，并且仍留有时间来进行规划执行加权A*搜索；给出当前亚优解；降低 ； =2.513次扩展解=11次移动 =1.515次扩展解=11次移动 =1.020次扩展解=10次移动构建随时搜索构建随时搜索执行一系列 降低的加权A*搜索： =2.513次扩展解=11次移动 =1.515次扩展解=11次移动 =1.020次扩展解=10次移动效率低，这是因为：不同搜索循环之间的许多状态值保持不变。

应复用上一次搜索的结果ARA*：有效随时：有效随时(复用加权复用加权)搜索搜索执行一系列 降低的加权A*搜索修改每次的加权A*搜索，使其复用上次搜索结果持续保证亚优解复用加权复用加权A*搜索搜索置所有 的初值为无穷；ComputePath函数：while (sgoal没有被扩展)从OPEN中移去f(s)( = g(s)+h(s)最小的s；把s插入CLOSED； (s)=g(s)；对s的每个不在CLOSED中的后续态sif g(s)g(s)+c(s,s)g(s)=g(s)+c(s,s)；把s 插入OPEN；注： 值是一个状态在其扩展过程中的值g(s)=minspred(s)(v(s)+c(s,s)OPEN：一个(s)(=)g(s)不一致性状态的集其它所有状态有(s)=g(s) 一致性复用加权复用加权A*搜索搜索用所有的不一致性的状态来初值化OPEN；ComputePathWithReuse函数：while (sgoal没有被扩展)从OPEN中移去f(s)( = g(s)+h(s)最小的s；把s插入CLOSED； (s)=g(s)；对s的每个不在CLOSED中的后续态sif g(s)g(s)+c(s,s)g(s)=g(s)+c(s,s)；把s 插入OPEN；注： 值是一个状态在其扩展过程中的值。

g(s)=minspred(s)(v(s)+c(s,s)OPEN：一个(s)g(s)不一致性状态的集其它所有状态有(s)=g(s) 一致性初始化OPEN时，使用上次搜索结果例如：复用例如：复用A* =1CLOSED=OPEN=s4,sgoal下一个扩展状态：s4g(s)=minspred(s)(v(s)+c(s,s)初始的初始的OPEN包含所有不一致性的状态包含所有不一致性的状态例如：复用例如：复用A* =1CLOSED=s4OPEN=sgoal,s3下一个扩展状态：sgoal例如：复用例如：复用A* =1CLOSED=s4,sgoalOPEN=s3结束现在能够计算一个最小代价路径当ComputePathWithReuse终止后，所有状态的g值都等于最终A*的g值回到实例回到实例执行一系列 降低的加权A*搜索： =2.513次扩展，解=11次移动 =1.515次扩展，解=11次移动 =1.020次扩展，解=10次移动ARA*：执行一系列 降低的ComputePathWithReuse函数： =2.513次扩展，解=11次移动 =1.51次扩展，解=11次移动 =1.09次扩展，解=10次移动高维状态空间的高维状态空间的ARA*规划规划0.05秒的ARA*规划90秒的ARA*规划增加再规划功能增加再规划功能在动态环境下，边的代价会改变。

如果边的代价减小，那么可用与上面相同的ComputePathWithReuse函数来重新计算一条路径；如果边的代价增加，那么可用类似的函数来计算最正确再规划器：最正确再规划器：D*与与D*精简版精简版置 为1；执行直到到达目标为止：ComputePathWithReuse()；公布当前亚优解路径；沿着该路径移动直到探测到某种地图上没有的物体为止；更新相应的边的代价；置sgoal为真体的当前状态；参考文献：S. Koenig and M. 。