Ein deklaratives Problemlösungsparadigma, bei dem Suchprobleme als logische Programme kodiert werden, deren stabile Modelle (Answer Sets) den Lösungen entsprechen; nichtmonotone Konstrukte und Default-Negation drücken Alternativen und Nebenbedingungen kompakt aus.

Prinzip

Constraints, kombinatorische Wahlmöglichkeiten und Defaults als Regeln kodieren, sodass die Stable-Model-Semantik selbstkonsistente Teilmengen von Literalen auswählt; das Lösen besteht im Berechnen stabiler Modelle eines endlich geerdeten Programms.

Demonstration

Kodierung der 3-Färbung eines Graphen: Regeln ordnen nondeterministisch Farben den Knoten zu, Constraints verbieten angrenzenden Knoten dieselbe Farbe, und jedes stabile Modell entspricht einer gültigen Färbungslösung.

Fehlanwendung

Naive Grounding ohne Berücksichtigung der Domänengröße führt zu kombinatorischem Explosionsverhalten, oder die Modellierung inhärent numerischer, kontinuierlicher Optimierungsprobleme ohne geeignete Erweiterungen missbraucht ASPs diskreten Stable-Model-Rahmen.

Konsequenz

Korrekt eingesetzt liefert ASP kompakte Kodierungen für harte kombinatorische Suchprobleme, erlaubt die Darstellung von Defaults und Ausnahmen und profitiert von effizienten Stable-Model-Solvern für schnelles Prototyping und Schlussfolgern.

Umkehrung

Umkehr zu klassischer Modellsuche oder SAT-Kodierungen, bei denen Modelle klassische propositionale Modelle sind statt stabiler Modelle; dadurch entfällt das nichtmonotone Default-Rational, das ASP charakterisiert.

Abgrenzung

Am wirksamsten für endliche, diskrete Suchräume und kombinatorische Probleme; schließt kontinuierliche Domänen oder Probleme aus, die prozedurale numerische Algorithmen benötigen, sofern nicht mit anderen Solver-Hybridisierungen erweitert.

Semantische Spannung

Spannungen zu verwandten Paradigmen (SAT, Constraint Programming): ASP betont nichtmonotone Wissensrepräsentation und multiple Answer Sets als Lösungen, während SAT/CP auf propositionale Erfüllbarkeit bzw. Constraints mit anderen betrieblichen Abwägungen fokussieren.

Synthese

Answer-Set-Programmierung ist eine deklarative Darstellung von Suche und Default-Rational, sodass das Berechnen stabiler Modelle Lösungen liefert: sie ersetzt prozedurale Steuerung durch regelbasierte Kodierungen unter nichtmonotoner Semantik.