set of points in the belief space, and interpolation is used to determine the optimal action to take for other belief states that are encountered which are not in the set of grid points. More recent work makes use of sampling techniques, generalization techniques and exploitation of problem structure, and has extended POMDP solving into large domains with millions of states. For example, adaptive grids and point-based methods sample random reachable belief points to constrain the planning to relevant areas in the belief space. Dimensionality reduction using PCA has also been explored. Another line of approximate solution techniques for solving POMDPs relies on using (a subset of) the history of previous observations, actions and rewards up to the current time step as a pseudo-state. Usual techniques for solving MDPs based on these pseudo-states can then be used (e.g. Q-learning). Ideally the pseudo-states should contain the most important information from the whole history (to reduce bias) while being as compressed as possible (to reduce overfitting). POMDP theory Planning in POMDP is undecidable in general. However, some settings have been identified to be decidable (see Table 2 in, reproduced below). Different objectives have been considered. Büchi objectives are defined by Büchi automata. Reachability is an example of a Büchi condition (for instance, reaching a good state in which all robots are home). coBüchi objectives correspond to traces that do not satisfy a given Büchi condition (for instance, not reaching a bad state in which some robot died). Parity objectives are defined via parity games; they enable to define complex objectives such that reaching a good state every 10 timesteps. The objective can be satisfied: almost-surely, that is the probability to satisfy the objective is 1; positive, that is the probability to satisfy the objective is strictly greater than 0; quantitative, that is the probability to satisfy the objective is greater than a given threshold. We also consider the finite memory case in which the agent is a finite-state machine, and the general case in which the agent has an infinite memory. Applications POMDPs can be used to model many kinds of real-world problems. Notable applications include the use of a POMDP in management of patients with ischemic heart disease, assistive technology for persons with dementia, the conservation of the critically endangered and difficult to detect Sumatran tigers and aircraft collision avoidance. References External links pomdp: Solver for Partially Observable Markov Decision Processes