ASP-07 | Choice Rules
Choice rules extend ASP's expressivity by allowing controlled generation of multiple answer sets through explicit enumeration of possibilities.Photo Credit: Rob Grzywinski
Choice Rules
Most of the programs that we've worked with so far have had a single answer set. We encountered multiple answer sets when we had a disjunction of atoms in a fact. This concept is going to be expanded with choice rules.{ p(1) ; q(2) } .
Choice rules wrap an expression in curly braces ("{" and "}") and provide a way to define a set of candidate solutions. They provide a way to generate and explore multiple possible solutions by explicitly enumerating combinations of atoms that could be true. Unlike disjunctive rules which force an either-or choice, choice rules say "here are some atoms that may be true in any combination." The result of (1) is { }{q(2)}{p(1)}{p(1)q(2)}
p(1) ; q(2) .
which results in . An empty choice rule:{ } .
results in the empty set () as does the truth values{ ⊤ } .
and{ ⊥ } .
. (These last two results will make more sense once conditional literals are introduced.)A choice rule results in all possible combinations of atoms including the empty set whereas a disjunction contains simply either-or. Note that this intentionally directly conflicts with the fact that answer sets are always the minimal set of atoms required to satisfy the rules. (See "Just the Facts ...|Answer Sets" for reference.) Choice rules explicitly introduce answer sets that would otherwise not be available.Pooling and Intervals
Pooling can be used with choice rules:{ p(1 ; 2 ; 3) } .
which is equivalent to { p(1) ; p(2) ; p(3) } and results in: { }{p(2)}{p(3)}{p(2) p(3)}{p(1)}{p(1) p(3)}{p(1) p(2)}{p(1) p(2) p(3)}
{ p(1..3) } .
which is also equivalent to { p(1) ; p(2) ; p(3) } and results in:{ }{p(2)}{p(3)}{p(2) p(3)}{p(1)}{p(1) p(3)}{p(1) p(2)}{p(1) p(2) p(3)}
Cardinality Constraints
An integer placed before the curly brace constrains the number of elements in the answer set to be at least the specified value:1 { p(1..4) } .
{}{}{}{}{}{}{}{}{}{}{}{}{}{}{} { p(1..4) } 2 .
Both constraints may be used at the same time:1 { p(1..4) } 2 .
If the bounds are inverted:2 { p(1..4) } 1 .
then the result is unsatisfiable ().Both constraints may be the same value:2 { p(1..4) } 2 .
which returns sets that have exactly that number of elements . There is shorthand for this last case since it occurs often:{ p(1..4) } = 2 .
Remember that this is a constraint and not an assignment.Having insufficient atoms for the cardinality constraint:{ p(1) } = 2 .
results in unsatisfiable ().Using both upper and/or lower bounds with the "=" operator:1 { p(1..4) } 2 = 3 .
results in an error ().
Multiple Choice Rules
A program may contain multiple choice rules:{ p } .
{ q } .
Each choice rule contributes either the empty set or itself. Together the result is all combinations . Notice that this is the same result as:{ p ; q } .
It is easy to get confused when working with cardinality constraints. Look at the rules below and think about what answer sets you expect before looking at the result{ p } = 1 .
{ q } = 1 .
The result is ! Did you expect two answer sets with one atom each? The individual cardinality constraints limits the contribution of that rule to the answer sets. In this case, { } and { p q } are both eliminated because they don't have a cardinality of 1. That leaves the following:p .
q .
which we know has the result of .Cardinality constraints expand how powerful and flexible choice rules are:{ p ; q } = 1 .
{ a } .
.Variables
Variables can be used with choice rules:{ p(X) } ← X = 1..2 .
The interval can be expanded:{ p(X) } ← X = 1 .
{ p(X) } ← X = 2 .
and the variable substituted:{ p(1) } .
{ p(2) } .
which results in { }{p(2)}{p(1)}{p(1) p(2)}
{ p(1) ; p(2) } .
{ p(1 ; 2) } .
{ p(1..2) } .
{ }{p(2)}{p(1)}{p(1) p(2)}
{ }{p(2)}{p(1)}{p(1) p(2)}
{ }{p(2)}{p(1)}{p(1) p(2)}
{ p(X) } ← X = 1..2 .
{ p(X) : X = 1..2 } .
{ p(1..2) } .
{ p(1 ; 2) } .
{ p(1) ; p(2) } .
{ p(1) } . { p(2) } .
Cardinality Constraints
The previous section showed that there were may ways to write the same rule but things get a bit more complicated when cardinality constraints are used:{ p(X) } = 1 ← X = 1..2 .
The cardinality constraint reduces the result to . Hopefully this result didn't surprise you. (If it did, look back at the [Multiple Choice Rules] section above.)Rules that combine cardinality constraints with intervals and variables can be a challenge to visually parse given multiple "=" operators. Locate the arrow ("←") and remember that everything to the left is the head and to the right is the body. You cannot nest the arrow in any way so use it as your starting point when reading rules. The head is a choice rule with a cardinality constraint and the body is the variable X that belongs to the set comprised of the numbers defined by the interval. If you're ever lost, simply expand a few rules to a grounded state which has no variables.{ p(X) } = 1 ← X = 1 .
{ p(X) } = 1 ← X = 2 .
Substituting the variable value:{ p(1) } = 1 .
{ p(2) } = 1 .
This is the same as:p(1) .
p(2) .
which gives the expected result of .More Cardinality Constraints
Let's increase the complexity of the rule a bit:{ p(X) ; q(X) } = 1 ← X = 1..2 .
Expanding the interval leads to:{ p(X) ; q(X) } = 1 ← X = 1 .
{ p(X) ; q(X) } = 1 ← X = 2 .
This can be further reduced to:{ p(1) ; q(1) } = 1 .
{ p(2) ; q(2) } = 1 .
and results in {p(1)q(2)}{p(1) p(2)}{q(1) q(2)}{p(2)q(1)}
More Examples
The next rule adds even more complexity:{ p(1..2, X) } = 1 ← X = 1..2 .
As always, if you get lost, just start expanding or grounding (substituting) until you get your legs back under you. In this case, we can choose to do either and it leads to the same result (which is the power of declarative programming!).Grounding the variable first:{ p(1..2, X) } = 1 ← X = 1 .
{ p(1..2, X) } = 1 ← X = 2 .
leads to predicates similar to what we already saw in [Numbers and Math|Rules and Variables]:{ p(1..2, 1) } = 1 .
{ p(1..2, 2) } = 1 .
where we can now expand the interval:{ p(1, 1) ; p(2, 1) } = 1 .
{ p(1, 2) ; p(2, 2) } = 1 .
which results in .Or expanding the interval first:{ p(1, X) ; p(2, X) } = 1 ← X = 1..2 .
then grounding the variable:{ p(1, X) ; p(2, X) } = 1 ← X = 1 .
{ p(1, X) ; p(2, X) } = 1 ← X = 2 .
and finally substituting its value:{ p(1, 1) ; p(2, 1) } = 1 .
{ p(1, 2) ; p(2, 2) } = 1 .
results in .
A Note on Expansion
While we've shown various expansions of rules to help understand how ASP processes them, it's important to note that you never need to perform these expansions manually in practice. We've demonstrated these step-by-step transformations solely to demystify how ASP interprets and processes complex rules with variables, intervals, and cardinality constraints.The power of declarative programming with ASP lies precisely in the fact that you can express your intent at a high level, letting the solver handle all the intricate details of grounding and finding stable models. The solver automatically performs all necessary expansions and optimizations far more efficiently than manual expansion would allow.This understanding of the expansion process is valuable for:- Debugging complex rules
- Understanding why certain answer sets are produced
- Writing more efficient and maintainable programs
- Predicting what answer sets to expect
But in day-to-day ASP programming, you'll work directly with the high-level expressions, leveraging the full power of variables, intervals, and constraints without concerning yourself with the underlying expansion process.
