A note on the maximum size of a rectilinear maze
Hefner, Kim A. S.
Mayer, Michael McClanahan
MetadataShow full item record
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 squared + 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.
RightsThis publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
NPS Report NumberNPS-52-89-057
Showing items related by title, author, creator and subject.
A Class of Bounded and Partially Bounded Nonlinear Controllers for First and Second Order Dynamical Systems Clemente, Eddie; Rodríguez-Liñán, M. C.; Meza-Sánchez, Marlen; Monay-Arredondo, Luis; Herrera, Leonardo (IEEE, 2021-06-30);This letter proposes structurally simple, bounded and partially bounded nonlinear controllers that offer satisfactory performance, demonstrated by their application to first and second-order dynamical systems. This is done ...
Buck, Ralph V. (Monterey, California. Naval Postgraduate School, 1965);The problem of estimating the position of an extreme point of an unknown function of several independent variables is examined for the case where the dependent variable is known to be bounded. The classical method of ...
Shi, Ronghua; Se, Xi Yang Ronald (Monterey, CA; Naval Postgraduate School, 2019-09);Verification of data-plane software is limited to verifying point properties such as bounded packet processing time or not misinterpreting malformed packet headers, which usually are chosen to illustrate the merits of some ...