Vector pathing via acceleration with velocity

Question

I'm trying to solve a scenario where I need to find the smallest number of time steps to reach a location in 2d space, where I can manipulate the velocity with an acceleration at each time step where the acceleration has a maximum magnitude of $n$. This sounds vague, so let me clarify:

I have the following scenario:

Where the green ball is the start location, the arrow is its starting velocity, and the red ball is the target location. At any given point, I can change the green ball's velocity with an acceleration vector with at most a magnitude of $n$, that is applied at the end of the turn.

As in, the green ball is moved by the velocity vector using the following equation:

$$\text{Location}_\text{new} = \text{Location}_\text{old} + \text{Velocity}$$

then the velocity vector is updated with the acceleration, using the following equation:

$$\text{Velocity}_\text{new} = \text{Velocity}_\text{old} + \text{Acceleration}$$

Below is a more concrete example (where orange is the veolicty):

In this case the ball starts at $(1,3)$ and I want to get it to $(2,1)$. Each "turn" I can change the velocity by adding an acceleration vector that has a maximum magnitude of $1$ (in this case $n=1$). As you can see, this is a pretty simple case, simply remove the horizontal velocity when it's aligned with the target then the vertical when it's aligned again. Of course, it starts to become more complicated once the ball is traveling in a different direction to the target, and an optimized solution would take a diagonal path.

If anyone has any sources for related work, or suggestions it would be greatly appreciated!

Edited to clarify acceleration and explicitly define the movement mechanics

Answer 1

There is a theorem that can be used to characterize the optimal solution, which then makes algorithm design trivial. In particular, you can solve the problem in logarithmic time.

Theorem

Suppose we are hoping for a solution that uses $k$ time steps. Let $v_0$ denote the starting velocity vector, $s$ the starting position, and $t$ the target position. Let $d = t - (s + kv_0)$. Then without loss of generality the solution can use acceleration vectors that all point in direction $d$ (i.e., if there exists a solution, there exists a solution that satisfies this condition). Moreover, there is a solution iff $\|d\| \le nk(k-1)/2$. If this condition holds, you can use an acceleration of $a=2d/k(k-1)$ in each time step (the same acceleration in each time step), i.e., an acceleration in direction $d$ with a magnitude chosen appropriately so that you reach the target.

Proof of the theorem

Why does this solution work? Well, letting $p_i,v_i,a_i$ denote the position, velocity vector, and acceleration at time step $i$, we have $$\begin{align*} v_i &= v_0 + a_0 + a_1 + \dots + a_{i-1}\\ p_i &= p_0 + v_0 + v_1 + \dots + v_{i-1}\\ &= p_0 + i v_0 + (i-1) a_0 + (i-2) a_1 + \dots + a_{i-2} \end{align*}$$ Now if $a_0=a_1=a_2=\cdots=a$, then we have $$\begin{align*} p_k &= p_0 + k v_0 + [1 + 2 + \dots + (k-1)] a\\ &= p_0 + k v_0 + \frac{1}{2} k(k-1) a \end{align*}$$ Now note that $p_0=s$, and our goal is to make $p_k=t$, so solving this equation for $a$ yields the expression given above.

Why is this the optimal solution? If you look at $(k-1) a_0 + (k-2) a_1 + \dots + a_{k-2}$, if we require $\|a_i\| \le n$ for all $i$, then the magnitude of $(k-1) a_0 + (k-2) a_1 + \dots + a_{k-2}$ is maximized when all $a_i$ point in the same direction, and moreover, when all $a_i$ have magnitude $n$.

Algorithm

This suggests a straightforward algorithm: find the smallest integer $k$ such that

$$\|t - (s+kv_0)\| \le n k(k-1)/2$$

and use the theorem above to output a solution for this $k$. You can use binary search to find the smallest such $k$. The correctness of the algorithm follows immediately from the theorem.

It might be possible to construct a constant time algorithm, as finding $k$ is closely related to solving a quadratic equation, and you might be able to use a closed-form solution for the quadratic equation, but I haven't tried to work out the details, as the difference between log-time vs constant-time might not be worth worrying about -- they will both be extremely fast in practice.