Find acceleration to stop at target in frictionless 2D space

[Ziks]

This is a problem that's appeared in a game I am writing, and is a bit beyond the mechanics I can sort-of remember from high school.

The context is I have an object in 2D space which has a position p and a velocity u, and a goal position G I want that object to be in as soon as possible. At each time step, I can add an acceleration a = xA, where A is the maximum acceleration and -1 \leq x \leq 1. When the object reaches the goal position, its velocity should be 0.

I need to define a function f with produces an acceleration a = f(G, A, p, u). This function should yield a sequence of states s_0, s_1, s_2 \ldots s_n with the smallest possible length n, where each state s_i is of the form s_i = (\mbox{position}, \mbox{velocity}).

The sequence of states must meet the criteria:

s_0 = (p, u) \\<br /> <br /> s_n = (G, 0) \\<br /> <br /> s_{i+1} = (\mbox{position}(s_i) + \mbox{velocity}(s_i), \mbox{velocity}(s_i) + f(G, A, \mbox{position}(s_{i+1}), \mbox{velocity}(s_i)))

Also, -A \leq f(G, A, p, u) \leq A

It's pretty trivial in one dimension, but extrapolating it to two dimensions is difficult because of the constraint on maximum acceleration.

My one dimensional solution:

f(G, A, p, u) = \begin{cases}<br /> \mbox{min}(u + A, v) &amp; u &lt; v \\<br /> \mbox{max}(u - A, v) &amp; u &gt; v \\<br /> u &amp; \mbox{otherwise}\end{cases}, where v=\sqrt{2A(G - p)}

My reasoning here is that it should find out the largest possible velocity the object can travel at while still being able to slow and stop at the target, and then depending on whether that velocity has been exceeded or not the object will either accelerate or decelerate by the acceleration limit.

I'm at a loss as to how to extrapolate this into two dimensions, any help is appreciated.

 

[mfb]

I think we had a similar question here one year ago (?), I don't remember if there was some reasonable solution.

In the continuous case, the best trajectory always uses the maximal acceleration. I would expect that the stepwise version will do the same, maybe with 1-2 steps as exception.

To restrict the search space: I would expect that three periods of constant acceleration direction will give a reasonable approximation to the ideal path. This leaves 5 degrees of freedom (three directions and two times), with 4 constraints (final position and velocity), so 1 parameter can be optimized.

 

[Ziks]

It would make sense that a decent method would be to eliminate tangential velocity first, and then solve it as the one dimensional case along the radial line (treating the goal as the centre). So the three stages you describe would be to:

1. Eliminate tangential velocity by accelerating in the opposite direction
2. Accelerate directly towards goal until the critical point is reached where deceleration is required
3. Acelerate in the opposite direction of motion to stop on the goal

This will certainly solve the problem of reaching the target with a final velocity of zero, but is it optimal? It will probably be good enough for my application, although I am interested in knowing if an optimal general solution exists (assuming this is not it).

An alternative I may test could be finding a way of determining the number of steps required to reach the target in the 1D case as a function of the maximum acceleration, and then balancing what ratio of the acceleration is allocated to solving the 1D case on both the X and Y axis such that they both reach the target at the same time.

 

[Khashishi]

Can you brute force it? Just estimate based on two 1D problems, and try some iterative solution? Granted, I haven't really thought it through.

edit:
I think this is an inverse kinematics problem. They can get a lot more complicated in general.
https://en.wikipedia.org/wiki/Inverse_kinematics

 

[mfb]

1. Eliminate tangential velocity by accelerating in the opposite direction
2. Accelerate directly towards goal until the critical point is reached where deceleration is required
3. Acelerate in the opposite direction of motion to stop on the goal

This will certainly solve the problem of reaching the target with a final velocity of zero, but is it optimal?

I am sure it is not, and it gives other issues, too - the tangential direction changes as the object moves. You could try to get rid of angular momentum first (this gives constant acceleration in one direction as first step), but I think my proposed method is more general and will find a better solution in most cases.

It will probably be good enough for my application, although I am interested in knowing if an optimal general solution exists (assuming this is not it).

There is an optimal solution, the problem is just to find it without excessive numerical simulations for every set of parameters.

An alternative I may test could be finding a way of determining the number of steps required to reach the target in the 1D case as a function of the maximum acceleration, and then balancing what ratio of the acceleration is allocated to solving the 1D case on both the X and Y axis such that they both reach the target at the same time.

Hmmhmm... could lead to interesting results.