变权值加快收敛的路径寻优实时算法

基金项目:

教育部博士点基金项目 20010497002

Real-time algorithm of finding optimal path with changing weight to speed up convergence

1.
School of Transportation, Shandong University of Technology, Zibo 255012, China
2.
ITS Center, Wuhan University of Technology, Wuhan 430063, China

摘要: 为获得满意解为目标的最优路径选择问题, 给出了一种加权的LRTA^* (LearningReal Time A^*) 算法, 通过改变估价函数值更新规则与解时间和解质量的相对折中, 加快算法收敛速度。实例应用表明, 该方法比LRTA^*算法更快地收敛于满意解, 是一种求解大城市稠密路网两点间最优路径的有效方法。
- 智能交通 /
- 最优路径 /
- 启发式搜索算法 /
- 人工智能 /
- 值更新规则
Abstract: For obtaining a satisfactory shortest path, this paper proposed an improved LRTA^* to speed up search algorithm convergence through changing value-update rules. Through the trade-off of time and quality of solution, the convergence speed was fasted. Application result shows that the method converges suboptimal solution faster than LRTA^*, it is a better algorithm to solve the satisfactory solution between O-D for a big density route network.
- intelligent transport /
- optimal path /
- heuristic search algorithm /
- artificial intelligence /
- value-update rules

图 1 两种算法性能描述

Figure 1. Characteristic comparison

下载: 全尺寸图片幻灯片

表 1 两种算法获得问题解的历时比较

Table 1. Time comparison of two solutions

算法时间/s L_R/m L_S/m

加权LRTA^*算法 0.40 4820 5160

实时LRTA^*算法 0.98 4820 4820

下载: 导出CSV

[1]	Korf R E. Real-time heuristic search[J]. Artificial Intelligence, 1990, 42(2): 189-211. https://www.cnki.com.cn/Article/CJFDTOTAL-MSSB201903001.htm
[2]	Hamidzadeh B, Shekar S D. A real-time planning algorithm to meet response time constrains in dynamic environments[A]. In Proceedings of the IEEE International Conference on Tools for AI[C]. Boston: IEEE, Piscataway, NJ, USA, 1991.
[3]	Ishida T, Korf R E. Moving target search[A]. In Proceedings of the 12^th International Joint Conference on AI[C]. AAAI Menlo Park, USA, 1991.
[4]	Shida I T. Moving target search with intelligence[A]. In Proceedings of the 10^th National Conference on AI[C]. AAAI Menlo Park, USA, 1992.
[5]	Chimura F, Tokoro M. The trailblazer search: a new method for searching and capturing moving targets[A]. In Proceedings of the 12^th National Conference on AI[C]. AAAI Menlo Park, USA, 1994.
[6]	Hamidzadeh B. Shekar S. Deadline compliance, predictability and on-line optimization in real-time problem solving[A]. In Proceedingsof the International Joint Conference on AI[C]. AAAI Menlo Park, USA, 1995.
[7]	Ishida T, Shimbo M. Improving the learning efficiencies of realtime search[J]. IEEE Transportaiton on Software Engineering, 1996, 13(6): 305-310. https://www.cnki.com.cn/Article/CJFDTOTAL-XTYD202102006.htm
[8]	Shekar S, Hamidzadeh B. Evaluation of real-time search algorithms in dynamic environments[A]. In Proceeding of the IEEE International Conference on Tools for AI[C]. Boston: IEEE, Piscataway, NJ, USA, 1992.

点击查看大图

图(1) / 表(1)