Approximation pour l'optimisation de performances : application à l'efficience des transports urbains.

Publié le
Equipe
Date de début de thèse (si connue)
Septembre 2022
Lieu
Rennes
Unité de recherche
IRISA - UMR 6074
Description du sujet de la thèse

Le transport individuel représente 54% de la pollution liée au transport. Avec la densification des villes et de leurs périphéries, un des enjeux est d’assurer des transports fiables répondant aux besoins des usagers. Les freins à l’utilisation quotidienne des transports en commun sont la connectivité des réseaux, le temps nécessaire de bout en bout pour un trajet… Il est essentiel de fiabiliser les interconnections entre moyens de transport, pour que le temps d’un trajet soit essentiellement du temps de déplacement et non du temps d’attente. Les réseaux de métro, colonnes vertébrales du transport urbain, sont souvent à leurs fréquences maximales. Les solutions en matière de mobilité ne peuvent donc pas venir de l’augmentation de la taille des flottes, mais plutôt de techniques fines de régulation qui anticipent et fluidifient le transport de passagers. Pour un opérateur de transport, cela doit aussi se faire en minimisant les coûts énergétiques et les coûts d’exploitation.

La question de l’optimisation du transport de passagers peut être vue comme un problème classique d’optimisation de récompense dans un système cyber-physique. La « solution » consiste alors à synthétiser une stratégie qui optimise en moyenne un ou des critères quantitatifs choisis. Ces solutions théoriques se heurtent cependant au problème de la taille des systèmes à étudier. Un petit réseau de métro induit rapidement des modèles formels à plusieurs millions d’états. Synthétiser une stratégie optimale pour de tels modèles excède de loin les capacités des outils les plus puissants.

Dans cette thèse, nous proposons d’étudier des techniques de synthèse efficace de stratégies quasi-optimales pour des modèles aléatoires, à l’aide de techniques issues de l’apprentissage statistique et de méthodes d’approximation. L’apprentissage statistique est une méthode qui permet de résoudre des problèmes en effectuant des simulations et corrigeant les stratégies à partir des performances obtenues. Ces techniques commencent à donner des résultats intéressants dans le cadre des jeux de stratégie. Un second angle pour traiter la complexité est de s’appuyer sur des approximations, à la fois des modèles étudiés et des calculs effectués pour construire une stratégie. Cette étape ne sera cependant pas suffisante, car il est inenvisageable d’énumérer, pour chaque état du système, le choix optimal indiqué par une stratégie. Nous chercherons donc à synthétiser des stratégies sous-optimales fonctionnant à partir d’abstractions des états du système. La difficulté sera ici de proposer des mécanismes d’abstraction garantissant que les performances d’un système restent suffisamment proches d’un optimum.

Le travail de thèse commencera par une étude des techniques d’apprentissage statistiques pour des modèles simples comme les Markov Decision Processes avec récompense, afin de comprendre les modèles les plus adaptés pour apprendre et abstraire une stratégie. La tâche suivante consistera à proposer des techniques d’abstraction de modèles et de stratégies, et à en prouver la pertinence et l’efficacité. Cette thèse se déroulera dans le cadre de l’ANR Maveriq (2021-2025) qui traite en particulier de problèmes d’approximation.

Bibliographie

[1] Alexandre David, Peter Gjøl Jensen, Kim Guldstrand Larsen, Marius Mikučionis and Jakob Haahr Taankvist. Uppaal Stratego. 21st International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), 2015.

[2] , , , :
Automated Verification Techniques for Probabilistic Systems, SFM2011, 53-113, 2015.

[3] Christel Baier and Joost-Pieter Katoen, Principles of Model Checking, Chap. 10, MIT Press, 2008.

[4] , , , :
On Abstraction of Probabilistic Systems. ROCKS : 87-116, 2012

 

 

Liste des encadrants et encadrantes de thèse

Nom, Prénom
Hélouët, Loïc
Type d'encadrement
Directeur.trice de thèse
Unité de recherche
Inria
Equipe

Nom, Prénom
Fabre, Eric
Type d'encadrement
2e co-directeur.trice (facultatif)
Unité de recherche
INRIA
Equipe
Contact·s
Nom
Hélouët, Loïc
Email
loic.helouet@inria.fr
Téléphone
02 99 84 75 90
Nom
Fabre, Eric
Email
eric.fabre@inria.fr
Téléphone
02 99 84 73 26
Mots-clés
Apprentissage, approximation, optimisation