COSC-574: Artificial Intelligence

Project 1
Fall 2019

Due: F 9/20 F 9/27 @ 5 P.M.
10 points

For this project, we're going to France. Formidable! You will implement state-space search routines for finding paths in a weighted graph.

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

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.

For this and subsequent projects, you must also provide a Makefile that produces the required executable and class files. The Makefile must include a clean target that removes the class files so the autograder can produce the executable from the source code. Note that compiling and running your program on cs-class (cs-class.uis.georgetown.edu) will be the best guarantee that it will compile and run on Autolab.

I put some starter code on cs-class. To get started, log on to cs-class and copy over the following zip file: 

cs-class% cd
cs-class% cp ~maloofm/cosc574/p1.zip ./
cs-class% unzip p1.zip
In the p1 directory, you will find a Makefile and class definitions for Action, State, Problem, and Main.

Your implementation must work for any state-space search problem, so you will need to derive classes for finding paths in France 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. I will evaluate your implementation on a search problem that you have not seen 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).
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 pair, your Main.main should print 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 average 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.

    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 LatLong to store the latitude and longitude of each city. I also implemented Frontier to store and order partial solutions, and we will discuss the implementation of the frontier in class.

    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 your assignment p1 two times. Make sure you remove all debugging output before submitting.

    Plan B

    If Autolab is down, upload your zip file to Canvas.

    Copyright © 2019 Mark Maloof. All Rights Reserved. This material may not be published, broadcast, rewritten, or redistributed.