动态环境中的规划.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * 复用加权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*（? =1） CLOSED={} OPEN={s4,sgoal} 下一个扩展状态：s4 g(s’)=mins”?pred(s’)(v(s”)+c(s”,s’)) 初始的OPEN包含所有不一致性的状态 示例：复用A*（? =1） CLOSED={s4} OPEN={sgoal,s3} 下一个扩展状态：sgoal 示例：复用A*（? =1） CLOSED={s4,sgoal} OPEN={s3} 结束 现在能够计算一个最小代价路径 当ComputePathWithReuse终止后，所有状态的g值都等于最终A*的g值。 回到实例 执行一系列? 降低的加权A*有哪些信誉好的足球投注网站： ? =2.5 13次扩展，解=11次移动 ? =1.5 15次扩展，解=11次移动 ? =1.0 20次扩展，解=10次移动 ARA*：执行一系列? 降低的ComputePathWithReuse函数： ? =2.5 13次扩展，解=11次移动 ? =1.5 1次扩展，解=11次移动 ? =1.0 9次扩展，解=10次移动 高维状态空间的ARA*规划 0.05秒的ARA*规划 90秒的ARA*规划 增加再规划功能 在动态环境下，边的代价会改变。 如果边的代价减小，则可用与上面相同的ComputePathWithReuse函数来重新计算一条路径；如果边的代价增加，则可用类似的函数来计算。 最佳再规划器：D*与D*精简版 置? 为1； 执行直到达到目标为止： ComputePathWithReuse()； 公布当前?亚优解路径； 沿着该路径移动直到探测到某种地图上没有的物体为止； 更新相应的边的代价； 置sgoal为真体的当前状态； 参考文献： S. Koenig and M. Likhachev, “Fast Replanning for Navigation in Unknown Terrain,” IEEE Trans. Robotics, 21, (3), 354-363, 2005 最佳再规划器：D*与D*精简版 置? 为1； 执行直到达到目标为止： ComputePathWithReuse()； 公布当前?亚优解路径； 沿着该路径移动直到探测到某种地图上没有的物体为止； 更新相应的边的代价； 置sgoal为真体的当前状态； 注： 有哪些信誉好的足球投注网站是向后进行的：sstart=真体的目标，sgoal=真体的当前状态，所有的边是反向的。 这样，在两次叫ComputePathWithReuse之间，sstart总是不变的，并且g值也很可能不变。 D*与D*精简版：示例 初始知识与初始目标距离 机器人移动之后的知识与目标距离 灰色区域的g值改变 D*与D*精简版：示例 初次A*有哪些信誉好的足球投注网站 初次D*精简版有哪些信誉好的足球投注网站 二次A*有哪些信誉好的足球投注网站 二次D*精简版有哪些信誉好的足球投注网站 随时再规划器：随时D* 置? 为大值； 执行直到到达目标为止： ComputePathWithReuse()； 公布当前?亚优解路径； 沿着该路径移动直到探测到某种地图上没有的物体为止； 更新相应的边的代价； 置sgoal为真体的当前状态； if 观察到重要的变化 增加? 或重新规划； else 减小? ； 随时D*规划 3DOF机器人手臂操纵一个末端执行器穿越动态环境。 在每步中有1秒钟的时间用于改善和（或）再规划。 开始时，? =20。 总结 规划经常是一个反复过程，且要求快速。 动态环境 不精确的初始模型 真体位置有误差 基于A*的规划器类型： ARA* 随时A*有哪些信誉好的足球投注网站 输出? 亚优解 能在有时间约束下使用 D*与D*精简版 递增A*有哪些信誉好的足球投注网站 通过复用前次有哪些信誉好的足球投注网站结果来计算最佳解 经常能显著加速反复规划 随时D*(AD*) 随时递增A*有哪些信誉好的足球投注网站 输出? 亚优解 能在有时间约束下使用 经常能显著加速反复规划 上述所有都基于