Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Artiicial Intelligence

You will be examining search strategies for the 15-puzzle, admissible heuristics for a trajectory planning problem, and pruning in alpha-beta search trees. You should submit a report in .pdf format with answers to the questions below.

Question 1:  Search Strategies for the 15-Puzzle (2 marks)

For this question you will construct a table showing the number of states expanded when the 15-puzzle is solved, from various start positions, using four diferent search strategies:

(i)    Breadth First Search

(ii)    Iterative Deepening Search

(iii)   Greedy Search (using the Manhattan Distance heuristic)

(iv)   A* Search (using the Manhattan Distance heuristic)

Unzip the ile and change directory to path search

unzip path_search. zip

cd path_search

Run the code by typing:

python3 search.py --start 2634-5178-AB0C-9DEF --s bfs

The --start argument speciies the start position, which in this case is:

BFS: --s bfs

IDS: --s dfs --id

Greedy: --s greedy

A*Search: --s astar

We irst consider a 1-dimensional version of GPGP where the vehicle moves through integer locations on a number line, with no obstacles.  Assume the Goal is at location n, and that the agent starts at location 0, with velocity k. We will use M (n, k) to denote the minimum number of time steps required to arrive and stop at the Goal.  Clearly M (一n, 一k) = M (n, k) so we only need to compute M (n, k) for k ≥ 0.

(a) Starting with the special case k = 0, compute M (n, 0) for 1 三 n 三 21 by writing down the optimal sequence of actions for all n between 1 and 21.  For example, if n = 7 then the optimal sequence is [+ + 。一 。一] so M (7, 0) = 6. (When multiple solutions exist, you should pick the one which goes  “fast early” i.e. with all the +’s at the beginning.)

(b) Assume n ≥ 0.  By extrapolating patterns in the sequences from part (a),

explain why the general formula for M (n, 0) is

where  Lz」denotes z rounded up to the nearest integer.

Hint:  Do not try to use  recurrence relations.  You should instead use this identity:

(c) Assuming the result from part (b), show that if k ≥ 0 and n ≥ 2/1 k(k−1) then

Hint: Consider the path of the agent as part of a larger path.

(d) Derive a formula for M(n, k) in the case where k ≥ 0 and n < 2/1k(k−1).

(e) Write down an admissible heuristic (that approximates the true number of moves as closely as possible) for the original 2-dimensional GPGP game in terms of the function M () derived above.

Hint: Consider the horizontal and vertical motion separately, keeping in mind that, unlike the 15-puzzle, the agent can move in the horizontal and vertical direction simultaneously. Your heuristic should be of this form:

h (r, c, u, v, rG , cG ) = max(M (.., ..), M (.., ..))

Question 4:  Game Trees and Pruning (3 marks)

(a)  Consider a game tree of depth 4, where each internal node has exactly two children (shown below). Fill in the leaves of this game tree with all of the values from 0 to 15, in such a way that the alpha-beta algorithm prunes as many nodes as possible. Hint: make sure that, at each branch of the tree, all the leaves in the left subtree are preferable to all the leaves in the right subtree (for the player whose turn it is to move).

(b)  Trace through the alpha-beta search algorithm on your tree, clearly show- ing which of the original 16 leaves are evaluated.

(c)  Now consider another game tree of depth 4, but where each internal node has exactly three children.  Assume that the leaves have been assigned in such a way that the alpha-beta algorithm prunes as many nodes as possible.  Draw the shape of the pruned tree.  How many of the original 81 leaves will be evaluated?

Hint:  If you look closely at the pruned tree from part  (b) you will see a pattern.  Some nodes explore all of their children; other nodes explore only their leftmost child and prune the other children.  The path down the extreme left side of the tree is called the line of best play or Principal Variation (PV). Nodes along this path are called PV-nodes.  PV-nodes explore all of their children. If we follow a path starting from a PV-node but proceeding through non-PV nodes, we see an alternation between nodes which explore all of their children, and those which explore only one child. By reproducing this pattern for the tree in part (c), you should be able to draw the shape of the pruned tree (without actually assigning values to the leaves or tracing through the alpha-beta algorithm).

(d) What is the time complexity of alpha-beta search, if the best move is always examined irst (at every branch of the tree)? Explain why.