Robotique

Introduction

La propriété dite de « turnpike » (ou de l'autoroute), remonte à un texte consacré à l'économétrie du prix Nobel Paul Samuelson et coauteurs 

R. Dorfman, P.A. Samuelson, R. Solow, Linear programming and economic analysis, New York,
McGraw-Hill, 1958.

Les auteurs produisent une preuve de l'optimalité de stratégies consistant à choisir durant une période intermédiaire une configuration du capital qui permet la croissance la plus rapide.

"La situation est exactement comparable à celle d'une autoroute doublée d'un réseau de routes secondaires. Il existe un itinéraire le plus rapide entre deux points quelconques ; si le point de départ et la destination sont proches l'un de l'autre et éloignés de l'autoroute, le meilleur itinéraire peut ne pas emprunter cette dernière. En revanche, si le point de départ et la destination sont suffisamment éloignés, il sera toujours avantageux de rejoindre l'autoroute et de parcourir la distance à la vitesse optimale, même si cela implique un léger allongement du trajet aux deux extrémités." (traduction d'un extrait du texte cité ci-dessus)

Un exemple de problème d'autoroute

Dans leur article, consacré à l'étude des stratégies optimales mixtes (arcs Bang - contrôle extrémal ; arcs singuliers - contrôle non extrémal), 

Ruben Chenevat, Bruno Cheviron, Sébastien Roux, Alain Rapaport. Extension of the Bang-Bang
Principle for spatially-temporally regional affine dynamics under constraints. 2024. hal-04606183

les auteurs étudient un problème de type "autoroute".

La dynamique en 2D est telle que la croissance maximale de $y$ a lieu lorsque $x=1$ (c'est l'autoroute) et le contrôle agit sur $x$ permettant de choisir de circuler sur cette autoroute : 

\begin{equation}
\left\{
\begin{array}{l}
x'(t) &= u(t) \\
y'(t) &= F(x(t)) \\
u(t) &\in [-1;1]
\end{array}
\right.
\end{equation}

avec 

\begin{equation}
F(x)=\left\{
\begin{array}{ll}
x & \text{si } x\leq 1  \\
2-x & \text{si } x\geq 1
\end{array}
\right.
\end{equation}

La cible à atteindre est un point particulier de l'espace, le point $F:(2,3)$.

Les auteurs démontrent qu'à partir de l'origine, la trajectoire optimale pour atteindre le point $F$ est de type "Bang - Singulière - Bang" : 

\begin{equation}
\left\{
\begin{array}{lll}
u^*(t) &= 1 & t\in [0;1]\\
u^*(t) &= 0 & t\in [1;3]\\
u^*(t) &= 1 & t\in [3;4]\\
\end{array}
\right.
\end{equation}

De plus, le temps minimal pour atteindre $F$ vaut $4$.

Le problème de l'autoroute 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.

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) :

$$
t_{min}(K,C)(x_0,y_0) = \inf_{(x_0,y_0,z)\in Capt(K,C)}z
$$

De plus, l'ensemble des trajectoires issues de $(x_0,y_0)$ réalisant ce temps minimal d'atteinte de cible correspond à l'ensemble des trajectoires issues de $(x_0,y_0)$ contenues dans $Capt(K,C)$.

Résultats

Le calcul du bassin de capture permet d'obtenir la valeur du temps minimal pour atteindre la cible pour tous les points de l'ensemble $K$.

Cible et ensemble de contraintes

Pour l'illustration numérique, nous choisissons comme zone de déplacement (ensemble de contraintes dans la terminologie de la viabilité)  $K = [0;2]\times[0;3]$ et comme cible un disque de petit diamètre autour du point $F$, $C = \mathcal{B}((2;3),0.001)$.

Bassin de capture

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. De plus, l'altitude du point de sa frontière inférieure donne la valeur du temps minimal pour atteindre la cible : 

$$
t_{min}(K,C)(x_0,y_0) = \inf_{(x_0,y_0,z)\in Capt(K,C)}z
$$

Nous reproduisons ci-dessous l'approximation de sa frontière inférieure calculée par le logiciel ViabLab à partir d'une grille de $1601\times 2401$ 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$.

Lignes de niveau de la fonction temps minimal

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

Trajectoires optimales

Comme précisé ci-dessus, les trajectoires optimales sont des sous-produits du bassin de capture. 
Ainsi, le logiciel ViabLab permet d'en calculer des approximations par des courbes linéaires par morceaux dont la précision dépend des approximations de pas de temps et d'espace conduisant à l'approximation du noyau de viabilité.

Ci-dessous sont représentées la solution exacte et l'approximation de la trajectoires optimales issues du point $(0;0)$ dans les deux représentations :

• à gauche dans l'espace 3D contenant la variable de coût (le temps qui s'écoule), la trajectoire approchée en cyan issue du point $(0;0, t_{min}(0,0))$ reste sur la frontière du bassin de capture
• à droite dans l'espace 2D du problème initial (projection des trajectoires de dimension 3), la trajectoire approchée en cyan et la trajectoire exacte en rouge

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) :

$$
t_{min}(K,C)(x_0,y_0) = \inf_{(x_0,y_0,z)\in Capt(K,C)}z
$$

De plus, l'ensemble des trajectoires issues de $(x_0,y_0)$ réalisant ce temps minimal d'atteinte de cible correspond à l'ensemble des trajectoires issues de $(x_0,y_0)$ contenues dans $Capt(K,C)$.

Résultats

Dynamique et ensemble de contraintes

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}

Bassin de capture

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$.

Lignes de niveau de la fonction temps minimal

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

Trajectoires optimales

Comme précisé ci-dessus, les trajectoires optimales sont des sous-produits du noyau de viabilité. 
Ainsi, le logiciel ViabLab permet d'en calculer des approximations par des courbes linéaires par morceaux dont la précision dépend des approximations de pas de temps et d'espace conduisant à l'approximation du noyau de viabilité.

Ci-dessous sont représentées deux approximations de trajectoires optimales pour les points initiaux $(-4,-1,5)$ et $(-5,1)$ dans les deux représentations :

• à gauche dans l'espace 3D contenant la variable de coût (le temps qui s'écoule), les trajectoires sont issues des points $(-4,-1,5, t_{min}(4,-1,5))$ et $(-5,1,t_{min}(-5,1))$ et restent sur la frontière du bassin de capture
• à droite dans l'espace 2D du problème initial (projection des trajectoires de dimension 3)