Week 3 - Forward chaining, RPG

Given a domain, how do we solve a problem?

With forward-chain planning or RPG

What is forward-chain planning?

A method of automated planning where we choose some state s and expand on it until we reach the goal state

What state do we always start from in forward-chain planning?

From the initial state

When we expand on a state in forward-chain planning, what do we do?

Choose from the set of applicable actions in that state

How do we get the set of applicable actions in a state?

We find all actions whose preconditions are satisfied in the given state

How do we generate the successor state s’ after applying an action α in state s?

s’ = s - {delete effects of α} + {add effects of α}

How do we create a plan for successor state s’ after applying action α in state s?

Chain action α onto the end of the plan for state s

What is the plan generated by forward-chain planning?

A sequence of actions from the set of all domain actions A that transform the initial state to the goal state

What is domain-independent planning?

Planning where the defined heuristics work for any PDDL domain

How can domain-independent planning be achieved?

Through RPG

What does RPG stand for?

Relaxed Planning Graph

What is RPG?

A planner that finds a plan from the current state S that achieves goals G while ignoring the delete effects of each action

What is the structure of an RPG?

Alternating fact and action layers

What is a fact layer in an RPG?

• Defines the state at time n

• Determines which actions’ preconditions are satisfied in f(n) and can appear in the action layer a(n+1)

For a fact layer f(n) and action layer a(n+1), how can we define the next fact layer f(n+1)?

f(n+1) = f(n) + all add effects of actions in a(n+1)

What is the plan generated by RPG called?

Relaxed solution plan

What is defined in a relaxed solution plan?

A collection where each element at index i is the set of actions selected in parallel at time step i

What is the heuristic function of an RPG?

The sum of the magnitude of all elements in a relaxed solution plan

How can we extract a solution from an RPG?

1. Work backwards through the RPG

2. Start with g(n) which contains the problem’s goal

3. For each fact in g(n),

   1. If it was in f(n-1), add it to g(n-1)

   2. Else choose an action from a(n) and add its' preconditions to g(n-1)

4. Stop when we reach g(0)