文件列表:

ACADEMIC_INTEGRITY.md (3658, 2023-08-18)
SELFEV.md (3770, 2023-08-18)
autograder.py (14889, 2023-08-18)
commands.txt (1148, 2023-08-18)
docker/ (0, 2023-08-18)
docker/Dockerfile (111, 2023-08-18)
docker/docker_config (98, 2023-08-18)
docker/docker_runner.sh (1500, 2023-08-18)
docker/requirements.txt (33, 2023-08-18)
eightpuzzle.py (8714, 2023-08-18)
game.py (25546, 2023-08-18)
ghostAgents.py (3108, 2023-08-18)
grading.py (10622, 2023-08-18)
graphicsDisplay.py (28042, 2023-08-18)
graphicsUtils.py (11979, 2023-08-18)
img/ (0, 2023-08-18)
img/alg1.png (72104, 2023-08-18)
img/loom_video.png (290191, 2023-08-18)
img/scientific_paper_graph_quality.png (13100, 2023-08-18)
keyboardAgents.py (3057, 2023-08-18)
layout.py (5782, 2023-08-18)
layouts/ (0, 2023-08-18)
layouts/bigCorners.lay (1405, 2023-08-18)
layouts/bigMaze.lay (1405, 2023-08-18)
layouts/bigOpenMaze.lay (1253, 2023-08-18)
layouts/bigSafeSearch.lay (256, 2023-08-18)
layouts/bigSearch.lay (480, 2023-08-18)
layouts/boxSearch.lay (210, 2023-08-18)
layouts/capsuleA1.lay (69, 2023-08-18)
layouts/capsuleA2.lay (83, 2023-08-18)
layouts/capsuleClassic.lay (141, 2023-08-18)
layouts/capsuleIDA1.lay (83, 2023-08-18)
layouts/capsuleIDA2.lay (59, 2023-08-18)
layouts/contestClassic.lay (189, 2023-08-18)
layouts/contoursMaze.lay (241, 2023-08-18)
layouts/greedySearch.lay (55, 2023-08-18)
layouts/mediumClassic.lay (231, 2023-08-18)
layouts/mediumCorners.lay (433, 2023-08-18)
... ...

# COMP90054 AI Planning for Autonomy - Assignment 1 - Search You must read fully and carefully the assignment specification and instructions detailed in this file. You are NOT to modify this file in any way. * **Course:** [COMP90054 AI Planning for Autonomy](https://handbook.unimelb.edu.au/subjects/comp90054) @ Semester 2, 2023 * **Instructor:** Dr. Nir Lipovetzky and Prof. Adrian Pearce * **Please note that we have two deadlines** * **Code Deadline:** Wednesday 16th August, 2023 @ 11:59pm * **Self-Evaluation Deadline:** Friday 18th August, 2023 @ 11:59pm (end of Week 4) * **Course Weight:** 10% * **Assignment type:**: Individual (you can work with another student on the code, but submit your own repo and self-evaluation) * **ILOs covered:** 1, 2, and 3 * **Submission method:** via GitHub using tagging (see [Submission Instructions](#submission-instructions) below for instructions) The **aim of this assignment** is to get you acquainted with AI search techniques and how to derive heuristics in Pacman, as well as to understand how to model a problem with python.

## Ungrading In COMP90054, we will use ungrading for the coursework component of the subject. Even though we are required to provide a grade out of 100, throughout the assignments, subject staff will not assign grades to anyone. Instead, we will use a combination of techniques that uses each student’s reflection of their own learning to provide grades. #### Why use ungrading? Who is better at assessing how much a student has leant: the student themselves, or a subject tutor/coordinator? I don’t imagine anyone would disagree that the student does. So why don’t we give students a say? For the coursework component of COMP90054 (assignments 1-3), the model that we employ cedes the power responsibility for monitoring and assessing progress to the students themselves. Research shows that grades and rubrics have three reliable effects on students in a class: 1. they tend to think less deeply; 2. they avoid taking risks; and 3. they lose interest in the learning itself, We want to encourage all three of these things. How will a student know if they are doing well? They will receive feedback on assessment throughout the semester. Feedback will be qualitative with broad ratings: needs further work; good; or outstanding; but these ratings will NOT be used for grading. Our detail feedback will be focused on your self-evaluation to facilitate and maximise your learning. Consider the following: - You have a good idea of what marks you will get prior to receiving them through our automated tests, this self-feedback approach means that if you want a higher mark, you know what you may have to do. - Tell us what you tried and didn't work, tell us what you learned while coming up with the solution, tell us why your solution doesn't pass a test, and how would you fix it if you had more time. All this reflection and evaluation give us better tools to assess your learning and provide you with useful feedback. - Since the assessment is self-directed, you understand well what your code is meant to do and the important lessons you acquired and want to convey with your code to us. It's easier for you to spend 10 - 20 hours with your code and come up with a comprehensive assessment than one tutor to do this for 30 - 50 students. Some of the possible reasons for mark misalignment of ungrading: - You're applying the knowledge you've learned to the task, *it is possible you've missed something critical*, even if you receive feedback about your assignment, the level of importance of each error or issue may not be clear. - *Perception of feedback length vs lost marks*. Contrast how seeing you lost 2 marks for returning suboptimal solutions suggests it is very wrong even with a small bit of feedback, and how seeing two pages of comments for improvements but no mark deduction suggests that there's lots to improve, but the quality of your solution is still ultimately good for someone early on their AI journey. Concentrate on the feedback. As a rule of thumb, give a good overview of your learning in your self-evaluation, It will significantly help tutors to provide feedback on your learning, which is what you want at this stage. - In the ungrading process, *you'll likely need to develop methods for verifying the correctness of your results*, not relying only on the more centralised and inflexible nature of automated tests approach. This is often extremely valuable in and of itself, as it forces you to design tests for your code, a vital principle in code development. That said, the centralised automated tests should give you a grounding sense of the correctness of your code. #### Length of the Self-Evaluation There's a tendency to conflate writing a lot for the self evaluation as being positive. On the contrary, be concise, and to the point. Practice your ability to synthesise important information, it is important for your communication skills. A self-assessment can be short AND good. There is no need to write pages of text -- just justify why you did a good job and learnt things. #### Final words (about ungrading) The objective is to reflect on your own learning, and take more risks, as you can justify it in your evaluation. In our positive experience with ungrading last semester in COMP90054, and corroborated by [research](https://www.jessestommel.com/how-to-ungrade/) (see bibliography, e.g. [Teaching more by grading less](https://www.lifescied.org/doi/full/10.1187/cbe.cbe-14-03-0054)), reasons people liked ungrading are chiefly: - Independence and autonomy: people felt more responsible for their own learning and appreciated the additional autonomy and independence that ungrading provided. - Reduced the stress of trying to get everything right and figure out what the staff wanted to see. - Allowed people to explore and take a few more risks, because if they failed, learning still occurred. #### Collaboration Assignment 1 can be completed individually or in pairs. We encourage pairs to work together to learn from each other; not to simple split the tasks for efficiency. But we will not monitor this – it is your responsibility. You can submit different solutions, we just want to encourage collaboration. For the student works in pair, you must submit an individual short self evaluation ([SELFEV.md](SELFEV.md)). In addition, you can either submit the same coding solution (both need to submit in their own repo using tag), or submit different coding solution. We encourage students to derive their own tests and share them with others to help with learning. ## Your tasks Since the purpose of assignments is to help you learn more, marks should not be assigned only on whether your code passes a few test cases but also on how much you have learnt. Who knows better about whether you have learnt from this assignment other than yourself? We ask you to evaluate your work. Each submission will contain a short self-reflection on what the student learnt, how they approached the tasks (including writing new tests) and will give the student a chance to argue that, even though they didn’t complete a task, they tried and learnt from it. More generally, In the past we saw several people either not submitting a self evaluation or not really taking the time to reflect on their learning. In this assignment, we make the expectations clearer: **students are marked based on their self evaluation.** Your task contains programming excercises with increasing difficulty. This is where we give students control over how much assessment they want to complete or have the time to complete. * [Programming Tasks](#programming-tasks): * [Practice](#practice) * [Part 0 (0 marks)](#part-0-0-mark-but-critical) * [Part 1](#part-1-3-marks) * [Part 2](#part-2-3-marks) * [Part 3](#part-3-4-marks) * [Self Evaluation Task (10 marks)](#self-evaluation-task-10-marks) * [Submission Instruction](#submission-instructions) ### Programming Tasks: You **must build and submit your solution** using the sample code we provide you in this repository, which is different from the original [UC Berkley code base](https://inst.eecs.berkeley.edu/~cs188/fa18/project1.html). * Please remember to complete the [SELFEV.md](SELFEV.md) file with your individual submission details (so we can identify you when it comes time to submit). * You should **only work and modify** files [search.py](search.py) and [searchAgents.py](searchAgents.py) in doing your solution. Do not change the other Python files in this distribution. * Your code **must run _error-free_ on Python 3.8**. Staff will not debug/fix any code. Using a different version will risk your program not running with the Pacman infrastructure or autograder. * Your code **must not have any personal information**, like your student number or your name. That info should go in the [SELFEV.md](SELFEV.md) file, as per instructions above. If you use an IDE that inserts your name, student number, or username, you should disable that. * **Assignment 1 FAQ** is available to answer common questions you might have about [Assignment 1 on ED](https://edstem.org/au/courses/12628/discussion/1460556) * **Getting started on GitHub** - the video below explains how to **clone**, **git add**, **commit** and **push** while developing your solution for this assignment: [](https://www.loom.com/share/ae7e93ab8bec40be96b638c49081e3d9) #### Setting up the environment * You can set up your local environment: * You can install Python 3.8 from the [official site](https://peps.python.org/pep-0569/), or set up a [Conda environment](https://www.freecodecamp.org/news/why-you-need-python-environments-and-how-to-manage-them-with-conda-85f155f4353c/) or an environment with [PIP+virtualenv](https://uoa-eresearch.github.io/eresearch-cookbook/recipe/2014/11/26/python-virtual-env/). * You need to install additional package (func_timeout) using: `pip3 install func_timeout` * Alternatively, you can use docker: * You need to install docker from the [official site](https://docs.docker.com/get-docker/) * Please check [Docker Run](#docker-run) to run your code. #### Practice To familiarize yourself with basic search algorithms and the Pacman environment, it is a good start to implement the tasks at https://inst.eecs.berkeley.edu/~cs188/fa18/project1.html, especially the first four tasks; however, there is no requirement to do so. You should code your implementations *only* at the locations in the template code indicated by ```***YOUR CODE HERE***``` in files [search.py](search.py) and [searchAgents.py](searchAgents.py), please do not change code at any other locations or in any other files. #### Part 0 (0 mark, but critical) This is a great way to test that you understand the submission instructions correctly, and how to get feedback from our hidden test-cases as many times as you want. Here are the steps: * Please tag your solution with `test-submission`. If you are not familiar with tag, please check [tag hints](#git-hints-on-tags) * We are going to run your code in our server. You can check your result from this [link](https://tinyurl.com/comp90054-a1-server) after a few minutes. This can test your code for part 1, 2 and 3. #### Part 1 Implement the **Enforced Hill Climbing (EHC) algorithm** discussed in lectures, using Manhattan Distance as the heuristic, by inserting your code into the template indicated by comment ```***YOUR CODE HERE FOR TASK 1***```. You can see the code location following this link: [search.py#L150](search.py#L150). > **Note** > You don't have to implement Manhattan Distance, as this has already been implemented for you in the codebase. You will need to call the heuristic from your implementation of EHC. You should be able to test the algorithm using the following command: ``` python pacman.py -l mediumMaze -p SearchAgent -a fn=ehc,heuristic=manhattanHeuristic ``` Other layouts are available in the [layouts](layouts/) directory, and you can easily create you own. When you use the `autograder` (see section [cheking submission](#checking-your-submission) ), it will try to validate your solution by looking for an exact match with your output. The successors list are expected to be visited in the original order given by the API. #### Part 2 In this part we will help you prove to yourself that you have all the ingredients to pick up many new search algorithms, tapping to knowledge you acquired in the lectures and tutorials. **Bidirectional A\* Enhanced (BAE\*)** is a search algorithm that searches in both directions, from the intial state to the goal state, and from the goal state towards the initial state, and keeps track of solutions found when the two directions meet. In Part 2, for simplicity, we assume there is only one goal state and no food, hence, progression and regression both search in the same state space, one uses the transition function forward, and the other backward. This algorithm has not been introduced in the lectures but it relies on ingredients which you already know: * **A\***, * the evaluation function used to guide the expansion order in **A\***, and * the definition of the transition function to generate a graph implicitly while searching. **BAE\*** is similar to A*, but: 1. It has two open lists (lines 1-2, Alg. 1) to alternate (line 22) expanding nodes (line 9) from the forward and backward lists. 2. While searcing, it keeps a lower bound and upper bound to know when to stop the search, i.e. when (line 15), the incumbent solution has been proved to be optimal. The lower bound is updated each time a node is selected for expansion (lines 5-9, Alg. 1), keeping track of the average value in both directions (line 8). Note that if the heuristic is **admissible**, then the minimum value in the open lists represent a lower bound on the optimal solution cost. 3. The upperbound is only updated if the current node exists in the open list of the opossite direction , which means that the two directions meet through node , and (the cost of the path form the initial state to ) + (the cost of the path from to the initial state of the opposite direction) is smaller than the best solution known so far, i.e. (line 11). If that's the case, keep the solution and update the upperbound (lines 12-13). 4. The priority used to order nodes in the openlists is slightly different than A*. Given that every time a node is chosen for expansion we know that its value represents the optimal cost to node in direction , then we can characterize and correct the innacuracy of the heuristic used in the opposite direction as . This value is added to and used to set the priority of each generated node (lines 18-20).  This algorithm is taken from the [paper](https://ojs.aaai.org/index.php/SOCS/article/view/21756/21520) presented at the [Symposium on Combinatorial Search](https://sites.google.com/unibs.it/socs2022/home?authuser=0), on the 22nd of July, 2022. Bidirectional search is currently a hot research topic given recent theoretical results and simple practical algorithms such as BAE*. The paper that introduced these results received a prestigious best paper award in a [top conference in AI](https://aip.riken.jp/award/aaai-20_honorable_mention/). This context alone should motivate you: you are literally implementing a cutting-edge search algorithm. Tips for your implementation: - Checking membership of a node in the opposite open (line 11), can be a computationally expensive operation (worst case linear in the size of the open, which in turn is exponential as the depth of the search increases). This is specially relevant as this line is executed for every expanded state. Think back about your Data Structures course, and use an auxiliary data structure to implement the membership test efficiently for this assignment. Otherwise, BAE* will be way slower than A*, even if it expands less nodes. - To understand what the search is doing, make sure that you understand the successor generators in both directions. In Backward search, given an action and state , you need to generate the state from which the application of resulted in state . - The function `getBackwardsSuccessors` already reverses the action for backwards search. - The function `getGoalStates` returns a list of all possible goal states. Implement the **BAE\* algorithm** discussed above by inserting your code into the template indicated by comment ```***YOUR CODE HERE FOR TASK 2***```, you can view the location at this link: [search.py#L169](search.py#L169). You should be able to test the algorithm using the following command: ``` python pacman.py -l mediumMaze -p BidirectionalSearchAgent -a fn=bae,heuristic=manhattanHeuristic,backwardsHeuristic=backwardsManhattanHeuristic ``` Other layouts are available in the layouts directory, and you can easily create your own. The `autograder` will seek for exact match of the solution and the number of node expansions. The successors list are expected to be visited in the original order given by the API. If your node expansion number is incorrect, please try to **reverse** it. An example is given as follows: ``` succs = problem.getSuccessors(state) succs.reverse() ``` #### Part 3 This part involves solving a more complicated problem. You will be able to model the problem, using the **BAE\* algorithm** from part 2 and design a heuristic function (optionally) that can guide the search algorithm. Just like in Q7 of the Berkerley Pacman framework, you will be required to create an agent that eats all the food (dots) in a maze. ... ...

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：