STRIPS Action schemata Instead of defi pickup-A and pickup-B and · Define a schema parameters(block ?obl)) precondition(and(clear ?ob1) (on-table ob1) (arm-empty)) effect(and(not(clear obl)) (not(on-table obl)) (not(arm-empty)) olding obl)) Outline Problem formulatio Problem solving as state space search · Mathematical model Graphs and search trees Reasoning algorithms Depth and breadth-first search Bran withams, Spring 03 6
6 Brian Williams, Spring 03 11 STRIPS Action Schemata (:operator pick-up :parameters ((block ?ob1)) :precondition (and (clear ?ob1) (on-table ?ob1) (arm-empty)) :effect (and (not (clear ?ob1)) (not (on-table ?ob1)) (not (arm-empty)) (holding ?ob1))) • Instead of defining: pickup-A and pickup-B and … • Define a schema: Note: strips doesn’t allow derived effects; you must be complete! } Brian Williams, Spring 03 13 Outline • Problem Formulation – Problem solving as state space search • Mathematical Model – Graphs and search trees • Reasoning Algorithms – Depth and breadth-first search
Problem Formulation: A Graph Undirected Directed Graph Graph (two-way streets) (one-way streets Snas witha, Spring 03 Examples of graphs Planning Actions Put B on c (graph of possible states of the world 闪A回[dl Put c on A
7 Brian Williams, Spring 03 14 Problem Formulation: A Graph Operator Link (edge) State Node (vertex) Directed Graph (one-way streets) Undirected Graph (two-way streets) Brian Williams, Spring 03 15 Examples of Graphs San Fran Boston LA Dallas Wash DC Airline Routes A B C A B C A B C A B C Put C on B Put C on A Put B on C Put C on A A B C Put A on C Planning Actions (graph of possible states of the world)
A graph Airline Routes A GraphG is represented as a pair <V, E>, where V is a set of vertices <Bos, SFO, LA, Dallas, Wash DO E is a set of (directed)edges &<SFO, Bos>. ≤SFO,LA> An edge is a pair <vl, v2> of vertices, where <LA, Dallas> 2 is the head of the edge, <Dallas. Wash DC> .and vl is the tail of the edge Snas witha, Spring 03 > a Solution is a state sequence Problem Solving searches Paths R ched paths using a tree Bran withams, Spring 03
8 Brian Williams, Spring 03 16 A Graph San Fran Boston LA Dallas Wash DC Airline Routes A Graph G is represented as a pair <V,E>, where: • V is a set of vertices • E is a set of (directed) edges An edge is a pair <v1, v2> of vertices, where • v2 is the head of the edge, •and v1 is the tail of the edge < {Bos, SFO, LA, Dallas, Wash DC} {<SFO, Bos>, <SFO, LA> <LA, Dallas> <Dallas, Wash DC> . . .} > Brian Williams, Spring 03 17 A Solution is a State Sequence: Problem Solving Searches Paths C S B G A D S D A C Represent searched paths using a tree. <S, A, D, C>
a Solution is a state sequence Problem Solving Searches Paths Represent searched paths using a tree Snas witha, Spring 03 a Solution is a state sequence Problem Solving searches Paths R ched paths using a tree Bran withams, Spring 03
9 Brian Williams, Spring 03 18 A Solution is a State Sequence: Problem Solving Searches Paths C S B G A D S D A C G Represent searched paths using a tree. Brian Williams, Spring 03 19 A Solution is a State Sequence: Problem Solving Searches Paths C S B G A D S D A B C G C G D C G Represent searched paths using a tree
Search trees Snas witha, Spring 03 Search trees Pare Bran withams, Spring 03 10
10 Brian Williams, Spring 03 20 Search Trees Root Link (edge) Node (vertex) Brian Williams, Spring 03 21 Search Trees Parent (Ancestor) Child (Descendant) Siblings