Learning Efficient Logical Robot Strategies Involving Composable Objects

1 Introduction

Commercial robots exist which carry out tasks such as vacuuming a cluttered room [Geringer et al., 2012] or delivering packages [Felder et al., 2003]. However, consider teaching a robot postman to both collect and deliver letters. In the initial state letters are to be collected; in the final state letters have been delivered to their intended destinations (Figure 1). In Section 3 we show that allowing the postman to form composite objects by placing letters in a postbag reduces the resource complexity of the problem from O(n + d) to O(nd), where n is the number of letters and d is the space size.

Example 2

Figure 1: Postman initial/final state examples alongside Prolog representations for a route on a hill. In the initial states letters are to be collected; in the final states letters are at their intended destinations.

However, most logic-based machine learning algorithms rely on an Occamist bias where textual complexity of hypotheses is minimised. Within Inductive Logic Programming [Muggleton et al., 2011] (ILP), this approach fails to distinguish between the efficiencies of hypothesised programs, such as quick sort (O(n log n)) and bubble sort (O(n2 )) 1 . For example, Figure 2 shows two strategies from our experiments (Section 5.2) for the postman problem, where strategy (a) was learned by MetagolD[Muggleton et al., 2015], an existing ILP system and strategy (b) was learned by MetagolO, a new ILP system introduced in Section 4. Although the strategies are equal in textual complexity they differ in their resource complexity 2 because MetagolO minimises both the textual complexity and resource complexity of hypotheses, learning a strategy involving composite objects (i.e. using a postbag), whereas MetagolD only minimises the textual complexity of hypotheses. Clearly, reducing the complexity of such problems and learning efficient strategies for them is of considerable value in similar real-world applications. In Section 5 we show how strategy optimisation can be used to learn classic efficient sorting algorithms as robot strategies.

1 We demonstrate that MetagolO succeeds in learning quick sort in the experiments described in Section 5.3.

2O(nd) vs O(n + d) respectively where n, d are the number of letters and places for delivery.

postman(A,B):- postman2(A,C), postman(C,B). postman(A,B):- postman2(A,C), go to bottom(C,B). postman2(A,B):- postman1(A,C), go to bottom(C,B). postman1(A,B):- find next sender(A,C), take letter(C,B). postman1(A,B):- find next recipient(A,C), give letter(C,B). (a) Inefficient strategy learned by MetagolD

postman(A,B):- postman2(A,C), postman2(C,B). postman2(A,B):- postman1(A,C), postman2(C,B). postman1(A,B):- find next sender(A,C), bag letter(C,B). postman2(A,B):- postman1(A,C), go to bottom(C,B). postman1(A,B):- find next recipient(A,C), give letter(C,B). (b) Efficient strategy learned by MetagolO

This paper extends the recently developed MetaInterpretive Learning (MIL) framework [Lin et al., 2014; Muggleton et al., 2014b]. MIL differs from most state-ofthe-art ILP approaches by supporting the use of predicate invention for problem decomposition and the learning of recursive programs. MIL has [Muggleton et al., 2015] been shown to be capable of learning a simple robot strategy for building a stable wall from a small set of initial/final state pairs. The learning of such a strategy differs from traditional AI planning techniques which involve the generation of a plan as a sequence of actions transforming a particular initial state of the world to a particular final state. By contrast, a strategy can be viewed as a (potentially infinite) set of plans. Once learned, such a strategy can be applied without invoking a search through a space of plans. MIL is extended in this paper towards finding programs which have low resource complexity. That is, use of resources (eg number of moves, power dissipation etc) is near minimal for the learned strategy over the entire class of initial states.

2 Related work

In AI, planning traditionally involves deriving a sequence of actions to achieve a specific goal from an initial situation [Russell and Norvig, 2010]. The majority of research into AI planning has focused on developing efficient planners, i.e. systems which efficiently learn a plan to accomplish a goal. However, we are often interested in plans that are optimal with respect to an objective function by which the quality of a plan is measured. A common objective function is the length of the plan, i.e. the number of time steps to achieve the goal [Xing et al., 2006]. Plan length alone is only one criterion to be optimised [Eiter et al., 2003]. If executing actions is costly, we may desire a plan which minimises the overall cost of the actions, e.g. to minimise the use of limited resources such energy capacity. The Answer Set Programming literature has already addressed learning optimal plans by incorporating action costs into the learning [Eiter et al., 2003; Yang et al., 2014].

In contrast to these approaches, this paper investigates the construction of strategies which consist of a program containing conditional execution and recursion representing a (sometimes infinite) set of plans. Various machine learning approaches support the construction of strategies, including the SOAR architecture [Laird, 2008], reinforcement learning [Sutton and Barto, 1998], learning from traces [Lau et al., 2003], learning by demonstration [Argall et al., 2009], learning by imitation [Hayes and Demiris, 1994], policy abstraction [Pineau et al., 2002]. and action learning within ILP [Moyle and Muggleton, 1997; Otero, 2005].

Relational Markov Decision Processes [van Otterlo and Wiering, 2012] provide a general setting for reinforcement learning. Strategies can be viewed as a deterministic special case of Markov Decision Processes (MDPs) [Puterman, 2014]. Unlike most work in learning MDPs, MIL involves generation of readable programs by way of problem decomposition using predicate invention and the learning of recursive definitions. This has allowed it to be used in this paper for the classic programming optimisation task of finding optimal solutions for sorting lists (see Section 5.3). While reinforcement learning addresses heuristic policy optimisation it does not generally provide provable convergent means for finding optimal programs.

Strategy learning can also be classified as a form of inductive programming [Gulwani et al., 2015], in which functional and logic programs are learned from example presentations of input/output pairs. In this case, MIL is unusual in its use of predicate invention for learning recursive definitions. Problem decomposition has been found to be valuable for reusability of sub-programs [Lin et al., 2014], which has also been explored previously in a heuristic form in Genetic Programming [Koza and Rice, 1994].

Our experiments involve robot strategies where objects are composed by robots storing objects in containers, thus increasing carrying efficiency. The idea of composition of objects appears in both the planning [Cambon et al., 2004] and Natural Language literature. For instance, [Eugenio, 1991] describes the action place a plank between two ladders to create a simple scaffold.

3 Theoretical framework

3.1 Meta-Interpretive Learning

MIL [Muggleton et al., 2014b; 2015] is a form of ILP based on an adapted Prolog meta-interpreter. Whereas a standard Prolog meta-interpreter attempts to prove a goal by repeatedly fetching first-order clauses whose heads unify with a given goal, a MIL learner attempts to prove a set of goals by repeatedly fetching higher-order metarules (Table 2) whose heads unify with a given goal. The resulting meta-substitutions are saved in an abduction store, and can be re-used in later proofs. Following the proof of a set of goals, a hypothesis is formed by applying the meta-substitutions onto their corresponding metarules, allowing for a form of ILP which supports predicate invention and the learning of recursive theories.

3.2 Resource complexity

In this section we outline a framework for describing the resource complexity of robot strategies. Resource complexity can be vewied as a generalisation of the notion of timecomplexity of algorithms, in which time can be viewed as a particular resource. In robot strategies energy consumption and consumption of materials such as solder, glue, or bricks might also be considered as resources.

General formal framework Let O represent an enumerable set of objects in the world. Objects are separated into two disjoint sets O0 (primitive objects) and O1 (composite objects) where O = O0 ∪ O1. Composite objects are defined in terms of primitives and other composite objects. Let P represent an enumerable set of places in the world. Let S represent an enumerable set of situations where each situation is a pair 〈p, o〉 referring to the place p ∈ P where the object o ∈ O can be found. In any situation, an object is paired with only one place. Let A represent an enumerable set of actions. Each action a in A is a function where a : S → S. Action names are separated into two disjoint sets A0 (primitive actions) and A1 (composite actions) where A = A0 ∪ A1. Composite actions are defined in terms of primitives and other composite actions. We assume a resource function r : A × S → N which defines the resources consumed by carrying out action a ∈ A in situation s ∈ S.

Example 1 Robot Postman (composable). In the Postman example (Section 1) we have O0 = {letter1, letter2, postman, postbag}, O1 = {postbag containing letter1, . . .}, P = {place1, place2, place3, . . .}, S = {<place1,postman>, . . .}, A0 = {move up, move down, . . .}, A1 = {go to bottom, go to top, . . .}. For simplicity we assume the resource function gives r(a, s) = 1 in all cases in which a ∈ A0.

Generalised meta-interpreter prove([], P rog, P rog). prove([Atom|As], Prog1, Prog2) : - metarule(Name, MetaSub, (Atom :- Body), Order), Order, abduce(metasub(Name, MetaSub), P rog1, P rog3), prove(Body, P rog3, P rog4), prove(As, P rog4, P rog2).

We now give a resource complexity bound for the Postman.

Theorem 1 (Postman composable object bound) Let n be the cardinality of O0 and d be the cardinality of P in the Postman problem and a be a composite action which minimises r(a) for a ∈ A1. In this case r(a) is O(d + n).

Proof. The optimal strategy involves the postman using the postbag to hold all n objects. This involves at most d steps for traversal and n object pick-ups. The postman then needs to deliver each object to its destination, which again involves at most d steps for traversal and n object placements. Thus the overall time is bounded by 2(n + d), which is O(n + d).

Suppose in the above that the postman is disabled from composing objects by adding them to the postbag. In this case the resource complexity for the task is different.

Theorem 2 (Postman non-composable object bound.) Let n, d and a be as in Theorem 1, but objects are limited to O0. In this case r(a) is O(nd).

Proof. The optimal strategy involves the postman repeatedly finding and picking up an object and then moving to its destination and placing it there. This involves at most 2d steps for finding and carrying the object plus one pick-up and placement. Thus for all n objects this involves a resource of n(2d + 2) which is O(nd).

The difference in the complexities demonstrated in Theorem 1 and 2 show that differences in optimal strategy solutions can exist with assumptions associated with composability of objects. In the experiments described in Section 5 we show that such differences are evident in the output of solutions generated by MetagolO .

4 Implementation

This section describes MetagolO , a variant of MetagolD [Muggleton et al., 2015], an implementation of the MIL framework which learns programs within the Datalog subset H2 2 , where Hi j consists of definite Datalog logic programs with predicates of adicity at most i and at most j literals in the body of each clause.

4.1 MetagolO

Figure 3 shows the implementation of MetagolO 3 as a generalised meta-interpreter, similar in form to a standard Prolog meta-interpreter. The metarule set (Table 2) is defined separately, with each metarule having an associated name

3 Full code for MetagolO together with all materials for the experiments is available at http://ilp.doc.ic.ac.uk/metagolO.

(Name), quantification (MetaSub), form (Atom:-Body) and Herbrand ordering constraint (Order). Owing to the Turing-expressivity of H2 2 it is necessary [Muggleton et al., 2015] to constrain (Order) the application of the metarules to guarantee termination of the hypothesised program. The termination guarantees are based on these constraints being consistent with a total ordering over the Herbrand base of the hypothesised program. Thus the constraints ensure that the head of each clause is proved on the basis of instances of body atoms lower in the ordering over the Herbrand base. Since the ordering is not infinitely descending, this guarantees termination of the meta-interpreter.

4.2 Iterative descent

The key difference between MetagolO and MetagolD is the search procedure. MetagolD uses iterative deepening to ensure that the first hypothesis returned contains the minimal number of clauses. The search starts at depth 1. At depth i the search returns a consistent hypothesis with at most i clauses if one exists. Otherwise it continues to depth i + 1. MetagolD minimises the textual complexity of the hypothesis rather than resource complexity, which we now define.

Definition 1 (Resource complexity) Assume the training examples E consist of positive examples E+ and negative examples E-. Furthermore a hypotheses H ∈ H is a robot strategy chosen from the hypothesis space. The resource complexity of hypothesis H on example set E+ is

where r(H(e)) is the sum of resource costs of primitive actions in applying the strategy H to example e.

To find the hypothesis with minimal resource complexity, we employ a search procedure named iterative descent, which works as follows: starting at iteration 1, the search returns a hypothesis H1 with the minimal number of clauses if one exists. Importantly, on iteration 1 we do not enforce a maximum resource bound. Because the hypothesis space is exponential in the length of the solution [Muggleton et al., 2015], the hypothesis H1 is the most tractable to learn. The hypothesis H1 gives us an upper bound on the resource complexity from which to descend. At iteration i > 1, we search for a hypothesis Hi with the minimal number of clauses but we also enforce a maximum resource bound set to r(Hi-1, E+) - 1.

This ensures that any returned hypothesis Hi has a lower resource complexity than any hypothesis Hj, where j < i. If a hypothesis Hi exists, the search continues at i + 1, until we converge on the optimal hypothesis.

4.3 Convergence

MetagolO finds an optimal hypothesis for the training examples as follows: MetagolO (E+, H) = argminH∈Hr(H, E+). The following result demonstrates convergence of MetagolO to the optimal strategy given sufficiently large numbers of examples.

Theorem 3 (Convergence to optimal hypothesis) Assume E consists of m examples randomly and independently drawn from instance distribution D. Without loss of generality consider the hypothesis space consists of two hypotheses H1, H2 where H1 has resource complexity O(f1(n, d)) and H2 has resource complexity O(f2(n, d)) and f1(n, d) < f2(n, d) for all n, d > c where c is a positive integer and n, d are two natural number parameters of the examples 4 In the limit MetagolO will return H1 in preference to H2.

Sketch Proof. Assume false. However, since f1(n, d) > f2(n, d) for n, d > c, with sufficiently large m there will exist an example e d such that r(H2(e)) > r(H1(e)) where r(H2(e)) > r(H2(e′ )) for all other e′ in E+ and r(H1(e)) > r(H1(e′ )) for all other e′ in E+. In this case r(H1,E+) < r(H2,E+) and MetagolO returns H1, which has the minimum resource complexity. This contradicts the assumption and completes the proof.

5 Experiments

We now describe experiments in which we use MetagolO to learn robot strategies involving composite objects in two scenarios: Postman and Sorter. The experimental goals are (1) to support Theorems 1 and 2, i.e. show that resource complexities of optimal strategies vary depending on whether objects can be composed within a strategy, and (2) show that MetagolO can learn such resource optimal strategies.

5.1 Materials

We use a similar problem representation for both experiments where there is humanoid robot in a one-dimensional space 5 . The world state is a list of Prolog facts. The robot performs actions that change the state. Actions are defined as dyadic predicates and are either primitive or composite. Composite actions are defined in terms of primitive ones. We compare strategies learned with MetagolO to strategies learned with MetagolD [Muggleton et al., 2015], an existing ILP system. In both experiments, we provide the same background knowledge and metarules to both systems.

4 For the Postman f1, f2 are sum and product and n, d are as in Theorems 1 and 2. For the Sorter problem n is list length, d = 0, f1(x) = x2 and f2 = xlog2x.

5 This is for simplicity and the learner can handle any ndimensional space.

5.2 Learning robot postman strategies

Materials

We learn strategies for the postman example introduced in Section 1 where the goal is to learn a strategy to collect and deliver letters. The primitive actions are as follows: move up, move down, take letter, bag letter, give letter. All primitive actions have a cost of 1. The robot can take and carry a single letter from a sender using the action take letter. Alternatively, the robot can take a letter from a sender and place it in the postbag using the action bag letter to form a composite object consisting of the postbag and the letter. The composite actions are as follows: go to bottom, go to top, find next sender, find next recipient. The cost of a composite action is dynamic and is based on its constituent actions. For example, the composite action go to top recursively calls the primitive action move up until the postman is at the top.

Method

To generate training examples we select a random integer d from the interval [0, 50] representing the number of places 6 . We select a random integer n from the interval [1, d] representing the number of letters. For each letter we select random integers i and j from the interval [1, d] representing the letter's start and end positions. To generate testing examples we repeat the same procedure as above but with a fixed number of letters n, as to measure the resource complexity as n grows. We use 5 training and 5 testing examples. We average resource complexities of learned strategies over 10 trials.

Results

Figure 4 shows that the strategies learned with MetagolO are in agreement with the theoretical composable tighter bounds demonstrated in Section 3. By contrast, the strategies learned with MetagolD are in agreement with the theoretical noncomposable tighter bounds. Figure 2 shows two recursive strategies learned by MetagolD (a) and MetagolO (b) respectively, able to handle any number of places, any number of letters, and different start/end positions for the letters. Although both strategies are equal in textual complexity, they differ in their resource complexity. The strategy learned by MetagolO (b) is more efficient than the one learned by MetagolD (a) because it uses composite objects, i.e. the action bag letter, whereas (b) does not. Table 1 illustrates this difference. The explanation for this is that MetagolD simply had no reason to prefer the more efficient hypothesis, it just happened to find the less efficient hypothesis first.

We also ran experiments (omitted for brevity) where we removed the ability to form composite objects, i.e. the action bag letter. In this scenario, the strategies learned with MetagolO are in agreement with the theoretical noncomposable tighter bounds.

5.3 Learning robot sorting strategies

Materials

In this experiment, we investigate recursive sorting algorithms learned as recursive robot strategies. In the initial state there is an unsorted list; in the final state there is a sorted list.

6 50 is an arbitrary limit, and the learner handles any finite limit.

The robot can traverse the list moving sideways. The leftmost element represents the smallest element in the sorted list. We provide the learner with the actions to perform robot translations of the quick sort and bubble sort algorithms. We provide four composite actions: compare adjacent, split, combine, go to start. The action compare compares two adjacent elements and swaps them if the one to the right is smaller than the one to the left. The action split allows the robot to move through the list comparing each element with the element in the robot's left hand (the pivot). If an element is less than or equal to the pivot, then the item is placed in a left bag; otherwise it is placed in a right bag. Both bags are stacks. The action combine empties the right bag, drops the pivot, and empties the left bag. We also provide two primitive actions: decrement end, pick up left. The decrement end action decrements a counter in the state representing the position of the last element of the list. The composite actions call other primitive actions that are unknown to the learner, e.g. move left, move right. The full list of such actions is omitted for brevity. All of the primitive actions have an action cost of 0, except the action compare holding which has an action cost of 1. Thus, the optimal strategy is the one that minimises element comparisons.

Method

To generate training examples we select a random integer n from the interval [2, 50] representing the length of the list. We use Prolog's randseq/3 predicate to generate a list of n unique random integers from the interval [1, 100] representing the input list, with this list sorted representing the output list. To generate testing examples we repeat the same procedure as above but with a fixed list length n as to measure the resource complexity as n grows. We use 5 training and 5 testing examples. We average resource complexities of learned strategies over 10 trials.

Results

Figure 6 shows that the strategies learned with MetagolO are in agreement with the theoretical average-case expectations of quick sort 7 (O(n log n)). By contrast, the strategies learned with MetagolD are closer to the average-case expectations of bubble sort (O(n2 )). Figure 5 shows the two recursive strategies learned by MetagolD (a) and MetagolO (b) respectively. MetagolO learns a variant of quick sort, which uses composite objects, whereas MetagolD learns a variation of bubble sort, which does not use composite objects.

metasort(A,B):- metasort1(A,C), metasort(C,B).

metasort1(A,B):- comp adjacent(A,C), metasort1(C,B).

metasort1(A,B):- decrement end(A,C), go to start(C,B).

metasort(A,B):- metasort1(A,C), go to start(C,B).

(a) Inefficient strategy learned by MetagolD

metasort(A,B):- metasort1(A,C), metasort(C,B).

metasort1(A,B):- pick up left(A,C), split(C,B).

metasort1(A,B):- combine(A,C), go to start(C,B).

metasort(A,B):- split(A,C), combine(C,B).

(b) Efficient strategy learned by MetagolO

Figure 6: Mean resource complexity of robot sorter strategies with varying lengths of input.

6 Conclusions and further work

To the authors' knowledge this paper represents the first demonstration of a learning algorithm which provably optimises the resource complexity of robot strategies. The approach differs from traditional AI planning techniques which involve the identification of a sequence of actions to achieve a single goal from a single initial situation (e.g. moving from the door to the table). By contrast, a learned strategy is a program which can be applied to a multiplicity of initial situations to achieve a multiplicity of corresponding goal situations (e.g. deliver all the letters to their destinations). Once learned, such a strategy can be applied without the need for searching a space of plans each time. This paper proves the existence (Theorems 1 and 2) of particular cases (Postman) in which classes of learnable strategies have different resource complexities. A new MIL implementation, MetagolO , is shown (Theorem 3) to converge with sufficiently large numbers of examples to the most efficient strategy. Our experiments demonstrate that the theoretical bounds of Theorem 3 hold in practice. The approach suggests the ability to build delivery and sorting robots which can learn resource efficient strategies from examples.

7 Resource complexity proofs are omitted for brevity.

6.1 Further work

A limitation of this paper is the lack of details regarding the computational requirements of MetagolO to converge on an optimal solution. We will explore this in future work, including exploring methods to optimise the iterative descent search procedure. For example, instead of decrementing the energy bound by 1, binary search would be more efficient.

In Section 5 we compared our implementation, MetagolO, to an existing ILP system, MetagolD. In future work we intend to run comparisons with non-ILP systems. We also want to test this approach on a broader range of program induction tasks that include resource optimisation. For instance, in the learning of proof tactics for theorem proving, game tactics strategies, and string transformation functions.

The approach taken in this paper can be generalised in several ways. For instance, the use of dyadic Datalog programs could be generalised by using a richer set of metarules. We also intend to further explore the notion of object composition and investigate the resource complexity reduction of inventing new objects in the world. For instance, in the postman example, we provide a postbag in the background knowledge. In future work we would like to investigate methods for the learner to invent such an object.

In this work we have assumed noise-free data. To move beyond this assumption we could consider probabilistic variants such as those investigated in Statistical Relational Learning [De Raedt et al., 2007; Muggleton et al., 2014a].

We also hope to better characterise the value of recursion in strategy-learning tasks. In [Broda et al., 2009] the authors consider continuous actions such as move hand until you touch the table. We aim to investigate continuous actions in further work.

All actions described in this paper have positive resource costs. We would like to consider actions with negative costs, i.e. benefits. For instance, an action which recharges the robot's battery, or actions in which the robot collects other resources, such as glue or bricks, or recruits other robots to help in a task.

To summarise, we believe that this paper opens exciting new avenues in a variety of areas in AI for understanding the value of machine learning efficient strategies.

Acknowledgments

The first author thanks the BBSRC for his PhD studentship. The second author acknowledges support from his Syngenta Royal Academy of Engineering Research Chair at the Department of Computing at Imperial College London.