Methods, systems, and apparatus, including computer programs encoded on computer storage media, for optimizing a plan for one or more robots using a process definition graph. One of the methods includes receiving a process definition graph for a robot, the process definition graph having a plurality of action nodes. One or more of the action nodes are motion nodes that represent a motion to be taken by the robot from a respective start location to an end location. It is determined that a motion node satisfies one or more splitting criteria, and in response to determining that the motion node satisfies the one or more splitting criteria, the process definition graph is modified. Modifying the process definition graph includes splitting the motion node into two or more separate motion nodes whose respective paths can be scheduled independently.