Accession Number:

ADA355529

Title:

Solution of Large-Scale Allocation Problems with Partially Observable Outcomes

Descriptive Note:

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s):

Report Date:

1998-09-01

Pagination or Media Count:

190.0

Abstract:

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.

Subject Categories:

  • Administration and Management
  • Operations Research
  • Defense Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE