DOC PREVIEW
UMBC CMCS 471 - LECTURE NOTES

This preview shows page 1-2-3-22-23-24-44-45-46 out of 46 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 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 46 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 46 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 46 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 46 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 46 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 46 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 46 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 46 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CMSC 671 Fall 2001Today’s classUninformed SearchBuilding Goal-Based AgentsWhat is the goal to be achieved?What are the actions?Representing actionsRepresenting statesClosed World AssumptionSome example problems8-Puzzle8 puzzleThe 8-Queens ProblemMissionaries and CannibalsMissionaries and Cannibals SolutionCryptarithmeticRemove 5 SticksWater Jug ProblemSome more real-world problemsKnowledge representation issuesFormalizing search in a state spaceFormalizing search IISlide 23Slide 24Formalizing search IIIFormalizing search IVState-space search algorithmKey procedures to be definedBookkeepingSome issuesEvaluating Search StrategiesUninformed vs. informed searchExample for illustrating uninformed search strategiesBreadth-FirstDepth-First (DFS)Uniform-Cost (UCS)Depth-First Iterative Deepening (DFID)Depth-First Iterative DeepeningHow they performDepth-First SearchBreadth-First SearchUniform-Cost SearchBi-directional searchComparing Search StrategiesAvoiding Repeated StatesA State Space that Generates an Exponentially Growing Search SpaceCMSC 671CMSC 671Fall 2001Fall 2001Class #3/4 – Monday, September 9 / Wednesday, September 11Today’s class•Goal-based agents•Representing states and operators•Example problems•Generic state-space search algorithm•Specific algorithms–Breadth-first search–Depth-first search–Uniform cost search–Depth-first iterative deepening•Example problems revisitedUninformed Uninformed SearchSearchChapter 3Some material adopted from notes by Charles R. Dyer, University of Wisconsin-MadisonBuilding Goal-Based AgentsTo build a goal-based agent we need to answer the following questions: –What is the goal to be achieved?–What are the actions?–What relevant information is necessary to encode about the world to describe the state of the world, describe the available transitions, and solve the problem? InitialstateGoalstateActionsWhat is the goal to be achieved?•Could describe a situation we want to achieve, a set of properties that we want to hold, etc. •Requires defining a “goal test” so that we know what it means to have achieved/satisfied our goal.•This is a hard question that is rarely tackled in AI, usually assuming that the system designer or user will specify the goal to be achieved. •Certainly psychologists and motivational speakers always stress the importance of people establishing clear goals for themselves as the first step towards solving a problem. •What are your goals???What are the actions?•Characterize the primitive actions or events that are available for making changes in the world in order to achieve a goal. •Deterministic world: no uncertainty in an action’s effects. Given an action (a.k.a. operator or move) and a description of the current world state, the action completely specifies –whether that action can be applied to the current world (i.e., is it applicable and legal), and –what the exact state of the world will be after the action is performed in the current world (i.e., no need for "history" information to compute what the new world looks like).Representing actions•Note also that actions in this frameworks can all be considered as discrete events that occur at an instant of time.–For example, if "Mary is in class" and then performs the action "go home," then in the next situation she is "at home." There is no representation of a point in time where she is neither in class nor at home (i.e., in the state of "going home").•The number of actions / operators depends on the representation used in describing a state.–In the 8-puzzle, we could specify 4 possible moves for each of the 8 tiles, resulting in a total of 4*8=32 operators. –On the other hand, we could specify four moves for the "blank" square and we would only need 4 operators.•Representational shift can greatly simplify a problem!Representing states•What information is necessary to encode about the world to sufficiently describe all relevant aspects to solving the goal? That is, what knowledge needs to be represented in a state description to adequately describe the current state or situation of the world?•The size of a problem is usually described in terms of the number of states that are possible. –Tic-Tac-Toe has about 39 states. –Checkers has about 1040 states. –Rubik’s Cube has about 1019 states. –Chess has about 10120 states in a typical game.Closed World Assumption•We will generally use the Closed World Assumption.•All necessary information about a problem domain is available in each percept so that each state is a complete description of the world. •There is no incomplete information at any point in time.Some example problems•Toy problems and micro-worlds–8-Puzzle–Missionaries and Cannibals–Cryptarithmetic–Remove 5 Sticks–Water Jug Problem•Real-world problems8-PuzzleGiven an initial configuration of 8 numbered tiles on a 3 x 3 board, move the tiles in such a way so as to produce a desired goal configuration of the tiles.8 puzzle•State: 3 x 3 array configuration of the tiles on the board. •Operators: Move Blank square Left, Right, Up or Down. –This is a more efficient encoding of the operators than one in which each of four possible moves for each of the 8 distinct tiles is used.•Initial State: A particular configuration of the board. •Goal: A particular configuration of the board.The 8-Queens Problem Place eight queens on a chessboard such that no queen attacks any other!Missionaries and CannibalsThere are 3 missionaries, 3 cannibals, and 1 boat that can carry up to two people on one side of a river. •Goal: Move all the missionaries and cannibals across the river. •Constraint: Missionaries can never be outnumbered by cannibals on either side of river, or else the missionaries are killed. •State: configuration of missionaries and cannibals and boat on each side of river. •Operators: Move boat containing some set of occupants across the river (in either direction) to the other side.Missionaries and Cannibals Solution Near side Far side0 Initial setup: MMMCCC B -1 Two cannibals cross over: MMMC B CC2 One comes back: MMMCC B C3 Two cannibals go over again: MMM B CCC4 One comes back: MMMC B CC5 Two missionaries cross: MC B MMCC6 A missionary & cannibal return: MMCC B MC7 Two missionaries cross again: CC B


View Full Document

UMBC CMCS 471 - LECTURE NOTES

Download LECTURE NOTES
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 LECTURE NOTES 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 LECTURE NOTES 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?