Conformance checking aims at assessing whether a process model and event data, recorded in an event log, conform to each other. In recent years, alignments have proven extremely useful for calculating conformance statistics. Computing optimal alignments is equivalent to solving a shortest path problem on the state space of the synchronous product net of a given Petri net and event data. State-of-the-art alignmentbased conformance checking implementations exploit the A∗-algorithm, a heuristic search method for shortest path problems, and include a wide range of parameters that likely influence their performance. In this paper, we present an exploratory empirical evaluation of parametrization of the A∗-algorithm used in alignment computation. Our initial results show that the performance of alignment computation greatly depends on adequate parametrization of the underlying search algorithm.
Process mining [
Early work in conformance checking focused on replaying behaviour in an
event log within a Petri net by “playing the token-game” [
The process mining tool-kit ProM [
In this paper we formalize the A∗-algorithm and associated
parametrization in terms of alignment computation, in line with the underlying
implementation in ProM. As such, this paper acts as a high-level description of
the current implementation. Using the ProM-based extension of RapidMiner
(http://rapidminer.org), i.e. RapidProM [
The remainder of this paper is organized as follows. In Section 2, we present preliminaries. In Section 3, we discuss related work. In Section 4, we explain how to find optimal alignments using A∗. In Section 5, we discuss parametrization of A∗ algorithm. In Section 6, we evaluate the proposed parametrization. Section 7 concludes the paper. 2
In this section we present preliminary concepts needed for a basic understanding of the paper. We assume the reader to be reasonably familiar with concepts such as partial functions, sets, bags, sequences and Petri nets.
For each countable set X we assume the existence of set IX = {1, 2, ..., |X|} and bijective function ι : IX → X, i.e. each set is indexed. We write x ∈ X to denote any arbitrary element in X and we let xi ∈ X denote that specific element x ∈ X for which ι(i) = x with i ∈ IX . We denote the set of all possible multisets over set X as B(X). We denote the set of all possible sequences over set X as X∗. The empty sequence is denoted hi. Concatenation of sequences σ1 and σ2 is denoted as σ1 · σ2. Given tuple x = (x1, x2, ..., xn) of Cartesian product X1×X2×...×Xn, we define πj(x) = xj for all j ∈ {1, 2, ..., n}. We overload notation and extend projection to sequences. Given sequence σ ∈ (X1×X2×...×Xn)∗ owfelehnagvteh πkjw(σit)h =σ =hxjh1(x,x11j,2 x,.2.1.,, x..j.k, xin∈1), X(xj1∗2,, xfo2r2, .a.l.l, xjn2∈), .{..1,,(x2,1.k.,.,xn2}k., ..G.,ixvnenk)ia, sequence σ = hx1, x2, ..., xki ∈ X∗ and a function f : X → Y , we define πf (σ) = hf (x1), f (x2), ..., f (xk)i. Given Y ⊆ X we define ↓Y : X∗ → Y ∗ recursively with ↓Y (hi) = hi and ↓Y (hxi · σ) = hxi· ↓Y (σ) if x ∈ Y and register request a t1 p2 examine thoroughly b t2 examine causally c decide e p5 pay compensation g t7 t3 t4
d check ticket p3 p4 t5 t6 t8 f h re-initiate reject request po
Definition 1 (Petri net). Let P denote a set of places, let T denote a set of transitions and let F ⊆ (P × T ) ∪ (T × P ) denote the flow relation. Let L denote the universe of labels and let λ : T → L denote a labelling function. A labelled Petri net is a quadruple N = (P, T, F, λ). N denotes the universe of Petri nets.
Marking M of Petri net N = (P, T, F, λ) is a multiset of P , i.e. M ∈ B(P ). The initial marking of N is denoted as Mi. An example of a labelled Petri net (with both full/abbreviated transition labels) is depicted in Figure 1. When a transition is enabled, we write (N, M )[ti, e.g. (N1, [pi])[t1i and (N1, [p3, p4])[t5i. If firing a sequence of transitions σ ∈ T ∗, starting in marking M , yields marking M 0, we write (N, M ) −→σ (N, M 0).
Alignments allow us to compare the behaviour recorded in event logs to the behaviour described by a Petri net. Conceptually, an alignment represents a mapping between the activities observed in a trace σ ∈ L and the execution of transitions in the Petri net.
Definition 2 (Alignment). Let σ ∈ A∗. Let N = (P, T, F, λ) be a labelled Petri net and let Mi, Mf ∈ B(P ) denote N 0s initial and final marking. Let ∈/ A ∪ T . A sequence γ ∈ ((A ∪ { }) × (T ∪ { }))∗ is an alignment if: 1. (π1(γ))↓A = σ; activity part (excluding ’s) equals σ.
(π2(γ))↓T 2. (N, Mi) −−−−−−→ (N, Mf ); transition part (excluding language.
’s) in Petri net γ1 : a b d e h t1 t2 t4 t5 t8 γ2 : a b d e t1 t2 t4 3. ∀(a, t) ∈ γ(a 6= ∨t 6= ); ( ,
) is not valid in an alignment.
We let Γ (N, σ, Mi, Mf ) denote the universe of alignments of Petri net N and trace σ given markings Mi and Mf .
Given an alignment, an individual element of a sequence is referred to as a move. If a move is of the form (a, ) we refer to it as a log move, which indicates that we are not able to map an observed activity to the execution of a transition. A move of the from (t, ) represents a model move and indicates that, according to the model, an activity was required to be executed, yet it didn’t occur. Finally, a move of the form (a, t) represents a synchronous move, given a = λ(t). Consider example trace ha, b, d, e, hi and consider Petri net N1 in Figure 1. Observe that the three sequences γ1, γ2 and γ3, presented in Figure 2, are all alignments. All three alignments are in Γ (N1, ha, b, d, e, hi, [pi], [po]). Observe that γ1 minimizes any moves of the form ( , t) and (a, ), hence, we prefer γ1 over γ2 and γ3. To be able to rank and compare alignments we define a cost-function over moves. The cost of the alignment itself is the sum of the costs of its moves. Definition 3 (Alignment Cost). Let σ ∈ A∗, let N = (P, T, F, λ) be a labelled Petri net with Mi, Mf ∈ B(P ), let ∈/ A ∪ T and let cm : (A ∪ { }) × (T ∪ { }) → R>0. Given alignment γ ∈ Γ (N, σ, Mi, Mf ), the costs κcm of γ, given move cost function cm, is defined as κcm (γ) = P|iγ=|1 cm(γ(i)).
In general one can opt to use an arbitrary instantiation of cm, however, in the remainder of the paper we adopt the unit-cost function: 1. cm(a, t) = ⇔ a ∈ A, t ∈ T and λ(t) = a 2. cm(a, t) = ∞ ⇔ a ∈ A, t ∈ T and λ(t) 6= a 3. cm(a, t) = 1 otherwise The unit function only assigns finite values to model-, log- and synchronous moves. Moves (a, t) of the form a 6= ∧t 6= ∧λ(t) 6= a have value ∞. As we assume unit-costs, we omit cm as superscript and simply refer to κ(γ). We write γopt to refer to the optimal alignment, i.e. γopt = arg minγ∈Γ (N,σ,Mi,Mf )κ(γ). 3
We primarily focus on work in conformance checking, for an overview of process
mining we refer to [
Early work in conformance checking uses token-based replay [
Alignments are introduced in [
In [
Recently approximation schemes for alignments, i.e. computation of
nearoptimal alignments, have been proposed in [
Given a Petri net N with initial marking Mi and final marking Mf , and a
trace σ we aim at finding γopt = arg minγ∈Γ (N,σ,Mi,Mf )κ(γ). Computing the
optimal alignment is equivalent to solving a shortest path problem based on the
synchronous product net of N and σ. A formal definition of such synchronous
product net and an equivalence proof of the two problems is outside the scope
of this paper. Hence, we refer to [
Consider Figure 3 which depicts the synchronous product net of Petri net
N1 and trace ha, b, d, e, gi. The trace is transformed into a sequential Petri net
fragment, depicted in the upper part of Figure 3 (coloured dark grey). Each
dark grey transition represents a log move, as reflected by their corresponding
label. The lower part of Figure 3 (coloured white) is based on the original model.
Each white transition represents a model move. Finally, the middle transitions
(coloured light grey) represent synchronous moves and connect each trace-based
transition to each equal-labelled transition in the model part. A firing sequence
of the synchronous product net from [pi, p0i] to [po, p0o] corresponds to a sequence
of moves, which in fact is an alignment [
Each transition in the synchronous product net corresponds to a move in an alignment, and moreover, to an arc in the state space of the synchronous product. Since each move has an associated cost, we are able to assign the weight of each arc in the state space with the cost of the associated move. The goal of finding an optimal alignment is thus equivalent to solving a shortest path problem on the state space of the synchronous product net, using [pi, p0i] as an initial state and [po, p0o] as a final state. In the remainder of this paper we assume the existence of a synchronous product oracle ⊗ : N × A∗ → N that, given a Petri net and a trace, computes a synchronous product. We write N ⊗ σ instead of ⊗(N, σ). Furthermore we define N S = {N S | ∃N ∈ N , σ ∈ A∗(N S = N ⊗ σ)}. Since the synchronous product inherits the initial marking of the given Petri net and just adds one marked place, i.e. p0i in Figure 3, we use p0i to refer to that place. Similarly, we refer to p0 .
o
Many algorithms exist that solve a shortest path algorithm on a weighted
graph with a unique start vertex and a set of end vertices. In this paper we
predominantly focus on the A∗ algorithm [
In Algorithm 1 we present an algorithmic skeleton for optimal alignment computation using A∗. The algorithm expects a Petri net N with associated initial and final marking Mi, Mf , and a trace σ as an input. Moreover it expects a heuristic function h. The algorithm first creates the synchronous product net N S . Subsequently it constructs the initial and final marking of the synchronous product net and initializes a set C which contains markings already visited in the search. We use a priority queue Q which stores triples of the form (M, g, h) ∈ B(P S ) × R≥0 × R>0. In such triple, M represents in the synchronous product net, g represents the best known cost so far of reaching marking M from MiS and h represents the estimated distance to MfS from M , i.e. the heuristic for Algorithm 1: A∗ (Alignments) input : N = (P, T, F, λ), Mi, Mf ∈ B(P ), σ ∈ A∗, h : N S × B(P) × B(P) → R>0 output: γopt ∈ Γ (N, σ, Mi, Mf ) begin
NS = (P S, T S, F S, λS) = N ⊗ σ; MMifSS ←← MMif ]][[pp0i0o]];; C ← ∅; initialize priority queue Q ⊆ B(P S) × R≥0 × R>0 sorted ascending by the sum of the two last tuple arguments; Q.enqueue(MiS, 0, h(NS, MiS, MfS)); while |Q| > 0 do (M, g, h) ← Q.dequeue(); C ← C ∪ (M, g, h); if M = MfS then
return reconstructed alignment by traversing from MfS back to MiS; foreach t ∈ {t0 ∈ T S | M[t0i} do
M0 ← (M \ •t) ] t•; if @(M0, g0, h0) ∈ C then g0 ← g + cm(λS(t)); if ∃(M00, g00, h00) ∈ Q(M0 = M00 ∧ g0 < g00) then replace (M00, g00, h00) by (M0, g0, h00) in Q; parent(M0) ← (M, t); else if @(M00, g00, h00) ∈ Q(M0 = M00) then
Q.enqueue(M0, g0, h(NS, M0, MfS)); parent(M0) ← (M, t); return failure; M . Sorting of Q is based on the sum of the last two tuple arguments, i.e. for some tuple (M, g, h) this is g + h. While the queue is not empty we remove its head and add it to collection C (line 7). If the head represents the final marking we return the corresponding alignment by reconstructing it using the parent pointers, set in line 18 and line 21. If not, we fire each enabled transition in the given marking and investigate the new marking (foreach in line 12). If there is already a tuple in C containing the new marking we do nothing (line 14). If not, we check whether Q already contains a tuple with the new marking. If so, we replace that entry if we now reach the marking with a lower path cost, i.e. g0 < g00 (line 16). If no tuple containing the newly obtained marking exists in Q, we simply insert it together with its associated path costs and heuristic value (line 19). In case of adding or replacing an entry in Q we update a pointer parent from the newly reached marking M 0 to tuple (M, t), stating that we are able to reach M 0 cheaper by firing t in M .
If we use an underestimating heuristic function, Algorithm 1 is guaranteed to find an optimal path from MiS to MfS . Hence, line 22 is never reached. If we reach a marking that is already present in C, we ignore this completely. Note that this is only feasible, if we are guaranteed that once we add a triple (M, g, h) to C we are never able to reach that state using distance g0 < g. This, in turn, is guaranteed if the following consistency property holds: d(M, M 0) + h(N, M 0, Mf ) ≥ h(N, M, Mf ), where d(M, M 0) represents the length of the shortest path in the state space of N from M to M 0.
We are able to parametrize and/or change several characteristics of the algorithmic skeleton, e.g. the second order sort criterion of Q and the heuristic function. In the upcoming section we discuss each of these changes in detail. 5
In this section we present parametrization and/or changes applicable to Algorithm 1. All changes presented here are in line with the implementation in ProM. Heuristic Function Observe that a trivial, naive, admissible and consistent heuristic for any marking in the synchronous product net is simply making all remaining activities corresponding to that marking synchronous, given that there exists at least one transition t with a corresponding label. For example, consider marking [p1, p2, p01] in the synchronous product net in Figure 3. Regardless of how we ended up in the marking, the remaining activity labels are the sequence hb, d, e, gi. Since for each label in that sequence there exists at least one synchronous transition with a similar label, a naive underestimate of the remaining costs is 4 . Note that this estimator completely ignores whether or not these equally labelled transitions are actually able to fire, at some point in the future, given the current marking. Moreover, the heuristic completely ignores the model part of the alignment (white transitions), i.e. several markings have an equal heuristic.
Alternatively, we exploit the state equation of Petri nets as a basis for a heuristic. Let A denote the incidence matrix of a Petri net N = (P, T, F, λ) (A is an |T | × |P | matrix with A(i, j) = 1 implies pj ∈ ti•, etc.). Furthermore, let x denote at |T |-sized column vector of integers. Let Mi and Mf denote σ two markings and let σ ∈ T ∗ s.t. (N, Mi) −→ (N, Mf ). Furthermore let mi and mf denote two |P | sized column vectors representing Mi and Mf , with mi(i) = Mi(pi) and mf (i) = Mf (pi) ∀i ∈ {1, 2, ..., |P |}. The state equation states that when we instantiate x as the Parikh vector of σ, i.e. if transition ti occurs k times in σ, x(i) = k, then x is a solution to mf = mi + A|x. The opposite however does not hold, i.e. if we find a solution to mf = mi + A|x, x is not necessarily a Parikh representation of a σ0 ∈ T ∗ s.t. (N, Mi) −σ→0 (N, Mf ).
Nonetheless we are able to utilize the state equation for the purpose of
calculating a heuristic. Given any marking M (with vector form m) within the
synchronous product net, we try to find a minimal solution to mf = m + A|x,
where A and x are defined in terms of the synchronous product net. Let c
denote a |T |-sized vector where each index i has value cm(λ(ti)) for each transition
ti in the synchronous product net. Vector x that minimizes c|x is a minimal
solution to mf = m + A|x. Observe that, by contradiction, the value c|x is
always a lower bound for the actual cost to reach Mf from M . Such solution is
easily found by, for example, using Integer Linear Programming (ILP) [
The ILP-based heuristic is expected to be closer to the actual costs of the shortest path in the synchronous product net’s state space, compared to the trivial heuristic. Hence we expect, when using the ILP-based heuristic, that the A∗ algorithm visits less states during execution and moreover on average stores less states in the queue. A trade-off is obviously the increase in computation time of the heuristic. Note that we are able to relax the computation time by relaxing the Integer Linear Program to a Linear Program, i.e. x ∈ R|≥T0|. This as a consequence leads to more severe underestimation of the true costs.
When using Integer Linear Programming to find a minimal solution to mf = m + A|x, we are able to estimate, and in some cases derive exactly, the heuristic of future states. Assume that we find a minimal-cost solution x to mf = m + A|x based on some marking M in the state space of the synchronous product net. Take any t ∈ T S with M [ti. We know that for marking M 0 = (M \ •t) ] t•, we have mf = m0 + A|(x − 1t), i.e. mf = m0 + A|x0 has a solution with x0 = x − 1t. Now assume that there exists some vector y that is a strictly t smaller solution to mf = m0 + A|x0 than x − 1t. Since we know that M →− M 0, we know that y + 1t is a solution to mf = m + A|x with a strictly lower cost than x. This however contradicts minimality of x, hence c(x − 1t) is a lower bound for h(N S , M 0, Mf ), i.e. c(x − 1t) ≤ h(N S , M 0, Mf ). In the more specific case that we fire ti in M with x(ti) > 0, we deduce, by similar rationale, that c(x − 1t) = h(N S , M 0, Mf ). Thus, based on solving one ILP for a marking M , we in some cases already know the heuristic for the next state M 0, and in some cases we know a lower bound. Therefore, if we know the exact heuristic we do not need to solve new ILP’s and simply add/update the heuristic of M 0 to c(x − 1t). If it is a lower-bound, we also add/update the heuristic of M 0 to c(x − 1t), and mark a boolean flag related to M 0 stating that we have a lower bound. In case the tuple related to marking M 0 gets on top of the queue we actually solve the underlying ILP to get the exact heuristic. This potentially moves the tuple further down the queue. Hence, we postpone and potentially reduce heuristic computation, yet we increase the number of polling operations to the queue. Second-Order Queueing Criterion Within the algorithmic skeleton we use queue Q that uses the sum of the g and h values as a sorting criterion, i.e. in terms of A∗ this is referred to as the f -value. Multiple markings of the synchronous product net exist that have the same f -value. By default the ordering of markings with an equal f -value is random. Alternatively, we pose two second-order sorting criteria. If we use the h-values as a second-order criterion, we effectively traverse the states with an equal f -value in a depth-first manner, i.e. we explore states that seem to have a better solution first. Alternatively, if we use the g-values as a second-order criterion, we traverse states with an equal f -value in a breadth-first manner, i.e. we explore states that have a minimal actual distance g to the start state first.
Restricting Transition Firing Reconsider the synchronous product net shown in Figure 3 with marking [pi, p0i]. Observe that there are three firing sequences in the net to achieve marking [p1, p2, p01], i.e. ht1,10 i, ht01, t1i and ht1, t01i. The cost associated with ht1,10 i is whereas the cost for ht01, t1i and ht1, t01i is 2. We observe that both possible permutations of the sequence containing t1 and t01 have the same cost and can both be part of a (sub-optimal) alignment. In the general sense, assume we have some alignment γ = γ1 · γ2 · γ3 ∈ Γ (N, σ, Mi, Mf ) s.t. γ2 only consists of log and model moves. In sequence γ2, if we swap any adjacent log and model move, yielding γ20, then also γ0 = γ1 · γ20 · γ3 ∈ Γ (N, σ, Mi, Mf ) and, trivially, κ(γ) = κ(γ0).
Hence, to find the optimal alignment we need to traverse one specific permutation of the path to the optimum, rather than all possible permutations. The A∗ algorithm already limits the number of visited states and also choosing an appropriate second-order criterion helps in preventing this. In its basic form, every enabled transition in a certain state is added to Q. However, we are able to limit this number of states by exploiting the previously mentioned property. We are able to manipulate the foreach-loop of Algorithm 1 (line 12) in two ways: – If the transition leading to the current marking relates to a model move we only consider those transitions t that relate to a model or synchronous move. – If the transition leading to the current marking relates to a log move we only consider those transitions t that relate to a log or synchronous move. Observe that the pointers stored for each marking allow us to make such decision. In the first option we are not able to schedule a log move after a model move. The other way around is however possible, i.e. we are allowed to schedule a model move after a log move. The second option behaves exactly opposite, i.e. we are not allowed to schedule a model move after a log move. 6
In order to observe the effect of the parameters presented in Section 5 in terms
of performance, i.e. computation time and queue size needed, we designed an
exploratory experiment. The experiment is designed as a scientific process
mining workflow [
To analyse the effect of different values of the parameters presented in Section 5,
we use a scientific workflow that, conceptually, performs the following steps.
1. We generate 11 (block-structured) Petri nets with k labelled transitions,
where k is drawn from a triangular distribution with parameters {10, 30, 50},
for increasing levels of Parallelism (from 0 to 50% in steps of 5%) [
In this section we present the results of the experiments performed. We first assess computation time performance, after which we focus on memory usage in terms of queue-size. Due to space limitation we only show results per category, i.e. we do not focus on parameter interaction. Moreover, we only present results in which (seemingly) significant differences are observed, and, parallelism levels up to 35%. For the optimizations based on the state equation, i.e. using linear programming and/or lower-bound estimation we did not encounter notable differences in terms of computation time and memory usage. The same holds for the parameters based on the use of transition restriction.
Computation Time In Figure 4 we depict the average optimal alignment computation time in milliseconds, when using either the naive heuristic, or the ILP-based heuristics, without relaxation and/or lower-bound estimation. Each plot in the figure represents a different level of parallelism within the generated process models. We show parallelism from 0% to 35%. On the x-axis we plot 0.05 0.1 0.15 0 0.1 0.2 0.3 0.4 0.5 Heuristic
Naive 0.35 ILP 0 0.1 0.2 0.3 0.4 0.5 % Noise the percentage of noise added to the generated event logs. On the y-axis we plot average computation time. We observe that for parallelism levels 0%, 5%, 10% and 15%, computation time of ILP is relatively stable and significantly larger than the naive estimator. The computation time for the naive estimator starts increasing when more noise is introduced for models with at least 15% parallelism. For ILP we observe similar behaviour starting from parallelism levels of 20% and higher. Interestingly, for 15% of parallelism the rate of growth of the naive version is clearly higher than the rate of growth of ILP. In all other cases, i.e. for parallelism levels of 20% and up, ILP’s growth rate seems higher than the naive variant.
In Figure 5 we depict the average optimal alignment computation time for each type of second order queueing criterion. For parallelism levels greater (or equal to) 25% we observe a significant difference in computation time between DFS and BFS/Random. We observe that the difference also increases with the increase of noise within the event logs. BFS and Random are comparable in computation time. The results of this experiment show that a preference for states within the queue based on the estimated remaining distances is beneficial for reaching a target state faster.
Memory Usage Here we focus on memory usage in terms of average queued states. In Figure 6 we depict the average amount of queued states, when using either the naive heuristic, or the ILP-based heuristics, without relaxation and/or lower-bound estimation. As expected the state equation based heuristic, i.e. using ILP, traverses the state space more efficiently leading to significantly less states queued. Whereas the naive heuristic rises in terms of queued states both with increases of parallelism and noise, the ILP-based heuristic seems unaffected by 10.0 7.5 5.0 0.05 0.1 0.15 2nd Order Sorting Crit.
BFS DFS Random 0 0.1 0.2 0.3 0.4 0.5 0 0.1 0.2 0.3 0.4 0.5 0 0.1 0.2 0.3 0.4 0.5 0 0.1 0.2 0.3 0.4 0.5
% Noise the amount of noise introduced. The number of queued states slightly increases when the level of parallelism is increased, however, it is orders of magnitude smaller than the increase of the naive heuristic. Based on these results, together with the computation time results, there seems to be a clear trade-off between using ILP or a naive heuristic function in terms of computation time versus memory usage.
In Figure 7 we depict the average queue size for each type of second order queueing criterion. We observe that, like in the case of computation time, the 0 0.05 0.1 0.15 0 0.1 0.2 0.3 0.4 0.5 Heuristic
Naive 0.35 ILP 0.05 0.1 0.15 2nd Order Sorting Crit.
BFS DFS Random 0 0.1 0.2 0.3 0.4 0.5 0 0.1 0.2 0.3 0.4 0.5 0 0.1 0.2 0.3 0.4 0.5 0 0.1 0.2 0.3 0.4 0.5
% Noise DFS variant outperforms the other two. The difference is however less prominent. 7
In this paper we have presented multiple ways to parametrize the A∗ search algorithm used in optimal alignment computation. Some parametrization concerns 2nd-order sorting criteria within an internal priority queue used, whereas other parametrization utilizes Petri net theory. The parametrization discussed is in line with, and limited to, the current implementation of optimal alignment computation in the process mining tool-kit ProM. As such, this paper acts as a high-level description of the current implementation. We have performed an exploratory evaluation of the effects of different parameter combinations w.r.t. the number of states queued and the computation time of finding optimal alignments. Our results show that, for the class of models considered, using a naive heuristic outperforms the more advanced state-equation based heuristic in terms of computation time. Moreover using the heuristic value as a second-order sorting criterion for the internal priority queue is beneficial for memory usage and computation time.
Future Work The results of this exploratory study show that parametrization of the heuristic search has an impact on its performance. We plan to extend the current evaluation using a larger variety of Petri nets and a larger number of iterations per model-log combination.
Several approximation schemes exist for A∗, e.g. using a scaling function within the heuristic. We plan to assess the impact of these approximation schemes on alignment computation as well. We additionally plan to examine the use of alternative informed search methods such as Iterative Deepening A∗ (IDA∗).