Maze robots that learn
A robot explores a maze it has never seen, then runs it again using what it learned. I put my 2022 coursework robot next to two planners, several learners and an A* oracle, and measured what each one actually gains on thousands of seeded mazes.
"4× fewer steps on the second run" depends on the maze.
In 2022 I described the robot as a blend of Dijkstra's, Trémaux's and A* forming an "iterative machine learning maze solver". It is a randomised depth-first explorer that replays its route, and the measurements now replace that description. On single-route Prim mazes the median gain is 3.7× at 7×7 and 14.7× at 30×30, but only 1.4–2.4× on single-route backtracker mazes, whose one route already winds through most of the maze. On mazes with loops it replays its detours too: its second run averages 1.7–13.1× the shortest route.
The route prover was shortest in all 5,400 mazes.
The route prover keeps exploring until it can prove which route is shortest, so every later run takes it. Its second run was a shortest route in every benchmark maze. On mazes with loops the proof costs extra exploration (256 steps instead of 188 on 15×15 mazes with 10% loops), and it pays that back by the 5th to 17th run. The map planner uses D* Lite, which made exactly the same moves as replanning from scratch with 4–77× less work.
Q-learning never settled. A model of the maze changes everything.
Learning from step costs alone, Q-learning never settled on a shortest route in any of 600 mazes, even after 30 runs. Dyna-Q, replaying 50 remembered moves per step, settled in 97–100% of mazes from around run 10–15. But here planning beats learning: a planner is what model-based learning becomes when the model is the map itself.
An explorer trained once, faster on mazes it never saw.
Learning earns its place when it carries experience from one maze to the next. An explorer whose frontier weights were trained with the cross-entropy method cuts mean first-run steps by 3–14% on Prim mazes at every size, including sizes it never trained on. Training is reproducible byte for byte: CI retrains it on Linux, macOS and Windows and fails if the weights change.
Java 21, a deterministic self-contained simulator, and CI on three operating systems. The robot began as university coursework uploaded in 2022; the originals are kept unchanged in the repository, and the course's own maze framework belongs to the university and is not included. Code, full results and reports.