Lakhasly

Computing and learning generalized patterns of behavior that address multiple related
problems is a longstanding goal in AI planning. Recent work features numerous threads
of research for addressing this problem, ranging form learning domain-wide heuristics to
learning generalized sketches and program-like generalized plans that aid computation, or
directly solve large classes of planning problems. The use of generalized plans, which utilize
cyclic control flow for generalization and scalability, has long been recognized as a vital
component in achieving this goal.
This paper addresses the problem of developing more accurate methods for assessing
the utility of generalized plans. It develops a new framework for analyzing the reachability
and termination properties of generalized plans by building upon the classic framework of
directed elimination trees (DETs) for complexity characterizations of graph structures. It
also presents a new algorithm for inductively analyzing termination properties of generalized
plans along with theoretical analysis of its correctness and empirical results on classes of
generalized plans that are not amenable to analysis using existing methods. These methods
yield new insights and algorithmic tools for use in computing reliable generalized plans.
Existing results on theoretical aspects of generalized planning, especially on determining
reachability and termination properties of generalized plans on arbitrary problem instances
have been restricted to specific types of graph structures (Srivastava, Immerman, & Zilberstein, 2012), limited dimensions of variation among problem instances (Hu & Levesque,
2010) or to limited expressiveness in the semantics of actions (Srivastava, Zilberstein, Immerman, & Geffner, 2011). While there has been immense progress in the field in recent
years (e.g., (Aguas, Jim´enez, & Jonsson, 2018; Bonet & Geffner, 2018; Illanes & McIlraith,
arXiv:2212.02823v1 [cs.AI] 6 Dec 2022
Hierarchical Termination Analysis for Generalized Planning
2019); a more complete survey is presented in the next section), we expect that methods for
more general analysis of termination of generalized plans would further enable continued
breakthroughs in the field.
Intuitively, the framework developed in this paper goes beyond existing efforts by developing a new process for the analysis of generalized plans expressed as finite-state machines
without the restrictions noted above, viz., it permits arbitrary structures and actions that
can increment or decrement variables by specific amounts in non-deterministic or deterministic control structures. These action semantics capture not only changes in Boolean state
variables but also changes in higher-order state properties or features (e.g., the number
of packages that still need to be delivered in logistics planning problems). Prior work on
generalized planning has established that such counter-based representations capture the
essence of generalized plans as needed for analysis of their utility (Srivastava, Immerman,
& Zilberstein, 2010) as well as for synthesis of generalized plans (Srivastava, Immerman, &
Zilberstein, 2008; Bonet & Geffner, 2018).
This paper shows that finite-memory policies that feature incrementing and decrementing actions can be decomposed into hierarchical strongly connected components using graphtheoretic principles. It presents a new approach for building an argument asserting termination of such policies by conducting a bottom-up analysis of these strongly connected
components, in a manner akin to analyzing “inner loops” before using those results in the
analysis of “outer loops.” Theoretical analysis and empirical results on a range of complex
finite-memory policies show that this method can effectively determine termination for a
broad class of generalized plans that could not be assessed for termination using existing approaches. It is well known that complete methods for termination assessment of generalized
plans are not possible due to the undecidability of the halting problem for Turing machines.
Our theoretical analysis shows that the methods presented in this paper are sound.
The rest of this paper is organized as follows. Sec. 2 presents a survey of related work
on the topic followed by our formal framework and the problem setting (Sec. 3). Secs. 4
and 5 present our new algorithmic framework for the analysis of generalized plans using
DETs and a formal analysis of the theoretical properties of this framework. Sec. 6 presents
empirical results followed by conclusions in Sec. 7.
2. Related Work
Recent research on computing and learning generalized knowledge for planning has led to
immense progress in generalized planning. Early work by Levesque (2005) articulated the
value and challenges of planning with iterative constructs and of proving that such constructs would terminate during execution. This work focused on settings where problem
classes are defined by varying a single numeric planning parameter. Levesque showed that
this parameter could be used to build iterative constructs. He argued that rather than attempting to assess or prove the termination of such plans, asserting weaker guarantees could
lead to computationally pragmatic approaches. Levesque proposed validation of computed
iterative plans up to a certain upper bound on the single numeric planning parameter. To
the best of our knowledge, this work constitutes the first clear articulation of the value and
challenges of computing plans with loops using AI planning related methods rather than
theorem proving.
2
Hierarchical Termination Analysis for Generalized Planning
Srivastava et al. (2008) showed that abstraction using logic-based features could be used
to identify useful loops from observed plans and that counters based on such properties
(e.g., the number of cells that need to be visited in a grid exploration task) could be used
to characterize whether such a loop would terminate. These methods were used to compute
“generalized plans” with simple loops along with proofs of correctness for arbitrary numbers
of counters that applied to infinitely many problem instances. Hu and Levesque (2010)
extended the earlier work by Levesque (2005) and showed that determining termination for
plans featuring iteration over a single numeric planning parameter is decidable.
Bonet, Palacios, and Geffner (2009) showed that the computation of finite-state controllers for some classes of planning problems could be reduced to planning by creating
meta-level planning domains whose actions involved the addition or deletion of edges in a
controller. These finite-state controllers were observed to have good generalization capabilities. Analysis by Srivastava et al. (2010) showed that the problem of identifying useful
cyclic control structures in generalized plans could be studied using primitive models of
computation such as abacus programs by transforming the planning-domain actions into
equivalent operations that changed counters corresponding to logic-based state properties.
The team developed algorithms for determining termination and graph-theoretic characterizations of generalized plans that could be assessed for termination despite the general
incomputability of the problem (Srivastava et al., 2012).
One of the main technical problems in determining termination is that it is often difficult to algorithmically determine that a complex, terminating generalized plan terminates.
The Sieve algorithm (Srivastava et al., 2011) traded off accuracy in the semantics of actions for greater computability in termination assessment for qualitative numeric planning
problems (QNPs). It showed that if the counter operations were “qualitative” or uncertain in a specific manner, the best that could be done in terms of computable termination
analysis matched the expressive power of such action semantics: any generalized plan using
such actions that could not be determined to be terminating under the qualitative analysis
conducted by this algorithm, did in fact allow for a non-terminating execution. In other
words, generalized plans using qualitative semantics have limited expressiveness and cannot
express patterns of behavior that generalized plans using deterministic semantics can. A
more formal comparison of termination under qualitative and deterministic semantics is
presented in Sec. 4.1.
QNPs were later extended by Srivastava, Zilberstein, Gupta, Abbeel, and Russell (2015)
to more general settings along with analysis showing the limited expressiveness of such controllers when compared with controllers using actions with deterministic semantics. Bonet
and Geffner (2020) showed that the analysis conducted by the Sieve algorithm for QNP
problems can also viewed as a fully observable non-determinstic (FOND) planning process. Several extensions to these foundational formulations of generalized planning have
been developed. Bonet, Giacomo, Geffner, and Rubin (2019) develop connections between
generalized planning and LTL synthesis; Belle (2022) analyzes the relationships between
various correctness criteria in stochastic and non-deterministic settings.
Several threads of research have developed methods for creating meta-level planning
problems that synthesize generalized plans in the form of controllers (Bonet et al., 2009;
Hu & Giacomo, 2011; Hu & De Giacomo, 2013). Aguas et al. (2018) present algorithms
for computing hierarchical generalized plans that include subroutines and are guaranteed
3
Hierarchical Termination Analysis for Generalized Planning
to solve an input set of finitely many planning problems. The planning domains used in
this reduction include actions that construct elements of hierarchical finite state controllers
as well as validate the resulting controllers on the input problem set. This paradigm of
evaluation using a finite validation set has been developed along multiple directions to
utilize finite sets of positive examples as well as negative examples indicating undesired
outcomes of plan execution (Aguas, Jim´enez, & Jonsson, 2020) and with finite validation
sets for use in a general heuristic search process for computing generalized plans (Aguas,
Jim´enez, & Jonsson, 2021; Aguas, Celorrio, Sebasti´a, & Jonsson, 2022).
A related direction of research explores the use of these principles for computing and
representing generalized control knowledge that does not represent deterministic generalized plans but rather auxiliary data structures that support planning for multiple related
planning problems. Such methods have been shown to be useful in the form of sketches for
planning (Bonet & Geffner, 2018; Frances, Bonet, & Geffner, 2021; Bonet & Geffner, 2021;
Drexler, Seipp, & Geffner, 2022), generalized heuristics (Karia & Srivastava, 2021) and
generalized Q-functions for reinforcement learning in stochastic settings (Karia & Srivastava, 2022). In the terminology of metrics for generalized planning presented by Srivastava,
Immerman, and Zilberstein (2011), these methods represent generalized knowledge that
has a relatively higher cost of instantiation1
than an optimized algorithmic solution would
(albeit much lesser than planning from scratch) but provide a significantly higher domain
coverage. These directions of research bridge that gap between generalized planning, lifted
sequential decision making (Boutilier, Reiter, & Price, 2001; Sanner & Boutilier, 2005, 2009;
Cui, Keller, & Khardon, 2019) and approaches for learning generalized control knowledge
and heuristics for solving multiple planning problems (Khardon, 1999; Winner & Veloso,
2003; Yoon, Fern, & Givan, 2008; Shen, Trevizan, & Thi´ebaux, 2020; Toyer, Thi´ebaux,
Trevizan, & Xie, 2020; Rivlin, Hazan, & Karpas, 2020; Garg, Bajpai, & Mausam, 2020;
Ferber, Geißer, Trevizan, Helmert, & Hoffmann, 2022; St˚ahlberg, Bonet, & Geffner, 2022).
3. Problem Formulation
We use a primitive but powerful representation where all variables are numeric variables
with N as their domains. Let V be the set of such variables.
A concrete state in a domain is an assignment that maps each variable in V to a value in
that variable’s domain. We denote the set of all possible concrete states as SV. The value
of a variable x in a state s ∈ SV is denoted as s(x). In this paper we use the unqualified
term “state” to refer to concrete states.
Definition 1. An action consists of a precondition, which maps each variable in V to a
union of intervals for that variable, and a set of action effects, effects(a). Each member of
effects(a) is of the form ⊕x or x, where x ∈ vars; effects(a) must include at most one
occurrence of each variable in V.
Prior work in generalized planning considers three types of interpretations of ⊕, that
correspond to popular frameworks in the literature (Srivastava et al., 2015). We focus on
deterministic and qualitative semantics in this work: