” 辅导COMP90054程序、 写作Python语言编程The University of MelbourneSchool of Computing and Information SystemsCOMP90054 AI Planning for AutonomyProject 1, 2021Deadline: Thursday 1st April 18:00This project counts towards 10% of the marks for this subject.This project must be Done individually.AimsThe aim of this project is to improve your understanding of various search algorithms usingthe Berkely Pac Man framework.Getting startedBefore starting the assignment you must do the following:Create a github account at httpss://www.github.com if you dont already have one.Visit httpss://classroom.github.com/a/XQszkhjs and accept the assignment. Thiswill create your personal assignment repository on github.Clone your assignment repository to your local machine. The repository contains theframework that you will need in order to complete the assignment.Complete the following form:This allows us to link your University ID to your github ID so that we can mark yourassignment.1Practice Task (0 marks)To familiarise yourself with basic search algorithms and the Pacman environment,how to interact with the Framework, I have provided an implementation of the depth firstsearch algorithm.Part 1 (1 mark)Implement the A* Algorithm described in lectures. You should be able to test the algorithmusing the following command:python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristicOther layouts are available in the layouts directory, and you can easily create you own!Part 2 (3 marks)The recursive best first search algorithm is designed to enable optimal solutions to be foundwhile using less memory than A*. It may be used to find optimal solutions for memoryconstrainedproblems. The algorithm is defined on page 99 of [2] (which you can access fromthe University library and is linked to in the Week 1 and 2 modules on Canvas) and reproducedhere for your convenience:Note that this is a tree-search algorithm which does not consider repeated states. For example,moving Pacman down and then up again would produce a new state. As a result, thealgorithm will expand a large Number of search nodes in order to find solutions to problems.I encourage you to consider how you could modify the algorithm to reduce the number ofnodes generated without requiring too much memory, but for the purposes of this question2you should implement the Algorithm as described. You should be able to test the algorithmusing the following command:python pacman.py -l tinyMaze -p SearchAgent -a fn=rebfsOther layouts are available in the layouts directory, and you can easily create you own!Part 3 (4 marks)We now consider a slight change to the rules of Pacman, specifically allowing non-uniformaction costs. For the purposes of this question, moving Pacman to a square that is empty orcontains food has a cost of 1, while moving Pacman to a square that contains a Capsule hasa cost of 0. Note that once Pacman eats the capsule the square becomes empty so movingPacman back to that square would incur a cost of 1.We wish to solve the problem of eating all The food in the maze in as few steps as possible.For this, well need a new search problem definition which formalizes the food-clearing problem:FoodSearchProblem in searchAgents.py (implemented for you). A solution is defined tobe a path that collects all of the food in the Pacman world. You should already be able tosolve this problem using Your A* Search implementation with the null Heuristic, but you willfind that heuristic quite inefficient. As a reference, our implementation expands over 100,000node to find a solution of length 25 for task3search.Your task is to implement foodHeuristic in order to improve the efficiency of A* searchfor this problem. Recall that in order to find optimal solutions to the problem, your heuristicmust be admissible.Non-Trivial Heuristics: The trivial heuristics are the ones that return zero everywhere(UCS) and the heuristic which computes the true completion cost. The former wont saveyou any time, while the latter will timeout the autograder. You want a heuristic which reducestotal compute time, though for this assignment the autograder will only check nodecounts (aside from enforcing a reasonable time limit).Grading: Your heuristic must be a non-trivial non-negative admissible heuristic to receiveany points. Make sure that your Heuristic returns 0 at every goal state and never returns anegative value. Depending on how few nodes your heuristic expands on task3search, youllbe graded:Number of nodes expanded GradeLess than 20,000 1/4Less than 10,000 2/4Less than 5,000 3/4Less than 2,500 4/4You can check the performance of your algorithm by running the following command:python pacman.py -l task3Search -p AStarFoodSearchAgentSince this computation can take some time for less efficienct heuristics, you may wish to startby verifying that your heuristic finds an optimal solution for task3Small and task3Medium.3Part 4 (2 marks)Challenge QuestionNote that this is a much more difficult question that requires you to interpret andimplement an algorithm from a research paper. Learning to implement it successfullywill give you great experience in solving a modern AI planning problemand experience in self-directed learning something that is valuable in general,but particularly with contemporary AI techniques, but is not necessary in orderto do well in the subject. As a result there is only a small mark allocation forthis question.Deceptive path-planning involves finding a path to a goal that makes it difficult for an outsideobserver to guess what that goal might be. This paper by Masters and Sardina describes anumber of algorithms for deceptive path-planning [1]. The main idea is that an agent has atrue goal as well as one or more false goals. The agent plans a path to the true goal designedto make it difficult for an observer to figure out whether it is trying to reach the true goal orone of the false goals.Your task is to implement Two of the strategies described in [1] using the Pacman framework.For each of the deceptive path planning layouts, assume that the true goal is representedby the Capsule and that the false goals are represented by Food.a) {1 mark} Implement an agent that uses the d2 strategy. You can call your agent usingthe following commandpython pacman.py –layout deceptiveMap –pacman pid2DeceptiveSearchAgentb) {1 mark} Implement an agent that uses the d3 strategy. You can call your agent usingthe following commandpython pacman.py –layout deceptiveMap –pacman pid3DeceptiveSearchAgentNOTE: You should not change any files other than search.py and searchAgents.py. Youshould not import any additional libraries into your code. This risks being incompatible withour marking scripts.Checking your submissionRun the command:python autograder.pyWe have provided some tests, called task1, task2, task3, task41 and task42. It is importantthat you are able to run the autograder and have these tests pass, otherwise, our markingscripts will NOT work on your submission. While the final tests will be similar to thoseprovided, we will vary the final test layouts to prevent hardcoded action paths from achievingany marks.Marking criteriaThis assignment is worth 10% of your overall grade for this subject. Marks are allocatedaccording to the breakdown listed above, based on how many of our tests the algorithms4pass. No marks will be given for code formatting, etc.SubmissionEnsure that you have pushed your files to the repository and completed the form in theGetting Started section before the due date.The master branch on your repository will be cloned at the due date and time.From this repository, We will copy only the files: search.py and searchAgents.py. Donot change any other file as part of your solution, or it will not run. Breaking these instructionsbreaks our marking scripts, delays marks being returned, and more importantly, givesus a headache.Note: Submissions that fail to follow the above will be penalised.Originality MultiplierWe will be using a code similarity comparison tool to ensure that each students work istheirown. For code that is similar to another submission or code found online, an originalitymultiplier will be applied to the work. For example, if 20% of the assessment is deemedtohave been taken from another source, the final mark will be multiplied by 0.8.Late submission policySubmissions that are late will be penalised 1 mark per day, up to a maximum of 5 marks.Academic MisconductThe University misconduct policy1 applies. Students are encouraged to discuss the assignmenttopics, but all submitted work must represent the individuals understanding of thetopic. The subject staff take academic misconduct seriously. In the past, we have prosecutedseveral students that have breached the university policy. Often this results in receiving 0marks for the assessment, And in some cases, has resulted in failure of the subject.Important: As part of marking, we run all submissions via a code similarity comparisontool. These tools are quite sophisticated and are not easily fooled by attempts to make codelook different. In short, if you copy code from classmates or from online sources, you riskfacing academic misconduct charges.But more importantly, the point of this assignment is to have you work through a series offoundational search algorithms. Successfully completing this assignment will make the restof the subject, including other Assessment, much smoother for you. If you cannot work outsolutions for this assignment, submitting another persons code will not help in the long run.1See httpss://academichonesty.unimelb.edu.au/policy.html请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
