  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.
