Planning with Dynamically Estimated Action Costs
Eyal Weiss, Gal A. Kaminka
- Planning is a subfield of artificial intelligence that relies on a model based approach for generating action plans for agents.
- There are currently two approaches for the modeling aspect of planning problems: either use fully specified declarative action models or rely on external action simulators. Neither approach takes into account the run time of accessing/acquiring the action models. Additionally, both approaches assume exact action costs are known.
- We propose to acquire estimates of action costs dynamically (i.e., during the planning phase), which allows the planner to trade-off model uncertainty vs. computational effort, thus offering a scalable&reliable approach for using data-driven models.
- A novel planning problem definition:
- Cost estimators as runnable procedures.
- User-supplied target sub-optimality.
- A novel graph-search algorithm (ASEC):
- ASEC is sound and also complete under special circumstances. General completeness can be obtained when using ASEC within an iterative framework.
- Extensive experiments conducted on 6600 modified planning problems based on international planning benchmarks demonstrate considerable savings:
- ASEC tightly meets target sub-optimality without wasting resources:
Accepted for publication in ICAPS'22 Workshop on Reliable Data-Driven Planning and Scheduling
- Eyal’s research is supported by Adams Fellowship and Bar-Ilan’s President Scholarship.
- Gal’s research is supported by an NSF-BSF research grant and industry funding.
- Our results provide empirical support for the efficacy of using dynamically estimated action costs.
- Future work aims to expand the approach for other aspects of dynamic modeling.