Abstract

In this paper, we explore the multifaceted capabilities of route-finding algorithms and their role in delivering dynamic paths for diverse navigation scenarios. In off-road route finding, the shortest path is not always the best; the route's smoothness must also be considered. Present methodologies like A* have notable limitations, such as difficulty adapting to complex terrains and producing rugged routes. This limitation hampers performance in critical scenarios, such as in emergencies like landslides or earthquakes, where off-road exploration is crucial. This paper proposes 3 methodologies that have been fine-tuned with optimal hyperparameters for optimal results using gradient descent. Two of these methodologies, Simulated Annealing and Ant Colony Optimization, overcome some limitations of A* but not all. However, Q-Learning significantly overcomes the limitations and saves travel time by providing a route with 70% fewer undulations and a 16% reduction in route length compared to A*. Compared to other implementations, the Q-Learning implementation proposed in this research not only focuses on minimizing path length but also minimizes route undulations, providing a dual objective approach that is well suited to real-world scenarios. Unlike prior implementations, which focus on a single objective, such as path length or obstacle avoidance, this work leverages a reward function that penalizes elevation variance while rewarding shorter routes, resulting in smoother, more easily traversable paths. Thus, Q-Learning overcomes the cons of the present methodologies and can form synergistic combinations, enhancing the overall performance of off-road space searching systems and accommodating the various challenges and complexities inherent in the targeted applications. The dataset used includes features such as latitude, longitude, and elevation. The strategic application of heuristics enables the swift evaluation of multiple paths, facilitating the selection of optimal routes in real-time applications. By combining various heuristics, the development of off-road path identification systems capable of discerning optimal paths across varied terrains becomes feasible.

Keywords

The Simulated Annealing Algorithm, A* Method, Ant Colony Algorithm, Q-learning, Path finding, Off-road routing,

Downloads

Download data is not yet available.

References

  1. X. Liang, Y. Mu, B. Wu, Y. Jiang, A review of related algorithms for path planning. Value Engineering, 39(03), (2020) 295–299.
  2. J.C. Yang, S.X. Li, Z.Y. Cai, Research and development of path planning algorithm. Control Engineering, 24(07), (2017) 1473–1480.
  3. M. Korkmaz, A. Durdu, (2018) Comparison of optimal path planning algorithms. In 2018 14th international conference on advanced trends in radioelecrtronics, telecommunications and computer engineering (TCSET), IEEE, Ukraine, https://doi.org/10.1109/TCSET.2018.8336197
  4. A.J. Dalton, (2008) Autonomous Vehicle Path Planning with Remote Sensing Data. Virginia Tech.
  5. B. Wang, S. Li, J. Guo, Q. Chen, Car-like mobile robot path planning in rough terrain using multi-objective particle swarm optimization algorithm, Neurocomputing, 282, (2018) 42–51. https://doi.org/10.1016/j.neucom.2017.12.015
  6. X. Zhou, Q. Xie, M. Guo, J. Zhao, J. Wang, Accurate and efficient indoor pathfinding based on building information modeling data, IEEE Transactions on Industrial Informatics, IEEE, 16(12), (2020) 7459–7468. https://doi.org/10.1109/TII.2020.2974252
  7. Y. Ma, S. Liu, B. Sima, B. Wen, S. Peng, Y. Jia, A precise visual localisation method for the Chinese Chang’e-4 Yutu-2 rover. The Photogrammetric Record, 35(169), (2020) 10–39. https://doi.org/10.1111/phor.12309
  8. H.B. Duan, (2005). Ant colony algorithms: theory and applications. Chinese Science.
  9. E. Shi, M. Chen, J. Li, Y. Huang, Research on method of global path-planning for mobile robot based on ant-colony algorithm. Transactions of the Chinese society for agricultural machinery, 45(6), (2014) 53-57.
  10. C. Zheng, H. Yin, J. Li, M. Lu, Multi objective evolutionary algorithm for shortest path with maximal visual coverage, In 2011 International Conference on Intelligent Computation and Bio-Medical Instrumentation IEEE, 232-235.
  11. J. Leng, X. Yu, (2023) Research on personalized travel route recommendation AI algorithm based on simulated annealing, IEEE 3rd International conference on electronic communications, Internet of Things and Big Data (ICEIB), IEEE, Taiwan. https://doi.org/10.1109/ICEIB57887.2023.10169965
  12. A. Panov, K. Yakovlev, R. Suvorov, Grid path planning with deep reinforcement learning: Preliminary results, Procedia Computer Science, 123, (2018) 347–353, https://doi.org/10.1016/j.procs.2018.01.054
  13. H.D. Pham, S.M. Narasimhamurthy, B. Mehran, E. Manley, A. Ashraf, "Reinforcement learning based estimation of shortest paths in dynamically changing transportation networks, Frontiers in Future Transportation, 6, (2025) 1524232. https://doi.org/10.3389/ffutr.2025.1524232
  14. Z. Hong, P. Sun, X. Tong, H. Pan, R. Zhou, Y. Zhang, Y. Han, J. Wang, S. Yang, L. Xu, Improved A-star algorithm for long-distance off-road path planning using terrain data map. ISPRS International Journal of Geo-Information, 10(11), (2021) 785. https://doi.org/10.3390/ijgi10110785
  15. P. Upadhyay, V. Marriboina, S.J. Goyal, S. Kumar, E.S.M. El-Kenawy, A. Ibrahim, A.A. Alhussan, D.S. Khafaga. An improved deep reinforcement learning routing technique for collision-free VANET, Scientific Reports, 13(1), (2023) 21796. https://doi.org/10.1038/s41598-023-48956-y
  16. W. Alhoula, J. Hartley, (2014) Static and time-dependent shortest path through an urban environment: Time-Dependent Shortest Path, in Science and Information Conference (SAI), IEEE, London, UK. https://doi.org/10.1109/SAI.2014.6918315
  17. Z. Sun, (2022) Applying reinforcement learning for shortest path problem International Conference on Big Data, Information and Computer Network (BDICN), IEEE, China https://doi.org/10.1109/BDICN55575.2022.00100
  18. D. Shah, A. Bhorkar, H. Leen, I. Kostrikov, N. Rhinehart, S. Levine. (2022) Offline reinforcement learning for visual navigation. arXiv preprint arXiv:2212.08244. https://doi.org/10.48550/arXiv.2212.08244
  19. S. Huang, X. Wu, G. Huang. (2023) Deep reinforcement learning-based multi-objective path planning on the off-road terrain environment for ground vehicles. arXiv preprint https://doi.org/10.48550/arXiv.2305.13783
  20. Y. Hu, L. Yang, Y. Lou, Path planning with Q-learning. Journal of Physics: Conference Series, 1948, (2021) 012038.
  21. B. Jang, M. Kim, G. Harerimana, J. Kim, Q-learning algorithms: A comprehensive classification and applications, IEEE Access, 7, (2019) 133653–133670. https://doi.org/10.1109/ACCESS.2019.2941229
  22. A.P. Mohamed, B. Lee, Y. Zhang, M. Hollingsworth, C.R. Anderson, J.V. Krogmeier, D.J. Love. (2024) Simulation-Enhanced Data Augmentation for Machine Learning Pathloss Prediction. In ICC 2024-IEEE International Conference on Communications, IEEE, USA. https://doi.org/10.1109/ICC51166.2024.10622237
  23. S. Wuqiang, S. Guiquan, C. Lei, Z. Jijun, (2023) Data Preprocessing Optimization Algorithm Based on Improved Particle Swarm Optimization. In International Conference on Networking, Informatics and Computing (ICNETIC), IEEE, Palermo, Italy, https://doi.org/10.1109/ICNETIC59568.2023.00152
  24. M. Dorigo, M. Birattari, T. Stützle, Ant colony optimization. IEEE computational intelligence magazine, IEEE, 1(4), (2006) 28-39. https://doi.org/10.1109/MCI.2006.329691
  25. P. Liashchynskyi, P. Liashchynskyi, (2019) Grid search, random search, genetic algorithm: A big comparison for NAS. arXiv preprint. https://arxiv.org/pdf/1912.06059