Approximate POMDP Solutions
In practice, POMDPs are often computationally intractable to solve exactly, so computer scientists have developed methods that approximate solutions for POMDPs.
Grid-based algorithms comprise one approximate solution technique. In this approach, the value function is computed for a 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, 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.
Read more about this topic: Partially Observable Markov Decision Process
Famous quotes containing the words approximate and/or solutions:
“A worker may be the hammer’s master, but the hammer still prevails. A tool knows exactly how it is meant to be handled, while the user of the tool can only have an approximate idea.”
—Milan Kundera (b. 1929)
“The anorexic prefigures this culture in rather a poetic fashion by trying to keep it at bay. He refuses lack. He says: I lack nothing, therefore I shall not eat. With the overweight person, it is the opposite: he refuses fullness, repletion. He says, I lack everything, so I will eat anything at all. The anorexic staves off lack by emptiness, the overweight person staves off fullness by excess. Both are homeopathic final solutions, solutions by extermination.”
—Jean Baudrillard (b. 1929)