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