A Note on the Maximum Size of a Rectilinear Maze

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 squared/3 + 8k/3 + 1 for mazes without ci...

Full description

Saved in:
Bibliographic Details
Main Authors: Shing, Man-Tak, Mayer, Michael M, Hefner, Kim A
Format: Report
Language:English
Subjects:
Cybernetics
GRAPHS
GRIDS
HEURISTIC METHODS
MOBILE
PATHS
PROBLEM SOLVING
ROBOTS
SEARCHING
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 squared/3 + 8k/3 + 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.