Finding Centroids and Minimum Covering States in Planning

Abstract

In automated planning, the most common task consists of finding a plan that achieves a set of goals. In this paper, we focus on a different task; that of finding states that minimize some goal-related metric. First, we present some domains for which that task is useful. Second, we propose two of such types of states: (1) centroid states, which minimize the distance to all the goals in the problem; and (2) minimum covering states, which minimize the maximum distance to any of the goals. Third, we define optimal and suboptimal algorithms to find such states. Finally, we show some experimental results in planning instances from different domains.