School of Computer Science The University of Adelaide

Artificial Intelligence Assignment 3

Semester 1 2023

Due 11:59pm Wednesday 7 June 2023

1 Robot localisation (UG and PG)

Robot localization is the process of determining where a mobile robot is located con- cerning its environment. Robot localization provides an answer to the question: Where is the robot now? A reliable solution to the localization is one of the most fundamental competencies required by an autonomous robot as the knowledge of the robot’s own location is an essential precursor to making decisions about future actions.

In a typical robot localization scenario, a map of the environment is available and the robot is equipped with sensors that observe the environment as well as monitor its own motion. The localization problem then becomes one of estimating the robot’s position within the map using information gathered from these sensors. The following shows an example of a 2D map drawn using ASCII characters:

0000X0000X XX00X0XX0X X000X0XX00 00X000X000

The character ‘X’ denotes an obstacle (the path cannot be traversed), while the character ‘0’ (Zero) represents a traversable positions. Any position within the map is indicated by the coordinates (k, j), where k is the row number (ordered top to bottom) and j is the column number (ordered left to right), starting from 1. For example, the top left position is (1, 1) and the bottom right is (4, 10).

A robot moves in the map and gathers information along the way. In this version, the robot has a single non-deterministic Move action and its sensors reports whether or not obstacles lay immediately to the north, south, east, and west. A sequence of

Semester 1 2023 Page 1

sensor readings observed is the set of possible blocked directions. The following shows the example of the observed sensor readings at each time step; which means e.g., at time 1, the north (N), south (S) and west (W) of the robot have obstacles:

Time Steps 1 2 3 4 Blocked direcition(s) NSW NS N NE

1.1 Problem formulation

• The state variable Xt represents the location of the robot on the discrete grid; the domain of this variable is the set of traversable points illustrated as ‘0’ points in the map.

• Let NEIGHBORS(i) be the set of traversable points that are adjacent to and let N(i) be the size of that set. Then the transition model for the Move action is defined as follows, which means the robot has equal probability to move to each of its neighbours.

(1/N(i) if j ∈ NEIGHBORS(i) P (Xt+1 = j|Xt = i) = 0 otherwise

We don’t know where the robot starts, so we will assume a uniform distribution over all the sates; that is, P(X0 = i) = 1/K, where K is the number of ‘0’ points in the map.

• The sensor variable Et has 16 possible values, each a four-bit sequence giving the presence or absence of an obstacle in each of the compass directions (North, East, South and West). NSWE is the way of specifying the four-bit sequence and your program must expand each direction in this order. For example, a four-bit sequence 1010 represents that the sensors report an obstacle on its north and south positions and the east and west positions do not have obstacles.

• The sensors’ error rate is ε and that errors occur independently for the four sensors. In that case, the probability of getting all four bits right is (1 − ε)4, and the probability of getting them all wrong is ε4. Furthermore, if dit denotes the number of directions are reporting erroneous values, then the probability that a robot at position i would receive a sensor reading et (i.e., the observation/emission model) is:

Semester 1 2023 Page 2

P(Et =et|Xt =i)=(1−ε)4−ditεdit

Using the above problem formulation, you are requested to use the Viterbi forward algorithm provided below to find the Trellis matrix. A trellis matrix gives us the prob- ability of each state (path in this case) given each observation made by the robot’s sensors. For the path(s) which cannot be traversed, the probability is 0 (Zero) in the trellis matrix. Therefore, the trellis matrix could reflect the possible positions of the robot.

Algorithm 1 Viterbi forward algorithm

  1:

2: 3: 4: 5: 6: 7: 8:

9: 10: 11:

input: O, observation space O = {o1, o2,...,oN}.

S, state space S = {s1,s2,...,sK} // Here, K refers to the traversable positions.

Q, array of initial probabilities Q = (π1,π2,...,πK) Y, a sequence of observations Y = (y1,y2,...,yT ). Tm, transition matrix of size K x K.

Em, emission matrix of size K x N.

output: Trellis matrix foreachpositioni=1,2,...,Kdo

trellis[i,1] ← πi * Emiy1 end for

for each observation j = 2, 3, ...T do for each state i = 1, 2, ...K do

trellis[i,j] ← max(trellis[k, j - 1] * T mki ∗ Emiyj ) k

prior positions and yj is the observation at time j. end for

end for return trellis

// Here, π1 = π2 =,...,πK.

// Here, k is the most likely

 1.2 Deliverables

Write your robot localisation program in Python 3.6.9 in a file called viterbi.py. Your program must be able to run as follows:

$ python viterbi.py [input]

Input: Here, [input] specifies the path to a text file. In GradeScope, the file path will

be provided. Your program need to be able to read the file in the following format: Semester 1 2023 Page 3

4 10 0000X0000X XX00X0XX0X X000X0XX00 00X000X000 4

1011

1010

1000

1100

0.2

The description of the input file to the program is as follows:

• The first line indicates the size of the map (rows by columns).

• The map data then follows for the specified number of rows, where all values are either 0 or X.

• Next line specifies the number of sensor observation(s).

• The observed values then follows for the specified number of rows corresponding

to each time step.

• The last line specifies the sensor’s error rate ε.

Given the inputs, your program must compute a trellis matrix (following the pre- scribed Algorithm 1) using the input provided. Your program must then build a map representations of the probabilities of each position at each time step using the trellis matrix. Remember, the path(s) which cannot be traversed, the probability is 0 (Zero) in the trellis matrix.

Output: Your program is required to output the map representations in a file called output.npz. We will assess the content of this output file. A sample of the output file is depicted below.

Each map representation is of the same size as of the input map. Below shows 2 map representations, representing the probabilities of all the positions present in the map at each time step (sensor observations). Since, we have 4 observations in the above example input file, your program will output 4 such map representations.

Semester 1 2023 Page 4

0.01575 0.00000

0.00394 0.00098

0.00000 0.00098

. . . . . . ..

0.00000 0.00000

 . 0.01575

0.00020 0.00000

.  0.00025

0.00000 0.00000

. . .....

0.00025 0.00000 ... 0.00645 0.00020 ...

0.00000 0.00000 ... . . ..

.  .....

 .

0.00001 0.00040 0.00000 . . . 0.00001

And so on..

Hint: For saving these maps in a output.npz file. You can use Numpy’s savez()

official documentation.

    maps = list of numpy matrices at each time step.

    np.savez("output.npz", *maps)

1.3 Python libraries

You are allowed to use the Python standard library to write your decision tree learning program (see https://docs.python.org/3/library/ for the components that make up the Python v3.6.9 standard library). In addition to the standard library, you are allowed to use NumPy. Note that the marking program will not be able to run your program to completion if other third party libraries are used.

1.4 Submission

You must submit your program files on Gradescope. Instructions on accessing Grade- scope and submitting assignments are provided at https://help.gradescope.com/ article/5d3ifaeqi4-student-canvas. Please use the course code 6ZWNXV to en- rol into the course.

For undergraduates, please submit your robot localisation program (viterbi.py) to Assignment 3 - Undergraduates. If there are any questions or issues with Grade- scope, please contact Ankit Yadav via email at [email protected].

1.5 Expected run time

Your program must be able to terminate within 300 seconds for the given 2D map. Semester 1 2023 Page 5

1.6 Assessment

We will compile and run your code on several test problems. If it passes all tests, you will get 15% (undergrads) or 12% (postgrads) of the overall course mark.

There will be no further manual inspection/grading of your program to award marks on the basis of coding style, commenting or “amount” of code written.

1.7 Using other source code

You should not use other source code(s) for this assignment. All submitted code must be your own work written from scratch. Only by writing the solution yourself will you fully understand the concept of the Viterbi algorithm.

1.8 Due date and late submission policy

This assignment is due by 11:59pm Wednesday 7 June 2023. If your submission is late the maximum mark you can obtain will be reduced by 25% per day (or part thereof) past the due date or any extension you are granted.

Continues next page for postgraduate section.

Semester 1 2023 Page 6

2 3D Robot Localisation (PG only)

For postgraduate students, completing this section successfully will give you the remain- ing 3% of the marks. UG students who pass this part will get 3% bonus marks.

The problem settings remain the same as described in Sec. 1.1.

2.1 Deliverables

Write your 3D robot localisation program in Python 3.6.9 in a file called viterbi 3d.py. Your program must be able to run as follows:

$ python viterbi_3d.py [input]

Input: Here, [input] specifies the path to a text file. In GradeScope, the file path will

be provided. The input file format is similar as defined in the above Sec. difference is we have 3 dimensions as depicted below.

11 7 2 XXXX00XX0XXXXX X0000XX0XX0X00 0X0X0X0X000000 000X000X0XXXXX 0XXX00XXXXX0X0 0X00XX00XXX0X0 X0XXX000XXXXX0 XX0XXX0XXX000X 00000XX000000X XXX0XX00XX0X0X 0X00XX0X000X0X 4

000111

000011

000001

101110

0.3

The description of the input file to the program is as follows: Semester 1 2023 Page 7

1.2. The only

• The first line indicates the size of the map (rows by columns and depth).

• The map data then follows for the specified number of rows, where all values are either 0 or X. Where each row is equally divided into d sections where d is depth. For example, the top left position is (1, 1, 1) and the bottom right is (11, 7, 2).

• Next line specifies the number of sensor observation(s).

• The observed values then follows for the specified number of rows corresponding

to each time step.

• The last line specifies the sensor’s error rate ε.

• The sensor variable Et has 64 possible values, each a six-bit sequence giving the presence or absence of an obstacle in each of the compass directions (North, South, West and East) along with Top and Bottom. NSWETB is the way of specifying the six-bit sequence and your program must expand each direction in this order. For example, a six-bit sequence 101010 represents that the sensors report an obstacle on its north, west and Top positions and the south, east and bottom positions do not have obstacles.

• The sensors’ error rate is ε and that errors occur independently for the six sen- sors. In that case, the probability of getting all six bits right is (1 − ε)6, and the probability of getting them all wrong is ε6. Furthermore, if dit denotes the number of directions are reporting erroneous values, then the probability that a robot at position i would receive a sensor reading et (i.e., the observation/emission model) is:

P(Et =et|Xt =i)=(1−ε)6−ditεdit

Using the above problem formulation, you are requested to update your Viterbi forward algorithm from Section 1 to be able to take the information for additional dimension. A trellis matrix gives us the probability of each state (path in this case) given each observation made by the robot’s sensors. For the path(s) which cannot be traversed, the probability is 0 (Zero) in the trellis matrix. Therefore, the trellis matrix could reflect the possible positions of the robot. Your program must then build map representations of the probabilities of each position at each time step using the trellis matrix.

Semester 1 2023 Page 8

Output: Your program is required to output the map representations in a file called output.npz. We will assess the content of this output file. The content of this file is exactly the same as defined in the above Sec. 1.2 but with an additional dimension of depth.

Submit your program in the same way as the submission for Sec. 1. For postgradu- ates, please submit your robot localisation programs (viterbi.py and viterbi 3d.py) to Assignment 3 - Postgraduates. The due date, late submission policy, python libraries, execution run time and code reuse policy are also the same as in Sec. 1.

∼∼∼ The End ∼∼∼

Semester 1 2023 Page 9