裁剪优化的anytime算法

《裁剪优化的anytime算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第!"卷第#期杭州电子科技大学学报$%&’!"，(%’##")"年"*月+%,-./&%01/.234%,56/.367.689-:6;<=>-’#")"裁剪优化的=.<;6?9算法孙俊，戴国骏，张怀相（杭州电子科技大学计算机应用技术研究所，浙江杭州!)"")@）摘要：解决路径规划问题时，传统的=.<;6?9算法有时候会遇到花费过多存储空间和计算时间的问题。该文提出的裁剪优化的=.<;6?9算法旨在提高这两方面的性能。该算法在已有的=.<;6?9算法的基础上，通过裁剪非均衡表中的节点来降低存储空间，然后通过分析裁剪后的节点信息来判断是否进入下次循环

2、，以此减少计算时间。最后通过仿真试验，验证了算法的可行性和有效性。关键词：移动机器人；路径规划；实时算法中图分类号：GH#*#文献标识码：=文章编号：)"")BA)*（C#")"）"#B""*)B"*"引言路径规划作为移动机器人和虚拟游戏的关键技术，多年来一直是国内外学者研究的热点。大多已有的经典算法如56IJ:;-/算法［)］，=!算法［#］等都能得出最优路径，然而却并不能保证在一定的时间内完成路径计算。而在现实世界的进行的路径规划经常碰到这样的情况：给予机器人一定量的时间，要求机器人在这个时间限制内得出可能的最好路径。实时算法中的=.<;6?9

3、算法就是一种符合这种有时间约束情况的路径规划算法。目前国内外学者已经研究出一系列的=.<;6?9算法，然而都各有缺点：K6&L9-M［!］是一个可行的算法，然而它不能评价每个次优路径相比于最优路径的:;96.和N,::9&&的=N7==算法次优率；OP=7=!算法［*］能够给出这个次优率，然而它对以前信息的重用率很低，以至于要浪费很多计算；=N=!算法［F］也存在着花费过多存储空间和计算时间的问题。本文提出的裁剪优化的=.<;6?9算法旨在解决上述问题。该算法的主题思想是：先在一个宽松的膨胀因子的限制下快速地找到一个可行的次优路径，然后进入循环，通

4、过不断降低膨胀因子来寻找更好的路径，直至时间结束。在每次进入循环之前，都要通过分析非均衡表中的节点情况来裁剪无用节点，只留下下次循环里可能有用的节点，以此来减少程序的存储空间。同时，还可以通过分析裁剪后剩下的节点来判断是否需要跳过下一循环。实验结果表明，该算法相对于=N=!算法取得了时间和空间上的性能提升。)算法的直觉来源=N=!算法是一种启发式的增量搜索算法，是一个比较优秀的=.<;6?9算法。=N=!算法的工作原理是通过多次执行伪=!算法来实现的：首先，=N=!算法的时候设置一个较大的膨胀因子9，然后每次执行（即产生一条路径）后就降低这个膨胀因

5、子9，直到9等于)为止。因此，=N=!算法能够保证在每次收稿日期：#""AB"AB)C基金项目：浙江省自然科学基金资助项目（D)"EE"C）作者简介：孙俊（)A@FB），男，浙江衢州人，在读研究生，移动机器人路径规划’H&杭州电子科技大学学报&I$I年搜索出一条路径后，这条路径的长度不大于最优路径的!倍。因此，"#"!算法既能够确定每个循环过程中产生的次优路径的次优率，也很好地重用了以前的计算信息。然而，通过仔细探索此算法的流程，仍能发现它的一些缺点，从而进行改进。如图$所示，这是"#"!算法在!%&’(时的情况（黑色的栅格代表障碍物，带“!”的栅

6、格代表此时次优路径的节点，灰色的栅格代表循环结束后加入非均衡表的节点，下同）。灰色的栅格，即非均衡表的节点有(个，然而经过分析发现，只有带“)”的&个栅格才有可能是最终所需要的节点。显然，其余的*个栅格完全可以从非均衡表中裁剪掉，从而可以减少存储空间。如图&所示，这是"#"!算法在!%*，!%&和!%$的*次循环中的情况。虽然在!%*的时候已经得到了最优路径，但是算法却完整地进行了*次循环才结束。通过观察可以发现，在!%*的循环结束时，由于非均衡表中的节点都不可能是最终需要的节点，因此可以判图$"#"!算法（!%&’(）断这个次优路径就是最优路径，

7、从而可以立即结束程序，以此来减少运行时间和计算。图&"#"!算法（*次循环）本文提出的算法就是通过分析每次循环后非均衡表的节点信息，裁剪其中不可能是最终需要的节点来克服以上缺点，提高"+,-./!算法的性能。&算法的过程描述&’$算法的定义解释（01）表示节点1到起点的路径代价，（21）表示节点1到终点的估计路径代价，（31，14）表示边的代价。5678表存放在本次循环中产生的非均衡节点，98:58;表存放在本次循环中已经扩展过的非均衡节点，它的作用是不在一次循环中两次扩展一个节点。由于5678表和98:58;表存储的都是非均衡节点，所以把它们统称

8、为非均衡表。!表示膨胀因子，!<=>?@A!计算的是带膨胀因子的路径代价。&’&算法的描述如下文中的算法伪代码所示，算法共