Week 1 Homework with answers -- 10/18/2011 1. Peg Solitare. Is it: A. Partially Observable {y,n} -- No B. Stochastic {y,n} -- No C. Continuous {y,n} -- No D. Adversarial {y,n} -- No 2. Loaded Coin flips. Is it: A. Partially Observable {y,n} -- YES! (ENHT! I said No...XXX) B. Stochastic {y,n} -- Yes C. Continuous {y,n} -- No D. Adversarial {y,n} -- No Note: to (A), the definition seems to be based on needing memory to maintain state information over multiple trials. The task of recognizing a _loaded_ coin requires memory of previous states, and is by their definition Partially Observable... further to this from reddit: []stanleyPhilips I think that the key to understanding Full vs Partial Observability is that you focus on the question being asked. For example, the question whether a coin is PO or FO should be restated as "Can I determine whether or not the coin is biased based on a single toss of the coin?". In this case the answer is No, you cannot. Why? because your sensory awareness of the outcome of the coin toss (looking at the coin) does not provided enough information to make a decision. Hence, it is partially observable. More importantly, your agent will need to maintain a history of previous coin tosses in order to answer the question. 3. Path Through Maze. Is it: A. Partially Observable {y,n} -- No B. Stochastic {y,n} -- No C. Continuous {y,n} -- No D. Adversarial {y,n} -- No (need to know: is the agent in the maze or omniscient above it? ->ABOVE what actions can be executed? -> FWD, LEFT, RIGHT) From Twitter: For Homework 1, Question 3: Assume you are looking at the maze from up above. Assume the only controls you have are right, left, straight. At an intersection, you can go along any of the paths. So you can spin in place (multiple rights/lefts). When you choose to go down a corridor, you move down the corridor instantly to the next intersection. No stops. 4. Search Tree, where s=start and g=goal s / | \ o o o /\ /\ /\ o g o o o o How many nodes are expanded (counting start and goal)? Searching left to right using: Breadth First -- 6 Depth First -- 4 Searching right to left using: Breadth First -- 9 Depth First -- 9 I'm assuming that nodes are expanded only once, i.e., Graph Search, AND that we are using the Search algorithm shown in the lecture rather than the one labeled "Breadth First Search" in the book: The Unit 2.10 video emphasizes that the goal test is done when the frontier is popped, whereas the book shows -- page 82 -- the goal test in the node expansion at the bottom of the loop. ALSO, technically the goal node is never expanded, but we are asked to count it anyway... See searchOrder.png screen capture of video for l-r numbering. 5. Search Tree 2, where s=start and g=goal s / | \ o o o /\ /\ /\ o o o o o o /\ \ o o g How many nodes are expanded (counting start and goal)? Searching left to right using: Breadth First -- 13 Depth First -- 10 Searching right to left using: Breadth First -- 11 Depth First -- 7 same assumptions as question 4 6. Search Network, diamond network where s=start and g=goal s / \ o o / \ / \ o a o / \ / \ / \ o o o g \ / \ / \ / o o o \ / \ / o o \ / o Never expand same node twice. How many nodes are expanded (counting start and goal)? Searching left to right using: Breadth First -- 10 Depth First -- 16 (for not directed: 14) Searching right to left using: Breadth First -- 7 Depth First -- 4 (need to know: if graph is directed, i.e., is "going back up" from lower link allowed as part of depth search? He says, "We search down..." but then the double links are mostly meaningless...) same assumptions as question 4, AND per http://www.reddit.com/r/aiclass/comments/ldhuy/clarifications_and_corrections/ It IS directed so you cannot traverse back up the tree on Depth Search) 7. A* Search, 4x6 grid with indicated heuristic values start in top left (a1), goal in bottom right (d6) 1 2 3 4 5 6 (column number) s ------------ a| 4 4 4 3 2 1 b| 3 3 3 3 2 1 c| 2 2 2 2 2 1 d| 1 1 1 1 1 0 (row letter) g Is the Heuristic Admissable {y,n} -- Yes (never over-estimates) First node to expand {b1,a2} -- b1 (f = 1g + 3h) Second node to expand {b1,c1,a2,a3,b2} -- c1 (f = 2g + 2h) Third node to expand {d1,c2,b3,a4} -- d1 (f = 3g + 1h) (need to know, so many questions.... is heuristic h(s) < trueCost or h(s) <= trueCost? -- lecture says h(s) < trueCost AND that h(s) doesn't Over-Estimate are diagonal moves allowed? -- probably not, but it's not obvious -> NOT ALLOWED per tweet: http://twitter.com/#!/aiclass/status/124666312545935360 is the path cost a constant, i.e., number of steps? -- probably yes, but it's not obvious why don't we expand the start a1 first? -- maybe it is assumed to be the zero'th expansion?) assumptions used: *The start node is _actually_ the first expanded, vis video 2.23, but I will call it zeroth. from reddit: srgb Hello, all. I came up with following assumptions to be able to solve the problem: * The goal of this particular A* search is to find the cheapest path * from Start to Goal (otherwise, any path from S to G will fit) as fast * as possible. * Cost of a transition from one state to another equals to 1 point (If * it's 0, then all paths equal by cost, thus deleting "cheapest" from * A* goal) * Only 4 (or less) transitions allowed: left, right, top, bottom or * even less, if state's near the edge (Taken from the possible answers * to "first node to expand" question) * "Move" is a process of selecting the next state from Frontier * priority queue, that has the lowest g+h. The purpose of selection of * a state - is to add its neighbors to Frontier. * If 2 states from Frontier priority queue have same g+h value, select * the one that was added there first, because of the queue's FIFO * feature.