Mémoire de licence sur la programmation par contraintes
juin 2019
Présentation
Plus une simulation comprend d’événements possibles, plus elle doit réévaluer de conditions. Mais si son évolution établit qu’une condition ne pourra plus jamais devenir vraie, peut-on cesser de la vérifier sans compromettre le résultat ? J’ai conçu et implémenté une méthode pour HydLa, un langage de modélisation de systèmes hybrides, qui utilise le sens de variation des variables pour supprimer les conditions devenues inutiles.
Dans le modèle d’évaluation, la méthode a ramené le temps d’exécution à environ la moitié de celui de l’algorithme d’origine, sans changer les résultats de la simulation. Ce gain provenait de l’exploitation de la structure du problème pour réduire les possibilités à examiner.
La perspective de la programmation par contraintes, acquise au cours de ces recherches, sous-tend aujourd’hui mon approche des projets de mon portfolio : définir les règles, les priorités et les limites, puis en déduire des solutions qui les respectent, plutôt que de spécifier directement chaque résultat.
Problème : davantage de possibilités allongent les temps d’exécution
HydLa décrit les systèmes hybrides, qui combinent des variations continues et des événements discrets, au moyen de contraintes mathématiques et logiques. Le modèle déclare les conditions à respecter sans détailler chaque étape d’une procédure ; le simulateur recherche ensuite des comportements qui les satisfont.
Dans les modèles comportant de nombreuses règles conditionnelles, le simulateur vérifie à plusieurs reprises un grand ensemble de candidats. Même les conditions qui ne peuvent plus devenir vraies y restent présentes. À mesure que le modèle s’agrandit, ces vérifications inutiles alourdissent les calculs.
Modèle : combiner changements continus et discrets
Une balle qui rebondit est un exemple simple de système hybride. Sa position et sa vitesse varient continûment lorsqu’elle est en l’air, puis le contact avec le sol déclenche un événement discret : le rebond. Les thermostats, les voitures et les robots combinent eux aussi ces deux types de changement, à différentes échelles.
L’évaluation utilisait un modèle de balle se déplaçant horizontalement et rebondissant sur une surface divisée en segments. Chaque segment possède une règle conditionnelle qui fait rebondir la balle lorsqu’elle atteint cette zone. Ajouter des segments permet de représenter davantage d’objets, mais augmente aussi le nombre de conditions à vérifier par le simulateur.
Goulot d’étranglement : le nombre de conditions accroît le temps d’exécution
Une règle qui ne s’active que lorsqu’une condition est satisfaite s’appelle une contrainte gardée. Dans le modèle d’évaluation, la règle de rebond d’un segment ne s’active que lorsque la balle atteint le sol et que sa position horizontale se situe dans ce segment.
Lorsque le nombre de segments passait de 10 à 200, le temps d’exécution du simulateur d’origine augmentait approximativement comme le carré de ce nombre. Les modèles plus grands peuvent amplifier ce problème en comprenant davantage d’objets, de zones de contact et d’événements possibles.
Analyse : où passaient 96 % du temps d’exécution ?
Le profilage du modèle à 100 segments a montré que FindMinTime représentait 96 % du temps d’exécution total. Cette routine recherche le prochain événement possible le plus proche en réévaluant toutes les conditions de garde candidates.
Ce résultat a permis de cibler une amélioration : réduire sans risque les candidats transmis à FindMinTime. L’objectif était d’écarter uniquement les possibilités devenues inutiles, tout en préservant les résultats de la simulation.
Approche : supprimer les conditions qui ne pourront plus devenir vraies
Imaginons une balle qui descend un escalier en rebondissant. Une fois une marche dépassée, si la balle continue d’avancer, cette marche ne peut plus agir sur elle. Une personne observant le schéma ignore immédiatement les marches derrière la balle ; l’algorithme d’origine continuait à toutes les examiner.
La difficulté consiste à prouver qu’une garde supprimée ne sera pas nécessaire par la suite. L’écarter simplement parce qu’elle est fausse à l’instant présent pourrait produire silencieusement un résultat incorrect si elle redevient vraie. La méthode proposée utilise donc la monotonie : peut-on garantir qu’une variable continuera à augmenter ou à diminuer sur un intervalle donné ?
Lorsque le sens de variation reste le même
La première approche s’applique lorsqu’une variable évolue dans un seul sens pendant toute la simulation. Dans le modèle de surface segmentée, la position horizontale de la balle augmente toujours. Dès qu’elle dépasse un segment, la garde de ce segment ne peut plus redevenir vraie. Des techniques de vérification de modèles peuvent établir cette propriété avant la simulation, ce qui permet de supprimer les gardes sans risque lorsqu’elles deviennent inutiles pendant l’exécution.
Lire les indications de la figure en français
L’axe t représente le temps, de 0 à MaxT, la fin de la simulation. La variable passe de α à β en conservant le même sens de variation.
Lorsque le sens de variation s’inverse
De nombreux systèmes n’évoluent pas indéfiniment dans un seul sens : une variable peut augmenter, changer de sens, puis diminuer. Le mémoire proposait donc une seconde approche. Elle suppose un sens de variation et surveille cette hypothèse à l’aide d’assertions. Lorsqu’il change, le processus de réduction redémarre et rétablit les gardes supprimées pendant l’intervalle monotone précédent. Cette approche a été conçue, mais ni implémentée ni évaluée dans ce projet.
Lire les indications de la figure en français
L’axe t représente le temps ; MaxT indique la fin de la simulation. Les pointillés prolongent le sens de variation supposé ; les croix marquent les échecs d’assertion. Chaque échec conduit à définir un nouvel intervalle, repéré successivement par α₀–β₀, α₁–β₁, puis α₂–β₂.
Résultat : un temps d’exécution presque divisé par deux dans le modèle d’évaluation
J’ai implémenté l’approche fondée sur la monotonie uniforme et l’ai évaluée avec le modèle de surface segmentée. Pour les deux algorithmes, le temps d’exécution augmentait avec le nombre de segments, mais la méthode proposée était systématiquement plus rapide. Dans les courbes ajustées, le coefficient du terme de plus haut degré est passé de 1,1463 à 0,6083. Le temps total de simulation sur ce cas de référence a été approximativement divisé par deux.
Ce résultat est propre au cas de référence étudié. La méthode est utile lorsqu’un modèle contient de nombreux objets associés à des gardes, que le sens de variation peut être prouvé et que certaines gardes deviennent définitivement inutiles pendant l’exécution. Elle ne signifie pas que tous les modèles HydLa s’exécuteront deux fois plus vite.
Lire les indications de la figure en français
Axe horizontal : N, nombre de segments de la surface. Axe vertical : temps de simulation, en secondes. « Original » désigne l’algorithme d’origine, représenté par des cercles ; « proposed » désigne la méthode proposée, représentée par des carrés.
Ce que j’en ai retenu
Ces recherches exploitaient des propriétés connues du comportement d’un système pour réduire l’ensemble des possibilités à examiner par le simulateur. Réduire l’espace de recherche tout en préservant les résultats est l’un des atouts de la programmation par contraintes.
L’implémentation et l’évaluation portaient sur les variables continuant d’évoluer dans un seul sens. La gestion des inversions restait au stade de la conception et devait encore être évaluée. D’autres propriétés que la monotonie pourraient également aider à repérer les contraintes inutiles.
Cette expérience nourrit mon intérêt actuel pour la conception des conditions et des limites à l’intérieur desquelles l’IA peut rechercher des solutions. Face à des résultats complexes, définir ce qui peut être ignoré sans risque compte autant que définir ce qu’il faut calculer.
Takafumi Horiuchi et Kazunori Ueda. « Dynamic Reduction of Guarded Constraints for the Hybrid Systems Modeling Language HydLa ». Proceedings of the 33rd Annual Conference of the Japanese Society for Artificial Intelligence, 2019. DOI : 10.11517/pjsai.JSAI2019.0_1E3OS3b02