A Survey of solution techniques for the partially observed Markov decision process <s> 10. <s> 2-Halomethyl-, 2-alkoxymethyl- and 2-acyloxymethyl-3-methyl-3-formyl-bicyclo[2.2.1]heptane and -hept-5-ene and a process for their preparation. The new compounds are obtained by reacting cyclopentadiene or dicyclopentadiene with the corresponding 4-halo-, 4-alkoxy- or 4-acyloxy-2-methyl-crotonaldehydes under the conventional conditions for Diels-Alder reactions, with or without subsequent catalytic hydrogenation of the Diels-Alder adduct obtained. The new compounds provide an industrially easily realized and advantageous method of synthesis of the sought-after essential ingredients of natural sandalwood oils. <s> BIB001 </s> A Survey of solution techniques for the partially observed Markov decision process <s> 10. <s> Algorithms are developed and analyzed for the solution of a class of problems that can be represented by locally finite graphs in which preferences among solution paths may be described by a transitive binary relation. The basic algorithmic structure of the popular heuristic search algorithm A* and its relatives is generalized using concepts from decision theory to allow for problems not effectively formulated in terms of the standard scalar criterion for directing search. The major motivation for this generalization is the importance of multiobjective problems in which it is often the case that development of a total order over the set of solution paths is neither necessary nor desirable. ::: Relevant background on heuristic search theory and decision theory is presented. A general algorithm for heuristic search using transitive binary relations, referred to as GOZ* for generally ordered Z*, is presented and its formal properties are investigated. Similar to its precursors, A* and Z*, this generalization is found to be complete and admissible under the appropriately adjusted definitions. Other relevant characteristics of the algorithm that are considered include termination, comparison of heuristics, monotonicity, and consistency. Specializations of this general algorithm to the cases of additive multiobjective problems and a linear additive parametric generalization of those problems are presented with the help of several illustrative examples. Implementation issues, computational questions, and extensions related to preferences and search of AND/OR graphs are discussed in the context of future research directions. Pseudo-code for several of the generalized search algorithms is presented in an appendix. <s> BIB002
Heuristic search-A direction for future research Dynamic programming has thus far served as the basis for determining the solution of the POMDP. Another related basis for solution is heuristic search, a subarea of artificial intelligence  . There are two intriguing aspects of heuristic search. First, heuristic search procedures generally assume the existence of a heuristic function, which (if admissible) represents an optimistic estimate (e.g. an upper bound) of the optimal value function and is used to guide the search. Results due to Astrom BIB001  (see also White and Harrington  ) guarantee that a simple extension of the solution of the completely observed MDP represents an easily generated upper bound on the optimal value function of the POMDP. Second, heuristic search procedures guided by simply generated heuristic functions can significantly out-perform dynamic programming; e.g. note the discussion found in  concerned with the application of the heuristic search procedure A* applied to the 8-puzzle. Lark and White  have presented a heuristic search based procedure for solving the finite horizon, completely unobserved MDP (CUMDP). The CUMDP is a POMDP that assumes the P(z, a) are independent of z, for all a. Interest in the CUMDP is due to the fact that a finite horizon version of the CUMDP can be cast as a locally finite, finite depth OR-graph. The specific heuristic search procedure applied is a multiobjective generalization of A* called MPA* BIB002 . (A" is an informed, best-first search procedure for finding an optimal path through an OR-graph from a given start node to a given set of terminal nodes based on a scalar criterion.) Preliminary numerical results show that this heuristic search algorithm can compare quite favorably to the SS algorithm. Extending this line of research to the more general POMDP, which requires the use of an AND/OR-graph, appears to be a promising topic for future research.