Un paradigme déclaratif de résolution de problèmes où les problèmes de recherche sont encodés en programmes logiques dont les modèles stables (ensembles de réponses) correspondent aux solutions ; la négation par défaut et les constructions non monotones expriment alternatives et contraintes de façon concise.

Principe

Encoder contraintes, choix combinatoires et défauts sous forme de règles afin que la sémantique des modèles stables sélectionne des sous-ensembles de littéraux auto-cohérents ; la résolution revient au calcul des modèles stables d'un programme mis à la terre fini.

Démonstration

Encodage du problème de 3-coloration d'un graphe : des règles attribuent nondéterministement des couleurs aux sommets, des contraintes interdisent aux sommets adjacents de partager une couleur, et chaque modèle stable représente une coloration valide.

Mauvaise application

Utiliser une mise à la terre naïve sans tenir compte de la taille du domaine provoque une explosion combinatoire, ou modéliser des problèmes de optimisation numérique continue sans extensions appropriées, abusant ainsi du cadre discret des modèles stables.

Conséquence

Utilisé à bon escient, ASP permet des encodages compacts pour des problèmes combinatoires difficiles, exprime facilement défauts et exceptions, et profite de solveurs de modèles stables efficaces pour le prototypage et le raisonnement rapide.

Inversion

Inverser vers la recherche de modèles classiques ou un encodage SAT où les modèles sont des modèles propositionnels classiques plutôt que des modèles stables ; on perd alors le raisonnement non monotone par défaut qui caractérise ASP.

Limite

Particulièrement adapté aux espaces de recherche finis et discrets et aux problèmes combinatoires ; il exclut les domaines continus ou les problèmes nécessitant des algorithmes numériques itératifs procéduraux sans hybridation avec d'autres solveurs.

Tension sémantique

Tensions avec des paradigmes connexes (SAT, programmation par contraintes) : ASP met l'accent sur la représentation non monotone et les multiples ensembles de réponses comme solutions, tandis que SAT/CP privilégient la satisfiabilité propositionnelle ou des domaines de contraintes avec des compromis opérationnels différents.

Synthèse

La programmation par ensembles de réponses est une manière déclarative de représenter recherche et raisonnement par défaut de sorte que le calcul des modèles stables fournit les solutions : elle échange le contrôle procédural contre des encodages à base de règles interprétés sous une sémantique non monotone.