Conference Proceeding Article
Agents or agent teams deployed to assist humans often face the challenges of monitoring the state of key processes in their environment (including the state of their human users themselves) and making periodic decisions based on such monitoring. POMDPs appear well suited to enable agents to address these challenges, given the uncertain environment and cost of actions, but optimal policy generation for POMDPs is computationally expensive. This paper introduces three key techniques to speedup POMDP policy generation that exploit the notion of progress or dynamics in personal assistant domains. Policy computation is restricted to the belief space polytope that remains reachable given the progress structure of a domain. We introduce new algorithms; particularly one based on applying Lagrangian methods to compute a bounded belief space support in polynomial time. Our techniques are complementary to many existing exact and approximate POMDP policy generation algorithms. Indeed, we illustrate this by enhancing two of the fastest existing algorithms for exact POMDP policy generation. The order of magnitude speedups demonstrate the utility of our techniques in facilitating the deployment of POMDPs within agents assisting human users.
meeting rescheduling, task allocation, partially observable markov decision process (POMDP)
Artificial Intelligence and Robotics | Business | Operations Research, Systems Engineering and Industrial Engineering
Intelligent Systems and Decision Analytics
AAMAS '05: The fourth International Joint Conference on Autonomous Agents and Multi Agent Systems, Utrecht University, the Netherlands, July 25-29, 2005
City or Country
VARAKANTHAM, Pradeep; Maheswaran, Rajiv; and Tambe, Milind.
Exploiting Belief Bounds: Practical POMDPs for Personal Assistant Agents. (2005). AAMAS '05: The fourth International Joint Conference on Autonomous Agents and Multi Agent Systems, Utrecht University, the Netherlands, July 25-29, 2005. 978-985. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/938
Copyright Owner and License
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.