# blocklevel_goal_recognition_design__af8f1eb7.pdf

Block-Level Goal Recognition Design

Tsz-Chiu Au

Department of Computer Science and Engineering, Ulsan National Institute of Science and Technology chiu@unist.ac.kr

Existing works on goal recognition design (GRD) consider the underlying domain as a classical planning domain and apply modifications to the domain to minimize the worst case distinctiveness. In this paper, we propose replacing existing modifications with blocks, which group several closely related modifications together such that a block can modify a region in a search space with respect to some design constraints. Moreover, there could be blocks within blocks such that the design space becomes hierarchical for modifications at different levels of granularity. We present 1) a new version of pruned-reduce, a successful pruning rule for GRD, for block-level GRD, and 2) a new pruning rule for pruning some branches in both hierarchical and non-hierarchical design space. Our experiments show that searching in hierarchical design spaces greatly speeds up the redesign process.

Introduction In goal recognition, an observer infers the goal of an agent acting in an environment from online observations of the agent s behavior (Kautz 1987; Carberry 2001; Ramirez and Geffner 2010; Sukthankar et al. 2014; Vered and Kaminka 2017; Pereira, Oren, and Meneguzzi 2017). Goal recognition design (GRD) aims to redesign an environment such that an observer can recognize an agent s goal as early as possible (Keren, Gal, and Karpas 2014, 2020). A popular performance measure in GRD is the worst case distinctiveness (WCD), which is the number of observations an observer needs to ascertain an agent s goal in the worst case. Minimizing the WCD has practical usage in real-world applications. For example, in the airport security domain as described in (Keren, Gal, and Karpas 2014, 2020), we want to redesign the layout of an airport such that a security guard can be one step ahead of an intruder by recognizing an inappropriate goal pursued by the intruder as soon as possible. Existing works on GRD consider environments as classical planning domains and redesign environments by modifying the actions in the planning domains using action removals (Keren, Gal, and Karpas 2014) or action conditioning (Keren, Gal, and Karpas 2018). In some environments, however, several modifications must be applied simultaneously to achieve the desired effect for goal recognition. For

Copyright 2024, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Figure 1: An example of block-level GRD. An agent can choose one of the four legal paths (the red lines) to reach either g1 or g2. The blue lines are the walls.

example, Figure 1 extends the example in (Keren, Gal, and Karpas 2014) by including all the walls such that an agent is not allowed to deviate from the given paths (the red lines). We can substitute one of the three yellow blocks for the red region in the grid to prevent an agent from choosing some of the given paths. All walls in a yellow block must be added to the red region simultaneously; otherwise, an agent could deviate from the given paths via some missing walls in the red region. Action removals and action conditioning ignore this design constraint, causing the GRD algorithms to enumerate all combinations of the modifications for adding these walls. In this paper, we introduce block-level GRD that uses blocks as the primary mean of environmental modifications. A block is a group of closely related modifications that can simultaneously modify multiple edges in the search space of classical planning problems. In Figure 1, there are three blocks, each of which modifies every edge in the red region in the grid. A block-level GRD algorithm chooses one of these blocks to minimize the WCD. If it chooses b1, the remaining paths an agent can choose are p2, p3 and p4, and the WCD is 6, which is the length of the longest common prefix of p2 and p3. If the algorithm chooses b2, the WCD is also 6. But if it chooses b3, the remaining paths are p1 and p4, and the WCD is 3. Therefore, the algorithm should choose b3. We formulate a hierarchical design model that allows blocks within blocks. The block at the top level of the hierarchy lays out the structure of the environment, whereas the blocks at the bottom level implement the design. The hierarchical design model resembles hierarchical task network (HTN) planning (Erol, Hendler, and Nau 1996; Nau

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

et al. 2003, 2005) and can greatly reduce the search space of the GRD algorithms, making our approach suitable for large-scale GRD problems. In summary, our contributions are: We define a hierarchical design model for block-level goal recognition design. We modify pruned-reduce (Keren, Gal, and Karpas 2014), a highly successful pruning rule for GRD, for block-level GRD, and state the sufficient condition for returning an optimal design in breadth-first search. We introduce a new pruning rule that avoids the expansion of some regions in a hierarchical design space. This pruning rule is applicable to non-hierarchical design models as well. We devise a local search algorithm to solve much larger GRD problems than breadth-first search. This paper is organized as follows. After presenting the related work, we define the problem of block-level goal recognition design. Next, we describe the block-based pruned-reduce and the design subtree pruning rule. Lastly, we present the experimental results and conclude this paper.

Related Work GRD is a special case of environment design (Zhang, Chen, and Parkes 2009). Keren et al. proposed using the WCD as a performance measure in GRD (Keren, Gal, and Karpas 2014, 2019). Subsequently, many works extended the WCDbased GRD model to deal with non-optimal agents (Keren, Gal, and Karpas 2015), non-observable actions (Keren, Gal, and Karpas 2016a), privacy preserving in GRD (Keren, Gal, and Karpas 2016b), stochastic domains (Wayllace et al. 2016; Wayllace, Hou, and Yeoh 2017), game-theoretic GRD (Ang et al. 2017), GRD for plan libraries (Mirsky et al. 2019), partially-observable states (Wayllace et al. 2020), incomplete information (Keren 2019), information shaping (Keren et al. 2020), stochastic domains with suboptimal agents (Wayllace and Yeoh 2022), interleaving between agents and observers (Gall, Ruml, and Keren 2021), and agents with multiple goals (Au 2022). (Keren, Gal, and Karpas 2020) is a survey of the works on GRD before 2020. Some works focus on improving the performance of GRD algorithms. Keren et al. introduced pruned-reduce in their seminal paper on WCD-based GRD (Keren, Gal, and Karpas 2014). Son et al. proposed solving GRD problems by Answer Set Programming solvers, which outperforms the existing approaches for fully observable models with optimal agents (Son et al. 2016). Ang et al. formulated the problem of computing optimal strategies as a mixed integer program in game-theoretic settings of GRD (Ang et al. 2017). Keren et al. framed existing pruning methods in the context of strong stubborn sets (Keren, Gal, and Karpas 2018). However, we still need better techniques to solve large GRD problems. Our hierarchical design model resembles hierarchical task network (HTN) planning, which is more expressive than classical planning and can achieve an exponential speedup with sufficient domain knowledge to guide the planning process (Erol, Hendler, and Nau 1996). Our hierarchical design

model also contains domain knowledge of which blocks fit a region. Like methods in SHOP2 (Nau et al. 2003, 2005), this knowledge can reduce the design space tremendously. However, our hierarchical design model provides little guidance on reducing the WCD.

Preliminary Definition: Classical Planning This work is based on STRIPS planning for fully observable and deterministic environments (Fikes and Nilsson 1971). A state s is a set of fluents, each of which is a ground, functionless atom that is true in s. A planning problem is a tuple F, s0, A, G, cost , where F is a set of fluents, s0 F is the initial state, G is a set of goal states, A is a set of actions and cost is the cost function of actions. Each action is a triple a = pre(a), add(a), del(a) , where pre(a) F, add(a) F, del(a) F are the precondition, the add list, and the delete list, respectively. a is applicable to state s if and only if pre(a) s. The resultant state of applying a to s is apply(s, a) = (s \ del(a)) add(a). For simplicity, we assume the costs of all actions are the same (i.e., cost(a) = 1 for all a A). A plan π is a sequence of actions a1, a2, . . . , ak , where ai A for 1 i k. π is valid if and only if ai+1 is applicable to si where si+1 = apply(si, ai+1) for 0 i < k. The path of a valid π is the sequence of states p(π) = s0, s1, . . . , sk visited by an agent when executing π. We say a state s is reachable by a valid plan π if and only if s p(π). Hence, a goal state g G is reachable by π if and only if g p(π). Let prefix(p1, p2) be the longest common prefix of p1 and p2. Our GRD problem revolves around modifications to the search space of classical planning problems. Let S be the set of all states reachable by some valid plans in a planning problem F, s0, A, G, cost . The search space of the planning problem is a directed graph (V, E), where V is a set of vertices and E is a set of directed edges. Each state s S has a vertex v in V , and we denote v by v[s]. Likewise, we denote s by s[v] for a given v. There is an edge (v1, v2) in E whose cost is cost[v1, v2] if there is an action a A applicable to s[v1] and the resultant state is s[v2] = apply(s[v1], a). We denote a by a[v1, v2]. Then we can formulate the planning problem as a graph search problem (V, E, v0, Vgoal, cost), where (V, E) is the search space, v0 = v[s0] V is the initial vertex, and Vgoal is the set of goal vertices representing the goal states in G. The objective is to find a path p that connects v0 to one of the goal vertices while minimizing the total cost of the path. Then, we can convert p into a plan π that solves the planning problem.

Block-Level Goal Recognition Design This section defines the goal recognition design problem that uses blocks as environmental modifications.

Blocks and Regions Previous works introduced two modifications for fully observable domains: action removals (Keren, Gal, and Karpas 2014) and action conditioning (Keren, Gal, and Karpas 2018). An action removal removes an action in A, whereas an action conditioning adds additional fluents to pre(a). The

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

effect of these modifications to the search space is the removal of some edges such that some legal plans become infeasible. In this paper, we consider modifications that directly update a search space by a block, which represents a search space that can be put in a region of another search space. A block can alter multiple connectivity in a search space at once. Typically, only a few configurations in a region conform to the design constraints in an environment (see Figure 1). A block can produce these configurations directly, making the modification process more efficient. We introduce a new type of vertices called regional vertices, which represent regions that can be substituted by blocks. Let us extend the definition of search spaces to include regional vertices. An extended search space is G = (V, V r, E, Er), where V is a set of ordinary vertices that represents a set S of states (i.e., s[v] exists for all v V ), V r is a set of regional vertices that do not represent any state (i.e., s[v] does not exist for any regional vertex v V r), E is a set of edges that represents actions applicable to the ordinary states in S (i.e., a[v1, v2] exists for any (v1, v2) E if v1 V ), and Er is a set of outgoing edges of the regional vertices in V r that do not represent any action (i.e., a[v1, v2] does not exist for any (v1, v2) Er if v1 V r is a regional vertex). In short, an extended search space is a graph in which the set of vertices is (V V r) and the set of edges is (E Er). Moreover, E is the set of all outgoing edges of the vertices in V , and Er is the set of all outgoing edges of the regional vertices in V r. We shall assume the root vertex vroot and the goal vertices in Vgoal are not regional vertices. All extended search spaces must satisfy the following condition in order to maintain the semantics of the planning problem: for all edge (v1, v2) such that both v1 and v2 are ordinary vertices, s[v2] = apply(s[v1], a[v1, v2]).

Substituting Blocks for Regional Vertices

The specification of a block b1 is (V1, V r 1 , E1, Er 1, V entry 1 , V exit 1 ), where G1 = (V1, V r 1 , E1, Er 1) is an extended search space, V entry 1 (E1 Er 1) is a set of entry vertices, and V exit 1 (E1 Er 1) is a set of exit vertices. Let us consider another extended search space G2 = (V2, V r 2 , E2, Er 2) with a regional vertex vr V r 2 , and we are going to substitute b1 for vr. Let Ein r = {(v1, vr)}v1 (V2 V r 2 ) be the set of incoming edges of vr and Eout r = {(vr, v2)}v2 (V2 V r 2 ) be the set of outgoing edges of vr in G2. Let V in r = {v1}(v1,vr) Ein r and V out r = {v2}(vr,v2) Eout r be the sets of vertices on the edges, excluding vr, in Ein r and Eout r , respectively. We say the vertices in V in r and V out r the incoming vertices of r and the outcoming vertices of r, respectively. After the substitution of b1 for vr, G1 and G2 are merged into a new search space G3 in which vr is replaced with the G1 with some new edges between V in r and V entry 1 as well as between V exit 1 and V out r . These new edges are specified by three given parameters: 1) Kin V in r V entry 1 is a set of edges that enter b1; 2) Kout V exit 1 V out r is a set of edges that leave b1; and 3) Kaction is a mapping from Kout ordinary to A, where Kout ordinary = Kout (V1 V out r ) is the set of edges in Kout whose start vertices are ordinary vertices in V1.

Definition 1 We say b1 is fit for vr in G2 with Kin, Kout, and Kaction if and only if 1) for all (v1, v2) Kin s.t. v1 V2 and v2 V1, apply(s[v1], a[v1, vr]) = s[v2]; and 2) for all (v1, v2) Kout s.t. v1 V1 and v2 V2, apply(s[v1], Kaction((v1, v2)) = s[v2]. These conditions are used to maintain the semantics of the planning problem: for any edge (v1, v2) in Kin or Kout, if both v1 and v2 are ordinary vertices, the resultant state after applying the action represented by the edge must be the same as s[v2]. Note that there is no restriction on any edge (v1, v2) in Kin or Kout if either v1 or v2 is a regional vertex. Given a block b1 that is fit for vr in G2 with Kin, Kout, and Kaction, we can substitute b1 for vr to create a new extended search space G3 = (V3, V r 3 , E3, Er 3), where

V3 = V1 V2, V r 3 = (V r 1 V r 2 ) \ {vr}, E3 = [(E1 E2) \ E4] (E6 E7), Er 3 = [(Er 1 Er 2) \ (Er 4 Er 5)] (Er 6 Er 7), E4 = {(v1, vr)}(v1, vr) Ein r and v1 V2 Er 4 = {(v1, vr)}(v1, vr) Ein r and v1 V r 2 Er 5 = {(vr, v1)}(vr, v1) Eout r E6 = {(v1, v2)}(v1, v2) Kin and v1 V2 Er 6 = {(v1, v2)}(v1, v2) Kin and v1 V r 2 E7 = {(v1, v2)}(v1, v2) Kout and v1 V1 Er 7 = {(v1, v2)}(v1, v2) Kout and v1 V r 1

This substititon removes the edges in E4, Er 4, and Er 5 from G1 and G2, and then adds the edges in E6, Er 6, E7, and Er 7 to G3. The only vertex that is removed is vr. We denote this substitution by G3 = Subst(G2, vr, b1, Kin, Kout, Kaction).

Hierarchical Design Models We define a hierarchical design model based on blocks and regions as follows. If the extended search space G = (V, V r, E, Er) of a block b has some regional vertices (i.e., |V r| 1), every vi V r can be substituted by another block bj fit for vi with given Kin j , Kout j , and Kaction j . We say bj is a feasible block for vi, and bj is a child block of b. In our design model, the set of all feasible blocks for vi, together with the corresponding Kin, Kout, and Kaction that make the feasible blocks fit for vi, is given. We denote the set of feasible blocks for vi by dom(vi), called the domain of vi. We assume the domain of a regional vertex must have at least one feasible block. We also assume each block can be uniquely identified. Hence, each block bj belongs to the domain of only one regional vertex that is denoted by v[bj]. Since Kin j , Kout j , and Kaction j for every bj are given, we shall omit them when we substitute bj dom(v[bj]) for v[bj] from now on. Thus, we write Subst(G, v[bj], bj, Kin j , Kout j , Kaction j ) as Subst(G, bj). Figure 2 shows a hierarchical design model. At the top level, there is a root block broot. For the completeness of our definition, we define a special vertex vdummy = v[broot] and its domain contains broot only. In the specification of broot,

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

Figure 2: A hierarchical design model. The red arrows represent a design tree in the model. The blue arrows denote the inclusion of non-open regional vertices in the design tree.

we set V entry = {v0}, V exit = {v[g]}g G, V in r = {vdummy} and V out r = {vdummy}, where v0 = v[s0] is the initial vertex. Note that v0 and the goal vertices in Vgoal must be ordinary vertices in broot. Every block b except broot has a parent parent[b]. Similarly, every block can have child blocks unless the block is a terminal block with no regional vertex. We shall assume there is no cycle of blocks within blocks ; thus, a hierarchical design model is finite. A design path from b0 to bm is a sequence b0, b1, . . . , bm of blocks, where bi = parent[bi+1] for 1 i < m. Since every block b is uniquely identified, there is one and only one design path broot, b1, . . . , bm 1, b from broot to b. Let ancestor[b] = broot, b1, . . . , bm 1 be the ancestors of b, where parent[b] = bm 1. A design tree Θ is a set of blocks such that Θ contains all blocks on the design path from broot to every block in Θ. Another way to define Θ is that Θ is a design tree if and only if parent[b] Θ for every b (Θ \ {broot}). In Figure 2, a red arrow (v, b) denotes the choice of a feasible block b in dom(v) of a regional vertex v. The set of all red arrows constitutes a design tree. A design tree s root is always broot. By contrast, the root of a design subtree can be any block. A design subtree of b is Θ(b), which is a set of blocks that contains all blocks on the design path from b to every block in Θ(b). If Θ(b) is a design subtree of b, parent[b ] Θ(b) for every b (Θ(b)\{b}). A design tree is a design subtree of broot. We denote the set of child blocks of a block b in Θ(b) by children[b ] = {b }b Θ(b) and parent[b ] = b . We say b is full if |children[b ]| = |V r| where V r is the set of regional vertices in b . A terminal block b is always full since it has no regional vertex and children[b] is empty. A design subtree Θ(b) is full if every block in Θ(b) is full; otherwise, Θ(b) is partial. The design tree in Figure 2 is full since all outgoing arrows of all blocks in the design tree are blue arrows. We say the blocks in Θ(b), excluding b, are subblocks of b in Θ(b). A block b is a possible subblock of b if and only if there exists a design subtree Θ(b) such that b is a subblock of Θ(b). Let Bsub(b) be the set of all possible subblocks of b. We can construct Bsub(b) by depth-first search in the hierarchical design model starting from b: whenever the depthfirst search visits a block b for the first time, it adds b to Bsub(b) if b = b, and then visits all child blocks of b . Let Ball = Bsub(broot) {broot} be the set of all blocks. A design tree Θ specifies which feasible block in dom(v)

should substitute for the corresponding regional vertex v in Θ. The result of the substitutions is a new extended search space G(Θ). G(Θ) can be constructed by depth-first search in Θ starting from the root of Θ. Initially, G is the extended search space of broot. Whenever the depth-first search visits a new block b in Θ, it replaces G with Subst(G, b). The replacement would succeed since all ancestors of b have been visited previously, and v[b] must be present in G. Ultimately, the depth-first search returns G(Θ). If Θ is full, G(Θ) has no regional vertex. If Θ is partial, we say the regional vertices in G(Θ) are open in Θ. For any open regional vertex v in Θ, we can extend Θ by adding a feasible block b dom(v) to Θ to form Θ = Θ {b}, which is also a design tree.

Legal Paths

An assumption in GRD research is that an agent cannot move freely but follow a given set Πleg of legal plans whose paths can be either the shortest paths to some goals (Keren, Gal, and Karpas 2014), some feasible paths subject to physical constraints (Au 2022), or some paths in a path library (Mirsky et al. 2019). Note that legal plans do not have to be optimal or near-optimal. Let P leg be the set of legal paths traversed by an agent when executing the legal plans in Πleg starting at the initial state s0. The last state last[p] of a legal plan p Πleg must be a goal state, denoted by g[p]. By the definition of goal states, no two goal states share the same state. Hence, each vertex on a legal path p P leg has at most one goal state. We assume an agent who chooses p aims for g[p] in the last state last[p] only and ignores the other goal states before last[p] on p. We also assume that a legal path p has no cycle (i.e., v1 = v2 for any v1, v2 p). Given a design tree Θ, a legal path p P leg is valid in Θ if and only if p exists in G(Θ) = (V, V r, E, Er), i.e., (v1, v2) E for all (v1, v2) edges(p) where edges(p) is the set of edges in p. Given a valid legal path p in Θ, we say the goal g(p) is reachable by p in Θ. A design tree Θ is encompassing if every goal in G is reachable by some valid legal path p P leg in Θ, i.e., G = {g[p]}p P leg and p is valid in Θ. The encompassment of design trees is important because we only consider design trees where all goals are reachable by some legal paths.

The Block-Level GRD Problem

According to (Keren, Gal, and Karpas 2020), a goal recognition design (GRD) model is a pair T = R0, D , where R0 is an initial goal recognition model, and D is a design model, which is a tuple M, δ, ϕ, U , where M is a set of atomic modifications, δ is a modification transition function, ϕ is a constraint indicator, and U is an evaluation function for the goal recognition models. In this paper, a goal recognition model R is a design tree Θ, which can be either full or partial. The initial goal recognition model R0 is Θ0 = {broot}. In our context, D is M, δ, ϕ, U , where 1) M = (Ball \ {broot}) is the set of all blocks except broot; 2) δ is a transition function that maps a design tree Θ to a new design tree after adding a new block to Θ to replace an open regional vertex in Θ; 3) ϕ checks whether a block adding to Θ is in the domain of an open regional vertex in Θ; and 4)

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

U is the worst case distinctiveness WCD(R) = WCD(Θ), which represents the maximal cost of a non-distinctive path, which is a path an agent can follow without revealing its goal (Keren, Gal, and Karpas 2020). In this paper, we assume the costs of all actions are the same, and therefore the WCD is the maximal length of a non-distinctive path. More precisely,

WCD(Θ) = WCD(Θ, P leg valid) = (2)

maxp1, p2 P leg valid and p1 = p2 |prefix(p1, p2)| if Θ is encompassing otherwise,

where P leg valid is the set of all valid legal paths in Θ and prefix(p1, p2) is the longest common prefix of the paths p1 and p2. The objective of a design algorithm is to find an optimal design tree Θ such that WCD(Θ) is minimized (i.e., for all Θ = Θ , WCD(Θ ) WCD(Θ)).

Block-Based Pruned-Reduce

The seminal paper on GRD introduced two algorithms for finding an optimal design with the minimum WCD (Keren, Gal, and Karpas 2014). The first algorithm is a breadth-first search (BFS) called exhaustive-reduce, and the second algorithm extends exhaustive-reduce with pruned-reduce, a pruning rule that avoids expanding nodes that cannot reduce the WCD. This section presents a new version of prunedreduce for block-level GRD problems. First, we devise a BFS to explore the space of design trees. Initially, the queue in the BFS contains Θ0 = {broot}. In each iteration, the BFS extracts the first design tree Θ from the queue. If Θ is encompassing (i.e., all goals are reachable in Θ) and WCD(Θ) < WCD(Θ ) where Θ is the current best design tree, the BFS sets Θ to Θ. Next, if Θ is partial, the BFS creates a new design tree Θ for every feasible block for every open regional vertex in Θ, and adds Θ to the end of the queue. The BFS continues until the queue is empty and then returns Θ whose WCD(Θ ) is minimum. The algorithm s time complexity is O(mh), where m is the maximum number of regional vertices in a block and h is the maximum height of design trees. The pseudocode of the BFS can be found in the technical appendix. Pruned-reduce is an effective pruning rule for GRD algorithms. According to Theorem 5 in (Keren, Gal, and Karpas 2014), a successor node in a BFS with pruned-reduce is created only for actions that appear in the legal paths that yield the WCD. However, we cannot directly apply pruned-reduce to block-level GRD due to two issues. First, pruned-reduce is applicable only when modifications do not add new actions to the goal recognition model because the new edges in the search space could increase the WCD. However, when a block substitutes for a region, the block can contain new edges that are added to the search space. Second, even if a block b does not contain any action that can modify the legal paths that yield the WCD, some of its possible subblocks may contain such action. Therefore, it is necessary to look into the possible design subtrees of b to decide whether b can reduce the WCD.

Based on our definition of blocks and regional vertices, the first issue does not exist. Since regional vertices do not invalidate any legal paths, a regional vertex can be considered an empty search space that allows legal paths to pass through. When we substitute a block b for a regional vertex v, the new edges in b still permit the legal paths that rely on the edges to pass through. By contrast, if an edge e in a legal path p is missing in b and e does not present in some possible subblocks of b even e is in the subpath of p that lies inside b, the legal path will be invalidated. Therefore, the effect of the substitution is like removing these missing edges from the search space covered by the regional vertex. When the BFS extends the first design tree Θ in the queue where Θ is partial and has some open regional vertex v, the substitution of a feasible block b dom(v) for v is like the removal of these missing edges in b simultaneously. If an edge e in a legal path p is missing in b and e presents in some possible subblocks of b, the BFS will later expand the design subtrees that contain these possible subblocks of b unless these design subtrees are pruned.

Possible Invalidation of Legal Paths

To address the second issue, we consider the exact condition under which a block could remove some actions in legal paths. A block b with an extended search space G = (V, V r, E, Er) supports a path p if and only if for all (v, v ) edges(p) s.t. v V , (v, v ) (E Kout). That is, if the start vertex of an edge in p is in G, the edge should also be in G or Kout. Note that b still supports p even if no edge in edges(p) has a start vertex in V . By contrast, b invalidates p if and only if b does not support p. More precisely,

Definition 2 b invalidates a legal path p if and only if there exists (v, v ) edges(p) s.t. v V but (v, v ) (E Kout).

If b invalidates p and b is added to a full design tree Θ, p cannot exist in G(Θ) due to the missing edges in b. Even if a block b does not invalidate a path p, some of the possible subblocks of b may still invalidate p if p has edges that enter the regional vertices of b. Hence, the exact condition under which a block will certainly invalidate a legal path p regardless of the choice of the design subtree of b is:

Definition 3 A block b necessarily invalidates p if and only if there exists at least one subblock b in every possible design subtree Θ(b) such that b invalidates p.

We can use necessary invalidation for pruned-reduce: when the BFS creates a new design tree Θ = Θ {b} where b dom(v) for an open regional vertex v in Θ, the BFS chooses not to add Θ to the queue if b does not necessarily invalidate the legal paths that yield the WCD in Θ since Θ cannot reduce the WCD. In fact, WCD(Θ ) = WCD(Θ) according to Theorem 5 in (Keren, Gal, and Karpas 2014). However, it is costly to check the condition of necessary invalidation since this involves an enumeration of all possible design subtrees of b. Hence, we propose a weaker condition that can be computed quickly. A block b necessarily supports a path p if and only if all the blocks in all possible design subtrees of b support p. By contrast, b possibly invalidates p if b does not necessarily support p. More precisely,

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

Definition 4 A block b possibly invalidates a legal path p if and only if there exists a design subtree of b in which there exists a block that invalidates p.

We can precompute the set Binvalid(p) of blocks that possibly invalidate a legal path p P leg. Initially, Binvalid(p) is empty for all p P leg. For all block b Ball, find P leg invalid(b) P leg, which is the subset of legal paths invalidated by p according to Definition 2. For every p P leg invalid(b), we add b and all blocks in ancestor[b] to Binvalid(p). Finally, we obtain Binvalid(p) for every p P leg. We use Binvalid wcd = S p Pwcd Binvalid(p) for pruned-reduce, where Pwcd is the current set of legal paths that yield the current minimum WCD. As shown in its pseudo-code, the BFS prunes the new design tree Θ = (Θ {bk}) if bk is not in Binvalid wcd . If Θ is not pruned, bk possibly invalidates the legal paths that yield the WCD but does not necessarily invalidate these legal paths, and Θ may or may not reduce the WCD. However, it is safe to keep more design subtrees in the queue so that the BFS can later find out whether some extensions of these design subtrees can reduce the WCD.

Pruning Design Subtrees In this section, we devise a new pruning rule to avoid the expansion of the design subtrees for some regional vertices.

The Lower and Upper Bounds of Relative WCDs Let P be a set of subpaths of legal paths that go through the extended search space of b s.t. all subpaths in P enter b from the same entry v1 of b and exit b from some exits of b. We combine the subpaths in P to form a legal path tree T by merging the longest common prefix prefix(p1, p2) of every pair of subpaths (p1, p2) in P. The root of T is v1, whereas the terminal vertices of T are some exits of b. We say the last vertex of prefix(p1, p2) a junction in T for any p1, p2 P. We want to compute the lower and upper bounds of the relative WCD of every vertex v in T regardless of design trees. The relative WCD is defined as follows:

Definition 5 The relative WCD of a vertex v in a legal path tree T for a given design tree Θ is RWCD(Θ, v) = WCD(Θ, P ) +1, where P is the set of subpaths in the subtree T of v in T such that every p P is a path from v to a terminal vertex in T and p is valid in Θ.

If v is the initial vertex vroot and the legal path tree T is formed by P leg, we have WCD(Θ) = RWCD(Θ, vroot) 1. Suppose the relative WCDs of the terminal vertices of T for a design tree Θ are given. We can recursively compute the relative WCDs of the internal vertices of T for Θ as follows. Let P P be the set of subpaths that are valid in Θ. Let T be a legal path tree formed by merging the subpaths in P . For every v (T \ T ), RWCD(Θ, v) is undefined since v is unreachable from v1 in Θ. The relative WCD of a vertex v in T is:

RWCD(Θ, v) = (3) 1 + maxv children[v] RWCD(Θ, v ) if |P (v)| > 1 0 otherwise,

where children[v] is the child vertices of v in T and P (v) is the set of paths in P s.t. v p P . Note that P (v) is non-empty since v is in T . Since RWCD(Θ, v ) is given for every terminal vertex v in T , we can use Equation 3 to compute RWCD(Θ, v) for every internal vertex v in a bottom-up fashion by depth-first search. If |P (v)| > 1, the paths in P (v) cannot be distinguished at v yet, and hence the relative WCD of v is one plus the maximum of the relative WCDs of its children. If |P (v)| = 1, there is only one path p in P that goes through v, and p can be identified at v and the relative WCD of v is 0. If we do not know the relative WCDs of the terminal vertices of T given a design tree Θ, we cannot calculate the relative WCDs by Equation 3. However, if we are given the lower bound Li and the upper bound Ui of the relative WCDs of every terminal vertex vi in T, we can use Equation 3 to compute the lower and upper bounds of the relative WCDs of the internal vertices in T. Let Bsub(b) be the set of all possible subblocks of b. Bsub(b) can be constructed by depth-first search as described previously. Let P min P be the subset of subpaths in P that are not invalidated by any block in Bsub(b). Let T min be the legal path tree formed by merging the subpaths in P min. Since P min is the smallest set of subpaths in P that is not invalidated by any block in any design tree, the relative WCDs of every internal vertex vj T min computed by Equation 3 using Li as the relative WCDs of every terminal vertex vi is the lower bound Lj of the relative WCD of vj in any design tree. For every vertex vj in T but not in T min, we set the lower bound Lj of the relative WCD of vj to 0. By contrast, since P is the largest set of subpaths before considering any invalidation, the relative WCDs of every internal vertex vj T computed by Equation 3 using Ui as the relative WCDs of every terminal vertex vi is the upper bound Uj of the relative WCD of vj in any design tree. The technical appendix contains an example illustrating the calculation of the lower and upper bounds. The calculation of Lj and Uj depends on the Li and Ui of every terminal vertex vi in T. Both Li and Ui can be calculated by Equation 3 using the lower and upper bounds of the relative WCDs of the vertices children(vi) in the legal paths that go through vi. If we compute the bounds of the relative WCDs of the blocks in the hierarchical design model in a top-down fashion, parent[b] of a block b is evaluated before b. Then we can obtain the lower and upper bounds of the relative WCDs of the vertices in children(vi) from V out of the regional vertex v(b) in parent[b].

Design Subtree Pruning Rule We can use the lower and upper bounds of relative WCDs in b to avoid the expansion of the design subtrees in b. Let Li and Ui be the lower bound and the upper bound of a vertex vi in T formed by a set P of subpaths of legal paths that go through the extended search space of b. Let T compact be the compact path tree of T. T compact is like T except that some ordinary vertices in T are replaced by regional vertices in b when these ordinary vertices lie inside these regional vertices. Due to space limits, we put the discussion on how to construct T compact from T in the technical appendix. First, for every junction v in T, if there are v1, v2 children(v)

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

such that L1 > U2, we mark all regional vertices in the subtree of v2 in T compact as pruned . For every regional vertex vr that is marked as pruned , if all instances of vr in T compact are also marked as pruned , we insert vr into a set Pruned Regions(b). Then, the BFS prunes the design subtrees by not extending any open regional vertex in Pruned Regions(b). We can avoid extending these regional vertices because the relative WCD of v2 is always lower than the relative WCD of v1 regardless of the design subtrees of the regional vertices in Pruned Regions(b). Therefore, the vertex that yields the minimum WCD will not be found in the subtree of v2 in T. Hence, there is no need to expand the design subtrees of the pruned regional vertices in the subtree of v2 in T. If we can avoid expanding some large design subtrees, the GRD algorithms can speed up tremendously. The pseudocode of the BFS with the design subtree pruning rule can be found in the technical appendix.

Empirical Evaluation We conducted two experiments to evaluate the pruning rules and compare the BFS with a local search algorithm. The local search algorithm is based on the min-conflict heuristics (Minton et al. 1992; Sosiˇc and Gu 1994), a highly effective heuristics for constrained optimization problems, and it can return a suboptimal design tree quickly. The local search algorithm s pseudocode can be found in the technical appendix. Experiment 1 compared the local search algorithm with the original BFS in (Keren, Gal, and Karpas 2014) and our BFS. Experiment 2 evaluated the performance of the pruned-reduce and the design subtree pruning rule. Experimental Setup We adopted four domains in the International Planning Competition: LOGISTICS, GRID, DEPOTS, and DRIVERLOG. We selected these domains because we could easily add hierarchical design models to them. For each domain, we implemented a problem generator that can also generate a hierarchical design model for each problem instance. In each domain, we generated 30 problem instances of different sizes, and for each problem instance, we generated n goals, where 2 n 10 and n increases with the problem size. Then, we used a planner called Fast Downward (Helmert 2006) to find a legal plan and the corresponding legal path for each goal. We randomly deleted some actions on the legal plans and ran Fast Downward again to find legal plans that were slightly different from the previous ones. Ultimately, the number of legal paths in P leg was around 5 n. In Experiment 1, we used three GRD algorithms: 1) the original BFS with pruned-reduce as described in (Keren, Gal, and Karpas 2014), 2) our BFS that utilizes hierarchical design models and uses both prunedreduce and design subtree pruning, and 3) the local search algorithm with design subtree pruning and a pruned-reducelike heuristic. We ran the algorithms to solve the problem instances and reported the average execution times and the average minimum WCDs in Tables 1. In Experiment 2, we ran our BFS in three scenarios: 1) without pruning rules, 2) with pruned-reduce only, and 3) with both pruned-reduce and design subtree pruning. We ran the algorithm to solve the problem instances and reported the average execution times in Table 2. Both experiments were conducted on an

Original BFS Our BFS Local Search Time WCD Time WCD Time WCD LOGISTICS 23.67 8.0 2.48 8.0 0.43 8.5 DEPOTS 17.29 4.2 0.80 4.2 0.24 4.2 GRID 37.64 8.5 3.24 8.5 0.52 8.6 DRIVERLOG 16.80 7.7 0.77 7.7 0.15 7.9

Table 1: The average execution times of the BFS (in second) and the average minimum WCDs in Experiment 1.

No Pruning Pruned-reduce P.R. + D.S.P. LOGISTICS 20.80 2.61 2.48 DEPOTS 5.25 0.89 0.80 GRID 33.02 3.55 3.24 DRIVERLOG 5.17 0.82 0.77

Table 2: The average execution times of the algorithms (in second) in Experiment 2.

Apple laptop with an M1 CPU and 16GB RAM.

Results In Table 1, we can see that our BFS with prunedreduce and design subtree pruning outperforms the original BFS with pruned-reduce by around an order of magnitude. Hence, our hierarchical design model can substantially reduce the size of the search space. The local search algorithm was much faster than the original BFS and our BFS, whereas its average minimum WCDs were not much larger. In Table 2, we can see that both pruning rules can speed up the BFS, but the performance improvement from design subtree pruning was much smaller than that from pruned-reduce. The effectiveness of design subtree pruning depends on how many design subtrees are pruned and how large the pruned design subtrees are. Perhaps there were not many junctions in the legal path trees that satisfy the condition of the design subtree pruning rule in our hierarchical design models. Therefore, the performance gain of the design subtree pruning rule is less than that of block-based pruned-reduce.

Conclusions and Future Work In this paper, we introduced the concept of blocks, which allows us to enforce some design constraints among modifications in deterministic GRD. Based on blocks and regions, we defined a hierarchical design model that can greatly reduce the search space of GRD problems. Our block-based prune-reduce is highly effective, whereas the effectiveness of the design subtree pruning rule depends on the locations of junctions in the legal path trees and the size of the design subtrees. Despite its name, the design subtree pruning rule is also applicable to non-hierarchical design models, which can be viewed as hierarchical design models with one layer of blocks, each of which contains exactly one modification. For many years, pruned-reduce has been the only pruning rule we know for GRD. Our design subtree pruning rule is another pruning rule for hierarchical and non-hierarchical design models. Block-level GRD offers a new way to think about the structure of environments for GRD. In the future, we intend to combine our hierarchical design model with hierarchical plans in HTN planning and extend our model with sensing actions for partial observability.

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

Acknowledgments

This work has been taken place at UNIST and was supported by NRF (2022R1A2C101216812).

Ang, S.; Chan, H.; Jiang, A. X.; and Yeoh, W. 2017. Game Theoretic Goal Recognition Models with Applications to Security Domains. In Game Sec 2017, 256 272. Au, T.-C. 2022. Extended Goal Recognition Design with First-Order Computation Tree Logic. In Proceedings of the AAAI Conference on Artificial Intelligence, 9661 9668. Carberry, S. 2001. Techniques for Plan Recognition. User Modeling and User-Adapted Interaction, 11(1 2): 31 48. Erol, K.; Hendler, J.; and Nau, D. S. 1996. Complexity results for hierarchical task-network planning. Annals of Mathematics and Artificial Intelligence, 18: 69 93. Fikes, R. E.; and Nilsson, N. J. 1971. STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving. Artificial Intelligence, 2: 189 208. Gall, K. C.; Ruml, W.; and Keren, S. 2021. Active Goal Recognition Design. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). Helmert, M. 2006. The Fast Downward Planning System. Journal of Artificial Intelligence Research, 26: 191 246. Kautz, H. 1987. A Formal Theory of Plan Recognition. Ph.D. thesis, Department of Computer Science, University of Rochester. Keren, S. 2019. Information Shaping for Enhanced Goal Recognition. In AAAI Workshop on Plan, Activity, and Intent Recognition. Keren, S.; Gal, A.; and Karpas, E. 2014. Goal Recognition Design. In International Conference on Automated Planning and Scheduling (ICAPS), 154 162. Keren, S.; Gal, A.; and Karpas, E. 2015. Goal Recognition Design for Non-Optimal Agents. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 3298 3304. Keren, S.; Gal, A.; and Karpas, E. 2016a. Goal Recognition Design with Non-Observable Actions. In Proceedings of the AAAI Conference on Artificial Intelligence, 3152 3158. Keren, S.; Gal, A.; and Karpas, E. 2016b. Privacy Preserving Plans in Partially Observable Environments. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 3170 3176. Keren, S.; Gal, A.; and Karpas, E. 2018. Strong Stubborn Sets for Efficient Goal Recognition Design. In International Conference on Automated Planning and Scheduling (ICAPS), 141 149. Keren, S.; Gal, A.; and Karpas, E. 2019. Goal Recognition Design in Deterministic Environments. Journal of Artificial Intelligence Research (JAIR), 65: 209 269. Keren, S.; Gal, A.; and Karpas, E. 2020. Goal Recognition Design - Survey. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 4847 4853.

Keren, S.; Xu, H.; Kwapong, K.; Parkes, D.; and Grosz, B. 2020. Information Shaping for Enhanced Goal Recognition of Partially-Informed Agents. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 9908 9915. Minton, S.; Johnston, M. D.; Philips, A. B.; and Laird, P. 1992. Minimizing Conflicts: A Heuristic Repair Method for Constraint-Satisfaction and Scheduling Problems. Artificial Intelligence, 58(1 3): 161 205. Mirsky, R.; Gal, K.; Stern, R.; and Kalech, M. 2019. Goal and Plan Recognition Design for Plan Libraries. ACM Transactions on Intelligent Systems and Technology, 10(2). Nau, D.; Au, T.-C.; Ilghami, O.; Kuter, U.; Mu noz-Avila, H.; Murdock, W.; Wu, D.; and Yaman, F. 2005. Applications of SHOP and SHOP2. IEEE Intelligent Systems, 20(2): 34 41. Nau, D.; Au, T.-C.; Ilghami, O.; Kuter, U.; Murdock, W.; Wu, D.; and Yaman, F. 2003. SHOP2: An HTN Planning System. JAIR, 20: 379 404. Pereira, R. F.; Oren, N.; and Meneguzzi, F. 2017. Landmark Based Heuristics for Goal Recognition. In Proceedings of the AAAI Conference on Artificial Intelligence, 3622 3628. Ramirez, M.; and Geffner, H. 2010. Probabilistic Plan Recognition Using Off-the-Shelf Classical Planners. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 1121 1126. Son, T. C.; Sabuncu, O.; Schulz-Hanke, C.; Schaub, T.; and Yeoh, W. 2016. Solving Goal Recognition Design Using ASP. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 3181 3187. Sosiˇc, R.; and Gu, J. 1994. Efficient Local Search with Conflict Minimization: A Case Study of the N-Queens Problem. Knowledge and Data Engineering, 6(5): 661 668. Sukthankar, G.; Geib, C.; Bui, H. H.; Pynadath, D.; and Goldman, R. P. 2014. Plan, Activity, and Intent Recognition: Theory and Practice. Newnes. Vered, M.; and Kaminka, G. A. 2017. Heuristic Online Goal Recognition in Continuous Domains. ar Xiv:1709.09839. Wayllace, C.; Hou, P.; and Yeoh, W. 2017. New Metrics and Algorithms for Stochastic Goal Recognition Design Problems. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 4455 4462. Wayllace, C.; Hou, P.; Yeoh, W.; and Son, T. C. 2016. Goal Recognition Design with Stochastic Agent Action Outcomes. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 3279 3285. Wayllace, C.; Keren, S.; Gal, A.; Karpas, E.; Yeoh, W.; and Zilberstein, S. 2020. Accounting for Observer s Partial Observability in Stochastic Goal Recognition Design: Messing with the Marauder s Map. In Proceedings of the European Conference on Artificial Intelligence (ECAI), 2394 2401. Wayllace, C.; and Yeoh, W. 2022. Stochastic Goal Recognition Design Problems with Suboptimal Agents. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 9953 9961. Zhang, H.; Chen, Y.; and Parkes, D. 2009. A general approach to environment design with one agent. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2002 2008.

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)