Pourquoi la programmation par planification est étonnante

 (hillelwayne.com)
2 points par GN⁺ 2024-02-22 | 1 commentaires | Partager sur WhatsApp
  • Le module planner de Picat va plus loin que la programmation logique qui cherche une affectation de valeurs : il permet d’exprimer le problème comme une séquence de changements d’état menant à un état objectif
  • Si l’on définit l’état initial Start, les règles de transition action(From, To, Action, Cost) et la condition d’arrêt final(S), alors best_plan(Start, Plan) trouve le plan de coût minimal jusqu’à l’état final
  • Dans l’exemple de parcours sur grille, le déplacement, les limites de bord, l’évitement d’obstacles et la visite de plusieurs objectifs se gèrent simplement en modifiant action et final, et l’ordre de visite peut être imposé ou laissé libre
  • La fonctionnalité de planification peut être combinée à la résolution de contraintes, ce qui permet aussi d’exprimer des problèmes comme la recherche de la plus grande sous-liste d’un partition problem que l’on peut partager en deux sommes égales après suppression d’éléments
  • Picat est un langage de recherche, donc sa documentation et ses messages d’erreur sont limités, mais comme langage-outil pour résoudre rapidement certains problèmes de calcul, il peut offrir des solutions plus concises qu’un langage généraliste

Idée de base de Picat et de la programmation par planification

  • Picat est un langage de recherche qui cherche à combiner la programmation logique, la programmation impérative et la résolution de contraintes
  • La programmation impérative ou fonctionnelle classique écrit un algorithme qui produit une sortie à partir d’une entrée, tandis que la programmation logique et la résolution de contraintes cherchent une affectation de valeurs qui satisfait une relation
  • Dans Picat, les identifiants non fonctionnels commençant par une minuscule sont des atoms comme a, b, c, et les identifiants commençant par une majuscule sont des variables
  • Même dans une expression comme member(Y, Arr) où la variable Y n’est pas encore définie, Picat peut chercher et affecter une valeur qui rend l’expression vraie
    • Si Arr = [a, b, c, a], alors Y peut être a, b ou c
    • Si l’on ajoute ensuite une condition comme X != Y, l’ensemble des valeurs possibles se restreint davantage
    • Avec member(a, Z), Picat peut même instancier Z comme une liste alors que la liste elle-même n’est pas encore connue

La planification cherche des changements d’état, pas une affectation de valeurs

  • La planification (planning) ne cherche pas des valeurs de variables satisfaisant une équation, mais une séquence de modifications de variables qui atteint un état terminal donné
  • Un problème de planification dans Picat nécessite trois éléments
    • l’état initial Start
    • des fonctions action représentant les transitions d’état
    • final(S), qui détermine si un état est terminal
  • Les fonctions action de Picat doivent toutes s’appeler action et prennent quatre paramètres
    • l’état courant
    • l’état suivant
    • le nom de l’action
    • le coût
  • best_plan(Start, Plan) affecte à Plan le plan le plus court en nombre d’étapes ou de coût minimal jusqu’à l’état terminal
    • Si tous les coûts valent 1, le coût du plan correspond au nombre total d’étapes de déplacement
    • Si l’on veut simplement n’importe quel plan, quelle que soit sa longueur, on peut utiliser plan(Start, Plan)

Exemple de recherche de chemin sur grille

  • Dans l’exemple, un marqueur placé sur une grille part de l’origine (0, 0) et doit atteindre une coordonnée cible
    • À chaque étape, il peut se déplacer d’une case vers le haut, le bas, la gauche ou la droite
    • Il ne peut pas sortir des limites de la grille
    • L’arrivée sur la coordonnée cible constitue un succès
  • L’état initial contient à la fois la position courante et la cible, sous la forme {Origin, Goal}
    • Dans Picat, {a, b} est une syntaxe de tableau, utilisée en pratique comme un tuple
  • La condition d’arrêt peut être exprimée par filtrage de motifs, par exemple final({Pos, Goal}) => Pos = Goal.
    • Pour écrire la même chose sans filtrage de motifs, il faut d’abord décomposer l’état en {Pos, Goal}
    • S’il existe plusieurs conditions final, le plan réussit dès qu’au moins l’une d’elles est vraie
  • L’action de déplacement choisit l’une des quatre directions {-1,0}, {1,0}, {0,-1}, {0,1}, puis vérifie que les nouvelles coordonnées restent dans l’intervalle 0..10
    • member({Dx, Dy}, Dir) sert à choisir une direction possible
    • member(Tx, 0..10) et member(Ty, 0..10) servent à vérifier que les coordonnées restent dans les limites
    • Pour un prédicat de vérification qui n’affecte pas de valeur, on peut aussi utiliser membchk
  • Le plan résultant s’affiche comme une liste d’actions de déplacement et de nouvelles coordonnées, par exemple {move,{1,0}}, {move,{2,0}}
    • Un script Raku permet de visualiser le chemin
    • En ajoutant une condition comme {Tx, Ty} != {2, 1}, on peut aussi faire de l’évitement d’obstacles pour éviter certaines coordonnées

Plusieurs objectifs et minimisation du coût

  • Pour visiter plusieurs objectifs, Goal n’est plus une seule coordonnée, mais une file d’objectifs comme [{2, 2}, {3, 4}]
  • On ajoute une nouvelle action qui retire l’objectif correspondant de la liste lorsqu’il est atteint
    • [Head|Tail] sépare une liste en premier élément et reste de la liste
    • Goal = [Pos|Rest] n’est vrai que si la position courante Pos correspond au premier élément de la liste d’objectifs
    • Si le nouvel état est {Pos, Rest}, l’objectif atteint est supprimé
  • Le fait d’avoir visité tous les objectifs se vérifie avec final({Pos, Goal}) => Goal = [].
    • La condition d’arrêt n’est plus l’égalité entre la position courante et un objectif donné, mais le fait que la liste des objectifs soit vide
  • Imposer un ordre fixe de visite des objectifs ne produit pas toujours le plus court chemin global
  • Pour ignorer l’ordre des objectifs et minimiser le chemin total, on modifie l’action mark
    • Au lieu de Goal = [Pos|Rest], on utilise member(Pos, Goal) pour vérifier que la position courante apparaît n’importe où dans la liste des objectifs
    • To = {Pos, delete(Goal, Pos)} supprime de la liste l’objectif déjà visité
    • Avec cette approche, Picat peut choisir le prochain objectif de manière à minimiser la longueur totale du parcours

Combiner planification et résolution de contraintes

  • La fonctionnalité de planification de Picat est intégrée aux autres fonctions du langage, ce qui permet d’utiliser ensemble la planification et la résolution de contraintes
  • L’exemple du partition problem traite un problème NP-complet consistant à diviser une liste de nombres en deux groupes de somme égale
  • Le programme cherche la plus grande sous-liste de nombres que l’on peut diviser en deux sommes égales après avoir supprimé certains éléments
    • La suppression d’éléments de la liste d’entrée devient une action de planification
    • final(Numbers) vérifie si la liste de nombres donnée admet une partition valide
    • Les contraintes du module cp représentent par des variables 0..1 le fait que chaque élément appartient au groupe de gauche ou de droite
    • Une contrainte impose que la somme totale soit égale à deux fois la somme d’un des groupes
  • Dans l’exemple de sortie, après suppression de [5,17], la liste restante peut être divisée en deux groupes de somme 1108 chacun
    • 32+99+977=1108
    • 122+77+86+59+47+154+141+172+49+62+109+30=1108
  • Cette approche ne se contente pas de résoudre directement des contraintes valides : elle exprime aussi en planification les modifications nécessaires pour atteindre un état où les contraintes sont valides

Limites de Picat et cas d’usage adaptés

  • Picat étant un langage de recherche, il n’est pas recommandé pour un usage en production
  • Il offre peu de fonctionnalités de confort, ainsi qu’une documentation limitée et des messages d’erreur peu explicites
    • Lorsqu’aucun plan réalisable n’existe, l’erreur s’affiche sous la forme *** error(failed,main/0)
  • Le fait qu’il puisse s’exécuter sous Windows est considéré comme un avantage par rapport à beaucoup d’autres langages de recherche
  • Picat ressemble moins à un langage destiné à écrire du code à maintenir ou à partager qu’à un langage-boîte à outils pour résoudre certains types de problèmes de calcul
  • Certains problèmes difficiles à traiter avec un langage de programmation généraliste et un solveur de contraintes peuvent être résolus de façon assez élégante avec Picat

Autres langages de planification et concepts liés

  • La planification a d’abord été développée en robotique et en IA, mais on la rencontre aujourd’hui souvent dans l’IA de jeux vidéo sous le nom de Goal Oriented Action Planning (GOAP)
  • PDDL est un langage de description de planification utilisé comme entrée par des planificateurs indépendants
    • Il joue un rôle comparable à celui de DIMACS comme format de description en SAT

À lire aussi

1 commentaires

 
GN⁺ 2024-02-22
Avis sur Hacker News

  • J’ai utilisé le mode planification de Picat dans un vrai contexte professionnel
    J’ai prototypé un système pour coordonner la maintenance de plusieurs groupes d’équipements, et l’approche consistait à fournir « ce que l’on veut », « quelles actions sont possibles » et « quelles contraintes doivent être respectées », plutôt que « comment faire »
    Sur de petits exemples, il produisait de bons plans optimaux, mais dès que l’échelle devenait réaliste, il s’effondrait comme prévu ; les problèmes de planification relèvent au final d’EXPTIME, donc les limites étaient importantes
    Picat offre une échappatoire permettant de définir des heuristiques, et j’ai fait prédire les chemins prometteurs par une forêt aléatoire et un classificateur naïf bayésien sur les prédicats d’état, mais même avec des contraintes de rupture de symétrie et de la planification hiérarchique, cela demandait beaucoup trop d’efforts
    Il semble qu’il reste encore un hiver de l’IA dans le domaine des problèmes classiques de GOFAI
    Peut-être pas si l’on reformule le problème de planification pour qu’il renvoie un « générateur en temps polynomial produisant des plans potentiellement exponentiellement longs »

    • Les solveurs commerciaux sont nettement meilleurs que l’open source en termes de performances, et vident aussi beaucoup plus vite le portefeuille
      CPLEX, Xpress, GUROBI et Hexaly me viennent à l’esprit, Hexaly étant particulièrement bon pour la planification d’horaires ou les problèmes de tournées de véhicules
      On y accède généralement via des API pour les langages très utilisés dans l’industrie, et je trouve cette approche beaucoup plus pertinente que des langages de solveurs dédiés mais faibles pour les tâches généralistes
      Appeler GUROBI depuis Python est très simple, et on peut continuer à utiliser les fonctionnalités ordinaires de Python
      Mosek est beaucoup moins cher que GUROBI, mais les deux API sont très bas niveau, et ses performances n’égalent pas celles de GUROBI
    • Dans ce cas, quelque chose comme CP-SAT (https://developers.google.com/optimization/cp) aurait probablement bien passé à l’échelle
      Ce solveur gère facilement un nombre délirant de variables et de contraintes, et ses heuristiques intégrées sont excellentes
    • Les anciens planificateurs réduisaient l’espace de recherche avec des méta-règles ou des heuristiques choisissant quelles règles appliquer
      Certains systèmes découpaient le problème en différentes représentations et y adjoignaient des solveurs automatiques spécialisés
      Le Jahob Analysis System et Cyc me viennent à l’esprit
      Du point de vue de l’usage réel, la conception la plus propre de l’IA classique était le Procedural Reasoning System, et j’aimerais voir une version reconstruite qui compense ses faiblesses avec des méthodes modernes
      https://en.wikipedia.org/wiki/Procedural_reasoning_system
    • Je me demande pourquoi il n’existe pas de solveur open source de grande qualité
      Dans d’autres domaines du calcul numérique, l’état de l’art est souvent open source ; je me suis toujours demandé pourquoi l’optimisation faisait exception
    • Vu les résultats ou les performances, je me demande si ce n’est pas, au fond, très proche d’une recherche en profondeur d’abord écrite vite fait avec un vague souvenir de Prolog

  • Dans la communauté de la programmation par contraintes, l’utilisateur HN actif hakank, c’est-à-dire Hakan Kjellerstrand, a rassemblé de nombreuses ressources et exemples sur Picat ici : http://www.hakank.org/picat/

  • Comme d’habitude, j’ai envie de recommander Prolog
    Il est élégant, facile à comprendre, plus mature, et si l’on veut de la résolution de contraintes sur domaines finis, la configuration de base suffit déjà largement
    Par ailleurs, MiniZinc est une excellente interface vers plusieurs solveurs spécialisés pour différents objectifs ; si vous n’êtes pas spécialiste, il a de bonnes chances de vous rapprocher du résultat souhaité
    Prolog a beaucoup d’atouts, mais le « sens mécanique » nécessaire pour obtenir de bonnes performances peut vite devenir assez conséquent
    Si vous avez écrit quelque chose en Picat, il peut être utile de réfléchir à la manière dont on écrirait la même chose dans un autre langage
    Ce genre de problème jouet est facile aussi dans d’autres langages, et dans la plupart des langages fonctionnels, Dijkstra ou A* tiennent en quelques lignes ; au final, il s’agit souvent simplement de définir l’espace d’états de l’algorithme de recherche

  • J’ai été content, sans être du tout surpris, de voir Predrag parmi les relecteurs
    Le Firebase technical screen aurait sans doute été bien plus facile avec ce genre d’outil, et c’était encore un problème d’optimisation
    Ça me donne envie de le résoudre à nouveau avec Picat
    Il fait aussi des choses intéressantes côté langages de programmation : https://github.com/obi1kenobi/trustfall

  • Ma première pensée a été : « on dirait un système de types qu’il faut résoudre soi-même »
    J’ai essayé de l’exprimer naïvement en TypeScript, mais comme a, b et c pouvaient tous être identiques, rien n’était résolu
    En essayant de l’exprimer correctement, je suis arrivé à quelque chose qui semblait à peu près utilisable, mais il fallait encore des assertions, et je n’arrivais toujours pas à représenter correctement le type de Y
    Ce processus montre au contraire à quel point les programmes de style planificateur sont puissants en matière de simplicité et de concision
    TypeScript ne semble pas assez puissant pour exprimer ce genre de contraintes
    Lien TS Playground de l’expérience : http://tinyurl.com/3p2pzdtn

  • Content de voir GOAP refaire surface
    C’était l’ingrédient secret qui rendait les ennemis de F.E.A.R. si intéressants, et l’article de Jeff Orkin sur son fonctionnement est accessible et agréable à lire

  • J’utilise Prolog et un peu de CLPFD dans mon vrai travail, et c’est vraiment excellent
    J’aimerais que ce soit présent partout ; plus précisément, j’aimerais un noyau logique qui mette l’accent sur la pureté, avec les comportements impératifs repoussés aux frontières
    C’est triste de voir l’industrie coincée avec des outils aussi mauvais

  • Cela ressemble à Prolog et paraît intéressant

  • Cette manière de programmer n’est pas entièrement nouvelle
    J’ai appris Prolog à l’université, et cela semble assez similaire, mais Prolog n’avait pas de fonctionnalité de planificateur
    Cela dit, un planificateur est une manière très élégante et simple de résoudre des problèmes
    La partie sur les jeux vidéo à la fin de l’article m’a rendu curieux
    Les fonctions de planification permettent de résoudre très facilement un problème avec quelques lignes de code clair, mais quelles seraient les performances par rapport à un algorithme écrit de façon impérative ?
    Picat semble assez efficace par rapport aux langages similaires [1], mais je n’ai pas trouvé de comparaison avec des langages « standards »
    [1]: https://arxiv.org/abs/1405.2538

  • Moi aussi, je rêve de pouvoir simplement dire à l’ordinateur quel état il doit atteindre
    Je connais mal la communauté de la planification et les solveurs, et je n’ai fait que toucher naïvement à ortools, mais j’ai déjà essayé de générer du code allant d’un état à un état cible avec A*
    Il générait des instructions assembleur pour passer d’un état à l’autre et trouvait même les transitions d’état cachées des appels de fonction pour atteindre l’objectif
    Pour accélérer la recherche, je l’ai aussi exécuté en parallèle avec Python multiprocessing, et comme chaque thread générait des voisins différents, j’ai utilisé une génération dynamique des voisins
    Dans ma tentative initiale, A* était difficile à paralléliser et nécessitait du sharding
    Le rêve de mon expérience est de dire à l’ordinateur « ce que j’ai maintenant » et « ce que je veux », puis qu’il trouve lui-même le bon chemin de déplacement
    Personnellement, je vois la programmation comme quelque chose de proche de la logistique, à la Factorio ou usine
    C’est pourquoi je l’appelle « sliding puzzle » : c’est un puzzle où il faut déplacer des choses dans tous les sens pour voir la bonne image
    Dépôt GitHub et notes : https://github.com/samsquire/sliding-puzzle-codegen-memory
    Replit : https://replit.com/@Chronological/SlidingPuzzle3