A Compilation Based Approach to Finding Centroids and Minimum Covering States in Planning

Abstract

In some scenarios, an agent may want to prepare for achieving one of several possible goals, by reaching some state which is close (according to some metric) to all possible goals. Recently, this task was formulated as finding centroids (which minimize the average distance to the goals) or minimum covering states (which minimize the maximum distance). In this paper, we present a compilation based approach for finding such states. Our compilation is very similar to the one used to find the worst case distinctiveness (wcd) in goal recognition design (GRD), and is orders of magnitude faster than the previous state-of-the-art, which was based on exhaustive search.