Wow, the video jumped right at me when I was browsing the site, despite my turned on content blocker and of course disable of pop-ups. Why would somebody do that? Or it’s just a quirk of Safari on my iPhone?
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:
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:
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.
Wow, the video jumped right at me when I was browsing the site, despite my turned on content blocker and of course disable of pop-ups. Why would somebody do that? Or it’s just a quirk of Safari on my iPhone?
They mention that the input grid contains the layout of the maze, but isn’t the point of solving a maze that you don’t have a global view of it?
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.
Funny, I was actually thinking of micromouse when I made my comment, thank you for clarifying
My third maze edit stumped the demo.