Accession Number:

ADA214445

Title:

A Note on the Maximum Size of a Rectilinear Maze

Descriptive Note:

Technical rept. Sep 1988-Aug 1989

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Report Date:

1989-09-01

Pagination or Media Count:

11.0

Abstract:

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.

Subject Categories:

  • Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE