Intelligent Systems Lecture Notes

7 October 2011 • Planning

---

Outline

Planning Worlds, agents, and states. World representations. States spaces. Features STRIPS

I Want That Car

What’s the cure?

Planning

• An agent operates in a world.
• Agent actions effect the world, including the agent’s relation to the world.
• An agent acts to achieve goals.
• Planning finds action sequences that achieve goals.
  • Considering the agent’s ability, the goals, and the world state.

Worlds

• The world contains everything knowable, including the agent.
• The world representation, or model, is predominantly state-based.
• A state is a collection of features in the world.
  • A feature need not be boolean valued.
• Differing state representations produce differing world models.

Agents

• Agents operate in the world, and are part of the world.
• An agent can perform a set of actions.
• Agent actions effect the world, and the agents relation to the world.
  • Actions map one state into another.

Agent Actions

• A deterministic action is a partial function from states to states.
  • Not every action is possible from every state.
• An action precondition specifies when the action can be carried out.
• An action effect specifies the resulting state.

Goals

• A goal is a desired state in the world.
• Goals are world predicates that are achieved or maintained.
  • Maintained goals are also known as safety goals, or properties.
  • Asimov’s Three Robotics Laws.
• Achievement goals should eventually be made true.

Assumptions

• The world is deterministic.
  • The same action in the same world produces the same result.
• All world changes result from agent actions.
  • There are no exogenous changes.
• The agent knows the world with certainty.
• Time is discrete on actions.

World Example

World Features: ALoc Al’s location AHC Al has coffee AHM Al has mail SWC Sam wants coffee MW Mail is waiting Agent Actions: mc move clockwise mcc move anticlockwise puc pick-up coffee dc deliver coffee pum pickup mail dm deliver mail

State-Space Representation

• Represent the world as an n-tuple of feature values.
• Enumerate the states, the actions and the resulting states.
  • Either in tabular or graph format (or both, or something else).

Example

State		Action		Resulting State
\(\langle\)lab, ahc, swc, mw, ahm\(\rangle\)		mc		\(\langle\)mr, ahc, swc, mw, ahm\(\rangle\)
\(\langle\)lab, ahc, swc, mw, ahm\(\rangle\)		mcc		\(\langle\)off, ahc, swc, mw, ahm\(\rangle\)
\(\langle\)off, ahc, swc, mw, ahm\(\rangle\)		dm		\(\langle\)off, ahc, swc, mw, ahm\(\rangle\)
\(\langle\)off, ahc, swc, mw, ahm\(\rangle\)		mcc		\(\langle\)cs, ahc, swc, mw, ahm\(\rangle\)
\(\langle\)off, ahc, swc, mw, ahm\(\rangle\)		mc		\(\langle\)lab, ahc, swc, mw, ahm\(\rangle\)
\(\vdots\)		\(\vdots\)		\(\vdots\)

Observations

• The state space grows exponentially with feature count.
• States are easy to change, but fragile overall.
  • Maintaining consistency over changed states is difficult.
• Explicit state spaces have lots of unexploited structure.
  • Graphs and tables exhibit structure, but don't exploit it.

Feature Representation

• Emphasize states, or features in states, exploiting common structure.
• A feature rule describes how and when actions effect states.
  • Causal rules specify when the feature gets a new value.
  • Frame rules specify when the feature keeps its value.

Feature Rules

• A feature rule has the form

  effects \(\leftarrow\) precondition \(\wedge\) actions

  • The given effects when the precondition holds and the action's taken.
• An apostrophe marks features after an action has been taken.

Example

• Pick-up coffee (puc) precondition:

  ALoc = cs \(\wedge\) ahc

• Rules leading to the agent is the coffee shop (cs):

  ALoc' = cs \(\leftarrow\) ALoc = off \(\wedge\) Act = mcc
  ALoc' = cs \(\leftarrow\) ALoc = mr \(\wedge\) Act = mc
  ALoc' = cs \(\leftarrow\) ALoc = cs \(\wedge\) Act \(\neq\) mc \(\wedge\) Act \(\neq\) mcc

• Rules when the agent has coffee (ahc):

  ahc' \(\leftarrow\) ahc \(\wedge\) Act \(\neq\) dc
  ahc' \(\leftarrow\) ahc \(\wedge\) cs \(\wedge\) Act = puc

STRIPS Representation

Emphasize actions instead of features. Given an action, describe what it can do. Many actions change a feature, but an action changes few features.

STRIPS Characteristics

• STRIPS divides world features into
  • Primitive features changed directly by actions.
  • Derived features derived from primitive features.
• Actions change primitive features, derived features are calculated from primitive features.
  • Using definite clauses.

STRIPS Actions

• Each action is
  • A precondition specifying when the action can be carried out.
  • An effect listing feature values established by the action.
• Both preconditions and effects are lists of features.
  • Features not listed are assumed unchanged.

Example

• Pick-up coffee (puc):
  • Precondition: [ cs, ahc ]
  • Effect: [ ahc ]
• Deliver coffee (dc):
  • Precondition: [ off, ahc ]
  • Effect: [ ahc, swc ]

STRIPS vs Features

• STRIPS representations can be translated into features.
  • Preconditions are identical.
  • Events are translated into causal rules.
  • Unchanged features are translated into frame rules.
• Features can represent conditional effects, which STRIPS cannot.

Planning vs Searching

• Haven't we done this before?
• Searching isn't easily extended to worlds with more lax assumptions.
• Planning includes searching as a special case.
  • Planning for multiple goals, and maintaining safety goals.
• Planning can go meta by manipulating searches.

Summary

• Actions change features in the world.
• Planning chooses an action sequence to meet a goal in a world.
• World representations are state spaces, and can emphasize features or actions.

References

• Planning in IS (Chapter 12) in Intelligent Systems by Robert Schalkoff from Jones and Bartlett, 2011.
• Classical Planning (Chapter 10) in Artifical Intelligence, third edition, by Stuart Russell and Peter Norvig from Prentice Hall, 2010.
• Planning (Chapter 15) in Knowledge Representation and Reasoning by Ronald Brachman and Hector Levesque from Morgan Kaufmann, 2004.
• Shakey, SRI International.

Credits

• Robot by Sebastian Lund under a Creative Commons BY license.
• Amtrak & Metra together by contemplative imaging under a Creative Commons BY NC SA license.
• CO 1069-143-13 from The National UK Archives.
• Computer History Museum - 169 by Phil Hollenback under a Creative Commons BY NC License.

---

This page last modified on 2011 October 7.