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

1、动态环境的规划、路径规划、摘要和计划往往是迭代过程，需要更快的速度。动态环境中不正确的初始模型true位置中存在错误基于A*的计划员类型：ARA*随时A*搜索输出A*搜索输出a-时间约束D*和D*精简版本增加A*搜索通过重复使用以前的搜索结果，在计算最佳解决方案时经常可以大大加快重复性计划D*(AD*)随时A*。所有任务都是ComputePathWithReuse函数、动态环境中的自动真、ATRV自动机、Segbot自动机、2D地图、3D地图、计划、计划是AI的关键部分路径计划：问题、机器人对世界的认识、基于高维搜索的计划、2D(x，y)计划54，000个状态计划快速执行速度、4D(x，y，V

2、)计划2000多万个状态计划慢执行速度、基于高维搜索的计划、6DOF机器人手臂3x109个状态计划由于以下原因，环境变化导航需要多次重新计划，如果有人在附近自动行驶，如果其他车辆在道路环境模型的不准确位置估计错误，则必须迅速重新计划！ 随时以D*(即随时以动态A*)计划4D，实际计划，随时以D*(即随时以动态A*)计划3D停车，随时以D*(即随时以动态A*)计划4D，实际计划，随时以算法可以满足时间约束。重新计划算法(例如，A*增量版本，即D*和D*缩减版本重新使用之前的计划)适用于动态和(或)某些已知环境。随时重新计划算法。例如，在任何时候增加A*的优点是D*在任何时候组合这两者。搜索最小成

3、本路径，计算相关类型的g值g(s):评估从sstart到s最小成本路径的成本。满足最佳值：g (s)=mins pred (s) (g (s) c (s)，s)，检索S3到sgoal的值c(s3，sgoal)，最小成本路径评估从s到s的最短路径值(low)，搜索a *，计算相关状态的最佳g值主函数：g(sstart)=0； 所有其他g值都是无限的。OPEN=sstart；computer path()；给出结果。ComputePath函数：while (sgoal未扩展)是OPEN中f(s)(=g(s) h(s)最小的s；扩展s；注：OPEN是扩展候选人类型的集。如果启发方法是一致的，则每个扩

4、展状态的g(s)是最佳的。A*搜索，计算相关状态的最佳g值ComputePath函数：while (sgoal未扩展)OPEN中f(s)(=g(s) h(s)最小的s；关闭s；请插入；s的每个后续状态s if g (s) g (s，s) g (s)=g (s) c (s，s)；s OPEN；插入到；注意：CLOSED是展开状态集。在If正文中，对g(s)重新赋值是为了将g(s)降低到sstart找到s的路径。，A*搜索：例如，计算相关状态的最佳g值ComputePath函数：while (sgoal未扩展)OPEN中的f(s)(=g(s) h(s)最小的s；关闭s；请插入；s的每个后续状态s

5、if g (s) g (s，s) g (s)=g (s) c (s，s)；s OPEN；插入到；CLOSED=OPEN=sstart以下扩展状态：sstart，g (S2) g (sstart，S2)，a *搜索：是，计算相关状态的最佳g值ComputePath关闭s；请插入；s的每个后续状态s if g (s) g (s，s) g (s)=g (s) c (s，s)；s OPEN；插入到；CLOSED=sstart OPEN=s2以下扩展状态：s2，A*搜索：是，计算相关状态的最佳g值ComputePath函数：while (sgoal未扩展)OPEN到f(s)关闭s；请插入；s的每个后续状

6、态s if g (s) g (s，s) g (s)=g (s) c (s，s)；s OPEN；插入到；CLOSED=sstart，s2 OPEN=s1，s4下一个扩展状态：s1，A*搜索：是，计算相关状态的最佳g值ComputePath函数：while (sgoal未扩展)关闭s；请插入；s的每个后续状态s if g (s) g (s，s) g (s)=g (s) c (s，s)；s OPEN；插入到；closed=sstart，S2，S1 OPEN=S4，s goal以下扩展状态：S4，A*搜索：是，计算相关状态的最佳g值ComputePath函数：while (sgoal关闭s；请插入；s

7、的每个后续状态s if g (s) g (s，s) g (s)=g (s) c (s，s)；s OPEN；插入到；closed=sstart，S2，S1，s4OPEN=s goal，S3以下扩展状态：s goal，A*搜索：是，计算相关状态的最佳g值ComputePath函数：while关闭s；请插入；s的每个后续状态s if g (s) g (s，s) g (s)=g (s) c (s，s)；s OPEN；插入到；closed=sstart，S2，S1，S4，s goal OPEN=S3 exit，A*搜索：是，计算相关状态的最佳g值ComputePath函数：while (sgoal关闭s

8、；请插入；s的每个后续状态s if g (s) g (s，s) g (s)=g (s) c (s，s)；s OPEN；插入到；g(s)最适合每个扩展状态。对于其他每个状态，g(s)为上限。现在可以计算最小成本路径。f(s)=g(s) h(s)(1)展开状态的权重A*。yayu:cost(解决方案)cost(最佳解决方案)。解决很多问题的速度比A*快得多。A*的最佳特性，f(s)=g(s) h(s)按顺序扩展状态。C*为最佳路径值，搜索A*:扩展f(s) C*的节点异常错误：h(s)=0，f(s)=g(s)搜索UCS，扩展当前状态的所有后续状态h(While 1，计划执行加权A*搜索的时间裴珉姬

9、：提供当前亚洲-优秀解决方案。降低；降低。=2.5 13扩展解决方案=移动11，=1.5 15扩展解决方案=移动11，=1.0 20扩展解决方案=移动10，随时构建搜索，执行一系列减少的加权A*搜索：=2.5 13扩展解决方案=移动11，=必须重复使用上次搜索的结果。ARA*:有效地随时搜索，执行一系列减少的权重A*搜索。修改每个加权A*搜索以重复使用上次搜索的结果。继续保证阿留申。重用权重A*搜索，所有初始值无限；ComputePath函数：while (sgoal未扩展)是OPEN中f(s)(=g(s) h(s)最小的s；关闭s；请插入；(s)=g(s)；s的每个后续状态s if g (s

10、) g (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)(即不一致)，权重A*搜索重用，以所有不匹配状态打开；开始；开始。ComputePathWithReuse函数：while (sgoal未展开)f(s)(=g(s) h(s)最小的s；关闭s；请插入；(s)=g(s)；s的每个后续状态s if g (s) g (s，s) g (s)=g (s) c (s，s)；s OPEN；插入到；注意：值是处于正在扩展状态的值。G (s)=mins

11、pred (s) (v (s) c (s)，s)open:一个(s)g(s)(即不一致)初始化OPEN时使用上次搜索结果。例如多路复用A*(=1)，CLOSED=OPEN=s4，sgoal以下扩展状态：s4，g (s)=mins pred (s) (v (s)例如，多路复用A*(=1)，CLOSED=s4 OPEN=sgoal，s3以下扩展状态：sgoal，例如，多路复用A*(=1)，CLOSED=s4，CLOSEDComputePath结束后，所有状态的g值与最终A*的g值相同。返回实例，然后执行一系列减少的权重A*搜索。=2.5 13扩展，解决方案=移动11，=1.5扩展，解决方案=移动1

12、1次，=1.0扩展20次，解决方案=移动10次，ARA*:运行一系列减少的ComputePathWithReuse函数降低边的成本后，可以使用与上述相同的ComputePathWithReuse函数重新计算路径。边的成本增加时，可以使用类似的函数计算。最佳再规划器：D*和D*精简版，设置为1；运行直到达到目标：computepathwithrepuse()；目前公布亚洲解决方案路径，沿该路径移动，直到检测到某地图上没有的物体；相应的边缘更新成本；将Sgoal设置为真实的当前状态；参考资料：S. Koenig and m. likhachov，fast re planning for navig

13、ation in unknown terrain，IEEE trans.robotics，21，(运行直到达到目标：computepathwithrepuse()；目前公布亚洲解决方案路径，沿该路径移动，直到检测到某地图上没有的物体；相应的边缘更新成本；将Sgoal设置为真实的当前状态；注意：搜索是反向进行的。sstart=true的目标，sgoal=true的当前状态，所有边都被反转。这样，在名为ComputePathWithReuse的两次之间，sstart始终保持不变，g值也很可能保持不变。D*和D* lite:是，初始知识和初始目标距离，自动机移动后的知识和目标距离，灰色区域的g值更改，D*和D* lite:是，初始A*搜索，初始D* lite搜索，第二次A运行直到到达目标：computepathwithrepuse()；目前公布亚洲解决方案路径，沿该路径移动，直到检测到某地图上没有的物体；相应的边缘更新成本；将Sgoal设置为真实的当前状态；观察重要的变化增加或重新计划