For this assignment, you will use heuristic and genetic searches to solve the scheduling problem in the radar simulation from the previous assignment. You will implement the following two algorithms within the simulation:

A. Solve the radar scheduling problem using A* Search

1. Determine an admissible heuristic for A* that can be used with this problem. You can use a non-admissible heuristic if you cannot find an admissible heuristic.
2. Implement A* using the heuristic defined above.
3. Compare A* with DFS in terms of utility and time taken to complete the search.
4. Understand how A* and DFS behave as the number of tasks and radars increase.

B. Solve the radar scheduling problem using Genetic Algorithm

1. Generate random schedules.
2. Determine a fitness value for those schedules
3. Pick pairs of those schedules to generate additional schedules
4. Mutate some schedules to generate more new schedules
5. How does the utility of the best solution of your Genetic Algorithm improve over time?
6. What is the effect of increasing the number of tasks and radars on the Genetic Algorithm?
7. What is the terminiating condition for your Genetic Algorithm??

Please see Homework 1 for a description of the radar simulation and instructions on how to download and get it running.

Assignment Evaluation

When the assignment is due, send the TA via email, a zipped (or tarred) file containing the following files for each of A* and Genetic Algorithm :

1. RadarMetAgent.java
2. MCCAgent.java
3. Any other java file you might have created. Please note you are not to modify any of the preexisting java files, unless you have the TA's permission to do so.
4. A writeup

Your writeup for A* should address the following questions:

1. What would an example search tree look like for the radar scheduling problem? You don't have to be too detailed here. A paragraph with a couple of diagrams (1-2 nodes per diagram) should suffice.
2. What heuristic function did you use for A*? Is your heuristic function admissible? If not, why is your heuristic function not admissible? Why do you think an admissible heuristic does not exist?
3. How does A* compare to DFS in terms of the utility of the final schedule generated and the time taken in finding the final solution? Moreover, what effect does scale have on both the algorithms?

Your writeup for the Genetic Algorithm should contain the following:

1. Plot a Decision Quality v/s Time curve for your Genetic Algorithm.
2. Answer each of the key questions outlined in Slide 8 of Lecture 8. What is your fitness function? How is an individual represented? How are individuals selected? How do individuals reproduce?
3. How does the plots you generated for Genetic Algorithm compare with your A* algorithm? Would you pick Genetic Algorithm over A* algorithm for the scheduling problem?

Final Word

Good luck with this assignment. Please start early and let the TA know if you face any problems.