一种新型的动态最优路径算法研究  

Research on an Efficient Algorithm about Dynamic Optimal Paths

作　　者：汪芳[1] 戴冠中[2] 慕德俊[2] 

机构地区：[1]西北工业大学计算机学院,西安710072 [2]西北工业大学自动化学院,西安710072

出　　处：《机械科学与技术》2012年第11期1885-1887,1892,共4页Mechanical Science and Technology for Aerospace Engineering

基　　金：国家科技重大专项课题项目(2008ZX03006);国家"863"高科技研究发展计划项目(2003AA142060)资助

摘　　要：目前,推移最优路径问题的讨论范围已经逐渐从静态图形转移到动态图形之上,而到现在为止能够有效的应用于动态最优路径的算法却非常少。本文中提出了一种高效的用于动态最优路径的算法—IAPLA算法,通过使用线性强化学习方案和新的更新算法,有效地减少了动态全局最优路径中不必要的更新操作,从而提高算法的收敛速度。该算法还利用阈值的思想,提出了一种可以控制最优路径精确程度的方法。实验结果表明:该算法在图形多次变化的环境下能大幅提高运算效率。The scope of the optimal path problem has gradually shift from static to dynamic graphics over time, but up to now those algorithms that can be effectively applied to the dynamic optimal path is scarce. This paper presen- ted an efficient algorithm for dynamic optimal path-IAPLA algorithm, effectively reduced the unnecessary updates and improved the convergence speed, by using the linear reinforcement learning scheme and a new update algo- rithm. The algorithm also used the threshold idea, propossing a control method of optimal path accuracy. Compa- ring IAPLA algorithm with Floyd algorithm through simulation experiments, the experimental results show there is a significant improvement in efficiency in some circumstances.

关 键 词：强化学习 动态最优路径 阈值 

分 类 号：TP30[自动化与计算机技术—计算机系统结构]