Trading Plan Cost for Timeliness in Situated Temporal Planning

Shahaf S. Shperberg, Andrew Coles, Erez Karpas, Solomon Eyal Shimony, Wheeler RumlIJCAI 2020 · DOI

TL;DR

This paper tackles the challenge of AI agents making plans in real-time, where the planning process itself consumes time and can invalidate potential plans. They introduce a new framework that balances finding a timely plan with minimizing its cost, developing a novel greedy algorithm (DAG) that significantly outperforms previous methods in empirical evaluations.

What Problem Does This Paper Address?

Imagine an AI agent needing to book a bus ticket. While the agent is busy searching for the best ticket (e.g., cheapest, most convenient), time is ticking away in the real world. The bus might depart before the agent even finishes its search, rendering its "plan" useless. This is the core problem of "situated temporal planning." Previous work focused on maximizing the chance of finding a timely plan. However, real-world scenarios often involve a trade-off: a slightly later but cheaper plan might be preferable to a slightly earlier but much more expensive one, or even a plan that's so expensive it's effectively undesirable. This paper addresses this gap by incorporating plan cost into the decision-making process, alongside timeliness.

Methods

The authors extend a previous model (AE2) to a new Markov Decision Process (MDP) called ACE2, which explicitly accounts for plan costs. They formalize the problem as finding a policy that minimizes the expected cost of a timely plan.

  • Formalization: They model the problem as a discrete-time MDP (DACE2) where the state includes the current time and the computation time allocated to each potential plan-finding process. Actions involve allocating more computation time to a process or executing a completed plan.
  • Complexity Analysis: They prove that optimally solving ACE2 is PSPACE-hard, meaning it's computationally very difficult, even for simplified versions. This suggests that optimal solutions are likely infeasible for practical problems.
  • Special Case Analysis: They analyze a simplified scenario with only one incomplete process and several pre-computed plans. This analysis provides insights into optimal stopping strategies.
  • Greedy Algorithm (DAG): Based on the insights from the special case, they develop a greedy algorithm called Delay-Aware Greedy (DAG). DAG prioritizes processes based on a criterion that balances the immediate reward (cost reduction) with the potential future loss incurred by delaying the decision. This criterion considers both the "return gain rate" and how much that rate degrades over time.

Datasets

The paper does not introduce new datasets. Instead, they use benchmark problems generated with various distributions for deadlines and costs:

  • Uniform (U): Minimal and maximal range values drawn uniformly.
  • Boltzmann (B): Truncated exponential distribution.
  • Truncated Normal (N): Normal distribution with specified mean and standard deviation.
  • Planner (P): Distributions derived from actual search trees of the OPTIC planner on Robocup Logistics League domain problems. This is a notable aspect, as it uses real-world planner behavior to generate benchmarks.

Key Insights and Ideas

  • Cost vs. Timeliness is a Fundamental Trade-off: The paper clearly demonstrates that balancing plan cost and timeliness is crucial for realistic situated planning, moving beyond just maximizing success probability.
  • Optimal Policies Can Be Contingent: Even when deadlines and costs are known, the optimal strategy isn't always a simple, linear sequence of actions. It can depend on the outcomes of previous steps, making it a "contingent" schedule. This is a significant departure from simpler models.
  • PSPACE-Hardness Implies Need for Heuristics: The theoretical complexity of the problem (PSPACE-hard) strongly suggests that finding optimal solutions is impractical. This justifies the development of efficient greedy heuristics like DAG.
  • Delay-Awareness is Key: The DAG algorithm's success stems from its explicit consideration of how delaying a decision impacts future opportunities and costs, not just the immediate gain.

Key Results

  • DAG Outperforms Baselines: The DAG algorithm consistently achieved lower average costs across various benchmark distributions compared to other algorithms, including P-Greedy (the previous state-of-the-art for timeliness-only planning) and simpler strategies like Random and Round-Robin.
  • Near-Optimal Performance: For small instances where the optimal MDP solution was computationally feasible, DAG's performance was very close to optimal.
  • Efficiency: While DAG was the slowest among the non-MDP algorithms, its metareasoning runtime was still orders of magnitude faster than solving the full MDP and typically under 1 second, making it practical for real-time applications.
  • Parameter Sensitivity: The paper notes that the performance of DAG depends on a parameter ($\gamma$) that balances immediate reward and future loss. Values of $\gamma=0.5$ and $\gamma=1$ were found to be the best performers in their experiments.

Limitations and Future Work

  • Independence Assumption: The theoretical analysis and the DAG algorithm rely on the assumption that deadlines and costs are independent. The paper acknowledges that dependencies complicate the problem significantly (making it PSPACE-hard even with independence). Future work could explore methods to handle these dependencies.
  • Implicit Distributions: While the paper uses explicit distributions for benchmarks, real-world scenarios might involve implicitly defined distributions (e.g., from ongoing search). The paper suggests that DAG can be optimized for such cases by focusing on specific points of interest rather than all possible time values.
  • Generalization to Other Domains: The current work focuses on planning with unknown deadlines and costs. Future research could extend this to other aspects of situated planning, such as uncertainty in action outcomes or more complex temporal constraints.
  • On-the-fly Statistics: The paper mentions that for practical planner integration, statistics like those used in the Planner (P) benchmarks would need to be generated "on-the-fly," which is a direction for future implementation and evaluation.

Summary updated

BibTeX
@inproceedings{shperberg2020trading,
  author = {Shahaf S. Shperberg and Andrew Coles and Erez Karpas and Solomon Eyal Shimony and Wheeler Ruml},
  title = {{Trading Plan Cost for Timeliness in Situated Temporal Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/577},
}
Figure