Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

1-2007

Abstract

While POMDPs (partially observable markov decision problems) are a popular computational model with wide-ranging applications, the computational cost for optimal policy generation is prohibitive. Researchers are investigating ever-more efficient algorithms, yet many applications demand such algorithms bound any loss in policy quality when chasing efficiency. To address this challenge, we present two new techniques. The first approximates in the value space to obtain solutions efficiently for a pre-specified error bound. Unlike existing techniques, our technique guarantees the resulting policy will meet this bound. Furthermore, it does not require costly computations to determine the quality loss of the policy. Our second technique prunes large tracts of belief space that are unreachable, allowing faster policy computation without any sacrifice in optimality. The combination of the two techniques, which are complementary to existing optimal policy generation algorithms, provides solutions with tight error bounds efficiently in domains where competing algorithms fail to provide such tight bounds.

Discipline

Artificial Intelligence and Robotics | Business | Operations Research, Systems Engineering and Industrial Engineering

Publication

IJCAI '07: Proceedings of the 20th International Joint Conference on Artifical Intelligence: Hyderabad, India, 6-12 January 2007

First Page

2683

Last Page

2643

Publisher

AAAI Press

City or Country

Menlo Park, CA

Additional URL

http://portal.acm.org/citation.cfm?id=1625700

Download

Share

COinS