King's College London

Research portal

Allocating Planning Effort when Actions Expire

Research output: Chapter in Book/Report/Conference proceedingConference paper

Shahaf Shperberg, Andrew Ian Coles, Bence Cserna, Erez Karpas, Wheeler Ruml, Solomon Shimony

Original languageEnglish
Title of host publicationProceedings of the Thirty Third AAAI Conference on Artificial Intelligence
PublisherAAAI Press
StatePublished - 27 Jan 2019

King's Authors

Projects

Abstract

Making plans that depend on external events can be tricky. For example, an agent considering a partial plan that involves taking a bus must recognize that this partial plan is only viable if completed and selected for execution in time for the agent to arrive at the bus stop. This setting raises the thorny problem of allocating the agent's planning effort across multiple open search nodes, each of which has an expiration time and an expected completion effort in addition to the usual estimated plan cost. This paper formalizes this metareasoning problem, studies its theoretical properties, and presents several algorithms for solving it. Our theoretical results include a surprising connection to job scheduling, as well as to deliberation scheduling in time-dependent planning. Our empirical results indicate that our algorithms are effective in practice. This work advances our understanding of how heuristic search planners might address realistic problem settings.

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454