An apparatus comprising an autonomous vehicle comprising controllable devices configured to cause the vehicle to traverse at least part of an optimal trajectory in a manner consistent with control policies and with cost rules that apply to respective transitions between successive world states along a world trajectory, a controller to provide commands to the controllable devices in accordance with the world trajectory, sources of information about world states at successive times, and a computational element, the apparatus being characterized in that the computational element is configured to: iteratively update a) a set of world states, each of the world states representing a combination of a state of the vehicle, a state of an environment of the vehicle, and a state of at least one other object in the environment based at least in part on the information about world states, and b) a set of world trajectories, each of the world trajectories representing a temporal transition between one of the world states and another of the world states, each of the iterations of the updating comprising for each of one or more of the world states and for a corresponding vehicle control policy, simulating a candidate trajectory from the world state to a subsequent world state, if the simulated candidate trajectory does not violate a constraint, adding the trajectory to the set of world trajectories to form an updated set of world trajectories, and if necessary, adding a new world state to the set of world states corresponding to the transition represented by the simulated candidate trajectory to form an updated set of world states, and determining a minimum-cost path through the updated set of world states and the updated set of world trajectories, the determining including applying cost rules to respective transitions of world trajectories, and deliver to the controller information representing a next transition from the current world state to a next world state along the minimum-cost path, for autonomous control of the vehicle. iteratively update a) a set of world states, each of the world states representing a combination of a state of the vehicle, a state of an environment of the vehicle, and a state of at least one other object in the environment based at least in part on the information about world states, and b) a set of world trajectories, each of the world trajectories representing a temporal transition between one of the world states and another of the world states, each of the iterations of the updating comprising for each of one or more of the world states and for a corresponding vehicle control policy, simulating a candidate trajectory from the world state to a subsequent world state, if the simulated candidate trajectory does not violate a constraint, adding the trajectory to the set of world trajectories to form an updated set of world trajectories, and if necessary, adding a new world state to the set of world states corresponding to the transition represented by the simulated candidate trajectory to form an updated set of world states, and determining a minimum-cost path through the updated set of world states and the updated set of world trajectories, the determining including applying cost rules to respective transitions of world trajectories, and deliver to the controller information representing a next transition from the current world state to a next world state along the minimum-cost path, for autonomous control of the vehicle. for each of one or more of the world states and for a corresponding vehicle control policy, simulating a candidate trajectory from the world state to a subsequent world state, if the simulated candidate trajectory does not violate a constraint, adding the trajectory to the set of world trajectories to form an updated set of world trajectories, and if necessary, adding a new world state to the set of world states corresponding to the transition represented by the simulated candidate trajectory to form an updated set of world states, and determining a minimum-cost path through the updated set of world states and the updated set of world trajectories, the determining including applying cost rules to respective transitions of world trajectories, and deliver to the controller information representing a next transition from the current world state to a next world state along the minimum-cost path, for autonomous control of the vehicle.