In mathematical optimization, Zermelo's navigation problem, proposed in 1931 by Ernst Zermelo, is a classic optimal control problem that deals with a boat navigating on a body of water, originating from a point
to a destination point
. The boat is capable of a certain maximum speed, and the goal is to derive the best possible control to reach
in the least possible time.
Zermelo Navigation with velocity
![\mathbf {v}](https://wikimedia.org/api/rest_v1/media/math/render/svg/35c1866e359fbfd2e0f606c725ba5cc37a5195d6)
under constant wind
![\mathbf {w}](https://wikimedia.org/api/rest_v1/media/math/render/svg/20795664b5b048744a2fd88977851104cc5816f8)
Without considering external forces such as current and wind, the optimal control is for the boat to always head towards
. Its path then is a line segment from
to
, which is trivially optimal. With consideration of current and wind, if the combined force applied to the boat is non-zero the control for no current and wind does not yield the optimal path.
History[]
In his 1931 article,[1] Ernst Zermelo formulates the following problem:
In an unbounded plane where the wind distribution is given by a vector field as a function of position and time, a ship moves with constant velocity relative to the surrounding air mass. How must the ship be steered in order to come from a starting point to a given goal in the shortest time?
Ernst Zermelo formulated and solved the general problem
This is an extension of the classical optimisation problem for geodesics –
minimising the length of a curve
connecting points
and
, with the added complexity of considering some wind velocity. Although it is usually impossible to find an exact solution in most cases, the general case was solved by Zermelo himself in the form of a partial differential equation, known as Zermelo's equation, which can be numerically solved.
The problem of navigating an airship which is surrounded by air, was presented first in 1929 at a conference by Ernst Zermelo. Other mathematicians have answered the challenge over the following years. The dominant technique for solving the equations is the calculus of variations.[2]
Constant-wind case[]
The case of constant wind is easy to solve exactly.[3]
Let
, and suppose that to minimise the travel time the ship
travels at a constant maximum speed
. Thus the position of the ship at
time
is
. Let
be the time of arrival at
, so that
. Taking the dot product of this with
and
respectively results in
and
. Eliminating
and writing this system as a quadratic in
results in
. Upon solving this, taking the positive square-root since
is positive, we obtain
![{\displaystyle {\begin{aligned}T[\mathbf {d} ]&={\frac {-2(\mathbf {d} \cdot \mathbf {w} )\pm {\sqrt {4(\mathbf {d} \cdot \mathbf {w} )^{2}+4\mathbf {d} ^{2}(\mathbf {v} ^{2}-\mathbf {w} ^{2})}}}{2(\mathbf {v} ^{2}-\mathbf {w} ^{2})}}\\[8pt]&={\sqrt {{\frac {\mathbf {d} ^{2}}{\mathbf {v} ^{2}-{\vec {w}}^{2}}}+{\frac {(\mathbf {d} \cdot \mathbf {w} )^{2}}{({\vec {v}}^{2}-{\vec {w}}^{2})^{2}}}}}-{\frac {\mathbf {d} \cdot \mathbf {w} }{\mathbf {v} ^{2}-\mathbf {w} ^{2}}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11b484d95059b967bd52066dde8f42f6160db03f)
Claim: This defines a metric on
, provided
.
Proof[]
By our assumption, clearly
with equality if and only if
. Trivially if
, we have
. It remains to show
satisfies a triangle inequality
Indeed, letting
, we note that this is true if and only if
![{\displaystyle {\begin{aligned}&{\sqrt {{\frac {(\mathbf {d} _{1}+\mathbf {d} _{2})^{2}}{c^{2}}}+{\frac {(({\vec {d}}_{1}+{\vec {d}}_{2})\cdot {\vec {w}})^{2}}{c^{4}}}}}-{\frac {(\mathbf {d} _{1}+\mathbf {d} _{2})\cdot \mathbf {w} }{c^{2}}}\\[8pt]\leq {}&{\sqrt {{\frac {\mathbf {d} _{1}^{2}}{c^{2}}}+{\frac {(\mathbf {d} _{1}\cdot \mathbf {w} )^{2}}{c^{4}}}-{\frac {\mathbf {d} _{2}\cdot \mathbf {w} }{c^{2}}}}}+{\sqrt {{\frac {\mathbf {d} _{2}^{2}}{c^{2}}}+{\frac {(\mathbf {d} _{2}\cdot \mathbf {w} )^{2}}{c^{4}}}}}-{\frac {\mathbf {d} _{2}\cdot \mathbf {w} }{c^{2}}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d69695249c3decdfff95770694a975ea10adc0f2)
if and only if
![{\displaystyle {\frac {\mathbf {d} _{1}\cdot \mathbf {d} _{2}}{c^{2}}}+{\frac {(\mathbf {d} _{1}\cdot \mathbf {w} )(\mathbf {d} _{2}\cdot \mathbf {w} )}{c^{4}}}\leq \left[{\frac {{\vec {d}}_{1}^{2}}{c^{2}}}+{\frac {(\mathbf {d} _{1}\cdot \mathbf {w} )^{2}}{c^{4}}}\right]^{1/2}\left[{\frac {{\vec {d}}_{2}^{2}}{c^{2}}}+{\frac {(\mathbf {d} _{2}\cdot \mathbf {w} )^{2}}{c^{4}}}\right]^{1/2},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0de02e0a7ff01055f06e0cf0c8e62230c8c61148)
which is true if and only if
![{\displaystyle {\frac {(\mathbf {d} _{1}\cdot \mathbf {d} _{2})^{2}}{c^{4}}}+{\frac {2(\mathbf {d} _{1}\cdot \mathbf {d} _{2})(\mathbf {d} _{1}\cdot \mathbf {w} )(\mathbf {d} _{2}\cdot \mathbf {w} )}{c^{6}}}\leq {\frac {\mathbf {d} _{1}^{2}\cdot \mathbf {d} _{2}^{2}}{c^{4}}}+{\frac {\mathbf {d} _{1}^{2}(\mathbf {d} _{2}\cdot \mathbf {w} )^{2}+\mathbf {d} _{2}^{2}(\mathbf {d} _{1}\cdot \mathbf {w} )^{2}}{c^{6}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/69210e1d7ef51b089a8cc03e9949bd8eb1be975f)
Using the Cauchy–Schwarz inequality, we obtain
with equality if and only if
and
are linearly dependent, and so the inequality is indeed true.
Note: Since this is a strict inequality if
and
are not linearly dependent, it immediately follows that a straight
line from
to
is always a faster path than any other path made up of straight line segments. We use a limiting argument to prove this is true for
any curve.
General solution[]
Consider the general example of a ship moving against a variable wind
. Writing this component-wise, we have the drift in the
-axis as
and the drift in the
-axis as
. Then for a ship moving at maximum velocity
at variable heading
, we have
![{\displaystyle {\begin{aligned}{\dot {x}}&=V\cos \theta +u(x,y)\\{\dot {y}}&=V\sin \theta +v(x,y)\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b04492444f6479e34b3b6bc3f43b49fd0d89e4c6)
The Hamiltonian of the system is thus
![{\displaystyle H=\lambda _{x}(V\cos \theta +u)+\lambda _{y}(V\sin \theta +v)+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8609901912a075fa42347489f0b4d7b8ac05aa7d)
Using the Euler–Lagrange equation, we obtain
![{\displaystyle {\begin{aligned}{\dot {\lambda }}_{x}&=-{\frac {\partial H}{\partial x}}=-\lambda _{x}{\frac {\partial u}{\partial x}}-\lambda _{y}{\frac {\partial v}{\partial x}}\\{\dot {\lambda }}_{y}&=-{\frac {\partial H}{\partial y}}=-\lambda _{x}{\frac {\partial u}{\partial y}}-\lambda _{y}{\frac {\partial v}{\partial y}}\\0&={\frac {\partial H}{\partial \theta }}=V(-\lambda _{x}\sin \theta +\lambda _{y}\cos \theta )\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05eb57441aa38b3c4211d38c54b8ced257655a97)
The last equation implies that
. We note that the system is autonomous; the Hamiltonian does not depend on time
, thus
= constant, but since we are minimising time, the constant is equal to 0. Thus we can solve the simultaneous equations above to get[4]
![{\displaystyle {\begin{aligned}\lambda _{x}&={\frac {-\cos \theta }{V+u\cos \theta +v\sin \theta }}\\[6pt]\lambda _{y}&={\frac {-\sin \theta }{V+u\cos \theta +v\sin \theta }}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/36a53c6ae1e31b2d5c2660d184393971dc83e827)
Substituting these values into our EL-equations results in the differential
equation
![{\displaystyle {\frac {d\theta }{dt}}=\sin ^{2}\theta {\frac {\partial v}{\partial x}}+\sin \theta \cos \theta \left({\frac {\partial u}{\partial x}}-{\frac {\partial v}{\partial y}}\right)-\cos ^{2}\theta {\frac {\partial u}{\partial y}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a97d9eb2ddc44e5fdd78dd8f84bf32ac0e21c33f)
This result is known as Zermelo's equation. Solving this with our system allows us to find the general optimum path.
Constant-wind revisited example[]
If we go back to the constant wind problem
for all time, we have
![{\displaystyle {\frac {\partial v}{\partial y}}={\frac {\partial v}{\partial x}}={\frac {\partial u}{\partial x}}={\frac {\partial u}{\partial y}}=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f035f72f30bd98d2ec7f3231e15c528141384da9)
so our general solution implies
, thus
is constant,
i.e. the optimum path is a straight line, as we had obtained before with an
algebraic argument.
References[]