ECS170 – Climbing Mt St Helens Instructions
Your assignment is to create an implementation of the AIModule interface that computes a path
from the start location to the end location while minimizing the total search space. Once you’ve
written this function, you can run your program through command line arguments, those being:
– w (int) – width of the map (default 500)
– 1 (int) – length of the map (default 500)
– seed (int) – seed to set for random terrain generation (default None, set by random module)
– filename (string) – filename for npy file to load for map
– cost (string) – cost function. Values [‘exp’, ‘div’] accepted. Default ‘exp’
– AI (string) – Name of AIModule to use. Values [‘AStarExp’, ‘AStarDiv’, ‘AStartMSH’
‘Dijkstra’] accepted. Default ‘exp’.
The program can be executed using the above command-line instructions. For example, running
the following command:
>> python Main.py -seed 0 -cost exp -AI Djikstra
Will create a random terrain map of size 500×500 using the division cost function (see below)
and use the Dijkstra Al. While the terrain map is random, you can get the exact same terrain map
whenever you use the seed O. Note that length and width are not set and their default values are
To help test your implementation, we’ve provided a working Dijkstra’s algorithm Al class called
DijkstraAl. As you’ve learned in class, Dijkstra’s algorithm always yields the optimal path, so
you can compare your own Al against the DijkstraAl module to see if your path is indeed
optimal. Note that when we run your program for grading purposes, we will be using a fresh
copy of the provided starter code. Please do not modify the starter code. Otherwise, you may be
under the impression that your code is working properly but it will not work properly on our
Submission Instructions
Please submit the following:
AIModule_
Assignment1
As individual files. Please do not include any starter code or any other files, and replace
Introduction & Assignment
You are lost but fortunately, you have an A* framework that you can use to find your way home.
In this assignment, you will devise an algorithm for plotting a course home, minimizing the total
cost of the path and the amount of time spent searching.
In this assignment, you’ll first work with the Map class, a class encapsulating a two-dimensional
world layered on top of a rectangular grid. Each point in the world has a height, represented by
an integer value between O and 255. You can move to any of the eight squares adjacent to your
own location (e.g. the four cardinal directions and the diagonals). As you would expect, the cost
to traverse between tiles is dependent on the differences in height between the tiles. Below are
different const functions for you to experiment with.
The Map class also keeps track of which tiles your algorithm visits as it looks for an optimal path
home. Part of your grade on this assignment will be determined by how many tiles your
algorithm visited. For example, if two different algorithms each yield the optimal path, but one
accomplishes this task and only considers 10% of the number of squares as the other, the
algorithm that visited fewer squares would be considered superior to the other. Interestingly,
many of the better search algorithms that visit fewer squares also run in considerably less time,
so you’ll have a dual incentive to keep your search space small. Please note that this is still
secondary to finding the shortest path.
Libraries and Requirements
This assignment requires you to use Python 3.. You can download the current version of Python here.
The assignment has been tested on Python 3.8 and Python 3.10, but I believe it should work on any
version of Python 3. Assignments will be graded on Python 3.10, so I recommend writing and testing in
this version, however, if there are any issues exclusive to a particular version of Python 3 that you are
using, you will not be penalized so long as you can demonstrate that the error is due to the Python 3
version alone.
The only external library you will need to run this assignment is numpy, a common Python library used
for matrix operations. You will not need to know how this library works, but it will run in the
background.
No other external libraries are allowed. If, for some reason, you believe another library would be
helpful and not make the assignment trivial (ie importing an A* implementation), you can reach out to
TA Michael Livanos for confirmation.
Coding Instructions
“Ouestion 1 (12pts): Designing Admissible Heuristics
For each cost function above for the chess movement (all eight neighbors), do the following:
a) Create an admissible heuristic, document the exact form of the heuristic and prove/show it is
admissable. (6 points per cost function)
“Question 2 (3pts): Implementing A* Algorithms
(Note: Upon reflection, Q2 has been reduced from 6 points to 3)
a) You will now implement your own version of A*. Look at the StupidAl class to get an idea of
how to search the state space. (2 points)
b) To implement the heuristic, write valid python code in a separate function (1/2 point for each):
Question 3 (10 pts): Testing Your Implementations
Try out your heuristic functions with the appropriate cost function on 500×500 maps with
random seeds 1, 2, 3, 4 and 5.
Use the following command to run this part of the assignment: “python Main.py -cost c -AI a
-seed x” with c being either “exp’ or ‘div’ and a being the appropriate AI module, and x being the
seeds listed above.
Submission Requirements: For each execution record the cost of the shortest path and the
number of nodes expanded as per the output of the program.
1 points per cost function for getting the shortest path. Non-optimal paths will get
(shortest path cost) / (your path cost)
For all students who get the shortest path: we will rank your performance and you shall receive
bonus marks of:
5* (Number of Qualified Students + 1 – Your Rank) / (Number of Qualified Students) for each
cost function.
Please include your output in your submission PDF.
Question 4 (8pts): Climbing Mt St Helens
(Note: Upon reflection, Q4 has been increased from 5 points to 8)
This is a much larger grid and hence you will have to more cleverly implement your algorithm.
Modify your A* algorithm and admissible heuristic so as to find the optimal path in this new
environment in the least possible time. Please describe the changes you made to your A*
implementation in your submission PDE. Note that in order to receive credit for this question,
you must provide some non-trivial changes to the code that result in it running faster. Examples
of non-trivial changes include:
Implementation of an A* variant such as:
Using multiple admissible heuristics
Bidirectional A*
Weighted A* – be very careful with this. Weighting A* by too much can ruin the
admissibility of the heuristic. You will have to show not only that you get a time
improvement using weighted A*, but also that you have not violated
admissibility.
Iterative deepening – note that this does not always make A* faster, but it can in
cases of memory constraints
More examples of A* variants can be found here
Making a nontrivial (ie more than just a line or two) change to the heuristic to make it run
faster, perhaps at the cost of nodes expanded.
If in doubt of whether or not your changes will be considered non-trivial, please reach out the TA
Michael Livanos.
You only need to consider the chess style movement (all 8 neighbors) and the exponential cost
function. You can use any valid technique to improve the performance of the algorithm.
Use the following command to run this part of the assignment: “python Main.py -AI AStarMSH
-filename msh.npy”.