AIspace

Practice Exercise 8.C

STRIPS to CSP

1: Background Reading

2: A Simple Planning Problem

In the first section we are going to look at a simple planning problem. We want to get from home to UBC, going either by car or by bike. Going by car or bike depends on having a car or bike. How might we represent this problem using the STRIPS representation? Before moving on to the next step, write your STRIPS representation, specifying the variables, actions, pre-conditions and post-conditions.

Open the STRIPS to CSP tool and load the file http://www.aispace.org/exercises/simpleCommuting.xml by clicking File → Load from URL. Does this representation match your STRIPS representation above? How do we represent our goal in this representation?

Make a hypothesis about how this STRIPS representation might be represented as a CSP. Write down your hypothesized CSP.

Click on the 'Solve' tab in the applet. The horizon value will be set to 1 by default. You can leave it there for now. Click on 'Solve with Arc Consistency.'
This opens a new applet for solving CSPs with arc consistency. Examine the CSP. Does it match your hypothesized CSP representation?
In the new applet, click on the solve tab.
To carry out arc consistency, you can either click 'Auto Arc-Consistency' or step through the process by clicking the 'Step' button.

If any values were removed from any variable's domain during arc consistency, explain why the values were removed.

Make a prediction about how many solutions, if any, will be found.
Click 'AutoSolve' to recursively apply arc consistency and domain-splitting until a solution is found. Pressing this again will find another solution, and so on.

Were any solutions found? Can you think of any advantages of the CSP representation over the STRIPS representation?

3: A More Complex Planning Problem

In our first example above, our problem was very simple. We needed to get to UBC, we had two actions available to us, and both actions were feasible (haveBike and haveCar were 'true'). Either choice would bring us to the correct location. We will now explore a more complex example.

Open the STRIPS to CSP tool and load the file http://www.aispace.org/exercises/complexCommuting.xml by clicking File → Load from URL.

Examining the STRIPS representation that was loaded, describe the represented scenario in plain English (e.g. what the actions are and what conditions must hold for an action to be possible). Describe how you imagine the STRIPS problem could be represented as a CSP. How will the preconditions and postconditions be represented? What are the domains of the action variables?

Click the 'Solve' tab and select 'Solve with Arc Consistency'. Keep the Horizon at 1.
Examine the CSP representation in the new applet window. Does it match your expectations?
Make sure the following variables have these values at the start: haveBusTicket is false, flatTire is true, haveBike is true, haveGas is false, haveCar is true, and haveMoney is true.
Switch to the 'Solve' tab.
Click 'Auto Arc-Consistency'.
Does arc consistency remove any values? What happens when you press 'AutoSolve' now?
Go back to the original 'STRIPS to CSP' applet and change the Horizon to 2. Then re-do the previous steps.

Is a solution now found? Explain what happened.

4: CSP Planning

If our goal is not just to get to UBC but to satisfy some other constraint while getting to UBC, how might we represent this? For example, what if we want to get to UBC and to minimize our impact on the environment at the same time? Give a CSP representation for this.

Open the consistency for CSP tool and load the file http://www.aispace.org/exercises/CSPcommuting.xml by clicking File → Load from URL.

In the 'Create' tab, you will see a careAboutEnvironment constraint in the upper right. Right click this to set the properties of the constraint. What do the three options here represent?
Select 'same' and make sure that 'aLittleWorse' and 'muchWorse' are not selected.
Move to the 'Solve' tab and click 'Auto Arc-Consistency.'
What is the solution? How many possible solutions are there? Explain why.