Explaining Soft-Goal Conflicts through Constraint Relaxations

1 Introduction

Imagine planning the next Mars Rover Mission. Due to the rovers' limited resources and timing constraints for data collection and uploads, only some of the rovers' tasks can be planned. Recent work by Eifler et al. [2020a; 2020b] suggests explaining trade-offs between such soft goals in terms of conflicts, i. e., minimal unsolvable soft-goal subsets. Howwhy the soft-goals

can not be jointly achieved. Understanding the cause of these conflicts and possible resolutions is crucial to reasoning about different options and finding the best trade-offs.

Here, we explore the question of what causes soft-goal conflicts in tasks with constraints such as resource availability and time windows. In this context, soft-goal conflicts can naturally be explained by identifying the minimal constraint relaxations under which the conflict disappears. For example the conflict {x-ray image, soil sample} could be explained by: "The rover needs 2 more units of energy or the upload window to relay X needs to be 3 time units longer, to perform both tasks". A similar approach is used in constraint programming [Lauffer and Topcu, 2019;

Senthooran et al., 2021], where they introduce soft constraints, to provide suggestions on how to modify an unfeasible subset of constraints to make it feasible. We investigate algorithms for computing such explanations based on minimal relaxations in a set of given relaxations, which we instantiate with resource and time window constraint relaxations.

Eifler et al. [2020b] introduced an algorithm that computes all minimal unsolvable goal subsets of a task by expanding the whole search space while tracking all maximal solvable goal subsets. To reduce the search space size they prune all states from which, according to a given heuristic, no superset of the incumbent solution is reachable. The basic adaption of this procedure is to iteratively call it for each relaxed task separately and compute the minimal relaxed task where each conflict disappears in a post-processing step.

We introduce two algorithms that improve over this baseline by exploiting the fact that information like reachable goal subsets and states can be propagated from one relaxed task to another if the latter is more relaxed. The first algorithm, Internal Constraint Reuse (ICR), iteratively computes the conflicts for each increasingly relaxed planning task and reuses the reachable subgoals from less relaxed tasks. This provides the pruning function with a growing set of reachable subgoals that it can use to prune parts of the search space that do not contain any subgoals that have not yet been achieved. The second algorithm, Search Space Reuse (SSR), reduces duplicate work by iteratively increasing one search space instead of generating a new one per relaxed task. This is done by storing the search frontier for each task, and using it as the starting point for more relaxed tasks. Thus for each relaxed task, only the newly reachable states are generated.

We show that these algorithms can exponentially outperform the baseline, with respect to the number of generated states, in theory. Experiments on 4 resource-centric domains and 3 domains with time windows show that both algorithms perform significantly better than the baseline in practice, and that they are complementary to each other in terms of finding explanations on resource- and time-centric domains.

2 Preliminaries

2.1 Planning Formalism

A finite-domain representation (FDR) [B¨ackstr ¨om and Nebel, 1995] planning task with soft-goals is a tuple τ =

(V,A, I,Ghard ,Gsoft ), where V is a finite set of state variables v with domain D(v), A is a finite set of actions, and I is a complete assignment to V called initial state. Ghard and Gsoft are disjoint partial assignment to V called hard and soft-goal. A state is a complete assignment to V . Variablevalue pairs v = d are referred to as facts, and (partial) variable assignments are identified by sets of facts. The value of v in the (partial) variable assignments s is referred to as s(v). Each action consists of a precondition and effect (prea , effa) defined as partial assignments to V . An action a is applicable in state s (appl(a, s)) if prea ⊆ s. Applying a to s, denoted by s[[a]] = s′ , changes the values of s to s′ (v) := effa(v) if effa(v) is defined and s′ (v) := s(v) otherwise. The resulting state of an iteratively applicable action sequence π is denoted by s[[π]]. A plan is an action sequence π where Ghard ⊆ I[[π]]. It achieves the soft-goalsGsoft∩I[[π]]. Instead of a cost-function with an upper bound, as in oversubscription planning by [Smith, 2004; Domshlak and Mirkis, 2015], here we consider constraints such as resources and time as a limiting factor for achievable soft-goals. The prefix a0 · · · ai of plan π = a0 · · · ai, aj · · · an is denoted by prefix(π, aj).

Running Example Our running example is based on the IPC Rovers domain. A rover must collect up to three samples S0, S1, S2 and upload the data to a relay satellite. The rover can perform three different actions: move between locations, take a sample when it is at the corresponding location, and upload the collected data at l0 or l3. The road map and the initial location of the rover are depicted on the left in Figure 1.

2.2 Planning with Consumed Resources

A consumed resource ρ with domain D(ρ) = [0, ρmax] ⊂ N has an initial value initρ ∈ D(ρ) and a function δρ : A ↦→ N that maps each action to the amount of resource consumed by that action. A state represents a complete assignment to V ∪ {ρ}. Action a is applicable in state s if prea ⊆ s and the remaining value of ρ is sufficient to execute the action s(ρ) ≥ δρ(a). Applying a in s decreases the resource by δρ(a): s[[a]](ρ) = s(ρ) - δρ(a). The amount of resource ρ consumed by an action sequence π is given by con(π) = ∑a∈π δρ(a). An extension to multiple resources is defined accordingly, where the set of all resources is denoted by R. In our running example, there is battery ρb as a resource.

2.3 Planning with Simple TimeWindows

We restrict ourselves to a concept of time that can be compiled to classical planning. This means discrete time units and no parallel execution of actions. A (start) time window is a tuple W = (AW , o, c) with 0 ≤ o ≤ c ≤ tmax. The application of the actions in AW ⊂ A is constrained by the opening time o and closing time c. The function δt : A ↦→ N maps each action to its execution duration. The passed time units are represented by the variable t with domain D(t) = [0, tmax]. A state represents a complete assignment to V ∪ {t}. Action a is applicable in state s if prea ⊆ s and if a ∈ AW then o ≤ s(t) ≤ c. Applying a in s increases the passed time by δt(a): s[[a]](t) = s(t) + δt(a). The execution duration of an action sequence π is given by dur(π) = ∑a∈π δt(a) and the execution time point of action a in π by exec(π, a) = dur(prefix(π, a)). An extension to multiple time windows is defined accordingly, where the set of all time windows is denoted with W. In our example, there is one time window WU = ({upload(Si) | i ∈ {0, 1, 2}}, 4, 6) which allows to upload data to the relay only between the time points 4 and 6.

2.4 Explanation Framework

In [Eifler et al., 2020a; Eifler et al., 2020b] Gsoft represents a set of plan properties, specifically LTLf plan-preference formulas compiled into soft-goal facts [Baier and McIlraith, 2006; Edelkamp, 2006]. The framework uses conflicts between these plan properties to generate answers to the users question. The soft-goals X, Y ⊆ Gsoft conflict each other if all plans of τ that achieve all g ∈ X, do not achieve all g ∈ Y . The strongest dependencies of this kind are given by the minimal unsolvable goal subsets (MUGS) X ∪ Y = G ⊆ Gsoft where G cannot be achieved but every G′ ⊊ G can. The set of all MUGS for a task τ is denoted by MUGS(τ).

3 Conflict Explanation Through Relaxations

We provide explanations for a soft-goal conflict based on minimal constraint relaxations under which the conflict disappears. In the following sections, we define the relaxations that are considered and how we identify explanations based on a given set of relaxed tasks.

3.1 Relaxation Orders

The most general property of an abstraction or relaxation T ′ of a planning task T is that all plans of T are preserved [Culberson and Schaeffer, 1998; Edelkamp, 2001; Seipp and Helmert, 2013]. This gives the most general definition of a relaxed task as:

Definition 1 (Relaxed Task). Let T be a planning task and Π(T) the set of all possible plans for task T. Then T ′ is a relaxed task of T (denoted by T ⊑ T ′ ) iff Π(T ) ⊆ Π(T ′ ).

Our explanation approach and algorithms make no further assumptions about the specific implementation of relaxation. To compute the explanation for a conflict C ∈ MUGS(T), we assume a final set of relaxed tasks T for T , where T ∈ T and for all T ′ ∈ T : T ⊑ T ′ , is given. For T the relation Ti ⊑ Tj represents a partial order, which we will use to define a minimal relaxed task that resolves C. The partially ordered set ˆ T = (T,⊑) we call in the following a relaxation order for T. The functions CU(T ′ ) and CL(T ′ ) denote the upper and lower covers of T ′ within ˆ T . Given a partially ordered set S then the upper cover of an element e ∈ S is the set CU(e) = {e′ ∈ S | e′ > e ∧ ∄e′′ ∈ S : e′ > e′′ > e}, and the lower cover the set CL(e) = {e′ ∈ S | e′ < e ∧∄e′′ ∈ S : e′ < e′′ < e}. One of our algorithms additionally assumes, that ˆ T has a supremum.

3.2 Resource and Time Constraint Relaxations

Next we instantiate the above with resource and time window constraint relaxations.

Resource Constraint Relaxations

A task with consumed resources can be relaxed by increasing the initial resource value.

Definition 2 (Resource Relaxed Task). Let T = (τ,R) be a planning task τ with resources R. Then a resource relaxed task for resource ρ ∈ R is defined as T ′ = (τ,R′ ) where ρ is replaced by resource ρ′ with D(ρ) = D(ρ′ ) = [0, ρmax], δρ′ = δρ and ρmax ≥ initρ′ ≥ initρ.

A resource relaxed task indeed represents a relaxed task according to Definition 1:

Proposition 1. Let T ′ be a resource relaxed task of T . Then, Π(T ) ⊆ Π(T ′ ).

Making the application of an action cheaper by reducing δρ is another way to relax a task with respect to a resource. This is almost equivalent to increasing the initially available resource, given that the resource is exhaustible and the action appears once in the plan. We use increasing resource availability as a proxy for any reduction in resource consumption.

Proof sketch: Π(T) ⊆ Π(T ′ ), because every action sequence π = a0 · · · an applicable in I of T is also applicable in I ′ of T ′ . For all actions ai ∈ π with πi = prefix(π, ai), s = I[[πi]], s′ = I ′ [[πi]] and c = con(πi), ai is applicable in s′ because ai is applicable in s and s(V ) = s′ (V ) and initρ - c = s(ρ) < s′ (ρ′ ) = initρ′ - c.

Using the set Tρ of all resource relaxed tasks of task T for ρ, we get a well-defined relaxation order ˆ Tρ = (Tρ,⊑) for T. Since all Ti ∈ Tρ are exclusively distinguished by initρi we have T ⊑ T ′ iff initρ < initρ′ , which results in a total order for Tρ. The task T ′ where initρ′ = ρmax represents the supremum of ˆ Tρ. The upper/lower cover of T ′ ∈ Tρ is the relaxed task where the initial resource value is one unit larger/smaller than in T ′ .

For our running example, we have four relaxed tasks for the battery Tρb = {Ti | i ∈ {7, 8, 9, 10}}, where in Ti the initial battery level is i.

Time Constraint Relaxations

A task with simple time windows can be relaxed by increasing the time window, either by decreasing the opening time or by increasing the closing time.

Definition 3 (Time-Window Relaxed Task). Let T = (τ,W) be a planning task τ with simple time windows W. Then a relaxed task for time window W = (AW , o, c) ∈ W is defined as T ′ = (τ,W′ ) where W is replaced by W ′ = (AW , o′ , c′ ) with 0 ≤ o′ ≤ o ≤ c ≤ c′ ≤ tmax.

A time-window relaxed task indeed represents a relaxed task according to Definition 1:

Proposition 2. Let T ′ be a time-window relaxed task of T. Then, Π(T ) ⊆ Π(T ′ ).

Proof sketch: Π(T) ⊆ Π(T ′ ), because every action sequence π = a0 · · · an applicable in I of T is also applicable in I ′ of T ′ . For all actions ai ∈ π, exec(π, ai) is the same in both tasks and with πi = prefix(π, ai), s = I[[πi]] and s′ = I ′ [[πi]], ai is applicable in s′ because ai is applicable in s and if ai ∈ AW then o′ ≤ o ≤ exec(π, ai) ≤ c ≤ c′ .

An alternative approach to relax a task with respect to time constraints is the reduction of the execution time of an action by decreasing δt. However, in addition to affecting multiple time windows, handling the explosion of possible relaxed tasks is not trivial, which is why we leave this for future work.

The subsumption relation of the intervals [o′ , c′ ] for time window W yields the partial order for ˆ TW = (TW,⊑), where TW is the set of all time-window relaxed tasks of T with respect to W. The task with W ′ = (AW , 0, tmax) is the supremum of ˆ TW. The upper/lower cover of T ′ ∈ TW are the relaxed tasks where either o is decreased/increased or c is increased/decreased by one compared to T ′ .

For our running example we have 25 different relaxed tasks for the upload windowTWU = {Ti,j | i ∈ {0, 1, 2, 3, 4}∧j ∈ {6, 7, 8, 9, 10}}, where in Ti,j the opening time is at i and the closing time at j.

3.3 Conflict Explanation

We aim to generate explanations for the conflicts in MUGS(T). Given a relaxation order, we can now define for each conflict whether a task is minimally relaxed for it.

Definition 4 (Minimally Relaxed Task). Let ˆ T = (T,⊑) be a relaxation order for task T and C ∈ MUGS(T) a conflict. Then T ′ ∈ T is minimally relaxed for C /∈ MUGS(T ′ ) if for all T ′′ ∈ T : T ′′ < T ′ → C ∈ MUGS(T ′′ ).

Thus, a minimally relaxed task for conflict C is one in which C is not a conflict, but for all less relaxed tasks it is. All conflicts in MUGS(T), for which T ′ ∈ ˆ T is minimally relaxed are denoted by mr-MUGS( ˆ T , T ′ ). The explanation for a conflict in MUGS(T) can then be defined as:

Definition 5 (Conflict Explanation). Let T be a task with conflict C ∈ MUGS(T) and ˆ T a relaxation order for T. Then the set of all minimally relaxed tasks for C, E( ˆ T ,C) = {T ′ | C ∈ mr-MUGS( ˆ T , T ′ )}, is the conflict explanation for C.

To illustrate the explanation for conflict C = {S0, S2} in our running example, we use the diagram in Figure 2. The minimal relaxed tasks and therefore the explanations are given as E = {T1,6, T4,7}: "Sample S0 and S2 can not both be uploaded, because the upload window, needs either to start 3 time units earlier or to end 1 time unit later".

Algorithm 1 Internal Constraint Reuse (ICR)

1: Given: relaxation order ˆ T , heuristic h 2: function COMPUTEMSGS( ˆ T , h) 3: M← {} ▷map of MSGSs 4: while HASNEXT( ˆ T ) do 5: ˆ T ← NEXT( ˆ T ) ▷current relaxed task 6: M[ ˆ T] ← ⋃ ˆ T ′∈CL( ˆ T ) M[ ˆ T ′ ] ▷propagate MSGS 7: O ← {INIT( ˆ T )} ▷initial state of relaxed task 8: while |O| ̸= 0 do 9: s ← NEXT(O, h) ▷next state acording to expansion order 10: if Ghard ⊆ s then ▷update MSGS 11: M[ ˆ T ] ← EXTEND(M[ ˆ T ], s ∩ Gsoft ) 12: if (Ghard ∪ Gsoft ) ⊆ s then ▷check and propagate solvability 13: ∀T ′ ∈ ˆ T ∧ ˆ T ⊑ T ′ : M[T ′ ] ←Ghard ∪Gsoft 14: break 15: O ← O ∪ {s′ ∈ SUCC( ˆ T, s) | ¬PRUNE( ˆ T ,M[ ˆ T ], h, s′ )} 16: return M

4 Internal Constraint Reuse (ICR)

In the following, we introduce two algorithms that given a relaxation order ˆ T compute the maximal solvable goal subsets (MSGS) for each task. The MSGS can then be used to compute the mr-MUGS of each task as follows.

FromMSGS to mr-MUGS AMSGS is a soft-goal subset G ⊆ Gsoft where G can be achieved but every G′ ⊋ G cannot. Given MSGS(T ′ ) for T ′ ∈ T we compute mr-MUGS( ˆ T , T ′ ) in two steps. First, we compute MUGS(T ′ ) by performing a bottom-up tree search over all subsets of Gsoft and use the MSGS as a fast solvability check as introduced by [Eifler et al., 2020b]. Then, the MUGS for which T ′ is minimally relaxed are computed as mr-MUGS( ˆ T , T ′ ) = MUGS(T) ∩ ((⋂T ′′∈CL(T ′ ) MUGS(T ′′ )) \ MUGS(T ′ )).

MSGS Computation Eifler et al. [2020b] compute the MSGS for a task by exhaustively exploring the state space while tracking all reached MSGS. To reduce the search space size they introduce a pruning function, which prunes all states from which no superset of the current MSGS is reachable.

Extending this algorithm, given a relaxation order ˆ T = (T, ⊑) for T , we compute the MSGS for all T ′ ∈ T by iterating over T according to the partial ordering, starting with T , and computing the MSGS for each task individually. Since all plans are preserved, for all Ti, Tj ∈ T with Ti ⊑ Tj , all softgoals G ⊆ Gsoft that are reachable in Ti are also reachable in Tj . Thus, the MSGS of Ti can be propagated to Tj .

PseudoCode of ICR The pseudo code of the Internal Constraint Reuse (ICR) algorithm is given in Algorithm 1. The underlying search algorithm for the state space exploration of one task is depth first search (DFS) guided by a heuristic (see [Eifler et al., 2020b]). This is abstracted by the function NEXT(O, h), which mimics the expansion order of DFS. M (line 3) is a map from task to a set of soft-goal subsets storing the MSGS for each task. The aforementioned propagation of MSGS is realized by initializing M[ ˆ T] with all MSGS reached in the lower cover of ˆ T (line 6). Iterating over the relaxed tasks according to the partial ordering is represented by the functions HASNEXT( ˆ T ) and NEXT( ˆ T ). The order of incomparable elements is resolved randomly.

Algorithm 2 Search Space Reuse (SSR)

1: Given: relaxation order ˆ T , heuristic h 2: function COMPUTEMSGS( ˆ T , h) 3: Ts ← SUPREMUM( ˆ T ) ▷maximal relaxed task 4: M← {} ▷map of MSGSs 5: F ← {} ▷map of search frontiers 6: O← INIT(Ts) ▷initial state of maximally relaxed task 7: ˆ T ← NEXT( ˆ T ) ▷current relaxed task 8: while True do 9: while |O| ̸= 0 do 10: s ← NEXT(O, h) ▷next state acording to expansion order 11: if Ghard ⊆ s then ▷update MSGS 12: M[ ˆ T ] ← EXTEND(M[ ˆ T ], s ∩ Gsoft ) 13: if (Ghard ∪ Gsoft ) ⊆ s then ▷check and propagate solvability 14: ∀T ′ ∈ ˆ T ∧ ˆ T ⊑ T ′ : M[T ′ ] ←Ghard ∪Gsoft 15: break 16: Ssuc ← {s′ ∈ SUCC(Ts, s) | ¬PRUNE(Ts,M[ ˆ T ], h, s′ )} 17: F[ ˆ T] ←F[ ˆ T] ∪ {s′ , ∈ Ssuc | ¬APPL( ˆ T , π(s′ ))} 18: O←O∪ {s′ ∈ Ssuc | APPL( ˆ T , π(s′ ))} 19: if ¬HASNEXT( ˆ T ) then 20: return M 21: ˆ T ← NEXT( ˆ T ) ▷current relaxed task 22: M[ ˆ T] ← ⋃ ˆ T ′∈CL( ˆ T ) M[ ˆ T ′ ] ▷propagate MSGS 23: FC ← ⋃ ˆ T ′∈CL( ˆ T) {s′ ∈ F[ ˆ T ′ ] | ¬PRUNE(Ts,M[ ˆ T ], h, s′ )} 24: F[ ˆ T] ← {s′ ∈ FC | ¬APPL( ˆ T , π(s′ ))} 25: O← {s′ ∈ FC | APPL( ˆ T , π(s′ ))}

M[ ˆ T ] is only updated (line 11) in case no superset has already been reached: EXTEND(M,G) returns M if there is a G′ ∈ M : G ⊆ G′ and {G′ ∈ M|G′ ⊈ G} ∪ {G} otherwise. The generation of successor states of state s according to the semantics of task T (SUCC(T, s)) is based on standard progression (see Sections 2.2 and 2.3). States are pruned (line 15) if no superset of soft-goals or the hard goal cannot be reached: PRUNE(T ′ ,M, h, s) returns true if Ghard ⊈ R ∨ ∃G ∈ M : R ∩ Gsoft ⊂ G, where R is the set of facts reachable from state s in task T ′ according to heuristic h and false otherwise. This can for example be realized by checking for each fact whether its hmax [Haslum and Geffner, 2000] estimation is finite, for more details we refer to [Eifler et al., 2020b]. If a state satisfies all hard and soft goals the search for the current task can be terminated early (line 12). All more relaxed tasks are also solvable, so their MSGS are updated accordingly (line 13). Tasks whose MSGS have already been determined are skipped by HASNEXT/NEXT.

5 Search Space Reuse (SSR)

ICR causes overhead, because equivalent states are generated multiple times in the separate search spaces. In addition to the MSGS, it can be beneficial to reuse the search space too.

Since all plans are preserved in the relaxations T of task T , for all T ′ ∈ T and the most relaxed task Ts = supremum( ˆ T ) holds (⋃T ′′∈CL(T ′ ) ST ′′) ⊆ ST ′ , where ST ′ are the states reachable from the initial state Is of Ts by plans of T ′ . Thus, we can base the computation of the MSGS for all relaxed tasks on the search space of Ts. We begin by exploring the reachable state space for T. All states that are generated, but which are not reachable in T, are stored in a search frontier. To decide whether a state s is reachable in a task T ′ , we check whether the action sequence π(s) leading to s is applicable in T ′ (APPL(T ′ , π(s))). In our example, states reached by paths consuming more than 7 energy units are not reachable in T7 and are therefore stored in the frontier. In subsequent iterations, the search frontiers of less relaxed tasks are further extended for more relaxed tasks. For example, for T8 the frontier states of T7 are further extended. This limits the states generated for each task to the newly reachable states.

PseudoCode of SSR The pseudo-code of the Search Space Reuse (SSR) algorithm is depicted by Algorithm 2. Unless explicitly mentioned, the algorithm parts work as described for Algorithm 1. The map F (line 5) stores for each task ˆ T the states which were generated during the search for ˆ T but were not reachable (line 17). In the first iteration, the openlist is initialized with the initial state of the most relaxed task Ts (line 6). In each subsequent iteration, it is initialized with the states in F of all tasks in the lower cover of ˆ T that are reachable in ˆ T (line 23-25). States are pruned by following the same approach as in Algorithm 1 (line 16/23). However, instead of basing the pruning on the current relaxed task ˆ T it is based on the most relaxed task Ts, since otherwise states that might be reachable in more relaxed tasked, would be pruned.

6 Theoretical Comparison

The propagation of MSGS can improve the pruning function, which is beneficial to both ICR and SSR. Reusing the search space in SSR reduces duplicate work, but states are only pruned based on the reachability in the most relaxed task, not the current task. We compare the overall number of generated states by each algorithm as a measure to decide whether they are exponentially separated. As the baseline algorithm, we consider ICR without the propagation of MSGS.

Definition 6 (Exponential Separation). Let {T n |n ∈ N} be a family of planning tasks of size (number of facts and actions) polynomially related to n and S(X) the number of states generated by search method X. Then, search method X is exponentially separated from search method Y iff |S(Y ) - S(X)| is exponential in n.

To give a family of planning tasks to prove the exponential separations of the algorithms we consider a planning task, where a robot has to visit different locations. The robot's movement is restricted by the resource ρ, which can have the values {0, 1, 2}, with initial value 1. Moving between connected locations consumes the amount of resources depicted in the maps in Figure 3. There is one location annotated with K which holds a set of n keys. The robot can pick up one key at a time (without using any resources) if it is in the same location as the key. To take the dashed connection the robot has to hold all keys. Since the robot can pick up any combination of keys, there can be exponentially many search states.

In the following examples, the pruning function uses the h2 heuristic [Haslum and Geffner, 2000] to decide reachability.

Theorem 1. ICR and SSR are exponentially separated from the baseline.

Example Consider the map depicted on the left in Figure 3. In the first iteration with initρ = 1 ICR and the baseline generate 2 states (R at L0 and L1). SSR, with initρ = 2, generates the same two states and 2 additional states (R at L2 and L3), which are not reachable and stored in the frontier. For both ICR and SSR MSGS = {{L1}} is propagated. In the next iteration of ICR (initρ = 2), moving to L3 is pruned because no new locations are reachable from there. The same holds for SSR. This leads to 2 + 3 and 4 + 1 states for ICR and SSR respectively. For the baseline, the reachability of L1 is not propagated and moving to L3 is not pruned. Thus, we get 2+3+2 ∗ 2n states, for picking up any combination of keys.

Theorem 2. ICR is exponentially separated from SSR.

Example Consider the map depicted on the right in Figure 3. In the first iteration with initρ = 1, ICR generates only one state. Moving to L1 is pruned because h2 recognizes that L2 is not reachable with ρ = 1. In SSR, the weaker constraint initρ = 2 prevents pruning L1 and picking up any combination of keys. Thus, 1 + 2n reachable and 2n (at L2 with any combination of keys) unreachable states are generated. In the last iteration in ICR with initρ = 2 visiting L2 via the upper connection and extending the MSGS to {{L2}} leads to early termination. The same holds for SSR. This results in 1 + 3 states for ICR and 1 + 2 ∗ 2n for SSR.

7 Experiments

We implemented both algorithms in the Fast Downward planning system [Helmert, 2006], extending the code base of Eifler et al. [2020b] and using hmax as a base heuristic for the pruning function 1 . The experiments were run on Intel E52660 machines running at 2.20 GHz, with a time (memory) limit of 2h (4GB) per benchmark instance.

Benchmark Our benchmark consists of 4 resourceconstraint domains (Blocksworld, NoMystery, Rovers R, TPP) and 3 domains (Parent's Afternoon, Rovers T, Satellite) with time constraints. The former part builds on the resource constraint benchmark by Eifler et al. [2020b]. In each instance there are two individual resources R. For each resource ρ ∈ R we generated one benchmark instance, scaling initρ between 0 and two times the initial value in the original instance. Rover T and Satellite are extension of the IPC domains with data upload windows for Rovers and time windows to take the images for Satellite. Parents'Afternoon [Eifler et al., 2022] models a parent's afternoon routine, including shopping and family member activities. The execution of these activities is constraint by time windows. For each time window W ∈ W we generated one benchmark instance. For Parent's Afternoon and Satellite, each time window is relaxed between its original size and the maximal value of the time variable domain. For Rovers the relaxation of an upload window is additionally bounded by the other upload windows. Each benchmark instance has up to 5 plan properties that, for example, restrict the order in which two goal facts are to be achieved. All plan properties and the original goal facts of the instance are soft goals. There are no hard goals.

1 The source code and the benchmark are available at: https:// github.com/XPP-explainable-planning

7.1 Evaluation

The coverage results are shown in Table 1. An instance is considered to be solved, when the MUGS for all relaxed tasks are computed. Comparing the ICR to the baseline shows propagating the MSGS increases the coverage in 5 domains, while not decreasing it in any. SSR solves more instances in 4 domains, while it is worse than the baseline in 2. ICR clearly has the advantage over SSR in the resource domains, while it is the opposite in the time constraint domains.

The increase in reachable states caused by relaxing a time window is usually much smaller than for a resource. Increasing a time window only adds few more times at which a single action a ∈ AW could start. However, as a is also constrained by all other time dependent actions, there may not be many added reachable states. In contrast, relaxing a resource allows you to add new actions and increases the number of action orderings. This is in favor for SSR, because it only considers the newly reachable states. A comparison of the number of expansions each algorithm requires per relaxed task, as depicted in Figure 4, confirms this assumption. In the time constraint domains SSR expands more states than ICR in the first task, but has many fewer expansions than ICR thereafter. In the resource-constraint task, the stronger pruning function in ICR is advantageous for a wider span of relaxed tasks, such that SSR only needs fewer expansions in more relaxed tasks.

Problems may not be solved either due to the exhaustion of the time or the memory limit. For Blocksworld and all time constraint domains, all algorithms ran out of time. For the other resource constraint domains SSR failed due to the memory limit. In TPP ICR failed due to the time limit and in rovers due to the memory. In Nomystery failure of ICRwas cased by about 25% timeouts and 75% memory limit exhaustion. Overall, timeout is most common. This could be addressed by parallelization of tasks without a strict order.

8 RelatedWork

Sreedharan et al. [2019] explain the unsolvability of a task by identifying necessary subgoals of relaxed tasks, that are unachievable in the original task. However, due to use of relaxations based on projections on subsets of variables, this approach is not suitable for quantifying the relaxation necessary to make the task solvable. An 'excuse' for unsolvability, as defined by [G¨obelbecker et al., 2010], is a series of value changes in the initial state and additional objects to make a task solvable. Their approach does not provide an explanation for a specific conflict, but explains why the task is not solvable and focuses on pointing out errors in the model description. The scheduling system by Agraval et al. [2020] provide information about constraint relaxations for not scheduled activities. Their main focus is to identify all unmet constraints of an activity and present them alongside the schedule to facilitate user review. Their analysis does not yet include any reasoning on the extent to which a constraint needs to be relaxed to schedule the activity. The unsolvability certificates provided by the proof system of Eriksson et al. [2017; 2018] are not intended to be human-readable and do not provide information on how the task could be made solvable.

The resource and time window constraints we consider here, can be compiled to classical planning and relaxation can be represented by domain abstractions [Domshlak et al., 2009]. Resources constraint relaxation could additionally be simulated by cost bound relaxation in classical planning with multiple cost functions [Katz et al., 2019; Altman, 1999].

9 Conclusion

Our approach addresses the question why soft-goal conflicts exist by identifying the minimal relaxation under which a conflict disappears. Combined with the work of Eifler et al.[2020a; 2020b], this provides an explanation framework that can explain trade-offs between soft goals by identifying not only conflicts, but also options for resolving them. This not only helps to better understand why a conflict exists, but also whether it can be resolved. In addition it enables the user to evaluate the trade-offs and benefits of a relaxation.

Future work includes the evaluation in an application setting and the automatic identification of relevant relaxations for a user and conflict.

Acknowledgments

This material is based upon work supported by the Air Force Office of Scientific Research under award number FA955018-1-0245, and by the German Research Foundation (DFG) under grant 389792660 as part of TRR 248 (see https:// perspicuous-computing.science).