On Policy Reuse: An Expressive Language for Representing and Executing General Policies that Call Other Policies

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 23:22:46

Abstract: Recently, a simple but powerful language for expressing and learning general policies and problem decompositions (sketches) has been introduced, which is based on collections of rules defined on a set of Boolean and numerical features. In this work, we consider three extensions of this basic language aimed at making policies and sketches more flexible and reusable: internal memory states, as in finite state con- trollers indexical features, whose values are a function of the state and a number of internal registers that can be loaded with objects; and modules that wrap up policies and sketches and allow them to call each other by passing parameters. In addition, unlike general policies that select actions indirectly by selecting state transitions, the new language allows for the selection of ground actions directly. The expressive power of the resulting language for recombining policies and sketches is illustrated through a number of examples. The problem of learning policies and sketches in the new language, from the bottom up, is left for future work.

Main paper: 
 introduction: 
 A new language for representing problem structure explicitly has been introduced recently in the form of sketches (Bonet and Geffner 2023) . Sketches are collections of rules of the form C → E defined over a set of Boolean and numerical domain features Φ, where C expresses Boolean conditions on the features, and E expresses qualitative changes in their values. Each sketch rule captures a subproblem: the problem of going from a state s whose feature values satisfy the condition C, to a state s ′ where the feature values change with respect to s in agreement with E. The language of sketches is powerful as it can encode everything from simple goal serializations to full general policies.The width of a sketch for a class of problems bounds the complexity of solving the resulting subproblems (Bonet and Geffner 2023) . For example, a sketch of width k decomposes problems into subproblems that are solved by the IW algorithm in time exponential in k (Lipovetzky and Geffner 2012) . Sketches provide a direct generalization of policies, which are sketches of width 0 that result in subproblems that can be solved in a single step (Bonet and Geffner 2023) .A method for learning sketches is developed by Drexler, Seipp, and Geffner (2022) where both the rules and its features are obtained by solving a combinatorial optimization problem that accepts three inputs: an upper bound on the width of the sketch to be learned, a small number of domain instances, and a pool of features defined from the domain predicates in a domain-independent manner.The current language of policies and sketches, however, does not support the reuse of existing policy sketches, and assumes instead that the top goals are set up externally. 1 Yet for reusing policies and sketches, goals must be set up internally as well. E.g., for reusing a general policy π on that achieves an atom on(x, y) for any blocks x and y within a policy π T that builds a given tower, it is necessary for the policy π T to invoke policy π on while selecting the right sequence of arguments x and y to pass to the policy.In this work, we develop an extension of the language of policies and sketches that accommodates policy and sketch reuse. In the resulting framework, policies and sketches can call other policies and sketches while passing them suitable arguments. For example, one can learn a policy π on for putting one block on top of another, and use the learned policy for learning a policy π T for building a tower of blocks, and reuse this policy in turn for learning to build any configuration of blocks.The language extensions are basically three: memory states, as in finite state controllers for sequencing behaviors, indexical features, whose values are a function of the state and a number of internal registers that can be loaded with objects, and modules, that package policies and sketches so that they can be reused by other policies or sketches. In this paper, we do not address the learning problem, but the representation problem, as in order to learn these policies bottom up, one must be able to represent them.The paper is structured as follows. The next two sections cover related work and review planning and sketches. Then, two sections introduce extended policies and sketches, and their semantics, and the following section introduces modules, call rules, and action calls. The last section contains a discussion with conclusions and directions for future work.General policies. The paper builds on a research thread that introduced the notions of width, generalized rule-based policies and sketches of bounded width, as well as methods for learning them (Lipovetzky and Geffner 2012; Bonet and Geffner 2018, 2023; Francès, Bonet, and Geffner 2021; Drexler, Seipp, and Geffner 2022, 2023) . The problem of representing and learning general policies has a long history (Khardon 1999; Martín and Geffner 2004; Fern, Yoon, and Givan 2006) , and general plans have also been represented in logic (Srivastava, Immerman, and Zilberstein 2011; Illanes and McIlraith 2019) , and neural nets (Groshev et al. 2018; Toyer et al. 2018; Bueno et al. 2019; Rivlin, Hazan, and Karpas 2020; Garg, Bajpai, and Mausam 2020; Ståhlberg, Bonet, and Geffner 2023) . Planning programs and inductive programming. Planning programs have been proposed as a language for representing and learning general policies that make use of a number of programming language constructs (Aguas, Celorrio, and Jonsson 2016; Segovia-Aguas, Jiménez, and Jonsson 2019, 2021) . However, without a rich feature language for talking about goals, states, and their relation, planning programs are basically limited to families of tasks where the goal is fixed; like "putting all blocks on the table", but not for "building a given tower". 2 The problem of program reuse, which is related to the problem of policy reuse, has been considered in program synthesis and inductive programming (Dumancic, Guns, and Cropper 2021; Ellis et al. 2023 ). Deictic representations. The use of registers to store objects in the extended language of policies and sketches is closely related to the use of indices and visual markers in deictic or indexical representations (Chapman 1989; Agre and Chapman 1990; Ballard et al. 1996) . The computational value of such representations, however, has not been clear (Finney et al. 2013 ). In our setting, indices (registers) make policies (and sketches) parametric and more expressive, as (sub)policies can be reused by setting and resetting the values of registers as needed. Hierarchical RL. Hierarchical structures have been used in RL in the form of options (Sutton, Precup, and Singh 1999) , hierarchies of machines (Parr and Russell 1997) and MaxQ hierarchies (Dietterich 2000) , and a vast literature has explored methods for learning hierarchical policies (Mc-Govern and Barto 2001; Machado, Bellemare, and Bowling 2017) , in some cases, encoding varying goals as part of the state (Kulkarni et al. 2016; Hafner et al. 2022) . In almost all cases, however, policies and subpolicies are learned jointly, not bottom up, and the information that is conveyed by parameters, if they exist, is very limited.A planning problem refers to a classical planning problem P = ⟨D, I⟩ where D is the planning domain and I contains information about the instance; namely, the objects in the instance, the initial situation, and the goal. A class Q of 2 The goal is fixed in a class Q of planning problems when for any P in Q, the goal G of P is determined by its initial state. planning problems is a set of instances over the same domain D. A sketch for a class of problems Q is a set of rules of the form C → E based on features over the domain D which can be Boolean or numerical, with non-negative integer values (Bonet and Geffner 2023) . The condition C is a conjunction of expressions like p and ¬p for Boolean features p, and n > 0 and n = 0 for numerical features n, while the effect E is a conjunction of expressions like p, ¬p, and p?, and n↓, n↑ and n? for Boolean and numerical features p and n, respectively. A state pair (s, s ′ ) over an instance P in Q is compatible with a rule r if the state s satisfies the condition C, and the change of value for the features from s to s ′ is consistent with E. This is written as s ′ ≺ r s and s ′ ≺ R s if R is a set of rules that contains r.A sketch R for a class Q splits the problems P in Q into subproblems P [s] that are like P but with initial state s (where s is a reachable state in P ), and goal states s ′ that are either goal states of P , or states s ′ such that s ′ ≺ R s. The algorithm SIW R shown in Fig 1 uses this problem decomposition for solving problems P in Q by solving subproblems P [s] via the IW algorithm (Lipovetzky and Geffner 2012) .If the sketch has bounded serialized width over Q and is terminating, SIW R solves any problem P in Q in polynomial time (Bonet and Geffner 2023; Srivastava et al. 2011a) .The width of a planning problem P provides a complexity measure for finding an optimal plan for P . If P has N ground atoms and its width is bounded by k, written w(P ) ≤ k, an optimal plan for P can be found in O(N 2k-1 ) time and O(N k ) space by running the algorithm IW(k), which is a simple breadth-first search where newly generated states are pruned if they do not make a tuple (set) of k atoms or less true for the first time in the search (Lipovetzky and Geffner 2012). If the width of P is bounded but its value is unknown, a plan (not necessarily optimal) can be found by running the algorithm IW with the same complexity bounds. IW calls IW(i) iteratively with i = 0, . . . , k, until P is solved (Lipovetzky and Geffner 2012) . If P has no solution, its width is defined as w(P ) . = ∞, and if it has a plan of length one, as w(P ) . = 0. The width notion extends to classes Q of problems: w(Q) ≤ k iff w(P ) ≤ k for each problem P in Q. If w(Q) ≤ k holds for class Q, then any problem P in Q can be solved in polynomial time as k is independent of the size of P .A sketch R has serialized width bounded by k on a class Q, denoted as w R (Q) ≤ k, if for any P in Q, the possible subproblems P [s] have width bounded by k. In such a case, every subproblem P [s] that arises when running the SIW R algorithm on P can be solved in polynomial time.Finally, a sketch R is acyclic in P if there is no state sequence s 0 , s 1 , . . . , s n in P such that s i+1 ≺ R s i , for 0 ≤ i < n, and s n = s 0 . R is acyclic in Q if it is acyclic in each problem P in Q. The SIEVE algorithm (Srivastava et al. 2011a ) can check whether a sketch R is terminating, and hence acyclic, by just considering the rules in R and the graph that they define (Bonet and Geffner 2023) . For a terminating sketch R with a bounded serialized width over Q, SIW R is guaranteed to find a solution to any problem P in Q in polynomial time (Bonet and Geffner 2023) .Example 1 shows a policy (sketch of width 0) for achieving the atom on(x, y) for blocks x and y in any Blocksworld instance, and also a sketch of width 2. The policy picks blocks above x and y, and put them away until no more such blocks exist, and then stacks x on y. However, the blocks are picked in non-specific order; e.g., one above x, one above y, another above x, etc. See below for a different policy that picks the blocks in order.Example 1: Policy and sketch for the class Q on A general policy πon for the class Qon of all Blocksworld problems with atomic goal on(x, y) for two blocks x and y can be defined with the numerical feature n that counts the number of blocks above x and y, and the Booleans On that represents whether x is on y, H that represents whether a block is being held, and Hx that represents whether block x is being held. The set of features is Φ = {On, H, Hx, n}, and the rules are: r0 := {¬On, n > 0, ¬H, ¬Hx} → {n↓, H, Hx?} r1 := {¬On, n > 0, H} → {¬H, ¬Hx} r2 := {¬On, n = 0, ¬H, ¬Hx} → {H, Hx} r3 := {¬On, n = 0, H, Hx} → {On, n↑, ¬H, ¬Hx}.Rule r0 says that in states where n > 0 and no block is held, picking a block above x or y is good (are subgoals according to the rules), r1 that in states where n > 0 and a block is held, putting the held block away from x or y is good, r2 that in states where n = 0 and no block is held, picking up x is good, and r3 that in states where n = 0 and block x is held, putting x on y is good, which results in On becoming true.Alternatively, a sketch of width 2 for Qon is obtained by replacing rules r0 and r1 with the rule {¬On, n > 0} → {n↓, ¬H}, and rules r2 and r3 with {¬On, n = 0} → {On, n↑, ¬H}.The first two extensions of sketches are introduced.The first language extension adds memory in the form of a finite number of memory states m:Definition 1 (Sketches with memory). A sketch with finite memory is a tuple ⟨M, Φ, m 0 , R⟩ where M is a finite set of memory states, Φ is a set of features, m 0 ∈ M is the initial memory state, and R is a set of rules extended with memory states. Such rules have the form (m, C) → (E, m ′ ) where C → E is a standard sketch rule, and m and m ′ are memory states in M .When the current memory state is m, only rules of the form (m, C) → (E, m ′ ) apply. If the current state and memory are s and m respectively, and s ′ is a state reachable from s such that the pair (s, s ′ ) is compatible with the rule C → E, then moving to state s ′ and setting the memory to m ′ is compatible with the extended rule(m, C) → (E, m ′ ). In displayed listings, rules (m, c) → (E, m ′ ) are written as m ∥ {C} → {E} ∥ m ′ to improve readability.Example 2 shows a general policy for solving Towers of Hanoi with 3 pegs. The policy uses two memory states to alternate between two types of movements. Such a policy cannot be expressed without memory states.Example 2: General policy for Hanoi with 3 pegs Liu et al. (2023) describe a simple policy for the class QHanoi that consists of Towers-of-Hanoi instances with 3 pegs for moving a tower in the first peg to the third peg. The policy is expressed by referring to the relative size of the disk being moved, among the top disks at each peg, either a movement of the smallest disk, or a movement of the other disk:Alternate actions between the smallest disk and a nonsmallest disk. When moving the smallest disk, always move it to the left. (If it is in the first peg, move it to the third peg.) If the smallest disk is on the first pillar, move it to the third one. When moving the non-smallest disk, take the only valid action.The movements are expressed in the language of sketches with three Boolean features pi,j, 1 ≤ i < j ≤ 3, that are true if the top disk at peg i is smaller than the top disk at peg j. For example, the smallest disk is at peg 1 (resp. peg 3) iff p1,2 ∧p1,3 (resp. ¬p1,3 ∧ ¬p2,3) holds. The alternation of movements is obtained by using two memory states m0 and m1 of which m0 is the initial memory. The rules are:% Movements of the smallest disk m0 ∥ {p1,2, p1,3} → {p1,2?, ¬p1,3, ¬p2,3} ∥ m1 m0 ∥ {¬p1,2, p2,3} → {p1,2, p1,3, p2,3?} ∥ m1 m0 ∥ {¬p1,3, ¬p2,3} → {¬p1,2, p1,3?, p2,3} ∥ m1 % Movements of the other disk m1 ∥ {p1,2, p1,3, p2,3} → {¬p2,3} ∥ m0 m1 ∥ {p1,2, p1,3, ¬p2,3} → {p2,3} ∥ m0 m1 ∥ {¬p1,2, p1,3, p2,3} → {¬p1,3} ∥ m0 m1 ∥ {¬p1,2, ¬p1,3, p2,3} → {p1,3} ∥ m0 m1 ∥ {p1,2, ¬p1,3, ¬p2,3} → {¬p1,2} ∥ m0 m1 ∥ {¬p1,2, ¬p1,3, ¬p2,3} → {p1,2} ∥ m0Registers, Indexicals, Concepts, and RolesThe second extension introduces internal memory in the form of registers. Registers store objects, which can be referred to in features that become indexical or parametric, as their value changes when the object in the register changes; e.g., the number of blocks above the block in register zero. The objects that can be placed into the registers R = {r 0 , r 1 , . . .} are selected by two new classes of features called concepts and roles that denote sets of objects and set of object pairs, respectively (Baader et al. 2003) .Concept features or simply concepts are denoted in sansserif font such as 'C', and in a state s, they denote the set of objects in the problem P that satisfy the unary predicate 'C' in s. Role features or simply roles are also denoted in sansserif font such as 'R', and in a state s, they denote the set of object pairs in the problem P that satisfy the binary relation 'R'. Concept and role features are also used as numerical features, e.g., as conditions 'C > 0' or effects 'R↓', with the understanding that the corresponding numerical feature is given by the cardinality of the concept C or role R in the state; namely, the number of objects or object pairs in their denotation.While a plain feature is a function of the problem state, an indexical or parametric feature is a function of the problem state and the value of the registers; like "the distance of the agent to the object stored in r 0 ". When the value of a register r changes, the denotation of indexical features that depend on the value of the register may change as well. We denote by Φ(r) the subset of features in Φ that refer to (i.e., depend on the value of) register r. The set of features Φ is assumed to contain a (parametric) concept for each register r, whose denotation is the singleton that contains the object in r, and that is also denoted by r.The extended sketch language provides load effects of the form Load(C, r) for updating the value or registers for a concept C and register r; an expression that indicates that the content of the register r is to be set to any object in the (current) denotation of C, a choice that is non-deterministic. Loading an object into register r can be thought as placing the marker r on the object. A rule with effect Load(C, r) has the condition C > 0 to ensure that C contains some object. Likewise, since a load may change the denotation of features, the effect of a load rule on register r is assumed to contain also the extra effects ϕ? for the features ϕ in Φ(r), and no other effects. Formally, Definition 2 (Extended rules). An extended rule over the features Φ and memory M has the form (m, C) → (E, m ′ ) where m and m ′ are memory states, C is a set of conditions of the form p, ¬p, n = 0, and n > 0 for Boolean and numerical features p and n in Φ, and E is a set of effects of the form p, ¬p, p? for Boolean p, n↓, n↑, and n? for numerical n, or it has a single load effect of form Load(C, r) for some concept C and register r. If E contains a Load(C, r), it also contains ϕ? for the features ϕ in Φ(r), but no other effect.Rules with a load effect are called internal rules, as they capture changes in the internal memory only, while the other rules are called external rules. For simplicity, it is assumed, that each load rule contains a single load effect, and that internal rules have their own memory state, meaning that no external rule can be applied in the same memory where an internal rule is applied. For convenience, we also allow internal rules of the form (m, C) → (true, m ′ ), abbreviated as (m, C) → ({}, m ′ ), that permit to change from mem-ory state m to memory state m ′ under condition C. Memory states associated with internal rules are referred to as internal memory; others, as external memory. Extended sketches are formally defined as Definition 3 (Extended sketch). An extended sketch is a tuple ⟨M, R, Φ, m 0 , R⟩ where M and R are finite sets of memory states and registers, respectively, Φ is a set of features, m 0 ∈ M is the initial memory state, and R is a set of extended Φ-rules over memory M . An extended sketch is well defined on a class Q if its set of features Φ is well defined on Q. If m is a memory state, R(m) denote the subset of rules in R of form (m, C) → (E, m ′ ).Example 3 defines a general indexical policy π * on for the class of Blockworld problems Q on in Example 1. The policy can be understood as putting the "mark" r 0 on a block in N, and a second mark r 1 is moved up from r 0 to the topmost block above r 0 . The block marked as r 1 is then put away and the mark r 1 is updated. When the block in r 0 becomes clear, the process repeats until counter N becomes zero. When N is zero, both x and y are clear. The policy then picks x and puts it on top of y. It is important to notice that this policy guarantees clearing one block x or y after clearing the other while the policy from Example 1 does not have this guarantee. The marks fix the attention on the blocks in a common tower which permits the use of much simpler features.Example 3: Indexical policy for the class Q on A general indexical policy π * on for Qon can be obtained with 8 memory states, two registers r0 and r1, the concept N for the blocks in {x, y} that are not clear, the indexical concept T0 (resp. T1) for the block on r0 (resp. r1), if any, and the Boolean features A that is true if the block in r1 is above x or y, H (resp. Hx) that is true if holding some block (resp.x), and On that is true iff on(x, y) holds. The set of features is Φ = {On, H, Hx, A, N, T0, T1}, the initial memory state is m0, and the rules are:% Internal rules r0 := m0 ∥ {¬H, N > 0} → {Load(N, r0), T0?} ∥ m1 r1 := m0 ∥ {¬H, N = 0} → {} ∥ m6 r2 := m0 ∥ {H} → {} ∥ m5 r3 := m1 ∥ {r0 > 0} → {Load(r0, r1), T1?, A?} ∥ m2 r4 := m2 ∥ {T1 > 0} → {Load(T1, r1), T1?, A?} ∥ m2 r5 := m2 ∥ {T1 = 0} → {} ∥ m4 r6 := m3 ∥ {T0 > 0} → {} ∥ m1 r7 := m3 ∥ {T0 = 0} → {} ∥ m0 % External rules r8 := m4 ∥ {¬H, A} → {H, ¬A, N?} ∥ m5 r9 := m5 ∥ {H, ¬A} → {¬H} ∥ m3 r10 := m5 ∥ {H, ¬A} → {¬H, N↓} ∥ m3 r11 := m6 ∥ {¬Hx} → {Hx} ∥ m7 r12 := m7 ∥ {Hx, ¬On} → {On} ∥ m7where rule r0 puts either block x or y to be cleared in r0, r1 goes to m6 when x and y are clear, r2 is used when initially holding a block, r3 puts r0 in r1, r4 moves r1 up in the tower, r5 goes to m4 when r1 is clear, rules r6, r7 form a conditional jump to m0 if r0 is clear, and otherwise, jumps to m1, r8 picks block in r1, r9, r10 puts it away, r11, r12 put block x on y. The feature A is used to avoid placing a block being held above x or y; this can be seen in rules r9 and r10 whose conditions A and ¬A is not mentioned in the effects, meaning that its value must not change in any transition compatible with the rules. Indexical features are used to keep track of objects, allowing simpler features than those used in the policy in Example 1. For example, the features T0 and T1, that contain the block directly on r0 and r1, respectively, are much simpler than the feature n that counts the total number of blocks above x and y. The following Figure 2 illustrates the usage of indexicals.b 3 b 2 b 1 x r 0 (a) Load(N,r0) b 3 b 2 b 1 x r 0 r 1 (b) Load(T1,r1) b 3 b 2 b 1 x r 0 r 1 (c) Load(T1,r1) b 3 b 2 b 1 x r 0 r 1 (d) Load(T1,r1)Figure 2 : Illustration of finding block b3 that must be put away:(a) the rule r0 sets the marker r0 on the block x ∈ N that must be cleared, (b) the rule r3 sets the marker r1 on the block b1 ∈ T0 above the block x in r0, (c) the rule r4 moves the marker r1 one step above to the block b2 ∈ T1, (d) the rule r4 moves the marker r1 one step above to the topmost block b3 ∈ T1. The concept T1 is empty and the loop over r4 terminates.Extended sketches are evaluated on planning states augmented with memory states, and values for the registers.Definition 4 (Augmented states). An augmented state for a problem P given an extended sketch ⟨M, R, Φ, m 0 , R⟩ is a tuple s = (s, m, v) where s is a reachable state in P , m is a memory state in M , and v is a vector of objects in Obj(P ) R that tells the content of each register r, denoted as v[r].Features ϕ are evaluated over pairs (s, v) made up of a state s and a value v for the registers. The value for ϕ at such a pair is denoted by ϕ(s, v).Definition 5 (Compatible pairs). Let r be an external Φ-rule (m, C) → (E, m ′ ), and let v be a valuation for the registers. A state s satisfies the condition C given v if the feature conditions in C are all true in (s, v). A state pair (s, s ′ ) satisfies the effect E given v if the values for the features in Φ change from s to s ′ according to E; i.e., the following holds where p is a Boolean feature, n is a numerical, concept or role feature, and ϕ is any type of feature,1. if p (resp. ¬p) is in E, p(s ′ , v) = 1 (resp. p(s ′ , v) = 0), 2. if n↓ (resp. n↑) is in E, n(s, v) > n(s ′ , v) (resp. n(s, v) < n(s ′ , v)), and 3. if ϕ is not mentioned in E, ϕ(s, v) = ϕ(s ′ , v).The pair (s, s ′ ) is compatible with an external rule r = (m, C) → (E, m ′ ) given v, denoted as s ′ ≺ r/v s, if given v, s satisfies C and the pair satisfies E. The pair is compatible with a set of rules R given v, denoted as s ′ ≺ R/v s, if it is compatible with some external rule in R given v.The search algorithm for extended sketches, called SIW * R and shown below in Fig. 3 , maintains the current memory state and values for registers, implements the internal rules, and perform IW searches to solve the subproblems that arise when the memory state becomes external. Definition 6 (Subproblems). If s = (s, m, v) is an augmented state for P , where m is external memory, the subproblem P [s] is a planning problem like P but with initial state s and goal states that are goal states of P or states s ′ such that s ′ ≺ r/v s for some rule r in R(m).Internal rules do not generate classical subproblems and do not change the planning state s but they affect the memory state and the register values, and with that, the definition of the subproblems that follow. The notion of reduction captures how internal rules are processed: Definition 7 (Reduction). Let ⟨M, R, Φ, m 0 , R⟩ be an extended sketch for a planning problem P , and let (s, m, v) be an augmented state for P where m is in M . The pair⟨(s, m, v), (s, m ′ , v ′ )⟩ is a reduction step if there is an in- ternal rule r in R of form (m, C) → (E, m ′ ) such that 1) s satisfies the condition C given v, and 2) v ′ is equal to v, except if Load(C, r) is in E, in which case v ′ [r] ∈ C(s, v).A sequence of reduction steps starting at (s, m, v) and ending at (s, m ′ , v ′ ) where m ′ is external is called a reduction, and it is denoted by (s, m, v) → * (s, m ′ , v ′ ). For convenience, if m is external, we also write (s, m, v) → * (s, m, v).An initial augmented state for problem P is of the form (s 0 , m, v) where s 0 is the initial state in P , and (s 0 , m 0 , v 0 ) → * (s 0 , m, v) for the initial memory m 0 and some v 0 in Obj(P ) R . There may be different initial augmented states for P that differ in their memory and/or the contents of the registers. Each such initial augmented state defines an initial subproblem P [s 0 , m, v] (cf. Definition 6). Definition 8 (Induced subproblems). Let ⟨M, R, Φ, m 0 , R⟩ be an extended sketch for a planning problem P with initial state s 0 . Let us consider a subproblem P [s] for s = (s, m, v) where m is external, and let s ′ be a state reachable from s with s ′ ≺ r/v s for some rule r in R(m). Then,1. subproblem P [s ′ , m ′ , v] is induced by subproblem P [s] if r = (m, C) → (E, m ′ ) and m ′ is external memory. 2. Subproblem P [s ′ , m ′′ , v ′ ] is induced by subproblem P [s] if r = (m, C) → (E, m ′ ), m ′ is internal memory, and (s ′ , m ′ , v) → * (s ′ , m ′′ , v ′ ).The collection P • of induced subproblems is the smallest set such that 1) P • contains all the initial subproblems, and2) P [s ′ , m ′ , v ′ ] is in P • if P [s, m, v] is in P • andthe first subproblem is induced by the second.By "jumping" over subproblems P [s, m, v] where m is internal, the definition ensures that the subproblems that make it into P • all have memory states m that are external, and hence represent classical planning problems. The extended sketch R is said to be reducible in P if for any reachable augmented state (s, m, v) in P where m is an internal state, there is an augmented state (s, m ′ , v ′ ) such that (s, m, v) → * (s, m ′ , v ′ ). A non-reducible sketch is one in which the executions can cycle or get stuck while performing internal memory operations. Definition 9 (Sketch width). The width of a reducible sketch R over a planning problem P is bounded by non-negative Algorithm 3: SIW * R search with extended sketch R 1: Input: Extended sketch ⟨M, R, Φ, m0, R⟩ 2: Input: Planning problem P with initial state s0 on which the features in Φ are well defined 3: s ← (s0, m0, v) for some v ∈ Obj(P ) R 4: while s in s = (s, m, v) is not a goal state of P 5:if m is internal memory 6:Find rule r = (m, C) → (E, m ′ ) with s, v ⊨ C 7: if r is not found, return FAILURE % Irreducible 8: if Load(C, r) in E, v[r] ← o for some o ∈ C(s, v) 9: s ← (s, m ′ , v) 10:else % m is external, solve subproblem 11:Run IW search from s to find goal state s ′ of P , or state s ′ such that s ′ ≺ r/v s for some (external) rule r = (m, C) → (E, m ′ ) in R 12:if no such state is found, return FAILURE 13: s ← (s ′ , m ′ , v) 14: return path from s0 to the goal state s R (Q) ≤ k, if w R (P ) ≤ k for each P in Q.The serialized width is zero for the indexical sketch in Example 3, as the sketch represents a policy where each subproblem is solved in a single step.Termination is a key property for sketches that guarantees acyclicity, and that only a polynomial number of subproblems may appear on any problem P where the features are well defined (Bonet and Geffner 2023) . Termination can be tested in polynomial time by a suitable adaptation of the SIEVE algorithm (Srivastava et al. 2011b; Bonet and Geffner 2023) . If the extended sketch is reducible, terminating, and has bounded serialized width over a class Q, then any problem P in Q can be solved in polynomial time with SIW * R , shown in Fig. 3 .Theorem 10 (Termination). If the extended sketch R is reducible, terminating, and has a serialized width bounded by k over the class of problems Q, then SIW * R finds plans for any problem P in Q in polynomial time.Reusable policies and sketches are wrapped into modules. A module is a named tuple ⟨args, Z, M, R, Φ, m 0 , R⟩ where args = ⟨x 1 , x 2 , . . . , x n ⟩ is a tuple of arguments, each one being either a static concept or role, Z and Φ are sets of features, M is a set of memory states, R is a set of registers, m 0 ∈ M is the initial memory state, and R is a set of rules. The features in Φ are the ones mentioned in the sketch rules in R, and their definition may depend on the value of the arguments and the features in Z. The sketch R in a module can contain two new types of internal rules, call and do rules, that permit to call other modules, and to directly execute ground actions of the planning problem, respectively. The value for the arguments in either case are given by the features in Φ or Z, and the arguments of the module; the difference between Φ and Z is that the rules in R must track the changes for the features in Φ, while Z can be used to define features in Φ, appear in conditions of rules, and provide values to arguments in call and do rules. If the name of the module is name, we refer to it as name(x 1 , x 2 , . . . , x n ).Call and do rules are of the form (m, C) → (name(v 1 , v 2 , . . . , v n ), m ′ ) where m is internal memory, C is a condition, name is a module or action schema name, and each value v i is of an appropriate type: for do rules, v i must be a concept, while for call rules, v i can be either a concept or a role. The idea is that if a call rule is used, the sketch associated with the module name is executed until no rules are applicable, and the control is then returned back to the caller at the memory state m ′ . For do rules, an applicable ground action of the form name(o 1 , o 2 , . . . , o n ), where the object o i belongs to the denotation of concept v i , must be applied at the current state to make a transition to a successor state, and control is then returned back to the caller at the memory state m ′ .The execution model for handling modules involves a stack as described below. Modules call each other by passing arguments but do not get back any values. The "side effects" of a module are in the problem state s that must be driven eventually to a goal state.Example 4 shows the module on(X, Y) for a policy for the class Q on that essentially implements the policy in Example 3. However, by directly executing ground actions, we define a policy that uses even simpler features than the ones used in Example 3. That is, the indexical Boolean A is not needed because the block being held is put away on the table with a Putdown action.Example 4: Module on(X, Y) for the class Q onThe module on(X, Y) implements a policy for the class Qon. Its parameters are singleton concepts X and Y that contain the blocks x and y, respectively. The module uses do rules to avoid references to complex concepts; it only uses the concepts B for all blocks, N for the blocks in X ∪ Y that are not clear, and the indexical concept T for the block on r0, if any. The other feature is the Boolean Tx that is true iff X is on the table. The module uses 7 memory states, two registers, and the following 13 rules:% Internal rules r0 := m0 ∥ {¬H, N > 0} → {Load(N, r0), T0?} ∥ m1 r1 := m0 ∥ {¬H, N = 0} → {} ∥ m6 r2 := m0 ∥ {H} → {} ∥ m5 r3 := m1 ∥ {r0 > 0} → {Load(r0, r1), T1?} ∥ m2 r4 := m2 ∥ {T1 > 0} → {Load(T1, r1), T1?} ∥ m2 r5 := m2 ∥ {T = 0} → {} ∥ m4 r6 := m3 ∥ {T0 > 0} → {} ∥ m1 r7 := m3 ∥ {T0 = 0} → {} ∥ m0 % External rules r8 := m4 ∥ {} → Unstack(r1, B) ∥ m5 r9 := m5 ∥ {} → Putdown(r1) ∥ m3 r10 := m6 ∥ {Tx} → Pickup(X) ∥ m7 r11 := m6 ∥ {¬Tx} → Unstack(X, B) ∥ m7 r12 := m7 ∥ {} → Stack(X, Y) ∥ m7Rules r0-r7 are like the ones for the indexical policy π * on . The external rules, however, are do-rules that apply ground actions to remove blocks above r0, and to pick X and put it on Y. The Boolean Tx is used to decide whether to use a Pickup or Unstack action to grab X.Example 5 shows the module tower(O, X) for building a given tower of blocks, expressed by the object pairs in O to put in place on top of the block X. The indexical features in the policy, namely M and W, are conceptually simple. The module calls the modules on-table(X) and on(X, Y), and also calls itself making it a recursive module. The module on-table(X), that puts the block in the singleton X on the table, is not spelled out.Example 5: Module tower(O, X)The module tower(O, X) is aimed at the class Qtower of problems where blocks are to be stacked in a single tower on the table. The goal is described by a conjunction of atoms ∧ k i=1 on(xi, xi-1) and ontable(x0). The module is the tuple ⟨⟨O, X⟩, Z, M, R, Φ, m0, R⟩ where O is a role argument whose denotation contains the pairs {(xi, xi-1) | i = 1, ..., k}, and X is a concept argument that denotes the lowest block in the target tower that is misplaced. a The other elements in the module are Z = ∅, M = {m0, m1, . . . , m3}, R = {r0}, and a set of features Φ = {M, W} where M is the indexical concept that contains the block to be placed above the block in r0 according to O, if any, and, W is the indexical concept that contains block directly below the block in r0, if any, also according to the target tower O. The rules in R are:% Module tower(O, X) r0 := m0 ∥ {X > 0} → {Load(X, r0), M?, W?} ∥ m1 r1 := m1 ∥ {W = 0} → on-table(r0) ∥ m2 r2 := m1 ∥ {W > 0} → on(r0, W) ∥ m2 r3 := m2 ∥ {M > 0} → tower(O, M) ∥ m3where r0 puts the lowest misplaced block in r0, r1 calls the module on-table(r0) to place r0 on the table, r2 calls the module on to place r0 on W, and r3 recursively calls with the block that is supposed to be on r0.a Block x is well-placed in state s iff x is on y if the pair (x, y) is in O, and recursively, y is well-placed; it is misplaced iff it is not well-placed. In the example, it is also assumed that the lowest block of the target tower must be placed on the table . Finally, Example 6 shows the module blocks(O) that solves arbitrary instances of Blocksworld. It works by calling the module tower(O, X) with parameter X being the singleton that contains the lowest misplaced block in one of the current towers. Such a block is chosen from the concept L that is a concept of higher complexity. A more involved implementation is able to remove the dependency on L by first putting a mark on a block x such that on G (x, z) differs from the atom on(x, y) that is true at the current state, and then moving such feature down with a loop. The execution model for modules is captured by the SIW M algorithm in Fig. 4 which uses a stack and a caller/callee protocol, as it is standard in programming languages. It assumes a collection {mod 0 , mod 1 , . . . , mod N } of modules where the "entry" module mod 0 is assumed to take no arguments. The execution may involve solving classical planning subproblems, internal operations on the registers, calls to other modules, or execution of ground actions. The modules do not share memory states nor registers, but they may all act on the planning states s.At each time point during execution, there is a single active module mod ℓ that defines the current set of rules, and there is a current augmented state (s, m, v). While no call or do rule is selected, SIW M behaves exactly as SIW * R . However, if a call rule (m, C) → (mod j (x 1 , x 2 , . . . , x n ), m ′ ) is chosen, where mod j refers to ⟨args, Z, M, R, Φ, m 0 , R, ⟩, the following steps are done:1. Push context (ℓ, v, m ′ ) where v is value for registers, 2. Set value of arguments of mod j to those given by x i , 3. Set memory state to m 0 (the initial state of mod j ), 4. Set the current set of rules to R, 5. [Cont. execution of mod j until no rule is applicable], and 6. Pop context (ℓ, v, m ′ ), set value of registers to v, memory state to m ′ , and rules R to those in mod ℓ .Similarly, if do rule (m, C) → (name(x 1 , x 2 , . . . , x n ), m ′ ) is chosen, an applicable ground action name(o 1 , o 2 , . . . , o n ) at the current state s with the object o i in x i , 1 ≤ i ≤ n, is applied and the memory state is set to m ′ . If no such ground action exists, an error code is returned. The SIW M interpreter has been implemented and all extended, indexical policies and sketches have been tested. We will make the code and the examples available.A basic, concrete question about policy reuse in a planning setting is: Can a policy for putting one block on top of another be used for building any given tower of blocks, and eventually any block configuration? The question is relevant because it tells us that policies for building given towers and block configurations do not have to be learned from scratch,Algorithm 4: Execution model SIW M for modules 1: Input: Collection M = {mod0, mod1, . . . , modN } of modules with entry module mod0 2: Input: Planning problem P with initial state s0 on which the features in Φ are well defined 3: Initialize stack 4: Let R j , m j 0 , and R j be the set of registers, initial memory, and rules of modj, j = 0, 1, . . . , N 5: ℓ ← 0, R ← R ℓ , and s ← (s0, m ℓ 0 , v) for v ∈ Obj(P ) R ℓ 6: while s in s = (s, m, v) is not a goal state of P 7:if m is internal memory 8:Find but that they can be learned bottom up, from simpler to complex, one after the other (Ellis et al. 2023 ). The subtlety is that in order for complex policies to use simpler policies, the former must pass the right parameters to the latter depending on the context defined by the top goal and the current state. In this work, we have developed a language for representing policies and sketches, and this form of hierarchical composition.rule r = (m, C) → (E, m ′ ) with s, v ⊨ C 9: if r is not found 10: if stack is empty, return FAILURE % Stalled 11: Pop context (j, v ′ , m ′ ) from stack 12: ℓ ← j, R ← R ℓ , m ← m ′ and v ← v ′ 13: else 14: if Load(C, r) in E, v[r] ← o for some o ∈ C(s, v) 15: s ← (s, m ′ ,We have also addressed another source of complexity when learning general policies and sketches: the complexity of the features involved. We have shown that indexical features whose values depend on the content of the registers, that can be dynamically loaded with objects, can be used to drastically reduce the complexity of the features needed, in line with the intuition of the so-called deictic representations, where a constant number of "visual marks" are used to mark objects so that they can be easily referred to (Chapman 1989; Ballard et al. 1996; Finney et al. 2013 ). In our setting, an object can be regarded as marked with r when the object is loaded into register r.The use of registers and concept features allows for general policies that map states into ground actions, even if the set of ground actions change from instance to instance. This is different than general policies defined as filters on state transitions (Bonet and Geffner 2018; Francès, Bonet, and Geffner 2021) , which require a model for determining the possible transitions from a state. Policies that map states into actions are more conventional and can be applied modelfree.The achieved expressivity is the result of three extensions in the common language of policies and sketches: internal memory states, like in finite state controllers for sequencing behaviors, indexical concepts and features, whose denotation depends on the value of registers that can be updated, and modules that wrap up policies and sketches and allow them to call each other by passing parameters as a function of the state, the registers, and the goals (represented in the state).The language of extended policies and sketches adds an interface for calling policies and sketches from other policies and sketches, even recursively, as illustrated in the examples. The resulting language has elements in common with programming languages and planning programs (Aguas, Celorrio, and Jonsson 2016; Segovia-Aguas, Jiménez, and Jonsson 2019, 2021) , but there are key differences too. In particular, the use of a rich feature language does not limit policies and sketches to deal with classes of problems with a fixed goal and the policy and sketch modules do not have to represent full procedures or policies; they can also represent sketches where "holes" are filled in with a polynomial IW search when the sketches have bounded width.Provided with this richer language for policies and sketches, the next step is learning them from small problem instances, adapting the methods developed for standard sketches (Drexler, Seipp, and Geffner 2022) . We want to learn hierarchical policies bottom-up by generating and reusing policies, instead of learning them top-down (Drexler, Seipp, and Geffner 2023) .For each predicate p appearing in the goal, a new predicate pG is introduced with the same arity as p. The atom p(c) in the state s means that p(c) is true in s, while pG(c) in s means that p(c) must be true in the goal. 
 
 Appendix:  


Decision: Clear case. Congrats!

I vote acceptance as poster here as the contribution seems rather technical and specific to a small subset of the community,

Reviews: review: strength_weakness: strength_weakness: I really only have two very minor, and fixable, complaints of the paper:

First, please list algorithms using the standard AAAI form (using horizontal lines, similar to a listing and not as a subfigure within a box).  I thought the use of boxes for the _examples_ was really eye-catching and novel.  But the use of the same kind of boxes for algorithms is very confusing.  I guess I'm so accustomed to seeing algorithms presented in AAAI format as their own blocks, separate from figures and tables, that this one threw me.  And to have those boxes listed inside a figure seemed more odd to me.  

Second, I found the citation of a yet unpublished 2023 arxiv paper as the first citation to weaken this paper.  There are several new results in that paper, it's 40 pages long, and ... it's on arxiv instead of a journal or conference.  Yes, I get the message that this is probably under submission to a journal, and, yes, I understand that some of those results are central to this paper.  If I could suggest a slightly different approach: perhaps you could cite the AAAI 2021 paper in the main body and add a footnote that states there are two _substantial_ extensions to the original work (using the arxiv references mentioned above).  Or maybe you could cite all three as independent references.  Either way, this would add two more references to your paper and give a fuller picture of the trajectory of this really interesting line of work.  

(This almost a non-issue point, but I have always found it hard to read s' \prec s.  It just looks so wrong to me even after I read the descriptions from the original paper and the extensions.)
questions: questions: None
strength_weakness: strength_weakness: Maybe describing a brief case study that shows how the algorithms work would result in a more robust version of the paper.
questions: questions: I understand that the definition of this kind of language allows an agent to learn basic procedures and generalize the resolution of more complex tasks. However, what do you think about how the use of these modules may affect the optimality of the obtained plans?

Have you implemented the algorithms that you introduced in the paper? If so, can you give an example of how a planning problem can be solved?
strength_weakness: strength_weakness: The paper is of pure theoretical nature in that it only addresses the "representation problem". 
The "learning problem" remains open.
Ultimately, this raises the question whether the proposed contribution will be of any practical usage.
questions: questions: In many contexts policies are part of the problem structure to be analyzed, e.g, "Does the policy reach the goal when executed from start?".
The SIW_R algorithm uses (problem decomposition based on) sketch R -- a policy representation -- to solve P. 
For a reader less familiar with your line of research, it might be helpful to explicitly state, that, here, the set of possible goal paths is not restricted to be compatible with R, but R guides the SIW search.

Typos:
"internal memory states, as in finite state controllers [,] indexical features" (Abstract)