COMP90054 AI Planning for Autonomy The University of Melbourne
School of Computing and Information Systems
Project 2, 2019
Contest: Pacman Capture the Flag
Deadline: 23:59 Wednesday 16 October 2019
This project counts towards 40% of the marks for this subject.
This is an team project-assignment and has to be done in groups of 3 (or 4).
The purpose of this project is to implement a Pac Man Autonomous Agent that can play and compete in a tournament.
http://ai.berkeley.edu/contest.html
Note that the Pacman tournament has different rules as it is a two teams game, where your Pacmans become ghosts in certain areas of the grid. Please read carefully the rules of the Pacman tournament. Understanding it well and designing a controller for it is part of the expectations. To help you develop your solution you must provide:
(i) A working Pac Man Agent that is capable of playing Pac-Man and competing in the tournament. Your Agent can use any technique, or combination of techniques, that you choose. For example using a classical off- the-shelf planner, Reinforcement Learning, Heuristic Search, Monte Carlo Tree Search or a purpose built decision tree of your own making (24 marks).
(ii) A recorded 5-minute oral presentation that outlines the theoretical or experimental basis for the design of your agents (i.e. why you did what you did), challenges faced, and what you would do differently if you had more time. Your presentation must end with a live demo of your different implementations, i.e. showing how the different techniques your tried work. The video will be shared with us through an unlisted youtube link in the Wiki of your GitLab repository. (10 marks).
(iii) A WIKI: describing the approaches implemented, a small table comparing your different agents showing their performance in several scenarios. Discuss briefly the table. The link for the recorded oral-presentation should be included in the wiki. (6 marks).
This project follows up from your Search agents for project 1. You should be familiarized with the pacman environment, and you can use variations of your search agents as a starting point for this project.
Corrections: From time to time, students or staff find errors (e.g., typos, unclear instructions, etc.) in the assignment specification. In that case, corrected version will be uploaded to the course LMS as quickly as possible and an announcement will posted in the course LMS and also to the forum (if they issue was related to a forum message). The date of the latest specification can be found in the bottom right of each page (S2 2019- Date).
Silent Policy: A silent policy will take effect 48 hours before this assignment is due. This means that no question about this assignment will be answered, whether it is asked on the newsgroup, by email, or in person.
Team Registration & GitLab Repo Setup
This is a group/team project assignment (groups of 3 or 4 students). There will be no need to explicitly submit anything for this assignment project, except filling the certification, as the repository on GitLab will represent the team’s submission (more details below).
COMP90054 AI Planning for Autonomy 1 S2 2019- September 15, 2019
A team should do the following (only one student member needs to do these steps):
1. Set-up project GIT repository:
• One of the members of the new team should fork privately the following template project repository in UoM GitLab using their Unimelb student account:
https://gitlab.eng.unimelb.edu.au/nlipovetzky/comp90054-pacman
This repository has the initial template for the contest under subdirectory pacman-contest/. Make sure:
• Click on the gitlab link above and Fork the repository forllowing these instructions.
• Repositorynamemustbeslightlychangedto“comp90054-pacman-
name of the project follow these instructions
• Set and keep your repository private. Respect the wishes of the creators of the UC-Pacman: “Please
do not distribute or post solutions to any of the projects.”
– Go to your forked project gitlab page and click on Poject’s Settings → General → Expand permis- sions tab → Change ”Visibility Level” to Private.
• Give write permissions to all the other students who are part of team. Follow these instructions. Add each member as a mantainer role.
• Give mantainer permission to me (Nir) by registering my username: nlipovetzky.
• Set up a Wiki in the repo: Wiki page should list team name, team member names and student numbers,
and can have information for each project. See a template here.
• Do not alter the directory structure of the forked repository.
Note: The team is expected to develop their solution incrementally in this repository and apply good Software Engineering practices and group working by regularly updating this repository (for example, a submission containing the final solution in just a few commits is not good practice). The repository will be used as a way to gauge any anomalies in the effort put in the semester for any student. This could lead to fairly different marks within the same team if deemed necessary.
2. Register the group team for this project by filling this form:
https://forms.gle/KacSUFnukeCJvFrV7
Once your team is registered, the team is ready to work and will be able to submit its solutions!
Deliverables
A final submission, by the official deadline, for this project should consist of:
(1) A working Pacman agent that is capable of competing in the tournament in Python by suitably modify-
ing file myTeam.py as per instructions in the UC Berkeley Contest page. The code should be internally commented at high standards and be error-free and never crash.
In your solution, You have to use at least 2 of the techniques (3 techniques at least for groups of 4) that have been discussed in COMP90054. Feel free to combine them in any form. The candidate techniques are:
(a) Heuristic Search Algorithms (using general or pacman specific heuristic functions) (b) Classsical Planning (PDDL and calling a classical planner, see subsection below) (c) Policy iteration or Value Iteration (Model-Based MDP)
(d) Monte Carlo Tree Search or UCT (Model-Free MDP)
(e) Reinforcement Learning – classical, approximate or deep Q-learning (Model-Free MDP) (f) Goal Recognition techniques (to infer intentions of opponents)
(g) Game Theoretic Methods
(2) A group.txt plain text file listing your group members’ student number, full name, and email, one per line.
(3) A Wiki in your repository, including the link to your youtube presentation at the top of the Wiki. Make your
youtoube video unlisted if you don’t want it to be searchable. The Wiki should explain and analyse critically
COMP90054 AI Planning for Autonomy 2 S2 2019- September 15, 2019
your Pacman agent system. Besides explaining the technique used, the wiki can include, but is not limited to, experiments to show how different variations of your agent perform against each other, assumptions that you made, analysis of the strengths and weaknesses of your solution, techniques tried but not used in the final version, etc. The techniques implemented that did not make it to the final submission should have their associated commit tag so we can explore and run the code. Otherwise we cannot mark techniques that we cannot see the code.
The above files must all be placed in folder pacman-contest/ of your repo and with the exact name and capitalization as described above. Please check submission details below.
Submission Instructions
To submit you must follow the next two steps:
1. Submit your solution by simply tagging “submission-contest” the commit you want to submit:
• See this guide for tagging using the command line or this video, and here for tagging via GitLab interface directly.
• To re-submit another version you need to delete previous submission tags
– First delete it from the GIT server by running: git push −−delete origin
For the marking process, we will automatically extract files myTeam.py, group.txt in the folder
pacman-contest/ of your repository. You can still import other files if needed; see item 5 below.
2. Each student must certify the submission and contribution details by filling the following form once
you finish the project (16-oct), no later than 20-oct:
Contest – Certification of Submission
Each member of the team must certify in order to get a mark for the assignment project. Lack of certifica- tion will attract zero marks for the whole assignment project (for the corresponding student).
While the project can be done as a team, we reserve the right to assess members of a team individually.
Important: When submitting a solution, please make absolutely sure you adhere to the following instructions:
1. Your code must run on Linux and adhere to Python 3.6. Staff will not debug or fix any code.
2. At the very minimum, your code should be error-free. If your code crashes in any execution, it will disqual-
ified from the contest. Again, staff will not debug or fix code that crashes.
3. The deliverables must be placed in folder pacman-contest/ of your repo (i.e., not in other folders).
4. You are not to change or affect the standard output or error (sys.stdout and sys.sterr) in any
way. These are used to report each game output and errors, and they should not be altered as you will be intefering negatively with the contest and with the other team’s printouts. If your file mentions any of them it will be disqualified automatically.
5. Your code will be copied into a directory called teams/
import sys sys.path.append(’teams/
6. Your code will be run by the following command:
python3 capture.py –delay 0.0 -r teams/
COMP90054 AI Planning for Autonomy 3 S2 2019- September 15, 2019
7. We’ve added some useful options 1) –delay to slow down the execution if you want to visualize in slow motion, 2) –record or –replay. Use –help to check all the options.
8. Do *NOT* use the current working directory to write temporary files; instead, redirect all output to your own folder ./teams/
9. If you want to use any other 3rd-party executable please discuss with us before submission. You can as- sume that TensorFlow, keras, sklearn, numpy, scipy and neat-python libraries are installed in our running environment, using the latest version available in Ubuntu 18.04. ff executable ver- sion 2.1 of the Metric-FF planner (https://fai.cs.uni-saarland.de/hoffmann/metric-ff. html) is available in /usr/local/bin.
10. Finally, submit your project substantially before the deadline, preferably one day before. Submitting close to the deadline could be risky and you may fail to submit on time, for example due to lose of Internet connection or server delays. There will be no extensions based on these unforeseen problems.1
Submissions not compatible with the instructions above will attract zero marks and do not warrant a re- submission. Staff will not debug/fix your submission.
General Comments (optional read) 1. Implementation of Pac Man Agents
You can always use hand coded decision trees to express behaviour specific to Pac-Man, but they won’t count as a required technique. You are allowed to express domain knowledge, but remember that we are interested in Autonomy, and hence using techniques that generalise well. The 7 techniques mentioned in the Deliverables section can cope with different rules much easier than any decision tree (if-else rules).
If you decide to compute a policy, you can save it into a file and load it at the beginning of the game, as you have 15 seconds before every game to perform any pre-computation.
While a classical planning approach is perhaps the simplest way to get a working agent (quick prototype), it is unlikely to do well in the tournament play if not combined with other techniques. That is, you should think about each possible situation that may arise during the game, and use the best technique you know. You do not need to use classical planning for each situation, actually you don’t need to use it at all. Just use at least 2 (3 if groups of 4) different techniques from the list in Deliverables Section.
2. Pac Man as Classical Planning with PDDL
Typical applications of planning consist on one or several calls to a planner. The instances are generated on the fly by a front–end (the pacman engine), and the solutions (plans) are interpreted as executable instructions. As the pacman is not a classical single agent problem, you could implement two points of view: The point of view of the pacman, where its goal is to stay alive while eating all the dots of the grid, and The point of view of the ghost, whose goal is to kill pacman. Assume that the game is turn-based, so at each step an instance is generated with the current state of the world, i.e. the dots and ghosts locations in the grid. From the point of view of pacman, the ghosts don’t move, and vice-versa, that is, the environment is static.
At each step the planner would come out with a plan to eat all the dots while avoiding static ghosts, and plans to enable ghosts to kill the static pacman. A simple interpretation of the plans by the pacman engine is to execute only the first action of the plan, ignore the remaining actions, and call the planner in the next step with a new updated instance accounting for the new locations of the ghosts and the pacman.
1Extensions will only be permitted in exceptional circumstances. Note that workload and/or heavy load of assignments will not be accepted as exceptional circumstances for an extension.
COMP90054 AI Planning for Autonomy 4 S2 2019- September 15, 2019
The axiomatisation should define the state model for pacman using PDDL, and another PDDL for a ghost state model. If you try this approach, explain clearly the assumptions made, e.g. pacman do not move to cell X when Y holds, Ghosts are static, etc., and describe several initial states or goals to illustrate interesting situations.
Use one PDDL domain file for pacman, and one domain file for the ghost containing the predicates and the actions of the world. The problem file describes the ‘initial’ state and goals. Therefore, with a single domain for either the pacman or the ghost, several problems can be generated by only updating the problem file.
By reading the state of the Pacman from the engine and converting this into PDDL predicates, you can describe the state of the game in PDDL and, at each step that an action is required, call your favourite planner using that state as the initial state. Then, parse the solution in order to choose the best action.
Different domains can be used to encode different strategies.
Make sure that your PDDL files can be solved using the online solver in http://editor.planning. domains.
Preliminary Contest Submission
We will be running informal tournaments based on preliminary submissions in the weeks before the final project submission. We will start once five teams have submitted their preliminary agents (by tagging their repos). We will group teams randomly in 4 different leagues. Given that we expect ≈200 teams, you will be playing against ≈50 teams.
Participating in these pre-contests will give you a lot of insights on how your solution is performing (by downloading and re-playing each game) and how to improve it. Results, including replays for every game, will be available only for those teams that have submitted in https://people.eng.unimelb.edu.au/ nlipovetzky/comp90054tournament/.
The pre-competitions will run every night at 0:10AM using your latest tagged version. In order to increase the amount of feedback, we will be running your team against the staff teams every 2hours, from 8AM untill 10PM.
You can re-submit multiple times, as long as your repository has a submission tag, and they carry no mark- ing at all; they are just for debugging and improving your solution! You do not need to certify the preliminary submissions, only the final one (you do need to register your team though).
Marking criteria
A final contest using many layouts will be run juts after final submission. The top-8 will play quarterfinals, semi- finals and finals, time permitting live in the last day of class or in week 13 in a day specified for that (these final phases will not be part of the marking criteria, just bonus marks).
The final contest and the quality of the Wiki and Presentation will be used to derive the final marks for the project.
Part (i) Pacman Agent– 24 marks
Marks will be given according to final position in the tournament with respect to staffTeam:
• Pacman competitor finishes above the staffTeamBasic agent [9 marks].
• Pacman competitor finishes above the staffTeamMedium agent [6 marks].
• Pacman competitor finishes above the staffTeamTop agent [6 marks].
• Pacman competitor finishes above the staffTeamSuper agent [3 marks].
• Final competition place (up to 2 bonus marks).
– Winner team of each league in the preliminary competition will receive 1 bonus mark.
– Winner of the Final Tournament will receive 1 bonus mark.
The precise mark will depend how far your agent system is from these reference agents in the final contest.
COMP90054 AI Planning for Autonomy 5 S2 2019- September 15, 2019
Part (ii) Video– 10 marks
• A clear presentation of the design decisions made, challenges experienced, and possible improvements [3 marks]
• A clear demonstration and understanding of the subject material [2 marks]
• Demo of the different agents implemented across a variety of scenarios, showcasing pitfalls and benefits of
each approach. No need of full game demo, just edit interesting parts and explain your insights [5 marks]
Part (iii) Wiki– 6 marks
• A clear written description of the design decisions made, approaches taken, challenges experienced, and possible improvements [3 marks]
• Anexperimentalsectionthatjustifiesandexplainstheperformanceoftheapproachesimplemented,including a table and discussion [3 marks]
The staffTeams are the reference baselines: the farther an agent is from the base reference agents (Basic, Medium, and Top), the more marks it will attract. The only exception is staffTeamSuper, any team that finishes above it, will earn full marks (24 points). This together with the quality of the Wiki and the presentation will determine the final mark, then adjusted as per individual contribution2 . So this means that if an agent system is between staffTeamMedium and staffTeamTop and has a VERY GOOD (all marks earned) Wiki and Presentation, then it will score between 77.5% and 92.5% overall (the closer to staffTeamTop, the closer to 92.5%).
Inter-University Competition
The top teams of the tournament will qualify to the yearly championship accross RMIT and The University of Melbourne, which will run each semester along with the best teams since 2017 onward (given you grant us permis- sion). Note that the top-8, i.e. 1st and 2nd of each of the 4 leagues, will play quarterfinals, semifinals and finals, time permitting live in the last day of class. This is just “for fun” and will attract no marks, but is something that previous students have stated in their CVs!
https://sites.google.com/view/pacman-capture-hall-fame/
Academic Misconduct
The University misconduct policy3 applies. Students are encouraged to discuss the assignment topic, but all sub- mitted work must represent the individual’s understanding of the topic.
The subject staff take academic misconduct very seriously. In this subject in the past, we have successfully prosecuted several students that have breached the university policy. Often this results in receiving 0 marks for the assessment, and in some cases, has resulted in failure of the subject.
2We will use the team code repository as a way to gauge any anomalies in the effort put in throughout semester for any student. This could lead to fairly different marks within the same team if deemed necessary. Plagiarism detection software will also be used.
3See https://academichonesty.unimelb.edu.au/policy.html
COMP90054 AI Planning for Autonomy 6 S2 2019- September 15, 2019
I hope you enjoy this open-ended contest-based project and learn much from it. If you still have doubts about the project and/or this specification do not hesitate asking in the Course Forum. GOOD LUCK!