Methods and apparatus for dynamically routing robots based on exploratory on-board mapping are disclosed. A control system of a robot includes an image manager to command a depth camera to capture depth images of an environment. The depth camera has a field of view. The control system further includes a map generator to generate a map of the environment based on the depth images. The map includes a representation of unoccupied space within the environment, and a path extending through the unoccupied space from a reference location of the robot to a target location of the robot. The control system further includes a field of view evaluator to determine whether the field of view associated with the reference location satisfies a threshold. The control system further includes a route generator to generate, in response to the field of view associated with the reference location satisfying the threshold, a route to be followed by the robot within the environment. The route includes a first candidate location located along the path of the map between the reference location and the target location. The first candidate location is within the field of view associated with the reference location.