Introduction to AI


Project 2: informed search

Summary

This project will take 6-10 hours to complete (you should be familiar with the code base from the previous assignment and you can build on your previous code, potentially making it shorter).  Note, as with the last project, graduate students have additional requirements.

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

  • Create an agent that moves around the board in a near-optimal manner using A* 
  • Implement A* search in a real-world environment
  • Become familiar with implementing agents in an existing codebase
  • Compete on the class-wide competition ladder

Class-wide ladders – Extra credit

The extra credit ladders remain the same as with Project 1.  You are welcome to choose a different ladder path than you chose for project 1.  

The class-wide ladders will start on Sep 15, 2021.

heuristic agents

The heuristic agents remain the same as with Project 1.

A* search

This project builds on the last project but focuses on A* search.  For this project, all of the obstacles will move around the environment, making it more challenging than the last project.  You should build on your chosen approach to search from Project 1 (gridded, hierarchical, roadmap) or you can build a new approach (if you didn’t like how your last search turned out). 

Unlike the last project, where the environment was mostly static, this environment is dynamic.  You will need to adapt your re-planning approach to handle the new dynamics of moving obstacles.  This is inherently a tricky problem and the most straightforward way to deal with the dynamics is to replan frequently. For this project, you should keep in mind that replanning at every time step will be too slow to be feasible. Instead, your agent should replan dynamically with >= 10 simulations steps in between plans. The best solution is to replan dynamically when something in the world has changed that affects your existing plan. When the agent is not planning, it should execute its plan from the previous planning period. You may choose other approaches to replanning but you can NOT replan at each step.

In addition to breaking the world into discrete pieces, you will need to implement an admissible and consistent heuristic for A* search to work.  Hint: don’t forget that the world is a torus in this simulator (and look for built-in functions that could help you)! Your heuristic should make use of world dynamics and your chosen mechanism to discretize the environment.

As with Project 1, 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 A* search at the heart of it!  Also keep in mind that A* 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 A* to navigate efficiently.

 

extra credit

The extra credit opportunities for being creative and finding bugs remain the same as in Project 1.

How to download and turn in your project

  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 and we will only grade the last submission.
    • Submit ONLY your writeup to the correct Project 2 on canvas: Project 2 for CS 4013 or Project 2 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 project2_coop \
--java_files *.java
/home/spacewar/bin/submit --config_file spacesettlersinit.xml \
--project project2_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 project2_coop_late \
--java_files *.java
/home/spacewar/bin/submit --config_file spacesettlersinit.xml \
--project project2_compete_late \
--java_files *.java

Rubric

  • A*
    • 30 points for correctly implementing A*. A correct player will move to the target beacons efficiently. 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.
    • 25 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).
    • 20 points if there are several minor mistakes or if your code is missing a lot of documentation.
    • 15 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.
    • 8 if there are several major mistakes or if you implement a search other than A* 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.
  • CS 4013/5013: A Star graphics
    • 10 points for correctly drawing graphics that enable you to debug your A* 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 optimal path found by A* that your ship will traverse.
    • 7 points for drawing something useful for debugging and grading but with bugs in it
    • 3 points for major graphical bugs
  • Admissible and consistent heuristic
    • 8 points for designing, correctly implementing, and documenting an admissible and consistent heuristic.
    • 6 points for one minor mistake. An example would be correctly designing an admissible heuristic but failing to implement it in an admissible way or making a minor coding error or failing to document your heuristic.
    • 4 points for several minor mistakes or one major mistake. An example of a major mistake would be designing a heuristic that is not admissible (but correctly implementing it)
  • Replanning
    • 7 points for dynamically replanning as needed in an efficient manner. This CANNOT be replanning every time step.
    • 3 points if you replan when you achieve your target only
    • 0 points if you never replan
  • CS 5013 students only: comparison to uninformed search methods: Using your solution to Project 1, you will need to collect data about your informed and uninformed search methods.  Collect at least 20 examples from your ships using your chosen alternative method and another 20 from your ships using your A* implementation. An example is the full set of actions from when you choose to go to a goal and when you reach (or fail to reach) the goal. So 20 attempts to collect an asteroid or 20 attempts to hunt a ship, etc. Put a graph in your writeup comparing the two implementations in terms of how they accomplish the goal of navigation.
    • 20 points for a fully implemented and correct second search method from BFS, DFS, hill climbing or GBFS.
    • 15 points for implementing the search but it is lacking documentation or has minor errors or the graph is missing in the writeup
    • 10 points for implementing the search correctly but failing to test it and discuss it in the writeup
    • 5 points for major errors or no documentation and testing
  • Good coding practices: We will randomly choose from one of the following good coding practices to grade for these 12 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:
    • 12 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: CS5013 students have additional requirements of documenting their other search method, described above. 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.
    • 8 points: Describe what form of A* you implemented, and how you dealt with the dynamics of the environment
    • 3 points: Describe your heuristic and why it is admissible and consistent
    • 2 points: Why did you choose the cooperative or competitive path? A sentence or two is sufficient here.
    • 5013 only (points above but the description goes here): Include a graph of your alternative search method compared to \astar{} and explain how and why they differ.