面向路径规划的改进图注意力强化学习算法
Improved Graph Attention Reinforcement Learning Algorithm for Path Planning
DOI: 10.12677/aam.2026.1511445, PDF,   
作者: 苏继满, 刘志刚:南通科技职业学院能源交通学院,江苏 南通;焦玉全:南通科技职业学院智能制造学院,江苏 南通
关键词: 路径规划;深度强化学习;几何边编码;门控残差块;课程式近端策略优化;Path Planning; Deep Reinforcement Learning; Geometric Edge Encoding; Gated Residual Block; Curriculum Proximal Policy Optimization
摘要: 节点遍历类路径规划广泛存在于智能制造、物流配送与交通运维等场景,需在约束下确定总通行代价最小的节点访问次序,属NP难组合优化问题。针对现有深度强化学习方法在几何特征刻画、拓扑感知与训练稳定性方面的不足,本文提出距离感知图注意力策略网络(DGAPN):以几何边编码将通行代价显式注入注意力,用门控残差块抑制深层图网络的特征趋同,经双路池化与门控读出形成全局图嵌入,并采用课程式近端策略优化将训练分为探索与精修两段,配合自适应优势与策略平滑。以旅行商问题(TSP)为载体的测试表明,DGAPN在路径长度、跨规模与跨分布泛化及推理效率上均优于多数同类方法,可作为此类路径规划问题的通用框架。
Abstract: Node-traversal path planning, common in intelligent manufacturing, logistics delivery and traffic operation and maintenance, seeks the minimum-cost node order under constraints, an NP-hard combinatorial optimization problem. To address weaknesses of deep reinforcement learning (DRL) in geometric depiction, topology perception and stability, this paper proposes a Distance-aware Graph Attention Policy Network (DGAPN). Geometric edge encoding injects travel cost into attention, a gated residual block avoids feature homogenization in deep graph networks, dual-branch pooling with gated readout yields a global graph embedding, and a curriculum proximal policy optimization splits training into two stages of exploration and refinement, with adaptive advantage and policy smoothing. Tests on the traveling salesman problem (TSP) show that DGAPN beats most DRL baselines in tour length and in cross-scale and cross-distribution generalization and inference efficiency, providing a general framework for such path planning problems.
文章引用:苏继满, 刘志刚, 焦玉全. 面向路径规划的改进图注意力强化学习算法[J]. 应用数学进展, 2026, 15(11): 223-235. https://doi.org/10.12677/aam.2026.1511445

参考文献

[1] Wang, Q., Lai, K.H. and Tang, C. (2023) Solving Combinatorial Optimization Problems over Graphs with BERT-Based Deep Reinforcement Learning. Information Sciences, 619, 930-946.
https://doi.org/10.1016/j.ins.2022.11.073
[2] 孔松涛, 刘池池, 史勇, 等. 深度强化学习在智能制造中的应用展望综述[J]. 计算机工程与应用, 2021, 57(2): 49-59.
[3] Applegate, D., Bixby, R., Chvatal, V., et al. (2006) The Traveling Salesman Problem: A Computational Study. Princeton University Press.
[4] Shi, X.H., Liang, Y.C., Lee, H.P., Lu, C. and Wang, Q.X. (2007) Particle Swarm Optimization-Based Algorithms for TSP and Generalized TSP. Information Processing Letters, 103, 169-176.
https://doi.org/10.1016/j.ipl.2007.03.010
[5] Vinyals, O., Fortunato, M. and Jaitly, N. (2015) Pointer Networks.
https://arxiv.org/abs/1506.03134
[6] Bello, I., Pham, H., Le, Q.V., et al. (2016) Neural Combinatorial Optimization with Reinforcement Learning.
https://arxiv.org/abs/1611.09940
[7] Kool, W., van Hoof, H. and Welling, M. (2018) Attention, Learn to Solve Routing Problems!
https://arxiv.org/abs/1803.08475
[8] Kwon, Y.D., Choo, J., Kim, B., et al. (2020) POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. Advances in Neural Information Processing Systems 33, Online, 6-12 December 2020, 21188-21198.
[9] Dai, H., Khalil, E.B., Zhang, Y., et al. (2017) Learning Combinatorial Optimization Algorithms over Graphs.
https://arxiv.org/abs/1704.01665
[10] Joshi, C.K., Laurent, T. and Bresson, X. (2019) An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem.
https://arxiv.org/abs/1906.01227
[11] Pan, X., Jin, Y., Ding, Y., Feng, M., Zhao, L., Song, L., et al. (2023) H-TSP: Hierarchically Solving the Large-Scale Traveling Salesman Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 37, 9345-9353.
https://doi.org/10.1609/aaai.v37i8.26120
[12] Fountoulakis, K., Levi, A., Yang, S., et al. (2022) Graph Attention Retrospective.
https://arxiv.org/abs/2202.13060
[13] Fellek, G., Farid, A., Fujimura, S., Yoshie, O. and Gebreyesus, G. (2024) G-DGANet: Gated Deep Graph Attention Network with Reinforcement Learning for Solving Traveling Salesman Problem. Neurocomputing, 579, Article 127392.
https://doi.org/10.1016/j.neucom.2024.127392