A technique is developed whereby a mobile robot equipped with sonar sensors autonomously explores a hallway environment and during exploration dynamically builds two types of maps: a graph of places defined by distinctive sonar events and a grid map from dead reckoning data that is accurate in the neighborhood of a place. With both maps available the robot can quickly plan a path between arbitrary locations and then define a sequence of behaviors that will move the robot along the selected path. Robust performance is achieved by dividing the computational processes into two parallel operations. Time-critical low-level behaviors like driving and steering in the exploratory mode are controlled by an onboard computer that uses sonar data as input to simple subsumption-based algorithms. 1 Higher level more computationally intense and less-time-critical activities like place designation map making display generation and path planning are performed in parallel on a remote computer that fetches sonar data and issues high-level commands via a radio link. An approach to integrating this work with efforts in planning and navigation to form a larger activity in intelligent vehicle research is discussed in a companion paper.