Satisfaction de contrainte ouverte ou interactive

17

Dans le passé, j'ai implémenté des modèles de coordination utilisant SAT et la satisfaction des contraintes régulières comme cheval de bataille principal dans leurs moteurs. Poursuivant dans cette ligne de travail, je voudrais rendre les modèles plus interactifs, et la meilleure façon que je vois de le faire est d'ouvrir le solveur de contraintes afin qu'il ne soit plus une boîte noire.

Ainsi, je souhaite en savoir plus sur la satisfaction des contraintes lorsque les contraintes ont ce que j'appellerai des variables externes , des prédicats et des fonctions , c'est-à-dire que le langage de contraintes peut avoir des prédicats tels que qui ne peuvent être que satisfait en consultant un agent extérieur au solveur, et seulement lorsque est à la masse. Un scénario où cela est utile est chaque fois que correspond à un processus de décision externe qui ne peut pas être incorporé dans le solveur de contraintes. De tels solveurs de contraintes pourraient être appelés ouverts (car les contraintes ne sont pas entièrement connues) ou interactifs.P(X)XP (car une interaction est nécessaire pour procéder avec satisfaction aux contraintes).

Je voudrais connaître les deux:

  • recherches théoriques effectuées dans ce sens
  • des outils ou des bibliothèques qui implémentent des solveurs de contraintes qui permettent une interaction avec le monde extérieur pendant le processus de résolution de contraintes.
Dave Clarke
la source

Réponses:

9

Je ne suis pas tout à fait convaincu par les travaux précédents sur les contraintes ouvertes et interactives.

Une tentative pour étudier les questions de tractabilité était:

bien que ce document laisse plusieurs questions importantes sans réponse. L'approche via les propagateurs dans cet article est étroitement liée aux implémentations existantes du solveur de contraintes.

Je pense que les travaux sur les théories SMT (satisfiability modulo) sont également étroitement liés à votre question. Les théories SMT sont souvent motivées par des problèmes de vérification des logiciels et du matériel, mais il existe des théories avec une saveur IA. J'ai hâte de voir plus d'applications construites avec SMT comme technologie de base et de travailler davantage sur les contraintes en appliquant les idées de SMT.

András Salamon
la source
1
Ce document semble certainement intéressant. Je n'ai jamais pensé aux solveurs SMT comme faisant ce dont j'avais besoin. C'est certainement une avenue à explorer.
Dave Clarke
Je suis confus par le dernier commentaire. Les solveurs SMT sont destinés aux logiques et aux théories, et non aux prédicats spécifiques. Les gens sont invités à apporter de nouvelles théories et références. Je sais que les développeurs MathSAT ont étudié l'IA et les problèmes de planification.
Vijay D
@Vijay D: vous avez raison, cette phrase est indûment biaisée et je la réviserai. Une mise en œuvre efficace d'INJECTIVE en tant que théorie SMT a été publiée en 2010 par Banković et Marić ( argo.matf.bg.ac.rs/publications/2010/alldiff-smt2010.pdf ).
András Salamon
7

En lisant votre question, je suis également d'accord pour dire que les théories de Modulo sur la satisfaction sont étroitement liées à vos besoins. Je suggérerais de lire le livre Decision Procedures - An Algorithmic Point of View .

Giorgio Camerani
la source
Dans quelle mesure le livre The Calculus of Computation: Decision Procedures with Applications to Verification est-il lié / utile par Aaron R. Bradley et Zohar Manna? Je sais où une copie de cela est accessible à pied.
Dave Clarke
@Dave: Disclaimer: Mon expérience personnelle sur SMT n'est qu'au tout début ;-) Je viens de regarder la table des matières de ce livre; il semble y avoir une grande intersection entre celui-ci et celui que j'ai indiqué. Dans ce dernier, ce que vous appelez ici les fonctions externes est appelé là les fonctions non interprétées et est largement couvert. Je n'ai pas pu trouver de fonctions non interprétées dans la table des matières des procédures de décision avec demandes de vérification ; cependant, il semble que ce soit un très bon livre et peut-être qu'il peut s'avérer utile.
Giorgio Camerani
@Dave: De nos jours, je lis les procédures de décision - un point de vue algorithmique . Je n'ai pas encore atteint le chapitre sur les fonctions non interprétées , mais si je ne me trompe pas, les formules avec fonctions non interprétées sont converties en formules dans la théorie de l'égalité. Il est vrai que la théorie de l'égalité est traitée dans les procédures de décision avec demandes de vérification (chapitre 9).
Giorgio Camerani
1
Je pense qu'Amazon appelle.
Dave Clarke
@Dave: OK, excellent! ;-)
Giorgio Camerani
7

P(X)

Evgenij Thorstensen
la source
4

Je suis un peu confus au sujet du terme interactif. Je vais carillon avec les autres et ajouter qu'un solveur SMT pourrait être utile. Pour ajouter au commentaire de Walter Bishop, des diapositives pour le livre sur les procédures de décision (Kroening et Strichman) sont disponibles. Le traitement approfondi de John Harrison dans Handbook of Practical Logic and Automated Reasoning peut également vous intéresser. Un exemple de code est disponible en ligne.

La princesse de Philipp Ruemmer prend en charge l'arithmétique avec des prédicats non interprétés, qui pourraient correspondre à ce que vous entendez par ouvert. Il est écrit en Scala, utilise la correspondance E pour gérer la quantification et fournit des interpolants.

Vijay D
la source
0

Qu'en est-il des outils, si vous décidez de vous Prolog comme langue de choix, je peux vous suggérer quelques approches d'implémentation:

  • GNU Prolog avec sa bibliothèque de programmation C. Vous pouvez appeler les fonctions C à partir de Prolog et Prolog à partir de C. Cela vous ouvre de nombreuses possibilités d'extension des fonctionnalités. Pro: Gnu Prolog est l'un des compilateurs Prolog les plus rapides et disponibles gratuitement. Remarque: Certaines personnes se plaignent du manque de prédicats intégrés ... en fait, la plupart d'entre eux peuvent être implémentés, consultez les couches de compatibilité Prolog @SO
  • SWI-Prolog possède une bibliothèque de programmation intéressante, y compris la communication réseau, la prise en charge des tampons de protocole, etc. Et est très populaire.
  • XSB Prolog certaines personnes affirment que c'est le projet le plus intéressant en termes d'interopérabilité - y compris: interfaces de bases de données, etc.

Prolog est un langage de programmation, qui convient à de nombreux types de solveurs (et la plupart d'entre eux ont leurs solveurs à domaine fini).

Grzegorz Wierzowiecki
la source