Submission Instructions

Submit your code on eClass as a zip file (the entire “starter” folder) and the answers to the questions of the assignment as a pdf.  The pdf must be submitted as a separate file so we can more easily visualize it on eClass for marking.

Overview

In this assignment you will implement Dijkstra’s algorithm and Bidirectional Search  (Bi-BS) for solving pathfinding problems on video game maps.  We will consider a grid environment where each action in the four cardinal directions (north, south, east, and west) has the cost of 1.0 and each action in one of the four diagonal directions has the cost of 1.5. Each search problem is defined by a video game map, a start location and a goal location.  The assignment package available on eClass includes a large number of maps from movingai.com, but you will use a single map in our experiments; feel free to explore other maps if you like.

Most of the code you need is already implemented in the assignment package. In the next section, we detail some of the key functions you will use from the starter code. You can reimplement all these functions if you prefer, their use isn’t mandatory. The assignment must be implemented in Python, however.

Heap Tutorial (0 Marks)

Run the file heap_tutorial .ipynb on Jupyter Notebook (see instructions on how to install Jupyter Notebook here:  https://jupyter .org/install).  The Notebook file is a tutorial about Python’s heapq library, as you will need it to implement the OPEN lists in the assignment. Note that we assume a minimum knowledge of Python to complete the assignment. For example, we assume that you are familiar with dictionaries and lists in Python.  If you aren’t familiar with the language and its basic structures, please seek help during office hours and labs. You will need to be familiar with Python for the other course assignments as well. If you aren’t familiar with the language, you should see this course as a good learning opportunity.

Starter Code (0 Marks)

The starter code comes with a class implementing the map and another implementing the nodes in the tree. We also provide the code for running the experiments (see main.py for details about the experiments).

State Implementation

The State class  (see algorithms.py) implements the nodes in the search tree.   It contains the following information:  x and y coordinates of the state in the map and the g-value of the node.  We also include the width (W) of the map.  This is because we use the map width to compute the following hash function for a state with coordinates x and y:  y × W + x  (see method state_hash of State).  This is a perfect hash function, i.e., each state is mapped to a single hash value.  We will leave it as an exercise for you to understand this hash function. Note that you can use the function without understanding it.

The “less than” operator for State is already implemented to account for the g-values of the nodes. Please see the heap tutorial to understand why the “less than” operator needs to be implemented.

Map Implementation

Most of the functions in the map implementation are called internally or in main.py, so you will not have to worry about them.  In main.py we create an instance of the map used in the experiments as follows: gridded_map  =  Map(“dao-map/brc000d .map”) .  This instance must be passed to your search algorithms, so they can access the transition function of the state space defined by the map.

The  most  important  method you will  need to  use  from  map.py  is  successors.   This  method  receives a  state  s  as  input  and  returns  a  set  of states,  the  children  of  s.   The  children  of s  are  returned  al- ready with their correct g-values (see State Implementation above for details).  For example,  children  = gridded_map .successor(start) generates all children of start and stores them in a list called children. One can then iterate through the children as one does with any list in Python: for  child  in  children.

The Map class also offers a method called plot_map for plotting the map and the states in CLOSED after completing a search.  This method can be helpful to visualize the search and possibly help you find bugs. For example, the image below shows the map and states in both CLOSED lists of Bi-BS. The white areas are traversable regions while black areas represent walls.  The gray areas represent the states expanded in search.  If you zoom in you will be able to see a pixel with a lighter color in the middle of the two circles;

one represents the start state and the other the goal state. Here is an example of use of this function.

map .plot_map(CLOSED,  start,  goal,  ’name_file’)

In this example, map is the map object, CLOSED is the union of Bi-BS’s CLOSED lists (or Dijkstra’s algorithm CLOSED list), and name_file is the name of the file in which the image will be saved.

Bringing Map and State Together

We consider 30 test instances from the file testinstances .txt for the brc000d map.  The test instances (start and goal states) are read in the main file. All you need to do is to pass the start and goal states as well as the map instance to your search algorithms (see the lines starting with “Implement here...”  in main.py for where you need to insert the calls to your implementation of Dijkstra’s algorithm and Bi-BS).

Here is a code excerpt that assumes the existence of a state called start and a map called map (see the Map Implementation above) and it creates a dictionary whose keys are given by the hash function.

CLOSED  =  {}

CLOSED[start .state_hash()]  =  start

children  =  gridded_map .successors(start)

for  child  in  children:

hash_value  =  child .state_hash()

if  hash_value  not  in  CLOSED:

CLOSED[hash_value]  =  child

How to Run Starter Code

Follow the steps below to run the starter code (instructions are for Mac and Linux).

。Install Python 3.

。It is usually a good idea to create a virtual environment to install the libraries needed for the assignment.

The virtual environment step is optional.

– virtualenv  -p  python3  venv

–  source  venv/bin/activate

– When you are done working with the virtual environment you can deactivate it by typing deactivate. 。Run pip  install  -r  requirements .txt to install the libraries specified in requirements.txt.

You are now ready to run the starter code by typing: python3 main .py  –-testinstances . Copy and paste might not work properly because –-testinstances could be pasted as –testinstances.

If everything goes as expected, you should see several messages as shown below.  These messages are the result of running a set of test cases.  Naturally, if you haven’t implemented the search algorithms, then all test cases will return with a “mismatch.”  You will not see any of these mismatch messages once you have correctly implemented what is being asked.

There  is  a mismatch  in  the  solution  cost  found  by  Dijkstra

and  what  was  expected  for  the  problem:

Start  state:    [108,  26]

Goal  state:    [105,  67]

Solution  cost  encountered:    None

Solution  cost  expected:    42 .5

There  is  a mismatch  in  the  solution  cost  found  by  Bi-BS

and  what  was  expected  for  the  problem:

Start  state:    [108,  26]

Goal  state:    [105,  67]

Solution  cost  encountered:    None

Solution  cost  expected:    42 .5

Implement Dijkstra’s Algorithm (4 Marks)

Implement Dijkstra’s algorithm and call your implementation in the line marked with the comment “Imple- ment here the call to your Dijkstra’s implementation...”  in main.py.  The implementation must be correct, i.e., it must find an optimal solution for the search problems.  The algorithm must return the solution cost and the number of nodes it expands to find a solution. If the problem has no solution, it must return -1 for the cost.  There is no need to recover the optimal path the algorithm encounters, but only report the cost and number of expansions.