CS401 Homework 8 -Solved

 Occupancy grid maps (Hans Moravec, A.E. Elfes: High resolution maps from wide angle sonar, Proc. IEEE Int. Conf. Robotics Autom. (1985)) are a popular approach to represent the environment of a mobile robot given known poses. The grid is basically discrete representation of the environment, which stores the posterior probability that the corresponding area in the environment is occupied or not, and each grid cell is considered independently from all others. Occupancy grid maps can be learned efficiently using a probabilistic approach. Reflection maps are an alternative representation. They store in each cell the probability that a beam is reflected by this cell. In this homework, we focus on the usage of probabilistic approach.

 Occupancy Mapping
 A robot has to build an occupancy grid map (cells c0, . . . cn) of a simple one-dimensional environment using a sequence of measurements from a range sensor:
  
 Assume a very simple sensor model: every grid cell with a distance (based on its coordinate) smaller than the measured distance is assumed to be occupied with p = 0.3. Every cell behind the measured distance is occupied with p = 0.6. Every cell located more than 20cm behind the measured distance should not be updated.

 Task 1
 Please calculate the resulting occupancy grid map using the inverse sensor model using Python.

 Assign the cell coordinates, which span from 0 to 200 (both endpoints included) with increments of 10, to one array c and the belief values to another array m. Use matplotlib.pyplot.plot(c,m) to visualize the belief.

 The measurements and the prior belief are given in the follow table:

 Grid resolution
10cm
Map length (1D only)
2m
Robot position
c0
Orientation (of th e sensor)
heading to cn (see figure)
Measurement (in cm)
101, 82, 91, 112, 99, 151, 96, 85, 99, 105
Prior
0.5
 In order to solve this exercise we will use log-odds, as they provide a very simple update formula, with only one addition and one subtraction. Recall the log-odds update formula:

 From the exercise we know that the prior:

 We also know that the inverse sensor model is the following:

The log-odds ratio should be applied to this function in order to obtain  . Note that unused in this context means we should not update the corresponding   cells. Doing an update with   would be equivalent, since  , but computationally more expensive.

 The solution of this exercise will thus involve applying for each measurement and for each cell the log-odds update formula. Once we are done with that we convert from log-odds to probability and display the output. Note that the inverse transformation is the unique solution w.r.t. p of the log-odds definition:

 Task 2
 Prove that in the occupancy grid mapping framework the occupancy value of a grid cell   is independent of the order in which the measurements are integrated.

 Let us consider the log-odds update formula and let us recursively unwrap it:

 It is clear that   is simply a sum of the log-odds form of the inverse measurements. Suppose that we exchange a measurement at time i with the measurement at a different time j. Since the sum is a commutative operator we will still obtain the same value of  . Hence, we can repeat exchanging measurements to obtain any order permutation of the measurements without changing the result. Finally, since the log-odds value does not change, neither will the corresponding probability.

 Code instructions for tasks
 Note1 task1.py give the implememtation framework of the task1.

 Note2 task2.py give the implememtation framework of the task2.