Trading Plan Cost for Timeliness in Situated Temporal Planning

Shahaf Shperberg, Andrew Coles, Erez Karpas, Eyal Shimony, Wheeler Ruml

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

4 Citations (Scopus)

Abstract

If a planning agent is considering taking a bus,for example, the time that passes during its planning can affect the feasibility of its plans, as the bus may depart before the agent has found a complete plan. Previous work on this situated temporal planning setting proposed an abstract deliberation scheduling scheme for maximizing the probability of finding a plan that is still feasible at the time it is found. In this paper, we extend the deliberation scheduling approach to address problems in which plans can differ in their cost. Like the planning deadlines, these costs can be uncertain until a complete plan has been found. We show that finding a deliberation policy that minimizes expected cost is PSPACE-hard and that even for known costs and deadlines the optimal solution is a contingent, rather than sequential, schedule. We then analyze special cases of the problem and use these results to propose a greedy scheme that considers both the uncertain deadlines and costs. Our empirical evaluation shows that the greedy scheme performs well in practice on a variety of problems, including some generated from planner search trees.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20)
Pages4176-4182
ISBN (Electronic)978-0-9992411-6-5
DOIs
Publication statusPublished - 14 Jul 2020

Fingerprint

Dive into the research topics of 'Trading Plan Cost for Timeliness in Situated Temporal Planning'. Together they form a unique fingerprint.

Cite this