ASP-20 | AI Planning
Answer Set Programming's declarative nature makes it ideal for AI planning problems — computing sequences of actions that transform an initial state into a desired goal state. Rather than procedurally coding how to reach a goal, we describe what makes valid states and actions, letting ASP find viable paths.Photo Credit: Rob Grzywinski
Modeling Change in ASP
ASP programs are inherently static — once a fact is added it can't be removed or changed. But the real world isn't static. Things change over time — temperatures rise and fall, objects move from place to place, systems switch between states. How can we model these dynamics while maintaining ASP's declarative nature?Time as a Relation
Instead of writing:temperature(50) .
we can write:temperatureΔ(50, 0) .
This reads "the temperature is 50 at time 0". We are relating a temperature to a particular instant, just as we might relate it to a location or any other property. This approach of modeling time explicitly is so useful in AI planning that these time-aware predicates have their own name: fluents.(It's also common to encode fluents using auxiliary predicates in a process called reification. For example, instead of writing temperature(50, 1) which reads "the temperature is 50 at time 1", one could write holds(temperature(50), 1) which reads "the temperature is 50 holds at time 1". This allows for potentially conflicting statements at the same time.)
Inertia
The concept of inertia is brought over from physics. Think of Newton's 1st law of motion: an object at rest tends to stay at rest and an object in motion tends to stay in motion. The same goes for fluents: a fluent that holds at a time step will hold at the subsequent time steps.Using a recursion relation, we can state that the temperature at the next instant is the same:temperatureΔ(T, I+1) ← temperatureΔ(T, I) .
Since it is common to have other elements that start with the letter t (such as "temperature"), we use I for "instant" rather than T for "time" in our variables.It is not recommended that you run (2) and (3) alone since there is no limit on time!
Horizon
It is best to define a time horizon to provide an upper-bound for how many instants the fluents will be available for:#const horizon = 4 .
The constant can then be used in conjunction with (2) and (3) to bound the fluent to that horizon:temperatureΔ(T, I+1) ← temperatureΔ(T, I), I < horizon .
{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 |
| 3 | 50 |
| 4 | 50 |
} horizon) and a number!)Notice how the instant is shown in the first column of the temperatureΔ/2 answer set with a Grouped Table. Any predicate suffixed with "Δ" that has at least an arity of one will show the last argument (the instant) in this way. This will become very helpful later when multiple predicates are combined in the same table.
Inertia and Changes
Our simple definition of inertia works great when nothing changes. But real systems aren't static — values change over time! Let's see what happens when we try to change the temperature:temperatureΔ(50, 0) . % Initial temperature is 50
temperatureΔ(52, 2) . % Temperature changes to 52 at instant 2
Using our basic inertia rule (5) results in {| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 | 52 |
| 3 | 50 | 52 |
| 4 | 50 | 52 |
} temperatureΔ(T, I+1) ←
temperatureΔ(T, I),
not not temperatureΔ(T, I+1),
I < horizon .
This rule reads: "the temperature at instant I + 1 is T if it was T at instant I and there is no evidence that it is not T at instant I + 1". (The first "not" is read "there is no evidence" and the second one is read "not T at instant I + 1".)Running this new version produces multiple answer sets:{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 | 52 |
| 3 | 50 | 52 |
| 4 | 50 | 52 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 | 52 |
| 3 | 50 |
| 4 | 50 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 | 52 |
| 3 | 50 | 52 |
| 4 | 50 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 | 52 |
| 3 | 50 | 52 |
| 4 | 52 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 | 52 |
| 3 | 50 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 | 52 |
| 3 | 50 | 52 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 | 52 |
| 3 | 52 |
| 4 | 52 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 | 52 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 | 52 |
| 3 | 52 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | |
| 2 | 52 |
| 3 | 52 |
| 4 | 52 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 52 |
| 3 | 52 |
| 4 | 52 |
}{}{}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | |
| 2 | 52 |
| 3 | 52 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 52 |
| 3 | 52 |
} { temperatureΔ(T, I+1) } ←
temperatureΔ(T, I),
I < horizon .
{}{}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | |
| 2 | 52 |
| 3 | 52 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | |
| 2 | 52 |
| 3 | 52 |
| 4 | 52 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 52 |
| 3 | 52 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 52 |
| 3 | 52 |
| 4 | 52 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 | 52 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 | 52 |
| 3 | 52 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 | 52 |
| 3 | 52 |
| 4 | 52 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 | 52 |
| 3 | 50 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 | 52 |
| 3 | 50 | 52 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 | 52 |
| 3 | 50 | 52 |
| 4 | 52 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 | 52 |
| 3 | 50 |
| 4 | 50 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 | 52 |
| 3 | 50 | 52 |
| 4 | 50 |
}{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 | 52 |
| 3 | 50 | 52 |
| 4 | 50 | 52 |
}
Existence and Uniqueness
Just as energy cannot be created or destroyed but only transformed, a fluent's value must exist and be unique at each instant. It can't spontaneously appear, disappear, or exist in multiple states simultaneously. Said another way: the value of a fluent must exist and be unique at each instant.⊥ ← #count{ T : temperatureΔ(T, I) } != 1,
I = 0..horizon .
{| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 50 |
| 3 | 50 |
| 4 | 50 |
} I = 1..horizon must be used rather than I <= horizon. The easiest way to remember this is that the ".." operator is expanded into separate rules during the grounding phase which means that (9) is equivalent to:⊥ ← #count{ T : temperatureΔ(T, 0) } != 1 .
⊥ ← #count{ T : temperatureΔ(T, 1) } != 1 .
⊥ ← #count{ T : temperatureΔ(T, 2) } != 1 .
⊥ ← #count{ T : temperatureΔ(T, 3) } != 1 .
⊥ ← #count{ T : temperatureΔ(T, 4) } != 1 .
which is what is desired. When starting out in ASP, this will trip you up many times and the "unsafe variable" warning for the solver will remind you.
Actions and Effects
In the previous section we showed that we can have a value (a fluent) and it can change with time. But we haven't addressed how these changes happen. They're caused by actions.Actions
Actions are symbols whose presence changes the value of a fluent. In Charm they use the "Ω" suffix. Actions take one time step and their effect occurs in the next instanttemperatureΔ(T, I+1) ← % Effect seen at I+1
changeΩ(T, I), % Action occurs at instant I
I < horizon .
The temperature is T at instant I + 1 if changeΩ/2 exists at instant I.To change the temperature:temperatureΔ(50, 0) .
changeΩ(52, 1) .
Notice that we wrote changeΩ(52, 1) rather than changeΩ(52, 2). The action occurs at instant I and the effect occurs at instant I + 1. {| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 52 |
| 3 | 52 |
| 4 | 52 |
} - Initial states (
temperature = 50 at instant 0) - When actions occur (change to 52 at instant 1)
- When effects manifest (temperature becomes 52 at instant 2)
- How inertia maintains values (52 persists through instants 3 and 4)
The grouped table format becomes even more valuable as we add multiple fluents and actions — it provides a clear timeline of how the system evolves.
Unique Actions
It is common that only a single action should occur in any instant:⊥ ← #count{ T : changeΩ(T, I) } > 1, I = 0..horizon .
If more than one action were to occur then the result is unsatisfiable.temperatureΔ(50, 0) .
changeΩ(52, 1) . changeΩ(53, 1) .
If multiple actions occur in different instants then the changes occur:temperatureΔ(50, 0) .
changeΩ(52, 1) .
changeΩ(53, 3) .
{| i | changeΩ/2 |
|---|
| 0 → 1 | |
| 1 → 2 | 52 |
| 2 → 3 | |
| 3 → 4 | 53 |
| i | temperatureΔ/2 |
|---|
| 0 | 50 |
| 1 | 50 |
| 2 | 52 |
| 3 | 52 |
| 4 | 53 |
}
Convenience Predicates
Notice that the expression I = 0..horizon was used many times. We can refactor this into its own predicate:always(I) ← I = 0..horizon .
This allows us to rewrite the unique-action constraint as:⊥ ← #count{ T : changeΩ(T, I) } > 1, always(I) .
It also reads much more easily (likely in the same way that you were thinking while you were writing it)!The expression I < horizon was also used multiple times. Notice that the maximum time instant is the horizon and that the "latest" that an action can be applied is the instant before the horizon. This means that we should have been writing I < horizon-1 since inertia always produces the next instant.next(I) ← I = 0..horizon-1 .
This allows us to refactor inertia:{ temperatureΔ(T, I+1) } ← temperatureΔ(T, I), next(I) .
Planning with ASP
Planning problems involve finding a sequence of actions that transform an initial state into a desired goal state. Let's extend our temperature example to demonstrate basic planning concepts.- Initial State: We start at a specific temperature:
temperatureΔ(20, 0) . % Start at 20°
- Available Actions: At each time step, we can choose to increase or decrease the temperature by 1°:
{ upΩ(I); downΩ(I) } = 1 ← next(I) .
The choice rule ensures exactly one action occurs at each instant. - Action Effects: Actions change the temperature in the next instant:
temperatureΔ(T+1, I+1) ← temperatureΔ(T,I), upΩ(I), next(I) .
temperatureΔ(T-1, I+1) ← temperatureΔ(T,I), downΩ(I), next(I) .
- Inertia: If no action occurs, the temperature stays the same:
temperatureΔ(T,I+1) ←
temperatureΔ(T,I),
not upΩ(I), not downΩ(I),
next(I) .
- State Constraints: Each instant must have exactly one temperature:
⊥ ← #count{ T : temperatureΔ(T, I) } != 1, always(I) .
- Goal State: We want to reach exactly 23° by the end:
⊥ ← not temperatureΔ(23, horizon) .
Exploring Different Horizons
Let's examine how the horizon affects plan generation:- Too Short (
horizon = 2): Need at least 3 steps to reach 23° from 20°Results in unsatisfiable since it's impossible to reach 23° from 20° in just 2 steps when we can only change by 1° per step. - Minimum Required (
horizon = 3): Exactly enough steps{| i | upΩ/1 |
|---|
| 0 → 1 | true |
| 1 → 2 | true |
| 2 → 3 | true |
| i | temperatureΔ/2 |
|---|
| 0 | 20 |
| 1 | 21 |
| 2 | 22 |
| 3 | 23 |
} - Even Numbers (
horizon = 4): Interestingly, this is unsatisfiable!This reveals something profound about our problem structure — we need an odd number of steps. Why? We start at 20° and need to reach 23° — that's a difference of 3°. Since we can only change by ±1° per step, and each step must include an action, we need exactly 3 steps to reach our goal. Any even number of steps would either overshoot or undershoot the target. - Extra Steps (
horizon = 5): With more steps than minimally required, we get multiple valid plans that include "detours" while still reaching the goal:{| i | downΩ/1 | upΩ/1 |
|---|
| 0 → 1 | | true |
| 1 → 2 | | true |
| 2 → 3 | | true |
| 3 → 4 | | true |
| 4 → 5 | true | |
| i | temperatureΔ/2 |
|---|
| 0 | 20 |
| 1 | 21 |
| 2 | 22 |
| 3 | 23 |
| 4 | 24 |
| 5 | 23 |
}{| i | downΩ/1 | upΩ/1 |
|---|
| 0 → 1 | | true |
| 1 → 2 | | true |
| 2 → 3 | true | |
| 3 → 4 | | true |
| 4 → 5 | | true |
| i | temperatureΔ/2 |
|---|
| 0 | 20 |
| 1 | 21 |
| 2 | 22 |
| 3 | 21 |
| 4 | 22 |
| 5 | 23 |
}{| i | downΩ/1 | upΩ/1 |
|---|
| 0 → 1 | | true |
| 1 → 2 | true | |
| 2 → 3 | | true |
| 3 → 4 | | true |
| 4 → 5 | | true |
| i | temperatureΔ/2 |
|---|
| 0 | 20 |
| 1 | 21 |
| 2 | 20 |
| 3 | 21 |
| 4 | 22 |
| 5 | 23 |
}{| i | downΩ/1 | upΩ/1 |
|---|
| 0 → 1 | true | |
| 1 → 2 | | true |
| 2 → 3 | | true |
| 3 → 4 | | true |
| 4 → 5 | | true |
| i | temperatureΔ/2 |
|---|
| 0 | 20 |
| 1 | 19 |
| 2 | 20 |
| 3 | 21 |
| 4 | 22 |
| 5 | 23 |
}{| i | downΩ/1 | upΩ/1 |
|---|
| 0 → 1 | | true |
| 1 → 2 | | true |
| 2 → 3 | | true |
| 3 → 4 | true | |
| 4 → 5 | | true |
| i | temperatureΔ/2 |
|---|
| 0 | 20 |
| 1 | 21 |
| 2 | 22 |
| 3 | 23 |
| 4 | 22 |
| 5 | 23 |
}
From Simple Steps to Complex Systems
While adjusting a thermostat might seem far removed from real-world software challenges, this example demonstrates all the essential elements of planning problems:- State Representation: Using fluents to track how system properties change over time
- Action Effects: Defining how operations transform the system state
- Constraints: Enforcing rules about valid states and transitions
- Goal Conditions: Specifying what we want to achieve
These same building blocks let us tackle much more complex scenarios like finding deadlocks in concurrent systems, validating deployment procedures, or generating test sequences that exercise specific edge cases.The real power comes from ASP's ability to find all valid plans. Rather than just getting one solution that works, we can explore the full space of possibilities. This is invaluable when analyzing failure modes in distributed systems, understanding race conditions in concurrent code, or discovering edge cases in business workflows.For larger problems, we can use incremental planning — gradually increasing the horizon until we find a solution. This lets us discover the shortest path to our goal without having to guess the right horizon in advance.The next time you're staring at a whiteboard trying to reason about complex state transitions, remember: you're not limited to what you can juggle in your head. ASP can systematically explore the possibilities, revealing paths you might never have considered. Whether you're designing protocols, debugging concurrency, or validating business rules, planning with ASP transforms daunting complexity into manageable logic.
Appendix
References
- Levenshtein in Blocks World: String Matching via AI Planning
- Answer Set Programming (Draft)
- ASP planning tools for PDDL
- Fluent
- Reification ("the process of turning a predicate or statement into an addressable object. Reification allows the representation of assertions so that they can be referred to or qualified by other assertions, i.e., meta-knowledge.")
- Computing programs for generalized planning using a classical planner
- An Overview of the International Planning Competition Part 1: Classical Tracks
- International Planning Competition 2023 (Competitions)
