🤖 machine learning

From Feasibility to Desirability: Plan, Learn, Adapt (PLA) Framework for Personalized On-Device Itinerary Generation

L'article présente le cadre Plan, Learn, Adapt (PLA), un système sur appareil en trois étapes qui combine un ensemble de planificateurs légers avec un modèle de récompense compact pour générer des itinéraires personnalisés réalisables et hautement désirables, surpassant à la fois les planificateurs uniques et les modèles de langage de pointe lors d'évaluations humaines tout en atteignant une latence et une faisabilité de niveau production.

Auteurs originaux : Himel Dev, Tanmoy Sen, Madhusudan Basak, Bashima Islam

Publié 2026-07-20

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Himel Dev, Tanmoy Sen, Madhusudan Basak, Bashima Islam

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous soyez le capitaine d'un vaisseau spatial, mais qu'au lieu de naviguer à travers les étoiles, vous naviguiez dans une ville bouillonnante pour planifier les vacances parfaites. C'est le monde de la planification de voyage, un casse-tête qui se situe au carrefour de deux mondes scientifiques très différents. D'un côté, vous avez l'optimisation combinatoire, qui est comme un professeur de mathématiques strict s'assurant que vous ne brisez pas les règles : le musée ferme à 17h, le train part à 18h, et vous ne pouvez pas visiter deux fois le même endroit. De l'autre côté, vous avez l'apprentissage de préférences, qui est comme un médium essayant de deviner ce que vous voulez réellement ressentir — voulez-vous une journée de détente ou une aventure intense ? Le problème, c'est que ces deux mondes se battent souvent l'un contre l'autre. Un emploi du temps mathématiquement parfait peut sembler ennuyeux, et un programme de rêve et amusant peut être impossible à exécuter concrètement. La grande question pour quiconque a déjà essayé de planifier un voyage est la suivante : Comment construire un guide de voyage qui soit à la fois légalement possible à suivre et véritablement délicieux à vivre, tout en fonctionnant sur votre téléphone sans avoir besoin d'Internet ?

Ce document présente un nouveau système ingénieux appelé PLA (Plan, Learn, Adapt — Planifier, Apprendre, Adapter) qui tente de résoudre exactement ce problème. Les auteurs, travaillant avec une application de voyage appelée FlyEnjoy, ont réalisé que les méthodes existantes échouaient de deux manières spécifiques. Certains planificateurs de la vieille école étaient excellents pour suivre les règles mais terribles pour comprendre les goûts humains, créant souvent des itinéraires qui semblaient robotiques. Parallèlement, les outils d'IA les plus récents et les plus flamboyants (comme les modèles de langage géants dont tout le monde parle) étaient excellents pour paraître utiles mais échouaient complètement aux mathématiques de base du voyage ; dans leurs tests, ces modèles d'IA ont produit des itinéraires strictement infaisables (taux de réussite de 0 %), avec une limite statistique supérieure suggérant qu'ils n'étaient valides que dans moins de 4 % des cas, violant les horaires d'ouverture et les temps de trajet.

Pour corrir cela, l'équipe a construit une « usine » en trois étapes qui fonctionne entièrement sur votre téléphone :

Plan (L'Usine à Idées) : Au lieu de s'appuyer sur une seule façon de créer un emploi du temps, ils ont construit une équipe de cinq « planificateurs » différents (comme un chef gourmand, un comptable prudent et un artiste créatif). Chacun essaie de construire un voyage valide à partir de zéro. Parce qu'ils pensent différemment, ils proposent des listes de lieux à visiter très différentes, garantissant ainsi un éventail diversifié d'options « réalisables » (respectant les règles) à choisir.
Learn (Le Testeur de Goût) : L'équipe n'a pas simplement deviné ce que les gens aiment ; elle a demandé à des humains de comparer des paires d'itinéraires de journées complètes. Ils ont collecté plus de 2 500 de ces comparaisons. En utilisant ces données, ils ont entraîné un « modèle de récompense » minuscule et ultra-rapide (un testeur de goût numérique) qui a appris à repérer les qualités invisibles d'un excellent voyage, comme un bon rythme et un bel équilibre entre les activités, plutôt que de simplement compter le nombre de musées visités.
Adapt (Le Raffineur Local) : Une fois le meilleur itinéraire choisi, cette étape effectue de petits ajustements sûrs. C'est comme un chef qui goûte une soupe et y ajoute une pincée de sel, mais avec une règle stricte : chaque modification doit maintenir la validité de la recette. Si un ajustement brise le programme (comme vous faire arriver devant un magasin fermé), il est instantanément rejeté. Cela se produit si vite qu'il ne faut que 109,9 millisecondes en moyenne, ce qui signifie que vous obtenez un plan parfait et personnalisé instantanément, même si vous êtes dans un avion sans Wi-Fi, car le système est conçu pour un usage prioritaire hors ligne.

Les résultats sont impressionnants. Lorsqu'ils ont testé leur système contre le meilleur planificateur individuel, l'équipe « Plan, Learn, Adapt » a gagné 67,8 % du temps face aux juges humains. En revanche, lorsqu'ils ont demandé à trois des modèles d'IA les plus avancés (GPT-5, Claude Opus 4.5 et Gemini 3 Pro) de créer des itinéraires sous ces mêmes règles strictes, aucun d'entre eux (0 %) n'a produit un seul voyage valide. Le nouveau système s'est également bien généralisé, fonctionnant avec précision dans plus de 100 villes différentes des États-Unis qu'il n'avait jamais vues auparavant.

Dans le monde réel, lorsqu'ils ont déployé ce système dans l'application FlyEnjoy, les résultats ont été tangibles. Les utilisateurs ont commencé leur planification de voyage 83 % plus souvent et 91 % de personnes en plus ont réellement terminé leurs itinéraires. Le système n'a pas seulement créé les plans ; il a rendu toute l'expérience plus fluide, prouvant que vous pouvez avoir un guide de voyage qui est à la fois mathématiquement parfait et parfaitement amusant, tout en vivant directement dans votre poche.

Résumé technique : De la faisabilité à la désirabilité : le cadre PLA (Plan, Learn, Adapt)

1. Énoncé du problème

L'article traite du défi de la génération d'itinéraires de voyage personnalisés et multi-jours sur des appareils mobiles. Cette tâche est définie par une tension fondamentale entre une faisabilité combinatoire complexe et une désirabilité latente subjective :

Faisabilité : Les itinéraires doivent strictement respecter des contraintes spatio-temporelles, incluant les heures d'ouverture des points d'intérêt (POI), les temps de trajet, les budgets de temps quotidiens et les limites de coûts.
Désirabilité : Les itinéraires doivent satisfaire des préférences utilisateur subjectives concernant le rythme, la cohérence géographique et la diversité des catégories, qui sont difficiles à capturer avec des fonctions objectives statiques et artisanales.
Viabilité : Les solutions doivent être déployables sur les appareils des utilisateurs finaux (spécifiquement dans des environnements iOS en mode "offline-first") avec des exigences de latence strictes (vitesse interactive) et des contraintes de confidentialité, ce qui exclut l'utilisation de modèles de langage (LLM) dépendants du cloud.

Les approches existantes ne parviennent pas à satisfaire simultanément ces trois exigences : les optimiseurs classiques garantissent la faisabilité mais manquent de modélisation nuancée des préférences ; les méthodes basées sur l'apprentissage capturent les préférences mais violent souvent les contraintes strictes ; et les LLM, bien que capables de génération en langage naturel, produisent fréquemment des calendriers invalides (0 % de faisabilité dans le benchmark des auteurs) et sont incompatibles avec un déploiement mobile hors ligne à faible latence.

2. Méthodologie : Le cadre PLA

Les auteurs proposent Plan, Learn, Adapt (PLA), un cadre en trois étapes conçu pour traiter conjointement la faisabilité, la désirabilité et la viabilité.

Phase 1 : PLAN (Génération de plans diversifiés et réalisables)

La phase Plan génère un ensemble structurellement diversifié d'itinéraires candidats réalisables en utilisant un ensemble hétérogène de cinq algorithmes de planification légers, partageant tous une couche de faisabilité unifiée :

Algorithmes : Greedy (constructif), Programmation Dynamique (DP), Beam Search, A* Search et Simulated Annealing (SA).
Couche de faisabilité : Un module de logique partagé qui impose les contraintes strictes (heures de visite, cohérence des temps de trajet, budgets temps/coût, pas de répétitions) et calcule les heures d'arrivée les plus tôt possibles.
Objectif : Bien que tous les planificateurs optimisent un score composite partagé (équilibrant l'efficacité des déplacements, le temps d'attente, l'urgence, la diversité des catégories et la popularité des POI), leurs paradigmes de recherche distincts produisent des itinéraires structurellement différents. Cette diversité est cruciale car aucun algorithme ne domine systématiquement tous les contextes de voyage.

Phase 2 : LEARN (Modélisation des préférences humaines)

La phase Learn ajuste un modèle de récompense compact pour capturer la satisfaction utilisateur latente au niveau de l'itinéraire complet, plutôt que de s'appuyer sur des scores par POI.

Collecte de données : 2 519 comparaisons par paires effectuées par des humains sur des itinéraires complets à travers plus de 100 villes américaines ont été collectées. Les annotateurs choisissaient entre des itinéraires générés par différents planificateurs sans connaître leur source.
Architecture du modèle : Un modèle de récompense Bradley-Terry est entraîné sur environ 20 caractéristiques interprétables au niveau de l'itinéraire (ex: temps de trajet total, entropie des catégories, équilibre de la charge quotidienne, marge de manœuvre du planning).
- Le modèle utilise une formulation basée sur la différence : $P(x_a \succ x_b) = \sigma(R_\theta(x_a) - R_\theta(x_b))$ .
- Contraintes de monotonie : Le modèle impose directement la connaissance du domaine (ex: une augmentation du temps de trajet ne devrait pas augmenter la récompense) lors de l'optimisation.
Sélection : Le modèle de récompense agit comme un sélecteur, choisissant l'itinéraire ayant le score le plus élevé parmi le pool diversifié généré lors de la phase Plan.

Phase 3 : ADAPT (Raffinement sur l'appareil)

La phase Adapt effectue un raffinement local guidé par la récompense sur l'itinéraire "graine" sélectionné, dans le cadre d'un budget de calcul strict adapté à l'appareil.

Éditions préservant la faisabilité : Le système applique des opérateurs atomiques (Supprimer, Insérer, Remplacer, Échanger, Relocaliser, Déplacer Jour) à l'itinéraire. Crucialement, chaque édition est suivie d'une procédure de re-chronologie incrémentielle qui valide les contraintes. Si une édition viole une contrainte, elle est rejetée. Cela garantit que chaque état intermédiaire reste réalisable, contrairement aux méthodes de réparation a posteriori.
Stratégie de recherche : Une approche de type "hill-climbing" (recherche de sommet) avec échantillonnage stochastique du voisinage sélectionne les mouvements qui améliorent le score de récompense.
Conscience des ressources : Le processus de raffinement est limité par un budget de temps dynamique (typiquement ~200–500 ms) ajusté selon les signaux de l'appareil (nombre de cœurs, mémoire, mode d'alimentation) pour garantir une latence interactive.

3. Contributions clés

Ensemble de planificateurs hétérogènes : Les auteurs démontrent empiriquement qu'aucun algorithme de planification ne domine seul. En combinant cinq algorithmes distincts, ils atteignent un taux de victoire de 67,8 % dans les comparaisons par paires, soit une amélioration de 11,2 points de pourcentage par rapport au meilleur planificateur individuel (DP).
Modélisation des préférences au niveau de l'itinéraire : Dépassant le simple score par POI, l'article introduit un modèle Bradley-Terry compact entraîné sur des comparaisons d'itinéraires complets. Ce modèle capture des propriétés émergentes (rythme, équilibre des journées) et atteint une précision de 67,6 % en validation croisée "leave-one-city-out".
Raffinement sur l'appareil préservant la faisabilité : La phase Adapt améliore la désirabilité tout en garantissant une faisabilité de 100 % par construction. Elle atteint une latence moyenne sur l'appareil de 109,9 ms, permettant une exécution entièrement hors ligne et interactive.

4. Résultats expérimentaux

Faisabilité vs LLM : Dans un benchmark contre trois LLM de pointe (GPT-5, Claude Opus 4.5, Gemini 3 Pro) sur 294 itinéraires, les LLM ont atteint 0 % de faisabilité stricte, violant des contraintes telles que le temps de trajet et les heures de visite. En revanche, PLA a maintenu 100 % de faisabilité.
Performance de l'ensemble : L'ensemble guidé par la récompense a surpassé le meilleur planificateur individuel de 11,2 points (67,8 % contre 56,6 % de taux de victoire). La distribution de sélection montrait une entropie élevée (97,6 % du maximum), confirmant que différents algorithmes contribuent de manière unique selon le contexte.
Gain du raffinement : La phase Adapt a apporté des améliorations de score statistiquement significatives pour tous les algorithmes sources. Par exemple, les graines A* ont bénéficié d'une amélioration de 11,7 %, tandis que les graines de l'ensemble, déjà de haut niveau, ont progressé de 3,9 %.
Impact en production : Déployé dans l'application iOS FlyEnJoy, PLA a augmenté les taux de complétion d'itinéraires de 91 % et les initiations de 83 % par rapport à une base de comparaison à heuristique unique, tout en réduisant le temps de session moyen par utilisateur de 38 %.

5. Signification et affirmations

L'article affirme que PLA fournit un modèle viable pour la planification alignée sur l'humain sous des contraintes de déploiement réelles. Sa signification réside dans la résolution du compromis entre faisabilité et désirabilité sans dépendre de l'IA basée sur le cloud :

Robustesse : En séparant la faisabilité (Plan) de l'apprentissage des préférences (Learn) et en utilisant un raffinement préservant la faisabilité (Adapt), le système évite le problème des "itinéraires invalides" courant dans les approches d'apprentissage et l'IA générative.
Portabilité : L'utilisation d'un modèle de récompense compact et interprétable ainsi que d'opérateurs de recherche légers permet au système de fonctionner entièrement sur l'appareil, supportant des cas d'usage hors ligne (aéroports, vols) où les API cloud sont indisponibles ou trop coûteuses.
Praticité : Le cadre démontre qu'une planification complexe sur plusieurs jours peut être exécutée avec une latence interactive (<300 ms) tout en respectant strictement les contraintes rigides, une capacité que les LLM de pointe actuels n'ont pas dans ce domaine spécifique.

Les auteurs concluent que si les LLM peinent avec les contraintes strictes, une approche hybride structurée combinant optimisation classique, apprentissage des préférences et recherche locale contrainte peut offrir des résultats supérieurs et prêts pour la production pour la génération d'itinéraires personnalisés.