H

ICS 361, Artificial Intelligence Programming

Assignment 3

Part A

Modify the textbook's best-first implementation to do A* search on the 8-puzzle. Make your modifications as minimal as necessary to do A* search. In particular, add dynamic programming to the best-first implementation and include print statements that show when dynamic programming is being used and print the state with its old f(n) value and its improved f(n) value.

Include a test run of your program with the 18 move start state (3 5 2 0 1 6 7 8 4), which should have 2 cases where dynamic programming will find a shorter path to a state. For fun you can also test your program with this very long 23 move problem from start state (3 5 2 7 0 1 8 4 6). Don't turn in a test run of this one as the trace output is much too long.

Hints

The book's website best-first code does not implement the best-first algorithm described in pseudo-code on page 134 of Artificial Intelligence, Structures and Strategies for Complex Problem Solving. In particular, when the child is already on open the website code just ignores the child. The best-first pseudo-code says that best-first should check to see if the child was reached by a shorter path and if so, add it to open. This is the dynamic programming part. We keep only the best path to any state and throw away worse paths. Your assignment is to modify the website best-first Lisp code to add the dynamic programming part.

To remove a state-tuple from *open*, you can use the built-in remove function with :test #'equal. Note that remove creates a new list, so you will have to setq *open* to be the result of the remove function call. For greater efficiency, delete, the destructive version of remove can be used instead of remove, but the setq *open* is still needed as deleting the first item of *open* will not change *open* (deleting any other item other than the first one will change *open*).

My solution adds 14 lines of code, not counting blank lines, comment lines or lines that were not modified from the book's website best-first search code. Of the 14 added lines, 6 are print lines for printing the state and its old and new f(n). If your solution is taking much longer, you are probably doing something wrong and should come see me or our TA for help.

If you are not satisfied with your 8-puzzle solution for assignment 2, just send email to our TA to get a copy of the solution for use in testing your code for this assignment. Of course, once you request the assignment 2 solution, you can no longer (re)submit assignment 2.

Part B

Modify your solution for Part A to allow arbitrary values of g(n). The textbook code assumes that the cost of going from one state to another, g(n), is always 1. This assumption is fine for the farmer-wolf-goat-cabbage problem and for the 8-puzzle, but won't work for many other types of problems. Test your solution by coding a solution to the Romanian travel problem from Russell and Norvig's Artificial Intelligence: A Modern Approach textbook:

Romania A* gif

The actual g(n) costs are given in the diagram. For example, the cost for traveling from state Arad to state Sibiu is 140 and the cost from Oradea to Zerind is 71. The heuristic estimate, h(x), is only given for the goal of traveling to state Bucharest and are listed in the table to the right of the figure (so no other states can serve as the goal unless you extend the table).

Please put your Romania travel problem code in a separate file from the A* search code.

Include a test run of your program with start state Arad and goal Bucharest. Make sure your program follows the expected search path that you calculate by hand.

Hints

The Romanian travel problem is easily coded as a look-up table using assoc-lists. Encode the cost of traveling between two states such as Arad and Sibiu as an assoc-list with keys being a cons of the two states, e.g., (Arad . Sibiu) and value being the cost, e.g., 140. Likewise, the heuristic estimate is easily coded as a similar look-up table using a different assoc-list. In this case, the cdr of the keys will always be Bucharest as we have no data for any other potential goal state.

Generating legal moves can also be done with look-up tables. As the highest connectivity states, Bucharest and Sibiu, have 4 neighbors (Bucharest has neighbors Pitesti, Fagaras, Urzeceni, and Giurgiu), you will need 4 different functions: a function to generate the first neighbor connected to a state, a function to generate the 2nd neighbor, a function to generate the 3rd neighbor and a function to generate the 4th neighbor. For many states, the third neighbor function will return nil as many states have only 2 neighbors (e.g. Oradea). Only Sibiu and Bucharest will have non-nil values for the 4th neighbor function. Three states (Neamt, Eforie, and Giurgiu) will have nil for their 2nd neighbor functions.

My solution adds 1 line of code and modifies 1 line in the textbook's best-first search code. The Romanian travel problem adds another 56 lines of code, not counting blank lines, comment lines or debug printing lines. If your solution is taking much longer, you are probably doing something wrong and should come see me or our TA for help.

Submitting

Submit by zipping together your source code files (e.g., a3a.lisp and a3b.lisp) and your typescript file (e.g., typescripta.txt and typescriptb.txt) into a3.zip and then upload a3.zip to Assignment 3 on Laulima.


David N. Chin / Chin@Hawaii.Edu