next up previous
Next: The Use of Point-Based Up: Point-Based DP Update: The Previous: The Backup Operator

Point-Based DP Update

Systematically searching for witness points for all vectors in tex2html_wrap_inline1230 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 tex2html_wrap_inline1230 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, tex2html_wrap_inline1304 and tex2html_wrap_inline1306 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.gif 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.

Dr. Lian Wen Zhang
Thu Feb 15 14:47:09 HKT 2001