# Planning with Dynamically Estimated Action Costs

arXiv: https://arxiv.org/abs/2206.04166 · HTML: https://mlsanity.com/paper/2206.04166/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 32 references that are in the map.
- First posted on arXiv 8 Jun 2022.

## Builds on (most cited first, 6 of 6)

- [Integrated Task and Motion Planning](https://mlsanity.com/paper/2010.01083/) (2020)
- [Generalized Lazy Search for Robot Motion Planning: Interleaving Search and Edge Evaluation via Event-based Toggles](https://mlsanity.com/paper/1904.02795/) (2019)
- [POMDPs Make Better Hackers: Accounting for Uncertainty in Penetration Testing](https://mlsanity.com/paper/1307.8182/) (2013)
- [Efficient Black-Box Planning Using Macro-Actions with Focused Effects](https://mlsanity.com/paper/2004.13242/) (2020)
- [Attack Planning in the Real World](https://mlsanity.com/paper/1306.4044/) (2013)
- [Position Paper: Online Modeling for Offline Planning](https://mlsanity.com/paper/2206.03356/) (2022)

## Abstract (arXiv)

Information about action costs is critical for real-world AI planning applications. Rather than rely solely on declarative action models, recent approaches also use black-box external action cost estimators, often learned from data, that are applied during the planning phase. These, however, can be computationally expensive, and produce uncertain values. In this paper we suggest a generalization of deterministic planning with action costs that allows selecting between multiple estimators for action cost, to balance computation time against bounded estimation uncertainty. This enables a much richer -- and correspondingly more realistic -- problem representation. Importantly, it allows planners to bound plan accuracy, thereby increasing reliability, while reducing unnecessary computational burden, which is critical for scaling to large problems. We introduce a search algorithm, generalizing A^*, that solves such planning problems, and additional algorithmic extensions. In addition to theoretical guarantees, extensive experiments show considerable savings in runtime compared to alternatives.