Solution of large-scale allocation problems with partially observable outcomes
By:  Kirk A. Yost
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1998
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 173
Description: We develop methods for optimally solving problems that require allocating scarce resources among activities that either gather information on a set of objects or take actions to change their status. Also, the information we gather on the outcomes of the actions we take may be erroneous. The latter situation is called partial observability, and methodology available prior to this dissertation is combinatorially intractable for problems with more than one object. We use two previously-uncombined methods - linear programming (LP) and partially observable Markov decision processes (POMDPs) - to construct a decomposition procedure to solve the resulting large-scale allocation problem with partially observable outcomes. We show theoretically that this procedure is both optimal and finite; in addition, we develop improvements to the procedure that reduce runtimes on test problems by 95%. We demonstrate the procedure on a small targeting problem with a known analytical solution, as well as a large- scale military example concerned with allocating aircraft sorties, weapons, and bomb-damage assessment sensors to targets. Finally, we develop analytical bounds on the expected objective function values of a related allocation problem with more stringent resource constraints, and present a simulation-based approach to estimate the distributions of the outcomes for that model.
Notes: "September 1998."

Dissertation supervisor(s): Alan R. Washburn.

Dissertation (Ph.D. in Operations Research) Naval Postgraduate School, September 1998.

Includes bibliographical references (p. 165-160).

Approved for public release; distribution unlimited.

Also Available online.

Mode of access: World Wide Web.

System Requirements: Adobe Acrobat reader.

US Air Force (USAF) author.

dk/dk cc:9116 11/4/98.