Premium
The LP/POMDP marriage: Optimization with imperfect information
Author(s) -
Yost Kirk A.,
Washburn Alan R.
Publication year - 2000
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(200012)47:8<607::aid-nav1>3.0.co;2-f
Subject(s) - partially observable markov decision process , markov decision process , computer science , perfect information , mathematical optimization , observable , set (abstract data type) , operations research , dual (grammatical number) , plan (archaeology) , control (management) , sequence (biology) , action (physics) , scale (ratio) , linear programming , markov chain , markov process , mathematical economics , markov model , artificial intelligence , mathematics , algorithm , machine learning , statistics , art , history , literature , archaeology , genetics , biology , quantum mechanics , programming language , physics
A new technique for solving large‐scale allocation problems with partially observable states and constrained action and observation resources is introduced. The technique uses a master linear program (LP) to determine allocations among a set of control policies, and uses partially observable Markov decision processes (POMDPs) to determine improving policies using dual prices from the master LP. An application is made to a military problem where aircraft attack targets in a sequence of stages, with information acquired in one stage being used to plan attacks in the next. © 2000 John Wiley & Sons, Inc., Naval Research Logistics 47: 607–619, 2000