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.

Thu Feb 15 14:47:09 HKT 2001