Presents a provably complete strategy for indoor environment exploration by an autonomous mobile robot. Without prior knowledge about the environment, the strategy guarantees the construction of a grid-based map, of the entire reachable area within a bounded region. Multiple map representations are utilized including a topological grid map for guiding the exploration process, a modified occupancy grid for fusing data from multiple range sensors, and a hierarchy of grids for real-time navigation. Experiments using a Nomad 200/sup TM/ robot have shown accurate map construction while navigating at a steady speed of 0.2m/sec.