Search and Belief-Space Planning › Search and Belief-Space Planning

Imagine walking into a building you have never seen, with a hand-drawn floor plan someone gave you. The plan is roughly right. You have a model of the building (the floor plan), an observation (the weak flashlight), and an objective (the room). Your flashlight is weak, and the corridor ahead looks identical to the one behind you. You need to find a specific room, and you need to decide, right now, whether to walk forward, turn back, or stop and look around to figure out where you are.

That scenario contains the entire problem of this chapter. You have a model (the floor plan), an observation (the weak flashlight), and an objective (the room). Turning the model into an action requires something that neither the model nor the objective provides by itself. It requires a decision procedure for evaluating candidate actions or contingent policies and selecting what to do. In this chapter, that decision procedure is search.

Why does that procedure deserve an entire chapter of its own, when the previous chapters already gave us planners? Search allocates compute differently from the preceding planners, which can make it especially useful in some large, discrete, or partially observed problems. To see why, it helps to recall what the alternatives do with their compute.

Search-based planning sits alongside the two planning families you have already seen in this part. In Sampling-Based Planning and Model Predictive Control you saw planners that score sampled action sequences. In Differentiable Planning you saw planners that optimize one smooth action sequence by differentiating through latent state dynamics $z_{t+1}=f(z_t,a_t)$ and a cost over horizon $H$. Both can focus computation: adaptive shooting methods such as CEM refit their proposal distributions, and gradient methods follow local derivatives. Tree search focuses it differently. Each simulation updates branch statistics, and those statistics determine which branch receives the next simulation. This explicit, adaptive allocation is especially useful when the horizon is long, the choices are discrete, or the model is available only as a simulator. It does not imply that all search problems are nondifferentiable; it means tree search does not require derivatives from the simulator interface.

The simulator interface is worth stating precisely. Gradient planning needs derivatives through the model. Shooting methods and Monte Carlo tree search can instead use a generative model: given a state and action, sample a successor, reward, and, for a partially observed problem, an observation. Tree search is therefore a natural option when derivatives are unavailable and discrete branching matters, but its interface is not weaker than every shooting method's interface. Both families can work with forward samples; they differ in how they reuse those samples and allocate the next query.

The second half of the chapter addresses the harder half of the problem. The planner comparison immediately above assumed you know what state you are in. In the corridor, you do not. You know a distribution over states, which we have been calling a belief, and for which you built machinery back in Bayesian Filtering and Belief States. Planning with a belief as your starting point changes the problem in a way that is not merely quantitative. Actions that change what you can observe may become valuable even when they make little immediate physical progress. In this chapter you will see how to search over beliefs, how to recognize information-gathering behavior when it emerges, and how to make the search cheap enough to run inside a control loop.

That phrase "not merely quantitative" needs unpacking before we start. If uncertainty only made our estimates noisier, we could handle it with the same planning machinery and a little more caution. But uncertainty adds structure to the problem. It gives information a decision value that is absent when the relevant state is already known. An uncertain agent may have to trade task progress against observations that improve later choices, and a planner that cannot represent that tradeoff can miss good policies rather than merely attach noisier values to them. This is the sense in which the second half of the chapter differs from the first, even though the two share an algorithm.

The chapter proceeds as follows. We start with tree search and Monte Carlo Tree Search (MCTS), the workhorse algorithm that turns a simulator into a decision rule. We then confront partial observability and see why the MDP machinery breaks, which leads to the belief MDP and its difficult continuous state space. Next we build belief trees, the structures that let a planner reason about observations, and we work through the classic tiger problem to see information gathering emerge from expected value alone. We then put all of it together in a hidden-state maze where an agent has to infer its location while choosing movements. Finally, we replace hand-crafted heuristics with learned guidance and measure how a small neural network changes finite-budget MCTS in this maze. Throughout, we will keep model error, sampling error, and search confidence separate, because conflating them makes finite-budget results easy to overstate.