Robotique

Introduction

Le « problème de navigation de Zermelo » originel s'énonce comme suit : dans un plan illimité où la répartition du vent est définie par un champ de vecteurs dépendant de la position et du temps, un navire se déplace à vitesse constante par rapport à la masse d'air environnante. Comment le navire doit-il être dirigé pour rallier une destination donnée depuis un point de départ dans le temps le plus court ?

Ce problème peut-être modélisé sous la forme d'un système dynamique contrôlé dont on cherche la commande optimale, celle qui minimise le temps mis pour atteindre la cible.
Les variables d'état $x$ et $y$ désignent les coordonnées du navire en mouvement, tandis que $f(x, y)$ et $g(x, y)$ représentent les composantes de la vitesse du vent qui dépendent de la position. Deux variables de commande régissent l'évolution du navire : la vitesse $v$, dont la norme $||v||$ est bornée par un seuil dépendant de la position ($||v|| ≤ c(x,y)$), et la direction $u$, c'est-à-dire l'angle que forme le vecteur vitesse relative avec l'axe des $x$ qui est contrainte par les bornes $\alpha_{min}(x, y)$ et $\alpha_{max}(x, y)$.
L'évolution du navire est ainsi régie par le système dynamique contrôlé suivant :
\begin{equation}
\left\{
\begin{array}{l}
x'(t) &= f(x(t), y(t)) + v(t) \cos u(t) \\
y'(t) &= g(x(t), y(t)) + v(t) \sin u(t) \\
u(t) &\in [\alpha_{min}(x(t), y(t)),\alpha_{max}(x(t), y(t)] \text{ et } ||v(t)|| ≤ c(x(t), y(t)).
\end{array}
\right.
\end{equation}
 

Etant donné un point de départ $(x_0,y_0)$, il s'agit de trouver les fonctions de commande $u(t)$ et $v(t)$ qui permettent d'atteindre une cible en temps minimal. 

Le problème de Zermelo revisité avec les concepts de la théorie de la viabilité

Depuis

J.-P.AUBIN & H. FRANKOWSKA, « The viability kernel algorithm for computing value functions of infinite horizon optimal control problems », Journal of mathematical analysis and applications, vol. 201, 555–576, 1996.

des liens sont établis entre les problèmes de contrôle optimal et les noyaux de viabilité ou bassins de capture.

Le problème de temps minimal pour l'atteinte d'une cible en est un cas particulier et le problème de Zermelo a été souvent illustré. 

Dans leur livre

Aubin, J.-P., Bayen, A., & Saint-Pierre, P. Viability Theory: New Directions. Springer. 2011.

les auteurs revisitent le problème de Zermelo en remplaçant le "plan illimité" par un environnement $K\subset \mathbb{R}^2$ avec des obstacles, le « but » étant le port, il joue le rôle de la « cible » $C \subset K$ dans la terminologie de la théorie de la viabilité. Il s’agit bien entendu d’un problème plus complexe que le problème de Zermelo initial en raison de ces contraintes supplémentaires définies par l'ensemble $K$ dans lequel les trajectoires doivent rester. 

Associer à chaque point de l'environnement $K$ la valeur du temps minimal nécessaire pour atteindre la cible $C$ revient à calculer le bassin de capture dans la terminologie de la théorie de la viabilité pour le système initial augmenté d'une dimension, celle du coût associé au temps qui s'écoule. En effet, ce bassin de capture correspond à l'épigraphe de la fonction de temps minimal (i.e. l'ensemble des points situés au-dessus de sa courbe représentative).

Résultats

Pour l'illustration numérique, nous choisissons comme zone de déplacement du bateau $K\subset [-6;1]\times[-2.5;2.5]$ privé de deux sous-ensembles représentant deux obstacles $0_1 =  [-4;3]\times[-0;2]$ et $0_2 =  [-2;-1]\times[-0.75;0.75]$ et comme cible $C = \{(x,y) | x^2+y^2\leq 0.04$. Ces sous-ensembles du plan sont dessinés dans le graphique ci-dessous :

La dynamique du courant est $f(x,y)=-0.25\tanh y $ et $g(x,y)=0$, sans contrainte sur le choix de l'angle de la vitesse relative $u(t) \in [0,2\pi]$ mais avec la norme de cette vitesse relative constante égale à 1, $|v(t)| =1$.  Ainsi,  l'évolution du navire est régie par l'équation :

\begin{equation}
\left\{
\begin{array}{l}
x'(t) &= \cos u(t) -0.25\tanh y(t)\\
y'(t) &= \sin u(t) \\
u(t) &\in [0,2\pi]
\end{array}
\right.
\end{equation}

Le bassin de capture est un sous-ensemble de dimension 3 (les 2 dimensions du problème initial + 1 dimension pour la fonction de coût associée au temps minimal).

Ce bassin de capture est épigraphique, c'est à dire qu'il se situe au-dessus de sa frontière inférieure dans la dimension de la fonction de coût. Nous reproduisons ci-dessous l'approximation de sa frontière inférieure calculée par le logiciel ViabLab à partir d'une grille de $701\times 501$ points dans l'espace initial de dimension 2 :

 
Les deux "trous" correspondent aux deux obstacles pour les points desquels la valeur du temps minimal pour atteindre la cible est $+\infty$.

Ce résultat peut également être visualisé sous forme de lignes de niveaux dans l'environnement du problème initial :