AI Navigates Mazes Faster Than Traditional Solvers

Imagine a robot exploring an unknown environment, needing to visit every location exactly once while minimizing turns. This fundamental challenge in computer science and robotics has found new solutions through artificial intelligence approaches that outperform traditional methods in specific scenarios. Researchers from Iran's Institute for Research in Fundamental Sciences and K.N.Toosi University of Technology have developed an AI-based method that solves complex exploration puzzles faster than conventional approaches, with implications for robotic navigation and pathfinding applications.

The key finding demonstrates that Monte Carlo Tree Search (MCTS), an artificial intelligence technique, can solve path exploration problems significantly faster than traditional SAT solvers for small to medium-sized scenarios. In tests using the Dash puzzle—a modified version of path traversal where an agent must explore a 2D grid without revisiting cells—the MCTS approach achieved run-times up to 20 times faster than SAT methods for 15x15 grids, completing in 0.09 seconds compared to 5.24 seconds for SAT solvers.

The researchers employed multiple approaches to solve the Dash puzzle, which requires an agent to traverse a grid while marking visited cells and changing direction only when encountering obstacles or previously visited locations. They compared four methods: SAT solvers that convert puzzle constraints into boolean logic, backtracking algorithms similar to depth-first search, randomized MCTS, and breadth-first search. The MCTS method operates through four main steps: selection of the most promising path, expansion of possible moves, simulation of random traversal, and backpropagation of results to update decision values. To optimize performance, the team implemented modifications including pruning failed paths early and using fast rollout functions that reduce memory consumption.

Analysis of the results, conducted on Ubuntu systems with Intel XEON processors, reveals clear performance patterns. For smaller grids (5x5 to 15x15), MCTS consistently outperformed other methods in both run-time and memory usage. The 15x15 grid with 66 obstacles demonstrated particularly strong MCTS performance at 0.09 seconds run-time using 14.2 MB memory, compared to SAT's 5.24 seconds and 13.5 MB. However, the study identified a critical limitation: as grid size increases beyond 30x30, MCTS performance degrades significantly due to computational overhead in the simulation step. The researchers calculated that simulation costs grow exponentially with problem size, making MCTS impractical for large-scale scenarios where SAT solvers maintain better performance.

This research matters because efficient path exploration has real-world applications in robotics, network routing, and memory storage systems. The constraint of minimizing turns directly relates to practical robotic navigation, where turning operations often require robots to reduce velocity, stop, and restart—adding time and energy costs. The demonstrated efficiency improvements for medium-sized exploration problems could lead to faster robotic mapping, more efficient warehouse automation, and improved autonomous vehicle navigation in constrained environments.

The study acknowledges several limitations. The non-overlapping exploration constraint creates dynamic obstacles that prevent MCTS from using pre-processing optimizations available to other methods. Additionally, the branching factor of the search tree remains small (typically 2 or less), creating challenges for tree-based approaches like MCTS when problem scale increases. The researchers note that their method cannot reliably predict complete solutions during simulation, requiring extensive testing of possible movements that becomes computationally prohibitive for large scenarios.