Marcel Steinmetz
email: steinmetz@cs.uni-saarland.de

Jörg Hoffmann
email: hoffmann@cs.uni-saarland.de

Olivier Buffet
email: olivier.buffet@loria.fr

Revisiting Goal Probability Analysis in Probabilistic Planning

Maximizing goal probability is an important objective in probabilistic planning, yet algorithms for its optimal solution are severely underexplored. There is scant evidence of what the empirical state of the art actually is. Focusing on heuristic search, we close this gap with a comprehensive empirical analysis of known and adapted algorithms. We explore both, the general case where there may be 0-reward cycles, and the practically relevant special case of acyclic planning, like planning with a limited action-cost budget. We consider three different algorithmic objectives. We design suitable termination criteria, search algorithm variants, dead-end pruning methods using classical planning heuristics, and node selection strategies. Our evaluation on more than 1000 benchmark instances from the IPPC, resource-constrained planning, and simulated penetration testing reveals the behavior of heuristic search, and exhibits several improvements to the state of the art.

Introduction

Goal probability maximization in MDPs is important in planning scenarios ranging from critical decision-making (e. g. maximizing the probability to survive) to security tests (analyzing the chances that an attacker may compromise a valuable asset), and generally in problems with unavoidable dead-ends (e. g. [START_REF] Kolobov | Heuristic search for generalized stochastic shortest path MDPs[END_REF][START_REF] Kolobov | A theory of goal-oriented MDPs with dead ends[END_REF][START_REF] Teichteil-Königsbuch | Stochastic safest and shortest path problems[END_REF]). The objective partly underlies the International Probabilistic Planning Competition (IPPC) [START_REF] Younes | The first probabilistic track of the international planning competition[END_REF][START_REF] Bryce | 6th international planning competition: Uncertainty part[END_REF][START_REF] Coles | A survey of the 7th international planning competition[END_REF], when planners are evaluated by how often they reach the goal in online policy execution.

We consider here the optimal offline setting, i. e., computing the exact maximum goal probability. We refer to this objective as MaxProb. While MaxProb certainly is relevant, there has been little work towards developing solvers. Optimal MDP heuristic search [START_REF] Barto | Learning to act using real-time dynamic programming[END_REF][START_REF] Hansen | LAO * : a heuristic search algorithm that finds solutions with loops[END_REF][START_REF] Bonet | Labeled RTDP: Improving the convergence of real-time dynamic programming[END_REF][START_REF] Mcmahan | Bounded real-time dynamic programming: RTDP with monotone upper bounds and performance guarantees[END_REF][START_REF] Smith | Focused real-time dynamic programming for MDPs: Squeezing more out of a heuristic[END_REF][START_REF] Bonet | Learning depth-first search: A unified approach to heuristic search in deterministic and non-deterministic settings, and its application to MDPs[END_REF] has been successful in expected-cost minimization, but suffers from a lack of admissible heuristic estimators of goal probability. The best known possibility is to detect dead-ends and set their estimate to 0, using the trivial estimate 1 elsewhere. Another major obstacle are complications arising from 0-reward cycles. As pointed out by [START_REF] Kolobov | Heuristic search for generalized stochastic shortest path MDPs[END_REF], MaxProb is equivalent to a non-discounted reward maximization problem, not fitting the stochastic shortest path (SSP) framework [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF] because non-goal cycles receive 0 reward and thus improper policies do not accumulate reward -∞. Kolobov et al. propose FRET (find, revise, eliminate traps), which admits heuristic search, but necessitates several iterations of complete searches, in between which FRET eliminates 0-reward cycles (traps). [START_REF] Hou | Revisiting risk-sensitive MDPs: New algorithms and results[END_REF] consider several variants of topological VI [START_REF] Dai | Topological value iteration algorithms[END_REF], solving MaxProb but necessitating to build the entire reachable state space. [START_REF] Kolobov | A theory of goal-oriented MDPs with dead ends[END_REF] and Teichteil (2012) consider objectives asking for the cheapest policy among those maximizing goal probability, also requiring FRET or VI. Other works addressing goal probability maximization (e. g. [START_REF] Teichteil-Königsbuch | Incremental plan aggregation for generating policies in MDPs[END_REF][START_REF] Camacho | From FOND to robust probabilistic planning: Computing compact policies that bypass avoidable deadends[END_REF] do not aim at guaranteeing optimality. In summary, heuristic search for MaxProb is challenging, and has only been addressed by [START_REF] Kolobov | Heuristic search for generalized stochastic shortest path MDPs[END_REF]. Kolobov et al.'s experiments run only one configuration of search (LRTDP [START_REF] Bonet | Labeled RTDP: Improving the convergence of real-time dynamic programming[END_REF]), with one possibility for dead-end detection (SixthSense [START_REF] Kolobov | Sixthsense: Fast and reliable recognition of dead ends in MDPs[END_REF]), on a single domain (Exploding-Blocks). This outperforms VI, but the dead-end detection is not used in VI so it is unclear to what extent this is due to the actual heuristic search, rather than the state pruning itself.

Given this: (i) What is actually the empirical state of the art in heuristic search for MaxProb? Are there other known algorithms, or variants thereof, that work better? (ii) What about simpler special cases, and weaker objectives, that are still practically relevant but that may be easier to solve?

Question (ii) is interesting because such special cases and weaker objectives do indeed exist. A practically relevant special case is probabilistic planning with acyclic state spaces. This applies, e. g., to IPPC TriangleTireworld. More importantly, planning with a limited action-cost budget, limited-budget planning, is acyclic when action costs are non-0, strictly decreasing the remaining budget. Furthermore, simulated penetration testing (pentesting), as per [START_REF] Hoffmann | Simulated penetration testing: From "Dijkstra" to "Turing Test++[END_REF], is acyclic. The MDP there models a network intrusion from the point of view of an attacker, which is acyclic because each exploit can be attempted at most once. In acyclic problems, there are no 0-reward cycles so we are facing an SSP problem and the need for FRET disappears.

Regarding weaker objectives, in addition to MaxProb, it is relevant to ask whether the maximum goal probability exceeds a given threshold θ, or to require computing the maximum goal probability up to a given accuracy δ. We refer to these objectives as AtLeastProb and ApproxProb respectively. For example, in pentesting AtLeastProb naturally assesses the level of network security: Can an attacker reach a target host (e. g. a customer data server) with probability greater than a given security margin (e. g. 0.01)?

Both AtLeastProb and ApproxProb allow early termination based on maintaining a lower (pessimistic) bound V L in addition to the upper (admissible/optimistic) bound V U . This is especially promising in AtLeastProb where we can terminate if the lower bound already is good enough (V L ≥ θ) or if the upper bound already proves infeasibility (V U < θ). Good anytime behavior, on either or both bounds, translates into early termination.

To answer our research questions (i) and (ii), we design an algorithm space characterized by (a) search algorithm, (b) dead-end pruning method, and (c) node selection strategy. For (a), we design variants of AO * and LRTDP maintaining upper and lower bounds for early termination, and we design a variant of FRET better suited to problems with uninformative initial upper bounds. We furthermore design a new probabilistic-state-space reduction method, via determinized bisimulation. For (b), we employ classical-planning heuristic functions, a connection not made before and which is especially promising in limited-budget planning where we can prune against the remaining budget.1 For (c), we design a comprehensive arsenal of simple strategies biasing node selection to foster early termination.

Our techniques are implemented in FD [START_REF] Helmert | The Fast Downward planning system[END_REF]). We explore their behavior on a benchmark suite including domains from the IPPC, resource-constrained planning, and pentesting, comprising 1089 instances in total. Amongst other things, we observe: substantial benefits of heuristic search, even with trivial initial estimates (+9% total coverage), more so with initial estimates based on dead-end detection (+12%); substantial benefits of early termination (e. g. for AtleastProb +8% with θ = 0.2 and +7% with θ = 0.9); and dramatic benefits of our FRET variant (+32%). Our state-space reduction method yields an optimal MaxProb solver that scales just as well in TriangleTireworld as the sub-optimal solver Prob-PRP [START_REF] Muise | Improved non-deterministic planning by exploiting state relevance[END_REF][START_REF] Camacho | From FOND to robust probabilistic planning: Computing compact policies that bypass avoidable deadends[END_REF]) -yet not only for the standard version where the goal can be achieved with certainty, but also for the limited-budget version where that is not so.

We omit some technical details. Full details are available in an online TR [START_REF] Steinmetz | Revisiting goal probability analysis in probabilistic planning[END_REF].

MDP Models

We consider a probabilistic extension of STRIPS, in two variants, with respectively without a limited action-cost budget. We specify first the unlimited-budget version. Planning The state space of a task Π is a probabilistic transition system (S, P, I, S ). Here, S is the set of states, each s ∈ S associated with its set F (s) of true facts. The initial state I is that of Π, the set of goal states S ⊆ S contains those s where G ⊆ F (s). The transition probability function P : S ×A×S → [0, 1] is defined as follows. Action a is applicable to state s if s ∈ S (goal states are absorbing) and pre(a) ⊆ F (s). By s o we denote the result of outcome o in s, i. e., F (s o ) = (F (s) ∪ add (o)) \ del (o). P (s, a, t) is p(o) if a is applicable to s and t = s o ,2 and is 0 otherwise (there is no transition). Absorbing states are those with no outgoing transitions (no applicable actions). The set of non-goal absorbing states -lost states -is denoted S ⊥ .

For limited-budget planning, we extend the above as follows. A limited-budget task is a tuple Π = (F, A, I, G, b), as above but now with a budget b ∈ R + 0 , and each outcome o being associated with a cost c(o) ∈ R + 0 . In addition to their true facts F (s), states s are also associated with their remaining budget b(s) ∈ R. States with negative remaining budget b(s) < 0 are legal and may occur, but are lost, s ∈ S ⊥ , because: the goal states s ∈ S are those where G ⊆ F (s) and b(s) ≥ 0; the actions a applicable to s are those where pre(a) ⊆ F (s) and at least one outcome fits within the remaining budget, i. e., there exists o ∈ O(a) so that c(o) ≤ b(s). In the outcome states s o , the outcome's cost is deduced from the budget, i. e., b(s o ) = b(s) -c(o).

Note here that, if c(o) > 0 for all o, then the state space is acyclic because every transition strictly reduces the remaining budget. Note further that the remaining budget is local to each state. If some states in a policy violate the budget, other parts of the policy (even other outcomes of the same action) can still continue trying to reach the goal. This differs from constrained MDPs [START_REF] Altman | Constrained Markov Decision Processes[END_REF], where the budget bound is applied globally to the expected cost of the policy. Compared to planning with continuous resource-consumption uncertainty [START_REF] Marecki | Towards faster planning with continuous resources in stochastic domains[END_REF][START_REF] Meuleau | A heuristic search approach to planning with continuous resources in stochastic domains[END_REF][START_REF] Coles | Opportunistic branched plans to maximise utility in the presence of resource uncertainty[END_REF], our form of limitedbudget probabilistic planning is restrictive. Yet it is still natural and relevant, suiting for example any problem asking to achieve a goal within a given number of steps.

A policy is a partial function π : S\(S ∪S ⊥ ) → A∪{ * }, mapping each non-absorbing state s within its domain either to an action applicable in s, or to the don't care symbol * . The latter will be used (only) by policies that already achieve sufficient goal probability elsewhere, so do not need to elaborate on how to act on s and its descendants. That is, we still require closed policies, and use * to explicitly indicate special cases where actions may be chosen arbitrarily. Formally, π(s) = * extends the domain of π by picking, for every t ∈ S ∪ S ⊥ reachable from s and where π(t) is undefined, an arbitrary action a applicable in t and setting π(t) := a. A policy π is closed for state s if, for every state t ∈ S ∪ S ⊥ reachable from s under π, π(t) is defined; π is closed if it is closed for the initial state I.

Following [START_REF] Kolobov | Heuristic search for generalized stochastic shortest path MDPs[END_REF], we formulate goal probability as maximal non-discounted expected reward where reaching the goal gives reward 1 and all other rewards are 0. The value V π (s) of a policy π closed for state s then is:

V π (s) = 1 s ∈ S 0 s ∈ S ⊥ t P (s, π(s), t)V π (t) otherwise The value of state s is V * (s) = max π:π closed for s V π (s).
For acyclic state spaces, we are facing an SSP problem (every run ends in an absorbing state in a finite number of steps). For cyclic state spaces, the Bellman update operator may have multiple sub-optimal fixed points, and updates from an optimistic (upper-bound) initialization are not guaranteed to converge to the optimum. One can either use a pessimistic initialization, or Kolobov et al.'s FRET method. We consider three different objectives (algorithmic problems) for goal probability analysis: MaxProb: Find an optimal policy, i. e., a closed π s.t.

V π (I) = V * (I). AtLeastProb: Find a policy guaranteeing a user-defined goal probability threshold θ ∈ [0, 1], i. e., a closed π s.t.

V π (I) ≥ θ. (Or prove that such π does not exist.) ApproxProb: Find a policy optimal up to a user-defined goal probability accuracy δ ∈ [0, 1], i. e., a closed π s.t.

V * (I) -V π (I) ≤ δ. We next examine search algorithms, pruning methods, and node selection strategies, to solve these problems.

Search Algorithms

We use VI as a baseline, and design variants of AO * and LRTDP. For VI, we make one forward pass building the reachable state space (actually its pruned subset, see next section). We initialize the value function as 0 everywhere. For acyclic cases, we then perform a single backward pass of Bellman updates, starting at absorbing states and updating children before parents. For the general case, we assume a parameter and run topological VI [START_REF] Dai | Topological value iteration algorithms[END_REF]): We find the strongly connected components (SCC) of the state space, and handle each SCC individually, children SCCs before parent SCCs. VI on an SCC stops when every state is -consistent, i. e. when its Bellman residual is at most . 3For AO * , we restrict ourselves to the acyclic case, where the overhead for repeated value iteration fixed points, inherent in LAO * (Hansen and Zilberstein 2001), disappears. Figure 1 shows pseudo-code. The algorithm incrementally constructs a subgraph Θ of the state space. The handling of duplicates is simple, identifying search nodes with states, as the state space is acyclic. For the same reason, simple backward updating suffices to maintain the value function.

procedure GoalProb-AO * initialize Θ to consist only of I;

Initialize(I) loop do if [MaxProb: V L (I) = 1] [AtLeastProb:V L (I) ≥ θ] [ApproxProb: V L (I) ≥ 1 -δ or V U (I) -V L (I) ≤ δ] then return π L endif /* early termination (positive) */ if [AtLeastProb: V U (I) < θ] then
return "impossible" endif /* early termination (negative) */ if ex. leaf state s ∈ S ∪ S ⊥ in Θ reachable using π U then select such a state s else return π U endif /* regular termination */ for all a and t where P (s, a, t) > 0 do if t not already contained in Θ then insert t as child of s into Θ; Initialize(t) else insert s as a new parent of t into Θ endif endfor BackwardsUpdate(s) endloop procedure Initialize(s):

V U (s) := 0 s ∈ S ⊥ 1 otherwise V L (s) := 1 s ∈ S 0 otherwise if s ∈ S ∪ S ⊥ then π L (s) := * endif
policy on V U , π L is the current greedy policy on V L . BackwardsUpdate(s) updates all of V U , π U , V L , π L .
As states may have several parents in Θ, we first make a backwards sweep to collect the sub-graph Θ| s ending in s.

Then we update Θ| s in reverse topological order.

Adopting ideas from prior work (e. g. [START_REF] Mcmahan | Bounded real-time dynamic programming: RTDP with monotone upper bounds and performance guarantees[END_REF][START_REF] Little | Prottle: A probabilistic temporal planner[END_REF][START_REF] Smith | Focused real-time dynamic programming for MDPs: Squeezing more out of a heuristic[END_REF])), we maintain two value functions, namely both an upper bound V U and a lower bound V L on goal probability. Both are initialized trivially, for lack of heuristic estimators of goal probability (dead-end detection, as a simple but non-trivial V U initialization, will be discussed in the next section). Nevertheless, both bounds can be useful for search. To refute an action, it often suffices to reduce V U for just one of its outcomes. Hence, even for trivial initialization, V U may allow to disregard parts of the search space, in the usual way of admissible heuristic functions. As we shall see, this kind of behavior occurs frequently. Furthermore, there are various possibilities for early termination. The lower bound enables positive early termination when we can already guarantee sufficient goal probability, namely 1 (MaxProb), θ (AtLeastProb), or 1-δ (ApproxProb). The upper bound enables negative early termination in AtLeastProb, when V U < θ. In ApproxProb, clearly we can terminate when V U (I) -V L (I) ≤ δ. 4Regarding correctness: Trivially, V U (s) and V L (s) indeed are upper respectively lower bounds on the goal proba-bility of the states s in Θ, at any point in time. Furthermore, π L is always a closed policy, because it applies the don't care symbol * at the non-absorbing leaf states in Θ (note also that * is applied only on those states). Its goal probability V π L (s) is at least the lower-bound goal probability,

V π L (s) ≥ V L (s), because V L (s) is monotonic.
For LRTDP, we consider the general case, including cyclic state spaces. We omit the pseudo-code, for space reasons (it is available in the TR). Like in GoalProb-AO * , we maintain V L in addition to V U . We test the exact same early termination criteria. Note that this is valid even in the general/cyclic case, i. e., if early termination applies then we can terminate the overall FRET process. We include an additional stopping criterion for trials in the cyclic case, also used by [START_REF] Kolobov | Heuristic search for generalized stochastic shortest path MDPs[END_REF], stopping if the current state s is -consistent. This keeps trials from getting trapped in 0reward cycles, yet preserves the property that, upon regular termination, all states reachable using π U are -consistent.

In the cyclic case, the V U fixed point found by LRTDP may be sub-optimal, so we have to use FRET. In the acyclic case, we use = 0, and a single call to LRTDP suffices.

To study early termination capabilities, for X ∈ {AO * , LRTDP} we will consider variants X| U and X| L , maintaining only V U respectively only V L . Early termination criteria involving the non-maintained bound are disabled. We write X| LU to make explicit that both bounds are used. For AO * | L , all non-absorbing leaf states in Θ are open (rather than only those reachable using π U ), and in case of regular termination we return π L . We do not consider a variant LRTDP| L as LRTDP without an upper bound does not make sense.

We finally design a variant of FRET, and a new statespace reduction method. FRET performs an iteration of heuristic searches, each finding a fixed point of V U . In between iterations, FRET runs a trap elimination step, which finds non-goal cycles in the greedy-policy graph with respect to V U , and forces the next search iteration to avoid these cycles. The "greedy-policy graph" here considers all actions greedy with respect to V U . We refer to this design as FRET-V U . Our alternative design, FRET-π U , instead considers the graph induced by the actions π U selected into the current greedy policy. This provides the same convergence guarantee (see the TR for the proof). FRET-V U may require less iterations, yet each trap elimination step may be much more costly. In particular, in goal probability analysis, V U often is 1 almost everywhere in the first step, and the graph considered by FRET-V U is almost the entire reachable state space.

Our reduction method computes a bisimulation of the all-outcomes determinization (e. g. [START_REF] Yoon | FF-Replan: a baseline for probabilistic planning[END_REF][START_REF] Little | Probabilistic planning vs replanning[END_REF]), using standard mergeand-shrink methods [START_REF] Helmert | Merge & shrink abstraction: A method for generating lower bounds in factored state spaces[END_REF]. We then run any MDP algorithm on the bisimulated state space. This is sound because bisimilar states have equivalent transition behavior, and transitions in the all-outcomes determinization are action outcomes in the original task. Thus bisimilar states are equivalent in the probabilistic state space (the bisimulation is a "homogenous partition" as per [START_REF] Dean | Model minimization in markov decision processes[END_REF]).

Dead-End Pruning

Dead-ends are states s where V * (s) = 0. One can treat such s exactly like lost states S ⊥ (except for setting π L (s) := * ). Apart from this pruning itself, for the heuristic search algorithms this provides a non-trivial initialization of V U , typically leading to additional search reductions. [START_REF] Kolobov | Heuristic search for generalized stochastic shortest path MDPs[END_REF] employ SixthSense [START_REF] Kolobov | Sixthsense: Fast and reliable recognition of dead ends in MDPs[END_REF], which learns dead-end detection rules by generalizing from information obtained using a classical planner. Here we instead exploit the power of classical-planning heuristic functions run on the alloutcomes determinization, readily available in our FD implementation framework. This works especially well in limited-budget planning, where we can use lower bounds on determinized remaining cost to detect states with insufficient remaining budget. Note that this is natural and effective using admissible remaining-cost estimators, yet would be impractical using an actual planner (which would need to be optimal and thus prohibitively slow). For the general case, we can use any heuristic function able to detect dead-ends (returning ∞), which applies to most known heuristics.

We experiment with state-of-the-art heuristic functions, namely (a) an admissible landmark heuristic as per [START_REF] Karpas | Cost-optimal planning with landmarks[END_REF] For limited-budget planning, we also considered to adopt the problem reformulation by [START_REF] Domshlak | Deterministic oversubscription planning as heuristic search: Abstractions and reformulations[END_REF] for oversubscription planning, which reduces the budget b using landmarks and in exchange allows to traverse yet nonused landmarks at a reduced cost during search. Somewhat surprisingly, however, pruning states whose reduced budget is < 0 is equivalent to the much simpler method pruning states whose heuristic (a) exceeds the remaining budget. The added value of Domshlak and Mirkis' reformulation thus lies, not in its pruning per se, but in its compilation into a planning language and the resulting combinability with other heuristics. We give more details in the TR.

Node Selection Strategies

In both GoalProb-AO * and GoalProb-LRTDP, good anytime behavior on V L and/or V U may translate into early termination. We explore the potential of fostering this via (1) biasing the tie-breaking in the selection of "best" actions π U greedy with respect to V U , and (2) biasing the choice of outcome states (AO * ), respectively the outcome-state sampling during trials (LRTDP). AO * | L is a special case where (1) does not apply but (2) is especially important as we are free to choose any open leaf state in the current search graph Θ.

We experimented with a variety of strategies. We give a brief summary only; details are available in the TR.

Our default strategy uses the standard in AO * and LRTDP. Tie-breaking for (1) is arbitrary, but fixed, i. e., π U (s) changes only if some other action becomes strictly better in s. Open outcome states (2) in AO * are selected arbitrarily, and the bias in LRTDP is by outcome probability. Our mostprob-outcome bias strategy in AO * prefers likely outcomes.

Our h-bias strategy prefers states with smaller h value, where the heuristic h is the same one used for dead-end pruning. In (1), we break ties in favor of actions minimizing the expected heuristic value, in (2) we weigh (and renormalize) the outcome probabilities by 1 h(t) * P (s, a, t). Inspired by BRTDP [START_REF] Mcmahan | Bounded real-time dynamic programming: RTDP with monotone upper bounds and performance guarantees[END_REF], our gap-bias strategy breaks ties in (1) by maximal expected gap, and weighs the outcome probabilities in ( 2) by [V U (t) -V L (t)] * P (s, a, t). Inspired by common methods in classical planning, e. g. [START_REF] Hoffmann | The FF planning system: Fast plan generation through heuristic search[END_REF][START_REF] Helmert | The Fast Downward planning system[END_REF]), our preferred actions strategy prefers in (1) actions used by delete-relaxed determinized plans.

In AO * | L , the default strategy is depth-first, the rationale being to try to reach absorbing states quickly. The h-bias strategy selects a deepest leaf with minimal h value, the preferred actions strategy selects a deepest open leaf reachable using only preferred actions. We furthermore experiment with a breadth-first strategy, just for comparison.

Experiments

We implemented the algorithms in Fast Downward (FD) [START_REF] Helmert | The Fast Downward planning system[END_REF]). FD's pre-processes were extended to handle PPDDL. The state of the art in optimal goal probability analysis is represented by particular points in our configuration space: topological VI and (FRET-V U using) LRTDP| U with dead-end pruning. The implementation by [START_REF] Kolobov | Heuristic search for generalized stochastic shortest path MDPs[END_REF], which uses the different dead-end detector Sixth-Sense, is not available anymore (personal communication with Andrey Kolobov). The TR includes a detailed comparison against the results reported by Kolobov et al.

Our aim being to comprehensively explore the relevant problem space, we designed a broad suite of benchmarks, 1089 instances in total, based on domains from the IPPC, resource-constrained planning, and pentesting. From the IPPC, we selected those PDDL domains in STRIPS format, or with moderate non-STRIPS constructs easily compilable into STRIPS. This resulted in 10 domains from IPPC'04 -IPPC'08; we selected the most recent benchmark suite for each of these. For resource-constrained planning, we adopted the NoMystery, Rovers, and TPP benchmarks by [START_REF] Nakhost | Resourceconstrained planning: A monte carlo random walk approach[END_REF], more precisely those suites with a single consumed resource (fuel, energy, money), which correspond to limited-budget planning. 5 We created probabilistic versions by adding uncertainty about the underlying road map, akin to the Canadian Traveler scenario, each road segment being present with a given probability (this is encoded through a separate, probabilistic, action attempting a segment for the first time). For simplicity, we set that probability to 0.8 throughout. For pentesting, we modified the POMDP generator by [START_REF] Sarraute | POMDPs make better hackers: Accounting for uncertainty in penetration testing[END_REF], which itself is based on a test scenario used at Core Security (http: 5 To make the benchmarks feasible for optimal probabilistic planning, we had to reduce their size parameters (number of locations etc). We scaled all parameters with the same number < 1, chosen to get instances at the borderline of feasibility for VI. //www.coresecurity.com/). The generator uses a network consisting of an exposed part, a sensitive part, and a user part. It scales the numbers H of hosts and E of exploits. We modified the generator to output Hoffmann's (2015) attack-asset MDP pentesting models. Sarraute et al.'s POMDP model and solver (SARSOP [START_REF] Kurniawati | SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces[END_REF], which is not optimal) scale to H = 6, E = 10. For our benchmarks, we fixed H = E for simplicity (and to obtain a number of instances similar to the other benchmark domains). We scaled the instances from 6 . . . 20 without budget limit, and from 10 . . . 24 with budget limit.

From each of the above benchmark task Π, except the pentesting ones, we obtained several limited-budget benchmarks, as follows. We set outcome costs to 1 where not otherwise specified. We determined the minimum budget, b min , required to achieve non-0 goal probability. For the resource-constrained benchmarks, b min is determined by the generator itself, as the minimum amount of resource required to reach the goal in the deterministic domain version. For all other benchmarks, we ran FD with A * and LM-cut on the all-outcomes determinization of Π. If this failed, we skipped Π, otherwise we read b min off the cost of the optimal plan and created several limited-budget tasks Π[C], differing in their constrainedness level C. Namely, following [START_REF] Nakhost | Resourceconstrained planning: A monte carlo random walk approach[END_REF], we set the global budget b in Π[C] to b := C * b min , so that C is the factor by which the available budget exceeds the minimum needed (to be able to reach the goal at all). We let C range in {1.0, 1.2, . . . , 2.0}.

For AtleastProb, we let θ range in {0.1, 0.2, . . . , 1.0} (θ = 0 is pointless). For ApproxProb, we let δ range in {0.0, 0.1, . . . , 0.9} (δ = 1 is pointless). On cyclic problems, the convergence parameter was set to 0.00005 (the same value as used by [START_REF] Kolobov | Heuristic search for generalized stochastic shortest path MDPs[END_REF]. All experiments were run on a cluster of Intel E5-2660 machines running at 2.20 GHz, with time/memory cut-offs of 30 minutes/4 GB.

Acyclic Planning

We consider first acyclic planning. This pertains to all budget-limited benchmarks, to pentesting with and without budget limit, as well as to IPPC TriangleTireworld (moves can be made in only one direction so the state space is acyclic). We consider the 3 objectives MaxProb, AtLeast-Prob, and ApproxProb. We run all 6 search algorithm variants, each with up to 5 node selection strategies as explained. For dead-end pruning, we run LM-cut, as well as mergeand-shrink (M&S) with the state-of-the-art shrinking strategies based on bisimulation and an abstraction-size bound N ; we show data for N = ∞ and N = 100k (we also tried N ∈ {10k, 50k, 200k} which resulted in similar behavior). We also run variants without dead-end pruning. We use the deterministic-bisimulation (BS) reduced state space with VI (the cases where BS succeeds are easily solved by VI). Overall, we get 217 different algorithm configurations.

We first examine the behavior of search algorithms and pruning on MaxProb. We fix the node selection to default, and we omit AO * | LU and LRTDP| LU as, for MaxProb heuristic search, maintaining V L is redundant (early termination is dominated by regular termination). Of the pruning methods, LM-cut clearly stands out. For every search algorithm, it yields the by far best overall coverage. M&S has substantial advantages only in RectangleTireworld and NoMystery-b. Note that, for N = ∞, overall coverage is worse than for using no pruning at all. This is due to the prohibitive overhead, in some domains, of computing a bisimulation on the determinized state space. And, having invested this effort, it pays off more to use the bisimulation as a reduced MDP state space ("VI on BS"), rather than only for dead-end pruning. An extreme example is Triangle-Tireworld. Far beyond the standard benchmarks in Table 1 (triangle-side length 20), VI on BS scales to side length 74 in both the original domain and the limited-budget version. For comparison, the hitherto best solver by far was Prob-PRP [START_REF] Camacho | From FOND to robust probabilistic planning: Computing compact policies that bypass avoidable deadends[END_REF], which scales to side length 70 on the original domain, 6 and is optimal only for goal probability 1, i. e., in the presence of strong cyclic plans.

Of the search algorithms, AO * | L is better than VI only in case of early termination on V L = 1, when a full-certainty policy is found before visiting the entire state space. This happens very rarely here, and AO * | L is dominated by VI (this changes for AtLeastProb, Figures 3 (a) and 4 below). LRTDP| U clearly outperforms AO * | U , presumably because it tends to find absorbing states more quickly.

To gauge the efficiency of heuristic search vs. blind search on MaxProb, compare LRTDP| U vs. VI in Table 1. Contrary to the intuition that a good initial goal probability estimator is required for heuristic search to be useful, LRTDP| U is clearly superior. Its advantage does grow with the quality of the initialization; LM-cut yields the largest coverage 6 We could not run the limited-budget domain as Prob-PRP does not natively support a budget, and hard-coding the budget into PPDDL resulted in encodings too large to pre-process. * increase by far. However, even without dead-end pruning, i. e., with the trivial initialization of V U , LRTDP| U dominates VI throughout, and improves coverage in 8 of the 16 domains. Figure 2 sheds additional light on this by comparing the respective search space sizes directly. The nontrivial initialization using LM-cut clearly helps. But even without it, gains of around 1 order of magnitude occur frequently, and larger gains (up to 3 orders of magnitude) occur in rare cases. As previously hinted, these observations have not been made in this clarity before: While [START_REF] Kolobov | Heuristic search for generalized stochastic shortest path MDPs[END_REF] also report LRTDP to beat VI on MaxProb, they consider only a single domain; they do not experiment with trivially initialized V U ; and they do not use dead-end pruning in VI, so that LRTDP already benefits from a smaller state space, and the impact of heuristic search remains unclear.

We now turn to the weaker objectives, AtLeastProb and ApproxProb. We fix LM-cut for the (almost always most effective) dead-end pruning. We examine the power of early termination for different search algorithms and node selection strategies. This is best viewed as a function of the goal probability threshold θ in AtLeastProb, and of the desired goal probability accuracy δ in ApproxProb. VI forms a baseline independent of θ. Consider Figure 3.

For AtLeastProb (Figure 3 (a)), one clear feature is again the superiority of LRTDP over AO * . There is now the striking exception of AO * | L , however, which for small values of θ approaches (and in one case, surpasses) the performance of LRTDP. The depth-first expansion strategy is quite effective for anytime behavior on V L and thus for termination via V L (I) ≥ θ. It is way more effective than the heuristic search in AO * | LU . As we shall see below (Figure 4), it is often also more effective than LRTDP. In general, for all algorithms, using V L is a clear advantage for small θ. For larger θ, maintaining V L can become a burden, yet V U is of advantage due to early termination on V U (I) < θ. Algorithms using both bounds exhibit an easy-hard-easy pattern.

The spike at the left-hand side in Figure 3 (a), i. e., significantly worse performance for θ = 0.1 than for θ = 0.2, is an outlier due to the Pentest domains (without them, AO * | LU and LRTDP| LU exhibit a strict easy-hard-easy pattern). In contrast to typical probabilistic planning scenarios, in penetration testing the goal probability -the chances of a successful attack -are typically small, and indeed this is so in our benchmarks. Searches using an upper bound quickly obtain V U (I) < 0.2, terminating early based on V U (I) < θ for θ = 0.2. But it takes a long time to obtain V U (I) < 0.1.

For ApproxProb (Figure 3 sistently result in worse performance. We see again the superiority of LRTDP over AO * , with a similar though not as pronounced exception for AO * | L in δ regions allowing aggressive early termination. We also see again the superiority of algorithms using both bounds over those that don't.

Figure 3 (c) examines the effect of different node selection strategies in AtLeastProb (the relative performance of node selection strategies is the same in ApproxProb, so we do not include a separate figure for that). For readability, we show only the most competitive base algorithms, AO * | L , AO * | LU , and LRTDP| LU (as well as the VI baseline). For LRTDP, we show only default node selection, which consistently works a little better than the alternatives. For AO * | L , we see that the depth-first strategy is important (and way beyond breadth-first, which does worse than VI). The h-bias strategy is generally on par with depth-first. For AO * | LU , the main observation is that the most-prob-outcome bias is helpful, improving over the default strategy except for high values of θ. The h-bias consistently improves a bit on default AO * . The gap-bias and preferred actions strategies are not shown as they were consistently slightly worse (apparently, the gap-bias leads to a more breadth-first style behavior, while preferred actions mainly cause runtime overhead). To conclude our discussion of acyclic planning, Figure 4 exemplifies typical anytime behavior, i. e., the development of the V L (I) and V U (I) bounds on the initial state value, as a function of runtime, for LRTDP| LU and AO * | L (using default node selection because the alternatives are not bene-ficial for these algorithms). The benefit of LM-cut pruning is evident. Observe that AO * | L is way more effective than LRTDP in quickly improving the lower bound. Indeed, the runs shown here find an optimal policy very quickly. Across the benchmarks solved by both AO * | L and LRTDP, omitting those where both took < 1 second, in 56% of cases AO * | L finds an optimal policy faster than LRTDP. On (geometric) average, AO * | L takes 66% of the time taken by LRTDP for this purpose. On the downside, unless V * (I) ≥ θ, AO * | L must explore the entire state space. Its runs in Figure 4 exhaust memory for MaxProb. In summary, heuristic search is much stronger in proving that the maximum goal probability is found, but is often distracting for improving V L quickly.

LRTDP V U LRTDP V U LM-cut LRTDP V L LRTDP V L LM-cut AO * |L AO * |L LM-cut
As both parts of Figure 4 use the same base instance but with different constrainedness levels C, we can also draw conclusions on the effect of surplus budget. With more budget, more actions can be applied before reaching absorbing states. This adversely affects the upper bound (consistently across our experiments), which takes a much longer time to decrease (cf. C = 1.8 vs. C = 1.4 in Figure 4). The lower bound, on the other hand, often increases more quickly with higher C as it is easier to find goal states.

Cyclic Planning with FRET

We now consider cyclic planning, pertaining to the standard IPPC benchmarks, and to probabilistic NoMystery, Rovers, TPP without budget (nor resource-) limit. We run only LRTDP, as AO * is restricted to acyclic state spaces. We use the two different variants of FRET described earlier: FRET-V U as per [START_REF] Kolobov | Heuristic search for generalized stochastic shortest path MDPs[END_REF], and our new variant FRET-π U . We consider all 3 objectives, and the same 4 dead-end pruning methods (as LM-cut returns ∞ iff the cheaper heuristic h max does, we use h max here).

Table 2 shows coverage data for MaxProb. FRET-π U outperforms both VI and FRET-V U substantially. Note that, in all domains except ExplodingBlocks and Rovers, the advantage over VI is obtained even without dead-end pruning, i. e., for trivial initialization of V U . This strongly confirms the power of heuristic search even in the absence of good admissible goal probability estimators. Figure 5 compares search space sizes. Initialization using h max is useful, but gains of 3 orders of magnitude are possible even without it. The search space size gains in FRET-π U result in similar runtime gains (see the TR). The single exception is No-Mystery, where VI and FRET-V U visit the same states and FRET-π U visits ca. 5 times less states, but the larger number of FRET-π U iterations results in worse runtime, ca. 20 times compared to VI and ca. 5 times compared to FRET-V U .

FRET-V U FRET-π U -h max M&S on -h max M&S on -h max M&S on Domain # N ∞ BS N ∞ BS N ∞
With respect to [START_REF] Kolobov | Heuristic search for generalized stochastic shortest path MDPs[END_REF] experiments on ExplodingBlocks -the previous empirical state of the art -we observe (see TR for details): VI with h max pruning performs similarly to FRET-V U with h max pruning, showing that Kolobov et al.'s choice to not use pruning in VI indeed obfuscates the possible conclusions; Kolobov et al.'s FRET-V U also performs similarly, except on the largest instances where SixthSense detects more dead-ends yet this is more than outweighed by the larger runtime overhead; FRET-π U convincingly outperforms all other algorithms.

For the weaker objectives AtLeastProb and ApproxProb, as before we examine coverage as a function of θ respectively δ. Figure 6 shows the data for default node selection in AtLeastProb (the behavior for ApproxProb is qualitatively similar). By FRET| U respectively FRET| LU , we refer to FRET using LRTDP| U respectively LRTDP| LU .

For FRET-V U , the picture is similar to Figure 3 (a), FRET| LU -V U exhibiting an easy-hard-easy pattern due to the advantages of early termination. For FRET-π U , though, the curves are flat over θ. This is due to benchmark scaling: in each domain, there is an instance number x so that, below x, FRET-π U can solve all instances completely (solving

Conclusion

Optimal goal probability analysis is a notoriously hard problem, to the extent that the amount of work addressing it is limited. We clarified the empirical state of the art, and substantially improved it through a novel variant of FRET and through a novel state-space reduction method. We showed that there are opportunities arising from naturally acyclic problems, and from early termination on criteria weaker than maximum goal probability. We hope that this will inspire renewed interest in this important problem. Promising future directions include advanced admissible goal probability estimators, e. g. from abstractions interpreted as boundedparameter MDPs [START_REF] Givan | Boundedparameter Markov decision processes[END_REF]; hybrids of heuristic search with Monte-Carlo tree search, geared at good anytime behavior and thus early termination; and the exploitation of goal probability monotonicity as a function of remaining budget. Simulated pentesting is an application worth algorithms research in it own right. Partial-order reduction appears especially promising there.

  tasks are tuples Π = (F, A, I, G) consisting of a finite set F of facts, a finite set A of actions, an initial state I ⊆ F , and a goal G ⊆ F . Each a ∈ A is a pair (pre(a), O(a)) where pre(a) ⊆ F is the precondition, and O(a) is the finite set of outcomes o, each being a tuple (p(o), add (o), del (o)) of outcome probability p(o), add list add (o) ⊆ F , and delete list del (o) ⊆ F . We require that o∈O(a) p(o) = 1.

Figure 1 :

 1 Figure1: AO * for MaxProb, AtLeastProb, and ApproxProb (as indicated), on acyclic state spaces. π U is the current greedy policy on V U , π L is the current greedy policy on V L . BackwardsUpdate(s) updates all of V U , π U , V L , π L . As states may have several parents in Θ, we first make a backwards sweep to collect the sub-graph Θ| s ending in s. Then we update Θ| s in reverse topological order.

  , (b) LM-cut (Helmert and Domshlak 2009), (c) several variants of merge-and-shrink heuristics, and (d) h max (Bonet and Geffner 2001) as a simple and canonical option. (a) turned out to perform consistently worse than (b), so we will report only on (b) -(d).

Figure 2 :

 2 Figure 2: Number of states visited, for VI (x) vs. LRTDP| U (y), with no pruning (left) and with LM-cut pruning (right).*

  (b)), smaller values of δ con-Total coverage in acyclic planning, for AtLeastProb as a function of θ in (a) and (c), for ApproxProb as a function of δ in (b). Node selection varies in (c), default used in (a) and (b). All configurations use LM-cut dead-end pruning.

Figure 4 :

 4 Figure 4: Anytime behavior in LRTDP| LU (V U and V L ) and AO * | L (V L only), as a function of runtime. Elevators instance 11, without pruning and with LM-cut pruning, for constrainedness levels C = 1.4 (left) and C = 1.8 (right).

VI

Figure 5 :

 5 Figure 5: Number of states visited, for VI (x) vs. FRET-π U (y), with no pruning (left) and with h max pruning (right).

Figure 6 :Figure 7 :

 67 Figure6: AtLeastProb coverage in cyclic planning, as a function of θ, using h max pruning and default node selection. MaxProb), while above x neither V L (I) nor V U (I) can be improved at all, up to the time/memory limit. On smaller instances, we do get the expected anytime behavior. Figure7exemplifies this. The easy-hard-easy pattern would thus emerge for smaller runtime/memory limits.

Table 1 :

 1 Table 1 shows coverage data (runtime results are qualitatively similar, see the TR). MaxProb coverage (number of tasks solved within time & memory limits) in acyclic planning. Best values in boldface. Domains "-b" modified with budget limit. "#":

			VI	AO * | L	AO * | U	LRTDP| U	VI
			-LM M&S	-LM M&S	-LM M&S	-LM M&S on
	Domain	#	N ∞	N ∞	N ∞	N ∞ BS
				IPPC Benchmarks
	TriaTire	10	4 4 4 4	4 4 4 4 10 10 10 10 10 10 10 10 10
			IPPC Benchmarks with Budget Limit
	Blocksw-b	66 24 28 24 24 24 28 24 24 24 28 24 24 24 28 24 24 24
	Boxworl-b	18	0 3 0 0	0 3 0 0	0 3 0 0	0 3 0 0	0
	Drive-b	90 90 90 90 52 90 90 90 52 90 90 90 52 90 90 90 52 52
	Elevator-b	90 71 82 72 33 70 82 72 33 65 77 67 33 79 86 79 33 33
	ExpBloc-b	84 32 46 38 37 32 46 38 37 39 57 39 37 38 65 39 37 37
	Random-b	60 27 33 35 33 27 33 35 33 35 44 36 33 36 44 36 33 33
	RecTire-b	36 30 31 36 36 30 31 36 36 30 31 36 36 30 31 36 36 36
	Tirewor-b	90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90
	TriaTire-b	60 45 52 52 52 45 52 52 52 46 55 55 55 47 57 57 57 60
	Zenotra-b	36 15 16 16 18 15 16 16 18 14 16 16 17 15 17 16 17 17
		Probabilistic Resource-Constrained Benchmarks with Budget Limit
	NoMystery-b 60 11 37 43 44 11 36 42 43 12 39 47 47 12 41 50 50 51
	Rovers-b	60 23 39 31 40 23 38 31 40 23 44 33 45 25 46 35 46 50
	TPP-b	60 18 35 25 25 16 35 24 24 15 37 26 22 19 38 27 25 26
				Pentesting Benchmarks
	Pentest	15	9 9 9 8	9 9 9 8	9 9 9 8	9 9 9 8	8
	Pentest-b	90 57 63 62 37 57 63 62 37 57 63 63 37 57 63 63 37 37
		925 546 658 627 533 543 656 625 531 559 693 641 546 581 718 661 555 564

number of instances. "-": no pruning; else pruning, against remaining budget on "-b" domains, based on h = ∞ on other domains. "LM": LM-cut; "M&S": merge-and-shrink, "N " size bound N = 100k, "∞" no size bound. "VI on BS": VI run on reduced (bisimulated) state space.

Table 2 :

 2 MaxProb coverage in cyclic planning. Best values in boldface. FRET-V U is as per[START_REF] Kolobov | Heuristic search for generalized stochastic shortest path MDPs[END_REF], FRET-π U is our modified version. Both use LRTDP| U . Dead-end pruning variants: "-" none, else based on heuristic value ∞, for h max respectively merge-and-shrink ("N " size bound N = 100k, "∞" no size bound). "on BS": run on reduced (bisimulated) state space.

On the side, we discover that Domshlak and Mirkis' (2015) landmarks compilation is, per se, equivalent to such pruning.

We assume here that each o ∈ O(a) leads to a different outcome state. This is just to simplify notation (our implementation does not make this assumption).

Focused topological VI eliminates sub-optimal actions in a pre-process to obtain smaller SCCs. While this can be much more runtime-effective, it still requires to build the entire state space, doing which was the only reason for VI failures in our experiments. So we do not consider focused topological VI here.

The V L = 1 and V L (I) ≥ 1 -δ criteria are redundant when maintaining an upper bound, i. e., for heuristic search, where they are subsumed by regular termination respectively termination on V U (I) -V L (I) ≤ δ. In configurations not maintaining V U , however, these termination criteria can be very useful to reduce search.

Acknowledgments. This work was partially supported by the German Research Foundation (DFG), under grant HO 2169/5-1. We thank Christian Muise for his Probabilistic-PDDL extension of the FD parser. We thank Andrey Kolobov for discussions. We thank the anonymous reviewers, whose comments helped to improve the paper.


I -Introduction

The performance and operational limits of present and future Tokamak plasmas are influenced by the equilibrium profiles, shape and position e.g. vertical position stability in strongly shaped plasmas or onset of disruptive instabilities driven by profile gradients. Free boundary plasma equilibrium profiles can have a strong effect on the interpretation of all physical phenomena occurring in the plasma e.g. core/edge MHD stability characterization, plasma transport and auxiliary heating. It is thus a fundamental task to determine the plasma equilibrium using as many available input experimental data e.g. magnetic diagnostics (magnetic flux and poloidal magnetic field), density and temperature diagnostics and polarimetry diagnostics. In the framework of the EUROfusion Work Package on Code Development for Integrated Modelling, a scientific Kepler [1] workflow for the reconstruction of Tokamak plasma equilibrium was developed (Figure 1). It includes consolidated reconstruction codes such as EQUAL [2], CLISTE [3], EQUINOX [4] and post-processing error bar estimator SDSS [5], all using the same physics and machine data ontology and methods for accessing the data used in the European Integrated Modelling (EU-IM) framework [6]. Presently implemented modules (actors) are interfaced to "data bundles" e.g. magnetic sensors, Thomson scattering diagnostics as well as poloidal field coil data, are packed into a "machine bundle", to facilitate the data exchange in the workflow through selfconsistent datasets. The reconstruction codes feature polynomial or spline (natural or Bspline) representation for the profiles and non-uniform spatially distributed knots for the equilibrium regularisations are implemented. Equilibrium reconstructions relying on magnetics data only (magnetic diagnostic, PF/TF coils and iron core) or with added internal data (motional Stark effect, polarimetry or pressure) may be performed. For pedestal top/edge pressure profile assisted reconstructions, pre-processing of the experimental density and temperature data presently includes a median filter and time average around the time of interest, mapped to the flux coordinates obtained for that time in the previous (magnetics only) reconstruction. Ion density is assumed to be proportional to electron density and fast particle density is assumed negligible.

II -Motional Stark Effect assisted reconstructions

A JET hybrid discharge (#89140) was considered to highlight the influence of internal MSE data on the equilibrium reconstructions, with a plasma current and toroidal magnetic field of 1.4MA and 1.75T respectively, 12.5MW of NBI and 1.9MW of ICRH ([49-52s]).

EQUAL and EQUINOX results using magnetics only are shown in Figure 2 for t=47.45s with CHAIN1 EFIT used for comparison. Good agreement in the plasma boundary (<1cm for EQUAL, <2cm for EQUINOX at outer midplane) and divertor strike points (<2.5cm) is found and fitting errors in the magnetics are below the experimental 5mT error. Even with magnetics only, the regularisations in EQUAL permit some (insufficient in view of the ELMy discharge) traces for a pedestal at the edge. The safety factor q evidences the lack of fidelity of the automated EFIT reconstruction i.e. q(0)>1 throughout despite the sawtoothing character of the discharge. Inclusion of MSE data shows a clear improvement on the overall agreement in the q(s) profile (<5% difference in q(0) among the 3 codes) as shown in Figure 3. Differences in the regularisations and/or weighting on sensors might explain the deterioration in the agreement on plasma boundary and magnetic axis location.

III -Plasma pressure assisted reconstructions

For pressure assisted reconstruction, an AUG ELM-y discharge (#33173) was taken as example, at t=2.7s, characterized by Ip=1MA, B T =2.46T and total heating power (NBI+ECRH) of ~12MW. The CLISTE code, fine-tuned to AUG plasmas, is used as a reference. For magnetics only reconstructions (see Figure 4), EQUAL and EQUINOX yield similar plasma geometry (<1cm on outer midplane radius, <2 cm separation of X-point and <2cm separation on strike points) to CLISTE but are challenged on the q(s) on axis and showing little evidence of a pressure pedestal. The associated fitted edge pressure profile from the diagnostic data (Ni=Ne is assumed) is also shown in Figure 4. The pressure constraint closes the gap between the profiles obtained by the three codes (see Figure 5) and also reduces the average fit error of the magnetic sensor data for EQUAL and CLISTE (EQUINOX solution in vacuum based on a toroidal harmonic expansion fit to magnetic data, is insensitive to internal constraints). The pressure profile fed to CLISTE, based on averaged data 2ms before ELMs occurring in a 200ms period centred on t=2.7s, yields a slightly higher pedestal pressure (~17kPa).

IV -Conclusions

Results of a EU-IM workflow for equilibrium reconstruction applied to a JET and AUG discharge were shown. Magnetic, polarimetry and kinetic constraints are implemented and evidence an improvement in the fitted results although some differences to reference code suites in JET/AUG persist (fine-tuning options or data used may apply there).

Figure 1 -

 1 Figure1-Kepler workflow for equilibrium reconstruction of tokamak discharges. An optional postprocessing module FixBndCode[7] for the calculation of the high resolution equilibrium is shown.

Figure 2 -

 2 Figure 2 -Magnetics only reconstruction using EQUAL and EQUINOX and EFIT for comparison (rho_pol_norm -squared root of the normalised poloidal flux) for JET #89140 at t=47.45s.

Figure 3 -

 3 Figure 3 -Magnetics and MSE reconstruction for JET #89140 at t=47.45s. The EFTC run relaxes the J sep =0 constraint. Location and weights of regularisation knots not the same for the 3 codes.

Figure 4 -

 4 Figure 4 -Magnetics only reconstruction on AUG discharge #33173 at t=2.7s. Edge detail on pressure profile is shown (left). The pressure profile mapped to EQUAL and EQUINOX is also shown.

Figure 5 -

 5 Figure 5 -Magnetics and pressure assisted reconstruction on AUG discharge #33173 at t=2.7s. Detail on the pressure gradient close to the edge is also shown (right).

Acknowledgements

This work has been carried out within the framework of the EUROfusion Consortium and has received funding from the Euratom research and training programme 2014-2018 under grant agreement No 633053. IST activities also received financial support from "Fundação para a Ciência e Tecnologia" through project UID/FIS/50010/2013. The views and opinions expressed herein do not necessarily reflect those of the European Commission.