A Note on the Maximum Size of a Rectilinear Maze

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 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1989
Accession Number
ADA214445

Entities

People

  • Kim A. Hefner
  • Mantak Shing
  • Michael M. Mayer

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Autonomy

DTIC Thesaurus Topics

  • California
  • Computer Science
  • Computers
  • Dead Reckoning
  • Diameters
  • Grids
  • Guidance
  • Mathematics
  • Security

Fields of Study

  • Mathematics

Readers

  • Agent-Based Social Robotics and Mobile-Assisted Learning in Virtual Environments.
  • Graph Algorithms and Convex Optimization.

Technology Areas

  • AI & ML
  • AI & ML - Autonomous Systems
  • AI & ML - Machine Learning Algorithms
  • Autonomy