CSE 471/598 – Introduction to Artificial intelligence

CSE 471/598 – Introduction to Artificial intelligence
Project I - Requirement Specifications

Problem Solving Agent for Traveling Salesman Problem

Deadline: March 8, 2004

The project specification may have few minor modifications. So, please keep looking on this page and myASU for the changes.

Please note: The highest standards of academic integrity are expected of all students. The failure of any student to meet these standards may result in suspension or expulsion from the university and other sanctions as specified in the academic integrity policies of the individual colleges. Violations of academic integrity include, but are no limited to, cheating, fabrication, tampering, plagiarism, or facilitating such activities. If you are not sure of something or in doubt then please contact the TA or the professor.

In this project you will solve the Traveling Salesman Problem using various search algorithms and a heuristic.

Traveling Salesman Problem (TSP)

The TSP problem is defined as follows: Given a set of cities and distances between every pair of cities, find the shortest way of visiting all the cities exactly once and returning to the starting city.

You can imagine the cities as nodes in a graph and distances as edge cost between the cities. Now the problem is transformed to finding the shortest tour of the graph. This is a well known NP-Complete problem and generally different heuristics are used to solve this problem. You are suppose to write a LISP program containing a function named "tsp" which should take three parameters, the input file as the first parameter, the name of the start city as the second parameter, and the name of the search method as the third parameter. The function then should return two values the first is the list of the shortest tour, and the second is the cost of the tour..

The format for the input file and the output values is given below. The search methods which your program should support are:

Depth First Search (function argument- DFS)
Breadth First Search (function argument- BFS)
Uniform Cost Search (function argument- UCS)
Minimum Spanning Tree heuristic (function argument- MST)

You may consider maintaining a list of visited cities and a list of unvisited cities to facilitate computations. In the 4^th part the heuristic function should be

h(n): estimated distance to travel all the unvisited cities (MST heuristic used here) + nearest distance from an unvisited city to the start city. Note that this is an admissible heuristic function.

Minimum Spanning Tree (MST)

A spanning tree of a graph is a sub-graph that contains all the vertices of the graph and is a tree. A graph may have many spanning trees; and the minimum spanning tree is the one with the minimum sum of the edge costs of the tree.

There are many algorithms developed for finding the minimum spanning tree of a graph. You can use any of the algorithms for this purpose. One of the algorithms that find the minimum spanning tree is described below.

NP :The min. spanning tree built should have the current node of the graph.

Algorithm for MST

It is a greedy approach to find the MST of a graph G.

 sort the edges of G in increasing order of cost

keep a subgraph S of G, initially empty

for each edge e in sorted order 

  if the endpoints of e are disconnected in S (i.e., does not form
a cycle)

     add e to S

return S

The above approach is called Kruskal’s algorithm which executes in O(|E|log|E|) complexity, where |E| is the number if edges in the graph.

The search algorithm should find the MST of the unvisited cities and use the cost of the minimum spanning tree in computing h(n) shown above. The cost of a spanning tree is the sum of the edge costs of the tree.

Spaces(multiple are possible) are used to separate the name of the cities and the cost matrix given is complete.

Input File Format

City₁ City₂ City₃ … City_N

d₁₁ d₁₂ d₁₃ … d_1N

d₂₁ d₂₂ d₂₃ … d_2N

…………………….

…………….

d_N1 d_N2 …….. d_NN

where City₁ … City_N name of N cities

d_ij – distance between City_i and City_j.

Note that d_ij may not be equal to d_ji and all the distances are integers. A value of 0 between two cities indicates that there is no path connecting them. The function "tsp" will be called by an automated script in the following format:

(tsp “c:\\test.tsp” ‘City₁ ‘DFS)

And the values returned should be:

(City₁ City₃ ….. City_N) 1000

Notice that the start city is not repeated in the returned tour.

Project Submission Guidelines

You need to submit the soft copy of the project via myASU Assignments section.

You should submit "one" LISP file named {last name}-{first-name}.lisp
Submit the file through Assignment section in myASU.
Please make sure that the file is in simple text format and not in document (Microsoft Word or some other document) format.
The first line in the file should be your name. Please comment it.
If you want to label portions of your code as solution to part one, part two, etc., or you want to write the problem statement in the lisp file(it is not needed, you can do it if you feel it is convenient for you), please make sure that they are all commented.
There should be no syntax errors in the program(like forgotten closing brackets, misplaced semicolon unmatched double quotes, etc.,)
Please try to comment whatever code you have written for debugging purpose. The function execution calls like (tsp “C:\\input.txt” 'Bavaria 'DFS) should all be commented.
Make sure your program executes in Allegro lisp (ideally it should execute in clisp too).
Don't use #t it is something from Scheme and not part of Ansi Lisp. Allegro Lisp supports it but clisp doesn't.
Please don't change the package name or create functions in different package.
Please follow the lisp style guide available at http://www.lisp.org/table/style.htm

Also, you are supposed to turn in a hardcopy report either in class or at the CSE department main office. The report should be brief and contain a discussion on any one aspect of the project of your interest. It could be anything like why the MST heuristic is admissible, other admissible heuristics for the problem, advantage/disadvantage of using A* as the search algorithm, any other better search strategy for the problem. It should also contain the difficulties you encountered, interesting observations, etc.

Grading

The distribution of grades for the project is :

Code – 80%

Project Report – 20%