Introduction to AI

Project 1: Uninformed search

Executive Summary

This project will take 6-10 hours to complete (this includes time getting familiar with the existing codebase, which is important for your long-term learning as you will be using existing code bases in whatever your future job is!).  Note that graduate students will need to implement two searches. 

By the end of this project, you will have accomplished the following objectives.

  • If you want to work with a partner, you will have formed a team
  • Create an agent that moves around the board intelligently using uninformed search
  • Implement uninformed search in a real-world environment
  • Become familiar with implementing agents in an existing codebase
  • Compete on the class-wide competition ladder

Summary Video

Uninformed search

The main focus of this project is to create an agent that moves around the environment intelligently using uninformed search (BFS or DFS).  To make this first project simpler, you will be searching in a continuous environment but all the obstacles will be static (e.g. not moving) and your only other moving items will be the other ships. You will still need to handle the continuous nature of the state space and we suggest one of the following approaches.

  • Gridded search: Break the environment up into n grid squares (where you determine the grid spacing). Create a graph based on these grid squares where adjacent grid squares are connected unless one of them contains an obstacle or a ship. Implement search to traverse the graph and find a path from the starting state to the goal beacon.
  • Hierarchical gridded search: The idea behind this approach is similar to the gridded search except that the grid spacing is not fixed. Instead, the agent searches at a very coarse granularity (large grid squares) and finds a path in this easier space. The agent then refines its path by making finer grid squares along the previous path. This process is refined until the agent has a reasonable path from the start state to the goal state.
  • Roadmap search: This approach is based on roadmap navigation. Instead of making grid squares of your entire environment, sample n points from the space and draw a straight line between each set of points. If the line connecting the two points does NOT intersect an obstacle or ship, connect the two points in your search graph. Implement your chosen search method and search on this graph. 

Again, since this is project 1, we will make the re-planning process simpler and simply ask that you re-create your plan anytime your target moves (e.g. you or someone else has gotten to your chosen asteroid or beacon).

If you are still stuck on how to implement your search method in this environment, consider jumping ahead to Topic 1 in Module 3 where we discuss how to adapt search to more real-world conditions.

Note that this project leaves a LOT of room for creativity. The success at making your agent move around the world effectively will pay off in all of your future projects. You can be creative in how you draw your graph and how you navigate the graph efficiently so long as you are doing uninformed search at the heart of it!  Note the next project will use informed search methods!

Also keep in mind that your search should be written in a modular fashion so you can use it for many high-level actions. For example, “navigate to beacon” and “navigate to base” should be able to both call your search to navigate efficiently.

heuristic agents

For this project, you are provided opponents using the following heuristics. Both versions of the ladder include a subset of these heuristics.

  • Random makes completely random moves. This generally results in random going through the space at high velocity and shooting. Random does not usually live very long nor does it collect many beacons or any asteroids except by accident.
  • DoNothing simply sits and does nothing. If it gets hit by an obstacle, it moves around with the velocity imparted on it by the obstacle. Surprisingly, this is a good strategy for surviving although it clearly won’t get collect many beacons or asteroids!
  • BeaconCollector is a naive beacon collecting agent (it just aims straight for them). It does well at collecting beacons but it dies a lot and it never shoots any weapons or makes any purchases.
  • PassiveHeuristicAsteroidCollector is the agent that the cooperative ladder needs to outperform. This agent collects the highest valued asteroid until it reaches a certain amount of resources. Then it takes the resources back to base. It goes for energy beacons when it runs low on energy. It never shoots. It buys additional bases when it has enough resources.
  • AggressiveHeuristicAsteroidCollector has two ships: one that does the same job as PassiveHeuristicAsteroidCollector and one that hunts down ships and shoots at them. Be wary of this team! They will not participate in any cooperative ladders.
  • AggressiveHeuristicAsteroidCollectorSingleton has one ships but does pretty much the same job as the team based version (the one ship just chooses between shooting enemies and collecting resources). Be wary of this team! They will not participate in any cooperative ladders.

Class wide ladders – includes extra credit

This game has two paths to victory and you must choose when you submit your agent to the extra-credit ladders and for grading. You must choose one of the two ladders for turning in your assignment, even if you do not participate in the extra credit ladder.

  1. Cooperative ladder: You can choose the cooperative path where you work only with known heuristic-based ships but not against other students. All students who beat the heuristic client PassiveHeuristicAsteroidCollector (see below) will receive extra credit. This option will give you one point of extra credit per day that you beat the heuristic. This ladder will rank students by resources obtained (listed as Resources in the configuration file).
  2. Competitive ladder: You can also choose the higher-risk but higher-payoff approach of competing against the other students.  In this ladder, the top scoring student will receive three points of extra credit per night that they remain on top. The second scoring student will receive two points of extra credit per night.  The third scoring student will receive one point of extra credit.  Students must also beat the AggressiveHeuristicAsteroidCollectorSingleton agent to receive extra credit but each game will be played with both heuristics and other students in the game.  For project 1, this ladder will rank teams by the number of Kills inflicted by their team minus the number of deaths suffered by their team plus the number of AI cores collected (listed as KillsMinusDeathsPlusCores in the configuration file).

To keep grades fair, the maximum extra credit possible through the ladder is eight points. 

The class-wide ladders for Project 1 will start on Sep 7, 2022.

Additional Extra-credit opportunities

To keep grades within a fair range, all grades will be capped at 110 points. This means that no project can receive a grade higher than 110, no matter if they win the ladder, find great exploits, and are very creative.

Bugs or exploits in Space Settlers

We are reasonably certain that you cannot exploit the simulator (say by directly affecting your opponents energy or by directly moving yourself to the goal location). However, any project has bugs and we want to know about them! If you find a bug or an exploit, you can receive extra credit according to the following scale:

  • 5 points: If you find an exploit and report it to us, you can receive 5 points extra credit upon verification of the report. Note, we know of several exploits for the previous version of the simulator that still exist here for which you cannot get extra credit as it is already discovered.
  • 10 points: If you find an exploit and give us a fix for it, you can receive 10 points extra credit upon verification of both the exploit and the fix.
  • 1 or 2 points: General simulator bugs are much more likely than exploits. Finding a bug and reporting it can get you 1 point. Fixing the bug and giving us the fix (you can’t check it in directly but you can give it to us in the bug report) can get you two points. Both bug and fix must be verified for any extra credit to be awarded.

Creativity 

Creativity is highly encouraged! To make this real, there are up to 10 points of extra-credit available for creative solutions. Some ideas here include real-time planning where you plan in the background while executing your current best plan (see the discussion of real-time planning in the book) or other forms of search that deal with continuous and dynamic environments. If you choose to implement anything that you consider creative, please do the following:

  • Document it in your writeup! I can’t give extra credit unless I know you did something extra.
  • Your navigation search must still have BFS/DFS at the heart of it. If you are unsure if your search qualifies, come talk to me.

Remember that by being creative I am referring to the algorithm and not to the ability to creatively download code. All project code must be written exclusively by your group except for the sample players that we provide.

 

Implementation details

All of your source code must reside in your src/4×4 directory and be in your 4×4 package. You may name your files within this package anything that makes sense to you (remember that we are grading on coding style as well). Your configuration file MUST be named spacesettlersinit.xml.

You are limited to 1 ship per team for this project. We will relax this assumption in later projects.

The client class contains the following useful methods.

  • getMovementStart() is called each time an agent is about to begin an action and it must return a valid action for the agent to execute
  • getMovementEnd() is called after all agents have ended their actions but before the simulator goes to the next timestep. This may be left empty if you have no need for cleaning up after an action
  • getPowerups() is called each time step to find out what powerups the agent may want to use (this is separate from movements)
  • getTeamPurchases() is also called each time step to find out what the team wants to purchase (if anything)
  • initialize() is called when an agent is created (but not when it comes back to life from being killed)
  • shutdown() is called at the end of the simulation and can be used to cleanup (e.g. close file handles, etc) for an agent
  • getGraphics() is called each step and can be used to draw on the screen (particularly useful for debugging!). See the HumanTeamClient for an example of using graphics inside an agent. getKeyAdapter() and getMouseAdapter() are called at the start of the simulation and be used to add a UI to your agent (useful for debugging but not useful in the ladders).

Using methods from within any of the spacesettlers code and within anything in the standard Java SDK is acceptable (and encouraged as there are some nice built-in tree classes, including DefaultMutableTreeNode) but downloading or using code from any other sources is not allowed. See the syllabus for more details on what is considered academic misconduct. As discussed below, any additional files you create should be turned in along with your main Client code.

 

How do I make a graph in spacesettlers?

Project 1: Part 1 Due Sep 6, 2022

  • You are allowed and encouraged to work in pairs for the projects.  These pairs will be considered your team for the entire semester.  If something happens later (such as one student dropping the course), we can adjust as needed but we will not be switching pairs randomly through the semester.
  • You may work in groups across 4000/5000 levels.  If this is the case, the 5000 student will need to complete the extra work for their level.
  • ALL students (regardless of if they intend to work in pairs or not) must turn in to this canvas assignment the name of their team (see the rules from Project 0) and the two 4x4s working as a team.  If you do not intend to work as a team, simply turn in your 4×4 and your team name.

Project 1: Part 2 Due Sep 16, 2022

Make sure you watch the grading video (below in the rubric section!) so you know what to turn in!

How to turn in your project

Remember, we had a video in project 0 on how to turn in your code.  Refer to that if you need help!

    1. 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.
    2. Change the SpaceSettlersConfig.xml file in spacesettlers/config/heuristicCooperative or heuristicCompetitive 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.
    3. Write your search code as described above
    4. 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.
    5. Submit your project on spacesettlers.cs.ou.edu using the submit script as described below.  You can submit as many times as you want to the ladder.  We will only initiate grading/feedback when you submit your writeup to the canvas project.
      • Submit ONLY your writeup to the correct Project 1 on canvas: Project 1 for CS 4013 or Project 1 for CS 5013.  If your group has someone in each category, then submit one writeup to each (this makes the grading using rubrics on canvas much easier!).
      • 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 project1_coop \
--java_files *.java
    /home/spacewar/bin/submit --config_file spacesettlersinit.xml \
--project project1_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 project1_coop_late \
--java_files *.java
    /home/spacewar/bin/submit --config_file spacesettlersinit.xml \
--project project1_compete_late \
--java_files *.java

Grading & rubric

We will be using un-grading principles this year where you are choosing how much you want to do and you also get a chance to turn the project in multiple times before the deadline for feedback.  Please watch the video to learn more!  Quick summary below:

  • All projects must compile and run to be graded.  Any project which does not compile or run will be returned without grading and should be re-submitted.
  • All projects MUST show graphics on the screen to be graded.  Any project which does not show the graphics of the search nodes and the search will be returned without being graded and should be re-submitted.

Rubric

  • Graphics
    • 20 points for correctly drawing graphics that enable you to debug your search and that help us to grade it. This means you should display your graph either all at once (if you initialize it that way) or step-by-step as it is built. You should also show the path found by BFS/DFS that your ship will traverse.
    • 15 points for drawing something useful for debugging and grading but with bugs in it
    • 10 points for major graphical bugs
    • Projects will not be graded without graphics – resubmit if you do not have graphics working!
  • BFS/DFS
    • Note:  CS4013 students need only to implement ONE of BFS or DFS.  CS 5013 students will need to implement a second uninformed search method from BFS, DFS, IDFS, or other uninformed search method from the book.  The rubric will score 20 points per search method for graduate students and 40 for undergraduates.
    • 40 points for correctly implementing search (single method for 4013, two methods for 5013). A correct player will move to the target beacons as efficiently as possible . The ship will rarely run into obstacles, other ships, or bullets. Full credit requires FULL code documentation explaining what each function does. The top of each java file should also contain a 2-3 sentence description of everything that java file does.
    • 35 points if there is only one minor mistake. An example of a minor mistake would be having off-by one errors (where you miss a search node). You can also lose 5 points for not documenting your code well (but at least somewhat).
    • 30 points if there are several minor mistakes or if your code is missing a lot of documentation.
    • 20 points if you have one major mistake. An example of a major mistake would be failing to mark a grid square as occupied (which causes you to run into obstacles, ships, or bullets) or failing to correctly connect your graph.
    • 15 if there are several major mistakes or if you implement a search other than BFS/DFS that at least moves the agent around the environment in an intelligent manner.
    • 5 points for an agent that at least does something other than random movements.
  • Replanning
    • 10 points for dynamically replanning as needed in an efficient manner. This CANNOT be replanning every time step.
    • 5 points if you replan when you achieve your target only
    • 0 points if you never replan
  • Good coding practices
    • We will randomly choose from one of the following good coding practices to grade for these 15 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:
      • 15 points for well commented code, descriptive variables names or making good use of classes and methods
      • 8 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
    • 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.
      • 10 points: Describe how you implemented search (gridded, roadmap, etc) and how you dealt with the dynamics of the environment
      • 5 points: Why did you choose the cooperative or competitive path? A sentence or two is sufficient here.

 

AI course home

Project Module home