Solving mazes with neural cellular automata (2021)

That depends on the maze, no? If the maze is a three-dimensional structure large enough for a human to navigate physically then yes the challenge is that there's no global view of it, but there are many mazes that are given as images that fully reveal the map of the maze. Those can still be challenging and fun to solve (at least up to a certain age) if they are complicated enough, a bit like a jigsaw puzzle.

In most maze-solving work in CS and AI the maze state is fully observable. For example that is the case when solving a maze with A* or Dijkstra's algorithm, or with Reinforcement Learning. The challenge then is to find the shortest path to the maze "exit".

In maze-solving with A* the location of the maze exit is used to estimate the heuristic cost function used during the search. In Reinforcement Learning the maze-solving problem is typically formulated as an MDP, a Markov Decision Process, which assumes full observability of the state of the environment.

As far as I can tell, there is very little work in solving mazes and similar grids in a POMDP (Partially Observable MDP) setting or similar. To toot my own horn, this is done in our recent work where we learn Finite State Automata to solve navigation problems on arbitrary grids where the agent doesn't know where the "exit" is and must search the grid for it:

https://github.com/stassa/ijclr_2024_experiments

Then there's the Micromouse competition where robotic "mice" (little wheeled robots these days) compete in solving a maze without being given its map to begin with:

https://en.wikipedia.org/wiki/Micromouse

The goal is for a mouse to search the maze and find the "exit" in its center, then return to the start and perform a number of runs to the center trying to optimise its path. The mouse that finds the shortest path faster wins. In that case you have a combination of searching an unknown environment, mapping it, and then finding an optimal solution for it.