A Note on the Maximum Size of a Rectilinear Maze
Technical rept. Sep 1988-Aug 1989
NAVAL POSTGRADUATE SCHOOL MONTEREY CA
Pagination or Media Count:
In this paper, we study the problem of searching through an unknown maze by a robot and show that the size of the largest rectilinear maze the robot can explore in at most k steps is bounded by 2K squred 2k 1 for mazes with circuits, and is bounded by 4k squared3 8k3 1 for mazes without circuits, Furthermore, we show that the bounds are tight. Keywords Grid graph Heuristics Maze Mobile robot Path finding Search tree-maze.