Answer Set Programming: Logic Programming with Stable Models

Introduction

Answer Set Programming (ASP) is a declarative programming paradigm based on logic programming with stable model semantics. ASP combines the expressiveness of logic programming with the ability to handle non-monotonic reasoning and disjunctive information. This article explores ASP fundamentals, semantics, and applications.

Historical Context

Answer Set Programming emerged in the 1990s from work on stable model semantics by Gelfond and Lifschitz. ASP combines logic programming with non-monotonic reasoning, enabling more expressive knowledge representation. Modern ASP systems like Clingo handle complex problems efficiently.

ASP Basics

Programs

ASP Program: Set of rules and facts

Rule Format: head :- body

Example:

bird(X) :- animal(X), has_wings(X).
flies(X) :- bird(X), not abnormal(X).
abnormal(X) :- penguin(X).

Stable Models

Definition: Stable model is a minimal model consistent with the program

Intuition: Model that “justifies” itself

Example:

Program:
  a :- not b.
  b :- not a.

Stable models: {a} and {b}
(Both are self-justifying)

Semantics

Negation as Failure

Semantics: ¬P is true if P cannot be proved

Difference from classical negation: Doesn’t assume closed world

Example:

Program:
  bird(tweety).
  flies(X) :- bird(X), not penguin(X).

Query: flies(tweety)?
Answer: Yes (penguin(tweety) cannot be proved)

Disjunction

Syntax: a | b :- c

Meaning: If c is true, then a or b (or both) must be true

Example:

Program:
  {a; b} :- c.
  c.

Stable models: {c, a}, {c, b}, {c, a, b}

ASP Applications

Knowledge Representation

Application: Represent knowledge with defaults and exceptions

Example:

bird(tweety).
penguin(tweety).

flies(X) :- bird(X), not penguin(X).

Planning

Application: Generate plans achieving goals

Example:

action(move(X, Y)) :- location(X), location(Y), X != Y.
goal(at(robot, goal_location)).

Diagnosis

Application: Diagnose faults from symptoms

Example:

fault(component1) :- symptom(s1), not fault(component2).
fault(component2) :- symptom(s2), not fault(component1).

Constraint Solving

Application: Solve constraint satisfaction problems

Example:

color(X, C) :- node(X), color_set(C), not other_color(X, C).
other_color(X, C) :- color(X, C'), C != C'.

ASP Systems

Clingo

Features: Grounding and solving Strengths: Fast, handles large programs Applications: Industrial problems

DLV

Features: Logic programming with stable models Strengths: Expressive, good for knowledge representation Applications: Knowledge representation, reasoning

Practical Example: Graph Coloring

Problem

Task: Color graph nodes with k colors, no adjacent nodes same color

ASP Solution

% Input: node(1..n), edge(X,Y)
% Parameters: k colors

% Generate: assign color to each node
{color(X, C) : color_set(C)} = 1 :- node(X).

% Test: no adjacent nodes have same color
:- edge(X, Y), color(X, C), color(Y, C).

% Define colors
color_set(1..k).

Execution

Input: 
  node(1..3).
  edge(1,2).
  edge(2,3).
  edge(1,3).
  k = 3.

Stable models:
  {color(1,1), color(2,2), color(3,3)}
  {color(1,1), color(2,3), color(3,2)}
  ... (other valid colorings)

Glossary

Answer Set: Stable model of program ASP: Answer Set Programming Constraint: Rule that must be satisfied Disjunction: Choice between alternatives Negation as Failure: ¬P true if P cannot be proved Stable Model: Self-justifying model Grounding: Converting program to ground form

Practice Problems

Problem 1: Write ASP program for “Typically birds fly, but penguins don’t”.

Solution:

bird(tweety).
penguin(tweety).

flies(X) :- bird(X), not penguin(X).

Problem 2: Write ASP program for N-queens problem.

Solution:

{queen(X, Y) : column(Y)} = 1 :- row(X).
:- queen(X1, Y), queen(X2, Y), X1 < X2.
:- queen(X1, Y1), queen(X2, Y2), X1 < X2, |Y1 - Y2| = |X1 - X2|.

Problem 3: Explain stable model semantics.

Solution: A stable model is a minimal model that is consistent with the program and “justifies” itself. It represents a possible world where the program’s rules are satisfied.

Related Resources

• Answer Set Programming: https://en.wikipedia.org/wiki/Answer_set_programming
• Stable Model Semantics: https://en.wikipedia.org/wiki/Stable_model_semantics
• Clingo: https://potassco.org/clingo/
• DLV: http://www.dlvsystem.com/
• Logic Programming: https://en.wikipedia.org/wiki/Logic_programming
• Prolog: https://en.wikipedia.org/wiki/Prolog
• Declarative Programming: https://en.wikipedia.org/wiki/Declarative_programming
• Knowledge Representation: https://en.wikipedia.org/wiki/Knowledge_representation_and_reasoning
• Non-Monotonic Reasoning: https://en.wikipedia.org/wiki/Non-monotonic_logic
• Constraint Satisfaction: https://en.wikipedia.org/wiki/Constraint_satisfaction_problem
• Automated Reasoning: https://en.wikipedia.org/wiki/Automated_reasoning
• Formal Methods: https://plato.stanford.edu/entries/formal-methods/
• Artificial Intelligence: https://en.wikipedia.org/wiki/Artificial_intelligence
• Planning: https://en.wikipedia.org/wiki/Automated_planning_and_scheduling
• Diagnosis: https://en.wikipedia.org/wiki/Diagnosis

Conclusion

Answer Set Programming provides a powerful declarative approach to knowledge representation and reasoning. By combining logic programming with stable model semantics, ASP enables expressive representation of knowledge with defaults, exceptions, and disjunctive information.

Understanding ASP is essential for anyone working with knowledge representation, planning, or constraint solving. The combination of logic programming with non-monotonic reasoning creates powerful systems for complex reasoning tasks.