Answer Set Programming (ASP) ist ein deklarativer Ansatz zur Lösung komplexer kombinatorischer Suchprobleme. Er basiert auf der Logikprogrammierung und der Semantik stabiler Modelle. Anders als bei Prolog, das anfragebasiert arbeitet, ist ASP modellbasiert. Dies bedeutet, dass das Problem durch Fakten und Regeln beschrieben wird, und der Solver berechnet alle "Answer Sets" (stabile Modelle), die diese Regeln erfüllen. Jedes Answer Set entspricht dabei einer gültigen Lösung des Problems[1].
Da ASP-Regeln oft Variablen enthalten (z. B. movable(A, T, ...) :- vehicle(A, ...)), müssen diese zunächst in eine variablenfreie Form übersetzt werden. Diesen Prozess nennt man Grounding. Der Grounder ersetzt systematisch alle Variablen in den Regeln durch alle möglichen Konstanten aus den Fakten.
Beispiel: Wenn es die Fakten time(1..2) und vehicle(car1) gibt, wird aus der Regel: moved(V, T) :- vehicle(V), time(T). durch Grounding eine Menge von konkreten Instanzen: moved(car1, 1) :- vehicle(car1), time(1). und moved(car1, 2) :- vehicle(car1), time(2).
Ein potenzielles Problem hierbei ist eine kombinatorische Explosion von Instanzen, die Auftritt, wenn der Wertebereich der Variablen zu groß ist[1:1].
Wikipedia contributors. (n.d.). Answer Set Programming. In Wikipedia. Retrieved January 15, 2025, from https://en.wikipedia.org/wiki/Answer_set_programming ↩︎ ↩︎