ANP- Homework #1 Solved

Make sure to name the submitted file ID1-ID2.zip (or .pdf) with ID1,ID2 - the students’ ids.
For hands-on parts, your source code should be submitted as well (include it in the above zip file).
Theoretical questions:

(Bayesian inference) Consider probabilistic motion and observation models
P(xk+1 | xk,ak) , P(zk | xk).

Assume at each time instant i a robot/agent gets an observation zi and performs action ai, that transitions its state from xi to xi+1. Assume a prior P(x0) is available.

Provide a full and detailed derivation of the following (indicate clearly all assumptions in derivation):

Recursive formulation: Express the posterior distribution over state xk at time instant k in terms of the posterior distribution over xk−1 from the previous time instant k − 1.
Smoothing formulation: Express the posterior distribution over past and current states, x0:k at time instant k, in terms of the corresponding posterior distribution from the previous time instant k − 1.
Smoothing formulation: Express the posterior distribution over past and current states, x0:k at time instant k, in terms of all actions and observations obtained thus far.
(Occupancy grid mapping) Consider a robot maps an unknown environment and assume localization is known (i.e. robot pose xi at each time instant i is known). Denote by M an occupancy grid map that partitions an environment into a set of cells (or voxels): M = {mi}. Develop equations of a binary Bayes filter considering a binary state m ∈ {occ,free} (e.g. one of the cells mi):Express the distribution over the hypotheses m = free and m = occ at time instant k, given observations z1:k captured from known locations/poses x1:k, and considering an inverse observation model P(m | z,x).
Define the log-odds ratio as freefree) ). Using the result from clause 2a, express the log-odds ratio lk(m) at time instant k in terms of lk−1(m),zk,xk and prior P(m).
Explain how to get a posterior distribution over M at time instant k based on clause 2a and state any assumptions you take.
Hands-on tasks:

Read Appendix G of the book https://algorithmsbook.com/# to make yourself familiar with Julia language. The official Julia Debugger is based on Visual Studio Code https://code.visualstudio.com/. To set up the debugging environment, you will need to install VSCode, and an extension called Julia. The core component to be installed is Julia language itself. Download the latest release from here https:// julialang.org/downloads/ (currently 1.7.2) and unpack somewhere. In VSCode open the Julia extension settings and set the Executable Path (<full_path_to_julia_executable/julia>).
If everything was set up correctly by pressing Alt+j, Alt+o, you would be able to start Julia REPL tied to the VSCode debugger. You also can use the button “run” to start the REPL and run the current opened file.

1

Julia is bleeding edge just in time compiled high performance oriented language. Therefore, it does various caching and precompilation operations. Thus, some code changes require restarting the REPL. Luckily to us, there is an essential package called “Revise” to avoid this.

VSCode debugger can run the file in interpreted and compiled mode. Without a debugger, Julia always runs in compiled mode. This mode is faster, but the debugging capabilities in this mode are not mature yet. In the VSCode debugger in the window of breakpoints, there is a compiled mode option. Run the file “main.jl” in two modes and observe speedup in compiled mode. Note that there is an included file “utils.jl”. We will use functions from this file in the