The Blocks World

lecture08-part2-task-planning-representation-algorithms-0.pdf

Constant symbols for concrete things:

The blocks: a, b, c, d, e

Predicates to represent conditions:

• ontable(x) - block x is on the table
• on(x,y) - block x is on block y
• clear(x) - block x has nothing on it
• holding(x) - the robot hand is holding block x
• handempty - the robot hand isn’t holding anything

Predicates have the form predicate-symbol(arguments).

States

a set of ground predicates

• Represents the conditions or facts that are true in that state.
• Since we have only a finite no. of predicates and a finite no. of constant symbols, we have only a finite no. of possible states.

$s1=ontable(a),ontable(b),ontable(e),on(c,a),clear(c),clear(b),clear(e),holding(d)$
Closed world assumption: What is not known to be true is assumed to be false.

Operators

Operators are generalizations of actions.

Operator: a triple o=(name(o), precond(o), effects(o))

• precond(o): preconditions
  • Predicates and their negations that must be true in order to use the operator.
• effects(o): effects
  • Predicates and their negations that the operator will make true.
• name(o): a syntactic expression of the form n(x1 ,…,xk )
  • n is an operator symbol - must be unique for each operator.
  • (x1 ,…,xk ) is a list of every variable symbol (parameter) that appears in o.

Rather than writing each operator as a triple, we’ll usually write like this:

pickup(x)   
	;; gripper picks up block x from the top of the table   
	Precond: ontable(x), clear(x), handempty   
	Effects: not ontable(x), not clear(x), not handempty, holding(x)  

Actions

An action is a ground instance (via substitution) of an operator

• Suppose we substitute x with b.
• Then we get the following action:
• pickup(b)
  • precond: ontable(b), clear(b), handempty
  • effects: not ontable(b), not clear(b), not handempty, holding(b)

i.e., The robot’s gripper picks up block b off the table.

Notation

Let a be an operator or action. Then

• precond+ (a) = {predicates that appear positively in a’s preconditions}

• precond– (a) = {predicates that appear negatively in a’s preconditions}

• effects+ (a) = {predicates that appear positively in a’s effects}

• effects– (a) = {predicates that appear negatively in a’s effects}

Example:

pickup(b)   
	precond: ontable(b), clear(b), handempty   
	effects: not ontable(b), not clear(b), not handempty, holding(b)   

• precond+ (pickup(b)) = {ontable(b), clear(b), handempty}

• precond- (pickup(b)) = {}

• effects+ (pickup(b)) = {holding(b)}

• effects– (pickup(b)) = {ontable(b), clear(b), handempty)}

Executing an Applicable Action

Goal

a set of ground predicates or its negations

• Represents the conditions that should hold in a goal state.
• Positive goal conditions should be present in the goal state and negavite goal conditions should be absent in the goal state.

goal = {on(b,c), on(a,b)}

Solutions

Planner

Given a planning domain and a planning problem, how can the robot autonomously find a plan, i.e. a sequence of actions, in order to go from the initial state to a state that satisfies the goal?
Algorithms that do this are called planners.

Three Main Types of Planners

Domain-specific planners

• Made or tuned for a specific planning domain 
• Most successful real-world planning systems work this way (Mars exploration, sheet metal bending, playing bridge, etc.)
• Won’t work well (if at all) in other planning domains

Domain-independent planners ⇒ focus of most research

• In principle, works in any planning domain
• In practice, need restrictions on what kind of planning domains it can be applied
• e.g. Classical Task Planning

Configurable planners

• Domain-independent planning engine
• Input includes info about how to solve problems in some domain

Link to original

Restrictive Assumptions in Classical Task Planning

A0: Finite system:

Finite no. of states and actions.

A1: Fully observable:

The agent always knows the current state of the world.

A2: Deterministic: Each action has only one outcome.

If an action is applied to a state, it will bring the world to a single new state.

A3: Static (no exogenous events):

Changes to the world state can be caused only through the agent‘s own actions.

A4: Attainment goals:

Goal is specified explicitly and corresponds to a set of goal states Sg .

A5: Sequential plans:

A plan is a linearly ordered sequence of actions (a1 , a2 , … an ).

A6: Implicit time:

No time durations; a linear sequence of instantaneous states and actions.

A7: Off-line planning:

Planner doesn’t know the execution status of the plan while it is generating the plan.

Link to original

Planning is Searching…

• Nearly all planning procedures are search procedures.
• In this lecture, we will look at state-space planning, which is used by classical task planners.

  • Similar to path planning algorithms.

  • Here, each node represents a state of the world.

  • Finds a path that starts at the initial state and ends at a goal state.

Forward Search

Forward-search is sound

Any plan that is returned is guaranteed to be a solution

Forward-search also is complete

If a solution exists then Forward-search will return a solution.

Search proceeds as follows:

1. The algorithm starts the search at the initial state.
2. If the initial state satisfies the goal, then search ends and we get a plan of length zero.
3. If not, the algorithm applies all applicable actions to the initial state to produce new states.
4. It checks if any of the new states satisfies the goal.
5. If yes, search ends.
6. If not, then search continues by applying actions to each of the new states.
7. Search continues until either all reachable states have been examined or a goal state has been reached.
8. If a goal state is reached, the algorithm returns the sequence of actions that led from the initial state to the found goal state.

Some deterministic implementations of forward search:

• breadth-first search
• best-first search (e.g., A*)

Breadth-first and best-first search are sound and complete.

• But they usually aren’t practical because they require too much memory.
• Memory requirement is exponential in the length of the solution.

Forward search can have a very large branching factor.

• E.g., many applicable actions that don’t progress toward goal.
• Why this is bad:
  • Deterministic implementations can waste time trying lots of irrelevant actions.
• Need a good heuristic function and/or pruning procedure.

Link to original

Classical Planning and Acting

Summary

• An example: Blocks world
• Classical representation of the planning domain (constant symbols, predicates, operators), states and actions.
• Applicability of an action to a state
• State transition function
• Assumptions needed for classical Task Planning
• Statement of a classical Task Planning problem
• Three types of planners: domain-dependent, domain-independent, configurable
• State-space planning: Forward Search
• Conceptual model of planning and acting (plan execution).