Project 1: Uninformed Search

Summary Video

Summary at a glance

• Create a general uninformed search that moves your agent from its current location to a goal location that you specify, avoiding obstacles along the way
• Create an agent that makes use of the search method to intelligently move around and maximize score in your chosen ladder (see below)

Uninformed search in SpaceSettlers

The main focus of this project is to create an agent that moves around the environment intelligently using uninformed search (BFS or DFS).  As with Project 0, 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 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.
• 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.

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 – More about the API

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 to make a graph in SpaceSettlers

This is a video from last year but it still works to explain how to do graphs in SpaceSettlers!

Project 1: Part 1  Due 11:59PM Sep 8, 2023

• 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 and you may cross between online/hybrid.  If you have a mixture of 4000/5000, the 5000 student will need to complete the extra work for their level and the 4000 level student will receive a grade only for the 4000 level part of the project.
• 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 11:59PM Sep 15, 2023

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. 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:

2. /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

3.  

Rubric

We will be using un-grading principles this year where you are choosing how much you want to do based on a known rubric. 

A few quick notes:

• 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 resubmitted.
• All projects MUST show graphics on the screen to be graded.  Any project with no graphics will also be returned without grading and will need to be resubmitted.

Rubric

• Graphics
  • 15 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.
  • 10 points for drawing something useful for debugging and grading but with bugs in it
  • 5 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
  • 5 points for dynamically replanning as needed in an efficient manner. This CANNOT be replanning every time step.
  • 2 points if you replan when you achieve your target only
  • 0 points if you never replan
• Choosing your targets
  • 5 points for choosing effective targets to go to.  This includes beacons, stars, asteroids, bases, etc.  The targets should be chosen to achieve the goals of your team, as specified in the writeup.  They should not just be a copy of one of the example agents.
  • 2 points for random targets that are not copied from the example agents
  • 0 points if you just copy an example agents choices
• 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.
    • 7 points: Describe how you implemented search (gridded, roadmap, etc) and how you dealt with the dynamics of the environment
    • 4 points: Describe how you selected your targets (e.g. why you choose a beacon versus an asteroid and when you make each choice).  This should be short, essentially describing your logic of why you chose the targets and how they accomplish the goals you wanted to achieve for your agent.
    • 4 points: Why did you choose the cooperative or competitive path? A sentence or two is sufficient here.