COMP SCI 3007 Artificial Intelligence - Assignment 3: Robot Localisation (UG and PG)
Artificial Intelligence Assignment 3
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:
0 0 0 0 X 0 0 0 0 X X X 0 0 X 0 X X 0 X X 0 0 0 X 0 X X 0 0 0 0 X 0 0 0 X 0 0 0
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 kis the row number (ordered top to bottom) andjis 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 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 Xtrepresents 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. P(Xt+1=j|Xt=i) =( 1/N(i) if j ∈NEIGHBORS( 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 Kis the number of ‘0’ points in the map. •The sensor variable Ethas 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 west positions, while the east and westsouth 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 ditdenotes the number of directions are reporting erroneous values, then the probability that a robot at position iwould receive a sensor reading et(i.e., the observation/emission model) is:
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: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 probabilitiesQ= (π1,π2,...,πK) // Here, π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. 2:output: Trellis matrix 3:foreach position i= 1,2, ..., K do 4: trellis[i,1] ←πiEm iy1 5:end for 6:foreach observation j= 2,3, ...T do 7:foreach state i= 1,2, ...K do 8: trellis[i,j] ←max k(trellis[k, j - 1] Tmki∗Em iyj) // Here, k is the most likely prior positions and yjis the observation at time j. 9:end for 10:end for 11:return trellis
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:
4 10 0 0 0 0 X 0 0 0 0 X X X 0 0 X 0 X X 0 X X 0 0 0 X 0 X X 0 0 0 0 X 0 0 0 X 0 0 0 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.
aca77c7b-b1a73030-c57bdfa7-43fdc044 0.01575 0 .00394 0 .00098 . . .0.00000 0.00000 0 .00000 0 .00098 . . .0.00000 ............... 0.01575 0 .00025 0 .00000 . . .0.00025 0.00020 0 .00645 0 .00020 . . .0.00000 0.00000 0 .00000 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 ) toAssignment 3 - Undergraduates .
1.5 Expected run time
Your program must be able to terminate within 300 seconds for the given 2D map.
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.
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. 1.2. The only difference is we have 3 dimensions as depicted below. 11 7 2 X X X X 0 0 X X 0 X X X X X X 0 0 0 0 X X 0 X X 0 X 0 0 0 X 0 X 0 X 0 X 0 0 0 0 0 0 0 0 0 X 0 0 0 X 0 X X X X X 0 X X X 0 0 X X X X X 0 X 0 0 X 0 0 X X 0 0 X X X 0 X 0 X 0 X X X 0 0 0 X X X X X 0 X X 0 X X X 0 X X X 0 0 0 X 0 0 0 0 0 X X 0 0 0 0 0 0 X X X X 0 X X 0 0 X X 0 X 0 X 0 X 0 0 X X 0 X 0 0 0 X 0 X 4 000111 000011 000001 101110 0.3 The description of the input file to the program is as follows:
•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 Ethas 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 ditdenotes the number of directions are reporting erroneous values, then the probability that a robot at position iwould 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.
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 andviterbi 3d.py ) toAssignment 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 ∼∼∼
