Optimal-time trajectory in 2D and 3D with simple constraints

Question

I'm trying to find the optimal-time trajectory for an object (point mass) from point p0 with initial velocity v0 to point p1 with velocity v1. I'm considering a simple environment without any obstacles to move around. The only constraint is a maximum acceleration in any direction of a_max and optionally a maximum speed of s_max.

This is easy to work out in 1D but I struggle with the solution 2D and 3D. I could apply the 1D solution separately to each dimension, but this would only limit acceleration and speed in a single dimension. The actual acceleration might be larger in multiple dimensions.

Are there any textbook, closed-form solutions to this problem? If not, how can I solve this in a discrete-event simulation?

Answer 1

In case you're not already aware, the problem you are asking about is generally referred to as the two-point boundary value problem. For some systems, a closed form solution may be extremely difficult to calculate and may not even exist. As such it would help to know more about your dynamics.

Your description would seem to imply that you are working with a double integrator system. If that's accurate then you could use a fixed-final-state-free-final-time controller. Because the dynamics matrix is nilpotent you can find a closed form solution in terms of time, then minimize the function to find the optimal arrival time. From there you can use your favorite numerical integration method to verify that the accelerations are within the desired bound. This approach will actually work for any linear system with a nilpotent dynamics matrix. For additional details please see section IV, Optimally Connecting a Pair of States, of my paper Kinodynamic RRT$^*$: Asymptotically Optimal Motion Planning for Robots with Linear Dynamics.