Sondik’s One-Pass Algorithm

As mentioned earlier, the modified exhaustive search with pruning approach can be seriously wasteful: It first computes the redundant set Λm in (7.107) that may contain many dominated vectors that will be removed by the dominance test in the second step of the algorithm. An alternative approach for efficiently computing optimal POMDP solutions thus is to avoid computing the set Λm all together and try to directly obtain the parsimonious set images from images However, so far, there is no algorithm that in general achieves this exactly. Many of the algorithms that follow this alternative approach construct an intermediate set that does not explicitly seem to be constructing Λm. Still, usually, this intermediate set can be bigger than the desired images . Hence, again, a pruning step is still included to remove the dominated vectors from the intermediate set so as to construct images . Sondik’s one-pass algorithm is one such algorithm [70, 71, 75].

We will need the following new notation:

Comparing with (7.98)) and (7.104), it is clear that is the set of β-vectors ...

Get Signal Processing for Cognitive Radios now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.