Optimal control problem (constant magnitude acceleration)

Question

A particle in $\mathbb R^2$ begins at initial position $(x_0, y_0)$ and velocity $(u_0, v_0)$. It must eventually reach a target position $(x_1, y_1)$ and velocity $(u_1, v_1)$.

The acceleration of the particle is a vector of constant magnitude $1$. The only control for this system is the direction of this acceleration, as a (not necessarily continuous) function of time.

What path will bring the particle to the target position and velocity in the least amount of time?

I believe I already have a solution to this problem, but what I'm wondering is: does this problem already have a name? Does the curve? What work has already been done to solve and generalize this problem?

Answer 1

After considering $x = x_1, y = x_3$, given the dynamics $$ \begin{array}{rcl} \dot x_1 & = & x_2\\ \dot x_2 & = & U_0\cos u\\ \dot x_3 & = & x_4\\ \dot x_4 & = & U_0\sin u \end{array} $$

with $|u| = U_0$ we have

$$ H(x,u,\lambda) = \lambda_1 x_2+\lambda_2 U_0\cos u +\lambda_3 x_4+\lambda_4 U_0\sin u $$

from which we obtain the adjoint dynamics

$$ \left\{ \begin{array}{rcl} \dot\lambda_1 & = & 0\\ \dot\lambda_2 & = & -\lambda_1\\ \dot\lambda_3 & = & 0\\ \dot\lambda_4 & = & -\lambda_3 \end{array} \right. \Rightarrow \left\{ \begin{array}{rcl} \lambda_1 & = & c_1\\ \lambda_2 & = & -c_1t+c_2\\ \lambda_3 & = & c_3\\ \lambda_4 & = & -c_3t+c_4 \end{array} \right. $$

and

$$ \frac{\partial H}{\partial u} = -\lambda_2 \sin u +\lambda_4 \cos u = 0 $$

or

$$ \sin u = \frac{\pm\lambda_2}{\sqrt{\lambda_2^2+\lambda_4^2}},\ \ \cos u = \frac{\pm\lambda_4}{\sqrt{\lambda_2^2+\lambda_4^2}} $$

The right sign is found by applying the maximum principle then

$$ \sin u^* = \frac{\lambda_2}{\sqrt{\lambda_2^2+\lambda_4^2}},\ \ \cos u^* = \frac{\lambda_4}{\sqrt{\lambda_2^2+\lambda_4^2}} $$

now according to the transversality conditions

$$ dt_f-\sum_{i=1}^4 \lambda_i f_i \vert_{t_i}^{t_f}dt_f+\sum_{i=1}^4 \lambda_i dx_i \vert_{t_i}^{t_f}dt_f = 0 $$

but at $t = t_i$

$$ \begin{array}{rcl} x_1 & = & x_0\\ x_2 & = & u_0\\ x_3 & = & y_0\\ x_4 & = & v_0\\ \end{array} $$

and at $t = t_f$

$$ \begin{array}{rcl} x_1 & = & x_1\\ x_2 & = & u_1\\ x_3 & = & y_1\\ x_4 & = & v_1\\ \end{array} $$

so a free terminal time requires

$$ 1-\sum_{i=1}^4 \lambda_i f_i \vert_{t_i}^{t_f}=0 $$

the movement reads now

$$ \begin{array}{rcl} \dot x_1 & = & x_2\\ \dot x_2 & = & \frac{(c_4-c_3 t)U_0}{\sqrt{(c_2-c_1 t)^2+(c_4-c_3 t)^2}}\\ \dot x_3 & = & x_4\\ \dot x_4 & = & \frac{(c_2-c_1 t)U_0}{\sqrt{(c_2-c_1 t)^2+(c_4-c_3 t)^2}} \end{array} $$

Now resuming, the movement equations and the adjoint movement equations require $8$ constants plus $t_f$ definition. In theory then can be solved because we have $8$ initial-final conditions plus the transversality condition involving $t_f$

Answer 2

$\begingroup$ $\newcommand{\V}[1]{\mathbf{#1}}$

The Pontryagin's maximum principle helps here to find out the general form of the control. Let $\V S$ be the state vector contains the coordinates of the position vector $\V x$ and velocity vector $\V v$ side by side. So $\V S = (\V x, \V v)$.

The time derivative of $\V S$ is $\dot{\V S} = (\V v, \V a)$. Overdot will denote the time derivative from now.

The running reward is a constant $r = -1$. As the longer the simulation runs the worse it gets.

The constraint is that $\V a \le A$, where $A$ is the magnitude of the acceleration. In your case it's 1, but can be any other constant.

We also have the costate vector $\V P$ of the same type as $\V S$. Let $\V p_1$ and $\V p_2$ correspond to the first and second half of the vector so. $\V P = (\V p_1, \V p_2)$.

The control Hamiltonian is defined as follows:

$$ H(\V S, \V P, r) = \dot{\V S} \cdot \V P + r $$

So in our case:

$$ H = \V p_1 \cdot \V v + \V p_2 \cdot \V a - 1 $$

For a time optimal control $H$ is maximal and is a constant (conserved).

This suggests that the direction of $\V a$ is the same direction as the direction of $\V p_2$ to maximize that dot product.

It also adheres to the equations of the Hamiltonian mechanics:

$$ \dot{\V P} = - \frac{\partial H}{\partial \V S} \\ \dot{\V S} = \frac{\partial H}{\partial \V P} $$

The partial derivative with respect to a vector is a shorthand for the vector formed by the partial derivatives with respect to the elements of that vector. The $H$ doesn't directly depend on the position only the velocity so

$$ \V{\dot P} = \left( \V 0, -\V p_1 \right) $$

By integrating we have the costate:

$$ \V P = \left( \V c_1, \V c_2 - \V c_1 t \right) $$

There $\V c_1$ and $\V c_2$ are constants of integration. So

$$ \V p_2 = \V c_2 - \V c_1 t $$

And as we said before the acceleration points into the direction of this vector so your acceleration is in the form:

$$ \V a = A \frac{\V c_2 - \V c_1 t}{\left| \V c_2 - \V c_1 t \right|} $$

So you can imagine a dot moving along a staright line with constant speed, and the direction of this dot tells you direction to accelerate. In the literature this is often referred to as the "bilinear tangent law" because it's a tangent of an angle when expressed with angles instead of vectors.

Once you have this it's possible integrate this twice to get the general solution for speed and position and write up the non-linear system equations to solve for the constant vector of $\V c_1$ and $\V c_2$.

Solving the resulting non-linear system is difficult. It's discussed the paper: COMPUTING MINIMUM TIME PATHS WITH BOUNDEDACCELERATION And references within.

$\endgroup$