An Investigation on Reinforcement Learning Approaches to Maze Solving
TL;DR
This paper summarizes the maze solving methods based on RL and mainly includes seven categories: Deep Q-Networks, Quantum Reinforcement Learning(QRL), Hierarchical RL, Curriculum Learning, Reward Shaping, Transfer Learning, and Multi-Agent RL.
Abstract
The problem of moving from a starting point to a destination through a maze of walls and passages, known as maze solving, has been an active field of research in mathematics and computer science for decades with applications to robotics, logistics, network routing and game AI. Classical search algorithms such as Depth First Search (DFS), Breadth First Search (BFS) and A* provide deterministic guarantees but require complete prior knowledge of the environment and fail in dynamic or partially observable settings. Reinforcement learning (RL) provides a completely different paradigm. Agents learn the optimal navigation strategy through trial and error interaction, without relying on predefined maps. This paper summarizes the maze solving methods based on RL. The research methods mainly include seven categories: Deep Q-Networks, Quantum Reinforcement Learning(QRL), Hierarchical RL, Curriculum Learning, Reward Shaping, Transfer Learning, and Multi-Agent RL. Each category has representative works, potential mechanisms and experimental results. Then the sample efficiency, scalability, observability requirements and applicability are compared to determine three urgent challenges: sample efficiency in large-scale maze, partial observability and processing of dynamic environment, and the gap between simulation and reality. The purpose of this survey is to provide researchers with a systematic understanding of the current landscape and determine the direction of future work.