Methods, systems, and apparatus, including computer programs encoded on computer storage media, for generating a motion planning for a robot. One of the methods includes receiving data representing a motion specification for performing a task by a robot in an environment. The motion specification specifies a goal and one or more constraints. An initial motion plan is determined based on the motion specification, where the initial motion plan specifies a trajectory that satisfies the one or more constraints of the motion specification. The initial motion plan is executed by the robot. Sensor data is monitored for detecting a change in the environment. A first updated motion plan is generated for the robot based on the first change in the environment. The first updated motion plan is executed by the robot.