This disclosure describes techniques for autonomous vehicles to determine driving paths and associated trajectories through unstructured or off-route driving environments. When an object is detected within a driving environment, a vehicle may determine a cost-based side association for the object. Various costs may be used in different examples, including costs based on a cost plot and/or motion primitives that may vary for terminal and non-terminal desired destinations (or ending vehicle states). Using tree searches to determine estimated candidate costs, the autonomous vehicle may compare right-side and left-side driving path costs around the object to determine a side association for the object. Based on the side association, the autonomous vehicle may determine an updated planning corridor and/or a trajectory to control the vehicle from a current state to a desired ending vehicle state.