next up previous
Next: Stopping Point-Based Value Iteration Up: Point-Based DP Update: The Previous: Retaining Uniform Improvability

The Algorithm

Here is the complete description of point-based DP update. It first backs up on the witness points of the input vectors. Then, it solves linear programs to identify more belief points and backs up on them so that its output dominates its input and hence is uniformly improvable.

 		  POINT-BASED-DPU tex2html_wrap_inline1612 :

1. tex2html_wrap_inline1614

2. tex2html_wrap_inline1492

3. return tex2html_wrap_inline1144 .

In terms of computational complexity, point-based DP update performs exactly tex2html_wrap_inline1620 backups in the first step and no more than tex2html_wrap_inline1622 backups in the second step. It solves linear programs only in the second step. The number of linear programs solved is upper bounded by tex2html_wrap_inline1624 and is usually much smaller than the bound. The numbers of constraints in the linear programs are upper bounded by tex2html_wrap_inline1626 .

There are several algorithms for standard DP update. Among them, the incremental pruning algorithm (Zhang and Liu 1997) has been shown to be the most efficient both theoretically and empirically (Cassandra et al. 1997). Empirical results (Section 6) reveal that point-based DP update is much less expensive than incremental pruning on a number of test problems. It should be noted, however, that we have not proved this is always the case.

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