A natural way to improve the quality of point-based update is to back up on additional belief points. We have explored the use of randomly generated points (Cassandra 1998a), additional by-product points, and projected points (Hauskrecht 2000). Here additional by-product points refer to points generated at various stages of standard update, excluding the witness points that are already being used. Projected points are points that are reachable in one step from points that have given rise to useful vectors.
Table 4 shows, for each test problem, the number of standard updates and the amount of time that VI1 took with and without using projected points. We see that the use of projected points did reduce the number of standard updates by one in 4x3CO, Cheese, and Shuttle. However, it increased the time complexity in all test problems except for Network. The other two kinds of points and combinations of the three did not significantly improve VI1 either. On the contrary, they often significantly degraded the performance of VI1.
A close examination of experimental data reveals a plausible explanation. Point-based update, as it stands, can already reduce the number of standard updates down to a just few and among them the last two or three are the most time-consuming. As such, the possibility of further reducing the number standard updates is low and even when it is reduced, the effect is roughly to shift the most time-consuming standard updates earlier. Consequently, it is unlikely to achieve substantial gains. On the other hand, the use of additional points always increases overheads.