La propriété de l'autoroute
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)$.
| Dynamiques | Contrôles | Incertitudes | Contraintes | Cible | Concept de Viabilité |
|
Temps continu Continues en espace de dimension 2 $\left\{ Fonction de coût : $c'(t)=-1$ |
$u(t)\in [-1;1] $
|
Aucune |
$K\subset \mathbb{R}^2\times \mathbb{R}$
|
$C\subset K\times [0;+\infty[$
|
Bassin de capture |
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
 |
 |
Nous mettons à disposition ci-dessous les fichiers nécessaires pour calculer l'approximation ci-dessus à l'aide du logiciel ViabLab.
Veuillez consulter les supports de formation :