**
Back
| POMDP Tutorial
**

#
Zhang and Liu's Incremental Pruning Algorithm

The latest approach, Zhang and Liu (1996), called incremental pruning,
combines elements of Monahan's enumeration and the witness algorithms.
Like witness, it considers constructing sets of vectors for each action
individually and then focusing on each one observation at a time.

The basic idea is to eliminate doing all this region business. Since
the main problem is in finding all the different combinations of future
strategies, we focus on this aspect of Zhang's algorithm. Adding the immediate
rewards is an easy step.

For a given action, we first construct all of S(a,z) sets (one for each
observation). In Monahan's algorithm we would then try all ways of combining
choices from each of these. Zhang's algorithm does this incrementally observation
by observation. For example:

###
Zhang's vector combinations

We do all combinations of the `S(a,z1)` and `S(a,z2)` vectors.
Which will yield a value function like this:
###
Zhang's resulting vectors

We then eliminate all those useless (light blue) vectors and are left with
just three vectors. We then combine these three with the vectors in `S(a,z3)`
as shown below.
###
Zhang's second step

This is repeated for the other action and then the sets combined just as
in the witness algorithm. There are some more sophisticated
generalizations of this algorithm (Cassandra, Littman and Zhang, 1997)
that can better exploit the geometry of the
values functions.
##
End of tutorial

**
Back
| POMDP Tutorial
**