Computational Principles of Mobile Robotics

A full treatment of Markov models is beyond the limit of space available here. A number of introductory texts and tutorials on Markov models are given at the end of this chapter. The tutorial provided here follows that given in [520].

Discrete Markov Process

Suppose that an autonomous agent moves about its environment in such a way that transitions from one location to another are as sketched in Figure C.1. The robot's environment has 13 distinct locations, and at any one time the robot is in one of these. Identify these N = 13 distinct locations (or states) as S1, S2, …, Sn. At each time step the robot can move from one state to another, including possibly remaining in the same location, according to a set of probabilities associated with each state. Then the robot's environment can be represented as a directed graph with the nodes of the graph corresponding to the distinct locations and the directed edges of the graph corresponding to possible transitions for each location. Let t denote the time instant associated with robot motions (state changes), and denote the actual location (state) of the robot at time t as qt. Suppose that the robot at time t was in location Sk, at time t − 1 the robot was in location Sj, …, and at time 1 the robot was in location Si; then what is the probability that the robot is in location Sl at time t + 1?