Introduction to AI
Project 4: Multi-agent systems
Extra Video on how to do planning in spacesettlers
Capture the flag (CTF)
This project focuses on multi-agent systems in a new environment for SpaceSettlers: Capture the Flag (CTF). The rules of the environment are the same as before, with mineable and non-mineable asteroids but a new object has been added: a Flag. A field of non-moveable and non-mineable asteroids has been setup to represent flag alcoves and barriers between the two sides. Each team has a single Flag that starts randomly inside one of the two alcoves for that team. The initial field setup is shown below. The non-mineable asteroids are the same at the start of every game. The small non-mineable asteroids (creating the barrier and alcoves) will remain stationary for the duration of the game. The larger non-mineable asteroids (around the perimeter) will move slowly, adding to the navigational challenges. The mineable and gameable ones continue to be randomly generated and to move around the environment.
CTF specific rules
The rules for the flag are:
- If a ship touches its own flag, it will move to a new random location inside a randomly chosen alcove for that team (could be the same one or could switch, it is chosen randomly).
- If a ship touches the other team’s flag, that ship picks up the flag. This is indicated in the graphics with a little white flag icon inside your ship.
- To count the flag for your team, the ship carrying the flag must bring it back to one of your bases. Once the flag carrier touches the base, your flag will count.
- If a ship dies while carrying the flag, the flag drops where the ship died. It acquires the ship’s velocity at the time of death, so it can move around.
There are two scoring mechanisms for Capture the Flag, one for the cooperative approach and one for the competitive approach. In both cases, teams will need to acquire flags. Resources will help teams to obtain flags by enabling teams to buy additional ships, bases, and powerups.
- Cooperative: The score is the total flags collected by both teams in the game MINUS the total kills from both teams (e.g you are penalized for killing people because this is against the goals of the cooperative ladder). This means that your final game score depends on working with the heuristic (and not actively interfering with it).
- Competitive: The score is the total Flags collected by your team, meaning you are directly competing against the other team for total number of flags.
There are two new heuristic agents for this project.
These are both extensions of the Passive or Aggressive Asteroid Collector client. The difference is that both focus on collecting flags as well as asteroids and (in the aggressive case) trying to shoot down enemies. Neither of them does any multi-agent coordination or planning since they are intended to be baseline teams for you to work with or to compete against.
The extra credit opportunities for being creative and finding bugs remain the same as in Project 1. Remember you have to document it in your writeup to get the extra credit!
How to Implement and then turn in your project
- Update your code from the last project. You can update your code at the command line with “git pull”. If you did not get the code checked out for project 0, follow the instructions to check out the code in Project 0.
- Note: the directories for config files changes for this project! As do the targets you will want to run in build! Change the SpaceSettlersConfig.xml file in spacesettlers/config/captureTheFlagCompetitive or captureTheFlagCooperative to point to your agent in src/4×4. The detailed instructions for this are in project 0. Make sure to copy over a spacesettlersinit.xml in the src/4×4 directory so your agent knows how to start. In spacesettlersinit.xml change the line <ladderName>Random Client</ ladderName> to the team name you chose in Canvas.
- Write your planning code as described above
- Build and test your code using the ant compilation system within eclipse or using ant on the command line if you are not using eclipse (we highly recommend eclipse or another IDE!). Make sure you use the spacesettlers.graphics system to draw your graph on the screen as well as the path your ship chose using your search method. You can write your own graphics as well but the provided classes should enable you to draw the graph quickly.
- Submit your project on spacesettlers.cs.ou.edu using the submit script as described below. You can submit as many times as you want and we will only grade the last submission.
- Submit ONLY the writeup to the correct Project 4 on canvas: Project 4 for CS 4013 and Project 4 for CS 5013
- Copy your code from your laptop to spacesettlers.cs.ou.edu using the account that was created for you for this class (your username is your 4×4 and the password that you chose in project 0). You can copy using scp or winscp or pscp.
- ssh into spacesettlers.cs.ou.edu
- Make sure your working directory contains all the files you want to turn in. All files should live in the package 4×4. Note: The spacesettlersinit.xml file is required to run your client!
- Submit your file using one of the following commands (be sure your java files come last). You can submit to only ONE ladder. If you submit to both, small green monsters will track you down and deal with you appropriately.
/home/spacewar/bin/submit --config_file spacesettlersinit.xml \ --project project4_coop \ --java_files *.java
/home/spacewar/bin/submit --config_file spacesettlersinit.xml \ --project project4_compete \ --java_files *.java
- After the project deadline, the above command will not accept submissions. If you want to turn in your project late, use:
/home/spacewar/bin/submit --config_file spacesettlersinit.xml \ --project project4_coop_late \ --java_files *.java
/home/spacewar/bin/submit --config_file spacesettlersinit.xml \ --project project4_compete_late \ --java_files *.java
Remember, as with the previous projects, some form of graphics is required for grading. This could, for example, including showing a target for what each ship is aiming for (e.g. this one aiming for the flag, this one for another ship, etc) or something else creative. In this case, while printouts could augment it, graphics should be used for debugging!
- 10 points for correctly drawing graphics that enable you to debug your planning and coordination and that help us to grade it.
- 7 points for drawing something useful for debugging and grading but with bugs in it
- 3 points for major graphical/printing bugs
20 points for correctly implementing planning within your group’s set of agents. A correct planner will choose among the actions intelligently using PDDL-style planning. Planning code should be well documented to receive full credit.
18 points if there is only one minor mistake. An example of a minor mistake would be not re-planning at the correct time or incorrectly specifying the pre or post-conditions for an action.
15 points if there are several minor mistakes or if documentation is missing.
10 points if you have one major mistake. An example of a major mistake would be not using an pre or post conditions or incorrectly applying them to your state representation.
5 points if you accidentally implement a search algorithm other than planning that at least moves the teams around the environment in an intelligent manner.
- Multi-agent coordination
20 points for correctly implementing multi-agent coordination within your group’s set of agents to achieve a common goal. A correct multi-agent systems will coordinate team behavior intelligently and rarely have issues running into each other and is well documented.
18 points if there is only one minor mistake. An example of a minor mistake would be not always coordinating well in a decentralized team or sometimes (rarely!) assigning incorrect roles in a centralized system. Note that errors in planning should count above rather than here. This focuses on the multi-agent coordination itself.
15 points if there are several minor mistakes or if it is not well documented.
10 points if you have one major mistake. An example of a major mistake would be not frequently failing to coordinate actions.
5 points for several major mistakes.
- High-level behaviors
10 points for making good use of your knowledge from AI so far to create good high-level behaviors with properly documented (in the writeup and the code) action schemas
8 points for one minor mistake.
5 points for several minor mistakes or one major mistake.
3 points for implementing a behavior that is at least somewhat intelligent, even if it doesn’t fulfill the requirements of the high-level behavior specified by your team.
- Knowledge integration
- 5 points for making good use of your knowledge from AI so far. For example, creative and good knowledge representations or integrating your search methods from earlier would count here. This is a good spot for creativity!
- CS 5013 students only: You must use both multi-agent coordination and other advanced planning mechanisms (such as duration, resources, etc) in your action schemas and implementation
- 10 points for correct use of advanced planning mechanisms
- 5 points for bugs
- Good coding practices: We will randomly choose from one of the following good coding practices to grade for these 10 points. Note that this will be included on every project. Are your files well commented? Are your variable names descriptive (or are they all i, j, and k)? Do you make good use of classes and methods or is the entire project in one big flat file? This will be graded as follows:
- 10 points for well commented code, descriptive variables names or making good use of classes and methods
- 5 points if you have partially commented code, semi-descriptive variable names, or partial use of classes and methods
- 0 points if you have no comments in your code, variables are obscurely named, or all your code is in a single flat method
- Writeup: 15 points total. Your writeup is limited to 2 pages maximum. Any writeup over 2 pages will be automatically given a 0. Turn your writeup in to canvas and your code into spacesettlers.
3 points: A full description of the high-level behaviors you chose
5 points: A full description of the planning approach you chose. This includes a full description of the goal condition, the state representation, and the schemas pre-conditions and effects for each action.
4 points: A description of how you implemented multi-agent coordination
3 points: A description of how you integrated your knowledge from other parts of the course into your existing agent.