Selecting goals in oversubscription planning using relaxed plans Articles uri icon

publication date

  • February 2021

start page

  • 1

end page

  • 24

volume

  • 291

International Standard Serial Number (ISSN)

  • 0004-3702

Electronic International Standard Serial Number (EISSN)

  • 1872-7921

abstract

  • Planning deals with the task of finding an ordered set of actions that achieves some goals from an initial state. In many real-world applications it is unfeasible to find a plan achieving all goals due to limitations in the available resources. A common case consists of having a bound on a given cost measure that is less than the optimal cost needed to achieve all goals. Oversubscription planning (OSP) is the field of Automated Planning dealing with such kinds of problems. Usually, OSP generates plans that achieve only a subset of the goals set. In this paper we present a new technique to a priori select goals in no-hard-goals satisficing OSP by searching in the space of subsets of goals. A key property of the proposed approach is that it is planner-independent once the goals have been selected; it creates a new non-OSP problem that can be solved using off-the-shelf planners. Extensive experimental results show that the proposed approach outperforms state-of-the-art OSP techniques in several domains of the International Planning Competition.

subjects

  • Computer Science

keywords

  • automated planning; oversubscription planning; partial satisfaction planning; satisficing planning