next up previous
Next: Point-Based DP Update Up: Point-Based DP Update: The Previous: Point-Based DP Update: The

The Backup Operator

  Let tex2html_wrap_inline1142 be a set of vectors and b be a belief state. The backup operator constructs a new vector in three steps:

  1. For each action a and each observation z, find the vector in tex2html_wrap_inline1142 that has maximum inner product with tex2html_wrap_inline1268 -- the belief state for the case when z is observed after executing action a in belief state b. If there are more than one such vector, break ties lexicographically (Littman 1996). Denote the vector found by tex2html_wrap_inline1276 .
  2. For each action a, construct a vector tex2html_wrap_inline1280 by:


  3. Find the vector, among the tex2html_wrap_inline1280 's, that has maximum inner product with b. If there are more than one such vector, break ties lexicographically. Denote the vector found by tex2html_wrap_inline1286 .

It has been shown (Smallwood and Sondik 1973, Littman 1996) that tex2html_wrap_inline1288 is a member of tex2html_wrap_inline1230 -- the set of vectors obtained by performing DP update on tex2html_wrap_inline1142 . Moreover, b is a witness point for tex2html_wrap_inline1296 .

The above fact is the corner stone of several DP update algorithms. The one-pass algorithm (Sondik 1971), the linear-support algorithm (Cheng 1988), and the relaxed-region algorithm (Cheng 1988) operate in the following way: They first systematically search for witness points of vectors in tex2html_wrap_inline1230 and then obtain the vectors using the backup operator. The witness algorithm (Kaelbling et al. 1998) employs a similar idea.

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