Mémoire de fin d'études sur la programmation par contraintes

Résumé

Plus les événements possibles augmentent, plus le simulateur examine de conditions de manière répétée. Alors, si l'on peut déterminer à partir de l'avancement que « cette condition ne se réalisera plus jamais », ne serait-il pas possible d'arrêter cette vérification en toute sécurité ? Nous avons conçu et implémenté pour le langage de modélisation de systèmes hybrides HydLa une méthode qui utilise la direction du changement des valeurs comme indice pour exclure des conditions devenues inutiles de l'exploration en cours.

Dans le modèle d'évaluation, le temps d'exécution a été réduit à environ la moitié de celui des méthodes traditionnelles, sans modifier les résultats de la simulation. L'important n'est pas d'avoir accéléré tous les calculs de manière uniforme. C'est d'avoir utilisé la structure du problème pour réduire le nombre même de possibilités à considérer.

La manière de penser de la programmation par contraintes que j'ai apprise dans cette recherche constitue la base de l'actuel Ma philosophie de design. Il ne s'agit pas de spécifier directement chaque résultat, mais de définir des règles, des priorités et des limites, et de déduire les solutions valides à partir de celles-ci.

Problème — Plus les possibilités augmentent, plus le calcul devient lent

HydLa est un langage destiné à décrire les « systèmes hybrides », qui combinent des changements continus et des événements discrets, sous forme de contraintes mathématiques et logiques. Sans avoir à écrire toutes les séquences de procédures, il est possible de simuler un comportement satisfaisant les conditions en déclarant simplement ce qui doit être établi.

D'autre part, dans les modèles où de nombreuses règles deviennent effectives en fonction des conditions, le simulateur vérifie de manière répétée un grand nombre de candidats. Les conditions qui ont déjà été dépassées et qui ne se réaliseront pas à l'avenir restent parmi les candidats, de sorte que plus le modèle est grand, plus les calculs inutiles s'accumulent.

Sujet — un système où le continu et le discret se mêlent

Une balle qui rebondit est un exemple clair d'un système hybride. Dans les airs, sa position et sa vitesse changent de manière continue, et au moment où elle touche le sol, un événement discret de rebondissement se produit. Les thermostats, les voitures et les robots possèdent également ces deux types de changements en leur sein, même si à des échelles différentes.

Pour l'évaluation, nous avons utilisé un modèle où une balle se déplaçant horizontalement rebondit sur une surface divisée en plusieurs sections. Pour chaque section de la surface, il existe une règle conditionnelle « la balle rebondit si elle atteint cette zone ». En augmentant le nombre de sections, on peut représenter un plus grand nombre de cibles, mais le simulateur doit également examiner davantage de conditions.

Goulot d'étranglement — le nombre de conditions augmente la complexité de calcul

Une règle qui ne devient effective que lorsque certaines conditions sont remplies est appelée « contrainte avec garde ». Dans le modèle d'évaluation, la règle de rebond d'une section n'est effective que lorsque la balle atteint le sol et que sa position horizontale se trouve dans cette section.

Lorsque le nombre de parcelles est augmenté de 10 à 200, le simulateur traditionnel devenait environ proportionnel au carré du nombre de parcelles. Dans les modèles de grande taille, le même problème devient plus important car le nombre d'objets, de zones de contact et d'événements possibles augmente.

Enquête — Où se trouvait 96 % du temps de traitement

Lors de la mesure du temps de traitement, dans le modèle de 100 sections, 96 % du temps total était utilisé pour FindMinTime. Il s'agit du traitement qui consiste à rechercher « le prochain événement le plus rapide » parmi les candidats. Par conséquent, toutes les conditions de garde étaient évaluées de manière répétée.

Les points à améliorer sont devenus clairs. Il n'est pas nécessaire de reconstruire l'ensemble de la méthode de calcul, il suffit de réduire en toute sécurité les candidats à transmettre à FindMinTime. L'objectif était de ne retirer que les possibilités inutiles à examiner, sans changer les résultats de la simulation.

Approche — Retirer en toute sécurité des conditions qui ne se réaliseront plus jamais

Imaginez une balle descendant les escaliers en rebondissant. Si la balle passe un degré et continue à avancer, ce degré n'a plus d'effet sur la balle. Une personne regardant le schéma ignore immédiatement les degrés derrière la balle. L'algorithme original continuait à vérifier chacun d'entre eux.

La difficulté réside dans le fait de montrer que la garde supprimée ne sera pas nécessaire par la suite. Si l'on la supprime simplement parce qu'elle est fausse pour le moment, elle pourrait silencieusement renvoyer un résultat incorrect lorsque cela redeviendra vrai. C'est pourquoi la méthode proposée utilise la monotonie — il s'agit de déterminer si l'on peut garantir qu'une certaine variable continue d'augmenter ou de diminuer sur un certain intervalle de temps.

Lorsque le sens du changement ne change pas

La première mesure s'applique lorsque la variable évolue dans une seule direction tout au long de la simulation. Dans un modèle où la surface est divisée, la position horizontale de la balle ne cesse d'augmenter. Une fois qu'elle a dépassé une section, les conditions de cette section ne seront plus jamais remplies. Cette propriété peut être vérifiée avant la simulation grâce aux techniques de vérification de modèle, ce qui permet de supprimer en toute sécurité les gardes devenus inutiles à mesure que l'exécution progresse.

Lorsque la direction du changement change en cours de route

De nombreux systèmes réels ne fonctionnent pas toujours dans une seule direction. Les variables peuvent augmenter, changer de direction, puis diminuer. L'article a donc présenté une deuxième approche. D'abord, on suppose une direction, on surveille cette hypothèse par une assertion, et lorsqu'un changement de direction se produit, le processus de réduction est recommencé depuis ce point. Les gardes retirés pour un intervalle monotone sont rétablis au début du prochain intervalle.

Résultat — le temps d'exécution du modèle d'évaluation a été réduit de moitié environ

Nous avons mis en œuvre la gestion de la monotonie uniforme et évalué le modèle avec les surfaces divisées. Tant l'algorithme original que la méthode proposée voient le temps requis augmenter avec le nombre de segments. Cependant, la méthode proposée nécessitait systématiquement moins de travail. En comparant les courbes ajustées, le coefficient du terme le plus élevé est passé de 1,1463 à 0,6083, ce qui a réduit d'environ moitié le temps total de simulation pour ce benchmark.

Il ne s'agit pas d'une affirmation selon laquelle tous les modèles HydLa deviennent deux fois plus rapides. Ce qui est montré, c'est où cette méthode fonctionne — dans les modèles où il y a beaucoup d'objets avec des gardes, où la direction des changements peut être prouvée, et où les gardes deviennent définitivement sans rapport pendant l'exécution.

Les perspectives obtenues à partir de cette recherche

Ce que nous avons fait dans cette recherche n'était pas d'accélérer légèrement chaque calcul individuel. Il s'agissait d'utiliser ce que nous savons sur le comportement du système pour réduire l'ensemble des possibilités à considérer. L'idée de restreindre l'espace de recherche sans changer le résultat est la force de la programmation par contraintes.

Ce qui a été mis en œuvre et évalué est le cas où les variables continuent de se déplacer dans une seule direction. Lorsque la direction du changement change en cours de route, cela reste au stade de la conception, l'évaluation étant laissée comme un sujet pour l'avenir. Il y a également une marge pour utiliser des propriétés autres que la monotonie et trouver d'autres contraintes inutiles.

Le fait que je cherche aujourd'hui à concevoir les conditions et les limites que l'IA peut explorer, plutôt que de concevoir directement les sorties de l'IA, est également lié à cette expérience. Lorsqu'on traite des résultats complexes, il est aussi important de définir ce qu'il n'est pas nécessaire de considérer que ce que l'on doit calculer.