La programmation planner, une surprise

Les fonctionnalités quasi magiques du langage de programmation Picat

• Picat est un langage de recherche qui tente de combiner la programmation logique, la programmation impérative et la résolution de contraintes.
• Le module planner de Picat est l’un des modèles de programmation les plus intéressants.

Brève explication de la programmation logique

• En programmation impérative et fonctionnelle, on écrit des algorithmes qui prennent des entrées et produisent des sorties.
• En programmation logique et en résolution de contraintes, on fournit une série d’équations et on cherche une affectation qui satisfait ces relations.

Définition du problème

• Il faut résoudre un problème de placement de marqueur sur une grille, avec un déplacement du point de départ (l’origine) vers une coordonnée cible.
• À chaque étape, on peut se déplacer d’une case dans l’un des quatre sens cardinales, sans dépasser les limites de la grille.
• Le programme réussit lorsque le marqueur se trouve sur la coordonnée cible.

Première implémentation

• Il faut fournir l’état initial Start, une suite de fonctions action représentant les transitions d’état, et la fonction final(S) qui détermine les états finaux.
• En appelant best_plan(Start, Plan), la séquence d’étapes la plus courte nécessaire pour atteindre un état final est assignée à Plan.

Ajouter plusieurs objectifs

• Le planner doit atteindre tous les objectifs dans l’ordre.
• On ajoute une nouvelle fonction action qui supprime de la file l’objectif dès que celui-ci est atteint.

Minimiser le coût

• Atteindre les objectifs dans l’ordre ne signifie pas forcément un chemin total minimal.
• Si l’on veut obtenir le plus court chemin global sans contrainte d’ordre sur les objectifs, on peut modifier action pour permettre au planner de choisir le prochain objectif afin de minimiser la longueur totale du chemin.

Variantes supplémentaires

• Picat prend en charge de nombreuses variantes de planification.
• best_plan(S, Limit, Plan) limite le coût maximum à Limit.
• sequence(P, Action) limite les actions possibles en fonction de la partie actuelle du plan.

Utilisation de Picat

• Picat est un langage de recherche et manque de certaines commodités, comme une bonne documentation ou des messages d’erreur clairs.
• Picat est plus utile en tant que langage « outil » pour apprendre à résoudre certains problèmes de calcul.

Annexe : autres langages de planification

• La « planification » a été développée pour la robotique et l’IA, mais elle est surtout utilisée dans l’IA des jeux vidéo comme GOAP (Goal-Oriented Action Planning).
• PDDL est un langage de description de planification utilisé en entrée d’un planner autonome.

Opinion de GN⁺

• Innovation de modèle de programmation : le module planner de Picat ajoute une nouvelle dimension à la programmation, notamment pour les problèmes complexes de recherche de chemin.
• Valeur pédagogique : Picat est important du point de vue pédagogique en programmation; il peut aider à apprendre les concepts de programmation logique et de résolution de contraintes.
• Résolution de problèmes spécifiques : Picat a de la valeur comme langage outil pour résoudre certains problèmes de calcul, offrant une approche nouvelle pour des problèmes difficiles à traiter avec un langage de programmation général.

[GN⁺]

Commentaires Hacker News

• Cas d'utilisation concrets du mode de planification de Picat

  • Développement d'un prototype de système pour la maintenance d'équipements
  • Donner au système ce que l'on veut plutôt que de lui indiquer comment l'atteindre
  • Génération d'un plan optimal avec Picat
  • Des problèmes de scalabilité sont apparus lors du passage à grande échelle
  • La planification étant de complexité EXPTIME, la scalabilité a donc une limite attendue
  • Malgré la définition d'heuristiques, d'un classifieur Naive Bayes et de contraintes de symétrie, il faut encore beaucoup de maintenance
  • Sur les domaines classiques de la GOFAI, on est encore dans un "hiver de l'IA"

• Informations sur les ressources et exemples Picat

  • Le site web de Hakan Kjellerstrand, membre actif de la communauté de programmation par contraintes, propose des ressources et des exemples sur Picat

• Recommandations de Prolog et de MiniZinc

  • Prolog est un langage facile à comprendre et mature, avec des capacités de résolution de contraintes
  • MiniZinc offre une interface pour accéder à des solveurs spécialisés pour différents usages
  • Il faut une bonne compréhension de Prolog pour en tirer de meilleures performances
  • Il est recommandé de réfléchir à la possibilité de réécrire facilement le même code dans un autre langage après l'avoir écrit en Picat

• Commentaire lié à l'entretien technique Firebase

  • Un entretien technique Firebase serait plus simple avec des outils comme Picat
  • Bonne surprise de voir apparaître Predrag comme reviewer

• Comparaison entre système de types et langages de programmation

  • Similaire au système de types de TypeScript, mais il faut résoudre les contraintes soi-même
  • TypeScript n'est pas assez puissant pour exprimer des contraintes
  • Mise en avant de la concision et de la simplicité de la programmation de style planificateur

• Mention du GOAP (Goal-Oriented Action Planning)

  • GOAP, utilisé pour améliorer l'IA ennemie du jeu F.E.A.R.
  • Le papier de Jeff Orkin sur le GOAP est jugé facile à lire et intéressant

• Évaluation des capacités de planification de Picat

  • Picat, proche de Prolog, auquel on a ajouté des fonctions de planification
  • La fonctionnalité de planification permet de résoudre des problèmes simplement, mais les performances doivent être comparées à celles de la programmation impérative

• Le rêve de donner l'état final à l'ordinateur pour le laisser trouver la solution

  • Utilisation de l'algorithme A* pour la génération de code et les transitions d'état
  • Peu d'expérience avec les communautés/solveurs de planification, mais expérimentations avec or-tools
  • Concevoir la programmation comme de la logistique, avec une analogie du « puzzle glissant »

• Remarque supplémentaire sur la syntaxe proche de Prolog

  • Utilise une syntaxe proche de Prolog et propose de terminer par true. comme solution plus élégante que comma first

Ce résumé reflète les opinions variées de plusieurs personnes et transmet chaque point de vue de manière neutre. Les éléments techniques liés aux langages de programmation y sont expliqués de façon concise pour un ingénieur logiciel débutant.