A system, comprising: one or more computing devices comprising program instructions that when executed on or across one or more processors implement (a) a behavior planner of a vehicle and (b) a motion selector of the vehicle; wherein the behavior planner is configured to: generate, using a combination of (a) a tree search algorithm and (b) heuristics produced by one or more machine learning models, a plurality of conditional action sequences with respect to the vehicle, including a first conditional action sequence and a second conditional action sequence, wherein the first conditional action sequence corresponds to a first set of anticipated states of the vehicle, and wherein the second conditional action sequence corresponds to a second set of anticipated states of the vehicle; and provide, at a first rate, at least some conditional action sequences of the plurality of conditional action sequences to the motion selector; and wherein the motion selector is configured to: generate, based at least in part on (a) one or more conditional action sequences provided by the behavior planner and (b) respective data sets obtained at a second rate from one or more sensors of the vehicle, one or more motion-control directives, wherein the second rate exceeds the first rate; and transmit the one or more motion-control directives to one or more motion control subsystems of the vehicle. one or more computing devices comprising program instructions that when executed on or across one or more processors implement (a) a behavior planner of a vehicle and (b) a motion selector of the vehicle; wherein the behavior planner is configured to: generate, using a combination of (a) a tree search algorithm and (b) heuristics produced by one or more machine learning models, a plurality of conditional action sequences with respect to the vehicle, including a first conditional action sequence and a second conditional action sequence, wherein the first conditional action sequence corresponds to a first set of anticipated states of the vehicle, and wherein the second conditional action sequence corresponds to a second set of anticipated states of the vehicle; and provide, at a first rate, at least some conditional action sequences of the plurality of conditional action sequences to the motion selector; and wherein the motion selector is configured to: generate, based at least in part on (a) one or more conditional action sequences provided by the behavior planner and (b) respective data sets obtained at a second rate from one or more sensors of the vehicle, one or more motion-control directives, wherein the second rate exceeds the first rate; and transmit the one or more motion-control directives to one or more motion control subsystems of the vehicle. generate, using a combination of (a) a tree search algorithm and (b) heuristics produced by one or more machine learning models, a plurality of conditional action sequences with respect to the vehicle, including a first conditional action sequence and a second conditional action sequence, wherein the first conditional action sequence corresponds to a first set of anticipated states of the vehicle, and wherein the second conditional action sequence corresponds to a second set of anticipated states of the vehicle; and provide, at a first rate, at least some conditional action sequences of the plurality of conditional action sequences to the motion selector; and wherein the motion selector is configured to: generate, based at least in part on (a) one or more conditional action sequences provided by the behavior planner and (b) respective data sets obtained at a second rate from one or more sensors of the vehicle, one or more motion-control directives, wherein the second rate exceeds the first rate; and transmit the one or more motion-control directives to one or more motion control subsystems of the vehicle. generate, based at least in part on (a) one or more conditional action sequences provided by the behavior planner and (b) respective data sets obtained at a second rate from one or more sensors of the vehicle, one or more motion-control directives, wherein the second rate exceeds the first rate; and transmit the one or more motion-control directives to one or more motion control subsystems of the vehicle.