DOC PREVIEW
UCI ICS 171 - State Space Representation

This preview shows page 1-2-20-21 out of 21 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

State-Space RepresentationWhat you should knowEveryday Problem SolvingGoal: GeneralityState-Space ModelMajor Simplifications8-Queens Model 18-Queens Model 28-Queens Model 3MintonTraveling Salesman ProblemTSPSliding Tile PuzzleSlide 14CryptarithmeticSlide 16Boolean Satisfiability (3-sat)Slide 18CrossWord SolvingMost Common Word (Misspelled) FindingMisspelled Word FindingState-Space RepresentationGeneral Problem Solving via simplificationRead Chapter 3What 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 modelEveryday 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 reasoningGoal: 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 freeState-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 solutionMajor 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 operators8-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-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?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 boardMinton•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.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.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 rationalitySliding Tile Puzzle•8 by 8 or 15 by 15 board•Initial State: •Operators:•Goal: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.Cryptarithmetic•Ex: SEND+MORE = MONEY•Initial State: •Operators:•Goal: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 ProblemBoolean Satisfiability (3-sat)•$1,000,000 problem•Problem example (a1 +~a4+a7)&(….)•Initial State: •Operators•Goal: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: hardCrossWord Solving•Initial-State: empty board•Operators: –add a word that •Matches definition•Matches filled in letters–Remove a word•Goal: board filledMost 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: HOUSEMisspelled 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


View Full Document

UCI ICS 171 - State Space Representation

Documents in this Course
Prolog

Prolog

16 pages

PROJECT

PROJECT

3 pages

Quiz 6

Quiz 6

9 pages

Load more
Download State Space Representation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view State Space Representation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view State Space Representation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?