# The Double Integrator: Matching velocity and position as quickly as possible with only a limited amount of force available

If a body with mass $m$ begins at position $x_0$ with velocity $v_0$ and experiences a force that varies as a function of time $f(t)$ (and we ignore gravity, friction, and everything else that might complicate matters), then we can compute the position and velocity of the body at any time:

$$v(t) ~= ~\int\limits_0^t \frac{f(t)}{m}\mathrm{d}t+v_0,$$ and $$x(t) = \int\limits_0^t\int\limits_0^t \frac{f(t)}{m}\mathrm{d}t+v_0\mathrm{d}t+x_0.$$

Now, if we have another body of the same mass that starts off at position $\hat{x}_0$ with velocity $\hat{v}_0$ and we want to apply a force, $\hat{f}(t)$, in order to match the first body's trajectory (position and velocity) as quickly as possible subject to the constraint that $|\hat{f}(t)|\le \mathrm{fmax}$.

What are the tools that I need to solve this?

-

Let us reformulate the question(v1) as a 1D kinematic mouse-and-cat optimal control problem. The masses are irrelevant for the kinematic problem and hence put to

$$m~=~1.$$

1) Consider first the cat. The goal for the cat is to obtain the position and velocity(!) of the mouse as quickly as possible. The cat can accelerate

$$|a|~\leq~ a_{0},$$

where $a_{0}>0$ is a maximal acceleration. (Update: This type of problem is in optimal control theory known as a double integrator. See also the textbook by H.P. Geering, Optimal Control with Engineering Applications, Springer, 2007, Section 2.1.4.) We want to show that, ideally speaking, there is an optimal strategy so that the acceleration of the cat is at all times either the maximally allowed or none,

$$a(t)~\in~\left\{ -a_0,0 , a_0 \right\},$$

i.e., the control parameter $a$ has the bang-bang property.

Let us define a signed kinetic energy

$$K~:=~\frac{mv|v|}{2}~=~\frac{v|v|}{2}~=~T ~{\rm sgn}(v), \qquad \qquad T~:=~\frac{mv^2}{2}~=~\frac{v^2}{2}~=~|K| .$$

It is convenient to consider a $(x,K)$ coordinate system. One may view it as a configuration space (or phase space) of the system, because the map $v \leftrightarrow K$ is a bijection: $\mathbb{R}\to\mathbb{R}$. In particular, one may plot the trajectories of the cat and the mouse in a $(x,K)$ diagram. From the work energy theorem, the slope of the trajectory is (up to a sign) the acceleration

$$a~=~ma~=~\frac{dT}{dx}~=~ \frac{dK}{dx} {\rm sgn}(v) .$$

Thus the cat in initial state $(x_0,K_0)$ must proceed within a cone $C(x_0,K_0)$ as indicated in red in Figures 1, 2 and 3. The cat can exit the cone $C(x_0,K_0)$ through the $x$-axis $K=0$ only, and turn around, in order to reach a final state $(x,K)$ outside the cone.

$\uparrow$ Figure 1. Case $K_0>0$. The red region denotes the cone $C(x_0,K_0)$. The black oriented paths indicate optimal strategies for the cat to reach 3 different final states $(x,K)$.

$\uparrow$ Figure 2. The cone $C(x_0,K_0)$ marked with red in the case $K_0=0$.

$\uparrow$ Figure 3. The cone $C(x_0,K_0)$ marked with red in the case $K_0<0$.

In mathematical detail, the cone $C(x_0,K_0)$ is

$$C(x_0,K_0)~:=~\left\{ \begin{array}{lcc} C_{+}(x_0,K_0)&{\rm for}& K_0>0, \cr\cr C_{+}(x_0,K_0)\cup C_{-}(x_0,K_0)&{\rm for}& K_0=0,\cr\cr C_{-}(x_0,K_0)&{\rm for}& K_0<0, \end{array} \right.$$

where we have defined the positive and negative cones as

$$C_{\pm}(x_0,K_0)~:=~ \left\{(x,K)\in\mathbb{R}^2 \mid \pm a_0 (x-x_0) \geq |K-K_0| \wedge \pm K\geq 0\right\} .$$

For the cat to go from state $(x_0,K_0)$ to state $(x,K)$, there is an optimal strategy that leads to minimal time consumption $\tau(x,K;x_0,K_0)$, which we have tried to indicate in Figure 1. Roughly speaking, the cat should choose a route as far away from the $x$-axis $K=0$ as possible, as it is most costly in terms of time to have small speed. If the final state $(x,K) \in C(x_0,K_0)$ is in the cone, then two legs are needed (one maximal acceleration and one maximal de-acceleration). It is straightforward to calculate that the minimal time consumption $\tau(x,K;x_0,K_0)$ for $(x,K) \in C(x_0,K_0)$ is

$$\tau(x,K;x_0,K_0) ~=~ \frac{2\sqrt{|K|+|K_0|+a_0|x-x_0|} -\sqrt{2|K|}-\sqrt{2|K_0|}}{a_0} .$$

There are similar expressions for $\tau(x,K;x_0,K_0)$ in various cases where $(x,K) \notin C(x_0,K_0)$ but with more legs/terms, which we will leave as an exercise to determine.

2) Next consider the mouse. Let us assume that the full future trajectory of the mouse $t\mapsto x_1(t)$, $t\geq 0$, is known to an all-knowing cat. (There are other possible rules of the game, but this setup seems to be closest to what OP is after.) Let the velocity and the signed kinetic energy of the mouse be denoted

$$v_1(t)~=~\frac{dx_1}{dt} \qquad {\rm and}\qquad K_1(t)~=~\frac{v_1(t)|v_1(t)|}{2},$$

respectively. For each future time $t\geq 0$, define the difference

$$\Delta\tau(t)~:=~ \tau\left(x_1(t),K_1(t);x_0,K_0\right) - t$$

between the time the cat could be at the mouse state $(x_1(t),K_1(t))$ (if the cat made a run for it), and the time $t$ the mouse would be there. If the two initial states of cat and mouse are different,

$$(x_0,K_0)~\neq~(x_1(t=0),K_1(t=0)),$$

then $\Delta\tau(t=0)>0$. The first instant $t_*$ that the cat can obtain the $(x,K)$ state of the mouse is the first time that $\Delta\tau(t)$ turns non-positive,

$$t_*~=~\inf \left\{ t\in \mathbb{R}_+ \mid \Delta\tau(t) \leq 0 \right\}.$$

This is the answer to how quickly the cat can obtain the position and velocity of the mouse.

-
Perfect. Thanks. It seems unintuitive that a bang-bang strategy would be optimal, but what you've illustrated makes sense. It's also interesting how the critical damping co-efficient of $\zeta=1$ is built into the configuration space as a slope of $\pm 1$. – JCooper Jan 24 '12 at 5:15

In fact you can find two physical analogies here that can explain my answer

1. In a spring, the restoring force is proportional to the deflection from the equilibrium. With some damping along the way, it will eventually take the initial position.

2. In particle dynamics (consider Stokes drag), the drag force of a particle in a viscous fluid is proportional to the velocity difference between particle and fluid. In the end, the particle will adjust to the liquid velocity.

If you combine both ideas, then the force

$\hat{f}(t)=f(t)+\alpha\Big(\hat{x}(t)-x(t)\Big)+\beta\Big(\hat{v}(t)-v(t)\Big)$

should in principle do what you want (you can always add your constraint as a limiter of course). Actually, the term in the velocity difference will act as the damping term for the position difference term.

Your question also includes as quickly as possible. This can be done by smartly choose the coefficients $\alpha$ and $\beta$. These can chosen dynamically: e.g. be a function of the velocity and position differences. For that, you should familiarize yourself with terms as critical damping and relaxation times.

-