HW#1 --- last modified January 23 2023 19:18:14.

Solution set.

Due date: Sep 16

Files to be submitted:
  Hw1.zip

Purpose: To gain experience with problem solving agents and the `A^\star` algorithm

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO1 -- Find solution nodes in a state space using the A* algorithm.

Specification:

For this homework, you will write a program hilary_norgay.py that reads in from a file a terrain map drawn using characters graphics that contains squares of various elevations, and which contains one square that has an explorer on it and one square which is a summit. Your program will output a sequence of terrains maps `M_0`, `M_1`, ..., `M_n`, such that `M_0` is the terrain map read from the file, for `0 < i <= n`, `M_i` differs from `M_{i+1}` in that the explorer's position changes by one square distance, horizontally, vertically, or diagonally, and such that in map `M_n` the explorer is on the summit. The explorer is not allowed to go off the left, right, top, or bottom of a map. When the explorer switches from one square to a different one, we also require the difference in elevation between the squares to be at most 1. Below is a glossary indicating the meaning of squares in our terrain maps:

0,1,2,3,4 - used to indicate the square has the explorer and the explorer is at elevation 0, 1, 2, 3, or 4.
~ - indicates water (terrain of elevation 0)
. - indicates a beach (terrain of elevation 1)
: - indicates lowlands (terrain of elevation 2)
M - indicates mountains (terrain of elevation 3)
S - indicates the summit (terrain of elevation 4)

A terrain map consists of a sequence of lines (lines can be of different lengths) using characters from the glossary above and terminated by newline characters such that the whole map only has at most one explorer character and at most one square that is either S or 4. When output by your program a terrain map should be proceeded by a line with a string "<newline>Map_some_number<newline>" indicating which map in the sequence it is. The goal state is a terrain map with a 4 (explorer at the summit), but otherwise matching what was read from the file.

Your program will be run from the command line using a syntax like:

python hilary_norgay.py some_file_name some_heuristic

For example,

python hilary_norgay.py water_world.txt 0

The value for heuristic will always be 0, 1, or 2. You can assume python above is a recent installation of Python 3, however, don't assume that the grader is going to use pip to install any additional packages (you might lose points if your program doesn't work out of the box on a vanilla python install). In the example, if water_world.txt contained the following lines:

SM:.~
~~~~~~~~~
~~~~~~~~~
:::~~~
1..~~~

A possible sequence of maps output by your program would be:

M_0
SM:.~
~~~~~~~~~
~~~~~~~~~
:::~~~
1..~~~

M_1
SM:.~
~~~~~~~~~
~~~~~~~~~
:::~~~
.1.~~~

M_2
SM:.~
~~~~~~~~~
~~~~~~~~~
:::~~~
..1~~~

M_3
SM:.~
~~~~~~~~~
~~~~~~~~~
:::0~~
...~~~

M_4
SM:.~
~~~~~~~~~
~~~0~~~~~
:::~~~
...~~~


M_5
SM:.~
~~~0~~~~~
~~~~~~~~~
:::~~~
...~~~

M_6
SM:1~
~~~~~~~~~
~~~~~~~~~
:::~~~
...~~~

M_7
SM2.~
~~~~~~~~~
~~~~~~~~~
:::~~~
...~~~

M_8
S3:.~
~~~~~~~~~
~~~~~~~~~
:::~~~
...~~~

M_9
4M:.~
~~~~~~~~~
~~~~~~~~~
:::~~~
...~~~

The grader won't test your program on bogus input files. To find a solution sequence of terrain maps your program should use the `A^\star` algorithm. This implementation should be flexible enough so that you can swap out heuristic functions for the distance remaining easily. When 0 is used from the command line I want you to use as a heuristic the Euclidean distance `sqrt((Delta X)^2 + (Delta Y)^2 + (Delta Z)^2)` from the explorer to the summit. For the two other heuristic (corresponding to values 1 and 2), I want you to make up something reasonable. For the last point of the homework, I want you to design, conduct, and write-up some experiments on how these different heuristics perform on different maps. This write up should include a brief description of the two new heuristics you came up with. Include this write-up in a file Hw1.pdf that you include with your homework ZIP. Be advised that the homework upload function only accepts files up to 10MB, so check your file sizes before submitting, and reduce any images etc in your write-ups to make it fix within this limit. If you don't have any images in your write-up it should be easy to meet this limit.

Point Breakdown