Using Constraint Satisfaction Problems to solve Ai Planning Problems.
Introduction
Just like AI Planning as Satisfiability, we can use an existing technique – Constraint Satisfaction Problems to help us solve AI Planning Problems. This way we can use the existing well-developed algorithms for solving CSPs to solve our AI Planning Problems.
We will first go through the general introduction of CSPs. We then continue to see how to encode AI Planning Problems into CSPs. Finally, we use CSP Backtracking Algorithm to solve our problems. We will prove all these theories by implementing them in Python.
Constraint Satisfaction Problems
From Wikipedia,
CSPs are mathematical questions defined as a set of objects whose state must satisfy a number of constraints.
The picture depicts A CSP over finite domains. We have a set of variables – X, a set of list of domains – D, and a set of constraints – C.
Values assigned to variables in X must be one of their domain in D.
A constraint restricts the possible values of a subset of variables from X.
Example
A good example is Map Coloring Problem. You can click on the link to see the map. In that problem we have the variables which are the regions, the domains are the colors that we can assign to the variables (red, green, yellow, blue); in this example all variables have the same domains.
The constraint is that a color that is assigned to a region cannot be assigned to the adjacent regions.
CSPs on finite domains are typically resolved using some kind of search algorithms. Now that we understand what CSP on finite domains is, we can start looking into how we can encode Planning Problems into CSP.
Encoding Planning Problems into CSPs
Just like with the "Planning as Satisfiability" in which we encode the Planning Problem into the Propositional Satisfiability Problem, we can do the same with this approach.
We encode the Bounded Planning Problem – restricted Planning Problem with a fixed length of plan into a Constraint Satisfaction Problem. There are four steps to fully encode it. We will see them one-by-one below.
CSP Variables and Domains
In this first step, we want to create CSP Variables and their corresponding CSP Domains. There are two components that we need to convert into CSP Variables, they are:
- Predicates
- Actions
For predicates, we instantiate all predicates for each step. Remember that we have a fixed length of plan (k).
For example, let’s assume that we have a simple planning domain in which we only have one robot and two locations, represented in the following pddl file. And, our Bounded Planning Problem has a length of 1.
We can encode the planning domain into the following CSP Variables and Domains:
The number denotes the step, so for every step from 0 to the length of our Bounded Planning Problem, we will have all possible predicates enumerated. In this example, we have two variables in which each of them has the same Domain {loc1, loc2}.
Similarly for actions, we instantiate from step 0 to the step length-1.
For our simple domain, we only have one variable for action, which is the act(0) with two possible values in its domain. But additionally, we will need to add a no-op action (No Operation Action) to the domain. It is an action that has no preconditions nor effects.
Now, we have our CSP variables and the corresponding domains, in the next steps, we’ll have our CSP constraints.
CSP Constraints on Initial State and Goal State
In this step, we encode our initial state and goal state into CSP constraints. For our example, we’ll use a Planning Problem of the simple Planning Domain represented in the pddl file below.
In the initial state, our robot is at loc1 and in the goal state, it is at loc2. It is really simple.
Now, this step is very straightforward. We just need to convert the initial state and the goal state into unary constraints, with each affected variable assigned to a value from its domain.
This means that at step 0 the location of the robot is restricted to loc1 and at step 1 it is restricted at loc2.
CSP Constraints on Actions
In this step, we convert the actions into binary constraints. We write sets of constraints as follows.
Preconditions:
Effects:
These constraints are to make sure that the variables are assigned correctly. If act(0) has been assigned to move(rob, loc1, loc2), atl(0, rob) can only be loc1.
CSP Constraints of Frame Axioms
A Frame Axiom Constraint is to say that variables that are not explicitly modified (or also called invariants) in effects of action remain unchanged. To give an example we need to add another predicate to our Planning Domain. Say we have a new predicate loaded(r)={cont, nil} that represents whether the robot is loaded with a container or not. This predicate isn’t affected by move(r, l, m) action and so it will remain the same before and after move(r, l, m) action is executed. We represent this fact as follows.
From the example above, we state that after executing the move action the robot remains unloaded/loaded depending on its initial state.
Algorithms to solve CSPs
We now have our Bounded Planning Problem – AI Planning Problem with a fixed length k, encoded into a Constraint Satisfaction Problem. We can use the existing resolvers to solve the CSP.
If a solution exists, the solvers return assigned variables (see our CSP variables in the previous section). We are particularly interested in the Action CSP Variables for us to extract the plan.
We can then order the extracted Action CSP Variables based on the step and have our plan.
Search Algorithms to solve CSPs
A common solver is a backtracking search algorithm such as the one below.
This algorithm is quite simple. It receives the partial solution in σ and the unassigned variables in X.
If all variables have been assigned, that means we have our solution and the algorithm returns the σ.
Otherwise, it will select one variable to assign a value to it. Then it proceeds to remove values that are not consistent from the Domain, D.
It then assigns a value to it, it then calls itself recursively. If it fails at some point, it will backtrack and choose another value at "choose vi ∈ Di".
It will be easier to read when we implement this algorithm in Python.
Conclusion and Code in Python
In this post, we learned how we can use the existing technique – CSPs, to find a solution plan to a Planning Problem by encoding our Classical Planning Problem representation into a Bounded Planning Problem and into a Constraint Satisfaction Problem.
We then use the classic CSP Backtracking Algorithm to solve our CSP.
One limitation of this approach is that we need to specify the length of the plan, which means we may need to try several times before knowing whether or not a solution plan to our problem exists.
I have written the encoding and CSP Backtracking algorithm in Python. The CSP Backtracking algorithm was taken from the following link:
…because I find it is easier to understand and implement the CSP constraints using functions instead of sets of tuples like in the algorithm in the previous section.
If you’re interested in the code, get it from here: