PaperlayerView exact revision on arXiv

Source-linked AI summary

Zermelo's problem: Optimal point-to-point navigation in 2D turbulent flows using Reinforcement Learning

Luca Biferale, Fabio Bonaccorso, Michele Buzzicotti, Patricio Clark Di Leoni, Kristian Gustavsson

arXiv:1907.08591v2nlin.CDcs.AIcs.LGcs.SYeess.SYphysics.flu-dyn

TL;DR

Zermelo’s problem asks how to navigate between two points in a flow in the shortest time, a challenge for directing probes to specific locations. This paper applies actor-critic Reinforcement Learning to vessels with fixed-magnitude, variable-direction slip in turbulent flows and compares frozen-flow policies with Optimal Navigation. RL finds quasi-optimal paths in frozen and evolving flows, with robust policies that can exploit flow structure.

  • Problem

    Time-optimal navigation through a flow is challenging when probes must reach specific locations, while moving sensors may drift away from key points.

    Source: §I · p. 1

  • Method

    The paper applies Reinforcement Learning to steer vessels with fixed-intensity, variable-direction slip through static and evolving 2D turbulent flows, comparing frozen-flow policies with Optimal Navigation.

    Source: §I · pp. 1–2, §II · p. 3

  • Results

    RL finds quasi-optimal paths in frozen and chaotically evolving turbulent flows, with robust policies that use flow features and remain effective when slip speed is small.

    Source: §I · p. 2, B. Results (time-independent flows) · p. 6, C. Results (time-dependent flows) · p. 8

  • Takeaways & Limitations

    Learned policies can use flow structure to reach targets and are reported as more robust than Optimal Navigation under small initial-condition disturbances.

    Source: §I · p. 2

Abstract

from arXiv · show

To find the path that minimizes the time to navigate between two given points in a fluid flow is known as Zermelo's problem. Here, we investigate it by using a Reinforcement Learning (RL) approach for the case of a vessel which has a slip velocity with fixed intensity, Vs , but variable direction and navigating in a 2D turbulent sea. We show that an Actor-Critic RL algorithm is able to find quasi-optimal solutions for both time-independent and chaotically evolving flow configurations. For the frozen case, we also compared the results with strategies obtained analytically from continuous Optimal Navigation (ON) protocols. We show that for our application, ON solutions are unstable for the typical duration of the navigation process, and are therefore not useful in practice. On the other hand, RL solutions are much more robust with respect to small changes in the initial conditions and to external noise, even when V s is much smaller than the maximum flow velocity. Furthermore, we show how the RL approach is able to take advantage of the flow properties in order to reach the target, especially when the steering speed is small.

I. INTRODUCTION

The paper studies time-optimal point-to-point navigation through complex 2D turbulent flows, where moving probes can be hard to direct to specific locations. It applies Reinforcement Learning (RL) and compares it with Optimal Navigation (ON), emphasizing robustness and the use of flow structure.

I. INTRODUCTION

  • Path planning for small autonomous marine vehicles is relevant to geophysical and engineering applications, where vessels face environmental disturbances including ocean currents, waves, and wind.These disturbances may compete and evolve chaotically.Source: §I · p. 1
  • Robust navigation matters for moving probes, which can drift away from key locations and are used when fixed platforms or manned vessels are not economically viable.The paper connects this motivation to optimizing data assimilation and to Zermelo’s time-optimal point-to-point navigation problem.Source: §I · p. 1
  • RL finds quasi-optimal paths in multi-scale 2D turbulent flows, and the paper compares its policies with Optimal Navigation (ON).The study covers frozen and chaotically evolving flows.Source: §I · pp. 1–2
  • The study addresses a gap in work on Optimal Navigation and RL, which had mainly considered simple advecting flows.Prior RL applications also included particle navigation in vortex, Taylor Green, and ABC flows, as well as animal-motion tasks.Source: §I · p. 2
  • RL policies are reported to remain stable under small initial-condition disturbances and to succeed when slip speed is much lower than the guiding flow.The paper also reports that RL can use features of the flow to reach the target.Source: §I · p. 2

II. PROBLEM SET-UP

The setup defines two shortest-time navigation tasks in a static 2D turbulent snapshot, with vessels steered by a fixed-magnitude slip velocity. It also presents the continuous ON steering rule for frozen flows and explains why that rule may be unstable over practical navigation times.

II. PROBLEM SET-UP

  • The study seeks shortest-time routes between two pairs of start and target regions in one static snapshot of 2D turbulence.These tasks are named P1 and P2.Source: §II · p. 3
  • Each vessel’s motion combines the advecting flow velocity with a control slip velocity of fixed intensity and variable direction.The steering angle is evaluated along the trajectory, and slip speed is scaled by the maximum flow speed.Source: §II · p. 3
  • For time-independent or sufficiently slowly evolving flows, continuous Optimal Navigation specifies a time-evolution equation for the steering angle.The rule depends on spatial derivatives of the flow velocity along the vessel trajectory.Source: §II · p. 3
  • The ON equations can produce chaotic dynamics even in a 2D time-independent flow, making the protocol practically unstable when finite-time growth persists through a navigation interval.The authors note that sensitivity to small errors can make ON unusable for practical applications in such cases.Source: §II · p. 3

A. Methods

The method trains a vessel-agent through repeated interactions with a discretized flow environment, using a one-step actor-critic algorithm and a shaped reward tied to travel time and target distance. Randomized starting positions and a softmax policy support learning across nearby conditions.

A. Methods

  • Training iterates over episodes in which the agent samples states, takes actions, collects rewards, and updates its policy toward higher total reward.Each episode begins with the policy produced at the end of the previous one.Source: A. Methods · p. 3
  • The vessel is the agent, flow tiles define its states, and eight steering angles are available at discrete time intervals.The setup uses 900 square tiles of size δ × δ and terminates episodes at a maximum time.Source: A. Methods · pp. 3–4
  • The shaped reward penalizes elapsed time and rewards progress toward the target, with the summed return approximately tracking time saved relative to travel without a flow.Episodes end on reaching the target region, exceeding the time limit, or moving far from the target; failures incur an extra negative reward.Source: A. Methods · p. 4
  • Episodes begin at uniformly randomized positions near the start, while a softmax policy maps state-action parameters to stochastic steering choices.The state-action feature matrix uses a non-overlapping tiling of the action-state space.Source: A. Methods · p. 4
  • A one-step actor-critic method estimates future reward with a learned state-value function and updates policy and value parameters during training.Its one-step return supports local-in-time gradient updates, with learning rates following Adam.Source: A. Methods · p. 4

B. Results (time-independent flows)

In time-independent turbulent flows, RL learns stable, efficient routes that adapt to the flow, especially when vessel slip speed is low. The learned policies outperform a direct-to-target policy at low slip speeds and explore beyond the shortest paths.

Training convergence

  • After 2,500 episodes, the P1 policy reaches a stable maximum reward, with total reward rising from approximately −300 at 200 episodes to approximately −8.The inset evaluates policies at 200, 500, and 2,500 episodes; the final policy produces stable, short paths between A1 and B1.Source: B. Results (time-independent flows) · p. 5, Figure 2 · p. 5

Flow-informed routes

Exploration and policy structure

  • Training explores regions beyond the optimal trajectory; the final policy is nearly deterministic near that route and becomes more random farther away.The state-visit maps show broad exploration around the optimal path, while the greediness maps indicate how action probabilities vary with distance from it.Source: Figure 5 · p. 5, B. Results (time-independent flows) · pp. 6–7

Comparison with the trivial policy

  • Compared with RL, the trivial policy often fails at low slip: vessels get trapped, and P2 succeeds only at ˜Vs = 1.The trivial policy chooses the action pointing most directly toward the target; RL actions show a persistent angle mismatch with it.Source: Figure 6 · p. 6, B. Results (time-independent flows) · p. 7

C. Results (time-dependent flows)

The authors test navigation in a time-dependent 2D turbulent flow and find that RL clearly outperforms the trivial policy. The learned policy uses favorable flow structures and avoids those that would carry vessels away from the target.

C. Results (time-dependent flows)

  • For the time-dependent 2D turbulent flow, the evaluation presents arrival-time distributions comparing reinforcement learning (RL) with the trivial policy (TP), using propelling velocity ˜Vs = 0.2.Source: C. Results (time-dependent flows) · p. 7, Figure 9 · p. 8
  • RL clearly outperforms the trivial policy in the time-dependent turbulent flow, as in the time-independent case.The authors conclude that RL converges on quasi-optimal navigation policies even with spatiotemporal chaos.Source: C. Results (time-dependent flows) · p. 8
  • The RL policy exploits favorable flow structures to accelerate toward the target and avoids structures that would carry vessels away.In contrast, the trivial policy can be trapped in or accelerated by vortical structures without regard to their effect on progress.Source: C. Results (time-dependent flows) · p. 8

IV. THE OPTIMAL NAVIGATION APPROACH

The paper applies the Optimal Navigation approach only to time-independent flows, where the problem can be solved analytically. It implements the approach proposed in Ref..

IV. THE OPTIMAL NAVIGATION APPROACH

  • The Optimal Navigation approach is examined only for time-independent flow, because the problem can then be solved analytically.Source: §IV · p. 8
  • The authors implement the approach proposed in Ref. for the time-independent case shown in Fig. 1.Source: §IV · p. 8

A. Methods

For frozen or slowly evolving flows, the methods derive a continuous steering strategy from optimal control and Hamiltonian dynamics. The section also notes that nonlinear-flow instability makes finding the globally optimal initial direction difficult.

A. Methods

  • The continuous optimal-control strategy specifies how the steering angle must evolve to minimize travel time, given an optimal initial angle.The paper obtains the strategy by mapping navigation to classical mechanics and solving the resulting Hamiltonian dynamics.Source: A. Methods · p. 8
  • The Hamiltonian dynamics orient vessels transverse to maximal stretching directions, so they avoid high-strain regions and accumulate in vortices.Source: A. Methods · p. 8
  • The optimal path is the quickest trajectory among the family of Zermelo problems defined by points in the target area.Each target point corresponds to a problem with its own optimal initial angle and travel time.Source: A. Methods · p. 9
  • In nonlinear flow, nearby initial angles can lead to different destinations, making local refinement prone to local rather than global minima.Source: A. Methods · p. 9

B. Results

The Optimal Navigation (ON) protocol can produce target-reaching trajectories, but its successes are intermittent across initial angles and sensitive to perturbations over navigation times. A representative RL trajectory, by contrast, takes advantage of strong-flow regions to reach the target earlier than the trivial policy.

B. Results

  • At ˜Vs = 0.2, 100 uniformly gridded ON trajectories for P2 all missed the target, while 10,000 trials produced only a few arrivals.The authors then sampled initial angles in an interval of length π/2500 around the quickest observed arrival.Source: B. Results · p. 9
  • A representative RL trajectory uses strong-flow regions to reach the target earlier than the trivial-policy trajectory.The figure compares kinetic energy along the two trajectories and shows the cosine of the angle difference between the vessel's navigation direction and the flow direction.Source: Figure 11 · p. 10
  • Success and failure alternate across initial angles, and some sampled trajectories arrive faster than θON, but continuous refinement from θON encounters failure regions.The arrival-time and angle outcomes therefore do not vary smoothly with the initial angle.Source: B. Results · p. 10
  • The maximal finite-time Lyapunov exponent is positive throughout target-reaching times for all tested slip velocities, indicating ON trajectories are unstable to small perturbations on that horizon.The paper concludes that this instability makes ON untractable for practical applications.Source: B. Results · p. 10

V. COMPARISON BETWEEN RL AND ON

RL and ON achieve similar best arrival times, but RL is substantially more robust: ON has a wider tail of long arrivals and more failures. The comparison shows coherent RL trajectories versus ON trajectories that disperse broadly.

V. COMPARISON BETWEEN RL AND ON

  • The comparison gives ON a narrow initial-angle interval around θON, while RL starts within a spatial circle and uses a small spread in initial angles.ON cannot use the wider starting box of side dAi = 0.2 because its dynamics are unstable over that range.Source: §V · p. 10
  • 14% of trajectories initialized within θON ± π/5000 reach the target; the figure also plots arrival time against initial angle, with zero marking failures.Figure 12 identifies the quickest trajectory among 10,000 as defining θON ≈ 2.4193 for Vs = 0.2 and P2.Source: §V · p. 11, Figure 12 · p. 11
  • RL trajectories follow a coherent spatial region, whereas ON trajectories spread almost uniformly, especially at larger navigation speeds.At small navigation speeds, many ON trajectories approach regular attractors.Source: §V · p. 11
  • ON’s best arrival time is comparable to, or sometimes slightly smaller than, RL’s, but ON has a wider tail of long arrivals and many more failures.The arrival-time distributions therefore indicate greater RL robustness despite similar best-case performance.Source: §V · pp. 10–11

VI. CONCLUSIONS

The conclusions report quasi-optimal, robust RL navigation in 2D turbulent flows, including at low vessel speeds, and contrast its stability with ON in frozen flows. They also note that flow-evolution information and a separate optimization for each flow and endpoint pair are required.

VI. CONCLUSIONS

  • The actor-critic RL approach finds quasi-optimal discretized navigation policies with strong robustness to changes in initial conditions in realistic 2D turbulent flow.In frozen flow, the comparison with ON finds strong ON sensitivity to initial conditions, making it inadequate for real-world applications.Source: §VI · p. 11
  • Vs down to ∼0.2 umax yields quick, close-to-optimal paths that differ strongly from always steering directly toward the target.The conclusions also report that RL found solutions in attempts with additive noise, with results deferred to elsewhere.Source: §VI · p. 11
  • The authors relate optimal paths to the flow’s topological properties and identify coherent structures as guides toward the target.They describe the learned information as non-trivial.Source: §VI · p. 11
  • The implemented RL approach requires information about flow evolution for the full navigation duration, and each flow evolution and endpoint pair requires individual optimization.The authors say a model must provide the flow information for realistic travel planning.Source: §VI · p. 11
  • Finding a minimum-time path requires repeated trials; the proposed online extension applies only if the objective is changed to reaching the target, not minimizing travel time.The authors identify 3D geometries and inertial-particle navigation as future directions.Source: §VI · p. 12

VII. SUPPLEMENTARY MATERIAL

The supplementary material includes a movie comparing RL and trivial-policy trajectories in a time-dependent 2D turbulent flow.

VII. SUPPLEMENTARY MATERIAL

  • A supplementary movie shows side-by-side trajectory evolution under the optimal RL and trivial policies in a time-dependent 2D turbulent flow.The movie compares two trajectory groups over time.Source: §VII · p. 12
Loading 1907.08591v2…