Current classical planners are very successful in finding (non-optimal) plans, even for large planning instances. To do so, most planners rely on a preprocessing stage that computes a grounded representation of the task. Whenever the grounded task is too big to be generated (i.e., whenever this preprocess fails) the instance cannot even be tackled by the actual planner. To address this issue, we introduce a partial grounding approach that grounds only a projection of the task, when complete grounding is not feasible. We propose a guiding mechanism that, for a given domain, identifies the parts of a task that are relevant to find a plan by using off-the-shelf machine learning methods. Our empirical evaluation attests that the approach is capable of solving planning instances that are too big to be fully grounded. Given a model of the environment, classical planning attempts to find a sequence of actions that lead from an initial state to a state that satisfies a set of goals. Planning models are typically described in the Planning Domain Definition Language (PDDL) BID16 ) in terms of predicates and action schemas with arguments that can be instantiated with a set of objects. However, most planners work on a grounded representation without free variables, like STRIPS BID4 or FDR BID1 . Grounding is the process of translating a task in the lifted (PDDL) representation to a grounded representation. It requires to compute all valid instantiations that assign objects to the arguments of predicates and action parameters, even though only a small fraction of these instantiations might be necessary to solve the task.The size of the grounded task is exponential in the number of arguments in predicates and action schemas. Although this is constant for all tasks of a given domain, and grounding can be done in polynomial time, it may still be prohibitive when the number of objects is large and/or some predicates or actions have many parameters.The success of planners like FF BID9 or LAMA BID24 in finding plans for large planning tasks is undeniable. However, since most planners rely on grounding for solving a task, they fail without even starting the search for a plan whenever an instance cannot be grounded, making grounding a bottleneck for the success of satisficing planners.Grounding is particularly challenging in open multi-task environments, where the planning task is automatically generated with all available objects even if only a few of them are relevant to achieve the goals. For example, in robotics, the planning task may contain all objects with which the robot may interact even if they are not needed BID13 ). In network-security environments, like the one modeled in the Caldera domain BID17 , the planning task may contain all details about the network. However, to the best of our knowledge, no method exists that attempts to focus the grounding on relevant parts of the task.We propose partial grounding, where, instead of instantiating the full planning task, we focus on the parts that are required to find a plan. The approach is sound -if a plan is found for the partially grounded task then it is a valid plan for the original task -but incomplete -the partially grounded task will only be solvable if the operators in at least one plan have been grounded. To do so, we give priority to operators that we deem more relevant to achieve the goal. Inspired by relational learning approaches to domain control knowledge (e.g., BID31 , BID3 , BID11 ), we use machine learning methods to predict the probability that a given operator belongs to a plan. We learn from small training instances, and generalize to larger ones by using relational features in standard classification and regression algorithms (e.g., BID12 ). As an alternative model, we also experiment with relational trees to learn the probabilities BID18 .Empirical results show that our learning models can predict which operators are relevant with high accuracy in several domains, leading to a very strong reduction of task size when grounding and solving huge tasks. In this paper, we proposed an approach to partial grounding of planning tasks, to deal with tasks that cannot be fully grounded under the available time and memory resources. Our algorithm heuristically guides the grounding process giving preference to operators that are deemed most relevant for solving the task. To determine which operators are relevant, we train different machine learning models using optimal plans from small instances of the same domain. We consider two approaches, a direct application of relational decision trees, and using relational features with standard classification and regression algorithms. The empirical results show the effectiveness of the approach. In most domains, the learned models are able to identify which operators are relevant with high accuracy, helping to reduce the number of grounded operators by several orders of magnitude, and greatly increasing coverage in large instances. Figure 3 : The scatter plots show the number of operators of a fully grounded task on the x-axis. The y-axis shows the number of operators that are needed to make the goal reachable in the grounding (leftmost two columns), and the number of operators that are needed to solve the task (rightmost two columns), for several priority functions.
This paper introduces partial grounding to tackle the problem that arises when the full grounding process, i.e., the translation of a PDDL input task into a ground representation like STRIPS, is infeasible due to memory or time constraints.
{"src": "scitldr-AIC_train", "paper_id": "r1e44bPpP4"}