Lecutre 2-State Space for control system

State Space Modelling of Mechanical System

1. State-Space Representation
General Problem Solving via
simplification
Read Chapter 3

2. What you should know
•Create a state-space model
•Estimate number of states
•Identify goal or objective function
•Identify operators
•Next Lecture: how to search/use model

3. Everyday Problem Solving
•Route Planning
–Finding and navigating to a classroom seat
•Replanning if someone cuts in front
–Driving to school
•Constant updating due to traffic
•Putting the dishes away
–Spatial reasoning

4. Goal: Generality
•People are good at multiple tasks
•Same model of problem solving for all
problems
•Generality via abstraction and
simplification.
•Toy problems as benchmarks for methods,
not goal.
•AI criticism: generality is not free

5. State-Space Model
•Initial State
•Operators: maps a state into a next state
–alternative: successors of state
•Goal Predicate: test to see if goal achieved
•Optional:
–cost of operators
–cost of solution

6. Major Simplifications
•You know the world perfectly
–No one tells you how to represent the world
–Sensors always make mistakes
•You know what operators do
–Operators don’t always work
•You know the set of legal operators
–No one tells you the operators

7. 8-Queens Model 1
•Initial State: empty 8 by 8 board
•Operators:
–add a queen to empty square
–remove a queen
–[move a queen to new empty square]
•Goal: no queen attacks another queen
–Eight queens on board
•Good enough? Can a solution be found?

8. 8-Queens Model 2
•Initial State: empty 8 by 8 board
•Operators:
–add ith queen to some column (i = 1..8)
–Ith queen is in row i
•Goal: no queen attacks another queen
–8 queens on board
•Good enough?

9. 8-Queens Model 3
•Initial State:
–random placement of 8 queens ( 1 per row)
•Operators:
–move a queen to new position (in same row)
•Goal: no queen attacks another queen
–8 queens on board

10. Minton
•Million Queens problem
•Can’t be solved by complete methods
•Easy by Local Improvement –
–to be covered next week
•Same method works for many real-world
problems.

11. Traveling Salesman Problem
•Given: n cities and distances
•Initial State: fix a city
•Operators:
–add a city to current path
–[move a city to new position]
–[swap two cities]
–[UNCROSS]
•Goal: cheapest path visiting all cities once and
returning.

12. TSP
•Clay prize: $1,000,000 if prove can be done
in polynomial time or not.
•Number of paths is N!
•Similar to many real-world problems.
•Often content with best achievable:
bounded rationality

13. Sliding Tile Puzzle
•8 by 8 or 15 by 15 board
•Initial State:
•Operators:
•Goal:

14. Sliding Tile Puzzle
•8 by 8 or 15 by 15 board
•Initial State: random (nearly) of number 1..7
or 1..14.
•Operators:
–slide tile to adjacent free square.
•Goal: All tiles in order.
•Note:Any complete information puzzle fits
this model.

15. Cryptarithmetic
•Ex: SEND+MORE = MONEY
•Initial State:
•Operators:
•Goal:

16. Cryptarithmetic
•SEND+MORE = MONEY
•Initial State: no variable has a value
•Operators:
–assign a variable a digit (0..9) (no dups)
–unassign a variable
•Goal: arithmetic statement is true.
•Example of Constraint Satisfaction Problem

17. Boolean Satisfiability (3-sat)
•$1,000,000 problem
•Problem example (a1 +~a4+a7)&(….)
•Initial State:
•Operators
•Goal:

18. Boolean Satisfiability (3-sat)
•Problem example (a1 +~a4+a7)&(….)
•Initial State: no variables are assigned values
•Operators
–assign variable to true or false
–negate value of variable (t->f, f->t)
•Goal: boolean expression is satisfied.
•$1,000,000 problem
•Ratio of clauses to variables breaks problem into 3 classes:
–low ratio : easy to solve
–high ratio: easy to show unsolvable
–mid ratio: hard

19. CrossWord Solving
•Initial-State: empty board
•Operators:
–add a word that
•Matches definition
•Matches filled in letters
–Remove a word
•Goal: board filled

20. Most Common Word
(Misspelled) Finding
•Given: word length + set of strings
•Find: most common word to all strings
–Warning: word may be misspelled.
•length 5: hellohoutemary position 5
•bargainsamhotseview position 10
•tomdogarmyprogramhomse position 17
•answer: HOUSE

21. Misspelled Word Finding
•Let pi be position of word in string i
•Initial state: pi = random position
•Operators: assign pi to new position
•Goal state: position yielding word with
fewest misspellings
•Problem derived from Bioinformatics
–finds regulatory elements; these determine
whether gene are made into proteins.