Learning Action Strategies for Planning Domains

By Roni Khardon. 1999

Abstract This paper reports on experiments where techniques of supervised machine learning are applied to the problem of planning. The input to the learning algorithm is composed of a description of a planning domain, planning problems in this domain, and solutions for them. The output is an efficient algorithm—a strategy—for solving problems in that domain. We test the strategy on an independent set of planning problems from the same domain, so that success is measured by its ability to solve complete problems. A system, L2A ct , has been developed in order to perform these experiments. We have experimented with the blocks world domain and the logistics transportation domain, using strategies in the form of a generalisation of decision lists. The condition of a rule in the decision list is an existentially quantified first order expression, and each such rule indicates which action to take when the condition is satisfied. The learning algorithm is a variant of Rivest's (1987) algorithm, improved with several techniques that reduce its time complexity. The experiments demonstrate that the approach is feasible, and generalisation is achieved so that unseen problems can be solved by the learned strategies. Moreover, the learned strategies are efficient, the solutions found by them are competitive with those of known heuristics for the domains, and transfer from small planning problems in the examples to larger ones in the test set is exhibited.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Learning First-Order Symbolic Representations for Planning from the Structure of the State Space (2019, methodology): “Inductive logic programming methods [31] have been used for learning general policies but from symbolic encodings too [23, 28, 14].”
A review of generalized planning (2019, background): “Another example are generalized policies, whose rules contain variables to be unified with the current state [48].”
Learning Generalized Policies from Planning Examples Using Concept Languages (2004, background): “Building on the work of Khardon [6], we have presented a representation for generalized policies based on a concept language and have shown through a number of experiments in the blocks-world that the new representation appears to produce better policies with less training data and no background kno”
Action Schema Networks: Generalised Policies with Deep Learning (2017, background): “eralised policies are a topic of interest in machine learning for planning (Zimmerman and Kambhampati 2003; Jim´enez et al. 2012). The earliest work in this area expressed policies as decision lists (Khardon 1999), but these were insufﬁciently expressive to directly capture recursive properties, and”
Generalizing plans to new environments in relational MDPs (2003, background): “Methods in deterministic planning have focused o n generalizing from compactly described policies learned fr om many domains to incrementally build a first-order policy [9; 11].”
Approximate Policy Iteration with a Policy Language Bias (2003, background): “Recent work on inductive policy selection in relational planning domai ns [ 17 , 19, 28], has shown that useful policies can be learned using a policy-space bias, de scribed by a generic knowledge representation language.”
Training Deep Reactive Policies for Probabilistic Planning Problems (2018, methodology): “An important exception is the prior work on learning reactive policies in the form of relational rule lists for deterministic STRIPS domains (Khardon 1999).”
Learning Generalized Reactive Policies using Deep Neural Networks (2017, unknown): “The works of Khadron (Khardon 1999), Martin and Geffner (Martín and Geffner 2004), and Yoon et al. (Yoon, Fern, and Givan 2002) learn policies represented as decision lists on the logical problem representation, which needs to be hand speciﬁed.”