Continuous progress on developing ever better, safer and more autonomous cyber-physical systems has brought the need for efficient and optimal automatic decision making. Long-range mission drones especially, whether flying in atmospheric wind fields or diving in oceanic currents, are faced with the challenge to optimally plan the route they follow to fulfill their mission in a highly dynamic, unfavorable and uncertain environment, on space scales of hundreds or thousands of kilometers and on time windows spanning tenths of hours or several days.

In this thesis, solving such routing problems for long-range airborne or underwater vehicles is the main focus. The routing problems tackled consist in traveling optimally from a given point to a destination in a strong, unsteady and uncertain flow field, in the presence of diffuse hazard and strictly forbidden zones, with key metrics being travel time, spent energy or exposure to hazard. The considered environment geometries are either the planar 2D space or the Earth’s 2D spherical space. The methods at stake are indirect methods, whether using extremals from Pontryagin’s Maximum Principle or solving numerically a relevant Hamilton-Jacobi-Bellman equation.

First, the properties of an extremal-based algorithm to compute time-optimal trajectories in an unsteady and possibly strong flow field are studied. In given applications cases, similar existing algorithms from the literature are shown to reach their limit. Improvements are proposed for the latter and demonstrated to leverage the encountered caveats. An extension of extremal-based algorithm is then proposed to handle hard obstacles, whether still or moving. The modified algorithm proves capable to compute time-optimal trajectories with obstacles but loses the ability to compute the optimal cost of the problem everywhere in space.

The navigation problem is then extended by adding the speed of the vehicle as a time variable and the total energy expense as an optimization metric. In this framework, the difference between energy-time-optimal trajectories and time-optimal trajectories is studied. On realistic examples, it is shown that an order of magnitude of 10% reduction in energy expense is possible when allowing the vehicle speed to adjust dynamically during the travel.

Hazard is added in the navigation problem as a dynamical and diffuse quantity. A Hamilton-Jacobi-Bellman partial differential equation is solved to get reachability sets for the vehicle in a hazard-physical space, from which hazard-time-optimal trajectories are computed. On realistic settings, it is shown that hazard-time-optimal trajectories are able to avoid a significant amount of hazard in the environment while increasing moderately the total travel time, thus proving the relevance of hazard-time-optimal planning in operational contexts.

Finally, uncertainty is tackled in the planning problem. A most important source of uncertainty comes from the flow field prediction. Weather ensemble predictions provide a collection of possible weather scenarios that help quantify uncertainty in the flow field data. On an airborne problem, the approach consisting in computing time-optimal trajectories in each scenario and simulating the variation in travel time incurred by following the trajectory in different scenarios is evaluated. The average travel time is overall constant over the possible paths, but there exist paths minimizing the dispersion in the travel duration. Next, a PMP formulation on ground paths rather than trajectories is proposed. It enables the writing of differential equations satisfied by extremals candidate to average travel time optimality. These average-time-optimal trajectories are shown to solve for the minimal average travel time in an example, however not with a significant reduction compared to classical time-optimal trajectories in the considered case.