COMPSCI 367 S2 2022: Artificial Intelligence - Assignment 1: Greedy Best-First Search versus A*
CS367 S2 2022: Artificial Intelligence - Assignment 1
Due Date: August 28 , 2022, 23:59pm
READ BEFORE YOU START:
You will need to use Python to do this assignment. The code is using Python 3.7, but it should work with later versions. It will not run with Python 2.
Advice to run the assignment code on your personal computer:
1. Download the S22022_A1.zip file.
2. Extract all the contents in a folder dedicated to your assignment.
3. Create a virtual environment to run the assignment code, in the previous folder (about using virtual environments with Python, see link).
4. Activate the virtual env. and run “pip install -r A1\requirements.txt” to install all the packages needed in the virtual env.
5. Run search.py to see if you get any error (should not output anything as there are no function/class calls in it).
6. You can then work in the virtual env. without “contaminating” your global python setup.
You should only make changes to the search.py file. Do not change any other file. You can add code in the existing functions, and also at the end of the file (for new classes and functions, as well as a main() function to run your experiments).
For better readability (the markers will appreciate it), we ask you to add comments where you add code, referring to the task you are solving by making those changes/additions.
Topic: Greedy Best-First Search versus A* (10 marks)
Task1: (1 mark) – Instrument A* search and implement greedy search
Instrument the astar_search function code (you actually need to put your code in the best_first_graph_search function called in astar_search) in search.py so that it retrieves and prints out (without display argument being True):
1. the number of expanded nodes (when a node is removed from the open list and added to the close list),
- the number of generated nodes (when a node is created from its parent),
- the number of duplicate nodes (when the state is already in the open list or the
In addition, add a function greedy_search to implement a greedy search algorithm (there is a comment above astar_search in the search.py file saying how to do this). You should be able to call it as you would call astar_search, e.g.: astar_search(EightPuzzle((1,2,3,4,0,6,7,5,8))) greedy_search(EightPuzzle((1,2,3,4,0,6,7,5,8)))
Task 2: (1 mark) – Implementing heuristics for the Eight Puzzle problem
Find the “misplaced tile” heuristic that is already in the EightPuzzle class code, and rename it h_mt.
Implement the Manhattan distance heuristic for the EightPuzzle class (call it h_man).
Task3: (1 mark) – Compare A* search and greedy search
Run the following 5 problems with both the “misplaced tiles h” (this is given in the code) and your Manhattan heuristics for A* search and greedy search. For each run, retrieve the number of expanded nodes and the solution path length.
The five problems you should run are:
Problem | Optimal solution path length |
EightPuzzle((1,2,3,4,5,6,0,7,8)) | 2 |
EightPuzzle((4,1,3,2,6,8,7,5,0)) | 8 |
EightPuzzle((7,1,6,3,0,4,5,8,2)) | 16 |
EightPuzzle((3,1,6,5,8,7,0,2,4)) | 22 |
EightPuzzle((4,2,1,6,0,5,3,8,7)) | 24 |
Fill the following table with your results to compare the results you get with A* and greedy:
Heuristic |
| Prob1 | Prob2 | Prob3 | Prob4 | Prob5 |
Misplaced Tile
| A* expanded nodes |
|
|
|
|
|
Greedy expanded nodes |
|
|
|
|
| |
A* solution path length |
|
|
|
|
| |
Greedy solution path length |
|
|
|
|
| |
Manhattan
| A* expanded nodes |
|
|
|
|
|
Greedy expanded nodes |
|
|
|
|
| |
A* solution path length |
|
|
|
|
| |
Greedy solution path length |
|
|
|
|
|
Task 4: (2 marks) – Implement the Bubble Puzzle game
Make a new class BubblePuzzle to solve the following type of puzzle/game (you can inspire yourself from the EightPuzzle class):
https://www.crazygames.com/game/bubble-sorting
We advise you to first play a few stages of the game to better understand how it works, and then formulate the problem (state representation, successor function, initial state, goal test), to guide your implementation.
Task 5: (2 marks) – Implement heuristics for the Bubble Puzzle game
Make two heuristics, h1 and h2, for the Bubble Puzzle game. h1 should be stronger than h2 and neither should be the 0-heuristic. Implement them in your BubblePuzzle class.
Since you are running A*, you should make sure your heuristics are admissible and consistent. If your heuristic is not admissible or not consistent you might notice that you are getting solutions longer than optimal. If you see solutions shorter than optimal, you have a bug in your actions or your goal test.
Task6: (3 marks) – Report about how A* search compares with Greedy search
Write a report discussing how A* compares to greedy search when you have a weak heuristic and a stronger one. Use the table from task 3 and include a similar table for the BubblePuzzle.
Task7: (Extra for Experts - 1 bonus mark – a bonus mark can be used to offset any lost marks in any assignment – but you cannot get more than 30 marks in the practical section)
1. Make your code handle inconsistent heuristics.
2. Make an admissible and inconsistent heuristic for the Eight Puzzle.
3. Prove that your heuristic is admissible and inconsistent.
4. Instrument your code to print out reopened nodes (a duplicate node whose g-value
What you need to turn in:
You need to turn in a search.py file with all your code.
You need to turn in a .pdf file of 2 page MAXIMUM (it can be 4 pages if you did the extra for experts task) which should include:
1) The expanded nodes table for the both sliding tiles and bubble sort.
2) A discussion of how you think greedy compares to A* when the heuristic is weak versus when it is strong. Also, how the number of nodes expanded is affected by
whether a solution path is short or long.
Marking is based on the following criteria:
• 1 mark for having instrumented the code correctly and created greedy search, • 1 mark for implementing the Manhattan Heuristic for sliding tiles,
• 1 mark for having the correct results table for EightPuzzle from task 3,
• 2 marks for implementing BubblePuzzle Class correctly,
• 2 marks for implementing two BubblePuzzle Heuristics,
• 2.5 marks for a discussion of how greedy and A* compare as the heuristic gets
better or the solution path gets longer (this must be IN YOUR OWN WORDS), • 0.5 mark for including the table for BubblePuzzle results from task 5,
• 1 bonus mark for experts.
The zip file can be found in the Assignment announcement.
The assignment must be submitted to Canvas. It will be run through Turnitin.
