4
$\begingroup$

I have a robot which moves abiding by the following equation: $$ \frac{d^2 \mathbf{x}}{dt} = -k \frac{d\mathbf{x}}{dt} + \mathbf{a}(t), $$ where $\mathbf{x}$ is a coordinate vector. It starts with $$ \frac{d\mathbf{x}}{dt} = v_0,$$ and $\mathbf{x} = (x0, y0, z0)$. I need to find continuous vector valued acceleration function $\|\mathbf{a}(t)\| \leq c$, which gets robot into spot with coordinates $(0,0,0)$ the quickest way possible, i.e. as fast as possible.

I'm not sure how to correctly write my target functional which to minimise.

It seems that my target functional is $$ \frac{\partial \int_{t=0}^{t=\tau}\frac{\mathbf{x}(t)}{dt}dt }{\partial \tau} = 0, $$ where $\frac{\mathbf{x}(t)}{dt}$ computed from solution of original differential equation with optimal $\mathbf{a}(t)$. Because if $\tau$ is optimal, then first derivative with respect to $\tau$ necessary zero. But I'm not sure I've got it right, so I would appreciate a few hints and pointers to the literature.

$\endgroup$
  • $\begingroup$ @WillieWong good catch. I mean quickest, that is as fast as possible. $\endgroup$ – Moonwalker Sep 26 '16 at 16:06
  • 1
    $\begingroup$ Some comments on your problem set up. You are asking for the solution of a shortest time optimal control problem with linear dynamics. This case is completely solved and in particular you cannot expect that the optimal solution is achieved with a continuous control function $a(\cdot)$. Rather the bang-bang principle holds says that optimal solutions (mostly) switch between $c$ and $-c$. Your target function is quite unusual, and I do not know if it is a helpful approach. $\endgroup$ – Fabian Wirth Sep 26 '16 at 19:02
  • 1
    $\begingroup$ I would suggest modifying the question in one or two ways: Relaxing the continuity on $\mathbf{a}(t)$ to be piecewise continuity, or (I prefer) adding a constraint that while $\mathbf{a}(0)$ can be any value satisfying the magnitude constraint,for $t>0$ the "jerk" $\left| \frac{d\mathbf{a}(t)}{dt}\right| \leq J$. $\endgroup$ – Mark Fischler Sep 26 '16 at 19:21
  • $\begingroup$ @FabianWirth: intuitively I see how the bang-bang principle would hold in the case where the norm $\|\cdots \|$ on $\mathbf{a}$ is the $\ell^\infty$ norm. Does it also hold for $\ell^2$? (If so, can I get a reference?) $\endgroup$ – Willie Wong Sep 26 '16 at 19:31
  • 3
    $\begingroup$ Do you want the robot just to pass through the origin quickly or to stop there? Those are two different problems. $\endgroup$ – fedja Sep 26 '16 at 23:36
4
$\begingroup$

Then if the constraint concerns the $L^\infty$ norm, that is, $\forall i \in \{x, y, z\} \leq c$, in each individual direction you have a probelm of a starting velocity, a target endpoint, and a maximum acceleration. You easily solve (for each coordinate) for the time taken to get to that target using the maximal acceleration: this is a matter of simply solving a quadratic equation, using maximum acceleration in the "right" direction. Of those three arrival times, take the longest; that direction will indeed use maximal acceleration. Now for the other two coordinates, fix the arrival time at that longest time, and solve for the necessary acceleration to get home at just that instant; it will in each case be less than the maximum allowed.

So the $L^\infty$ case does not have worries about continuity.

If the constraint is n the $L^2$ sense (that is, $a_x^2+a_y^2+a_z^2 \leq c^2$), then the problem becomes more difficult. First, you can always make a homogeneous linear transformation of variables such that you are trying to travel from $(x_0,0,0)$ to the origin, and indeed there is still a rotation about the $X$ axis degree of freedom left, so that the vector $v_0$ can be considered to lie in the $XY$ plane. These transformations leave the $L^2$ norm constraint unchanged, and turn this into a two-dimensional problem.

I believe the optimal solution to this two-dimensional problem will use a constant acceleration, although this is not so easy to prove. The angle of acceleration is dictated by the requirement that both $x$ and $y$ arrive at zero at the same time; there is in general a unique solution. A bit of algebra arrives at the tangent of the correct angle; again the maximum acceleration magnitude is used, and again there is no continuity worry. Small perturbations about this solution improve one arrival time, at the cost of making the other later, so this is an extremum.

Note that your problem did not say you have to end up stopped at the origin. If it did, you would then run up against the "bang-bang" principle.

$\endgroup$
  • $\begingroup$ Mark Fischer, thank you very much. Could you also suggest a few textbooks on optimal control? $\endgroup$ – Moonwalker Sep 26 '16 at 23:55
1
$\begingroup$

This response is perhaps too late, but... You're looking for the Pontryagin maximum principle applied to minimum time problems. It may be a good idea to look at the extensive set of examples in the canonical and seminal text: Pontryagin, L. S.; Boltyanskii, V. G.; Gamkrelidze, R. V.; Mishchenko, E. F. (1962). The Mathematical Theory of Optimal Processes, Interscience. You need to look for "minimal time" problems in the above text for your answers; the presentation is a bit dated, but the exposition is very detailed and remarkably crisp.

Several later texts are more 'accessible', e.g., the book on Optimal Control by M. Athans and P. Falb. However, be aware that Athans-Falb mostly don't account for the so-called "abnormal multiplier" in their book, except for the proof of the Pontryagin maximum principle; it is important to keep track of the abnormal multiplier at all times, especially in constrained control contexts (such as yours). Modern expositions may be found in D. Liberzon, Calculus of Variations and Optimal Control Theory: A Concise Introduction; there's a preprint version freely available from the author's webpage here: http://liberzon.csl.illinois.edu/publications.html, and Schättler and Ledzewicz, Geometric Optimal Control, http://www.springer.com/la/book/9781461438335.

For your simple control system, it's possible to give a rather complete description of the optimal controls provided that the manoeuvre is feasible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.