The objective of this assignment is to estimate the probability distribution of the eventual location of a robot given a brief parametric description of its behavior over an indicated course. More specifically, the robot—which incorporates both sensor and motor errors—is tasked to find its way around a linear grid course characterized by wall-door-wall-door, respectively named P0 through P3.
An example problem has been provided. Unfortunately, the example evidences a variety of errors. For example, during the expansion and application of Bayes’s theorem, the constant 0.075 appears out of left field. As another example, the assertion that the probabilities of moving to the next grid, the subsequent grid, and the grid yet father evaluate to 70%, 20%, and 10%, respectively, even though it is clearly impossible to move to “the grid yet farther” if the robot is currently in either position P1 or position P2.
For this reason, it was decided to perform a strict Markov chain analysis based upon the available data. The first step is accurately to evaluate the probabilities of the constituent transitions, from which the transition matrix is formed. The transition matrix is subsequently raised to a high power in the endeavor to determine what the asymptotic probabilities of ending up in each grid are, as well as whether any absorbing state exists.
If the robot is in grid P0, the probabilities of transitioning to P1, P2, and P3 evaluate to 70%, 20%, and 10%, respectively. By symmetry, if the robot is in grid P3, the probabilities of transitioning to P0, P1, and P2 evaluate to 10%, 20%, and 70%, respectively.
If the robot is in grid P1, the notion of transitioning to “the grid yet farther” is zero—not 10%—since there is no P4. The only consistent information is that the probability of transitioning to the next grid is 70% and that the probability of transitioning to the remanent grid is 20%. Since 70% + 20% does not evaluate to unity, these figures must be scaled up accordingly to (10/9)(70%) = 77.8% and (10/9)(20%) = 22.2%. Moreover, since there are two “next” grids that can be reached with equal likelihood—note that, sensor errors notwithstanding, either both are doors or both are walls—their respective transition probabilities evaluate to 77.8% / 2 = 38.9%. Consequently, for P1, the probabilities of transition to P0, P2, and P3 evaluate to 38.9%, 38.9%, and 22.2%, respectively. Further, by symmetry, the probabilities that the robot, positioned at P2, will transition to P0, P1, and P3 evaluate to 22.2%, 38.9%, and 38.9%, respectively.
The transition matrix that forms the kernel of the required Markov chain is therefore constructed as follows:
| 0 0.7 0.2 0.1 |
| 0.389 0 0.389 0.222 |
| 0.222 0.389 0 0.389 |
| 0.1 0.2 0.7 0 |
In order to determine the probabilities that the robot will find itself in each of the grids P0 through P4 after an extended sequence of moves, the transition matrix is raised to a large power. It was straightforward to locate a free website that was capable of raising matrices to integer powers as large as 100 (“Matrix Power”). The result of that operation is the following matrix:
| 0.2022 0.2978 0.2978 0.2022 |
| 0.2022 0.2978 0.2978 0.2022 |
| 0.2022 0.2978 0.2978 0.2022 |
| 0.2022 0.2978 0.2978 0.2022 |
One learns from this closed-form evaluative technique that the probabilities that the robot ends up in P0, P1, P2, and P3 are 20.22%, 29.78%, 29.78%, and 20.22%, respectively.
Works Cited
“Matrix Power Calculator.” Reshish.com, 2022. matrix.reshish.com/power.php.