A Survey of POMDP Applications

Summary:

Cassandra's survey summarizes some uses for partially observable Markov decision problems. MDPs are useful in artificial intelligence and planning applications. The overall structure of these problems involves states and transitions between the states, with costs associated with the transitions and states. The goal of a robot/problem is to find an optimal solution (policy) to a problem in the least number of transitions.

The POMDP model consists of:

• States
• Actions
• Observations
• A state transition function
• An observation function
• An immediate reward function

Cassandra's paper focuses on examples of using POMDPs, but he describes them in more detail here: http://www.pomdp.org/pomdp/index.shtml. Basically, they are MDP problems in which you cannot observe the entire state.

Some example applications include:

• Machine maintenance - parts of the machine are modeled as states, and the goal is to minimize the repair costs or maximize the up-time on the machine.
• Autonomous robots - robots need to navigate or accomplish a goal with a set of actions, and the world is not always observable
• Machine vision - determining where to focus higher resolution (i.e., fovea) of the computer image to focus on specific parts such as hands and heads of people.

POMDPs have a number of limitations. One limitation is that the states need to be discrete. Although continuous states can be discretized, some domains can have trouble with this step. The main issue with POMDPs is in their computation limits. POMDPs become intractable rather quickly since their state spaces are exponential.


Discussion:

This paper had little to nothing to do with what we've been currently discussing in class. Although POMDPs are interesting from a theoretical standpoint, their intractability is a huge factor for avoiding them in any practical domain. I've been trying to think of how to even apply them to gesture recognition, and one idea I came up with included modeling hand positions as states for a single gesture, but then it just becomes an HMM with a reward function, and I'm not sure how beneficial a reward function is when taking the computation costs into account.