We've created a LaTeX template here for you to use that contains the prompts for each question.

  python --version
  

  python3 --version
  

conda create --name cs221_hw7 python=3.10

conda activate cs221_hw7

python drive.py -l lombard -i none

Modeling car locations

At each time step $t$, let $C_t \in \mathbb R^2$ be a pair of coordinates representing the actual location of the single other car (which is unobserved). We assume there is a local conditional distribution $p(c_t \mid c_{t-1})$ which governs the car's movement. Let $a_t \in \mathbb R^2$ be your car's position, which you observe and also control. To minimize costs, we use a simple sensing system based on a microphone. The microphone provides us with $D_t$, which is a Gaussian random variable with mean equal to the true distance between your car and the other car and variance $\sigma^2$ (in the code, $\sigma$ is Const.SONAR_STD, which is about two-thirds the length of a car). In symbols,

For example, if your car is at $a_t = (1,3)$ and the other car is at $C_t = (4,7)$, then the actual distance is $5$ and $D_t$ might be $4.6$ or $5.2$, etc. Use util.pdf(mean, std, value) to compute the probability density function (PDF) of a Gaussian with given mean mean and standard deviation std, evaluated at value. Note that evaluating a PDF at a certain value does not return a probability -- densities can exceed $1$ -- but for the purposes of this assignment, your computations can get away with treating the returned PDF value like a probability. The Gaussian probability density function for the noisy distance observation $D_t$, which is centered around your distance to the car $\mu = \|a_t - C_t\|_2$, is shown in the following figure:

Your job is to implement a car tracker that (approximately) computes the posterior distribution $\mathbb P(C_t \mid D_1 = d_1, \dots, D_t = d_t)$ (your beliefs of where the other car is) and update it for each $t = 1, 2, \dots$. The helper code will take care of using this information to actually drive the car (i.e., set $a_t$ to avoid a collision with $c_t$), so you don't have to worry about that part.

To simplify things, we will discretize the world into tiles represented by (row, col) pairs, where 0 <= row < numRows and 0 <= col < numCols. For each tile, we store a probability representing our belief that there's a car on that tile. The values can be accessed by: self.belief.getProb(row, col). To convert from a tile to a location, use util.rowToY(row) and util.colToX(col).

Here's an overview of the assignment components:

• In Problems 1 and 2 (written and code), you will check your understanding and implement ExactInference, which computes a full probability distribution of another car's location over tiles (row, col).
• Problem 3 (written) gives you a chance to extend your probability analyses to a slightly more realistic scenario where there are multiple other cars and we can't automatically distinguish between them.
• Problem 4 (written) asks you to consider concepts in research ethics that one may encounter in the development of autonomous vehicles and similar technologies.

A few important notes before we get started:

• Past experience suggests that this will be one of the most conceptually challenging assignments of the quarter for many students. Please start early, especially if you're low on late days!
• We strongly recommend that you attend/watch the lectures on Bayesian networks and HMMs before getting started, and keep the slides handy for reference while you're working. The code portions of this assignment are short and straightforward -- no more than about 10 lines in total -- but only if your understanding of the probability concepts is clear!
• For the coding sections, you should always use util.pdf instead of from util import * and referencing pdf() directly. Also, don't use keyword arguments for util.pdf and just pass parameters directly, e.g. util.pdf(mean, std, value) and not util.pdf(mean=mean, std=std, value=value)
• As a notational reminder: we use the lowercase expressions $p(x)$ or $p(x|y)$ for local conditional probability distributions, which are defined by the Bayesian network. We use the uppercase expressions $\mathbb P(X = x)$ or $\mathbb P(X = x | Y = y)$ for joint and posterior probability distributions, which are not pre-defined in the Bayesian network but can be computed by probabilistic inference. Please review the lecture slides for more details.

Problem 1: Emission probabilities

In this problem, we assume that the single other car is stationary (e.g., $C_t = C_{t-1} = C$ for all time steps $t$). We'll denote the single variable representing the other car's stationary location as $C$, and note that $p(C)$ is a known local conditional distribution. You will implement a function observe that upon observing a new distance measurement $D_t = d_t$ updates the current posterior probability from $$\mathbb P(C \mid D_1 = d_1, \dots, D_{t-1} = d_{t-1})$$ to find the posterior for the next time step $$\mathbb P(C \mid D_1 = d_1, \dots, D_t = d_t) $$ The current posterior probability is stored as self.belief in ExactInference.

1. Draw a Bayesian Network describing the distribution of variables $C, D_1, D_2, D_3, a_1, a_2, a_3$. Shade the variables that have been observed after time step $t=3$, and leave variables that are unobserved unshaded.
   A drawing of a Bayesian Network with nodes for each variable described above. Recall that if $p(X|\text{Parents}(X))$ is a known local conditional distribution, there should be one arrow for each of $X$'s parents pointing from the parent to $X$.
2. Give an expression for the joint probability $\mathbb P(C=c, D_1=d_1, D_2=d_2, D_3=d_3)$. Your expression should only use known local conditional distributions given by the Bayesian Network. Recall that the location of your car at each time step, i.e. $a_1, a_2, a_3$, is known with probability 1.
   A mathematical formula for the joint probability distribution of the variables described above that only uses local conditional distributions given in the problem.
3. Now suppose we have previously computed the posterior distribution up through time step $t-1$, i.e. we know $\mathbb P(C \mid D_1 = d_1, \cdots, D_{t-1}=d_{t-1})$. We make a new observation that $D_t=d_t$, and we'd like to update our posterior distribution to $\mathbb P(C \mid D_1 = d_1, \cdots, D_t = d_t)$. The unnormalized updated posterior can be computed as: $$\mathbb P(C=c \mid D_1=d_1, \cdots, D_t=d_t) \propto \mathbb P(C=c \mid D_1 = d_1, \cdots, D_{t-1}=d_{t-1}) p(d_t| C=c)$$ Fill in the observe method in the ExactInference class of submission.py. This method should modify self.belief in place to update the posterior probability of each tile given the observed noisy distance to the other car. After you're done, you should be able to find the stationary car by driving around it (using the flag -p means cars don't move):

Notes:

• Once you implement the observe function, you can start driving with exact inference.

  python drive.py -a -p -d -k 1 -i exactInference

  You can also turn off -a to drive manually.
• Read through the code in util.py for the Belief class before you get started... you'll need to use this class for several of the code tasks in this assignment.
• Remember to normalize the posterior probability after you update it. (There's a useful function for this in util.py).
• On the small map, the autonomous driver will sometimes drive in circles around the middle block before heading for the target area. In general, don't worry too much about the precise path the car takes. Instead, focus on whether your car tracker correctly infers the location of other cars.
• Don't worry if your car crashes once in a while! Accidents do happen, whether you are human or AI. However, even if there was an accident, your driver should have been aware that there was a high probability that another car was in the area.

Problem 2: Transition probabilities

Now, let's consider the case where the other car is moving according to transition probabilities $p(C_{t+1} \mid C_t)$. We have provided the transition probabilities for you in self.transProb. Specifically, self.transProb[(oldTile, newTile)] is the probability of the other car being in newTile at time step $t+1$ given that it was in oldTile at time step $t$.

1. Draw a Bayesian Network describing the distribution of variables $C_1, C_2, C_3, D_1, D_2, D_3, a_1, a_2, a_3$. Shade the variables that have been observed after time step $t=3$, and leave variables that are unobserved unshaded.
   A drawing of a Bayesian Network with nodes for each variable described above. Recall that if $p(X|\text{Parents}(X))$ is a known local conditional distribution, there should be one arrow for each of $X$'s parents pointing from the parent to $X$.
2. Give an expression for the joint probability $\mathbb P(C_1=c_1, C_2=c_2, C_3=c_3, D_1=d_1, D_2=d_2, D_3=d_3)$ which uses only known local conditional distributions. Recall that the location of your car at each time step, i.e. $a_1, a_2, a_3$, is known with probability 1.
   A mathematical formula for the joint probability distribution of the variables described above that only uses local conditional distributions given in the problem.

3. Now, you will implement a function elapseTime that updates the conditional probability about the location of the car at a current time $t$ $\mathbb P(C_t = c_t \mid D_1 = d_1, \dots, D_t = d_t)$ to the next time step $t+1$ conditioned on the same evidence, via the recurrence: $$\mathbb P(C_{t+1} = c_{t+1} \mid D_1 = d_1, \dots, D_t = d_t) \propto \sum_{c_t} \mathbb P(C_t = c_t \mid D_1 = d_1, \dots, D_t = d_t) p(c_{t+1} \mid c_t).$$ Again, the posterior probability is stored as self.belief in ExactInference.

   Finish ExactInference by implementing the elapseTime method. When you are all done, you should be able to track a moving car well enough to drive autonomously by running the following.

python drive.py -a -d -k 1 -i exactInference

Notes:

• You can also drive autonomously in the presence of more than one car:

  python drive.py -a -d -k 3 -i exactInference

• You can also drive down Lombard:

  python drive.py -a -d -k 3 -i exactInference -l lombard

  On Lombard, the autonomous driver may attempt to drive up and down the street before heading towards the target area. Again, focus on the car tracking component, instead of the actual driving.

Problem 3: Which car is it?

So far, we have assumed that we have a distinct noisy distance reading for each car at each time step. In reality, our microphone would just pick up an undistinguished set of these signals, and we wouldn't know which distance reading corresponds to which car. We'll now consider this more realistic setting.

First, let's extend the notation from before: let $C_{ti} \in \mathbb R^2$ be the location of the $i$-th car at the time step $t$, for $i = 1, \dots, K$ and $t = 1, \dots, T$. Recall that all the cars move independently according to the transition dynamics as before.

Let $D_{ti} \in \mathbb R$ be the noisy distance measurement of the $i$-th car at time step $t$, which is no longer directly observed. Instead, we observe the unordered set of distances $\{ D_{t1}, \dots, D_{tK} \}$ as a collective and so cannot attribute any individual measurement in this set to a specific car. (For simplicity, we'll assume that all distances are distinct values.) In other words, you can think of this scenario as the same as observing the list $\mathbf{E_t} = [E_{t1}, \dots, E_{tK}]$ which is a uniformly random permutation of the (noisy) correctly ordered distances $\mathbf{D_t} = [D_{t1}, \dots, D_{tK}]$ where index $i$ represents the noisy distance to car $i$ at time $t$.

For example, suppose $K=2$ and $T = 2$. Before, we might have gotten distance readings of $8$ and $4$ for the first car and $5$ and $7$ for the second car at time steps $1$ and $2$, respectively. Now, our sensor readings would be permutations of $\{8, 5\}$ (at time step $1$) and $\{4, 7\}$ (at time step $2$). Thus, even if we knew the second car was distance $5$ away at time $t = 1$, we wouldn't know if it moved further away (to distance $7$) or closer (to distance $4$) at time $t = 2$.

Below is a diagram that shows the flow of information corresponding to the above situation for the case where $K = 2$ and only showing two timesteps, $t$ and $t+1$. Note that because the observed distances $\mathbf{E_t}$ are a permutation of the true distances $\mathbf{D_t}$, each $E_{ti}$ depends on all of the $D_{ti}$. Also note that the above diagram is not a Bayes net as $E_{t1}$ and $E_{t2}$ are not conditionally independent given $D_{t1}$ and $D_{t2}$ (however, $D_{t1}$ and $D_{t2}$ are conditionally independent given $C_{t1}$ and $C_{t2}$).

1. Suppose we have $K=2$ cars and one time step $T=1$. Write an expression for the conditional probability $p(C_{11} = c_{11}, C_{12} = c_{12} \mid \mathbf{E_1} = \mathbf{e_1})$ as a function of the PDF of a Gaussian $\mathcal p_{\mathcal N}(v; \mu, \sigma^2)$ and the prior probability $p(c_{11})$ and $p(c_{12})$ over car locations. Note that by conditioning on $\mathbf{E_1} = \mathbf{e_1}$, we are saying we have seen a set of observations, but don't know which distance relates to which car. Your final answer should not contain variables $D_{11}$, $D_{12}$.

   Remember that $\mathcal p_{\mathcal N}(v; \mu, \sigma^2)$ is the probability of a random variable, $v$, in a Gaussian distribution with mean $\mu$ and standard deviation $\sigma$.

   Hint: for $K=1$, the answer would be $$p(C_{11} = c_{11} \mid \mathbf{E_1} = \mathbf{e_1}) \propto p(c_{11}) p_{\mathcal N}(e_{11}; \|a_1 - c_{11}\|_2, \sigma^2).$$ where $a_t$ is the position of your car (that you are controlling) at time $t$. Remember that $C_{ti}$ is the position of the $i$th observed car at time $t$. To better inform your use of Bayes' rule, you may find it useful to draw the Bayesian network and think about the distribution of $\mathbf{E_t}$ given $D_{t1}, \dots, D_{tK}$.

   Hint: Note that the observed variable(s) are the shuffled/randomized distances $\mathbf{E_t} = [E_{t1}, E_{t2}, ..., E_{tK}]$. These are a random permutation of the unobserved noisy distances $\mathbf{D_t} = [D_{t1}, D_{t2}, ..., D_{tK}]$, where $D_{t1}$ is the distance of car $1$ at timestep $t$. Note that $E_{t1}$ is the emission from one of the cars at timestep $t$, but we aren't sure which one (it is NOT necessarily car 1, it could be any of the cars). On the other hand, $D_{t1}$ is the measured distance of car 1 (we know with certainty that it comes from car 1), the only issue is that we don't observe it directly.

   Hint: To reduce notation, you may write, for example, $p(c_{11}∣e_{11})$ instead of $p(C_{11}=c_{11}∣E_{11}=e_{11})$.

   A mathematical expression, with the steps you took to derive that expression, relating (can be proportionality) $p(C_{11} = c_{11}, C_{12} = c_{12} | \mathbf{E_1} = \mathbf{e_1})$ with the PDF of a Gaussian and the priors $p(c_{11})$ and $p(c_{12})$ over car locations.
2. Assuming the prior $p(c_{1i})$ of where the cars start out is the same for all $i$ (i.e. for all K cars), show that the number of assignments for all $K$ cars $(c_{11}, \dots, c_{1K})$ that obtain the maximum value of $p(C_{11} = c_{11}, \dots, C_{1K} = c_{1K} \mid \mathbf{E_1} = \mathbf{e_1})$ is at least $K!$ (K factorial).

   You can also assume that the car locations that maximize the probability above are unique ($c_{1i} \neq c_{1j}$ for all $i \neq j$).

   Hint: The priors $p(c_{1i})$ are a probability distribution over the possible starting positions ($t=1$) of each car $i$. Note that even if the car positions share the same prior, it doesn't necessarily mean they have the exact same start positions $c_{1i}$ because the start positions are sampled from the prior distribution, which can yield different values each time it is sampled from. However, you should think about what the priors all being the same means intuitively in terms of how we can associate observations with cars.

   Note: you don't need to produce a complicated proof for this question. It is acceptable to provide a clear explanation based on your intuitive understanding of the scenario.

   Either a short mathematical argument or concise explanation for why the statement defined in the problem is true.
3. (extra credit) For general $K$, what is the treewidth corresponding to the posterior probability over all $K$ car locations at all $T$ time steps conditioned on all the sensor readings: $$p(C_{11} = c_{11}, \dots, C_{1K} = c_{1K}, \dots, C_{T1} = c_{T1}, \dots, C_{TK} = c_{TK} \mid \mathbf{E_1} = \mathbf{e_1}, \dots, \mathbf{E_T} = \mathbf{e_T})?$$ Briefly justify your answer.

   For reference, the treewidth of a factor graph is defined as the maximum arity (number of variables that a factor depends on) of any factor created by variable elimination under the best variable elimination ordering. You can find further information, along with an example, that may be relevant to this problem here.

   Note: the conditioning is already done, so the only factors remaining are for $C_{ti}$ variables.
   The treewidth as a function of $K$ and a brief justification for why the treewidth is represented by that function.
4. Now suppose you change your sensors so that at each time step $t$, they return the list of exact positions of the $K$ cars, but the list of positions is shifted by a random number of indices (with wrap around). For example, if the true car positions at time step $1$ are $c_{11} = (1, 1) , c_{12} = (3, 1), c_{13} = (8, 1), c_{14} = (5, 2)$, then $\mathbf{e_1}$ would be $[(1, 1), (3, 1), (8, 1), (5, 2)]$, $[(3, 1), (8, 1), (5, 2), (1, 1)]$, $[(8, 1), (5, 2), (1, 1), (3, 1)]$, or $[(5, 2), (1, 1), (3, 1), (8, 1)]$, each with probability $1/4$. The shift can change from one timestep to the next.

   Define auxiliary variables $z_1, z_2, \dots z_t$ which can be used to model the relation between $\mathbf{c_t}$ and $\mathbf{e_t}$. Give an expression for $p(\mathbf{c_t} \mid \mathbf{c_{t-1}})$ in terms of $\mathbf{e_1}, \cdots, \mathbf{e_t}$ and $z_t$.

   A description of auxiliary variables $z_t$ with their domains, followed by an expression for $p(\mathbf{c_t} \mid \mathbf{c_{t-1}})$.
5. (extra credit) Following up on Problem 3d, describe an efficient algorithm for computing $p(c_{ti} \mid \mathbf{e_1}, \dots, \mathbf{e_T})$ for any time step $t$ and car $i$. Your algorithm should not be exponential in $K$ or $T$.
   A description of the factor graph/Bayesian net used to model the problem, including any relevant variables and conditional probabilities. Also, a description of how you would use the factor graph to compute the provided probability. Note that you should try to simplify your expression for the probability as much as possible given the information provided.

Problem 4: Ethics in Advanced Technologies

1. Dual-use technologies serve two purposes: one with positive consequences and one with negative consequences. Researchers developing dual-use technologies face a moral dilemma: though they may intend to improve only peaceful, socially beneficial use of the technology, any improvements they make may also aid others who use the technology for harm. For example, tracking of the kind developed in this assignment can be used both in self-driving cars or in surveillance-tracking and autonomous weapons systems, such as lethal drones. To learn more about dual use technologies, refer back to the Externalities and Dual Use Technologies module (video, pdf).
   
   When integrating tracking technologies into self-driving cars, we have to make decisions regarding the tradeoff between the accuracy of the tracking technology and the privacy of the other cars and people on the road. These decisions impact the ways in which the tracking technology might be misused for negative aims. The microphone sensor used in Problems 1-3 preserves privacy relatively well; it only gives us a noisy distance reading. However, in practice, self-driving cars often use cameras (which provide more accurate readings than microphones), but also collect lots of visual information including, but not limited to, pedestrians’ faces and license plate numbers of other vehicles.
   
   How might the data collected by a camera sensor and/or the output of its reading be misused? What measures, if any, could you take to preempt this misuse?
   In 4-6 sentences, describe a potential misuse of the car tracking technology considered and what measures you might take to preempt such misuse, or explain why there are no such measures.
2. Self-driving cars and tracking technologies can potentially be hacked by bad actors to purposefully cause unsafe behavior (e.g., to harm people within a specific community). Research on adversarial ML focuses on how attacks like these can be carried out against machine learning systems and how to develop safeguards against such attacks [1].
   
   Two specific examples of adversarial ML attacks on self-driving cars include:
   • "Cloaking and stealthy attacks" to hide the presence of another vehicle from being detected
   • Sensor deception to make it seem like vehicles are closer or farther than they actually are
   Let's look at a case study with a sensor deception attack.
   
   Assume that sensor deception affects the problem setup from Problem 2 as follows. The observed distance $D_{t}^{'}$ after attack (see below) is now a skewed Gaussian distribution. To apply skewness, apply the adjustment below to the observed distance variable in submission.py ExactInferenceWithSensorDeception.observe() (we are using a technique called Box-Muller transform but you don’t need to know the details of this method for this problem). The skewness factor is set in the __init__ constructor with a default value of 0.5 (and you can assume the factor will always be greater than 0). Implement this change in the code and rerun python drive.py -a -p -d -k 3 -i exactInferenceWithSensorDeception to observe any changes.
   
   $D_{t}^{'} = \frac{1}{(1+\text{skewness}^2)} * D_t + \sqrt{2 * \frac{1}{(1+\text{skewness}^2)}}$
   Update the code in submission.py observe() for class ExactInferenceWithSensorDeception.
3. Comment on how one can guard against sensor deception if the type of attack is known beforehand (hint: consider redundancy of sensors).
   In 1-2 sentences, describe a way of guarding against sensor deception.
4. One way of increasing security and preventing adversarial attacks is by keeping data on-device. Assume that we are now using particle filtering, which is a more efficient, Monte-Carlo based method for car tracking. Though exact inference works well for small maps, it can be too slow on large worlds such as lombard. With particle filtering, the complexity of the program is $O(numParticles)$ as opposed to $O(numTiles)$. We have filled out the code for particle filtering for you. Simply run python drive.py -a -d -k 3 -i particleFilter to observe the behavior. Comment on how the simulation looks different from the exact inference case and provide a reason why.
   In 1-2 sentences, comment on the differences in the simulation with exactInference and particleFilter.
5. Assume that because particle filtering is more efficient, we can run the model on-device (vs. exact inference which requires us to run the model in the cloud). By keeping all of the relevant data on-device, we improve the privacy (security) of the data, but decrease the accuracy of the model. While the car can still sometimes make its way down Lombard effectively, it has a less accurate picture of other car locations. How would you weigh this trade-off?
   In 3-5 sentences, discuss how you would evaluate the privacy accuracy trade-off outlined above.

[1] See https://www.technologyreview.com/2017/08/22/242124/hackers-are-the-real-obstacle-for-self-driving-vehicles/

[2] See https://mit-serc.pubpub.org/pub/wrestling-with-killer-robots/release/2 and https://www.forbes.com/sites/cognitiveworld/2019/01/07/the-dual-use-dilemma-of-artificial-intelligence.

Submission is done on Gradescope.

Written: When submitting the written parts, make sure to select all the pages that contain part of your answer for that problem, or else you will not get credit. To double check after submission, you can click on each problem link on the right side, and it should show the pages that are selected for that problem.

Programming: After you submit, the autograder will take a few minutes to run. Check back after it runs to make sure that your submission succeeded. If your autograder crashes, you will receive a 0 on the programming part of the assignment. Note: the only file to be submitted to Gradescope is submission.py.

More details can be found in the Submission section on the course website.