Vehicle trajectory tree search

Techniques are discussed herein for generating trajectories for controlling motion and/or other behaviors of vehicles in complex driving environments. In certain examples, a search algorithm may be used to determine and evaluate a set of possible candidate actions for a vehicle, including candidate actions based on a predetermined exploration policy and additional candidate actions based on machine learned models that output predicted behaviors for the vehicle based on the current driving environment. Costs associated the various candidate actions may be evaluated based on state transition costs and/or future state predictions of the driving environment. Certain examples may include a tree search using a combination of predetermined heuristic candidate actions and adaptive-learning candidate actions at various nodes within a tree structure representing a driving route from a current vehicle state to an intended end state.