Monterey, California. Naval Postgraduate School
Solution of large-scale allocation problems with partially observable outcomes
Abstract
dc:description.abstractWe 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.
Degree
thesis:*- Name thesis:degree_name
- Ph.D in Operations Research
- Level thesis:degree_level
- Doctoral
- Discipline thesis:degree_discipline
- Operations Research
- Department dc:contributor.department
- Department of Operations Research
- Grantor dc:publisher
- Monterey, California. Naval Postgraduate School
- Year dc:date.issued
- 1998
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Yost, Kirk A.
- Advisors dc:contributor.advisor
-
- Washburn, Alan R.
- Owen, Guillermo
Rights
dc:rights- Statement dc:rights
-
- This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
- Approved for public release; distribution is unlimited.
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/10945/8979