Implement a general search as described on the slides, with OPEN and CLOSED lists. Implement different OPEN list orderings (for best-first, depth-first, Best-First, and A* (2.5pts, Attrib. 5) 2. Implement a successor state generator for the 8-puzzle (2.5pts, Attrib 5) 3. Implement Hamming distance, Manhatten distance, Permutation Inversion heuristics for the 8-puzzle (2pts, Attrib. 5) 4. Compare the length of the search path and the optimality of the solution found for Best-First and A* for the three admissible heuristics mentioned above plus an inadmissible heuristic (you may use the one from Assignment 1) (1pt, Attrib 1,4) 5. On March 10, 2022, I will post an initial configuration that you have to solve with your code. Report on your solution in your report. (1pt, Attrib 5,4) 6. Provide ample and clear documentation in-line in your code and in a report. The report should be an electronic document in .pdf that shows how the different heuristics perform on different test runs for both, Best-First and A* (in tabular form) with some analysis and explanation. Explain what happens for the inadmissible heuristic. (Make sure the marker knows which one is the inadmissible one in the code, too.) Explain how many experiments you have run to compile the table (1pt, Attrib 1,4)
Comp 472 Mini-Project 1 Fall 2022 Due date: March 12th, 2022 Goal: Implement A* search and test different heuristics for the 8-puzzle using the goal state from the book: 1 2 3 8 _ 4 7 6 5 Input: a state is a board configuration in form of a list. The board configuration of the goal state would be represented as: ‘(1 2 3 8 B 4 7 6 5). Remember, that not all initial configurations can be transformed into this goal configuration, take care with your test examples to be solvable. Output: A list of successive states, beginning with the start state and ending with the goal state, and including all states required to transform the start state into the goal state. For admissible heuristics this path should be optimal. Description: 1. Implement a general search as described on the slides, with OPEN and CLOSED lists. Implement different OPEN list orderings (for best-first, depth-first, Best-First, and A* (2.5pts, Attrib. 5) 2. Implement a successor state generator for the 8-puzzle (2.5pts, Attrib 5) 3. Implement Hamming distance, Manhatten distance, Permutation Inversion heuristics for the 8-puzzle (2pts, Attrib. 5) 4. Compare the length of the search path and the optimality of the solution found for Best-First and A* for the three admissible heuristics mentioned above plus an inadmissible heuristic (you may use the one from Assignment 1) (1pt, Attrib 1,4) 5. On March 10, 2022, I will post an initial configuration that you have to solve with your code. Report on your solution in your report. (1pt, Attrib 5,4) 6. Provide ample and clear documentation in-line in your code and in a report. The report should be an electronic document in .pdf that shows how the different heuristics perform on different test runs for both, Best-First and A* (in tabular form) with some analysis and explanation. Explain what happens for the inadmissible heuristic. (Make sure the marker knows which one is the inadmissible one in the code, too.) Explain how many experiments you have run to compile the table (1pt, Attrib 1,4) Submit your work in Moodle.