### COSC-570: Artificial Intelligence

Project 1
Fall 2022

Due: F 9/16 @ 5 PM ET
9 points

For this project, we're going to France. Formidable! It will be Uh-MAZE-ing. You will implement state-space search routines for finding paths in mazes and weighted graphs.

For this and subsequent projects, you must implement your program using Java 11. Your code must be well-structured and well-organized and follow object-oriented design principles.

For this and subsequent projects, you must implement your program using only the standard libraries the language provides. If you want to use external libraries or something non-standard, check with me first.

You can use any platform for development, but for this and subsequent projects, the source must compile on the command line using the following command within the directory containing your source:

$javac *.java  This is the command that Autolab will use to build your project. Do not use packages. I put some starter code on “cs-class” (i.e., class-1.cs.georgetown.edu). To get started, log on to cs-class and copy over the following zip file: cs-class-1% cd cs-class-1% cp ~maloofm/cosc570/p1.zip ./ cs-class-1% unzip p1.zip  In the p1 directory, you will find a Makefile and class definitions for Action, State, Problem, and MarksMain. The use of the Makefile is optional. I provided it for your convenience. Your implementation must work for any state-space search problem, so you will need to derive classes for finding paths in France and in mazes from Action, State, and Problem. The code in Main should help you understand these classes and the other classes and methods you will need to implement. Do not change the names of the classes or methods that I have specified in this assignment. Additionally, I will evaluate your implementation on a search problems that you have not encountered before. Implement 1. uniform-cost search as the method Solution Search.ucs(Problem), 2. greedy best-first search as the method Solution Search.gbfs(Problem), and 3. A* as the method Solution Search.astar(Problem). Note that you can also implement these methods by using the best-first search algorithm and providing different objects for f. Derive a class from Problem and encode the following weighted graph: Use the following latitudes and longitudes for the cities to write a function that returns the estimated distance between two cities. Paris, 48:51:00N 2:20:00E Caen, 49:15:00N 0:20:00W Calais, 50:57:36N 1:57:00E Dijon, 47:21:00N 5:02:00E Lyon, 45:44:00N 4:52:00E Grenoble, 45:21:36N 5:19:12E Avignon, 43:50:00N 4:45:00E Marseille, 43:18:00N 5:25:00E Nice, 43:42:00N 7:21:00E Montpellier, 43:38:00N 3:53:00E Toulouse, 43:37:00N 1:27:00E Bordeaux, 44:50:00N 0:37:00W Limoges, 45:30:00N 1:10:00E Rennes, 48:07:00N 1:02:00W Brest, 48:24:00N 4:30:00W Strasbourg, 48:32:24N 7:37:34E Nancy, 48:50:00N 6:10:00E Nantes, 47:15:00N 1:30:00W  The file france.txt should help you save a few keystrokes, especially if you know how to program. There is also a copy of this file in p1.zip. • In addition to computing a solution and its cost for the initial and goal cities, each search method should also compute: 1. the number of nodes explored, entered, or visited 2. the number of nodes expanded (i.e., the total number of successors) 3. the number of nodes maintained (i.e., stored in the frontier) The Main.main that you submit should use each of the three search methods to find a path between the following initial and goal cities:  Run Initial State Goal State 1 Brest Marseille 2 Montpellier Calais 3 Strasbourg Bordeaux 4 Paris Grenoble 5 Grenoble Paris 6 Brest Grenoble 7 Grenoble Brest For each algorithm and then for each pair, your Main.main should print to the console the cost of the solution, the actions, and the counts. • For each search method over the seven city pairs, compute the following: 1. the average number of nodes explored or entered 2. the average number of nodes expanded (i.e., the total number of successors) 3. the average number of nodes maintained (i.e., stored in the frontier) 4. the number of times it found the optimal solution Place these averages in a file named README. Write a paragraph that compares and contrasts the search algorithms in terms of these statistics. What differences or similarities do you see between the informed search algorithm and the optimal search algorithms? What differences or similarities do you see between the two optimal search algorithms. Include this file with your submission. Of course, when you are in Paris, it is important to be able to navigate the catacombs. For this task, implement the class Maze and the constructor Maze(String filename) that reads a maze from the specified file with the following format: %%%%%%% % S% % %%% % % % % %% %% %G %%%% %%%%%%%  Percent signs (%) represent walls, ‘S’ designates the starting or initial state, and ‘G’ designates the goal state. Note that S and G are optional parameters. The constructor should set the initial and goal states based on S and G if they are present in the file. There are four maze files in the zip file that I provided. Regardless, the application programmer should be able to set initial and goal states by calling Problem.setInitialState or Problem.setGoalState and providing the appropriate state. To facilitate this, implement the MazeState class and the constructor MazeState(int x, int y) that sets the x-coordinate and the y-coordinate, respectively, of the state. #### Hints for Development I am certainly interested in how you decide to structure your implementation. For mine, in addition to the classes discussed previously, I derived France from Problem, FrenchAction from Action, and FrenchCity from State. I implemented the class LatLong to store the latitude and longitude of each city. You should have similar implementations for finding paths in mazes. #### Instructions for Electronic Submission In a file named HONOR, provide the following information: Name NetID In accordance with the class policies and Georgetown's Honor Code, I certify that, with the exceptions of the course materials and those items noted below, I have neither given nor received any assistance on this project.  When you are ready to submit your project, create the zip file for uploading by typing: $ zip submit.zip Main.java (other java files) Makefile README HONOR

You can also type:
\$ make submit


Upload submit.zip to Autolab. You can submit to the compile check p1c five times. You can submit your assignment p1 two times. Make sure you remove all debugging output before submitting.