Evaluation and Comparison of Deterministic Search and Reinforcement Learning Algorithms for Routing in Network and Urban Environments

Shafieenejad, Iman; Shokri, Faezeh

doi:10.22034/jtae.2026.10.3.8

Evaluation and Comparison of Deterministic Search and Reinforcement Learning Algorithms for Routing in Network and Urban Environments

Document Type : Research Article

Authors

Iman Shafieenejad

Faezeh Shokri

Aerospace Research Institute, Ministry of Science, Research and Technology, Tehran, Iran

10.22034/jtae.2026.10.3.8

Abstract

This study presents a comprehensive comparative evaluation of three routing algorithms in static network environments with complex obstacles. The algorithms include A* as a deterministic heuristic search method, Q-learning as a classical reinforcement learning approach, and Double Q-learning as an improved version designed specifically to reduce overestimation bias. Experiments were conducted in two distinct environments: a simple 25×25 grid network and a complex 40×40 urban environment. Algorithm performance was systematically assessed using multi-dimensional criteria including path length, execution time, success rate, path smoothness measured by number of turns, and learning stability across multiple episodes. To ensure statistical reliability of the results, each algorithm underwent 30 repeated independent runs with advanced statistical analyses including 95% confidence intervals, paired t-tests, and ANOVA to validate significance of observed differences. Findings revealed that A* consistently outperformed other algorithms across all quantitative metrics, generating optimal and smoothest paths with average length of 42 steps, minimal execution time of 0.0043 seconds, and only 7 turns. Although both reinforcement learning algorithms achieved 100% success rates in all experimental conditions, they required substantially longer execution times and produced lower-quality paths with considerably more turns (19 and 20 turns respectively). In the complex urban environment, performance disparities intensified significantly, with Double Q-learning optimality dropping from 91.3% to 90%. The results showed that reinforcement learning-based algorithms are better suited to unknown, dynamic, and uncertain environments due to their adaptive capabilities, whereas the A* algorithm achieves superior performance in static and well-defined environments.

Keywords

Optimal Routing

A* Algorithm

Q-Learning

Double Q-Learning

Statistical Analysis

Subjects

Flight mechanics/Navigation/Control/...

[1] C. J. C. H. Watkins, "Learning from delayed rewards," 1989.

[2] C. J. Watkins and P. Dayan, "Q-learning," Machine Learning, vol. 8, no. 3, pp. 279–292, 1992, https://doi.org/10.1007/BF00992698.

[3] A. H. Borzabadi, A. V. Kamyad, M. H. Farahi, and H. H. Mehne, "Solving some optimal path planning problems using an approach based on measure theory," Applied Mathematics and Computation, vol. 170, no. 2, pp. 1418–1435, 2005, https://doi.org/10.1016/j.amc.2005.01.035.

[4] B. Q. A. Nguyen, N. T. Dang, T. T. Le, and P. N. Dao, "On-policy and Off-policy Q-learning algorithms with policy iteration for two-wheeled inverted pendulum systems," Robotics and Autonomous Systems, 2025, Art. No. 105111, https://doi.org/10.1016/j.robot.2025.105111.

[5] R. Wu, E. Luo, X. Li, H. Tang, and Y. Li, "Hybrid artificial bee colony algorithm with Q-learning for distributed heterogeneous flexible job shop scheduling problem considering machine preventive maintenance," Swarm and Evolutionary Computation, vol. 98, 2025, Art. no. 102134, https://doi.org/10.1016/j.swevo.2025.102134.

[6] X. Guo, Q.-K. Pan, W. Zhang, Z.-H. Miao, X.-L. Jing, and H.-Y. Sang, "A Q-learning-assisted memetic algorithm for joint vehicle scheduling problem for harvesting and transportation in smart agriculture," Swarm and Evolutionary Computation, vol. 96, 2025, Art. no. 102007, https://doi.org/10.1016/j.swevo.2025.102007.

[7] C. Sun, L. Hou, S. Yu, and J. Shu, "HQA: Hybrid Q-learning and AODV multi-path routing algorithm for flying Ad-Hoc networks," Vehicular Communications, 2025, Art. no. 100947, https://doi.org/10.1016/j.vehcom.2025.100947.

[8] X. H. Qiu, S. J. Tian, A.-F. Liu, Y.-H. Wei, H. Sekiya, and Y.-J. Choi, "Q-learning-based hyper-heuristic algorithm for priority and precedence dual-driven task assignment in spatial crowdsourcing," Expert Systems with Applications, vol. 297, 2026, Art. no. 129327, https://doi.org/10.1016/j.eswa.2025.129327.

[9] Z. Duan, Y. Zhang, Z. Shao, Z. Xu, and Z. Xiang, "Advanced robot path planning on rough terrain: A Q-learning-based multi-objective PSO algorithm," Applied Soft Computing, 2025, Art. no. 113798, https://doi.org/10.1016/j.asoc.2025.113798.

[10] J. Guo, B. Peng, B. Du, K. Wang, and Y. Li, "Q-learning-based multi-objective spotted hyena algorithm for flexible open shop scheduling problem with consideration of preventive maintenance and travel/setup times," Journal of Manufacturing Systems, vol. 82, pp. 224–238, 2025, https://doi.org/10.1016/j.jmsy.2025.06.001.

[11] Z. Q. Zhang, X. Y. Wu, B. Qian, R. Hu, and J. B. Yang, "A Q-learning-based multi-objective hyper-heuristic algorithm for energy-efficient integrated distributed hybrid flow-shop scheduling with preventive maintenance," Computers & Operations Research, 2025, Art. no. 107267, https://doi.org/10.1016/j.cor.2025.107267.

[12] L. Xu, T. Zhou, K. Li, J. Chen, and H. Zhang, "Q-learning-driven multi-population cooperative evolutionary algorithm with local search for scheduling of network-shared manufacturing resources," Computers & Operations Research, vol. 180, 2025, Art. no. 107076, https://doi.org/10.1016/j.cor.2025.107076.

[13] G. Zuo, Z. Jia, Z. Wu, J. Shi, and G. Wang, "A Q-learning guided dual population genetic algorithm for distributed permutation flow shop scheduling problem with machine having fuzzy processing efficiency," Expert Systems with Applications, 2025, Art. no. 127882, https://doi.org/10.1016/j.eswa.2025.127882.

[14] F. B. Ozsoydan, "A trajectory-based algorithm enhanced by Q-learning and cloud integration for hybrid flexible flowshop scheduling problem with sequence-dependent setup times: A case study," Computers & Operations Research, vol. 181, 2025, Art. no. 107079, https://doi.org/10.1016/j.cor.2025.107079.

[15] H. Dinçer et al., "Q-learning algorithm and molecular fuzzy multi-objective particle swarm optimization-based decision-making approach to circular economy-oriented investment alternatives for renewable energy technologies," Information Sciences, vol. 718, 2025, Art. no. 122378, https://doi.org/10.1016/j.ins.2025.122378.

[16] Z. Zhaohui, Z. Jiaqi, and L. Jing, "Q-learning-based semi-fixed clustering routing algorithm in WSNs," Ad Hoc Networks, vol. 174, 2025, Art. no. 103837, , https://doi.org/10.1016/j.adhoc.2025.103837.

[17] Z. Li, Y. Wang, Y. Han, K. Gao, and J. Li, "Q-Learning-Driven Accelerated Iterated Greedy Algorithm for Multi-Scenario Group Scheduling in Distributed Blocking Flowshops," Knowledge-Based Systems, vol. 317, 2025, Art. no. 113424, https://doi.org/10.1016/j.knosys.2025.113424.

[18] H. Xuan, Q.-Q. Zheng, L. Lv, and B. Li, "Q-learning based estimation of distribution algorithm for scheduling distributed heterogeneous flexible flow-shop with mixed buffering limitation," Engineering Applications of Artificial Intelligence, vol. 149, 2025, Art. no. 110537, https://doi.org/10.1016/j.engappai.2025.110537.

[19] K. Wang, X. Ma, Y. Li, Y. Luo, Y. Li, and L. Gao, "An adaptive genetic algorithm based on Q-learning for energy-efficient e-waste disassembly line balancing and rebalancing considering task failures," Journal of Manufacturing Systems, vol. 80, pp. 1–19, 2025, https://doi.org/10.1016/j.jmsy.2025.02.009.

[20] G. Wang, Z. Zhang, and A. Nazarova, "A digital twin-based platform for testing and optimization of path planning algorithms," Simulation Modelling Practice and Theory, 2025, Art. no. 103206, 2025, https://doi.org/10.1016/j.simpat.2025.103206.

[21] S. Zeng, Y. Wang, X. Yu, H. Song, X. Guo, and Z. Li, "A dyeing clustering algorithm based on ant colony path-finding mechanism," Engineering Applications of Artificial Intelligence, vol. 136, 2024, Art. no. 108941, https://doi.org/10.1016/j.engappai.2024.108941.

[22] A. Giuffrida, N. Basilico, and F. Amigoni, "An empirical evaluation of learning-based multi-agent path finding algorithms in warehouse environments," Robotics and Autonomous Systems, vol. 194, 2025, Art. no. 105149, https://doi.org/10.1016/j.robot.2025.105149.

[23] Q. Zhou, Y. Lian, J. Wu, M. Zhu, H. Wang, and J. Cao, "An optimized Q-Learning algorithm for mobile robot local path planning," Knowledge-Based Systems, vol. 286, 2024, Art. no. 111400, https://doi.org/10.1016/j.knosys.2024.111400.

[24] J. Gao, Y. Li, X. Shi, and K. Yan, "Customer satisfaction optimization in due-aware multi-agent path finding," Information Sciences, 2025, Art. no. 122782, https://doi.org/10.1016/j.ins.2025.122782.

[25] S. Venu and M. Gurusamy, "A Comprehensive Review of Path Planning Algorithms for Autonomous Navigation," Results in Engineering, 2025, Art. no. 107750, https://doi.org/10.1016/j.rineng.2025.107750.

[26] S. Aslan and S. Demirci, "An immune plasma algorithm with Q-learning based pandemic management for path planning of unmanned aerial vehicles," Egyptian Informatics Journal, vol. 26, 2024, Art. no. 100468, https://doi.org/10.1016/j.eij.2024.10046.

[27] Y. Wang and G. Wang, "An adaptive and efficient path planning algorithm for UAV navigation in complex environments," Computers & Operations Research, vol. 185, 2026, Art. no. 107296, https://doi.org/10.1016/j.cor.2025.107296.

[28] X. Ni, W. Hu, Q. Fan, Y. Cui, and C. Qi, "A Q-learning based multi-strategy integrated artificial bee colony algorithm with application in unmanned vehicle path planning," Expert Systems with Applications, vol. 236, 2024, Art. no.121303, https://doi.org/10.1016/j.eswa.2023.121303.

[29] J. Wu, H. Jin, S. Cai, and L. Liu, "A delay tolerant network routing algorithm based on multi-step double Q-learning," IET Communications, vol. 17, no. 11, pp. 1321–1333, 2023, https://doi.org/10.1049/cmu2.12626.

[30] M. S. El, "Intelligent routing agent based on Q-learning and Markov decision processes for routing optimization in DTN networks," International Journal of Intelligent Networks, vol. 6, pp. 97–112, 2025, https://doi.org/10.1016/j.ijin.2025.07.001.

[31] N. Manogaran et al., "Developing a Novel Adaptive Double Deep Q-Learning-Based Routing Strategy for IoT-Based Wireless Sensor Network with Federated Learning," Sensors, vol. 25, no. 10, 2025, Art. no. 3084, https://doi.org/10.3390/s25103084.

[32] J. Liu et al., "QMR:Q-learning based Multi-objective optimization Routing protocol for Flying Ad Hoc Networks," Computer Communications, vol. 150, pp. 304–316, 2020, https://doi.org/10.1016/j.comcom.2019.11.011.

[33] M. Ghanifar, A. Nikkhah, M. Kamzan, M. Teshnehlab, and M. Tayefi, "Online trajectory regeneration for multirotors via a proportional-derivative physics-informed neural network," IEEE Access, vol. 13, pp. 145168 - 145190, 2025, https://doi.org/10.1109/ACCESS.2025.3598862.

[34] M. Ghanifar, M. Omidali, A. Nikkhah, M. Teshnehlab, and M. Tayefi, "Fuzzy PID-inspired Potential Field Path Planning for Quadrotors in Environmental Monitoring," Journal of Technology in Aerospace Engineering, vol. 37, Special Issue, pp. 1–12, 2025, https://doi.org/10.22034/jtae.2026.1400.

[35] J. Gandhi and Z. Narmawala, "Q-Learning and Double Q-Learning Based Routing in Opportunistic Networks," International Journal of Networked and Distributed Computing, vol. 14, 2026, Art. no. 13, https://doi.org/10.1007/s44227-026-00090-7.

[36] J. Singh, S. K. Dhurandher, I. Woungang, and L. Barolli, "Double Q-learning based routing protocol for opportunistic networks," Journal of High Speed Networks, vol. 29, no. 1, pp. 1–14, 2023, https://doi.org/10.3233/JHS-22201.

[37] J. Zhou, X. Gong, L. Sun, Y. Xie, and X. Yan, "Adaptive Routing Strategy Based on Improved Double Q-Learning for Satellite Internet of Things," Security and Communication Networks, vol. 2021, no. 1, 2021, Art. no. 5530023, https://doi.org/10.1155/2021/5530023.

[38] M. Patil, P. Tambolkar, and S. Midlam-Mohler, "Optimizing Traffic Routes With Enhanced Double Q-Learning," IET Intelligent Transport Systems, vol. 19, no. 1, 2025, Art. no. e70002, https://doi.org/10.1049/itr2.70002.

[39] I. Shafieenejad, "Design of swarm guidance for aerial spherical robots with social intelligence inspired by grasshopper' optimal motion and fuzzy logic," Aerospace Knowledge and Technology, vol. 14, no. 1, pp. 193–216, 2025, (in Persian), 20.1001.1.23221070.1404.14.1.11.4.

[40] I. Shafieenejad, "Designing optimal Robust Guidance and Model Predictive controller for Mono-Wing Aerial Robot by the Maple Seed Tree Inspired," Journal of Aeronautical Engineering, vol. 27, no. 1, pp. 56–74, 2025, (in Persian), https:doi.org/10.22034/joae.2025.481623.1251.

[41] S. J. Russell, S. Russell, and P. Norvig, Artificial Intelligence: A Modern Approach. Pearson, 2020.