Systematically searching for witness points for
all vectors in 
is computationally
expensive.
Point-based DP update does not do this.
Instead, it uses heuristics to come up with
a collection of belief points and backs up
on those points. It might miss witness points
for some of the vectors in and hence
is an approximation of standard DP update.
Obviously, backing up on different belief states
might result in the same vector. In other words,
and
might be equal
for two different belief states
b and b'. As such, it is possible that one gets
only a few vectors after many backups.
One issue in the design of point-based DP update
is to avoid this.
We address this issue using witness
points.
Point-based DP update assumes that one knows a
witness point for each vector in
its input set. It backs up on those
points.
The rationale is that witness points
for vectors in a given set ``scatter all over the belief space"
and hence the chance of creating duplicate vectors is low.
Our experiments have confirmed this intuition.
The assumption made by point-based DP update is reasonable because its input is either the output of a standard DP update or another point-based DP update. Standard DP update computes, as by-products, a witness point for each of its output vectors. As will be seen later, point-based DP update also shares this property by design.
Figure 3: Modified Value Iteration for POMDPs.