Answer Set Programming: Into the Multiverse

What? Why?

  • Practical logic programming
  • Expressive; easy to model search problems
  • Fast enough to be used in the Real World

Search problems?

Abstractly,

  • A search space (and a way to navigate it)
  • A goal

e.g. solving puzzles

  • Search space: game states
  • Goal: winning state

Milos Hauskrecht

e.g. procedural generation

  • Search space: all fully-connected maps
  • Goal: a map traversable in n steps

A Map Generation Speedrun with Answer Set Programming, 2011

Answer Set Programming for Procedural Content Generation: A Design Space Approach, 2011

e.g. algorithmic composition

  • Search space: all sequences of notes
  • Goal: melodies which abide by the so-called “Palestrina rules” for Renaissance music
The composition of most styles of music is governed by rules... by formalising these rules in a suitable logical language, powerful and expressive intelligent composition tools can be easily built.

Automatic Music Composition using Answer Set Programming, 2010

e.g. dependency resolution

  • Search space: all possible package configurations
  • Goal: a set of package versions which satisfies all dependency constraints

aspcud

e.g. PI Planning

  • Search space: all possible plans (ticket-sprint assignments)
  • Goal: a plan subject to lots of unspoken constraints…

Automating Continuous Planning in SAFe, 2020

“Optimized brute force”

Appropriate when:

  • brute force is the best one can do (NP-hard)
  • domain isn’t fully understood; rapid prototyping > asymptotics
  • constraints are nontrivial and would eventually require search

Programming

“Generate and test”

  • Define search space
  • Remove unwanted parts

“Generate and Test”

Trial and error is also a heuristic method of problem solving, repair, tuning, or obtaining knowledge. In the field of computer science, the method is called generate and test (Brute force). In elementary algebra, when solving equations, it is guess and check.

Trial and error, Wikipedia

“Guess and Check”

There are 15 puppies and birds at a pet shop. There are 42 legs altogether. How many puppies are there?

Learn Guess and Check, practicle.sg

Facts

animal(puppy).
animal(bird).

legs(puppy,4).
legs(bird,2).

animal_n(1..15).

Rules

bipedal(A) :- animal(A), legs(A,2).

“A thing A is bipedal if it is a two-legged animal.”

Answer Sets

bipedal(A) :- animal(A), legs(A,2).

$ clingo animals.lp
clingo version 5.4.0
Reading from animals.lp
Solving...
Answer: 1
animal_n(1) animal_n(2) animal_n(3) animal_n(4) animal_n(5) animal_n(6) animal_n(7) animal_n(8) animal_n(9) animal_n(10) animal_n(11) animal_n(12) animal_n(13) animal_n(14) animal_n(15) legs(puppy,4) legs(bird,2) animal(puppy) animal(bird) bipedal(bird)
SATISFIABLE

Models       : 1
Calls        : 1
Time         : 0.024s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.001s

Choice Rules

Define search space, or “possible worlds”: 

animal(bird).
{ animal(puppy) }.

$ clingo animals.lp
clingo version 5.4.0
Reading from animals.lp
Solving...
Answer: 1
animal(bird)
Answer: 2
animal(bird) animal(puppy)
SATISFIABLE

Models       : 2
Calls        : 1
Time         : 0.021s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.001s

Choice Rules

Generate every possible pet shop… all \(2^{15}\) of them: 

{ animal_at_shop(A, N) : animal(A) } = 1 :- animal_n(N).

SATISFIABLE
Models       : 32768
Calls        : 1
Time         : 3.294s (Solving: 3.27s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.249s

Integrity Constraints

Remove possible worlds: 

animal(bird).
{ animal(puppy) }.
:- animal(puppy).

$ clingo -n 0 animals.lp
clingo version 5.4.0
Reading from animals.lp
Solving...
Answer: 1
animal(bird)
SATISFIABLE

Models       : 1
Calls        : 1
Time         : 0.013s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.001s

Integrity Constraints

Remove every world without the right number of legs: 

correct_number_of_legs :- legs_total(42).
:- not correct_number_of_legs.

Aggregates

legs_total(L) :-
  L = #sum { N,M : animal_at_shop(A, M), legs(A, N) }.

animal_count(A,N) :-
  N = #count { M : animal_at_shop(A, M) }, animal(A).

Directives

#show animal_count/2.
#project animal_count(A,N).

#minimize { D : unassigned_count(D) }.

Putting it all together

animal(puppy;bird).
legs(puppy,4).
legs(bird,2).
animal_n(1..15).
{ animal_at_shop(A, N) : animal(A) } = 1 :- animal_n(N).
correct_number_of_legs :- legs_total(42).
:- not correct_number_of_legs.
legs_total(L) :- L = #sum { N,M : animal_at_shop(A, M), legs(A, N) }.
animal_count(A,N) :- N = #count { M : animal_at_shop(A, M) }, animal(A).
#show animal_count/2.
#project animal_count(A,N).

Running

$ clingo -n 0 animals.lp --project
clingo version 5.4.0
Reading from animals.lp
Solving...
Answer: 1
animal_count(puppy,6) animal_count(bird,9)
SATISFIABLE

Models       : 1
Calls        : 1
Time         : 0.271s (Solving: 0.26s 1st Model: 0.00s Unsat: 0.26s)
CPU Time     : 0.268s

“Generate and Test”

  • Define search space using facts, rules, and aggregates
  • Remove unwanted parts using integrity constraints

PI Planning + ASP

Facts

sprint(1..1).
story(1..2).

story_weight(2,1).
story_depends_on(1,2).
sprint_capacity(1,1).

Assignments

Each story is assigned to exactly one sprint: 

{ assign(T,S) : sprint(S) } = 1 :- story(T).

Sprint Capacity

Sum story weights, grouping by assigned sprint: 

sprint_total(S,To) :-
  To = #sum { W,T : story_weight(T,W), assign(T,S) }, sprint(S).

Sprint Capacity

The sum of story weights cannot exceed sprint capacity, unless they’re unassigned: 

sprint(unassigned).

:- sprint_total(S,A), sprint(S),
  sprint_capacity(S,E), A > E, S != unassigned.

Optimization

unassigned_count(D) :- D = #count { T : assign(T,unassigned) }.
#minimize { D : unassigned_count(D) }.

Dependencies

Given a story dependency, the dependent story cannot be assigned to a later sprint than its dependency: 

:- assign(T1,S1), assign(T2,S2),
  story_depends_on(T1,T2), S1 < S2.

Pins

Story 1 must always be assigned to sprint 2: 

:- not assign(1,2).

Design Choices

  • Don’t solve for assignments globally
  • Don’t solve on keypress…
  • Where to run solver?
  • Intuitiveness of assignments?
  • Unstated constraints

Generating Stories

Generating Stories

Then suddenly, he was struck by a powerful but simple little truth, and it was this: That English grammar is governed by rules that are almost mathematical in their strictness! Given the words, and given the sense of what is to be said, then there is only one correct order in which those words can be arranged. Therefore, it stands to reason that an engine built along the lines of the electric computer could be adjusted to arrange words (instead of numbers) in their right order according to the rules of grammar. Then feed it with plots and leave it to write the sentences.

The Great Automatic Grammatizator, 1998

The Event Calculus

  • Logical representation of actions and their effects
  • “How do we represent time?”

A Logic-based Calculus of Events, 1986

Key ideas

  • Index rules by time
  • Keep track of events which happen
  • Keep track of the effects of events, i.e. what is now known about the world

Adam's minimal event calculus formalism

Time

#const t_max=15.
time(0..t_max).
  • Abstract unit of time
  • Simulate t_max time points

Events

Events happen only under specific conditions 

{ happens(T,E) } :- time(T), possible(T,E).

Only one event happens at a time 

:- time(T), not { happens(T,E) } = 1.

Effects of Events

Facts hold as a result of things happening 

initiated(T,F) :- happens(T,E), initiates(T,E,F).
holds(T+1,F) :- time(T), happens(T,E), initiates(T,E,F).

Facts are inertial; they continue to hold without external influence 

terminated(T,F) :- happens(T,E), terminates(T,E,F).
holds(T+1,F) :- time(T), holds(T,F), not terminated(T,F).

Authoring

  • Events: possible, initiates, terminates
  • Static knowledge
  • Dynamic knowledge
  • Constraints

Let’s make a Disney movie

Static Knowledge

character(rey).
character(kylo).
character(palpatine).

Places

place(pasaana).
place(kijimi).
place(endor).
place(exegol).
place(resistance_base).
place(tatooine).

always_reachable(resistance_base,pasaana).
always_reachable(pasaana,kijimi).
always_reachable(kijimi,endor).
always_reachable(exegol,endor).
always_reachable(exegol,kijimi).
always_reachable(exegol,tatooine).

Dynamic Knowledge

holds(0,reachable(P1,P2)) :- always_reachable(P1,P2),
  place(P1), place(P2).

Dynamic Knowledge

holds(0,at(kylo,exegol)).
holds(0,at(rey,resistance_base)).
holds(0,at(palpatine,exegol)).

holds(0,alive(C)) :- character(C).

Moving around

possible(T,moves(C,P1,P2)) :-
  holds(T,at(C,P1)), not holds(T,at(C,P2)),
  holds(T,reachable(P1,P2)),
  holds(T,alive(C)),
  character(C), place(P1), place(P2).
initiates(T,moves(C,P1,P2),at(C,P2)) :-
  possible(T,moves(C,P1,P2)).
terminates(T,moves(C,P1,P2),at(C,P1)) :-
  possible(T,moves(C,P1,P2)).

Trying it out

$ clingo disney.lp
clingo version 5.4.0
Reading from disney.lp
Solving...
Answer: 1
happens(0,moves(kylo,exegol,pasaana)) happens(2,moves(rey,resistance_base,pasaana)) happens(3,moves(palpatine,exegol,tatooine)) happens(1,moves(kylo,pasaana,endor)) happens(4,moves(kylo,endor,tatooine)) happens(5,moves(kylo,tatooine,exegol))
SATISFIABLE

Models       : 1+
Calls        : 1
Time         : 0.021s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.021s

Trying it out

happens(0,moves(rey,resistance_base,pasaana))
happens(1,moves(rey,pasaana,kijimi))
happens(2,moves(rey,kijimi,endor))
happens(3,moves(palpatine,exegol,kijimi))
happens(4,moves(kylo,exegol,kijimi))
happens(5,moves(palpatine,kijimi,endor))

Wayfinding

item(wayfinder).

holds(0,has(endor,wayfinder)).

possible(T,finds(C,I,P)) :-
  holds(T,at(C,P)),
  not holds(T,has(C,I)), holds(T,has(P,I)),
  holds(T,alive(C)),
  character(C), item(I), place(P), time(T).
initiates(T,finds(C,I,P),has(C,I)) :- possible(T,finds(C,I,P)).
terminates(T,finds(C,I,P),has(P,I)) :- possible(T,finds(C,I,P)).

Wayfinding

happens(0,moves(kylo,exegol,endor))
happens(1,moves(palpatine,exegol,endor))
happens(2,finds(palpatine,wayfinder,endor))
happens(3,moves(rey,resistance_base,pasaana))

MacGuffins

holds(T,reachable(P,exegol)) :-
  holds(T-1, has(rey,wayfinder)), time(T), place(P).

No one goes into Exegol until then…

MacGuffins

happens(0,moves(rey,resistance_base,pasaana))
happens(1,moves(rey,pasaana,kijimi))
happens(2,moves(rey,kijimi,endor))
happens(3,finds(rey,wayfinder,endor))
happens(4,moves(palpatine,exegol,endor))
happens(5,moves(rey,endor,exegol))

Not from a Jedi

side(light).
side(dark).

holds(0,alignment(rey,light)).
holds(0,alignment(kylo,dark)).
holds(0,alignment(palpatine,dark)).

Not from a Jedi

possible(T,turns(C1,C2,S1,S2)) :-
  holds(T,alignment(C2,S1)), not holds(T,alignment(C2,S2)),
  holds(T,at(C1,P)), holds(T,at(C2,P)),
  holds(T,alignment(C1,S2)),
  holds(T,alive(C1)), holds(T,alive(C2)),
  place(P), character(C1), character(C2), side(S1), side(S2).
initiates(T,turns(C1,C2,S1,S2),alignment(C2,S2)) :-
  possible(T,turns(C1,C2,S1,S2)).
terminates(T,turns(C1,C2,S1,S2),alignment(C2,S1)) :-
  possible(T,turns(C1,C2,S1,S2)).

Not from a Jedi

happens(0,moves(rey,resistance_base,pasaana))
happens(1,moves(rey,pasaana,kijimi))
happens(2,moves(rey,kijimi,endor))
happens(3,moves(palpatine,exegol,endor))
happens(4,moves(kylo,exegol,endor))
happens(5,turns(palpatine,rey,light,dark))

Lightsabers

possible(T,lightsaber_duel(C1,C2)) :-
  C1 != C2,
  holds(T,alignment(C1,S1)), holds(T,alignment(C2,S2)), S1 != S2,
  holds(T,at(C1,P)), holds(T,at(C2,P)),
  holds(T,alive(C1)), holds(T,alive(C2)),
  place(P), character(C1), character(C2),
  side(S1), side(S2), time(T).
terminates(T,lightsaber_duel(C1,C2),alive(C2)) :-
  possible(T,lightsaber_duel(C1,C2)).

Lightsabers

climax :- happens(T,lightsaber_duel(C1,C2)),
  character(C1), character(C2).
:- not climax.

rey_reaches_exegol :- holds(t_max+1,at(rey,exegol)).
:- not rey_reaches_exegol.

turn :- happens(T,turns(C1,C2,S1,S2)),
  character(C1), character(C2), side(S1), side(S2).
:- not turn.

Lightsabers

happens(0,moves(rey,resistance_base,pasaana))
happens(1,moves(kylo,exegol,kijimi))
happens(2,moves(rey,pasaana,kijimi))
happens(3,moves(palpatine,exegol,kijimi))
happens(4,turns(rey,palpatine,dark,light))
happens(5,lightsaber_duel(rey,kylo))

Plot Point Reversal

{ pick_reason(T,plot_point_reversal(C,R)) : reason(R) } = 1 :-
  character(C), time(T).

possible(T,plot_point_reversal(C,R)) :-
  not holds(T,alive(C)),
  pick_reason(T,plot_point_reversal(C,R)),
  place(P), character(C), time(T).
initiates(T,plot_point_reversal(C,R),alive(C)) :-
  possible(T,plot_point_reversal(C,R)).

Plot Point Reversal

anticlimax :- happens(T,plot_point_reversal(C,R)),
  character(C), reason(R).
:- not anticlimax.

Generated Plot

happens(0,moves(palpatine,exegol,tatooine))
happens(1,moves(kylo,exegol,endor))
happens(2,moves(rey,resistance_base,pasaana))
happens(3,moves(rey,pasaana,kijimi))
happens(4,moves(rey,kijimi,endor))
happens(5,lightsaber_duel(kylo,rey))
happens(6,plot_point_reversal(rey,it_was_all_a_dream))
happens(7,lightsaber_duel(kylo,rey))
happens(8,plot_point_reversal(rey,the_dark_side_of_the_force_is_a_pathway_to_many_abilities_some_consider_to_be_unnatural))
happens(9,finds(rey,wayfinder,endor))
happens(10,turns(rey,kylo,dark,light))
happens(11,moves(kylo,endor,exegol))
happens(12,moves(kylo,exegol,tatooine))
happens(13,lightsaber_duel(palpatine,kylo))
happens(14,moves(rey,endor,exegol))
happens(15,moves(palpatine,tatooine,exegol))

Another

happens(0,moves(rey,resistance_base,pasaana))
happens(1,moves(rey,pasaana,kijimi))
happens(2,moves(rey,kijimi,endor))
happens(3,finds(rey,wayfinder,endor))
happens(4,moves(kylo,exegol,endor))
happens(5,moves(rey,endor,exegol))
happens(6,moves(rey,exegol,kijimi))
happens(7,moves(rey,kijimi,exegol))
happens(8,moves(kylo,endor,exegol))
happens(9,lightsaber_duel(rey,kylo))
happens(10,lightsaber_duel(rey,palpatine))
happens(11,plot_point_reversal(kylo,it_was_a_hologram))
happens(12,moves(rey,exegol,tatooine))
happens(13,plot_point_reversal(palpatine,it_was_a_hologram))
happens(14,moves(rey,tatooine,exegol))
happens(15,turns(rey,palpatine,dark,light))

Story generation + ASP

  • Tabula rasa generation: explore plot space
  • Constrained generation: touch on given plot points
  • Finish a partial story

RoleModel: Towards a Formal Model of Dramatic Roles for Story Generation

Can we really generate stories?

Yes, but expect lots of writing...

Potpourri

  • Performance
  • Random sampling
  • Debugging
  • Ecosystem

clingo runs forever!

  • Variables are replaced with concrete values before any solving starts (“grounding”)
  • Wide relations will cause blowup
  • Denormalize
  • More efficient encodings

Random sampling

--rand-freq=1 --seed=39403

Debugging

Solving...
UNSATISFIABLE

Models       : 0

Debugging

Removing a goal can make a predicate at most more general, never more specific.

Declarative Debugging, The Power of Prolog

Debugging

  • Bisect program!
  • Give names to integrity constraints so invalid worlds can be inspected
  • Unfortunately, have to modify program

Ecosystem

Limitations

“Declarative”

  • Small changes can drastically affect performance
  • Correctness is not obvious
  • Translations of imperative concepts can be difficult
  • Unfamiliar

Black box

  • By design
  • Efficient encodings are hard for non-experts
  • No e.g. global constraints

Reflection

  • Useful for a class of problems
  • Rapid prototyping
  • Nice formalism that works in practice

Further Reading