CSC4444 Homework 2 PDF

Preview

Summary

AI Chen...

Description

Hw2 Search 10 Points

Answer the following sub-questions. 1.1) Depth-first search always expands at least as many nodes as A* search with an admissible heuristic. True / do not know / false Depth-first search may possibly, sometimes, BY GOOD LUCK, expand fewer nodes than A* search with an admissible heuristic, e.g. it is logically possible that sometimes, by luck, depth-first search may march directly to the goal with no back-tracking 1.2)

h(n)=0 is an admissible heuristic for the 8-puzzle.

True / false true. h(n)=0 NEVER over-estimates the remaining optimal distance to a goal node. Zero is not higher than any other number. An admissible heuristic never overestimates the cost to reach the goal, i.e., it is optimistic 1.3)

A* is of no use in robotics because percepts, states, and actions are continuous.

True / False False, continuous state spaces can be abstracted to discrete states. All the percepts, actions and states change in robotics are base on pattern search. We do the search work first and then convert the results to continuous actions, etc. 1.4)

Breadth-first search is complete even if zero step costs are allowed.

True / false Optimal if all step cost is 1. Complete if d is finite. If a goal exists it will happen at finite depth d and found in O(bd) steps. 1.5) Assume that a rook can move on a chessboard any number of squares in a straight line, vertically or horizontally, but cannot jump over other pieces. Manhattan distance is an admissible heuristic for the problem of moving the rook from square A to square B in the smallest number of moves. True / False

False. The Manhattan distance may over-estimate the optimal remaining number of moves to the goal because a rook may cover several squares in a single moves. NOTE: If the path cost instead were the number of squares covered, then Manhattan distance would be admissible. easier 8-puzzle: You can move a tile from A to B if (1) A is adjacent to B, (2) B is blank. If you remove “B is blank” condition (jump over other pieces?), you get Manhattan distance 2.1)

Breadth-first search is a special case of uniform-cost search. True / False When step costs are equal, uniform-cost produces breadth-first

2.2)

Depth-first search is a special case of best-first tree search.

True / False Breadth-first search, depth-first search, and uniform-cost search are special cases of best-first search. Breadth-first search is best-first search with f(n) = depth(n); depth-first is best-first search with f(n) = −depth(n); uniform-cost search is best-first search with f(n) = g(n). 2.3)

Uniform-cost search is a special case of A* search.

True / False Uniform-cost search is A* search with h(n) = 0. 3.1)

We will use the same state space for the entire question. Consider the unbounded version of the regular 2D grid shown below (Fig. 3.6 in the AIMA book): The start state is at the origin (0,0), and the goal state is at (x,y). You can assume x > 0 and y > 0. Assume each step costs 1.

What is the branching factor b in this state space? 4 because there are 4 branches

3.2)

How many distinct states are there at depth k (for k>0)?

Note that the question is NOT asking about the number of "nodes" at depth k. It is about the number of "distinct states" at depth k (not counting the number of states at depth < k). For example, a search tree has 4 distinct states with k=1. A search tree may have 16 nodes at depth k=2 (if you use tree search), but only 8 distinct states (do NOT count the states already shown at depth 1). 4k C has 4 expanded nodes, depth 2 -> 4x2 = 8 green 3.3)

What is the maximum number of nodes expanded by breadth-first tree search when finding the goal at (x, y)? Roughly 4^(x+y) It’s bd, branching factor to depth of solution

3.4)

Is h=|u−x|+|v−y| an admissible heuristic for a state at (u,v)? Yes, The robot can only move in the grid directions.

3.5)

Does h remain admissible if some links are removed? Yes Removing links will increase actual path lengths, and the heuristic will be an underestimate.

3.6)

Does h remain admissible if some links are added between nonadjacent states? No, adding edges can reduce actual cost to below Manhattan distance Adding new links will decrease some actual path lengths and the heuristic will no longer be an underestimate.

4) A* tree search: Given the following undirected, weighted graph, representing a state space. Here each node in the graph represents a state, and the weight w(u, v) on an edge (u, v) indicates the cost of going from state u to state v (and it is also the cost from state v to state u).

Let state A be the initial state and state G be the goal state. The heuristic function h (which is admissible) is defined by the following table: 4.1) Draw the A* search tree obtained AFTER expanding the initial state. Show the f(n) value for each fringe node (write it below the node). Also in the picture, indicate which node ( you can mark it with a star next to the node) in fringe will be selected for expansion next. Let us call this node n1 (useful for next sub-question)

4.5) Show the sequence of states that form the optimal solution (shortest path from A to G), and the cost for the solution. A->B->D->F->G f = 10 5) Here we have a vacuum-cleaning agent that can sense the environment and perform actions to move around and vacuum-clean dirty squares.

5.1) Formulate the vacuum cleaning problem as a search problem. In this sub-problem, you would define the states, actions, the successor function, the goal test. You can assume the initial state has the top 5 squares all dirty, and the agent is located at the bottom left square. You can represent each square in the 5x5 grid world by (x, y) with the bottom left square = (1, 1), and top right square = (5, 5). How do you represent a state? state space: 5x5 grid, which squares are clean and dirty, current location of agent Initial state: top 5 squares all dirty, and the agent is located at the bottom left square (1,1) Actions: left, right, up, down, suck Successor: go to nearest dirty square Goal test: 5x5 grid is completely clean

5.2) In this sub-question, you should specify a step cost function COST(s1, a, s2)>0, which defines the cost of one step transition from state s1 to state s2 by applying action a. Keep in mind that cost of one step move consists of two parts: the cost due to move (which is always 1) and the cost due to remaining dirty squares.

Hint: If you use w(s2) to represent the number of dirty squares at the state s2 (the state reached after the action a), you would probably get a good sense about the part of step cost due to dirtiness. Answer: cost = w(s2)* 2 + 1 = 9 * 2 + 1 = 19 Q5.3 10 Points

Define an admissible heuristic function h1 for the vacuum cleaning search problem. h1(n) must be an under-estimate of the real cost from node n to goal state. Hint: h1(n) clearly should be related to the distance between the current agent location to some dirty square, and to the number of dirty squares at the state s associated with node n. Answer: (distance between current position and nearest dirty square position) + remaining dirty squares Q5.4 10 Points

Define another admissible heuristic function h2 for the vacuum cleaning search problem, such that h2 dominates h1. This means for any node n (associated with state s), we always have h2(n) >= h1(n). Answer: (distance between current position and farthest dirty square position)+ remaining dirty squares...