How to pick acceleration that minimizes my travel time without overshooting the destination?

Question

This is for a game AI where everything takes place in time ticks.

Imagine we are at the origin and we want to reach point $(d, 0)$ on the $x$-axis. We already have some initial velocity $v_i$.

Every second, we can supply a non-negative acceleration $0 \leq a$, and the position/velocity will update so we can do it again the next second. Friction is then applied to the velocity as the turn ends.

So for one turn we have:

$(V_i + a)(1-f) = V_f$

And then that $V_f$ becomes $V_i$ next turn.

How do I choose my $a$ parameters over time so that I arrive at the destination in the shortest amount of time, and without "overshooting" the destination? In other words I want to get there fast but also decelerate fast and stay at the spot -- I don't want to just blast through it at max acceleration the whole time.

Answer 1

If we have no other limitations but a maximum acceleration, minimum travel time to rest (zero velocity) at stationary destination is achieved by constant acceleration. For the initial part of the trip, we accelerate towards the target. For the final part of the trip, we decelerate (accelerate away from the target). If we started from rest, the turnaround would be at the halfway point.

Friction does not change that. The turnaround point depends only on the friction and the initial velocity.

Unfortunately, OP uses discrete time, with velocity and friction defined as an iteration. This makes things difficult.

Fortunately, a game AI that is only limited by maximum acceleration, does not need to calculate the turnaround point: all it needs to find out whether it is part the turnaround point or not. If it is, it needs to decelerate at maximum power; if not, it can still accelerate at maximum power towards the target.

To find out whether it is at or past the turnaround point, the AI only needs to find out how hard it needs to decelerate to arrive at the destination with zero velocity. If it is at or near the maximum deceleration, then the AI is at or past the turnaround point, and must decelerate.

---

First, we need to find the non-iterated forms for the velocity and position of an object, with constant acceleration.

Let $C = 1-f$, and $a$ some constant acceleration. Then, as defined in the question, $$v_{i+1} = ( v_i + a ) C$$ Expand a few iterations, $$\begin{array}{l} v_1 = ( v_0 + a ) C = v_0 C + a C \\ v_2 = ( v_1 + a ) C = ( ( v_0 + a ) C + a ) C = v_0 C^2 + a C^2 + a C \\ v_3 = ( v_2 + a ) C = ( ( ( v_0 + a ) C + a ) C + a ) C = v_0 C^3 + a C^3 + a C^2 + a C \end{array}$$ to see that the velocity at time step $i$ with constant acceleration $a$ is $$v_i = v_0 C^i + a \sum_{k=1}^{i} C^k$$ Because $$\sum_{k=1}^{i} (1 - f)^k = \left ( \frac{1}{f} - 1 \right ) \left ( 1 - ( 1 - f)^i \right )$$ the velocity at time step $i$ is $$v_i = v_0 (1 - f)^i + a \left ( \frac{1}{f} - 1 \right ) \left ( 1 - ( 1 - f )^i \right ) \tag{1}\label{NA1}$$

The position at the end of time step $i$ is $$x_{i+1} = x_i + v_i + \frac{a}{2}$$ or, if you want to be pedantic, $x_{i+1} = x_i + v_i \tau + \frac{a}{2} \tau^2$, where $\tau = 1$ is the duration of each time unit. If you wonder about that third term, then remember that $v(t) = \int_0^t a(\tau) d \tau$ and $x(t) = \int_0^t v(\tau) d\tau = x_0 + v_0 t + \frac{a}{2} t^2$.

If we expand the position iterations, $$\begin{array}{l} x_1 = x_0 + v_0 + \frac{a}{2} \\ x_2 = x_1 + v_1 + \frac{a}{2} = x_0 + v_0 + v_1 + 2 \frac{a}{2} \\ x_3 = x_2 + v_2 + \frac{a}{2} = x_0 + v_0 + v_1 + v_2 + 3 \frac{a}{2} \end{array}$$ you can see that in the general case, $$x_i = x_0 + a \frac{i}{2} + \sum_{k=0}^{i} v_k$$ Substituting $\eqref{NA1}$ and massaging a bit, we get the position at time step $i$, $$x_i = x_0 + a \frac{i}{2} + \frac{a (1 - f) - v_0 f}{f^2} (1 - f)^{i + 1} + \frac{a i + 2 a + v_0}{f} - a (i + 1) - \frac{a}{f^2} \tag{2}\label{NA2}$$

---

The pair of equations $x_n = d$, $v_n = 0$ does not seem to have algebraic solutions for $a$ and $n$.

Solving for $v_n = 0$ for $n$ yields $$n = \left\lceil \frac{\log\left(\frac{(1 - f)a}{(1 - f)a - f v_0}\right)}{\log\left(1-f\right)}\right\rceil$$ where $\lceil\dots\rceil$ denotes the ceiling function (rounding up). This is the number of steps needed to decelerate to standstill (if $v_0 \ge 0$ and $a \lt 0$). In pseudocode,

Function Steps_to_standstill(v0, a): # a < 0
    Return ceil( log((1-f)*a/((1-f)*a-f*v0)) / log(1-f) )
End Function

Solving $x_n = d$ for $a$ yields the acceleration needed to reach distance $d$ in $n$ steps, $$a = \frac{v_0 (1-(1-f)^{n + 1}) - f d}{f + \frac{1}{f} - 2 - \frac{1}{f} (1-f)^{n + 2} + n \left ( \frac{f}{2} - 1 \right)}$$ In pseudocode,

Function Acceleration_to(n, d, v0):
    Return (v0*(1-pow(1-f, n+1)) - d*f) / (f + 1/f - 2 - pow(1-f, n+2)/f + n*(f/2 - 1) )
End Function

The pseudocode for the AI could be implemented as follows:

# d = Distance from target
# v = Current velocity (v > 0 if towards target)
# a = Maximum acceleration/deceleration

If (v < 0) Then:
    We are heading away from the target,
    so accelerate towards the target

Else
If (d <= a) and (v >= -a) and (v <= a) Then:
    Land at the target

    # To be exactly correct, we should adjust the
    # acceleration one step before, as the acceleration
    # on the landing step should be 0.
Else:
    # Find the number of time steps to stop
    # at maximum deceleration.
    n = Steps_to_standstill(v0, -a)
    If (n < 3) Then:
        # We are going very slow.
        If (d > 2*a) Then:
            Accelerate
        Else:
            Prepare for landing (decelerate)
        End If
    Else:
        # Find the acceleration we need, to reach
        # the target in about n-1 time steps.
        an = Acceleration_to(n-1, d, v)
        If (an > -a) Then:
            Accelerate
        Else:
            Decelerate
        End If
    End If
End If

The above pseudocode is untested, but should work. If you do find an error or weirdness (other than the exact landing, which should be done one step prior to the actual landing since we control acceleration, and velocity control is effectively one time step behind), do let me know in the comments, so I can check and correct if necessary.