State Space Intro show

Information about State Space Intro show

Published on January 3, 2008

Author: Bernadette

Source: authorstream.com

Content

Slide1:  State-Space representation and Production Systems Introduction: what is State-space representation? What are the important trade-offs? (E.Rich, Chapt.2) Basis search methods. (Winston, Chapt.4 + Russel&Norvig) Optimal-path search methods. (Winston, Chapt.5 + Russel&Norvig) Advanced properties and variants. (Rich, Chapt.3 + Russel&Norvig + Nilsson) Game Playing (Winston, Chapt.6 + Rich + Russel&Norvig ) State-space representation: Introduction and trade-offs:  State-space representation: Introduction and trade-offs What is state-space representation? Which are the technical issues that arise in that context? What are the alternatives that the paradigm offers to solve a problem in the state-space representation? State-space representation: general outline::  State-space representation: general outline: Select some way to represent states in the problem in an unambiguous way. Formulate all actions that can be preformed in states: including their preconditions and effects == PRODUCTION RULES Represent the initial state (s). Formulate precisely when a state satisfies the goal of our problem. Activate the production rules on the initial state and its descendants, until a goal state is reached. Initial issues to solve::  Initial issues to solve: How to formulate production rules? (repr. 2) Ex.: express how/when squares may be moved? Or: express how/when the blank space is moved? When is a rule applicable to a state? (matching) How to formulate when the goal criterion is satified and how to verify that it is? How/which rules to activate? (control) The (implicit) search tree:  The (implicit) search tree Each state-space representation defines a search tree: But this tree is only IMPLICITLY available !! A second example: Chess:  A second example: Chess Problem: develop a program that plays chess (well). Chess (2)::  Chess (2): 2. Describe the rules that represent allowed moves: Ex.: Chess (3)::  Chess (3): 3. Provide a way to check whether a rule is applicable to some state: Ex.: Chess (4)::  Chess (4): 4. How to specify a state in which the goal is reached (= a winning state): Ex.: Chess (5)::  Chess (5): 5. A way to verify whether a winning state is reached. Ex.: Chess (6).:  Chess (6). 6. The initial state. Chess (7).:  Chess (7). Need very efficient search techniques to find good paths in such combinatorial trees. Very many issues and trade-offs::  Very many issues and trade-offs: 1. How to choose the rules? 2. Should we search through the implicit tree or through an implicit graph? 3. Do we need an optimal solution, or just any solution? ‘optimal path problems’ 4. Can we decompose states into components on which simple rules can in an independent way? Problem reduction or decomposability 5. Should we search forwards from the initial state, or backwards from a goal state? 1. Choice of the rules:  1. Choice of the rules Example: The water jugs problem: Given: 2 jugs: Problem: fill the 4 l jug with 2 l of water. 4 l 3 l Rules for the jugs example::  Rules for the jugs example: Fill large: [ x, y ] and x < 4  [ 4, y ] Fill small: [ x, y ] and y < 3  [ x, 3 ] Empty large: [ x, y ] and x > 0  [ 0, y ] Remove some from large: [ x, y ] and x > d > 0  [ x - d, y ] Empty (remove some from) small. Rules for the jugs example (2)::  Rules for the jugs example (2): Fill large from small: [ x, y ] and x + y  4 and y > 0  [ 4, y-(4-x) ] Fill small from large. Empty small in large: [ x, y ] and x + y  4 and y > 0  [ x + y , 0 ] Empty large in small. Slide19:  Part of the state space: Rules for the jugs example::  Rules for the jugs example: Fill large: [ x, y ] and x < 4  [ 4, y ] Fill small: [ x, y ] and y < 3  [ x, 3 ] Empty large: [ x, y ] and x > 0  [ 0, y ] Remove some from large: [ x, y ] and x > d > 0  [ x - d, y ] Empty (remove some from) small. * Part of the state space::  Part of the state space: 2. Avoiding loops: search in trees or graphs ?:  2. Avoiding loops: search in trees or graphs ? Avoids generating loops: but needs to keep track of ALL the nodes. 3. Any path, versus shortest path, versus best path::  3. Any path, versus shortest path, versus best path: Ex.: 8-puzzle: any or shortest path problem. Ex.: Traveling salesperson problem: Find a sequence of cities ABCDEA such that the total distance is MINIMAL. State space representation::  State space representation: State: the list of cities that are already visited Ex.: ( NewYork, Boston ) Initial state: Ex.: ( NewYork ) Rules: add 1 city to the list that is not yet a member add the first city if you already have 5 members Goal criterion: first and last city are equal 4. Problem reduction or problem decomposition::  4. Problem reduction or problem decomposition: Ex.: Computing symbolic integrals: State: the integral to compute Rules: integration reduction rules Goal: all integrals have been eliminated Necessary for decomposition: independence of states::  Necessary for decomposition: independence of states: Ex.: Blocks world problem. Initially: C is on A and B is on the table. Rules: to move any free block to another or to the table Goal: A is on B and B is on C. Slide28:  But: branches cannot be combined 5. Forward versus backward reasoning::  5. Forward versus backward reasoning: 5. Forward versus backward reasoning::  5. Forward versus backward reasoning: Criteria::  Criteria: Branching factor (Ex.: see previous slide) Sometimes: no way to start from the goal states because there are too many (Ex.: chess) because you can’t (easily) formulate the rules in 2 directions. Criteria (2)::  Criteria (2): Other possibility: middle-out reasoning. Production-rule systems::  Definition: Programs that implement approaches to search problems using the state space representation. Production-rule systems: Consist of: A rule base, a ‘working memory’, containing the state(s) that have currently been reached, a control strategy for selecting the rules to apply next to the states in the ‘working memory’ (including techniques for matching, verifying preconditions and whether a goal state has been reached)

Related presentations


Other presentations created by Bernadette

Article Usage
16. 11. 2007
0 views

Article Usage

halloween safety
05. 11. 2007
0 views

halloween safety

Oral Cancer
04. 01. 2008
0 views

Oral Cancer

service
03. 10. 2007
0 views

service

AMATYC 2004 Orlando Talk
06. 12. 2007
0 views

AMATYC 2004 Orlando Talk

16 graph design2
05. 11. 2007
0 views

16 graph design2

Astro105 Lecture13
14. 11. 2007
0 views

Astro105 Lecture13

aafsurvey 2006
16. 11. 2007
0 views

aafsurvey 2006

The Real Water World
01. 01. 2008
0 views

The Real Water World

Asteroid Mining
02. 01. 2008
0 views

Asteroid Mining

Dali parteI
05. 01. 2008
0 views

Dali parteI

peer relationship2
28. 12. 2007
0 views

peer relationship2

ladisch purdue
04. 01. 2008
0 views

ladisch purdue

TeamSystem2008Overvi ew
01. 12. 2007
0 views

TeamSystem2008Overvi ew

2005 4160s2 06 Fasano
04. 10. 2007
0 views

2005 4160s2 06 Fasano

GM Presentation
15. 11. 2007
0 views

GM Presentation

digitisation and data capture
27. 02. 2008
0 views

digitisation and data capture

patryk
19. 12. 2007
0 views

patryk

PP O2Dock
29. 02. 2008
0 views

PP O2Dock

Editorial Policy and Process
04. 12. 2007
0 views

Editorial Policy and Process

costianes
05. 03. 2008
0 views

costianes

Export Presentation
14. 03. 2008
0 views

Export Presentation

2 Poster 5 Grant
21. 12. 2007
0 views

2 Poster 5 Grant

recitationreviewv2
13. 04. 2008
0 views

recitationreviewv2

montes inaoep
28. 11. 2007
0 views

montes inaoep

13 1
17. 12. 2007
0 views

13 1

Podzim v Chicagu
05. 11. 2007
0 views

Podzim v Chicagu

bioterrorism new
27. 12. 2007
0 views

bioterrorism new

BlacksburgConcl2
12. 12. 2007
0 views

BlacksburgConcl2

E2005 1 347788 EteSeance5
27. 11. 2007
0 views

E2005 1 347788 EteSeance5

SONIA MENNA BARRETO 01
01. 11. 2007
0 views

SONIA MENNA BARRETO 01

Envir100LectOct29
21. 11. 2007
0 views

Envir100LectOct29

welinski 2
28. 11. 2007
0 views

welinski 2

OHP9b PCA 2006
23. 11. 2007
0 views

OHP9b PCA 2006