Systems, methods, devices, and other techniques are described for planning motions of one or more robots to perform at least one specified task. In some implementations, a task to execute with a robotic system using a tool is identified. A partially constrained pose is identified for the tool that is to apply during execution of the task. A set of possible constraints for the unconstrained pose parameter are selected for each unconstrained pose parameter. The sets of possible constraints are evaluated for the unconstrained pose parameters with respect to one or more task execution criteria. A nominal pose is determined for the tool based on a result of evaluating the sets of possible constraints for the unconstrained pose parameters with respect to the one or more task execution criteria. The robotic system is then directed to execute the task, including positioning the tool according to the nominal pose.