Abstract This paper addresses a navigation problem for a very simple robot equipped with only a map, a noisy compass, and a contact sensor. We present a planning algorithm that enables such a robot to navigate reliably through its environment. The algorithm constructs a directed graph in which each node is labeled with a subset of the environment boundary. Each edge is labeled with a sequence of actions that can move the robot from any location in one such set to some location in the other set. We use a variety of local planners to generate the edges, including a "corner-finding" technique that allows the robot to travel to and localize itself at a convex vertex of the environment boundary. The algorithm forms complete plans by searching the resulting graph. To accelerate the planning process, we also present a priority function to focus computational effort on attempting to generate edges between the most promising node pairs. We have implemented this algorithm and present results from both simulation and a physical realization on the iRobot Create differential drive platform.