Explaining Plan Quality Differences

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-06 18:14:38

Abstract: In this paper we describe a method for explaining the differences between the quality of plans produced for similar planning problems. The method exploits a process of abstracting away details of the planning problems until the difference in the quality of the solutions they support has been minimised. We give a general definition of a valid abstraction of a planning problem. We then give the details of the implementation of a number of useful abstractions. Finally, we present a depth-bounded breadth-first search algorithm for finding suitable abstractions for explanations; and detail the results of an evaluation of the approach.

Main paper: 
 introduction: 
 In mixed-initiative planning settings, human and automated planners interact and collaborate to produce satisfactory plans. An automated planner is used to produce plans quickly and a human can then add constraints and preferences to the model until they are satisfied with the resulting plan produced by the automated planner. After each addition of a constraint the newly generated plan can be of better or worse quality compared with the version generated with-20 out the constraint, or the problem could even become unsolvable. In each of these cases it would be useful to have accompanying explanations for why additional constraints lead to a difference in plan quality.The setting in which these types of explanations are useful does not have to be a mixed-initiative setting. We assume that the setting is as follows: there is a planning model, Π, a constraint, c, which when applied to Π limits it's possible plans, a solution plan for Π, π, and a solution plan for Π + c, π ′ , where there is a difference in the quality of π and π ′ . A special case for this is where π ′ does not exist, that is the model Π + c is unsolvable. As in Krarup et al. 2021 , we refer to this process as model restriction. We restrict planning models such that they admit only solutions that obey a certain constraint. The problem is then to explain why there is a difference in the quality of π and π ′ . We assume that an explanation of the form "the difference is because of the constraint c" is not helpful. While there is a long history of work on explanation in AI, most work on explanation of plans (XAIP) is relatively recent. Fox et al. 2017 highlight contrastive 'why' questions as being important for plan explanation, and describe a number of different types of these questions and possible responses. Chakraborti et al. 2017 adopt the position that explanation is a model reconciliation problem -namely, that the need for explanation is due to differences between the agent's and the human's model of the planning problem. Eifler et al. 2020 approach answering local contrastive questions by explaining the reason that a contrast case B was not in the plan, or a feature of the plan, by using the properties that would hold if B were the case. Kasenberg et al. 2019 focus on justifying an agent's behaviour based on deterministic Markov decision problems.We are not aware of any work that focusses on explaining the difference in the quality of plans. However, there is work on explaining why planning models are unsolvable. Gobeldecker et al. 2010 focus on finding changes to the initial state that would make the planning problem solvable, and provide an algorithm to produce these excuses in a reasonable time. Sreedharan et al. use abstractions to explain the unsolvability of planning problems, as opposed to explaining the difference in quality of problems. They do this by considering relaxations of the planning problem until a solution can be found, and then looking for landmarks of this relaxed problem that cannot be satisfied in less relaxed versions of the problem. They assume that the existence of certain predicates cause a planning problem to be unsolvable. Thus the only abstraction they use is the removal of predicates from the model. We recognise a larger set of useful abstractions for AI planning systems, especially those that have languages to specify temporal characteristics of plans.An explanation for why two similar problems produce different quality plans should focus on the essential characteristics of the problems. For example, in a delivery problem, a user might ask why a particular truck was used rather than an alternative. The answer might be that the selected truck is better because of a weight limit on a bridge, or refrigeration properties of the truck. Inspired by Lipton's difference condition (Lipton 1990 ) we want to find and explain more accurately the causal differences between the original and hypothetical plans. Finding this kind of explanation requires abstracting away unimportant details like drivers, cargo, and perhaps route details. We show how these explanations can be generated by abstracting features of the planning problem until the two plans become equi-quality -that is, of equal or similar quality. We can then explain why one plan is better or worse than the other in terms of the abstracted features that impacted the difference in plan quality between the two.The primary contribution of this paper is to define a framework for the use of abstractions to explain plan quality differences. In this paper, we first define a valid abstraction for a planning model, these can be used to extend this work for new abstractions. We then introduce a running example we will use to motivate some useful abstractions. We formalise the implementation of a number of useful abstractions for explaining quality differences of temporal plans. We show how these abstractions fit our definition of an abstraction. We detail a proof-of-concept breadth-first search algorithm for finding suitable abstractions for explanation, and present the results of an experiment evaluating it. 
planning formalism: 
 Definition 1. A planning model is a pair Π = ⟨D, P rob⟩. The domain D = ⟨P s, V s, As, arity⟩ is a tuple where P s is a finite set of predicate symbols, V s is a finite set of function symbols, As is a set of action schemas, called operators, and arity is a function mapping all of these symbols to their respective arity. The problem P rob = ⟨Os, I, G, M, T ⟩ is a tuple where Os is the set of objects in the planning instance, I is the initial state, G is the goal condition, M is a planmetric function from plans to real values (plan costs) and T is a set of timed initial literals.A set of atomic propositions P is formed by applying the predicate symbols P s to the objects Os (respecting arities). One proposition p is formed by applying an ordered set of objects o ⊆ Os to one predicate ps, respecting its arity. This process is called "grounding" and is denoted with ground(ps, χ) = p, where χ ⊆ Os is an ordered set of objects. The inverse of this function ground -1 (p) = ⟨ps, χ⟩ returns the predicate symbol and objects. Similarly the set of ground functions V are formed by applying the function symbols V s to Os.A state s consists of a time t ∈ R, a logical part s l ⊆ P , and a numeric part s v that describes the values for the ground functions at that state. The initial state I is the state at time t = 0. We use the function S(Π) to denote the state space for a model Π, i.e. all states reachable from the initial state in Π. The goal G = g 1 , ..., g n is a set of propositions, including a subset of the logical state variables, P , and a set of constraints over numeric state variables in V , that must hold at the end of an action sequence for a plan to be valid.Similarly to propositions and functions, the set of ground actions A is generated by the substitution of objects for operator parameters. Each ground action is defined as follows: Eff (a) n ↔ , Eff (a) n ⊣ that act upon some v ∈ V , at the start of an action, continuously over the entire execution of an 145 action, and the end of an action.For ease of notation we allow access to multiple types of effects or preconditions through the ground action functions at once. For example for some ground action a, Eff + denotes all add effects of a, P re ⊢⊣ (a) denotes all start and 150 end preconditions of a but not invariant conditions, Eff (a) denotes all effects of a including numeric effects, etc.A plan is a sequence of grounded actions, π = ⟨a 1 , a 2 , . . . , a n ⟩ each with a respective time denoted by Dispatch(a i ) and duration Dur(a i ). A valid plan is a plan 155 that transforms the initial state from I into a state s such that s |= G; such that the start and end preconditions of all actions are satisifed at the time they start/end; all invariant conditions hold throughout the durations of each action, and all actions execute for their respective durations.The plan-metric function is, by default, the makespan of the plan. Therefore usually, and throughout this paper, the higher the metric of the plan the worse the quality of the plan. More generally, the metric assesses plan quality by taking into account both the extent to which a plan respects user 165 preferences and also the costs associated with the choices of action or combinations of actions within a plan. It is often the case that plans fail to meet expectations because of a mismatch in the way that plans are evaluated.Timed initial literals (TILs) were introduced as part of 170 PDDL2.2 (Hoffmann and Edelkamp 2005) , allowing an initial state to include simple effects triggered at specified times, regardless of the plan. Each timed initial literal t ∈ T is a tuple t = ⟨t time , t v ⟩ where t v is a proposition which becomes true or false, or a numeric effect which acts upon 175 some n ∈ V at the time t time . As a reference example, we use a simplified version of a food delivery domain. There are two trucks: truck T1 is a normal truck, whereas truck T2 is refrigerated. There is 180 only one driver. The goal of the problem is to deliver the meat and cereals packages to their respective locations. The meat must be delivered to loc b and the cereals to loc c. Both trucks, the meat, and the cereals are initially at loc a. It takes 20 minutes for a truck to move between the loc a and loc b, 185 15 minutes from loc b and loc c, and 10 minutes between loc a and loc c. The meat will spoil after 22 minutes, unless it is refrigerated. The cereals do not spoil. 
food delivery problem: 
 For simplicity, we define two possible routes. Route 1 is any plan in which we load the meat and cereals packages into any truck, drive from loc a to loc b and deliver the meat, and finally drive from loc b to loc c and deliver the cereals. Route 1 takes 35 minutes. Route 2 is any plan in which we load the meat and cereals packages into any truck, drive from loc a to loc c and deliver the cereals, and finally drive from 195 loc c to loc b and deliver the meat. Route 2 takes 25 minutes. Note, not every route is necessarily possible with every truck. The optimal plan is to perform Route 2 with the refrigerated truck T2. We refer to this plan as π * throughout. 
abstraction 200: 
 In the setting of model restriction described in Section 1, we want to explain why there is a difference in the quality of two plans π and π ′ based on a constraint c added to a planning model Π. We propose to do this through abstracting away elements of one of the planning models until 205 M (π) = M (π ′ ). We will abstract away details from Π if and only if M (π) > M (π ′ ), and we will abstract away detail from Π+c if and only if M (π ′ ) > M (π). An abstraction of a planning model can be thought of as a relaxation of the problem that the planning model describes. For any planning model Π ′ to be an abstraction of Π then every solution of Π must be a solution of Π ′ . Therefore, we ensure that by abstracting away details from the model with the lesser quality plan that we are always preserving valid plans for this model and therefore making the problem as easy to solve, and likely easier.There is a large body of work on abstraction in planning. The majority of this work focuses on the use of abstractions for computing heuristics. A planning problem can be abstracted, making it easier to solve, this abstracted solution can then be used as an estimate for the actual solution. One abstraction for computing a heuristic is the relaxed planning graph heuristic (Hoffmann and Nebel 2001) , where all delete effects are removed from the planning model to make the problem easier to solve. This is then used to gen-225 erate a relaxed plan that provides an estimate of distance to a goal state in the original problem. Another example of an abstraction for computing heuristics is merge-and-shrink heuristics (Helmert et al. 2014) , where a planning model is separated into transition graphs on each proposition. These transition graphs can then be merged and shrunk until a good estimate for the total transition system implied by the original planning model is found that can then be used for generating a heuristic. These are both examples of abstractions under our definition. Helmert et al. 2007 define what a general abstraction is in the context of AI planning based on a labeled state transition system that maps to the semantics of a planning system. They do this for providing flexible abstraction heuristics.In this section we propose a more general approach to abstraction, where state merging is one realisation, based on the idea that abstraction is a relaxation. We define the space of legal abstractions using a labeled state transition system (LST), which represents the state space corresponding to the grounding of a planning problem, and a simple temporal network (STN), which represents the temporal constraints and orderings on possible solutions of a planning problem.We rigorously define what a valid abstraction of a planning model is as we later give the implementations of model surgeries that abstract planning models. We use the definitions in this section to prove that these model surgeries are valid abstractions. Abstractions that are not valid could make planning problems harder to solve, and so would not be useful for providing explanations.The states of a planning model and transitions between them via applying actions can be modeled with an LST. Definition 3. A labelled state transition system (LST), τ , is a triplet ⟨S, L, T ⟩, where S is a set of states, L is a set of labels and T ⊆ S × L × S is a set of transitions. A path, π, in τ is a pair in S × L * , consisting of a state and a finite sequence of labels l 0 , ..., l n-1 , such that there is a sequence of states, s 0 , ..., s n such that s=s 0 and, for each i=0, ..., n-1,(s i , l i , s i+1 ) ∈ T .Given an LST τ we define an abstraction, τ ′ , as follows: Definition 4. An LST, τ ′ = (S ′ , L, T ′ ), is an abstraction of LST, τ = (S, L, T ), with respect to initial state, I ∈ S, and goal set, G ⊆ S, if there is a mapping, f : S → S ′ , such that for every transition, ⟨x, l, y⟩ ∈ T , from a reachable and relevant state, x ∈ S, there is ⟨f (x), l, f (y)⟩ ∈ T ′ .An LST can be derived from a planning model: Definition 5. Let Π be a planning model; the LST derived from Π is τ = ⟨S, L, T ⟩. S is the set of all valuations of valid groundings of P s and V s. L is the set of labels corresponding to the ground actions A. T = {(s, o, s ′ )|s ∈ S, the ground action o represents is applicable ins, s ′ is the resulting state of applying the ground action o represents in s}. We define the function σ(Π) = τ to denote the derivation of an LST from a planning model Π.In planning problems, only states that can be traversed to from the initial state are reachable and only states that support paths to a goal state are relevant to the solution: Definition 6. Given an LST, τ = (S, L, T ), a problem is a pair, (I, G), such that I ∈ S and G ⊆ S, and these are referred to as the initial state and goal set of the problem. Definition 7. Given an LST, τ = (S, L, T ), and a problem, (I, G), a state, s ∈ S, is reachable if there is a path from I to s in τ . A state, s ∈ S, is relevant if there is a path in from s to some state g ∈ G in τ .Instead of thinking about abstractions of boundless LSTs, for planning problems we can think of abstractions of LSTs with relevant problems. Definition 4 can be generalised to define an abstraction that operates over all problems in some family of problems, P, for a given LST. Definition 8. An LST, τ ′ = (S ′ , L, T ′ ), is a general abstraction of LST, τ = (S, L, T ), with respect to a set of problems, P, if τ ′ is an abstraction of τ for every problem, (I, G) ∈ P.The next set of corollaries trivially follow from the set of definitions above. These are useful for our presented proofs in Section 5 and for proving some properties about abstractions that are generally useful, and expected from the definition of an abstraction.Corollary 1 is very informative for abstractions for planning problems. Many relaxations of a planning problem will add transitions to the LST of the planning problem. Through this corollary, we can know that these suite of relaxations are all valid abstractions. Note that not all relaxations to a planning problem are trivially valid abstractions due to this abstraction. For example, if we remove negative effects from a planning problem but we allow negative preconditions, then this will remove edges in the derived LST. This is, of course, not the case if modelling language does not allow negative preconditions where this relaxation would be a valid abstraction trivially proved by this corollary.Corollary 2 is a more formal way of denoting this effect removal abstraction that is common in relaxations of planning problems.Corollary 3 is similarly informative. As abstractions of planning problems are relevant to a problem, (I, G), then any relaxation of a planning problem that affects only states that are not relevant to the solution of the problem, of which there are often many, is a valid abstraction shown by this corollary.Finally, Corollary 4 shows that state merging is valid according to our more general definition of an abstraction. This is useful as state merging abstractions have been long used as powerful tools in planning. However, we do not rely on this corollary for any of our proofs.Corollary 1. A second specific type of abstraction that falls trivially within those defined in Definition 4 is edge insertion abstraction: the addition of transitions to an LST, with f as the identity function, certainly contains all transitions in T .Corollary 2. For a planning model Π with an initial state I, goal state G, and ground actions A we can remove an effect e ∈ Eff +- ⊢⊣ (a) ∪ Eff n ⊢↔⊣ (a) for some action a ∈ A, to produce a planning model Π ′ . The LST τ ′ with the problem (I, G) derived from Π ′ is an abstraction of the LST τ with the problem (I, G) derived from Π, if e does not make any reachable and relevant condition c ∈ P re ⊢↔⊣ (a ′ ) true for any a ′ ∈ A or satisfy any goal g ∈ G.Corollary 3. Removing states s and transitions ⟨s, l, y⟩ where s is not reachable or relevant for any problem P is a legal abstraction.Corollary 4. The state merging abstraction is an abstraction according to Definition 4 using the following construction: states u, v ∈ S are merged into the new state, m, bytaking S ′ =S \ {u, v} ∪ {m} and f (s)=s if s / ∈ {u, v}, f (u)=f (v)=m, and T ′ = {⟨f (s), l, f (s ′ )⟩|⟨s, l, s ′ ⟩ ∈ T }.This is an abstraction by construction.To model plans in which action durations, temporal happenings, and temporal constraints matter; we can create a Simple Temporal Network (STN) (Dechter, Meiri, and Pearl 1991) on top of the LST from Definition 5 that dictates the timings of the state transitions in the LST. An STN is a graph whose vertices represent time points and weighted edges represent the maximum/minimum separation between these. Definition 9. A simple temporal network (STN), G, is a directed graph denoted by the triplet ⟨V, E, L⟩, where V is a set of vertices, E ⊆ V × V is a set of edges, and L ⊆ E × R is a set of labels applied to edges to represent temporal separation between vertices.An STN is constructed over an LST, τ , as follows: given a finite sequence of labels in τ , {a 1 , a 2 , ..., a n }. the corresponding STN has n + 2 vertices, labelled I, a i (for i = 1...n) and G. The edges of the STN comprise an edge from a 1 to I and from a i+1 to a i , each weighted -ϵ (where ϵ sep-365 arates interfering actions), an edge from G to a n weighted 0, and, for each pair of labels, a i and a i+j , that represent the start and the end of the same durative action instance, edges from a i+j to a i weighted with -Dur(a i )[0] and from a i to a i+j weighted Dur(a i )[1], i.e. for the edge e 1 from a i to 370 a i+j , l(e 1 ) = Dur(a i )[1], and for the edge e 2 from a i+j to a i , l(e 2 ) = -Dur(a i )[0]. If any action starts or ends are not paired off, the label sequence is not a valid plan; the sequence of labels is otherwise a valid plan if and only if it is both a valid path in the LST and also a consistent STN.TILs can be captured within the framework of the LST and STN described above as follows. Given a TIL, t = ⟨t time , t v ⟩, specifying effect t v occurs at time t time , to be added to a planning model Π, a new proposition, t, is created and added to the initial state, an action, T IL t is created 380 with precondition t, that deletes t and with add effects t v and doneT ; doneT is added to the goal. An LST is then created in the usual way. The STN created for this temporal domain is then adjusted by adding edges of weight t time from I to T IL t and -t time in the opposite direction. In this model, 385 a valid plan will be forced to contain exactly one copy of the action T IL t , in order to satisfy the goal. No additional copies can appear because of the deleted precondition. The temporal constraints can only be satisfied if T IL t occurs at exactly time t time , along with all the other constraints of the 390 temporal structure of the plan.We can then define an abstraction of an STN: Definition 10. An STN G ′ =⟨V ′ , E ′ , L ′ ⟩ is an abstraction of STN G=⟨V, E, L⟩, where V ′ ⊆ V and E ′ ⊆ E, and if for any two vertices v, v ′ ∈ V that are connected by an edge 395 e ∈ E where there is a label l for e in L, we have l ′ ∈ L ′ where l ′ (e) ≤ l(e) , if v, v ′ ∈ V ′ and e ∈ E ′ .Finally, as we are working with temporal-numeric planning domains, we can define what a valid abstraction of a planning model is based on their derived LST and STN: 400 Definition 11. A planning model Π ′ is an abstraction of Π if the LST τ ′ and the STN G ′ derived from Π ′ are abstractions of the LST τ and STN G derived from Π.In a perfect world, we would be able to explain why a model is not solvable, by adding states, labels, and transi-405 tions to the LST of a planning model. The LST would have to represent the entire state space of a problem. LSTs can be large even for simple planning problems (Helmert 2009) .Not only can it become infeasible to explicitly represent the LSTs for these problems, but it can become intractable to 410 realise what modifications to the LST we must make for precise abstractions. We instead make changes to the lifted representation of the planning problem with model surgeries. space than expected. 
abstraction implementation: 
 In this section we describe the implementation of abstractions that we have identified as important for explanation. We motivate each abstractions use in explanation with an example, we give the formal process of performing the abstraction on a planning model, and show how these fit our definition of abstraction. We prove proposition 1 for each abstraction α. This proposition must hold to guarantee that the model surgeries we propose do not reduce the number of valid plans for a model, and therefore can be used to search for valid solutions or solutions of better quality. Proposition 1 (Valid Abstraction). Given an LST τ = ⟨S, L, T ⟩ and STN G = ⟨V, E, L⟩ both derived from a planning model Π and an LST τ ′ = ⟨S, L ′ , T ′ ⟩ and STN G = ⟨V ′ , E ′ , L ′ ⟩ derived from the planning model Π α , τ ′ is a valid abstraction of τ and G ′ is a valid abstraction of G, and therefore Π α is a valid abstraction of Π.Each proof of a valid abstraction in this section follows the same approach. Definition 4 defines what it means for a planning problem to be an abstraction of another. Each proof consists of showing that for τ τ ′ , G, and G ′ derived from Π and α(Π), τ ′ is an abstraction of τ and G ′ is an abstraction of G and therefore α(Π) is an abstraction of Π.For ease of notation, we define two new functions P rop : 440 P s → P and P red : P → P s. The function P rop takes a set of predicates and returns each of the propositions in P that were formed from it's grounding, i.e. for a set of predicates ps, P rop(ps) = {p ∈ P |∃ps ′ ∈ ps, χ ⊆ Os : ground -1 (p) = ⟨ps ′ , χ⟩}. The function P red takes a set of propositions and returns the the set of predicates that were grounded for them to be formed, i.e. for a set of propositions p, P red(p) = {ps ∈ P s|∃χ ⊆ Os : ground(ps, χ) = p}Given the example spoken about in Section 3 with the plan 450 being presented to a user as one in which truck T2 performs route 2, the user might instead prefer truck T1 to be used.Through the system of model restriction we can force the planner to ensure that the truck T1 is used throughout the plan. The resultant plan will consist of truck T1 performing route 1. This is because truck T1 cannot perform route 2 as the meat will spoil at time 22 and it is not possible to extend the life of the meat in the unrefrigerated truck T1. Route 2 takes only 25 minutes. However more than 22 minutes would have passed before the meat was delivered and so it would no longer be fresh. This new plan π takes 35 minutes compared to the original 25 minutes.Through the use of abstractions we can determine the cause of the disparity in solution quality. If we abstract away the predicates, ps ∈ P s, that are responsible for modelling the need for refrigeration, then we can produce a plan, π ′ , in which truck T1 can perform route 2. This is a plan of the same quality as the original plan, but we are instead using truck T1 rather than truck T2 as the user expected. We can therefore produce an explanation such as "if there were no need for refrigeration, then truck T1 could be used such as in π ′ , otherwise our new plan will be π which is slower by 10 minutes". Abstracting a predicate consists of removing the predicate from everywhere that is appears in the model.The formal process for abstracting a predicate from a planning model is as follows. Given a planning model Π and a set of predicates ps ⊆ P s the abstracted model is Π ps = ⟨D, P rob⟩, where D = ⟨P s \ {ps}, V s, As ′ , arity⟩ and As ′ = {a ′ |∀a ∈ As : Dur(a ′ ) = Dur(a), P re(a ′ ) = P re(a) \ {ps}, Eff (a ′ ) = Eff (a) \ {ps}}; and P rob = ⟨Os, I \ {p}, G \ {p}, M, T ⟩, where P rop(ps) = p.Proof. Removing a predicate ps from the planning model is a valid abstraction. Removing a predicate obviously causes all preconditions involving that predicate to be removed. However, it also removes all effects (positive and negative) on that predicate, but these effects no longer matter, since no transition depends on them. This operation is equivalent to merging states that are otherwise identical except for the presence or absence of ps.This can be seen by realising that, for the LST τ with a set of problems P, the mapping f (s) = s \ {ps} maintains that for every transition ⟨x, l, y⟩ ∈ T from a reachable and relevant state s with respect to the problems in P, ⟨f (x), l, f (y)⟩ ∈ T ′ .In the same scenario as above a user might want truck T1 to be used rather than truck T2. After restricting our problem to behave due to the contrast case our new plan would consist of truck T1 taking route 1, for the same reasons described in the previous chapter. As in the previous chapter this new plan π takes 35 minutes compared to the original 25 minutes.Through the use of abstractions we can determine the cause of the disparity in solution quality. In some cases abstracting away an entire predicate may be extreme and unnecessary. Instead we can abstract away certain preconditions for actions. If we abstract away the preconditions, ps ∈ P s, that are responsible for checking that the produce is fresh before it is delivered, then we can produce a plan π ′ in which truck T1 can perform route 2. This is a plan of the same quality as the original plan, but we are instead using truck T1 rather than truck T2 as the user expected. We can therefore produce an explanation such as "if the produce did not need to be fresh for it to be delivered, then truck T1 could be used such as in π ′ , otherwise our new plan will be π which is slower by 10 minutes". An abstraction of a precondition consists of removing a predicate from all preconditions that the predicate appears in.The formal process of abstracting a precondition from a planning model is as follows. Given a planning model Π and a set of predicates ps ⊆ P s the abstracted model is Π pre(ps) = ⟨D, P rob⟩, where D = ⟨P s, V s, As ′ , arity⟩ and As ′ = {a ′ |∀a ∈ As : Dur(a ′ ) = Dur(a), P re(a ′ ) = P re(a) \ {ps}, Eff (a ′ ) = Eff (a)}.Proof. Removal of preconditions from actions is a valid abstraction. This is because removing preconditions manifests as adding transitions in the LST, as can be seen from Definition 5 (the ground action o represents is applicable in s), so by Corollary 1, it is a valid abstraction.By Corollary 1 this is an abstraction with T ′ = T ∪ {⟨s \ {ps}, a, Eff a (s \ {ps})⟩|⟨s, a, Eff a (s)⟩ ∈ T } where 530 Eff a (s) is the result of updating s with the effects of a.Again, assuming a user prefers truck T1 to be used rather than truck T2 in the example in Section 3. We would have new plan, π, that would consist of truck T1 taking route 1 and take 35 minutes compared to the original 25 minutes.In our example, if we abstracted the duration of the action drive truck, then we can produce a plan π ′ in which truck T1 can perform route 1 quicker. An abstraction of an action's duration involves editing the action's duration constraint so 540 that the planner can select any positive duration.Given a planning model Π and action schemas as ⊆ As ,the abstracted model is Π as = ⟨D, P rob⟩, where D = ⟨P s, V s, As ′ , arity⟩ and As ′ = As \ {as} ∪ {a ′ |∀a ∈ as : Dur(a ′ ) = ⟨0, inf⟩, P re(a ′ ) = P re(a), Eff (a ′ ) = (a)}.Proof. Our abstraction has no effect on the derived LST: τ == τ ′ , there is therefore no effect on the vertices and edges in the STN:V ′ == V and E ′ == E, only L ′ ̸ = L.For any two vertices v i , v i+1 ∈ V connected by an edge e 1 ∈ E and v i+1 , v i connected by e 2 ∈ E, then v i , v i+1 ∈ 550 V ′ and e 1 , e 2 ∈ E ′ and l(e 1 ) ′ >= l(e 1 ) and l(e 2 ) ′ <= l(e 2 ). This is because the labels in the STN are defined by the duration's of actions, the smallest possible duration of an action is 0, and the largest is inf. Therefore the labels in G are contained within the labels of G ′ . 555Given the same scenario above, rather than abstracting the duration of the drive truck action so that we can deliver the meat before it spoils, we could abstract the TIL that is responsible for the meat spoiling.Through this abstraction we can produce a plan π ′ in which truck T1 performs route 2. We can still deliver the meat when we arrive to location c in the unrefrigerated truck because it would not have spoiled. This is a plan of the same quality as the original plan, but we are satisfying the users 565 foil posed in their question. We can therefore produce an explanation such as "if the meat did not spoil after 22 minutes, then truck T1 could be used such as in π ′ , otherwise our new plan will be π which is slower by 10 minutes. An abstraction of a TIL consists of creating an action that models the TIL. This action can be performed at any time and will have the same effect as the TIL.Given a planning model Π and a set of TILs t ⊆ T the abstracted model is Π t = ⟨D, P rob⟩, where D = ⟨P s ′ , V s, As ′ , arity⟩ and P s ′ = P s ∪ {p t , d t |∀t}, andAs ′ = As ∪ {a t |∀t : Dur(a t ) = ⟨0, 0⟩, P re(a t ) = {p t }, Eff x (a t ) = {t v }, Eff -(a t ) = {p t }},where x is + if the TIL is positive andotherwise; and P rob = ⟨Os, I, G ∪ {d t |∀t}, M, T \ t.Proof. The abstraction of a TIL consists of modelling it as an action, which is exactly how TILs are handled in the LST and STN. This is an exact copy of the TIL in the LST and therefore the TIL is not changed and therefore τ == τ ′ . This differs in the LST only in that the action can now be executed at any time, i.e. V ′ == V and E ′ == E, only L ′ ̸ = L. In the same way as the proof in Section 5.3 this is a valid abstraction as per Definition 10. 
searching for suitable abstractions: 
 As described in Section 1 we consider the problem where we have a planning model, Π, with a solution, π, and a constrained model, Π+c, which we will call Π ′ , with a solution, π ′ , and there is a difference in quality between π and π ′ .We consider an abstraction α of a model Π ′ to be suitable as part of an explanation if for both the solution to the abstracted constrained model Π ′ α , π ′ α , and the abstracted original model Π α , π α , have costs, M (π ′ α ) and M (π α ) and|M (π ′ α ) -M (π α )| < n.Where n is a user-defined bound below which we consider plans to be equi-cost.This creates a suitable explanation as it abstracts details from both of the models until they produce equi-cost plans. We can therefore say that it is those details that cause the discrepancy between the quality of the solutions for the original and constrained models. However, there may be many possible abstractions that produce equi-cost plans. To distinguish between these we are guided by the principle that we want to maintain, as much as possible, the most important and relevant structures of the problem. To this end we prioritise abstractions first by their size (fewer composed abstractions is better) and then by the similarity of the solutions to the abstracted and original problems, i.e the abstraction with the smallest |M (π α ) -M (π)|.In this section we propose a search algorithm to identify correct abstractions that produce informative explanations.The approach we take is to search over a poset of possible abstractions. Definition 12 allows us to determine a poset given a planning model, Π, the set of possible abstractions, α, as L(Π, α) = (M Π , ≤). This gives an ordering on the models that can be reached through the set of abstractions α. This underpins our approach of abstraction for explanation. Definition 12. Given a planning model, Π, and a set of abstractions, α, the collection of associated models, M Π , is the closure of the image of Π under the application of the abstractions, α. The partial ordering on M Π is defined by: forΠ 1 , Π 2 ∈ M Π , Π 1 ≤ Π 2 iff ρ(Π 1 ) ⊆ ρ(Π 2 ). This deter- mines the poset L(Π, α) = (M Π , ≤).For an abstraction poset, elements higher up in the poset are more abstract than those at the bottom. The abstractions that will form A in our search are all the possible abstractions defined in Section 5. We do not construct this poset a priori, we generate parts of the poset during search time.We provide a search algorithm for finding suitable abstractions for explanations in Algorithm 1. This algorithm implements a bottom-up breadth first search. We start from the constrained model and apply all possible abstractions at each level of the poset before traversing up the poset in a single step. This is repeated until we reach a model that produces an equi-cost plan to the original solution. This algorithm take as input the constrained model, Π ′ , the set of possible abstractions, A, (see Sec. 5), the original plan, π, and a real value specifying the bound for equi-cost plans, n. A queue is constructed, queueA, from the abstractions, A, the current abstraction, curr a , is then dequeued. The first model that abstractions are applied to, curr Π , is a copy of the model Π ′ . This is abstracted with curr a to give the abstracted model, Π ′ a , the function abstract takes an abstraction, a, and a model, Π, and returns an abstracted model, Π a . A queue, queueΠ, is constructed from the abstracted model, curr a , that model is then solved, the function, solve, takes a model, Π, and returns a valid solution plan for, Π. The algorithm then checks if the abstracted plan and original plan are equi-cost, the function bound is as described in the introduction to this section. The algorithm then loops, repeating this process for each model in the queue, for each abstraction in the queue until there are no models left in the queue. In each iteration there is a further check that an abstraction, curr a , has not already been applied to the current model, curr Π .Algorithm 1 gives a satisficing solution. It gives the first of abstractions that produces a model whose solution is equicost to the original. If we assume that all abstractions are of equal cost, then this would be an optimal solution as we will apply all possible abstractions at each level of the poset before moving on. However, as noted earlier in this section, we can evaluate abstractions based on the distance between the quality of the solution of the abstracted model and the original solution. We can modify the stopping condition of Algorithm 1 to give an optimising search algorithm that evaluates the quality of certain solutions based on this metric.The explanation will be composed of the abstractions that were used in order to get a satisfiable plan under the restricted model. The specific explanation will be contextualised by the constraint applied to the original model that lead to a difference in the quality of the solutions. Each abstraction a curr is popped from the set of abstractions a. The type of the abstraction is then checked, these are each of the abstractions outlined in Section 5. The explanation is then formed by the types of, and the abstractions that allow the problem to produce an equi-cost solution. In the next section we give some examples of these generated explanations. 
experiments and results: 
 In this section we present an empirical evaluation of our approach to finding explanations. Whilst we present results indicating the performance of our algorithm; our focus is on testing the ability of our approach to find explanations. Optimizing the efficiency of the algorithm is left to future work.Evaluation uses 6 differently structured planning problems. 2 of these problems are based on our running example and the other 4 are instance 1 of Rovers and 2 of Satellite from the International Planning Competition (IPC) (Long and Fox 2003) . The 2 explainable problems are the Delivery Algorithm 1: Breadth first search over an abstraction poset L(Π ′ , A) to find a set of abstractions a ∈ A supporting a plan π ′ such that |M (π ′ ) -M (π)| < n Data: {Π, Π ′ , A, n} Result: a ⊆ A ∨ F AIL 1 queueA ← queue(A); 2 curr a ← dequeue(queueA); 3 Π a ← abstract(Π, curr a ); 4 Π ′ a ← abstract(Π ′ , curr a ); 5 queueΠ ← queue(Π a ); 6 queueΠ ′ ← queue(Π ′ a ); 7 π ← solve(Π a ); 8 π ′ ← solve(Π ′ a ); 9 if |M (π ′ ) -M (π)| < nIn Rovers, rovers take samples of soil, rock, and image data to send back to a lander. Not all rovers are equipped for all sample types. Cameras must be calibrated to take images, rock data must be stored before it can be communicated, and soil data can be collected and communicated. The optimal 700 plan for problem 1 is to use rover R1, calibrate the camera and take an image, traverse to and collect the rock sample, store it, and communicate the data; and finally traverse to the soil sample, collect it, and communicate the data.In our Satellite problem there is a satellite with two instru-705 ments able to take photos in different modes. Instrument I1 can take infrared images and I2 can take both infrared and visible images. The goal of the problem is to take images of certain targets in certain modes. The optimal plan is to turn on and calibrate I2 and take the required images.Each problem is solved, then constraints added to make the problem unsolvable or to require a plan of worse quality than the original. We search for suitable abstractions using the optimising version of Algorithm 1. Experiments ran on a 4gb machine with an i7-12800H CPU, and a 4 hour timeout. 715 We use the full set of abstractions detailed in Section 5.The delivery problem is constrained so that truck T1 must Table 1 : Time taken to find and number of suitable and optimal abstractions for a selection of planning problems.be used, requiring the poorer route 1 to be taken. The deliv-ery+ problem is similarly constrained, but also so that driver, D1, who cannot use the refrigerated truck, must make the deliveries. This is unsolvable.The Rovers problem is constrained so that the image must be taken before the camera is calibrated. The resulting plan has the image capture in a different place in the solution. The problem is separately constrained by removing the capability of the rover to sample soil or rocks, which is unsolvable.The Satellite problem is constrained so that instrument I1 must be used to take an image; the plan then uses I1 to take the infrared images and instrument I2 is switched on to take the visible light images. The problem is separately constrained so I2 cannot be used, which is unsolvable.The results in Table 1 show, for each problem, the number of abstractions at each search level, (the size of A); the time to find the first suitable abstraction (henceforth, abbreviated to fsa); the time to find the first optimal abstraction; the numbers of suitable and of optimal abstraction sets for explanations found; the size of the abstraction set; the number of nodes expanded in the search; and finally the time bound given for each problem. The bound is calculated by finding the largest time taken to solve the original problem, or any of the constrained problems, and doubling it.The fsa for the delivery problem was found in 20.04 seconds; it is also optimal. 585 combinations of abstractions were searched of which 489 were suitable and 203 optimal. The first optimal solution found, of size 1, abstracts away the predicate determining whether meat or cereal is in a truck. Now, the action that prolongs the life of the meat can be used with truck T2 as the meat is no longer required to be in the truck for this action to be performed. The plan is then to use truck T1 to perform route 2 whilst using truck T2 to act as the refrigerator from location loc a. The explanation produced is: {Predicate: (in ?p -produce ?t -truck)}. There are many optimal solutions for this problem. Another is to abstract the TIL responsible for determining when the meat spoils. The plan for this abstracted problem uses truck T1 to perform route 2 without worrying about the meat spoiling at all. The explanation is: {TIL: (fresh ?m -meat)}.The fsa for the delivery+ domain is found in 220.37 seconds. The first optimal abstraction is found in 1382.22 seconds. 868 combinations of abstractions were searched. of which 307 were suitable and 12 were optimal. The first optimal solution found, of size 2, abstracts away both the predicate for a truck to be refrigerated and the requirement for a driver to be qualified to drive certain trucks. Then truck T1 can be used in place of the refrigerated truck, and any driver can drive any truck. The plan for this abstracted problem is to use T1 with the driver D1 to perform route 2.The fsa for the rovers problem constrained to produce a worse quality plan was found in 520.61 seconds. The first optimal abstraction was found in 1802.31 seconds. 178 com-770 binations of abstractions were searched, of which 33 were suitable and 2 optimal. The first optimal solution found abstracts away the predicate responsible for ensuring the target of calibration matches is the objective image to be taken. This allows for a camera to be calibrated on any target and 775 so the original calibration action never has to be performed and so the constraint is trivially satisfied. The plan continues the same as in the original plan, after the camera is calibrated with an arbitrary objective.The fsa for the rovers problem constrained to be un-780 solvable is found in 10295.09 seconds; it is also optimal. 350 combinations of abstractions were searched, of which 10 were suitable and 4 optimal. The first optimal solution, of size 2, abstracts away the preconditions of the sample rock and sample soil actions that en-785 sure the rover has the ability to sample rock and soil; any rover can then gather rock and soil samples and the plan is then the same as the original. The explanation is: {Precondition: (equipped for soil analysis ?rrover),(equipped for rock analysis ?r -rover)}The fsa for the Satellite problem constrained to produce a worse quality plan is 420.31 seconds; it is also optimal. 52 combinations of abstractions were searched, of which 11 were suitable and 8 optimal. The first optimal solution, of size 1, abstracts the precondition of the take image ac-795 tion responsible for ensuring the instrument taking the image supports the relevant mode. The instrument I0 can then be used to take images of visible light and the plan for the abstracted model is the same as the original plan other than in using instrument I0 instead of I1.The fsa for the Satellite problem constrained to become unsolvable is 280.20 seconds; it is also optimal. 52 combinations of abstractions were searched of which 26 were suitable and 16 optimal. The first optimal abstraction and resulting plan is the same as the other Satellite problem. 
8 conclusion: 
 In this paper a general definition for abstractions in planning problems is presented and a number of surgeries on planning models are defined. A proof-of-concept algorithm is presented and used to find suitable and optimal abstractions. 810 Building natural language explanations from these abstractions and evaluating them remains future work. 
 
 Appendix:  


Decision: This is a short metareview: everybody liked the paper, and no further discussion was needed to come up with an "accept" recommendation. Congratulation on a nice paper, looking forward to seeing it at ICAPS!

Reviews: review: strength_weakness: strength_weakness: -- Complexity of Abstraction Process: The process of abstracting planning models to explain plan quality differences is inherently complex. This complexity might make it challenging for users without a deep understanding of planning models and abstractions.
-- Dependence on Accurate Model Abstractions: The effectiveness of the methodology heavily relies on accurately abstracting the planning models. Any inaccuracies in abstraction might lead to incorrect or misleading explanations.
-- Limitations in Handling Highly Complex Domains: While the approach is novel, its effectiveness in extremely complex planning domains with numerous interacting elements and constraints is not fully explored. The abstraction process could become overly complicated or less effective in such scenarios.
-- Computational Resources and Efficiency: The process of finding suitable abstractions and generating explanations might require significant computational resources, especially for large and complex planning models. This could limit its applicability in resource-constrained environments.
-- Generalizability of the Methodology: The paper's methodology, while innovative, might have limitations in its applicability to a wide range of planning problems. The specific types of abstractions and their implications for different planning domains are not extensively discussed.
-- User-Defined Parameters and Subjectivity: The process involves user-defined parameters (like the threshold for equi-cost plans), which introduces a degree of subjectivity. Different users might arrive at different explanations for the same plan quality differences.
-- Potential Over-Simplification in Explanations: There is a risk that the explanations generated might oversimplify the actual reasons behind plan quality differences, especially in cases where multiple factors contribute to the disparity.
questions: questions: 1) How do the authors propose to manage the inherent complexity of the abstraction process, especially for users who may not be deeply familiar with the intricacies of planning models and abstractions?
2) What measures are in place to ensure the accuracy of the model abstractions? How do the authors address the potential impact of inaccuracies in abstractions on the explanations provided?
3) Can the authors elaborate on the effectiveness of their methodology in extremely complex planning domains? Are there limitations to the abstraction process in scenarios with numerous interacting elements and constraints?
4) How does the methodology account for computational resource limitations, especially in large and complex planning models? Are there any strategies to improve the efficiency of the abstraction process?
5) How generalizable is the methodology across different planning problems? Can the authors discuss its applicability and limitations in various types of planning domains?
6) What is the impact of user-defined parameters and the inherent subjectivity in the process? How can different users ensure consistency in the explanations for the same plan quality differences?
7) How do the authors address the risk of oversimplification in the explanations, especially when multiple factors contribute to plan quality differences?
8) Can the authors provide more insights into the scope of their evaluation? Are there plans to extend the evaluation to cover a broader range of scenarios and planning problem variations?
strength_weakness: strength_weakness: The used domains are pretty similar, and I don’t know if this abstraction only is good for these three domains. I would like to know what intuition the authors have in which areas this might not work well. 

I don’t understand why 4 hours for experimentations only rovers unsolvable need more than 600 second to find first solution. This time a satellite or rover would involve a high battery cost and would not be applicable in real environments. 
The first solution in delivery problem is the optimal (this domain in simple) and it takes around 20 second to exact it, I don’t really need run 4 hours for that or to find another solution. I think the limitation of the experimentation should be 3 hours for these domains. At least the authors  know that this technique only resolves in less than 3 hours for these domains and in others nothing is achieved.
questions: questions: Do you think this technique, regardless of temporal domains, is generalizable?
Could this abstraction be used in numerical domains?
strength_weakness: strength_weakness: An issue here is the granularity of the abstractions. I appreciate that it is not the point here to consider the generation of text explanations, however, given that the explanation is at the level of predicate/action duration etc., I am concerned that the generated explanations lack the necessary information content to make useful text explanations. E.g., compare the explanations in the paper  for the specific TIL against the explanation for removing a predicate from the domain. 

The actual approach was surprising to me. There is no real discussion about what we can expect when we add a constraint to a model. My view would be that it only makes sense to use an explanation approach of plan quality if the setup is expected to generate plans of consistent quality (e.g., that the time-limit is suitable for the problem). And in this case we can expect that the new plan will have the same or worse quality. In the case of the same quality, there is nothing to explain. Otherwise, it seems that the simulation of the original plan in the constrained model would provide a starting point for an explanation. This would potentially allow for more guidance, which might allow for more specific abstractions.

The main limitation for me is that the evaluation does not properly investigate the approach, and didn't provide any insight into when the approach would be useful. Of course there are multiple explanations generatable, but how would this be used in practice? The paper suggests that a useful explanation might be one of those generated by the approach, but it is impossible to understand how many of the generated explanations are useful and how this would degrade as more modifications were made. I think that the evaluation needs motivated with a scenario where this approach, with its associated runtime, can be justified.

Notes:
In XAIP-as-a-service I would expect the structure for the constraints to be automatically generated. I appreciate that you do not aim to generate text explanations here, but this seems to be a problem.

The properties of the approach are not really discussed. 

The parameter of n used in the evaluation is (I believe) missing from the paper.
questions: questions: 1. Can you report on the fraction of optimal explanations that correspond to the actual change that was made? How does this change with more modifications?

2. Is there a scenario, where providing an explanation after 30 minutes is useful?

3. Did you explore the impact of parameter n? I don't see any reason for this not to be 0. I understand that with a value higher than 0 you might allow for smaller abstractions that miss details that only account for marginal difference. However, this is at the cost of weakening the only criteria you have for pruning out incorrect explanations. From my understanding you will increase the set of satisfying candidate abstractions. Is there any evidence that this parameter can lead to a reasonable compromise?

---
Thanks for your responses.