{环境管理}动态环境中的规划

《{环境管理}动态环境中的规划》由会员分享，可在线阅读，更多相关《{环境管理}动态环境中的规划（45页珍藏版）》请在金锄头文库上搜索。

1、动态环境中的规划,路径规划,概要,规划经常是一个反复过程，且要求快速。 动态环境 不精确的初始模型 真体位置有误差 基于A*的规划器类型： ARA* 随时A*搜索 输出 亚优解 能在有时间约束下使用 D*与D*精简版 递增A*搜索 通过复用前次搜索结果来计算最佳解 常常能显著加速反复规划 随时D*(AD*) 随时递增A*搜索 输出 亚优解 能在有时间约束下使用 常常能显著加速反复规划 所有都基于ComputePathWithReuse函数,动态环境中的自动真体,ATRV机器人,Segbot机器人,2D地图,3D地图,规划（Planning）,规划 利用一个问题的结构来构造一个到达目的行动计划

2、是以研究理性行动为己任的AI的核心部分 路径规划：对求解问题的路径及其代价进行规划,基于搜索的规划,离散化,机器人对世界的认识,规划图,基于搜索的规划,离散化,规划图,转化成图形,搜索图形得到一条从sstart到sgoal的最小代价路径,8向连接网，为什么?,机器人对世界的认识,基于高维搜索的规划,2D（x,y）规划 54千个状态 规划快 执行慢,4D（x,y,V）规划 超过2千万个状态 规划慢 执行快,基于高维搜索的规划,6DOF机器人手臂 3x109个状态,20DOF机器人手臂 1026个状态,实际规划,由于下面原因，需多次再规划 环境变化 导航时，有人在附近 自动驾驶时，有其它车辆在路上

3、 环境模型不精确 位置估计有误差 需快速再规划，来满足时间约束。,实际规划,由于下面原因，需多次再规划 环境变化 导航时，有人在附近 自动驾驶时，有其它车辆在路上 环境模型不精确 位置估计有误差 需快速再规划，来满足时间约束。,用随时D*（即随时动态A*）来做4D规划,实际规划,用随时D*（即随时动态A*）来做3D停车规划,用随时D*（即随时动态A*）来做4D规划,实际规划,随时规划算法，例如， A*的随时复用（复用加权）版，即ARA* 快速找到第一个可能的亚优解，然后用其余时间来改进它。 允许满足时间约束。 再规划算法，例如， A*的递增版，也即D*与D*精简版 复用以前规划来加速再规划 很

4、适合于动态和/或部分已知的环境。 随时再规划算法，例如，随时递增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

5、),目前找到的一条从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

6、中移去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(

7、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*搜索：例

8、子,计算相关态的最佳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的每个不在

9、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=sg

10、oal,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

11、(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(

12、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

13、.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

14、(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)

15、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 下一个扩展状

16、态：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()； 公布