NICOP - Planning under Uncertainty with Factored Actions
Abstract
We propose to investigate methods for solving Markov decision processes (MDP) with largefactored action spaces, using determinizati"on and reduction to maximum a posteriori probability(MAP) problems in Markov random fields. MDPs with large factored action spaces" can be usedto model applications such as multi-agent search and rescue operations, fleet management inlogistics, and agent coordi"nation in games. The very large number of combined actions forthese problems (easily exceeding trillions of actions at every time step) prevents mostsystematic search and optimization techniques from being used. By using determinization andreduction to Markov r"andom fields, we are able to exploit relaxations to linear programming thatcan be scaled to very large problems using message-passi"ng on Markov random fields. Theserelaxations can also be iteratively tightened by the addition of violated constraints to createan"ytime algorithms. Through the use of systematic optimization, instead of heuristics and adhoccombination of techniques, we hope to"" be able to obtain improved techniques for solvingmany problems that can be modelled by these MDPs; if successful, these advances w"ill bedisseminated through conference/journal publications and open source software release.Relevance to ONR: The applications ena"bled by the research program are common withinRobotics and Autonomous Systems, one of Basic Research area of primary interest to th"eMarine Corps (2012 US Marine Corps S&T Strategic Plan).
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Dec 20, 2017
- Source ID
- N629091812023
Entities
People
- Wee Sun Lee
Organizations
- National University of Singapore
- Office of Naval Research
- United States Navy