Greedy Coverage of Incomplete Planning Domain Interpretations by t-strength Diagnoses

Abstract

In this work, we present a greedy algorithm for covering the set of incomplete STRIPS planning domain interpretations by $t$-strength diagnoses. We present a greedy algorithm to cover the incomplete domain model interpretations with a set of plans by iteratively generating plans so that each additional plan is biased to cover at least one new interpretation not previously covered. We also present a second greedy algorithm to construct a set of plans that covers all $t$-strength diagnoses of plan failure for plans in the incomplete domain model. We show that covering domain interpretations by $t$-strength diagnoses leads to increased coverage by a set of plans despite potentially lower coverage per plan because covering by $t$-strength diagnoses leads to a more scalable approach to planning where more plans can be found.