Artificial Intelligence | AI代写 | report代写 | Algorithm代写 | Python | 作业assignment – CS367 S2 2022: Artificial Intelligence

CS367 S2 2022: Artificial Intelligence –

Artificial Intelligence | AI代写 | report代写 | Algorithm代写 | Python | 作业assignment – 这个题目属于一个AI的代写任务, 涉及了AI/Algorithm/Python等代写方面, 该题目是值得借鉴的assignment代写的题目

算法代写 代写算法 Algorithm代写 代写Algorithm  算法作业代写

assignment 1

Worth: 10% of total grade [10 marks] Due Date: August 28th, 2022, 23:59pm


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. Extract all the contents in a folder dedicated to your assignment.
  2. Create a virtual environment to run the assignment code, in the previous folder (about using virtual environments with Python, see link).
  3. Activate the virtual env. and run pip install -r A1\requirements.txt to install all the packages needed in the virtual env.
  4. Run to see if you get any error (should not output anything as there are no function/class calls in it).
  5. You can then work in the virtual env. without contaminating your global python setup.

You should only make changes to the 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.

There is quite a bit of code in the file as it can be used for other tasks. The instructions for each task in this assignment will guide you about which part you should focus on. However, you should start by spending some time understanding how the code is structured to be able to add your own parts.

Make sure you read the last section What you need to turn in before you submit your assignment.

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 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),
  2. the number of generated nodes (when a node is created from its parent),
  3. the number of duplicate nodes (when the state is already in the open list or the closed list),
  4. the solution path, and
  5. the solution path length.

In addition, add a function greedy_search to implement a greedy search Algorithm (there is a comment above astar_search in the 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 Prob
A* expanded
Greedy expanded
A* solution path
Greedy solution
path length
A* expanded
Greedy expanded
A* solution path
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):

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.

The class should be called as follows: astar_search(BubblePuzzle([[ORANGE, PURPLE], [], [], [ORANGE, PURPLE]]))

This is an initial state with 4 bottles. The first bottle has purple at the bottom and orange at the top, the two next bottles are empty, and the last bottle has purple at the bottom and orange at the top.

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.

To help you out, here are 4 problems and their optimal solution path length: Problem Solution path length



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 is lower than the node with the same state in the open list or the closed list)

What you need to turn in: You need to turn in a 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.

Copyright Warning Notice
Copyright University of Auckland. This material is provided to you for your
own use. You may not copy or distribute any part of this material to any other
person. Failure to comply with this warning may expose you to legal action for
copyright infringement and/or disciplinary action by the University.