The DOI matches its Crossref record; 133 of the 133 references it cites were found in a registry or an index.
Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
Open accessAbstract
Planning under uncertainty is a central problem in the study of automated sequential decision making, and has been addressed by researchers in many different fields, including AI planning, decision analysis, operations research, control theory and economics. While the assumptions and perspectives adopted in these areas often differ in substantial ways, many planning problems of interest to researchers in these fields can be modeled as Markov decision processes (MDPs) and analyzed using the techniques of decision theory. This paper presents an overview and synthesis of MDP-related methods, showing how they provide a unifying framework for modeling many classes of planning problems studied in AI. It also describes structural properties of MDPs that, when exhibited by particular classes of problems, can be exploited in the construction of optimal or approximately optimal policies or plans. Planning problems commonly possess structure in the reward and value functions used to describe performance criteria, in the functions used to describe state transitions and observations, and in the relationships among features used to describe states, actions, rewards, and observations. Specialized representations, and algorithms employing these representations, can achieve computational leverage by exploiting these various forms of structure. Certain AI techniques -- in particular those based on the use of structured, intensional representations -- can be viewed in this way. This paper surveys several types of representations for both classical and decision-theoretic planning problems, and planning algorithms that exploit these representations in a number of different ways to ease the computational burden of constructing policies or plans. It focuses primarily on abstraction, aggregation and decomposition techniques based on AI-style representations.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Reinforcement Learning: An Introduction
Sutton, R. S., & Barto, A. G. (1998) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.1998.712192 · Cited by 27,225
Reinforcement Learning: An Introduction
(2005) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2004.842673 · Cited by 24,496
(1988) · Cited by 16,582
Bellman, R. E. (2010) · doi:10.1515/9781400835386 · Cited by 14,588
Graph-Based Algorithms for Boolean Function Manipulation
Bryant (1986) · IEEE Transactions on Computers · doi:10.1109/tc.1986.1676819 · Cited by 8,891
Decisions with Multiple Objectives: Preferences and Value Tradeoffs.
Tsoukias, A., Keeney, R. L., & Raiffa, H. (1994) · The Journal of the Operational Research Society · doi:10.2307/2584151 · Cited by 8,370
Introduction to Reinforcement Learning
Sutton, R. S., & Barto, A. G. (1998) · The MIT Press eBooks · Cited by 6,855
Markov Decision Processes: Discrete Stochastic Dynamic Programming
Puterman, M. L. (1994) · Wiley Series in Probability and Statistics · doi:10.1002/9780470316887 · Cited by 6,024
STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving
Fikes, R. E., & Nilsson, N. J. (1971) · Artificial Intelligence · doi:10.1016/0004-3702(71)90010-5 · Cited by 4,882
Floyd, R. W. (1962) · Communications of the ACM · doi:10.1145/367766.368168 · Cited by 3,998
Cited by
A Roadmap of Agent Research and Development
Jennings, N. R., Sycara, K., & Wooldridge, M. (1998) · Autonomous Agents and Multi-Agent Systems · doi:10.1023/a:1010090405266 · Cited by 2,161
Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition
Dietterich, T. G. (2000) · Journal of Artificial Intelligence Research · doi:10.1613/jair.639 · Cited by 1,435
A domain-independent framework for modeling emotion
Gratch, J., & Marsella, S. (2004) · Cognitive Systems Research · doi:10.1016/j.cogsys.2004.02.002 · Cited by 725
Reinforcement Learning and Markov Decision Processes
van Otterlo, M., & Wiering, M. (2012) · Adaptation, Learning, and Optimization · doi:10.1007/978-3-642-27645-3_1 · Cited by 628
Value-Function Approximations for Partially Observable Markov Decision Processes
Hauskrecht, M. (2000) · Journal of Artificial Intelligence Research · doi:10.1613/jair.678 · Cited by 527
A Survey of Multi-Objective Sequential Decision-Making
Roijers, D. M., Vamplew, P., Whiteson, S., & Dazeley, R. (2013) · Journal of Artificial Intelligence Research · doi:10.1613/jair.3987 · Cited by 461
Artificial intelligence: foundations of computational agents
(2010) · Choice Reviews Online · doi:10.5860/choice.48-2130 · Cited by 415
Reinforcement Learning for RoboCup Soccer Keepaway
Stone, P., Sutton, R. S., & Kuhlmann, G. (2005) · Adaptive Behavior · doi:10.1177/105971230501300301 · Cited by 387
SPUDD: Stochastic Planning using Decision Diagrams
Hoey, J., St‐Aubin, R., Hu, A. J., & Boutilier, C. E. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.6704 · Cited by 380
Self-citationThe Communicative Multiagent Team Decision Problem: Analyzing Teamwork Theories and Models
Pynadath, D. V., & Tambe, M. (2002) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1024 · Cited by 376
Anytime Point-Based Approximations for Large POMDPs
Pineau, J., Gordon, G., & Thrun, S. (2006) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2078 · Cited by 370
Stochastic dynamic programming with factored representations
Boutilier, C., Dearden, R., & Goldszmidt, M. (2000) · Artificial Intelligence · doi:10.1016/s0004-3702(00)00033-3 · Cited by 361
Self-citationA Framework for Sequential Planning in Multi-Agent Settings
Gmytrasiewicz, P. J., & Doshi, P. (2005) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1579 · Cited by 360
Reinforcement Learning: A Tutorial Survey and Recent Advances
Gosavi, A. (2009) · INFORMS Journal on Computing · doi:10.1287/ijoc.1080.0305 · Cited by 326
Deliberation for autonomous robots: A survey
Ingrand, F., & Ghallab, M. (2017) · Artificial Intelligence · doi:10.1016/j.artint.2014.11.003 · Cited by 309
Bounded-parameter Markov decision processes
Givan, R., Leach, S., & Dean, T. (2000) · Artificial Intelligence · doi:10.1016/s0004-3702(00)00047-3 · Cited by 308
Self-citationEquivalence notions and model minimization in Markov decision processes
Givan, R., Dean, T., & Greig, M. (2003) · Artificial Intelligence · doi:10.1016/s0004-3702(02)00376-4 · Cited by 308
Self-citationMulti-sensor management for information fusion: issues and approaches
Xiong, N., & Svensson, P. (2002) · Information Fusion · doi:10.1016/s1566-2535(02)00055-6 · Cited by 295
An artificial intelligence perspective on autonomic computing policies
Kephart, J. O., & Walsh, W. E. (2004) · Proceedings. Fifth IEEE International Workshop on Policies for Distributed Systems and Networks, 2004. POLICY 2004. · doi:10.1109/policy.2004.1309145 · Cited by 291
Optimal and Approximate Q-value Functions for Decentralized POMDPs
Oliehoek, F. A., Spaan, M. T. J., & Vlassis, N. (2008) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2447 · Cited by 265
Complex system reliability modelling with Dynamic Object Oriented Bayesian Networks (DOOBN)
Weber, P., & Jouffe, L. (2006) · Reliability Engineering & System Safety · doi:10.1016/j.ress.2005.03.006 · Cited by 258
An object-oriented representation for efficient reinforcement learning
Diuk, C., Cohen, A., & Littman, M. L. (2008) · Proceedings of the 25th international conference on Machine learning - ICML '08 · doi:10.1145/1390156.1390187 · Cited by 226
Efficient Solution Algorithms for Factored MDPs
Guestrin, C., Koller, D., Parr, R., & Venkataraman, S. (2003) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1000 · Cited by 169
(2007) · National Conference on Artificial Intelligence · Cited by 98
An online POMDP algorithm for complex multiagent environments
Paquet, S., Tobin, L., & Chaib-draa, B. (2005) · Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems · doi:10.1145/1082473.1082620 · Cited by 92
A basic model for proactive event-driven computing
Engel, Y., Etzion, O., & Feldman, Z. (2012) · Proceedings of the 6th ACM International Conference on Distributed Event-Based Systems · doi:10.1145/2335484.2335496 · Cited by 67
Measuring the Distance Between Finite Markov Decision Processes
(2016) · Adaptive Agents and Multi-Agents Systems · doi:10.5555/2936924.2936994 · Cited by 47
Prinzie, A., & Van den Poel, D. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-00399-8_11 · Cited by 6
Metadata
- Authors
- Boutilier, C., Dean, T., & Hanks, S.
- Venue
- Journal of Artificial Intelligence Research
- Publisher
- AI Access Foundation
- Published
- 1999-07-01
- Volume
- 11
- Pages
- 1-94
- ISSN
- 1076-9757 (ISSN-L)
- OpenAlex
- W2061504687
- Cited by
- 1,074
- References
- 133
- FWCI
- 54.12
- Type
- journal article
- Language
- en
- Open access
- diamond
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.