Accelerating Particle Problem

The Problem

Given a particle in a 2-dimensional plane that has some initial position and velocity and can accelerate at a constant rate in any direction, in which direction should it accelerate to reach a target destination?

initial velocity acceleration path target initial position

There is only a single acceleration vector for which the particle will actually hit the target. How can we find that vector? This problem statement was actually arrived at via a slightly different question: on which path should the particle travel to reach a target destination in minimal time? I conjecture that following the time-optimal path is the single-acceleration-vector path. In this post, I cover a few ways of thinking about the problem, approximate solutions, an exact solution, and followup questions for another post.

Some Thoughts

A naive sub-optimal path involves two phases. First, accelerate in the opposite direction of travel in order to come to a complete stop. Once stopped, accelerate directly toward the target. This is obviously suboptimal in all but one case: when the initial velocity vector points directly away from the target.

phase one zero velocity phase two single optimal acceleration

A better solution is to imagine a line drawn between the particle and the target. If the velocity vector is on one side of this line, the acceleration vector should be on the other side. How far to the other side is a function of how far the particle is from the destination, and how far the velocity vector is from the line.

particle target initial velocity possible acceleration

Approximate Solution

To codify the approximate solution mentioned above, we'll need some mathematics. Let's label the vector from the particle to the target as \(\vec s\) and the velocity vector as \(\vec v\). These are the inputs to our acceleration function, \(A\). When developing these sorts of functions, I find it helpful to start teasing the equation out of some simplified cases. The simplest case is when the particle is moving directly towards or away from the target:

$$ A(\vec s, c\vec s) = \text{atan2}(\hat s) $$

That is, if velocity is zero or the particle is already moving directly towards or away from the target, whatever equation we come up with should return the unit vector pointed at the target, \(\hat s\).

This implies that our solution will need to know the angle between \(\vec v\) and \(\vec s\). The angle \(\theta\) between two vectors can be found with the formula:

$$ \theta = \arccos \left( \frac{\vec v\cdot\vec s}{|\vec v|\cdot|\vec s|} \right) $$

A little intuition implies that the optimal angle must be in \([0, \pi - \theta]\) on the other side of \(\vec s\).

particle target initial velocity possible acceleration

Note that this is the same diagram as was presented above, but with the additional knowledge of why the range of possible accelerations stops in line with \(\vec v\), at \(\pi - \theta\). It's clear that any angle beyond \(\pi - \theta\) is needlessly introducing a velocity component away from the target.

Let's define \(\phi\) as the angle between the acceleration vector \(\vec a\) and \(\vec s\). According to our observation above, we can define \(\phi_\text{max}\) as \(\pi - \theta\). We need a function that produces smaller \(\phi\) when \(\vec v\) is closer to \(\vec s\). Let's define just the component of velocity we want to cancel, the projection of \(\vec v\) onto \(\vec s_\text{perp}\), a vector perpendicular to \(\vec s\):

$$ \vec s_\text{perp} = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix} \vec s $$

$$ \vec v_\text{bad} = (\vec v \cdot \hat s_\text{perp}) \hat s_\text{perp} $$

With that defined, we want a function that produces smaller \(\phi\) with smaller \(\vec v_\text{bad}\):

$$ \phi = \phi_\text{max}\left(1 - \frac{1}{1 + c |\vec v_\text{bad}|}\right) $$

This definition appears to work pretty well, but it could be more efficient by not braking as hard when farther away from the target.

The function should also produce smaller \(\phi\) when the distance to the target is large. Let's try scaling \(\vec v_\text{bad}\) by \(\frac{1}{|\vec s|}\):

$$ \phi = \phi_\text{max}\left(1 - \frac{1}{1 + c \frac{|\vec v_\text{bad}|}{|\vec s|}}\right) $$

Below are the two strategies at the same time. It can be seen that if there is a significant difference between the paths, the smoother path is typically faster.

I tried a lot of other approximate solutions, but I didn't find any as simple as these that were better in all cases. But why waste too much time with approximation when perfection is achievable?

Exact Solution

Given an initial position, \(\vec p\), initial velocity, \(\vec v\), destination \(\vec d\), and acceleration angle \(\theta\), we can set up a system of equations:

$$ \vec d_x = \vec p_x + \vec v_x t + \frac{1}{2} cos(\theta) t^2 $$

$$ \vec d_y = \vec p_y + \vec v_y t + \frac{1}{2} sin(\theta) t^2 $$

Since this system has two equations and two variables (\(\theta\) and \(t\)), we can solve for both. \(\theta\) is the angle of acceleration, and \(t\) is the time to reach the destination. Unfortunately, the solution one arrives at is a quartic equation. And while a quartic formula does exist, it's a monster compared to your gradeschool quadratic formula — and that's assuming you didn't make a tiny error when doing all of the algebraic manipulation to get there. So let's just be happy knowing that a solution does exist, but use numerical methods to compute the exact result. Below is a comparison between our last approximation we developed above, and the exact solution. We see that the exact solution is an even smoother curve, and frequently much more efficient:

2020-04-05