Search - Assignment 2

CSCI 446
Artificial Intelligence
Fall 2018

Schedule | Assignments | Course Syllabus | Course Project Information | Moodle

ASSIGNMENT 2: Search

The goal of this assignment is to write a generic tree search algorithm and then provide different strategies to the algorithm to modify the type of search.

You will apply your search algorithm and strategies to a map traversal problem and report the results of each in terms of how many nodes were expanded and the length (in terms of cost) of the solution found by each algorithm. Your program will take in a description of the environment as its percepts. Internally it must create a tree of the environment states and then use this tree to find a solution. The output of your program will be its solution, the cost of the solution, and the number of nodes expanded in order to reach that solution.

The Problem
You are provided two text files. The first one, Roads.txt, lists pairs of Montana cities with roads between them and the driving distance. Note that even though each city pair is only listed once, the road betwwen them is a bi-directional link, e.g. you can drive from Butte to Helena or from Helena to Butte. The second file, SLD.txt, is the straight line distance between each of the cities and the goal city, Whitefish. The start city is Jordan. Your job is to figure out a route from the start state to the goal state.

Part 1: Design (and Code) the Input Module
You must decide how you will read in the map data and organize it to eventually represent this as a tree.

Part 2: Design (and Code) the Generic Tree Search Module
The generic tree search module should follow the generic algorithm in your text and also in the slides. This way you can simply manipulate your handling of the fringe/frontier in order to control search order (and implement a particular search strategy). You should be careful not to allow cycles in your tree.

Part 3: Design (and Code) the Strategy Modules
Implement two of the search strategies we talked about. One must be uninformed, such as depth first, breadth first, etc. The second must implement A* and use the straight line distance heuristic function. As your search proceeds, you should keep track of how many nodes were expanded. You also need to report the total cost of the path your algorithm chose.

Part 4: Design (and Code) the Output Module
The output should report:
0. The algorithm used.
1. The path that takes you through all the nodes.
2. The cost of that path.
3. The total number of nodes expanded while searching.

Note: If you'd like, you can write a driver program that uses both search methods in succession.

Submission. Submit your search program, with all files required to make it run, via Moodle. Please submit source files, not executables. I want to look at the source and compile and run it myself. Be sure each submitted source file has the required header comment with your name, and a description of the class/program. It's up to you what programming language and environment you use, but please write up instructions on how to compile and run your program so that I am able to test it.

Page last updated: August 17, 2018