ASSIGNMENT 1: Navigation Problem

Ever wonder how the navigation app in your mobile phone works? Well, in this
assignment , you have a chance to create your very own navigation program. Your
task here is to develop a program that will accept as inputs:
• An environment map, represented as a graph. The graph is a weighted
directed graph, where a vertex represents a location of interest. Throughout
this assignment specification, we will use vertex and the state it represents
interchangeably. A directed edge vv’ with label c means that there is a direct
road to move from v to v’, and the cost of moving through the road is c.
• An initial and goal locations.
The program should output the shortest path to move from the initial to the goal
locations.
To develop the navigation program, please:
1. Define the navigation agent.2
2. Please use Uniform Cost and A* search algorithms to solve the problem faced
by the navigation agent.
Input format
The input is two .txt files: One file contains the environment map, while another
file contains the queries.
The environment map is represented as a graph. This graph is written in a matrix
format: The matrix’ size is nXn, where n is the number of vertices in the graph.
Element [i, j] (row-i, col-j) of the matrix is the cost of moving from vertex-i to
vertex-j. The cost of an edge is always a real number greater than 0.01. An element,
say [i, j], with value 0 means there is no edge from vertex-i to vertex-j.
The file that contains this graph consists of n+1 lines. The first line contains only
a single number: n. Each of the next n lines correspond to each row in the matrix,
with line-k in the file corresponding to row-(k-1) in the matrix. The rows are
separated by a single white space.
The queries file contains q+1 lines, where q is the number of queries. The first
line contains only a single number: q. The rest of the files are the queries.
Each query is written in a single line, and consists of three components separated
by a single white space. The first component is the type of algorithm to use. In this
assignment, there will only be 2 types of algorithms: Uniform for Uniform Cost
search and A* for A* search. The second component is the ID of the initial vertex,
while the third component is the ID of the goal vertex.
Output format
The output file contains q lines, where q is the number of queries in the input file.
Each solution (the shortest path) is written in a single line. The solution at line q
must be the solution of the query at line q+1 in the input file. Each path should be
written as a sequence of vertices separated by a dash (“-“) sign. This sequence
starts with the initial vertex and ends with the goal vertex.
Grading for the Programming Part (total points: 60/100)
For marking, we will use 4 different pairs of environment and queries files. Each
queries file will contain 4 queries. Therefore, there will be a total of 16 queries.
COMP3702 students can get a full mark by solving 12 of the 16 queries. However,
COMP7702 students must solve all queries to get a full mark. Solving a query
means finding the optimal path within the given time limit. The time limit may be
different for different pairs of environment-queries files. The details of the grading
scheme is as follows:
COMP3702:
• = 1 & < 10: The program does not compile nor run.
• = 10 & < 20: The program runs but fails to solve any query. The program
fails to solve a query when it does not find a solution (i.e., a path with the
least cost from the initial to the goal vertices) after more than 2X the given
time limit.
• = 20 & < 30: The program solves at least one of the queries within 1-2X the
given time limit.3
• =30 & <= 60: The program solves at least one of the queries within the given
time limit. Each query is worth 2.5 points.
COMP7702:
• = 1 & < 5: The program does not compile nor run.
• = 5 & < 10: The program runs but fails to solve any query. A program fails
to solve a query when it does not find a solution after more than 2X the given
time limit.
• = 10 & < 20: The program solves at least one of the queries within 1-2X the
given time limit.
• =20 & <= 60: The program solves at least one of the queries within the given
time limit. Each query is worth 2.5 points.
Report (total points: 40/100)
Your report must contain answers to the following questions:
1. [2.5 points] What is the formal definition of the navigation agent in this
assignment?
2. [2.5 points] What type of agent is the navigation agent as described in
question-1 (i.e., discrete / continuous, fully / partially observable,
deterministic / non-deterimistic, static / dynamic)? Please explain your
selection.
3. [7.5 points] What is the heuristic you use for A* search? Please explain why
do you think it is a good heuristic?
4. [12.5 points] Please compare the performance (in terms of time and space)
of Uniform Cost and A* search as the number of vertices in the graph
increases. Please explain your findings. This explanation should include
comparisons with the theoretical results.
5. [15 points] Suppose you are given 2 environment maps, say A and B. True
or False that if the number of vertices in A is larger than in B, then given
the same implementation of A* search, finding an optimal path in A will
always take longer time than in B? Please explain your answer.
Please note that in each of the above question, when explanation is requested, the
explanation part is 80% of the total points. For instance, in question 5, correct
True or False answer will only give you 3 points, while a good explanation about
your true or false answer could earn you up to 12 points.
Please also note that good explanation is NOT equal to long explanation!!!