Methods, systems, and apparatus, including computer programs encoded on computer storage media, for performing robot plan online adjustment. A method includes receiving an initial plan for performing a particular task with a robot having a sensor. The initial plan defines an initial path having a plurality of waypoints. Each waypoint is associated with a target position and a target velocity. The method includes generating an alternative path from the initial path. Generating an alternative path includes generating a plurality of alternative paths including performing respective modifications to one or more waypoints in the initial plan, evaluating each alternative path according to a simulated total time duration required for the robot to traverse the alternative path, and selecting an alternative path having a total time duration that is less than a total time duration of the initial plan.