Peter Norvig on Belief States - Dictionary of Arguments
Norvig I 156
Belief states/programming/artificial intelligence/Norvig/Russell: The idea of transforming partially observable problems into belief-state problems originated with Astrom (1965)(1) for the much more complex case of probabilistic uncertainty (…). Erdmann and Mason (1988)(2) studied the problem of robotic manipulation without sensors, using a continuous form of belief-state search. They showed that it was possible to orient a part on a table from an arbitrary initial position by a well-designed sequence of tilting actions.
More practical methods, based on a series of precisely oriented diagonal barriers across a conveyor belt, use the same algorithmic insights (Wiegley et al., 1996)(3). The belief-state approach was reinvented in the context of sensorless and partially observable search problems by Genesereth and Nourbakhsh (1993)(4). Additional work was done on sensorless problems in the logic-based planning community (Goldman and Boddy, 1996(5); Smith and Weld, 1998(6)). Bonet and Geffner (2000)(7) introduced the first effective heuristics
Norvig I 157
for belief-state search; these were refined by Bryce et al. (2006)(8). The incremental approach to belief-state search, in which solutions are constructed incrementally for subsets of states within each belief state, was studied in the planning literature by Kurien et al. (2002)(9); several new incremental algorithms were introduced for nondeterministic, partially observable problems by Russell and Wolfe (2005)(10). For uncertainty in temporal change see >Change/AI research.
1. Astrom, K. J. (1965). Optimal control of Markov decision processes with incomplete state estimation. J. Math. Anal. Applic., 10, 174–205.
2. Erdmann, M. A. and Mason, M. (1988). An exploration of sensorless manipulation. IEEE Journal of
Robotics and Automation, 4(4), 369–379.
3. Wiegley, J., Goldberg, K., Peshkin, M., and Brokowski, M. (1996). A complete algorithm for designing passive fences to orient parts. In ICRA-96.
4. Genesereth, M. R. and Nourbakhsh, I. (1993). Time-saving tips for problem solving with incomplete information. In AAAI-93, pp. 724–730.
5. Goldman, R. and Boddy, M. (1996). Expressive planning and explicit knowledge. In AIPS-96, pp.
6. Smith, D. E. and Weld, D. S. (1998). Conformant Graphplan. In AAAI-98, pp. 889–896.
7. Bonet, B. and Geffner, H. (2000). Planning with incomplete information as heuristic search in belief space. In ICAPS-00, pp. 52–61.
8. Bryce, D., Kambhampati, S., and Smith, D. E. (2006). Planning graph heuristics for belief space search. JAIR, 26, 35–99.
9. Kurien, J., Nayak, P., and Smith, D. E. (2002). Fragment-based conformant planning. In AIPS-02.
10. Russell, S. J. and Wolfe, J. (2005). Efficient belief-state AND-OR search, with applications to Kriegspiel. In IJCAI-05, pp. 278–285._____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. Translations: Dictionary of Arguments The note [Author1]Vs[Author2] or [Author]Vs[term] is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition.
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010