Partially Observable<scp>MDPs</scp>(<scp>POMDPS</scp>): Introduction and Examples
Wiley Encyclopedia of Operations Research and Management SciencePublished 1 January 2011
Emine Yaylalı, Julie S. Ivy
Citations6
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
POMDPs are introduced and the relationship between Markov models and PomDPs is discussed and a wide range of POMDP applications from the literature are presented.
Abstract
Abstract A partially observable Markov decision process (POMDP) is a generalization of a Markov decision process where the states of the model are not completely observable by the decision maker. Noisy observations provide a belief regarding the underlying state, while the decision maker has some control over the progression of the model through the selection of actions. In this article, we introduce POMDPs and discuss the relationship between Markov models and POMDPs. A general POMDP formulation and a wide range of POMDP applications from the literature are also presented.
Keywords
Computer Science
Wiley series in probability and statisticsMarkov Decision Processes
5,868 Citations1994Martin L. Puterman
Artificial IntelligencePlanning and acting in partially observable stochastic domains
4,129 Citations1998Leslie Pack Kaelbling, Michael L. Littman +1 more
A novel algorithm for solving pomdps off line and how, in some cases, a finite-memory controller can be extracted from the solution to a POMDP is outlined.
Operations ResearchThe Optimal Control of Partially Observable Markov Processes over a Finite Horizon
1,499 Citations1973Richard D. Smallwood, Edward J. Sondik
If there are only a finite number of control intervals remaining, then the optimal payoff function is a piecewise-linear, convex function of the current state probabilities of the internal Markov process, and an algorithm for utilizing this property to calculate the optimal control policy and payoff function for any finite horizon is outlined.
Computer Speech & LanguagePartially observable Markov decision processes for spoken dialog systems
876 Citations2006J. D. Williams, Steve Young
This paper cast a spoken dialog system as a partially observable Markov decision process (POMDP) and shows how this formulation unifies and extends existing techniques to form a single principled framework.
Theory of Probability and Its ApplicationsOn Optimum Methods in Quickest Detection Problems
845 Citations1963Albert N. Shiryaev
In this paper optimum methods are developed for observing a process (1), in which the moment when a “disorder” $\theta$ appears is not known, and the basic quantity characterizing the quality of this observation method is the mean time delay for detection of a disorder.
Management ScienceState of the Art—A Survey of Partially Observable Markov Decision Processes: Theory, Models, and Algorithms
745 Citations1982George E. Monahan
A wide range of models in such areas as quality control, machine maintenance, internal auditing, learning, and optimal stopping are discussed within the POMDP-framework.
Naval Research Logistics QuarterlyA survey of maintenance models: The control and surveillance of deteriorating systems
690 Citations1976William P. Pierskalla, John A. Voelker
The literature on maintenance models is surveyed and includes models which involve an optimal decision to procure, inspect, and repair and/or replace a unit subject to deterioration in service.
Annals of Operations ResearchA survey of algorithmic methods for partially observed Markov decision processes
544 Citations1991William S. Lovejoy
Several approximation methodologies are reviewed that have the potential to generate computationally feasible, high precision solutions for solving discrete-time, finite POMDPs over both finite and infinite horizons.
Journal of Artificial Intelligence ResearchValue-Function Approximations for Partially Observable Markov Decision Processes
536 Citations2000Miloš Hauskrecht
This work surveys various approximation methods, analyzes their properties and relations and provides some new insights into their differences, and presents a number of new approximation methods and novel refinements of existing techniques.
European Journal of Operational ResearchMarkov decision processes
414 Citations1989Chelsea C. White, Douglas J. White
This review presents an overview of theoretical and computational results, applications, several generalizations of the standard MDP problem formulation, and future directions for research.
The Annals of Mathematical StatisticsA Bayes Approach to a Quality Control Model
367 Citations1952M. A. Girshick, Herman Rubin
Operations ResearchComputationally Feasible Bounds for Partially Observed Markov Decision Processes
310 Citations1991William S. Lovejoy
This paper explains how to approximate the state space by a finite grid of points, and use that grid to construct upper and lower value function bounds, generate approximate nonstationary and stationary policies, and bound the value loss relative to optimal for using these policies in the decision problem.
Spoken dialogue management using probabilistic reasoning
290 Citations2000Nicholas Roy, Joëlle Pineau +1 more
This work uses a Partially Observable Markov Decision Process (POMDP)-style approach to generate dialogue strategies by inverting the notion of dialogue state; the state represents the user's intentions, rather than the system state.
Artificial Intelligence in MedicinePlanning treatment of ischemic heart disease with partially observable Markov decision processes
171 Citations2000Miloš Hauskrecht, Hamish Fraser
This paper shows how the POMDP framework can be used to model and solve the problem of the management of patients with ischemic heart disease (IHD), and demonstrates the modeling advantages of the framework over standard decision formalisms.
Operations ResearchAssessing Dynamic Breast Cancer Screening Policies
164 Citations2008Lisa M. Maillart, Julie S. Ivy +2 more
It is concluded that, in general, to efficiently achieve a lifetime risk comparable to the current risk among U.S. women, screening should start relatively early in life and continue relatively late in life regardless of the screening interval(s) adopted.
Annals of Operations ResearchA survey of solution techniques for the partially observed Markov decision process
163 Citations1991Chelsea C. White
Several computational procedures presented are convergence accelerating variants of, or approximations to, the Smallwood-Sondik algorithm, which generalizes the standard, completely observed Markov decision process, and new research directions involving heuristic search.
International Journal of Production ResearchOptimal condition based maintenance with imperfect information and the proportional hazards model
122 Citations2006Alireza Ghasemi, Soumaya Yacout +1 more
Journal of Mathematical PsychologyA tutorial on partially observable Markov decision processes
119 Citations2009Michael L. Littman
The purpose of this article is to introduce the POMDP model to behavioral scientists who may wish to apply the framework to the problem of understanding normative behavior in experimental settings.
IIE TransactionsMaintenance policies for systems with condition monitoring and obvious failures
117 Citations2006Lisa M. Maillart
This work examines the problem of adaptively scheduling observations and preventive maintenance actions for a multistate, Markovian deterioration system with obvious failures, such that the long-run average-cost per unit time is minimized.
Operations ResearchMarkovian Deterioration with Uncertain Information
106 Citations1976Donald B. Rosenfield
Under the assumptions that the transition matrix representing the process is upper-triangular and totally positive of order two, it is shown that the state-space can be broken up into at most four regions of action and that the optimal region of repair is of a special intuitive type.
Operations ResearchA Simple Model of Search for a Moving Target
101 Citations1970Stephen M. Pollock
Empirical equations are given that characterize the minimum expected number of looks to detect the target, and the maximum probability of detecting the target within a given number of look.
Operations ResearchOptimum Maintenance with Incomplete Information
96 Citations1968James E. Eckles
The maintenance of a system characterized by a discrete-parameter, non-stationary, finite-state Markov process is considered and the action that minimizes the discounted value of expected immediate and future costs assuming optimum future actions is determined by the system's age and the posterior distribution over the states.
Management ScienceA Markov Quality Control Process Subject to Partial Observation
90 Citations1977Chelsea C. White
Several results associated with observation quality are determined which are sufficient for particularly simple characterizations of an optimal policy for the two-state case and generalizations of several results due to Ross are presented.
European Journal of Operational ResearchOptimal adaptive control policy for joint machine maintenance and product quality control
78 Citations2004Yarlin Kuo
This paper studies the joint machine maintenance and product quality control problem of a finite horizon discrete time Markovian deteriorating, state unobservable batch production system and formulate the system as a partially observable Markov decision process and derive some properties of the optimal value function.
Operations ResearchStructural Results for Partially Observable Markov Decision Processes
73 Citations1979S. Christian Albright
Monotonicity results for a fairly general class of partially observable Markov decision processes when there are only two actual states and when the actions taken are primarily intended to improve the system, rather than to inspect it are examined.
Journal of the Operational Research SocietyOptimal Inspection and Repair of a Production Process Subject to Deterioration
68 Citations1978Chelsea C. White
Operations ResearchA Partially Observable Model of Decision Making by Fishermen
67 Citations1989Daniel E. Lane
This paper presents an application of a partially observable Markov decision process for the intraseasonal decisions of fishing vessel operators and may be used as a decision aid in the regulation of the common property fisheries resource.
International Journal of Systems ScienceOptimal control-limit strategies for a partially observed replacement problem†
67 Citations1979Chelsea C. White
IIE TransactionsSimultaneous optimization of [Xbar] control chart and age-based preventive maintenance policies under an economic objective
58 Citations2007Thomas G. Yeung, C. Richard Cassady +1 more
Operations ResearchComparison of Some Suboptimal Control Policies in Medical Drug Therapy
52 Citations1996Chuanpu Hu, William S. Lovejoy +1 more
This paper defines some tractable policies for adaptive control of drug concentrations in compartment models and compares their performances using computer simulation in a one-compartment model and addresses the topic of actively versus passively learning.
Journal of Accounting ResearchOptimal Investigation Strategies with Imperfect Information
48 Citations1969Robert S. Kaplan
Active gesture recognition using partially observable Markov decision processes
48 Citations1996Trevor Darrell, Alex Pentland
A foveated gesture recognition system that guides an active camera to foveate salient features based on a reinforcement learning paradigm and uses a new multiple-model Q-learning formulation.
Quality and Reliability Engineering InternationalA Modeling Approach to Maintenance Decisions Using Statistical Quality Control and Optimization
47 Citations2005Julie S. Ivy, Harriet Black Nembhard
A methodology for maintenance decision making for deteriorating systems under conditions of uncertainty that integrates statistical quality control (SQC) and partially observable Markov decision processes (POMDPs) is presented and simulation is used to develop realistic maintenance policies for real-world environments.
IEEE Transactions on Automatic ControlDynamic file assignment in a computer network
44 Citations1976A. Segall
A separation theorem between estimation of the rates and the optimal control is proven, similar to Wonham's separation theorem for linear Gaussian models.
Computer Speech & LanguageEnvironment adaptation for robust speaker verification by cascading maximum likelihood linear regression and reinforced learning
42 Citations2006Ka Fai Cedric Yiu, Man‐Wai Mak +1 more
Experimental results based on 150 speakers of the HTIMIT corpus show that environment adaptation based on the combination of MLLR, reinforced learning and feature transformation outperforms CMS, Hnorm, Tnorm, and speaker model synthesis.
Journal of Mathematical PsychologyThe analysis of economic teaching strategies for a simple learning model
34 Citations1971Richard D. Smallwood
It is proved that the optimum policy for a multi-item list can be calculated by considering each item individually and then aggregating the individual results into a total policy.
IEEE Transactions on ReliabilityMarginally Monotonic Maintenance Policies for a Multi-State Deteriorating Machine With Probabilistic Monitoring, and Silent Failures
34 Citations2005Julie S. Ivy, Stephen M. Pollock
It is proved that the policy that minimizes the total expected cost of system maintenance has a "marginally monotonic" structure.
Naval Research Logistics (NRL)An optimal structured policy for maintenance of partially observable aircraft engine components
34 Citations1998Wallace J. Hopp, Yar-Lin Kuo
This paper incorporates stress information collected via sensors into the scheduling decision process by means of a partially observable Markov decision process model, and demonstrates the optimality of structured maintenance policies, which support practical maintenance schedules.
Operations ResearchToward an Integrated Methodology for the Analysis of Health-Care Systems
30 Citations1971Richard D. Smallwood, Edward J. Sondik +1 more
Journal of Mathematical PsychologyOptimal stimulus presentation strategy for a stimulus sampling model of learning
29 Citations1966William Karush, Robert E. Dear
Naval Research Logistics QuarterlyBounds on optimal cost for a replacement problem with partial observations
28 Citations1979Chelsea C. White
Naval Research Logistics (NRL)Multiaction maintenance under markovian deterioration and incomplete state information
25 Citations1988Wallace J. Hopp, Sung-Chi Wu
This work models the replacement problem under incomplete state information and derives structural results concerning the optimal maintenance policy, and shows a specific structure, consisting of monotonic waiting times and constant maintenance actions, to be optimal.
Journal of Applied ProbabilityComputing optimal quality control policies — two actions
25 Citations1976Robert C. Wang
Journal of Applied ProbabilityOptimal replacement policy with unobservable states
22 Citations1977Robert C. Wang
Journal of Applied ProbabilityOptimal replacement policy with unobservable states
22 Citations1977Robert C. Wang
Information and ControlOptimal diagnostic questionnaires which allow less than truthful responses
13 Citations1976Chelsea C. White
When answers to questions are not necessarily truthful, a charge per question of the channel capacity of the associated channel and an appropriate terminal charge are shown to imply that the average cost of a questionnaire is bounded below by the Shannon entropy of a given a priori density, thus further exploring the relationship between optimal diagnostic questioning and information theory.
Journal of Applied ProbabilityComputing optimal quality control policies — two actions
10 Citations1976Robert C. Wang
It is shown that a monotone policy is optimal and how to compute the optimal critical point is shown.