

![0_image_0.png](0_image_0.png)

of the methods for 10 update cycles (each cycle consists of 40 grid point updates) on the Maze20 problem. We see that the differences in the quality of value-function approximations for different strategies (even the very simple ones) are relatively small. We note that we observed similar results also for other problems, not just Maze20.

The relatively small improvement of our heuristics can be explained by the fact that ery new linear function influences a larger portion of the belief space and thus the method should be less sensitive to a choice of a specific point. 27 However, another plausible explanation is that our heuristics were not very good and more accurate heuristics or combinations of heuristics could be constructed. Efficient strategies for locating grid points used in some of the exact methods, e.g. the Witness algorithm (Kaelbling et al., 1999) or Cheng's methods (Cheng, 1988) can potentially be applied to this problem. This remains an open area of research.

## 4.7.4 C Ontrol

The grid-based linear-function approach leads to a piecewise linear and convex approximation. Every linear function comes with a natural action choice that lets us choose the action greedily. Thus we can run both the lookahead and the direct controllers. Figure 26 compares the performance of four different controllers for the fixed grid of 40 points, combining standard and incremental updates with lookahead and direct greedy control after 1, 5 and 10 update cycles.  The results (see also Figure 24) illustrate the trade-offs between the computational time of obtaining the solution and its quality. We see that the incremental approach and the lookahead controller design tend to improve the control performance.  The prices paid are worse running and reaction times, respectively.