Approximately Optimal Monitoring of Plan Preconditions

Monitoring plan preconditions can allow for replanning when a precondition fails, generally far in advance of the point in the plan where the precondition is relevant. However, monitoring is generally costly, and some precondition failures have a very small impact on plan quality. We formulate a model for optimal precondition monitoring, using partially-observable Markov decisions processes, and describe methods for solving this model effectively, though approximately. Specifically, we show that the single-precondition monitoring problem is generally tractable, and the multiple-precondition monitoring policies can be effectively approximated using single-precondition solutions. 1 Introduction Uncertainty in planning problems is often handled by modeling the problem deterministically---enabling classical planning techniques to be used---but using methods for execution monitoring and replanning to handle situations that arise when the plan fails (e.g., when a precondition...