Domain-Independent Deceptive Planning

We investigate deceptive planning, the problem of generating a plan such that an observer is unable to determine its ultimate goal. Most work in this area has focused on path and/or motion planning. However planning problems can be quite varied and challenging. We present domain-independent approaches for deceptive plan generation utilising the concepts of landmarks, centroids, and minimum covering states. We introduce new, domain-independent metrics to evaluate a plan's deceptivity as a ratio between its deceptive quantity and cost; and we extensively evaluate the performance of our proposed approaches over widely different planning domains providing guidelines as to when to use each approach.