Problem Solving as State Space Search Brian c Williams 16410-13 from: Sepl5,2003 6.034 Tomas Lozano Perez. Russell and Norvig AIMA Bnas withams, Spring 03 Complex missions must carefully of action Schedule tight resources Monitor and diagnose behavior B Most aI problems, like these, may be formulated as Bran withams, Spring 03 CourtesyofNasa/Jpl-CalteCh.http://www.jpl.nasa.gov
1 Brian Williams, Spring 03 1 Problem Solving as State Space Search Brian C. Williams 16.410-13 Sep 15th, 2003 Slides adapted from: 6.034 Tomas Lozano Perez, Russell and Norvig AIMA Brian Williams, Spring 03 2 Complex missions must carefully: • Plan complex sequences of actions • Schedule tight resources • Monitor and diagnose behavior • Repair or reconfigure hardware. Ö Most AI problems, like these, may be formulated as state space search. Courtesy of NASA/JPL-Caltech. http://www.jpl.nasa.gov
Assignments · Remember: Problem set#1: Rules and Scheme due today September 15th, 2003 Reading Solving problems by searching: AIMA Ch 3 Homework for this lecture Problem set #2 due Monday, Sept. 22 Snas witha, Spring 03 Outline · Problem formulation Problem solving as state space search · mathematical model Graphs and search trees Reasoning algorithms Depth and breadth-first search Bran withams, Spring 03 2
2 Brian Williams, Spring 03 3 Assignments • Remember: Problem set #1: Rules and Scheme due today September 15th, 2003. • Reading: – Solving problems by searching: AIMA Ch. 3 • Homework for this lecture: – Problem set #2 due Monday, Sept. 22 Brian Williams, Spring 03 4 Outline • Problem Formulation – Problem solving as state space search • Mathematical Model – Graphs and search trees • Reasoning Algorithms – Depth and breadth-first search
rain Fox Rove · Astronaut+ 1 iten allowed in the Can the astronaut get its produce Goose alone eats grain safely across the Martian canal? · Fox alone eats goose Early Al: What are the universal problem solving methods? Simple-XTrivial Bnas withams, Spring 03 ImagetakenfromNasa'swebsitehttp://www.nasa.gov Problem Solving as State Space Search · Formulate goal Astronaut. Fox. Goose grain across river · Formulate problen States Location of astronaut. Fox. goose grain at top or bottom river bank Operators Move rover with astronaut 1 or0 items · Generate Solution Move(goose, astronaut), Move(astronaut), Bran withams, Spring 03
3 Brian Williams, Spring 03 5 Early AI: What are the universal problem solving methods? Astronaut Goose Grain Fox Rover Can the astronaut get its produce safely across the Martian canal? • Astronaut + 1 item allowed in the rover. • Goose alone eats Grain • Fox alone eats Goose Simple Trivial Brian Williams, Spring 03 6 Problem Solving as State Space Search • Formulate Goal – State • Astronaut, Fox, Goose & Grain across river • Formulate Problem – States • Location of Astronaut, Fox, Goose & Grain at top or bottom river bank – Operators • Move rover with astronaut & 1 or 0 items to other bank. • Generate Solution – Sequence of States • Move(goose,astronaut), Move(astronaut), . . . Image taken from NASA's website: http://www.nasa.gov
Goose Goose Astronaut Astronau Grain Astronaut Fox Goose Grain Fo Grain Fox Grain Goose Grain Grain Astrona Fox OOS Fox Astronaut Astron Grain Grain Goose Goose Astronaut Astronaut Grain F F ral Grain A stronau Grain Goose Grain Fox Goose Grain Astronaut Grain 4
4 Brian Williams, Spring 03 7 Astronaut Goose Grain Fox Grain Fox Astronaut Goose Astronaut Grain Fox Goose Goose Astronaut Fox Grain Astronaut Goose Grain Fox Astronaut Goose Grain Fox Grain Astronaut Goose Fox Astronaut Goose Grain Fox Fox Astronaut Goose Grain Astronaut Goose Fox Grain Goose Fox Astronaut Grain Goose Grain Astronaut Fox Astronaut Grain Goose Fox Astronaut Fox Goose Grain Goose Grain Fox Astronaut Astronaut Goose Grain Fox Brian Williams, Spring 03 8 Astronaut Goose Grain Fox Grain Fox Astronaut Goose Astronaut Grain Fox Goose Goose Astronaut Fox Grain Astronaut Goose Grain Fox Astronaut Goose Grain Fox Grain Astronaut Goose Fox Astronaut Goose Grain Fox Fox Astronaut Goose Grain Astronaut Goose Fox Grain Goose Fox Astronaut Grain Goose Grain Astronaut Fox Astronaut Grain Goose Fox Astronaut Fox Goose Grain Goose Grain Fox Astronaut Astronaut Goose Grain Fox
Example: 8-Puzzle Start Goal States. integer location for each tile AND Operators: move empty square up, down, left, right Goal Test: goal state as given Snas witha, Spring 03 Planning as state space search STRIPS Operator Representation Initial state north11 block b (block c) on-table a) (on-table b) (clear a precondition:(and(agent-at 1 1) lear b (clear c) (agent-facing north)) goal(partial state: effect:(and(agent-at 1 2) (not(agent-at 1 I )) E Effects specify how Available actions Strips operators change the set of assertions Bran withams, Spring 03
5 Brian Williams, Spring 03 9 Example: 8-Puzzle • States: • Operators: • Goal Test: 5 4 6 1 7 3 8 2 1 2 8 3 7 6 4 5 Start Goal integer location for each tile AND … move empty square up, down, left, right goal state as given Brian Williams, Spring 03 10 Planning as State Space Search: STRIPS Operator Representation Ö Effects specify how to change the set of assertions. a a north11 W0 W1 • Initial state: • (and (block a) (block b) (block c) (on-table a) (on-table b) (clear a) (clear b) (clear c) (arm-empty)) • goal (partial state): • (and (on a b) (on b c))) • Available actions • Strips operators precondition: (and (agent-at 1 1) (agent-facing north)) effect: (and (agent-at 1 2) (not (agent-at 1 1))) North11
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 , where V is a set of vertices . ≤SFO,LA> An edge is a pair of vertices, where 2 is the head of the edge, .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 , where: • V is a set of vertices • E is a set of (directed) edges An edge is a pair of vertices, where • v2 is the head of the edge, •and v1 is the tail of the edge , . . .} > 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
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
