环境管理_动态环境中的规划教材

动态环境中的规划 路径规划 概要 规划经常是一个反复过程 且要求快速 动态环境不精确的初始模型真体位置有误差基于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 ifg 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 ifg 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 ifg 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 ifg 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 ifg 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 ifg 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 ifg 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 ifg 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中的后续态s ifg 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 ifg 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 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 KoenigandM Likhachev FastReplanningforNavigationinUnknownTerrain IEEETrans 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观察到重要的变化