Trading Plan Cost for Timeliness in Situated Temporal Planning

Trading Plan Cost for Timeliness in Situated Temporal Planning

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

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 4176-4182. https://doi.org/10.24963/ijcai.2020/577

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.
Keywords:
Planning and Scheduling: Temporal and Hybrid planning
Heuristic Search and Game Playing: Meta-Reasoning and Meta-heuristics