《动态环境中的规划》PPT课件.ppt

动态环境中的规划 路径规划 概要 规划经常是一个重复过程，且要求快速。 动态环境 不精确的初始模型 真体位置有误差 基于A*的规划器类型： ARA* 随时A*搜索 输出 亚优解 能在有时间约束下使用 D*与D*精简版 递增A*搜索 通过复用前次搜索结果来计算最佳解 常常能显著加速重复规划 随时D*(AD*) 随时递增A*搜索 输出 亚优解 能在有时间约束下使用 常常能显著加速重复规划 所有都基于ComputePathWithReuse函数 动态环境中的自动真体 ATRV机器人 Segbot机器人 2D地图 3D地图 规划（Planning） 规划 利用一个问题的结构来构造一个到达目的行动 计划 是以研究理性行动为己任的AI的核心部分 路径规划：对求解问题的路径及其代价进 行规划 基于搜索的规划 离散化 机器人对世界的认识规划图 基于搜索的规划 离散化 规划图 转化成图形 搜索图形得到 一条从sstart到 sgoal的最小代 价路径 8向连接网，为什么? 机器人对世界的认识 基于高维搜索的规划 2D（x,y）规划 54千个状态 规划快 执行慢 4D（x,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)=mins”pred(s)(g(s”)+c(s”,s) 由s3到sgoal边的 代价c(s3,sgoal) 搜索最小代价路径 最小代价路经是由回溯（backtracking）获 得的一条的贪婪路径 从sgoal开始，并且从任一状态s移向其前任状态 s，使得：s=argmins”pred(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中的后续态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值 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 下一个扩展状态：sstart g(s2)g(sstart)+c(sstart,s2) 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=sstart OPEN=s2 下一个扩展状态：s2 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=sstart,s2 OPEN=s1,s4 下一个扩展状态：s1 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=sstart,s2,s1 OPEN=s4,sgoal 下一个扩展状态：s4 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=sstart,s2,s1,s4 OPEN=sgoal,s3 下一个扩展状态：sgoal 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=sstart,s2,s1,s4,sgoal OPEN=s3 结束 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； 对每个已扩展状态，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.5 13次扩展 解=11次移动 =1.5 15次扩展 解=11次移动 =1.0 20次扩展 解=10次移动 构建随时搜索 执行一系列降低的加权A*搜索： =2.5 13次扩展 解=11次移动 =1.5 15次扩展 解=11次移动 =1.0 20次扩展 解=10次移动 效率低，这是因为： 不同搜索循环之间的许多状态值保持不变。 应复用上一次搜索的结果。 ARA*：有效随时搜索 执行一系列降低的加权A*搜索。 修改每次的加权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*搜索 用所有的不一致性的状态来初值化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 结束 现在能够计算一个最小代 价路径 当ComputePath终止后： 所有状态的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 观察到重要的变化 增加