Function to minimize time to go from A to B with limited acceleration

[pgimeno]

I have this problem.

Imagine, in 3D space, a rocket that has to go to a certain point in the minimum possible time, so that when it gets to its destination its speed is 0. How much thrust to apply and in what direction?

My problem is purely ideal: there is no mass loss due to fuel consumption; the thruster has maximum force it can apply and can maintain it indefinitely; the rocket can be considered a point in space, and there's no gravity involved. The orientation and power of the thrust can change at will between 0 and the maximum, and the changes are assumed to happen instantaneously. Since the mass is constant, we can disregard force and just deal with acceleration. So, there is a maximum acceleration. I suspect that there's no need to reduce it below the maximum at any point until reaching the destination, but I can't prove it.

The complication comes from the fact that the rocket can have an arbitrary initial velocity pointing anywhere. Otherwise, the obvious answer would be to accelerate at maximum thrust towards the destination until the distance matches the space needed to "brake", then decelerate (i.e. accelerate in the opposite direction) until it stops, which should happen exactly when it's in the destination. If I didn't mess the calculation up, the distance needed to "brake" is v^2/(2a) where a is the maximum acceleration and v the velocity at a given instant. This is also the solution for the 1D case, which only has the extra complication that the rocket can overshoot once, depending on the initial velocity.

Since we have, in a sense, three points involved (source, destination, and the "tip" of the velocity vector when translated to the rocket), the problem can always be translated to 2D by using the plane that crosses these three points. Therefore, it's enough to solve the problem for the 2D case.

Ideally for me, the solution would be in the form of a function that accepts a velocity vector and a destination point, and gives the acceleration to apply at that instant. It can always be rotated so that the destination is to the right of the rocket on the X axis, in which case a distance to the destination would suffice instead of two coordinates. This diagram will hopefully illustrate it:

Does anyone have a clue on how to find such a function?

 

[pgimeno]

Nobody has an answer? Is the problem really that tough? I also discussed it in IRC (FreeNode) for hours, and none of the people who tried could come up with an answer. It seems no piece of cake indeed.

An alternative formulation for the problem is: find a function a_{p_F, v_F}(t) that gives the acceleration necessary for going from (0, 0) at zero velocity, to p_F at v_F velocity, in the least possible time. Reversing time should give a solution to the original formulation.

 

[K^2]

Do you care how fast you cross the destination point? If not, yes, the solution is fairly simple, and you can use constant acceleration.

Suppose, initial displacement is (x,y) relative to destination. For each direction you have an equation.

$$\frac{1}{2}a_xt^2 + v_xt + x = 0$$

$$\frac{1}{2}a_yt^2 + v_yt + y = 0$$

That's two equations and three unknowns. But you have an extra equation to fix the maximum magnitude of acceleration.

$$a_x^2 + a_y^2 = a_{max}^2$$

These 3 equations can be solved simultaneously to find the direction in which acceleration must be applied.


If you want the rocket to get to destination and stop, you generally have to vary thrust. There is a linear optimization problem that minimizes acceleration integrated over time. The solution is a critically-damped harmonic oscillator. All you really have to do with that one is find the value for ω₀ such that initial acceleration is equal to your maximum.

 

[lalbatros]

pgimeno,

Like you, I consider that this is not a simple question.
However, this is mainly so because I am not a specialist in "optimal control" theory.
You can google on "optimal control" and you will likely find some good text on that.

A first approach is to formulate the optimization problem in a more or less standard way.
Your problem combines a function to be minimized (the time) and constraints.
Therefore, it is very likely that the method of the Lagrange multipliers will help a lot to solve the problem.
There will be then one such multiplier for each constraint.
These constraints are:

1. for each time, the four equations of motion (for x, y, vx, vy)
2. four boundary conditions for the initial and final velocities
3. for each time a limit on the thrust that can be exerced by the rocket

The constraints 1 and 2 are linear, while the constraints 3 are nonlinear.
The constraints 1 and 2 are equality constraints and will all be "active constraints".
The constraints 3 are inequalities, and might not be all "active constraints", which is bad news for analytical solutions.

(active constraints are constraint that are 'hit' by the solution, which means they play a role)

Unfortunately, the function to be minimized is the time.
If you consider the time as an index for the unknows of the problem (x, y, vx, vy),
then you end up with the number of unknows being itself an unknown!

Therefore, the explanations above need to be amended so as to avoid that.
This is possible by using another index than the time.
An arbitrary parameter z might be used such that z=0 corresponds to the initial condition, and z=1 corresponds to the final condition.
This will add two constraints in the modified formulation.

In addition, the "equation of motion for the time" implies an additional unknown and an additional constraint: dt/dz = vt .

Finally, the function to be minimized is the time = integral(vt,{z,0,1}) .
By parsing this last equation, you will be able to identify the "Lagrangian" of this problem.
Combining the Lagrangian and the constraints using "Lagrange Multipliers" should put you on known tracks in "optimal control theory".
This does not garantee an easy solution, even less an analytical solution.

I would be curious to see how this could be developped.

 

[pgimeno]

Do you care how fast you cross the destination point? If not, yes, the solution is fairly simple, and you can use constant acceleration.

Yes, the destination point has to be reached at zero speed.

But your idea of a constant acceleration suggested me another approach.

It seems that finding a provably optimal solution is going to be really tough. I don't know if this solution is optimal, it probably isn't, but here we go. It seems to me that it's possible to solve the problem in 1D independently for each component, adding the constraint that the maximum acceleration for each axis must meet your last equation:

$$a_x^2 + a_y^2 = a_{max}^2$$

Since the 1D solution has two possible accelerations to apply (a_max and -a_max), the 2D solution has four possible orientations of the vector.

As I said, the 1D case has the complication of the possibility of overshooting. The solution involves the calculation of the point where the final speed would be zero if we started to brake since the beginning, which is given by v|v|/(2a) where a is the maximum acceleration for that axis, and v|v| is used instead of v² so that the result has the same sign as the velocity. If it's past the destination, it will overshoot, so the total time will be the time needed for braking until stopping, plus the time needed to go from the stopping point to the destination. The same reasoning applies if the velocity points in the opposite direction to where the destination is. If the stopping point is between the current position and the destination, then the total time is also related to that calculation and is not difficult to find.

Actually, I'm not completely convinced about this solution being non-optimal. But I have no idea of how to put it in the form of equations to solve for the acceleration, let alone how to prove it's optimal or not.

If you want the rocket to get to destination and stop, you generally have to vary thrust.

If you mean vary thrust as in vary the modulus, I'd be surprised, because the thrust that you're reducing could be used to approach the target faster and brake harder.

 

[pgimeno]

lalbatros, thanks, but I'd have a hard time converting your explanations to something I could use. I'm convinced that the approach I've stated above must be really close to the optimal one, and I might end up using it. If you or someone can put the explanations in a more practical form, as K^2 did, I'd be very grateful.

 

[K^2]

If you mean vary thrust as in vary the modulus, I'd be surprised, because the thrust that you're reducing could be used to approach the target faster and brake harder.

The vector has to be changed, but yes, in this case, all of the change can be absorbed into direction.

So you want to fire with maximum thrust, vary direction, and go from (x,y) with some initial (v_x, v_y) to (0, 0) with zero speed, right? With a change of coordinate system, this can be turned into a general solution with arbitrary initial and final position/velocity.

I'll try to think about it and see if there is an analytical solution.

 

[pgimeno]

So you want to fire with maximum thrust, vary direction, and go from (x,y) with some initial (v_x, v_y) to (0, 0) with zero speed, right? With a change of coordinate system, this can be turned into a general solution with arbitrary initial and final position/velocity.

Yes, that's right.

I've been giving a bit more thinking to the (possibly not minimal) solution I've stated, namely to fix the maximum acceleration for both axes since the beginning. It seems to me that finding the maximum acceleration per axis that makes the times match, would be the objective.

Also, I've devised an empirical way to disprove minimality (but not to prove it). The idea is to calculate the new acceleration per axis after the system has evolved a bit. If the solution is different, then it's not minimal. If the solution is the same, then it may be minimal or not.

 

[pgimeno]

I just found a simple proof that my solution is not minimal, unless there are multiple minimal solutions, which I doubt: Rotating the reference system should give a rotated solution. It doesn't.