A method includes receiving sensor data of an environment about a robot and generating a plurality of waypoints and a plurality of edges each connecting a pair of the waypoints. The method includes receiving a target destination for the robot to navigate to and determining a route specification based on waypoints and corresponding edges for the robot to follow for navigating the robot to the target destination selected from waypoints and edges previously generated. For each waypoint, the method includes generating a goal region encompassing the corresponding waypoint and generating at least one constraint region encompassing a goal region. The at least one constraint region establishes boundaries for the robot to remain within while traversing toward the target destination. The method includes navigating the robot to the target destination by traversing the robot through each goal region while maintaining the robot within the at least one constraint region.