Intelligent Systems Lecture Notes

28 October 2011 • Markov Models

---

Outline

• Markov Chain
  • Stationary Markov Chain
  • Hidden Markov Model
• Localization
• Combining Sensor Information

An Agent’s World

An agent roams a 16-segment circular corridor. Segments 2, 4, 7, and 11 have doors.

An Agent's Problem

• The agent can sense doors and lights.
  • But the sensors are flakey.
• The agent can move forward or backward one segment.
  • But sometimes the agent overshoots by varying amounts, and sometimes it sticks in place.
• The agent starts in an unknown segment, and executes a known sequence of actions.
  • At the end of the actions, in which segment is the agent?

Markov Chain

• A Markov chain is a special belief network:

  

• Pr(S_{t + 1} | _{S sub 0}, …, S_t) = Pr(S_{t + 1} | S_t)).
• S_t is the state at time t.
  • Future states know only about S_t.
• The past is independent of the future given the present.

Stationary Markov Chain

• If

  pr (S_{t + 1} | S_t) = pr (S_{t + 1'} | S_t') for all t, t' > 0.

• the Markov chain is stationary.
• Specify pr (S₀) and pr (S_{t + 1} | S_t).
  • Simple model, easily specified.
  • Often the natural model.
  • Easily made infinite.

Hidden Markov Model

• A hidden Markov model (HMM) is a belief network:

  

  • pr (S₀) specifies initial conditions.
  • pr (S_{t + 1} | S_t) specifies the dynamics.
  • pr (O_t | S_t) specifies the sensor model.

Localization Example

Sensor Model Example

• Pr Observe door | at door = 0.8
• Pr Observe door | not at door = 0.1

Example Dynamic Model

Combining Sensor Information

L_t robot location at time t
A_t robot action at time t
D_t door-sensor value at time t
B_t brightness-sensor value at time t

Summary

References

• Inference in Temporal Models (Chapter 15) in Artifical Intelligence, third edition, by Stuart Russell and Peter Norvig, Prentice Hall, 2010.
• Design and Implementation (Chapter 3) in The Practice of Programming by Brian Kernighan and Rob Pike, Addison Wesley, 1999.

---

This page last modified on 2011 October 26.