Tuesday Jan 22 2013 - Lecture 5

7 Pages
Unlock Document

Computing and Information Science
CIS 3700
Yang Xiang

Tuesday, January 22 2013 CIS 3700 Lecture 5 Review • Moved into problem solving by search River-Crossing Problem • We want to develop an algorithm that will solve this problem • Afarmer, with a wolf, a sheep, and a cabbage, needs to cross a river using a boat. The boat can carry the farmer plus one other thing. The wolf and sheep cannot be left in the same bank unattended, nor can the sheep and the cabbage • How can the farmer cros the river with his belongings intact? ◦ Step 1: Identify factors affecting rational behaviour ◦ Step 2: Identify inital state and goal state ◦ Step 3: Find action sequence using Tree Search P, E,A, S //Performance measures, Environment,Actuators, Sensors E: V={at_ib, at_db} //Represent the environment using two variables at_ib є {P, {f}, {w}, ..., //Represents the objects on the initial bank {f,w}, {w,c}, ..., //f = farmer, w = wolf, s = sheep, c = cabbage {f,w,c}, {f,s,c}, ..., {f, w, s, c}} at_db є .... //Represents the objects on the destination bank • The environment can be represented by sets of ordered pairs • For example, at the start, the environment looks like this: {{f,w,s,c}, null} • ◦ The | | is the river ◦ Before the | | is the initial bank ◦ After the | | is the destination bank ◦ Everyone on the initial bank • ◦ Wolf and cabbage on one side, the farmer and sheep on the other • What actions can be taken by this agent? ◦ A: To(), From() ◦ To(): ▪ To({f}) //Farmer alone ▪ To({f,w}) //Farmer and wolf ◦ From(): ▪ From(f) //Simplified notation for farmer alone ▪ From(f,w) //Simplified notation for farmer and wolf • What sensors does this agent require? ◦ The environment is fully observable ◦ Requires ability to know what is on either side of the river • What are the performance measures? ◦ Performance measure is whether or not the farmer is able to transform the environment state from to < | | f,w,s,c > Goals • Agent's task at hand can often be specified in terms of a goal to be satisfied • An agent always has a goal state in mind that it is trying to achieve The Idea of Tree Search treeSearch(problem,strategy){ set rootoftree to initial state of the problem; // loop{ find a leaf X to expand according to the strategy; if no qualified leaf is found, return failure; if X corresponds to a goal state{ return the corresponding solution; } else{ expand X; add children of X to the search tree; } } } Expand X Means generate all the child nodes that are legal: In the search tree, leaf nodes may correspond to the same environmental space • Do we need to add a code check to see if there is a duplicated state? • For now, assume we don't check Data Structure for Node on Search Tree • Components in node data structure ◦ 1. Corresponding environmental state ◦ 2. Parent node on search tree ▪ Want to encode whhich node came immediately before ▪ This property is important so that once you have found the goal state in the leaf nodes, you can retrace your sequence of actions that led you from the initial state to the goal state ◦ 3. Action that generated this node from its parent ▪ This property is important so that once you have found the goal state in the leaf nodes, you can retrace your sequence of actions that led you from the initial state to the goal state ◦ 4. Depth: Length of the path from the root of the tree ◦ 5. Path cost from the root to the node ▪ Allow
More Less

Related notes for CIS 3700

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.