REINFORCEMENT LEARNING MODEL FOR FINDING OPTIMAL PATH

Abstract

Reinforcement learning (RL) has become a powerful method for addressing complex optimization challenges, such as determining optimal (shortest) paths across various fields. This study aims to design and examine RL algorithms to identify the shortest path in expansive and dynamic environments. Our research advances RL algorithms for optimal pathfinding, showcasing Q-Learning's scalability, path length, and cumulative rewards superiority, enriching optimization methodologies, and guiding future RL explorations. We utilized a blend of Q-learning and Double Q-learning methods to improve our model's performance in conjunction with the Reward Shaping technique and exploration-exploitation tactics like epsilon-greedy with decaying epsilon. We evaluated our approach on a 27x27 matrix representing the environment. In both 17x17 and 27x27 environments, Q-Learning consistently showed optimal paths with shorter distances, while having a slightly slower performance than Dijkstra's algorithm, with completion times of (0.00093 seconds versus 0.000023 seconds and 0.0097 seconds versus 0.000034 seconds); nevertheless, our assessment encompassed Q-Learning, Dijkstra, and Random-selection algorithms. Q-Learning consistently showcased excellence, while random selection yielded suboptimal routes due to its inherent randomness. Cumulative rewards highlighted Q-Learning's superiority (ranging from 2,197,570.15 to 205,823.20), reflecting its adept learning capacity. Dijkstra prioritized minimal path length (cumulative rewards ranging from 6 to 1), whereas Random-selection exhibited considerable variation (ranging from 132,449 to 11,901).