I discovered when doing something in this space recently that even the simple case of doing optimal planning for a particle under Newtonian dynamics, with limits on eg. velocity and acceleration, is NP-Complete.