This is an ocean vessel path finding algorithm that optimizes fuel consumption and travel time between destinations. We achieve this by combining the locally optimal solution found by the classic Zermelo's Navigation Problem and applies a discretized Jacobi-Newton method for path smoothing and global optimization.

The repository is structured into the following directories:

• /hybrid_routing: where the python code is.

Conveniently, a set of workflows via Github actions are already installed:

• black: Code styling & formatting.

In addition, all docstrings shall be in the numpy format.

This package is purely written in Python and it depends on Scipy, Numpy, and Google's JAX with their dependencies. All packages and dependencies are listed in requirements.txt.

There are two install options, we recommend installing an environment using conda. However it would work with a regular pip install.

• Conda:

  conda env create -f environment.yml --force

  Make sure to activate the conda environment once installation is finished.

• Pip:

  pip install -r requirements.txt
  pip install -e .[dev]

you can also use make install.

The difference between conda and pip is that conda will create an isolated environment while pip will install all the dependencies in the current Python env. This might be a conda environment or any other Python env created by other tools. If you already have the dependencies installed, you can update it to reflect the last version of the packages in the requirements.txt with pip-sync.

If JAX is not using GPU, the following message will appear:

WARNING:absl:No GPU/TPU found, falling back to CPU. (Set TF_CPP_MIN_LOG_LEVEL=0 and rerun for more info.)

To solve it, install the following dependencies in the environment:

conda install -c anaconda cudatoolkit
conda install -c anaconda cudnn
pip install -U jaxlib==0.3.14+cuda11.cudnn82 -f https://storage.googleapis.com/jax-releases/jax_cuda_releases.html
conda install -c nvidia cuda-nvcc

If the following error appears:

cuLinkAddData fails. This is usually caused by stale driver version.
The CUDA linking API did not work. Please use XLA_FLAGS=--xla_gpu_force_compilation_parallelism=1 to bypass it, but expect to get longer compilation time due to the lack of multi-threading.

You can fix it by running:

pip install --upgrade "jax[cuda]" -f https://storage.googleapis.com/jax-releases/jax_cuda_releases.html

This will raise an ERROR telling that the package hybrid_routing is no longer compatible. Ignore that.

Add abstract dependency to setup.py. If neccessary, add version requirements but try to be as flexible as possible

• Update requirements.txt: pip-compile --extra dev > requirements.txt
• Update environment: pip-sync

The library is structured as follows.

The module hybrid_routing.vectorfields contains all the different Vectorfield classes used in our study. Each Vectorfield implements a synthetic field of sea currents.

Sample code to use vectorfields:

from hybrid_routing.vectorfields import Circular

# Initialize the vectorfield
vectorfield = Circular()

# Get the current velocity (u, v) at point (x, y)
# x = longitude, y = latitude
x, y = 0.5, 0.2
# u = velocity vector component parallel to longitude
# v = velocity vector component parallel to latitude
u, v = vectorfield.get_current(x, y)

# Plot the vectorfield
vectorfield.plot()

Here is the expected plot output:

The module hybrid_routing.jax_utils implements all the functions to optimize a route by using JAX.

Example and set up of optimize_route:

  from hybrid_routing.jax_utils.optimize import optimize_route
  from hybrid_routing.vectorfields import NoCurrent
  import numpy

  # We must provide the following parameters:
  #   vectorfield, (x_start, y_start), (x_end, y_end)

  vectorfield = NoCurrent()
  x_start, y_start = 0, 0
  x_end, y_end = 10, 10

  # The following parameters are optional, but we recommend
  # you test them out:
  #   time_iter, time_step, angle_amplitude,
  #   num_angles, vel, dist_min

  time_iter, time_step = 5, 0.5
  angle_amplitude, num_angles = np.pi/2, 6
  vel, dist_min = 2.5, 1

  # invoking optimize route function:
  list_routes = optimize_route(
    vectorfield, 
    x_start, y_start, 
    x_end, y_end, 
    time_iter = time_iter, time_step = time_step, 
    angle_amplitude = angle_amplitude, num_angles = num_angles, 
    vel = vel, dist_min = dist_min)

  # "list_routes" contains all paths as entries orginates
  # from (x_start, y_start), each entry is a list of points
  # (x, y, theta). It has the same length as time_iter / 
  # time_step, and there are "num_angles" amount of entries.
  # The path that brings us closest to (x_end, y_end) is
  # the first entry, as we are printing below:
  print(list_routes[0])

The diagram below illustrates the setup:
(x0, y0) = (x_start, y_start),
(xN, yN) = (x_end, y_end).

---SECTION UNDER CONSTRUCTION---

The module hybrid_routing.web contains the utils used to deploy our demo. You can learn more about this in our demo section.

With the hybrid-routing environment active, you can initialize the web application by running the following command:

streamlit run hybrid_routing/demo.py --server.port 8501

The demo will start at port 8501 (you can change the port to anyone you prefer). Then you can access the web in your PC by going to [https://localhost:8501]

Robert Milson - [email protected]

Project link: https://github.com/daniprec/hybrid_ivp

• Daniel Precioso
• Robert Milson
• Louis Bu
• Zermelo Navigation Problem
• Parallel iterative methods for variational integration applied to navigation problems
• Google: JAX