# maximisation_of_admissible_multiobjective_heuristics__9b4133ae.pdf Journal of Artificial Intelligence Research 78 (2023) 619-639 Submitted 04/2023; published 11/2023 Research Note Maximisation of Admissible Multi-Objective Heuristics Patrik Haslum PATRIK.HASLUM@ANU.EDU.AU Ryan Xiao Wang RYAN.WANG@ANU.EDU.AU The Australian National University, Canberra, Australia In multi-objective (MO) heuristic search, solution costs, as well as heuristic values, are sets of multi-dimensional cost vectors, representing possible non-dominated trade-offs between objectives. The maximum of two or more such vector sets, which is an important operation in creating informative admissible MO heuristics, can be defined in several ways: Geißer et al. recently proposed two MO maximum operators, the component-wise maximum (comax) and the anti-dominance maximum (admax), which represent different trade-offs between informativeness and computational cost. We show that the anti-dominance maximum is not admissibility-preserving, and propose an alternative, the select one maximum (somax). We also show that the comax operator is the greatest admissibility-preserving MO maximum, and briefly investigate its efficient implementation. The conclusion of our experimental results is that somax achieves a trade-off similar to that intended with admax cheaper to compute but less informed also when compared to an improved comax implementation. 1. Introduction A multi-objective (MO) optimisation problem has some number k of objective functions, without an a priori specified trade-off between them. The cost of a solution is not a single value but a vector of values, one for each objective, and solutions that achieve better values on different objectives for example, a schedule that is slower but cheaper vs. one that is faster but more expensive are incomparable. Therefore, the optimal solution to such a problem is a set of solutions representing all non-dominated solution cost vectors, known as the Pareto cover set (PCS) (Roijers, Vamplew, Whiteson, & Dazeley, 2013). The multi-objective version of deterministic, discrete sequential decision problems, such as classical planning, can be solved by MO heuristic search algorithms, such as NAMOA (Mandow & P erez-de-la-Cruz, 2010), which make use of multi-objective admissible heuristics. In the multi-objective setting, the heuristic value of a state is also a set of (k-dimensional) cost vectors, like the solution set it lowerbounds. Recently, Geißer, Haslum, Thi ebaux, and Trevizan (2022) proposed MO generalisations of several families of admissible classical planning heuristics. In single-objective heuristic search, taking the maximum of heuristic values is an important operation: the maximum of two admissible heuristics is also admissible, and at least as informed as either of the two heuristics. Maximisation plays a key role in effective combination of abstraction heuristics (e.g., Holte, Felner, Newton, Meshulam, & Furcy, 2006; Haslum, Helmert, Bonet, Botea, & Koenig, 2007; Seipp, Keller, & Helmert, 2020), and in the definition of planning heuristics such as hmax and hm (often known as critical path heuristics). In the multi-objective setting, however, it is not obvious how to define the maximum of two heuristic values, as these are sets of cost vectors that are only partially ordered by the dominance relation. Geißer et al. (2022) proposed two different MO maximum operators, the component-wise maximum (comax) and the anti-dominance 2023 The Authors. Published by AI Access Foundation under Creative Commons Attribution License CC BY 4.0. HASLUM & WANG maximum (admax), representing different trade-offs between complexity of computing the MO maximum and its informativeness. Empirically, heuristics using comax performed better on the majority of domains and problems in their benchmark suite. In this paper, we show that the admax operator proposed by Geißer et al. (2022) is in fact not admissibility-preserving. We examine the reason for this flaw, and arrive at a new MO maximum operator, the select one maximum (somax), which preserves admissibility. Although somax lacks most other theoretical guarantees, canonical MO PDB heuristics using it have lower total runtime compared to their counterparts using comax on a majority of the suite of benchmark MO planning problems used in Geißer et al. s (2022) evaluation. We also investigate the comax operator further, showing it is in fact the strongest possible MO maximum. The potential disadvantage of comax, which motivates the continued search for alternative MO maximum operators, is its computational cost. We show that comax can be computed efficiently (in linear time) in the special bi-objective case, and investigate some improvements to its computation in the general case. Still, in the final experimental comparison, neither of heuristics using the improved comax implementation nor somax consistently outperform the other. 2. Background We adopt the following statement of the multi-objective planning problem from Geißer et al. (2022): A multi-objective planning (MOP) task is a STRIPS planning task with k cost functions, c1, . . . , ck. Each action a is associated with a k-dimensional cost vector, c(a) Nk, where the ith component, denoted c(a)i, is a s contribution to ci. The cost of a plan π = a1, . . . , an is also a vector, c(π) = Pn i=1 c(ai), where the sum is taken with vector addition. We apply c also to sets of plans: if Π is a set of plans, then c(Π) = { c(π) | π Π} is the set of cost vectors of plans in Π. Given two cost vectors v1, v2, v1 Pareto dominates v2, denoted v1 v2, iff for all i = 1 . . . k : vi 1 vi 2 and v1 = v2. Dominance is a strict partial order, i.e., it is transitive and asymmetric. Given a set of cost vectors, V , ND(V ) denotes the set of vectors in V that are not dominated by any other in V , i.e., ND(V ) = { v V | v V v v}. We say v1 dominates or equals v2, denoted v1 v2, iff v1 v2 or v1 = v2. A plan π1 dominates (resp. dominates or equals) plan π2 if c(π1) c(π2) (resp. c(π1) c(π2)). With slight abuse of notation, we use ND( ) to denote the subset of non-dominated plans in a set of plans as well. A MOP task can have multiple solution plans whose cost vectors are mutually non-dominating, and not equal, representing different possible trade-offs between the k objectives. The solution to a MOP task is defined as computing a set of plans including one representative of each such nondominated cost vector; this known as a Pareto coverage set. If T is a MOP task and Π(T ) the set of all plans for T , a Pareto coverage set, PCS(T ), is a set of plans such that: (i) PCS(T ) ND(Π(T )); and (ii) π Π(T ) π PCS(T ) c(π) c(π ). An alternative solution concept is to compute the Pareto front, PF(T ) = ND(Π(T )), i.e., the set of all non-dominated plans. We will use PCS(s) and PF(s), where s is any state in T , to denote the Pareto coverage set and Pareto front, respectively, starting from the given state s instead of the initial state of T . The Pareto coverage set of a task (or state) does not have to be unique, since there may be different plans for each non-dominated cost vector. However, c(PCS(T )) is unique, i.e., whatever representatives are chosen they collectively have the same set of cost vectors. In the special case that k = 1, computing the PCS reduces to finding a plan with minimum cost, i.e., classical optimal planning. MAXIMISATION OF ADMISSIBLE MO HEURISTICS 3. MO Heuristics A multi-objective heuristic function maps states of the planning problem to sets of k-dimensional cost vectors. Like a heuristic in the classical, single-objective case, it represents an estimate of the cost of solution plans from the state, but since there can exist several plans, with distinct nondominated cost vectors, the heuristic estimate is also a set. To compare such cost vector sets, we extend the notion of dominance: Definition 1. Let V and U be sets of k-dimensional cost vectors. V U iff u ND(U) v V v u. V U iff V U and u ND(U) v V v u. This definition of domainance between cost vector sets mirrors the defintion of dominance between cost vectors: V U iff for every cost vector in U there is one in V that is at least as good ( v u), and V U iff in addition there is at least one essential cost vector in U (not dominated by another vector in U) such that there is a strictly better cost vector in V ( v u). In Section 3.2 below, we show that dominance is indeed a partial order over a suitably defined set of cost vector sets. Definition 2. A MO heuristic H is admissible iff H(s) c(PCS(s)) for all states s. The definition of admissibility given by Mandow and P erez-de-la-Cruz (2010), and also used by Geißer et al. (2022), is slightly different: s π PF(s) v H(s) v c(π), but equivalent since c(PF(s)) = c(PCS(s)). Admissibility of an MO heuristic requires the weak dominance relation ( ) between the heuristic set and the true cost set, while strict dominance between admissible heuristic sets implies that the dominated set is, in a sense, more informed. This mirrors the case in classcial single-objective heuristics, where admissibility requires h(s) h (s) and h(s) < h (s) implies that h is a stronger heuristic than h when both are admissible. Because dominance is transitive (cf. Section 3.2), H(s) c(PCS(s)) implies ND(H(s)) c(PCS(s)). That is, we can remove from the heuristic set for any state any dominated cost vectors without compromising admissibility. Conversely, because admissibility is defined as the existence of some cost vector v H(s) that dominates or equals each solution cost vector, an admissible heuristic set also remains admissible when enlarged by any set of cost vectors, i.e., if H(s) c(PCS(s)) then H(s) V c(PCS(s)) for any set V ; this holds even if V contains cost vectors that do not dominate or equal any solution cost in c(PCS(s)). 3.1 Size of the Heuristic Set In general, there is no relationship between the size of the Pareto cover set and that of an admissible heuristic set. A small (PCS) set can be dominated-or-equalled by a much larger (heuristic) set. For k 3, a set of integer cost k-vectors V such that V { v}, for a given k-vector v > 0, and such that V contains no cost vector dominated by another in V , i.e., V = ND(V ), can be arbitrarily large, though finite. Conversely, any cost vector set V is dominated-or-equalled by its so-called ideal point, min v V v1, . . . , min v V vk , and therefore by a singleton set. There are some trivial limits: m(2n), where m and n are the number of actions and propositions, respectively, in the problem, bounds the number of possible non-redundant plans, and therefore the size of the PCS. This applies also to abstraction heuristics, where the bound is determined by the HASLUM & WANG number of abstract actions and states, respectively. Geißer et al. (2022) gave a similar bound on the size of the heuristic set for MOIP operator counting heuristics. 3.2 Vector Set Dominance In this section, we show that dominance between cost vector sets has the properties of a partial order. Lemma 3. Both weak and strict vector set dominance are transitive. Proof. Follows from transitivity of the vector dominance relations. Suppose V U W, and w W: there must exist u U such that u w, and v V such that v u; this implies v w. Suppose V U W. Because strict dominance implies weak dominance and from the above, we have V W. There exists a w ND(W) such that u w for some u U. We also have v u for some v V , and therefore v w. Hence V W. The proof that V U W implies V W is essentially the same. Note that V U is not equivalent to (V U) (V = U): we can have V U and U V with V = U, if V and U contain different dominated cost vectors. However, their subsets of non-dominated cost vectors must be the same: Lemma 4. If V U and U V then ND(V ) = ND(U). Proof. Let v ND(V ). U V implies u U such that u v; V U then implies v V such that v u v. This means either v = u = v or v v, but the latter contradicts that v ND(V ). Thus v U, and ND(V ) U. The proof that ND(U) V is symmetric. Suppose there is some v ND(V ) such that v ND(U). Since ND(V ) U, this means v is in U but is dominated by another cost vector u ND(U). However, since we also have ND(U) V , u V , so v is dominated also in V , contradicting that v ND(V ). Thus ND(V ) ND(U) and, symmetrically, ND(U) ND(V ), leading to ND(V ) = ND(U). Corollary 5. Let Pk = 2Nk, i.e., the power set of the set of k-dimensional cost vectors, and PND k = {V Pk | ND(V ) = V }, i.e., PND k is the subset of vector sets that do not contain any cost vector dominated by another cost vector in the same set. Then weak set dominance is a partial order over PND k . In Section 4.1.1 we will show that comax is the least upper bound operator in this partially ordered set. We end this section by showing that strict vector set dominance is asymmetric, and therefore a strict partial order: Lemma 6. V U implies U V . Proof. Since V U there exists u ND(U) such that there exists v V such that v u. Suppose U V : then there must exist u U such that u v. By transitivity of cost vector dominance, u v u implies u u, contradicting that u ND(U). Hence U V . MAXIMISATION OF ADMISSIBLE MO HEURISTICS Finally, we briefly describe two properties of the NAMOA MO heuristic search algorithm, and their implications for the effectiveness of MO heuristics. NAMOA processes an queue of open , as-yet non-dominated, paths in the search space; each path is represented by a tuple (s, gs, Fs), where s is the state at the end of the path, gs the path cost, and Fs = { gs + h | h H(s)} a set of estimated cost vectors for the completion of this path to a goal state. Paths are taken from the queue, following a priority rule, expanded by appending possible successor transitions, and moved to a closed list. This is analogous to classical single-objective A . If the cost gs of a new path found to state s is dominated by the cost of a path to s that has already been expanded (i.e., that is in the closed list), then successors of the new path do not need to be explored, and it is not added to the open queue. Mandow and P erez-de-la-Cruz (2010) showed that the NAMOA algorithm, like classical single-objective A , has the property that if the MO heuristic is consistent, then the algorithm will not find a dominated path before the path that dominates it, and therefore no path once closed will be reopened. Consistency of an MO heuristic was defined by Stewart and White (1991), as follows: H is consistent iff for all states s, t and every non-dominated s t-path P, v H(t) u H(s) ( u c(P) + v) holds. They also showed that consistency holds iff it holds for all paths of length 1, i.e., state transitions. A path (s, gs, Fs) to a non-goal state s is pruned from the open queue when a set of plans Π has been found such that for each fs Fs there exists a plan π Π such that c(π) fs. (This pruning is applied when the path is generated as well as to paths in the queue when a new non-dominated plan is found.) It follows that if H(s) H (s), using heuristic H in place of H can not result in a path through s being pruned earlier (assuming paths are explored in the same order), or, in other words, a heuristic set that is a strict superset can not be more informed. That is not the same as saying a smaller heuristic set is to be preferred; indeed, as shown by Geißer et al. (2022) the so-called ideal point heuristic, which consists of a single cost vector of independent admissible estimates for each objective, is often outperformed by MO heuristics that estimate the Pareto coverage set more accurately with a set of cost vectors. But simply adding more cost vectors to an already admissible heuristic set cannot improve it. 4. MO Maximum Operators 4.1 Component-Wise Maximum (comax) Let v and u be cost vectors of equal dimension. We define max( v, u) = max( v1, u1), max( v2, u2), . . . , max( vk, uk) . The component-wise maximum is defined by Geißer et al. (2022) as follows: Definition 7. Let V1 and V2 be sets of cost vectors of dimension k. The component-wise maximum of V1 and V2 is comax(V1, V2) = ND({max( v1, v2) | v1 V1, v2 V2}). The following proposition summarises properties of comax that were stated by Geißer et al. (2022): Proposition 8. Let H1 and H2 be MO heuristics. (i) If H1 and H2 are admissible, so is H(s) = comax(H1(s), H2(s)). (ii) If H1 and H2 are consistent, so is H(s) = comax(H1(s), H2(s)). (iii) comax is commutatitve and associative. (iv) V1 comax(V1, V2) and V2 comax(V1, V2). HASLUM & WANG Proof. Proofs of (i) and (ii) were given by Geißer et al. (2022). Note that (i) also follows from Proposition 9 below, since admissibility implies c(PCS(s)) is an upper bound on H1(s) and H2(s). (iii) Follows from commutativity and associativity of max. (iv) Consider u comax(V1, V2): u is the result of combining, by coordinate-wise maximum, vectors v1 V1 and v2 V2. Since ui = max( vi 1, vi 2) we have vi 1 ui and vi 2 ui, for i = 1, . . . , k. Hence v1 u and v2 u. 4.1.1 comax IS THE GREATEST ADMISSIBLE MAXIMUM Recall from Corollary 5 that PND k is the set of all sets of k-dimensional cost vectors that contain no dominated cost vector, and that this set is partially ordered by weak set dominance. Proposition 9. comax is the least upper bound of any pair of elements in PND k . Proof. Note that comax by definition excludes dominated cost vectors; thus, comax(V, U) PND k for any V, U PND k . That comax is an upper bound was shown by Proposition 8(iv). Let W PND k be any upper bound on V and U, i.e., such that V W and U W, and let w W. Since V W and U W there exists v V and u U such that v w and u w. Consider the ith objective: Since v w and u w, we have vi wi and ui wi, and therefore max( vi, ui) wi. Since this holds for all k objectives, max( v, u) w. Either max( v, u) comax(V, U) or there is another x comax(V, U) such that x max( v, u); in either case, there is a cost vector in comax(V, U) that dominates or equals w. Hence comax(V, U) W. If H1 and H2 are admissible MO heuristics, then for any state s H1(s) c(PCS(s)) and H2(s) c(PCS(s)), i.e., c(PCS(s)) is an upper bound on H1(s) and H2(s). Given only this information, it is possible that c(PCS(s)) is also equal to the least upper bound on H1(s) and H2(s), i.e., equal to comax(H1(s), H2(s)). Therefore, no MO maximum operator that is strictly greater than comax can be guaranteed to preserve admissibility. Corollary 10. Let H1 and H2 be admissible MO heuristics, and momax : Pk Pk Pk any binary operator on cost vector sets. If comax(H1(s), H2(s)) momax (H1(s), H2(s)), then momax (H1(s), H2(s)) cannot be guaranteed to be admissible. Given the superiority of comax, why search for alternative MO maximum operators? The potential disadvantage of comax is its computational cost: | comax(V1, V2)| can be as large as the product of |V1| and |V2|. A simple example in k = 4 dimensions is V1 = { i, n i, 0, 0 | i = 1, . . . , n 1} and V2 = { 0, 0, i, n i | i = 1, . . . , n 1}. All cost vectors are mutually non-dominating in both sets, and the maximum contains all n2 cost vectors of the form i, n i, j, n j , with 1 i, j < n, none of which dominate each other. For the special bi-objective case, we can show the following: Proposition 11. If k = 2, then | comax(V1, V2)| |V1| + |V2|. The proof of this proposition is in Appendix A. What is the worst case size bound when k = 3 is an open question. 4.1.2 COMPUTING comax EFFICIENTLY A naive implementation of comax first constructs the set of all pair-wise vector maximums and then filters out dominated cost vectors. This has a complexity of O((|V1||V2|)2), regardless of the size MAXIMISATION OF ADMISSIBLE MO HEURISTICS of the resulting set. An implementation that constructs comax(V1, V2) incrementally, adding only cost vectors not dominated by any already in the set, and removing any dominated by each newly added cost vector, will be more efficient on average if the non-dominated set is small, in particular if non-dominated cost vectors are added early, but has the same complexity in the worst case. Ren, Zhan, Rathinam, Likhachev, and Choset (2022) show that a set of 3-dimensional cost vectors that is generated incrementally can be stored as a balanced binary search tree, such that the complexity of testing whether a cost vector is dominated by or equal to any in the set is logarithmic in the size of the set. This representation could also be used to compute the comax set. However, the complexity of updating the set representation when a new cost vector that dominates some already in the set is added remains linear in the size of the set, so the worst case total complexity of the comax computation does not change. There is also the potential that the additional structure of the comax set can be exploited to compute it more efficiently. In Appendix A we propose a linear-time algorithm for the special bi-objective case (k = 2). Here we make only two observations that hold in the general case. Lemma 12. If v v , then max( v, u) max( v , u); symmetrically, if u u , then max( v, u) max( v, u ); Proof. max( v, u)i equals either vi or ui. If max( v, u)i = vi, then vi ui; since v v , v i vi, and thus max( v , u)i = v i max( v, u)i. If max( v, u)i = ui, then ui vi; since max( v , u)i ui, we also have max( v , u)i max( v, u)i. The symmetric claim follows from same argument, since the maximum is commutative. Corollary 13. comax(V1, V2) = comax(ND(V1), ND(V2)). That is, comax(V1, V2) can be computed from the subsets of non-dominated cost vectors in V1 and V2 respectively. This is significant because the complexity of finding the non-dominated cost vectors in these two sets is O(|V1|2+|V2|2), while the complexity of finding the non-dominated cost vectors in the set of all pair-wise maximums is O((|V1||V2|)2). Unfortunately, the converse of Lemma 12 does not hold: combining cost vectors that are non-dominated in V1 and in V2, respectively, can still yield dominated cost vectors. For a simple example, consider V1 = V2 = { i, n i | i = 0, . . . , n}. As in the earlier example, all cost vectors in this set are mutually non-dominating. From Lemma 14 below, each of these cost vectors is (non-dominated) in comax(V1, V2). However, every combination max( i, n i , j, n j ), where i = j, results in a cost vector max(i, j), n min(i, j) which is strictly dominated by both i, n i and j, n j . Lemma 14. If v1 ND(V1), v2 ND(V2) and v1 v2, then v2 comax(V1, V2). Proof. v1 v2 means that vi 1 vi 2 for all dimensions i; thus max( v1, v2) = v2, which means v2 comax(V1, V2) unless it is dominated by another pair-wise maximum. Suppose there exists w comax(V1, V2), such that w v2. w = max( v, u) for some v V1 and u V2, and hence u w. But u w and w v2 implies u v2, contradicting that v2 ND(V2). As a special case, Lemma 14 implies that any v ND(V1) ND(V2) is in the comax set. 4.2 Anti-Dominance Maximum (admax) The anti-dominance maximum is defined by Geißer et al. (2022) as follows: HASLUM & WANG V1: v V2: ui uj Figure 1: Example of dominance between cost vectors in V1, V2 (both admissible) and PCS. Definition 15. Let V1 and V2 be sets of k-dimensional cost vectors. The anti-dominance maximum of V1 and V2 is admax(V1, V2) = { v1 ND(V1) | v2 ND(V2) : v1 v2} { v2 ND(V2) | v1 ND(V1) : v2 v1}. The intuition behind admax is that if v1 V1 strictly dominates a non-dominated cost vector v2 V2, then including v1 in the union unnecessarily weakens it; admissibility of V2 should ensure that any cost vector u c(PCS(s)) is still dominated by or equal to some vector in V2. The flaw in Definition 15 is that this is done to both sets independently. The following counterexample shows how this can lead to inadmissibility. Example 16. Let V1 = { 1, 2 , 3, 1 }, V2 = { 2, 1 , 1, 3 }. Then admax(V1, V2) = { 3, 1 , 1, 3 }. If c(PCS(s)) = { 2, 2 , 3, 1 , 1, 3 } then V1 and V2 are both admissible heuristic sets for state s, but admax(V1, V2) is not, since no cost vector in it dominates or equals 2, 2 . When we remove a cost vector v V1 from the union of V1 and V2, then given only the knowledge that V1 is an admissible heuristic set, for each cost vector w c(PCS(s)) such that v w, we cannot know if any cost vector other than v in V1 also dominates or equals w. Therefore, to ensure admissibility, we have to keep at least one vector uj V2 such that uj w. Figure 1 illustrates the situation. If v ui, then v w for any w such that ui w, but the reverse does not hold. Thus, we have to keep from V2 also any cost vector u that is incomparable with v. This means if we remove v V1 from the union, we can only remove from V2 any vector u such that u v. But since the reason for removing v is that v ui ND(V2), there can be no u V2 such that u v, since that would imply u ui and hence ui ND(V2). Consequently, any admissible union of subsets of V1 and V2 must include at least one of V1 or V2 in full. This, together with the observation that enlarging an admissible heuristic set, while still admissible, cannot make it a more informed heuristic, motivates the new MO maximum operator, which we define in the next section. 4.3 Select-One Maximum (somax) The idea of the select-one maximum is that if V1 and V2 are both admissible heuristic sets for a state s, then selecting either one of them to be their maximum is also admissible. The reason why we can still expect this maximum of two admissible heuristics to be more informed than using just one of them is that the selection is done per state, and that if one of the two sets is, in some sense, strictly better than the other, we select the better one; only if the two sets are incomparable is the choice arbitrary. MAXIMISATION OF ADMISSIBLE MO HEURISTICS Definition 17. The select-one maximum of V1 and V2 is somax(V1, V2) = V1 (i) if V2 V1 V2 (ii) if V1 V2 Vi (iii) where i {1, 2} chosen by some tie-breaking condition otherwise The choice of vector set dominance as strictly better is natural, but not the only choice. All that is really needed is that the condition is asymetric, so that at most one of cases (i) or (ii) hold. The tie-breaking condition can be arbitrary, including always choosing one of the two arguments. The following proposition shows admissibility. Proposition 18. Let H(s) = somax(H1(s), H2(s)). If H1 and H2 are admissible, then so is H. Proof. (a) Let v c(PCS(s)). By definition, H(s) = Hi(s), for some i {1, 2}. Since H1 and H2 are admissible, there exist u1 H1(s) such that u1 v and u2 H2(s) such that u2 v. At least one of u1 and u2 is in H(s). Hence, H is admissible. Note that Proposition 18 is independent of the tie-breaking condition in Definition 17; in fact, it is independent of cases (i) and (ii) as well. It follows simply because when applied to admissible heuristics, somax selects, for each state, one of two admissible heuristics to use in that state. Compared to comax, somax has very weak theoretical guarantees. In general, we cannot guarantee that Vi somax(V1, V2) for both i = 1, 2, since the non-selected set may be incomparable. If the tie-breaking condition depends only on the content (not index) of the two vector sets, then somax is commutative. Without further assumptions on the tie-breaking order, however, somax is not associative: Let A, B and C be vector sets, and suppose A C but A and C are both incomparable to B. Furthermore, suppose the tie-breaking condition prefers A to B and B to C. Then we have somax(A, B) = A, somax(B, C) = B and somax(A, C) = C, and therefore somax(A, somax(B, C)) = A = C = somax(somax(A, B), C). somax is not guaranteed to preserve MO heuristic consistency. In fact, there is no tie-breaking rule under which such a guarantee can be obtained, as the following counterexample shows. Example 19. We have three states, s1, s2 and t, with transitions from s1 to t and from s2 to t, both with cost 1, 1 . Heuristics H1 and H2 assign values as follows: s1 s2 t H1 { 2, 3 } { 1, 1 } { 1, 2 } H2 { 1, 1 } { 3, 2 } { 2, 1 } somax(H1, H2) { 2, 3 } { 3, 2 } ? Note that both heuristics assign singleton cost vector sets to all three states. H1 is consistent w.r.t. the s1 t transition because 2, 3 1, 1 + 1, 2 and w.r.t. the s2 t transition because 1, 1 1, 1 + 1, 2 . H2 is consistent w.r.t. the s1 t transition because 1, 1 1, 1 + 2, 1 and w.r.t. the s2 t transition because 3, 2 1, 1 + 2, 1 . somax(H1(s1), H2(s1)) = H1(s1) = { 2, 3 }, because there exists a cost vector in H2(s1), namely 1, 1 , which dominates all in H1(s1). Likewise, somax(H1(s2), H2(s2)) = H2(s2) = { 3, 2 }. HASLUM & WANG However, somax(H1(t), H2(t)) can be either H1(t) = { 1, 2 } or H2(t) = { 2, 1 }, since neither vector set dominates the other. Suppose somax(H1(t), H2(t)) = H1(t) = { 1, 2 }. Then the maximum of the two heuristics is inconsistent w.r.t. the s2 t transition, since 3, 2 2, 3 = 1, 1 + 1, 2 . If, on the other hand, somax(H1(t), H2(t)) = H2(t) = { 2, 1 }, then the maximum is inconsistent w.r.t. the s1 t transition, since 2, 3 3, 2 = 1, 1 + 2, 1 . Hence, there is no choice of tie-breaking rule that will ensure somax preserves consistency. 5. Experimental Comparison We compare the use of comax and somax in the canonical MO PDB, the MO Hmax and MO H2 heuristics defined by Geißer et al. (2022) on their collection of 437 benchmark MO planning problems. We use their MO planner implementation, modifying only the MO maximum operators, and like them we use all non-redundant patterns of 2 or 3 variables for the PDB heuristic. Comparing somax and comax. The number of problems solved is summarised in Table 1. Figure 2(a c) shows a comparison of node expansions and runtime between the two operators in each heuristic on pairwise commonly solved problems. Comparisons are shown as cumulative distributions of the log2 of the ratio alternative/baseline , where the baseline is (a naive implementation of) comax, and the alternative is somax. For example, a value of 1 on the x-axis means the value plotted (expansions or runtime) achieved by the alternative is 1 2 that of the baseline; a corresponding y-value of p means that the alternative achieves this, or better, in p percent of the problem instances. Replacing comax with somax reduces the informativeness, as measured by node expansions, of all the compared MO heuristics to varying degrees. In the canonical MO PDB heuristic, where node expansions often do not increase, using somax does frequently reduce total runtime. Improved comax implementations. We also compare improved implementations of comax. These have no effect on expansions, since the maximum, and therefore the heuristic, computed is always the same, but have an effect on runtime. Figure 2(d) shows the result. Runtime ratio distributions for PDB(2), PDB(3) and Hmax using somax i.e., the curves from Figure 2(c) are shown in gray to make comparison easier. The baseline (naive) implementation computes all pair-wise vector maximums first, and then filters out dominated ones. (This is the implementation that was used in the experiments reported by Geißer et al.) The first improved version ( v.1 ) filters dominated cost vectors on-the-fly, as each pair-wise maximum is added to the result set. The second improved version ( v.2 ) does the the same, but also filters dominated cost vectors from both input sets before computing the maximum. In Hmax and H2, where each input to the maximum is a minimum, this is already the case, since the MO minimum of two cost vector sets V1 and V2 is defined as ND(V1 V2). Hence, in Hmax and H2 versions 1 and 2 are the same (we label them both v.2 ). The baseline version of comax used in Hmax and H2 does not perform filtering of dominated cost vectors at all, since the maximums are recursively input to the minimum operator. In the canonical PDB heuristic, however, inputs to the maximum are sums: these are dominance-filtered in version 2. The third improved version ( v.3 ) checks for cost vectors common to V1 and V2 first, and adds these directly to the result set (by Lemma 14). This can be done in time O(|V1| + |V2|) because the set implementation sorts set elements in lexicographic order. It then computes the remaining cost vectors in comax(V1, V2), with on-the-fly dominance filtering. It is also applied to dominance-filtered input sets. MAXIMISATION OF ADMISSIBLE MO HEURISTICS In the MO Hmax heuristic, introducing any dominance filtering of the MO maximum has a runtime overhead and little or no benefit. In the canonical MO PDB heuristic, however, incremental dominance filtering (version 1) often reduces runtime, and in combination with dominance filtering of the input vector sets (version 2) even more so, with a median reduction around 12% for PDBs of size 3. The special handling of common cost vectors (version 3) does not improve on this, however. Note, though, that even the best comax implementation does not outperform the heuristic using somax, which solves 82% and 60% of problems in less time when used with PDBs of size 2 and 3, respectively, although the heuristic using comax (v.2) solves more problems overall. Tie-breaking in somax. When neither V1 V2 nor V2 V1, somax falls back on a tie-breaking condition to choose one of the two sets. Lastly, we examine how frequently this tie-breaking occurs, and evaluate the effect of some alternative tie-breaking rules. Our default tie-breaking rule (used in the comparison with comax above) selects the first argument: under this rule, somax(V1, V2) equals V2 if V1 V2 and V1 otherwise. This has the advantage that only one set dominance check is required. However, to measure how often tie-breaking occurs, we modified the somax implementation to perform both dominance checks, and then explicitly apply a tie-breaking rule when neither V1 V2 nor V2 V1. In addition to the default, choose first rule, we trialled two other tie-breaking rules: 1) choose small , which selects the smaller (by cardinality) of V1 and V2; and 2) choose big , which selects the larger of V1 and V2. When V1 and V2 have the same size, both rules fall back to choose first. The rationale for preferring larger heuristic sets is that these may be a more accurate representation of the Pareto cover set of cost vectors, and therefore more informative, while the reason for preferring smaller sets is that the size of the heuristic set impacts the time required to perform many operations, including dominance checking and subsequent maximisations. Figure 3(a) shows the fraction of somax calls that were decided by the tie-breaking rule, i.e., for which neither V1 V2 nor V2 V1, under different MO heuristics. We call this the tie-breaking ratio. (Note, though, that instances in which V1 and V2 are equal also count as decided by tiebreaking here, even though the rule used does not matter in such cases.) The ratio shown is using the choose first rule; using one of the other tie-breaking rules makes very small changes to the tie-breaking ratio. Figures 3(b c) show the impact of the variant tie-breaking rules on heuristic informativeness (as measured by number of expansions) and total runtime, in comparison with the baseline choose first rule. Note that the implementation of the baseline rule used here performs both dominance checks, rather than just one. We omit H2 from the comparison in Figures 3(b c) due to the small number of instances solved with it. The MO Hmax and MO H2 heuristics have a much higher tie-breaking ratio, compared to the canonical MO PDB heuristic. Note also that MO Hmax performs, at median, 7.25 times more somax calls per heuristic evaluation compared to the canonical MO PDB heuristic with patterns of size 3, and 36 times more than the PDB heuristic with patterns of size 2. Consistent with this, Hmax shows the greatest amount of variation in informativeness and runtime when we vary the tie-breaking rule, while the MO PDB heuristic with patterns of size 2 shows the least. Somewhat surprisingly, preferring smaller heuristic sets yields more informed heuristics more frequently than tie-breaking in favour of larger sets with the MO Hmax and canonical MO PDB heuristic with patterns of size 3. Neither rule, however, yields a consistent improvement over the default, choose first, rule. HASLUM & WANG comax (naive) comax (v.2) somax PDB(2) 275 275 272 PDB(3) 308 312 295 Hmax 223 216 195 H2 43 7 Table 1: Number of problems solved with each heuristic using different MO maximum operators. The baseline (naive) and version 2 of comax differ in how comax(V1, V2) is implemented; this affects the time to compute the operator, but not its result. Figure 2: Comparison of MO maximum operators in the context of MO PDB, Hmax and H2 heuristics. The x-axis is log2 of the ratio alternative/baseline , where the baseline is the naive implementation of comax. The y-axis is cumulative percentage, of instances solved by both. (a) Node expansions. (b) Runtime; (c) closeup of the range of ratios 0.8 0 in (b). (d) Runtime comparison of different comax implementations in canonical MO PDB heuristics (see text for descriptions). MAXIMISATION OF ADMISSIBLE MO HEURISTICS Figure 3: (a) somax reliance on the tie-breaking condition in the context of different MO heuristics. The tie-breaking ratio (x-axis) is the fraction of somax calls that were decided by the tie-breaking rule. (b c) Distribution of the number of expansions and runtime over varying MO heuristics and tie-breaking rules. The x-axis is the log2 of the ratio alternative/baseline , where the baseline is the same heuristic with the choose first rule. The y-axis, in all three plots, is the cumulative frequency (in %) of instances solved with the respective heuristic/tie-breaking rule. HASLUM & WANG 6. Conclusion Multi-objective heuristics, because dominance imposes only a partial order on heuristic values, have more options for admissible combination than their single-objective counterparts. Although we have shown that the component-wise maximum (comax) is the greatest possible admissibility-preserving MO maximum operator, its potential computational overhead, particularly when heuristic sets are large and high-dimensional, motivates continued investigation into its efficient implementation as well as of alternative MO maximum operators. The experimental evaluation conducted by Geißer et al. (2022) suggested that heuristics using the comax MO maximum operator were, in aggregate across the benchmark set, superior to those using the admax operator, with exceptions for certain combinations of heuristic and domain. Our experimental results are consistent with this. While the admax MO maximum operator turns out to be not admissibility-preserving, the somax operator we have proposed achieves a similar trade-off in canonical MO PDB heuristics, sacrificing some informativeness for, in a majority of cases, lower runtime, also when compared to an improved implementation of comax. Appendix A. comax in the Bi-Objective Case As is often the case in multi-objective search and optimisation, the special case of k = 2 objectives exhibits some particular properties. Specifically, in this section, we prove for this case a characterisation of the cost vectors that are in comax(V1, V2) (Proposition 21). A consequence of this is that when k = 2, the size of comax(V1, V2) is bounded by |V1|+|V2|, i.e., the worst case size is the sum of the input set sizes rather than the product, as it is in the general case (Proposition 11). We also propose a linear-time algorithm for computing comax in this case. Zhang, Salzman, Felner, Kumar, Skyler, Ulloa, and Koenig (2023) also propose a polynomial-time algorithm for computing comax in the bi-objective case, based on a different approach. A.1 Characterisation of the comax Set Assume k = 2, V1 and V2 contain only non-dominated, within each set, cost vectors, and furthermore that V1 and V2 are sorted lexicographically, in increasing order, on dimension 0 first. Let y . This is necessary since both cost vectors must have one component that is strictly smaller than the corresponding component of the other, and the lexicographic order implies x x . Hence, V1 = { x1, y1 , . . . , xn, yn }, such that xi < xj and yi > yj for i < j, and likewise for V2. Another important property that holds in the bi-objective case is that v y > b > b and x < x < a < a . Hence, (i) max( v, u) = a, y and max( v, u ) = a , y , and a, y a , y ; and (ii) max( v , u) = a, y and max( v, u) = a, y , and a, y a, y . MAXIMISATION OF ADMISSIBLE MO HEURISTICS Proposition 21. Assume k = 2, V1 and V2 contain only non-dominated, within each set, cost vectors, and let v1, . . . , vm be V1 V2 sorted by i + 1 ( vp must be in the opposite set to vi+1, and therefore in the same set as vi), v0 i+1 < v0 p, and vi does not dominate and is not dominated by any cost vector in the opposite set; (v) max( vi, vp) such that vi and vp are in opposite sets, i + 1 < p, vi vl for all i < l < p ( vl must be in the opposite set to vi, and therefore in the same set as vp), v1 i < v1 p 1, vp is not dominated by any cost vector in the opposite set, and either vp does not dominate any cost vector in the opposite set, or v0 p < v0 p+1. Proof. That cost vectors satisfying condition (i) or (ii) are in comax(V1, V2) was shown in Lemma 14. Condition (iii): Consider a cost vector w = max( vi, vi+1), where vi, vi+1 are in opposite sets (i.e., one in V1 and the other in V2, and neither is in both V1 and V2), and both vi and vi+1 do not dominate and are not dominated by any vector in their respective opposite sets. Suppose w comax(V1, V2), i.e., that there is a cost vector w comax(V1, V2) such that w w. w = max( vj, vj ), where vj V1 and vj V2; note that here, vj may equal vj , and either of them may equal vi or vi+1. Since v1 i and v1 j > v1 i , and, since v1 i > v1 i+1, consequently w 1 > w1: w cannot dominate w. (2) vi+1 v0 i+1 and v0 j > v0 i+1, and, since v0 i+1 > v0 i , consequently w 0 > w0: w cannot dominate w. (3) vj v0 i+1 > v0 i and v1 j > vi > v1 i+1; consequently, w 0 > w0 and w 1 > w1: w cannot dominate w. (4) vj v1 i > v1 i+1, and thus w 1 > w1: w cannot dominate w. Again, the case with vj and vj changing places is symmetric. (7) vj = vi+1 and vj v0 i+1 > v0 i , and thus w 0 > w0: w cannot dominate w. The case with vj and vj changing places is symmetric. This shows that all cost vectors satisfying condition (iii) are in comax(V1, V2). HASLUM & WANG Condition (iv): Let w = max( vi, vi+1) such that vi and vi+1 are in opposite sets, vi+1 vp for some p > i + 1, v0 i+1 < v0 p, and vi does not dominate and is not dominated by any cost vector in the opposite set. Suppose there exists w = max( vj, vj ) comax(V1, V2) such that w w. The only difference to condition (iii) is in case (8), with vi+1 taking the role of vj and vp taking the role of vj : since vi+1 vp, the ordering vi+1 v1 p ( v1 j v1 p 1 because j may equal p 1), so w = v0 p, v1 i and w = vj . The additional condition ensures w 1 = v1 j v1 p 1 > v1 i so w cannot dominate w. (2) vp can dominate some other cost vector vq. Note that vq must be in the opposite set to vp (and therefore in the same set as vi) and that vp p. Again, Lemma 20 does not apply, but the additional condition v0 p < v0 p+1 ensures v0 p < v0 q and therefore that max( vi, vp) max( vi, vq). It remains to show that no other combination max( vi, vj), where vi and vj are from opposite sets, not satisfying any of the conditions above, is in comax(V1, V2), i.e., that any such cost vector is dominated by or equal to some other cost vector in comax(V1, V2). Since the component-wise maximum of two vectors is commutative, we can assume w.l.o.g. that i < j. (a) Suppose neither vi nor vj dominates or is dominated by any cost vector in their respective opposite sets. If j = i + 1, then there exists some vl such that vi v1 p+1, so vp+1 max( vi, vp). (d) Suppose vj dominates some cost vector in the opposite set (and vi does not) and that condition (iv) does not apply. There are three cases: (1) vi is dominated, by vj or some other cost vector in the same set as vj. This is covered by case (b) above. (2) vj 1 satisfies condition (iv) and vi v1 p, so vp max( vi, vj). We can now state the proof of Proposition 11: Proposition 11. Assume k = 2: | comax(V1, V2)| |V1| + |V2|. Proof. We can assume V1 and V2 contain only non-dominated, within each set, cost vectors. Let D = { v V1 | u V2 : u v} { v V2 | u V1 : u v}, i.e., the subset of cost vectors in V1 V2 that are dominated by a cost vector from the opposite set. For each vi (V1 \ D), there is at most one vj (V2 \ D) with i < j, that can satisfy at most one of conditions (iii)-(v), giving rise to a non-dominated cost vector in comax(V1, V2), and likewise for each vi (V2 \ D). Hence, comax(V1, V2) contains at most |D| + |V1 \ D| + |V2 \ D| cost vectors. A.2 A Geometric Interpretation The set of cost vectors dominated by v is D( v) = { u | vi ui, 0 i < k} { v}. The set of cost vectors dominated by a set V is the union of the sets dominated by each cost vector in V , i.e., D(V ) = S v V D( v). From Proposition 9, we have that the set of cost vectors dominated by comax(V1, V2) is the intersection of the sets dominated by V1 and V2, i.e., D(comax(V1, V2)) = D(V1) D(V2). In the special case of k = 2, v = vx, vy , D( v) can be viewed in the plane as the quadrant above and to the right of v, including the line segments { vx, y | y > vy} and { x, vy | x > vx}. Figure 4 illustrates conditions (ii) (v) of Proposition 21. A.3 Algorithm We can now use the above result to create a specialised algorithm for computing comax in the biobjective case. This algorithm examines only the relevant pairs of cost vectors from the two input sets, and generates only the non-dominated cost vectors in the resulting set (i.e., dominance filtering of the result set is not needed). Thus, it runs in linear time. First, we need to show one more fact about the relation between dominance and lexicographic ordering: Lemma 22. If v1