Paper deep dive
Approximate Multi-Objective Search Under Rulebooks
Omar Muhammetkulyyev, Oren Salzman, Tichakorn Wongpiromsarn
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 90%
Last extracted: 8/9/2026, 3:37:50 AM
Summary
The paper introduces RA*pex, a best-first search algorithm for approximate multi-objective search under rulebooks. It addresses the computational expense of finding full rulebook-optimal solutions by proposing epsilon-rule-dominance and leveraging dimensionality reduction to efficiently compute a compact set of epsilon-approximate solutions, achieving significant speedups over existing methods.
Entities (6)
Relation Signals (5)
RA*pex → uses → epsilon-rule-dominance
confidence 95% · RA*pex leverages dimensionality reduction... while respecting rule hierarchies... We introduce the concept of epsilon-rule-dominance... and propose RA*pex
RA*pex → solves → Multi-Objective Search (MOS)
confidence 92% · propose RA*pex, a best-first search algorithm that efficiently computes a compact set of epsilon-approximate rulebook-optimal solutions.
RA*pex → employs → Dimensionality Reduction
confidence 90% · RA*pex leverages dimensionality reduction, a technique used to speed up existing multi-objective search algorithms
RA*pex → extends → A*pex
confidence 88% · A*pex, which also serves as the algorithmic foundation of our algorithm.
Rulebooks → generalizes → Multi-Objective Search (MOS)
confidence 85% · Rulebooks formalize these relationships, allowing partial ordering of objectives that generalizes both Pareto and lexicographic dominance.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Robotic planning often involves multiple objectives with complex priority relationships, such as safety, efficiency, and regulatory compliance. Rulebooks formalize these relationships, allowing partial ordering of objectives that generalizes both Pareto and lexicographic dominance. Computing the full set of rulebook-optimal solutions, however, is computationally expensive. To address this challenge, we introduce the concept of epsilon-rule-dominance, a principled notion of approximate dominance under rulebooks, and propose RA*pex, a best-first search algorithm that efficiently computes a compact set of epsilon-approximate rulebook-optimal solutions. RA*pex leverages dimensionality reduction, a technique used to speed up existing multi-objective search algorithms, while respecting rule hierarchies by maintaining separate closed sets and performing dominance checks over truncated and residual rule sets. We provide a formal analysis of RA*pex, proving that every rulebook-optimal solution is epsilon-rule-dominated (a generalization of approximate dominance we introduce) by at least one solution in the returned set. Empirical results demonstrate that our approach achieves computation times over two orders of magnitude faster than existing methods.
Tags
Links
- Source: https://arxiv.org/abs/2608.04398v1
- Canonical: https://arxiv.org/abs/2608.04398v1
PDF not stored locally. Use the link above to view on the source site.
Full Text
79,405 characters extracted from source content.
Expand or collapse full text
11institutetext: Iowa State University, Ames IA 50010, USA 11email: omar99@iastate.edu, 11email: nok@iastate 22institutetext: Technion - Israel Institute of Technology, Haifa 3200003, Israel 22email: osalzman@cs.technion.ac.il Approximate Multi-Objective Search Under Rulebooks Omar Muhammetkulyyev Oren Salzman Tichakorn Wongpiromsarn Abstract Robotic planning often involves multiple objectives with complex priority relationships, such as safety, efficiency, and regulatory compliance. Rulebooks formalize these relationships, allowing partial ordering of objectives that generalizes both Pareto and lexicographic dominance. Computing the full set of rulebook-optimal solutions, however, is computationally expensive. To address this challenge, we introduce the concept of -rule-dominance, a principled notion of approximate dominance under rulebooks, and propose RA*pex, a best-first search algorithm that efficiently computes a compact set of -approximate rulebook-optimal solutions. RA*pex leverages dimensionality reduction, a technique used to speed up existing multi-objective search algorithms, while respecting rule hierarchies by maintaining separate closed sets and performing dominance checks over truncated and residual rule sets. We provide a formal analysis of RA*pex, proving that every rulebook-optimal solution is -rule-dominated (a generalization of approximate dominance we introduce) by at least one solution in the returned set. Empirical results demonstrate that our approach achieves computation times over two orders of magnitude faster than existing methods. 1 Introduction Robotic planning and navigation problems often require reasoning over multiple, potentially conflicting objectives, including safety, efficiency, and task-related constraints. For example, an autonomous vehicle must avoid collisions, respect traffic rules, and minimize travel time and energy consumption. These requirements naturally lead to multi-objective search (MOS), in which planning is performed on graphs whose edge weights are represented by vectors of multiple cost components, each representing a distinct objective. In classical MOS, solution paths are compared using Pareto dominance, i.e., a path π dominates another path π′π if every cost component of π is no larger than the corresponding component of π′π and at least one component is strictly smaller. Instead of returning a single optimal solution, MOS aims to compute the complete set of non-dominated solution paths. While this formulation captures trade-offs among objectives without requiring manual weighting, it is computationally demanding as the number of non-dominated paths grows exponentially with the size of the graph [2, 8]. Moreover, unlike a single objective search where there is only one optimal cost, the number of optimal cost vectors in MOS are also exponential in terms of the graph size. The inherent complexity of MOS has motivated the development of approximate algorithms [9, 20]. Instead of computing the complete set of non-dominated solutions, these methods aim to compute a reduced representative subset that approximates the Pareto frontier within a specified tolerance. Many robotic applications, however, impose additional structure on objective relationships that is not captured by Pareto dominance alone [14]. In particular, safety-critical objectives are often strictly more important than efficiency-related objectives. This observation has led to lexicographic formulations that impose a strict priority ordering among objectives [18]. Lexicographic search can substantially reduce the solution space, but it requires a strict total ordering and cannot handle partial or mixed priority relationships. In practice, robotic planning problems frequently involve a combination of hierarchical and non-comparable objectives. For example, collision avoidance may be strictly prioritized over regulatory compliance, while objectives such as minimizing energy consumption and travel time may remain mutually non-comparable. We adopt the rulebooks formalism [3] to formalize complex relationships among objectives. Rulebooks capture partial priority structures that subsume both Pareto dominance and lexicographic ordering. However, computing the set of non-dominated solutions under a rulebook remains computationally expensive and exhibits exponential worst-case complexity [19]. This paper addresses the computational challenges of MOS under rulebooks. Our contributions are threefold. First, we introduce the notion of -dominance with respect to rulebooks, which provides a principled approximation of the rulebook non-dominated solution set. Second, we propose an algorithm that computes a set of approximate solutions such that every solution path is -rule-dominated by at least one path in the returned set. Finally, we present extensive experimental results demonstrating that our approach achieves significant computational improvements (up to two orders of magnitude faster) over existing algorithms that compute the complete set of rulebook non-dominated solutions, while preserving the intended objective priorities. 2 Preliminaries This section presents formal definitions and concepts of MOS [17] and rulebooks [3, 19]. Throughout the paper, we let ℝ,ℝ≥0,ℝ>0R,R_≥ 0,R_>0 and ℕN denote the set of real, non-negative real, positive real, and natural numbers, respectively. Boldface symbols denote vectors or vector-valued functions and viv_i denotes the i-th component of a vector or vector function v. Let p and q be N-dimensional vectors. We write +p+q to denote component-wise addition. For a minimization problem, we say that p weakly dominates q, denoted ⪯p , if pi≤qip_i≤ q_i for all i. We say that p dominates q, denoted ≺p , if ⪯p and pj<qjp_j<q_j for at least one index j. Finally, let ∈ℝ≥0N _≥ 0^N be another non-negative N-dimensional vector. We say that p approximately dominates q with an approximation factor , denoted ⪯p _ q, if pi≤(1+εi)qip_i≤(1+ _i)q_i for all i. 2.1 Multi-Objective Search (MOS) In Multi-Objective Search (MOS), we are given a directed graph G=(V,E)G=(V,E) where each edge e∈Ee∈ E has a nonnegative cost vector (e)∈ℝ≥0Nc(e) _≥ 0^N, where N>0N>0 is the number of objectives. A path is a sequence of vertices π=⟨v1,…,vk⟩π= v_1,…,v_k such that vi∈Vv_i∈ V and (vi,vi+1)∈E(v_i,v_i+1)∈ E for all i. We let Π denote the set of all paths in G. The cost of a path π∈Ππ∈ is defined as the component-wise sum of the cost vectors of its edges: c(π)=∑i(vi,vi+1)c(π)= _ic(v_i,v_i+1). Given start and target vertices s,t∈Vs,t∈ V, a path from s to t is called a solution. A solution is Pareto-optimal iff its cost is not dominated by any other solution. The objective of the basic MOS problem is to compute the set Π⋆⊆Π of Pareto-optimal solutions, also known as the Pareto front (PF), for given s,t∈Vs,t∈ V. As the size of Π⋆ may be exponential in |V||V|, computing the entire PF is often impractical. Thus, we instead seek its bounded approximation. Specifically, given an approximation factor ∈ℝ≥0N _≥ 0^N, the -approximate PF, denoted Π⋆ _ , is a set of solutions such that ∀π∈Π⋆,∃π′∈Π⋆s.t.(π′)⪯(π)∀π∈ ,∃π ∈ _ ~s.t.~c(π ) _ c(π). Namely, every solution in Π⋆ is approximately dominated by some solution in Π∗ ^*_ . 2.1.1 Exact MOS algorithms and dimensionality reduction. Arguably, the most common approach to MOS is using a best-first search approach [1, 5, 6, 12, 13, 16] which generalizes the celebrated A∗ algorithm [10] to the MOS setting. A key insight that dramatically improved the efficiency of these algorithms was to order the nodes in the priority queue in increasing lexicographic order and apply the notion of dimensionality reduction [15]. More specifically, when the search frontier is ordered lexicographically, the value of the first objective is guaranteed to be non-decreasing throughout the expansion process. This monotonicity implies that any newly generated node will essentially have a first-objective cost that is equal to or greater than that of any previously expanded node, rendering explicit comparisons for this dimension redundant. As a result, the dominance check can be restricted to the remaining objectives, effectively reducing the dimensionality of the problem by one. This was shown (see, e.g., [11, 15]) to have a dramatic impact on the running time of the algorithm. For additional details, see [15, 17]. 2.1.2 Approximate MOS algorithms. Arguably, the state-of-the-art algorithm to compute an -approximate PF is A*pex [20], which also serves as the algorithmic foundation of our algorithm. Similar to exact MOS heuristic search algorithms, A*pex performs a best-first search over the search space. The efficiency of A*pex stems from the fact that instead of reasoning about single paths, A*pex reasons about sets of paths with the same last vertex and similar costs, which results in small numbers of search-node expansions and thus small runtimes. Specifically, each node of A*pex is represented by an apex-path pair =⟨,π⟩AP= A,π , where ∈ℝ≥0N A _≥ 0^N is called the node’s apex and π∈Ππ∈ is called the node’s representative path, with the requirement that ⪯(π) A (π), i.e., the apex weakly dominates the cost of the representative path. The vertex v()v(AP) of AP is defined as v():=v(π)v(AP):=v(π), where v(π)∈Vv(π)∈ V is the last vertex of path π. Each apex-path pair =⟨,π⟩AP= A,π corresponds to a set of paths Π _AP (which includes π) with the same last vertex v()v(AP). Instead of storing Π _AP explicitly, A*pex only stores the apex =minπ′∈Π(π′) A= _π ∈ _AP\c(π )\, which is the component-wise minimum of (and hence weakly dominates) the costs of all paths in Π _AP, including the representative path π∈Ππ∈ _AP. Given a heuristic function :V→ℝ≥0Nh:V _≥ 0^N, the g-value and f-value of =⟨,π⟩AP= A,π are defined as ():=g(AP):= A and ():=+(v())f(AP):= A+h(v(AP)). Finally, we say that AP is -bounded iff (π)⪯()f(π) _ f(AP), where (π):=(π)+(v(π))f(π):=c(π)+h(v(π)). As we will see, all nodes in A*pex will be -bounded. Before we explain how apex-path pairs are used, let us define the operations on apex-path pairs: First, extending an apex-path pair =⟨,π⟩AP= A,π by an edge e results in an apex-path pair ′=⟨+(e),π′⟩AP = A+c(e),π , where π′π is a path π extended by edge e. Conceptually, apex-path pair ′AP corresponds to the set of paths Π′ _AP that extends every path in Π _AP by e. It is easy to verify that the apex of ′AP is the component-wise minimum of the costs of the paths in Π′ _AP . The second operation is merging two apex-path pairs that contain the same vertex. Conceptually, merging two apex-path pairs corresponds to merging the two sets of paths that these two apex-path pairs correspond to. Hence, the apex of the merged apex-path pair is the component-wise minimum of the apexes of the two apex-path pairs. The representative path of the merged apex-path pair is either one of the two representative paths of the two apex-path pairs. A*pex starts with a single apex-path pair ⟨,[s]⟩ 0,[s] in a priority-queue Open. In each iteration, A*pex extracts an apex-path pair AP from Open with the lexicographically smallest f-value. The algorithm then performs dominance checks and discards AP if either (i) there exists a solution already found whose cost -dominates the f-value of AP or if (i) there exists an expanded apex-path pair that contains v()v(AP) and whose g-value weakly dominates ()g(AP) When A*pex expands an apex-path pair that contains the goal vertex t, it adds the representative path of this apex-path pair to the set of found solutions. When A*pex expands an apex-path pair that does not contain t, it generates a child apex-path pair AP for each vertex v′v such that (v,v′)∈E(v,v )∈ E by extending the expanded apex-path pair with edge (v,v′)(v,v ). Consider that the child apex-path pair AP is not discarded after the dominance checks, and let Open[v] Open[v] be the set of apex-path pairs in Open that contains vertex v. A*pex then checks if there exists an apex-path pair ′AP in Open[v()] Open[v(AP)] that results in an -bounded apex-path pair when merged with AP. If so, A*pex removes ′AP from Open and then adds the merged apex-path pair to Open. Otherwise, it adds AP to Open. When Open becomes empty, A*pex terminates and returns the set of solutions as an -approximate Pareto frontier. 2.2 Rulebooks To avoid ambiguity in terminology, we fix the following conventions for the remainder of the paper. Specifically, we follow standard robotics terminology and use the term state to refer to what is commonly called a vertex in graph-search literature, and realization to refer to a path. Readers familiar with graph terminology may interpret these terms interchangeably. A rulebook is evaluated over a set of possible outcomes, referred to as the set of realizations and denoted by Σ . In the context of multi-objective search, a realization corresponds to a path in the underlying graph. A rulebook consists of two main components: a set of rules and a preorder that specifies their relative importance. Each rule corresponds to a distinct objective and assigns a non-negative cost that reflects the degree to which the realization violates the objective. The preorder encodes priority relationships among rules, allowing the representation of both hierarchical objectives and objectives that are not comparable. Definition 1 A rule is a function r:Σ→ℝ≥0r: _≥ 0 that measures the degree of violation of its argument. For any realizations x,y∈Σx,y∈ , r(x)<r(y)r(x)<r(y) indicates that y violates the rule r to a greater extent than x. In particular, r(x)=0r(x)=0 indicates that x fully satisfies the rule. Although we refer to these functions as “rules”, they are not limited to regulatory constraint. A rule may represent performance-related objectives like efficiency or user preferences that are desirable but not strictly required. Definition 2 A preorder on a set S is a binary relation ≲ that is reflexive (s≲s s for all s∈Ss∈ S), and transitive (s1≲s2s_1 s_2 and s2≲s3s_2 s_3 imply s1≲s3s_1 s_3 for all s1,s2,s3∈Ss_1,s_2,s_3∈ S). A preorder generalizes a partial order by relaxing the antisymmetry requirement. In particular, it allows both s1≲s2s_1 s_2 and s2≲s1s_2 s_1 to hold for distinct elements s1≠s2s_1 =s_2. This property enables the representation of objectives that are of equal priority [19]. One can define an equivalence relation ∼ on S so that s1∼s2s_1 s_2 if and only if s1≲s2s_1 s_2 and s2≲s1s_2 s_1. The preorder on S can then be viewed as a partial order on S∖∼S\, where each element is an equivalence class of ∼ . Definition 3 A rulebook is defined as a tuple ℛ=⟨R,≲⟩R= R, , where R is the set of rules and ≲ is a preorder on R that specifies their relative importance. As proved by Slutsky et al. [3], a rulebook ℛR induces a preorder ≲ℛ _R on Σ , ensuring consistency and preventing cyclic preferences among realizations. Intuitively, a realization x is considered “at least as desirable as” a realization y if any increased violation in a lower-priority rule is compensated by an improvement in a higher-priority rule. Formally, we say that x weakly rule-dominates y, denoted x≲ℛyx _Ry, if for any rule r′∈Rr ∈ R such that r′(x)>r′(y)r (x)>r (y), there exists a higher priority rule r>r′r>r such that r(x)<r(y)r(x)<r(y). We say that x rule-dominates y, denoted by x<ℛyx<_Ry, if x≲ℛyx _Ry but y≴ℛxy _Rx. 3 Problem Formulation We consider multi-objective search on a graph G=(S,E)G=(S,E), where S is a finite set of states and E⊆S×SE S× S is a finite set of edges. A realization is any path in G, regardless of its start or end states. We let Σ denote the set of all realizations. The quality of a realization is evaluated using a rulebook ℛ=⟨R,≲⟩R= R, where R=r1,…,rNR=\r_1,…,r_N\, which induces a preorder ≲ℛ _R on Σ as defined in Section 2.2. Let sstart∈Ss_start∈ S and sgoal∈Ss_goal∈ S denote the start and goal states, respectively. We define the set of solutions as the subset of realizations that start at sstarts_start and end at sgoals_goal and denote this set by Σsol⊆Σ _sol . We first define the notion of optimality with respect to a rulebook. A solution is said to be rulebook-optimal if it is not rule-dominated by any other solution. The set of all such solutions forms the rulebook-optimal solution set. Definition 4 The rulebook-optimal solution set is defined as ℛ=x∈Σsol|∄y∈Σsol such that y<ℛxP_R=\x∈ _sol\ |\ ∃ y∈ _sol such that y<_Rx\ The set ℛP_R generalizes the classical Pareto-optimal set and captures both hierarchical and non-comparable objectives. As in standard multi-objective search, the size of ℛP_R can grow exponentially in the size of the graph, making exact computation impractical for large problems. To enable approximation of ℛP_R, we introduce a relaxed notion of rule-dominance. Definition 5 Let ℛ=⟨R,≲⟩R= R, be a rulebook, where R=r1,…,rNR=\r_1,…,r_N\, and ∈ℝ≥0N _≥ 0^N. For realizations x,y∈Σx,y∈ , we say that x -rule-dominates y, denoted x≲ℛyx _R y if for any rule rj∈Rr_j∈ R such that rj(x)>(1+εj)rj(y)r_j(x)>(1+ _j)r_j(y), there exists a higher-priority rule ri>rjr_i>r_j such that ri(x)<(1+εi)ri(y)r_i(x)<(1+ _i)r_i(y). Example 1 Consider a rulebook ℛ=⟨R,≲⟩R= R, with R=r1,r2,r3R=\r_1,r_2,r_3\, r1>r2r_1>r_2 and r1>r3r_1>r_3, i.e., r1r_1 is the highest priority rule while r2r_2 and r3r_3 are not comparable. Consider two realizations x,y∈Σx,y∈ with r1(x)=1.9r_1(x)=1.9, r2(x)=r3(x)=2r_2(x)=r_3(x)=2 and r1(y)=r2(y)=r3(y)=1r_1(y)=r_2(y)=r_3(y)=1. Then, y≲ℛxy _Rx but x≴ℛyx _Ry because r1(x)>r1(y)r_1(x)>r_1(y) and there is no rule rir_i satisfying ri>r1r_i>r_1. However, with = =1, we get y≲ℛxy _R x and x≲ℛyx _R y because r1(x)<(1+ε1)r1(y)r_1(x)<(1+ _1)r_1(y). This definition relaxes rule-dominance by allowing bounded degradation, controlled by . Using -rule-dominance, we define a notion of an approximate optimal solution set. Definition 6 A set ℛ⊆ΣsolP_R _sol is an -approximate rulebook-optimal solution set if for every rulebook-optimal solution x′∈ℛx _R, there exists a solution x∈ℛx _R such that x≲ℛx′x _R x . We note that this definition does not require the elements of ℛP_R to be rulebook-optimal or even near-optimal. In the extreme case, the entire solution set Σsol _sol trivially satisfies this definition. Our goal is not to minimize the suboptimality of the returned solutions, but to efficiently compute ℛP_R , ideally one of small size. Problem 1(Approximate Multi-Objective Search under Rulebooks:) Given a graph G=(S,E)G=(S,E), start and goal states sstart,sgoal∈Ss_start,s_goal∈ S, a rulebook ℛ=⟨R=r1,…,rN,≲⟩R= R=\r_1,…,r_N\, , and a tolerance vector ∈ℝ≥0N _≥ 0^N , compute an -approximate rulebook-optimal solution set ℛP_R . 4 Rulebook-A*pex (RA*pex) This section presents rulebook-A*pex (RA*pex), our algorithm for Problem 1. At a high level, RA*pex follows the same best-first “expand-and-prune” template as A*pex, but replaces component-wise -dominance ⪯ _ with the rulebook-based relation ≲ℛ _R . This change is conceptually simple, yet it has two important consequences that drive the technical development in the rest of the section. A*pex can rely on purely component-wise reasoning: when Open is ordered lexicographically by f, the first component becomes monotone along the search and can be ignored in dominance checks (dimensionality reduction). Under rulebooks, dominance depends on the priority structure among rules and, crucially, on whether a difference is strict (an improvement in a higher-priority rule can compensate for a degradation in a lower-priority rule). As a result, the simple component-wise dominance machinery of A*pex no longer applies directly. We first give a baseline RA*pex that operates on full rule-value vectors and uses ≲ℛ _R and ≲ℛ _R directly for pruning. This baseline introduces the algorithmic logic but does not benefit from dimensionality reduction. We then develop a dimensionality-reduction variant: we explain why the A*pex argument fails under rulebooks, and show how to restore an efficient dominance test by partitioning expanded nodes while preserving correctness. 4.1 Baseline RA*pex To simplify notation, we define a mapping that associates each realization with its vector representation of rule-violation values. Definition 7 Let ℛ=⟨R,≲⟩R= R, be a rulebook with R=r1,…,rNR=\r_1,…,r_N\. We define the mapping ℛ:Σ→ℝ≥0Nc_R: _≥ 0^N by ℛ(x)=[r1(x),…,rN(x)]c_R(x)=[r_1(x),…,r_N(x)] so that the i-th component of ℛ(x)c_R(x) represents the degree to which realization x violates rule rir_i. This vector representation allows us to reason directly about N-dimensional vectors (similar to the way that A*pex reasons about path costs). In particular, both rule-dominance and -rule-dominance can be defined and evaluated purely at the vector level, without reference to the underlying realization. Definition 8 Let ℛ=⟨R,≲⟩R= R, be a rulebook with R=r1,…,rNR=\r_1,…,r_N\ and let ,∈ℝ≥0Nu,v _≥ 0^N be N-dimensional vectors. We say that ≲ℛu _Rv, if for any rule rj∈Rr_j∈ R such that uj>vju_j>v_j, there exists a higher-priority rule ri>rjr_i>r_j such that ui<viu_i<v_i. Similarly, -rule-dominance ≲ℛ _R can be defined for vectors in the same way as for realizations in Definition 5. Motivated by A*pex, we represent each node by a rule-apex-realization pair. Definition 9 A rule-apex-realization pair ℛ=⟨,x⟩RP= ,x consists of a rule apex ∈ℝ≥0Nr _≥ 0^N and a representative realization ≲ℛ(x)r _Rc_R(x). A state of ℛ=⟨,x⟩RP= ,x , denoted s(ℛ)s(RP), is defined as the last state of x. Similar to A*pex, for a given heuristic function :S→ℝ≥0Nh:S _≥ 0^N, we define the g-value and f-value of ℛRP as (ℛ):=g(RP):=r and (ℛ):=+(s(ℛ))f(RP):=r+h(s(RP)). We say that ℛRP is -bounded iff (x)≲ℛε(ℛ)f(x) _R f(RP), where (x):=ℛ(x)+(s(x))f(x):=c_R(x)+h(s(x)). RA*pex ensures that all the rule-apex-realization pairs are -bounded. Open←⟨ Open←\ 0, [sstart]⟩[s_start] \ ; // ordered according to rule-dominance ≲ℛ _R solutions←∅solutions← ; for s∈Ss∈ S do Gcl(s)←∅G_ cl(s)← ; while Open≠∅ Open = do ℛ=⟨,x⟩←Open._()RP= ,x ← Open. extract\_min() if _(ℛ,Gcl,solutions) is\_dominated(RP,G_ cl,solutions) then // Alg. 2 continue ; Gcl(s(ℛ)).add((ℛ))G_ cl(s(RP)).add(f(RP)) ; if s(ℛ)=sgoals(RP)=s_goal (ℛ,solutions) insert(RP,solutions) ; // Alg. 4 continue ; for s′∈(s(ℛ))s ∈ succ(s(RP)) do ℛ′←⟨+ℛ(⟨s(ℛ),s′⟩),(x,⟨s(ℛ),s′⟩)⟩RP ← +c_R( s(RP),s ), extend(x, s(RP),s ) ; if _(ℛ′,Gcl,solutions) is\_dominated(RP ,G_ cl,solutions) then // Alg. 2 continue ; (ℛ′,Open) insert(RP , Open) ; // Alg. 4 x:⟨,x⟩∈solutionsreturn\x: ,x ∈ solutions\ Algorithm 1 ∗(S,E,ℛ,sstart,sgoal,,) RA^*pex(S,E,R,s_start,s_goal,h, ) The baseline version of RA*pex, outlined in Alg. 1 closely follows the structure of A*pex, but replaces vector-based dominance (⪯ and ⪯ _ ) with rule-dominance (≲ℛ _R and ≲ℛ _R ) to account for hierarchical rule priorities. This difference is reflected in the _ is\_dominated function, outlined in Alg. 2. if ∃ℛ′=⟨′,x′⟩∈solutions:(x′)≲Rε(ℛ) = ,x ∈ solutions:f(x ) _R f(RP) then // Alg. 3 remove ⟨′,x′⟩ ,x from solutionssolutions ; add ⟨__(,′),x′⟩ comp\_wise\_min(r,r ),x to solutionssolutions ; TRUEreturn\; TRUE ; if ∃w∈Gcl(s(ℛ)):w≲ℛ∃ w∈ G_ cl(s(RP)):w _Rr then TRUEreturn\; TRUE ; FALSEreturn\; FALSE ; Algorithm 2 _(ℛ=⟨,x⟩,Gcl,solutions) is\_dominated(RP= ,x ,G_ cl,solutions) Let ⟨v1ℛ,v2ℛ…vMℛ⟩ v_1^R,v_2^R… v_M^R be a topological order of R∖∼R ; Q←⟨v1ℛ,v2ℛ,…,vMℛ⟩Q← v_1^R,v_2^R,…,v_M^R ; while Q≠∅Q≠ do v=Q.pop()v=Q.pop() ; if ∃r∈[v]∃ r∈[v] such that r(x)>(1+ε)r(y)r(x)>(1+ )r(y) then FALSEreturn\,\, FALSE; else if ∃r∈[v]∃ r∈[v] such that r(x)<(1+ε)r(y)r(x)<(1+ )r(y) remove all successors of v from Q ; TRUEreturn\,\, TRUE ; Algorithm 3 Approximate dominance check x≲ℛεyx _R y for ℛ′∈listRP ∈ list do ℛnew←(ℛ,ℛ′)RP_new← merge(RP,RP ) ; if ℛnewRP_new is -bounded remove ℛ′RP from listlist ; add ℛnewRP_new to listlist ; return ; add ℛRP to listlist ; return ; Algorithm 4 (ℛ,list) insert(RP,list) RA*pex maintains three main data structures throughout the search: (i) the priority queue Open, storing candidate rule-apex-realization pairs and ordered according to rule-dominance ≲ℛ _R (instead of lexicographic ordering as in A*pex), since dominance checks are performed over the full rule-value vectors; (i) the set solutionssolutions, storing the current representative solutions; and (i) a per-state closed structure Gcl(⋅)G_ cl(·) (initialized in Line 1), storing the f-values of rule-apex-realization pairs that have already been expanded at state s. At each iteration, RA*pex extracts a rule-apex-realization pair ℛ=⟨,x⟩RP= ,x from Open (Line 1) and immediately applies the pruning test _ is\_dominated (Line 1, implemented in Alg. 2). This test consults both solutionssolutions and the state-local closed set Gcl(s(ℛ))G_ cl(s(RP)) to decide whether ℛRP can be discarded; the approximate dominance checks within _ is\_dominated rely on Alg. 3. If ℛRP is not pruned, we insert its f-value into Gcl(s(ℛ))G_ cl(s(RP)) (Line 1). If ℛRP reaches the goal state (Line 1), we insert it into solutionssolutions (Line 1) using Alg. 4. Similar to A*pex, RA*pex merges rule-apex-realization pairs by taking the component-wise minimum of their rule apexes (i.e., the merged apex is min,′ \r,r \) and keeping one of the two representative realizations; this is performed by merge in Alg. 4, Line 4. Otherwise, we generate successors (Line 1); each child ℛ′RP is again filtered by the same pruning test (Line 1) and, if it survives, inserted into Open via Alg. 4 (Line 1). Upon termination, the algorithm returns the representative realizations stored in solutionssolutions (Line 1). The core operation underlying all dominance checks is the -rule-dominance test ≲ℛε _R , shown in Alg. 3. Since the rulebook ℛR forms a partial order on R∖∼R , it can be represented by a directed acyclic graph Gℛ=(Vℛ,Eℛ)G_R=(V_R,E_R). Every vertex viℛ∈Vℛv_i^R∈ V_R represents a set of equivalent rules [viℛ]⊆R[v_i^R] R, such that r∼r′r r for all r,r′∈[viℛ]r,r ∈[v_i^R]. An edge viℛ→vjℛv_i^R→ v_j^R means that there are rules ri∈[viℛ]r_i∈[v_i^R] and rj∈[vjℛ]r_j∈[v_j^R] such that ri>rjr_i>r_j, meaning that rir_i has a higher rank that rjr_j, also implying that the rules in [viℛ][v_i^R] have a higher rank than the rules in [rjℛ][r_j^R]. The procedure in Alg. 3 follows the rulebook structure by traversing the rules in the topological order ⟨v1ℛ,v2ℛ,…,vMℛ⟩ v_1^R,v_2^R,…,v_M^R of their equivalence classes in VℛV_R, where M≤NM≤ N is the number of equivalence classes. It checks for violations that exceed the allowed bound and prunes the lower-priority rules once sufficient improvement is detected at a higher level. This hierarchical filtering is what fundamentally distinguishes RA*pex from A*pex and explains why dominance checks are more complex in the rulebook setting. 4.2 Dimensionality Reduction Recall that dimensionality reduction is more challenging with rulebooks because of the structure of rule-dominance. In A*pex, Open is ordered lexicographically by the f-values. Thus, when an apex-path pair AP is extracted from Open, lexicographic best-first ordering guarantees that the first component of ()f(AP) cannot improve upon that of any previously expanded pair that ends at the same state or any pair already in the solution set, i.e., f1()≥f1(′)f_1(AP)≥ f_1(AP ) for all ′∈Gcl(s())∪solutionsAP ∈ G_ cl(s(AP))∪ solutions. This property enables a simple form of dimensionality reduction, i.e., when checking whether ()f(AP) is dominated by any vector in Gcl(s())∪solutionsG_ cl(s(AP))∪ solutions, the first component can be ignored and dominance checks reduce to comparisons over the remaining components only. Example 2 Given three vectors =[1,3,4]u=[1,3,4], =[2,3,4]v=[2,3,4], and =[2,4,1]w=[2,4,1], consider testing whether ⪯u or ⪯v . Since u1≤w1u_1≤ w_1, it suffices to compare the suffixes [3,4][3,4] and [4,1][4,1]. Since [3,4]⋠[4,1][3,4] [4,1], we can conclude that u⋠wu w. The same reasoning applies to v, yielding ⋠v . When there are hierarchies among the rules, this simplification no longer applies. Although RA*pex also guarantees that the first component of (ℛ)f(RP) is not smaller than that of any previously expanded pair that ends at s(ℛ)s(RP) or any pair in solutionssolutions, this information alone is insufficient to determine rule-dominance. Unlike component-wise dominance, rule-dominance depends not only on non-inferiority at higher-priority rules, but also on the presence of strict improvements that may compensate for degradations at lower-priority rules. Consequently, lexicographic ordering cannot isolate a single component, and dominance checks must explicitly account for the rule hierarchy and distinguish strict from non-strict improvements, as illustrated in the following example. Example 3 Consider the same rulebook as in Example 1, namely ℛ=⟨R,≲⟩R= R, with R=r1,r2,r3R=\r_1,r_2,r_3\, r1>r2r_1>r_2 and r1>r3r_1>r_3. Let x,y,zx,y,z be realizations with ℛ(x)=[1,3,4]c_R(x)=[1,3,4], ℛ(y)=[2,3,4]c_R(y)=[2,3,4] and ℛ(z)=[2,4,1]c_R(z)=[2,4,1]. For consistency with Example 2, let =ℛ(x)u=c_R(x), =ℛ(y)v=c_R(y) and =ℛ(z)w=c_R(z). First, consider whether ≲ℛu _Rw. As in Example 2, we have u1≤w1u_1≤ w_1 and the suffixes satisfy [3,4]≴ℛ[4,1][3,4] _R[4,1] because u3>w3u_3>w_3. Under component-wise dominance, this would be sufficient to conclude non-dominance. However, under rule-dominance, the degradation at r3r_3 is offset by a strict improvement at a higher-priority rule r1>r3r_1>r_3 where u1<w1u_1<w_1. This strict improvement at a more important rule compensates for the degradation at r3r_3, and therefore ≲ℛu _Rw. Now consider whether ≲ℛv _Rw. Again, the suffixes satisfy [3,4]≴[4,1][3,4] _R[4,1]. However, unlike the previous case, there is no strict improvement at any higher-priority rule since v1=w1v_1=w_1. Since the degradation at r3r_3 is not compensated by a strict improvement at a more important rule, we conclude that ≴ℛv _Rw. Note that in both this example and Example 2, we have v1,u1≤w1v_1,u_1≤ w_1. Under rule-dominance, however, the distinction between a strict improvement (u1<w1)u_1<w_1) and equality (v1=w1v_1=w_1) is critical. This illustrates why lexicographic ordering alone is insufficient for dimensionality reduction under rule-dominance. if ∃ℛ=∈Gcl=(s(ℛ)):f1(ℛ=)<f1(ℛ) ^=∈ G_ cl^=(s(RP)):f_1(RP^=)<f_1(RP) then // transfer Gcl=G_ cl^= to Gcl<G_ cl^< for ℛ′∈Gcl<(s(ℛ))RP ∈ G_ cl^<(s(RP)) do if ∃ℛ′∈Gcl=(s(ℛ)):Tr((ℛ′))≲ℛTr((ℛ′)) ∈ G_ cl^=(s(RP)):Tr(f(RP )) _RTr(f(RP )) remove ℛ′RP from Gcl<(s(ℛ))G_ cl^<(s(RP)) ; Gcl<(s(ℛ))←Gcl<(s(ℛ))∪Gcl=(s(ℛ))G_ cl^<(s(RP))← G_ cl^<(s(RP))∪ G_ cl^=(s(RP)) ; Gcl=(s(ℛ))←∅G_ cl^=(s(RP))← ; if ∃ℛ=∈Gcl=(s(ℛ)):Tr((ℛ=))≲ℛTr((ℛ)) ^=∈ G_ cl^=(s(RP)):Tr(f(RP^=)) _RTr(f(RP)) then TRUEreturn\; TRUE ; if ∃ℛ<∈Gcl<(s(ℛ)):α((ℛ<))≲ℛα((ℛ)) ^<∈ G_ cl^<(s(RP)):α(f(RP^<)) _Rα(f(RP)) then TRUEreturn\; TRUE ; if ∃ℛ′=⟨′,x′⟩∈solutions: = ,x ∈ solutions: (x′)≲Rε(ℛ)f(x ) _R f(RP) then remove ⟨′,x′⟩ ,x from solutionssolutions ; add ⟨__(,′),x′) comp\_wise\_min(r,r ),x ) to solutionssolutions ; TRUEreturn\; TRUE ; FALSEreturn\; FALSE ; Algorithm 5 _dr(ℛ=⟨,x⟩,Gcl=,Gcl<,solutions) is\_dominated_ dr(RP= ,x ,G_ cl^=,G_ cl^<,solutions) Supporting dimensionality reduction under rule-dominance thus requires maintaining two closed sets for each state s instead of a single set Gcl(s)G_ cl(s) used in the baseline RA*pex (see Alg. 1) and in A*pex. Specifically, RA*pex maintains Gcl<G_ cl^< and Gcl=G_ cl^= for local dominance checks at each state. Intuitively, for any rule-apex-realization pair ℛRP, the set Gcl=(s(ℛ))G_ cl^=(s(RP)) stores previously expanded pairs ℛ′RP that end at the same state and have the same f1f_1-value, i.e., s(ℛ′)=s(ℛ)s(RP )=s(RP) and f1(ℛ′)=f1(ℛ)f_1(RP )=f_1(RP), while Gcl<(s(ℛ))G_ cl^<(s(RP)) stores those that end at the same state but have strictly smaller f1f_1-value. Formally, whenever ℛRP is checked for dominance, it holds that ∀ℛ′∈Gcl=(s(ℛ)),f1(ℛ′)=f1(ℛ) ∈ G_ cl^=(s(RP)),f_1(RP )=f_1(RP) and ∀ℛ′∈Gcl<(s(ℛ)):f1(ℛ′)<f1(ℛ) ∈ G_ cl^<(s(RP)):f_1(RP )<f_1(RP). With this partitioning, we update the dominance test by introducing the _dr is\_dominated_ dr function presented in Alg. 5 and using it in Alg. 1 Lines 1 and 1. To formalize the dimensionality reduction, we first compute a topological ordering [4] ⟨v1ℛ,v2ℛ,…,vMℛ⟩ v_1^R,v_2^R,…,v_M^R of the directed acyclic graph GℛG_R. We then obtain an ordering ⟨rσ(1),rσ(2),…,rσ(N)⟩ r_σ(1),r_σ(2),…,r_σ(N) of rules such that rσ(i)≮rσ(j)r_σ(i) <r_σ(j) for all i>ji>j by simply expanding each equivalence class [viℛ][v_i^R] in their topological order. Intuitively, this ordering arranges rules in non-increasing priority. Given a rule-value vector =[u1,…,uN]u=[u_1,…,u_N], we reorder its components according to this permutation to obtain σ=[uσ(1),uσ(2),…,uσ(N)]u_σ=[u_σ(1),u_σ(2),…,u_σ(N)]. Open is subsequently ordered lexicographically with respect to these reordered rule-value vectors, as in A*pex. For notational simplicity, we henceforth assume that the rules are indexed in topological order, so that ri≮rjr_i <r_j for all i>ji>j. Under this convention, r1r_1 is a highest-priority rule, meaning that there is no rule ri∈Rr_i∈ R such that ri>r1r_i>r_1 (rir_i may have equal priority as r1r_1). We then define the truncated rule set Tr(R):=r2,…,rNTr(R):=\r_2,…,r_N\, which excludes r1r_1 as in A*pex. Additionally, we define the residual rule set α(R):=ri∈Tr(R)|¬(ri<r1)α(R):=\r_i∈ Tr(R)\ |\ (r_i<r_1)\, which excludes r1r_1 and any rule that is strictly lower in priority than r1r_1. By a slight abuse of notation, we use the same operator Tr(⋅)Tr(·) and α(⋅)α(·) to denote the corresponding operations on rule-value vectors. Specifically, for any ∈ℝNu ^N, we define Tr()Tr(u) and α()α(u) as the subvector of u obtained by keeping only the components corresponding to the rules in Tr(R)Tr(R) and α(R)α(R), respectively, with the original order preserved. Alg. 5 uses Tr(⋅)Tr(·) and α(⋅)α(·) to perform dimensionality reduction-based rule-dominance. Conceptually, the algorithm maintains two state-local closed sets: Gcl=(s)G_ cl^=(s) for expanded pairs whose extracted f1f_1-value equals the current best-known value at s, and Gcl<(s)G_ cl^<(s) for expanded pairs with strictly smaller f1f_1. Whenever the extracted f1f_1 at s increases (Line 5), all pairs in Gcl=(s)G_ cl^=(s) become “strictly better in r1r_1” than the new pair and are therefore moved into Gcl<(s)G_ cl^<(s) (Lines 5–5), after filtering out entries that are already dominated in the residual space α(⋅)α(·). After this bookkeeping, the dominance test proceeds in three stages. First, it checks for a witness in Gcl=(s(ℛ))G_ cl^=(s(RP)) using only the truncated vector Tr((⋅))Tr(f(·)) (Line 5): since all candidates have the same f1f_1-value, rule-dominance cannot rely on a strict improvement in r1r_1, and we can safely ignore r1r_1 and compare the remaining rules. Second, it checks Gcl<(s(ℛ))G_ cl^<(s(RP)) in the residual space α(⋅)α(·) (Line 5): here every candidate already has a strict improvement in r1r_1, so any rule that is strictly lower priority than r1r_1 is automatically “covered” and can be removed from the comparison. Finally, it performs the global approximate-dominance check against solutionssolutions exactly as in the baseline algorithm (Line 5). 5 Theoretical Analysis This section provides a formal guarantee that RA*pex solves Problem 1. In summary, the correctness of RA*pex hinges on a key structural property of -rule-dominance ≲ℛ _R , namely its one-sided transitivity with respect to exact rule-dominance ≲ℛ _R. Definition 10 Let ≾ and ≾′ be two binary relations on a set X. We say that ≾′ is one-sided transitive with respect to ≾ if, for any x,y,z∈Xx,y,z∈ X, x≾′yx y and y≾zy z implies x≾′zx z. With the definition of -rule-dominance given in Definition 5, it can be shown that ≲ℛ _R is one-sided transitive with respect to ≲ℛ _R (see Lemma 5 below). This property is not guaranteed for alternative notions of -rule-dominance as demonstrated in the following example. Example 4 Consider an alternative definition of ≲ℛ _R : Given realizations x,y∈Σx,y∈ and a vector ≥ ≥ 0, define x≲ℛyx _R y if for any rule rj∈Rr_j∈ R such that rj(x)>(1+εj)rj(y)r_j(x)>(1+ _j)r_j(y), there exists a higher-priority rule ri>rjr_i>r_j such that ri(x)<ri(y)1+εir_i(x)< r_i(y)1+ _i. Intuitively, any degradation at a rule beyond the allowed tolerance must be compensated by a sufficiently strong improvement at a higher-priority rule. The motivation behind this definition is to treat small relative differences at higher-priority rules as negligible under approximation. In particular, if two realizations differ only slightly at a high-priority rule, then differences at lower-priority rules may still be considered meaningful. For example, consider rules R=r1,r2R=\r_1,r_2\ with r1>r2r_1>r_2 and rule-value vectors =[1,106]u=[1,10^6] and =[1.001,1]v=[1.001,1]. With =[0.1,0.1] =[0.1,0.1], the relative difference at the higher-priority rule r1r_1 is within tolerance, while v is significantly better at the lower-priority rule r2r_2. Under this alternative definition, we obtain ≲ℛv _R u but ≴ℛu _R v, i.e., v is strictly preferred to u. In contrast, under Definition 5, we have both ≲ℛv _R u and ≲ℛu _R v, so u and v are treated as equivalent. Despite this intuition, this alternative definition does not satisfy one-sided transitivity. Consider rules R=r1,r2,r3R=\r_1,r_2,r_3\ with r1>r2r_1>r_2 and r1>r3r_1>r_3, and rule-value vectors =[2,2,2],=[4,1,1],=[3,4,2]u=[2,2,2],v=[4,1,1],w=[3,4,2] with =[1,1,1] =[1,1,1]. It is easy to check that ≲ℛw _R u (since there is no rule rjr_j such that wj>2ujw_j>2u_j) and ≲ℛu _Rv (since u1<v1u_1<v_1). However, based on the alternative definition, ≴ℛw _R v because w1=3≮0.5v1=2w_1=3 <0.5v_1=2. One-sided transitivity allows us to reason about sets of realizations with ε -bounded rule-apex-realization pairs and ensures that dominance relations are safely propagated across search expansions. The following lemmas and the theorem, with -rule-dominance defined in Definition 5, show that RA*pex correctly solves Problem 1. We begin by establishing a fundamental property of the search order. Lemma 1 The sequence of extracted rule-apex-realization pairs has monotonically non-decreasing f1f_1-values. Proof The rule-apex-realization pair extracted from Open has the smallest f1f_1-value due to the lexicographic ordering. Also, any newly generated pair has an f1f_1-value that is greater than or equal to that of its parent pair, and the resulting pair of a merge can not have an f1f_1-value smaller than both of its merged pairs (their rule apexes). Thus, the sequence of extracted pairs has monotonically non-decreasing f1f_1-values. The next two lemmas justify the correctness of pruning based on previously expanded nodes. Lemma 2 If there exists a rule-apex-realization pair ℛ′RP in Gcl=(s(ℛ))G_ cl^=(s(RP)) the truncated f-value of which weakly rule-dominates the truncated f-value of some realization-pair ℛRP on Line 5 of the Algorithm 5, then the f-value of ℛ′RP weakly rule-dominates the f-value of ℛRP. Proof The rule-apex-realization pair ℛ′RP has been expanded and added to Gcl=(s(ℛ))G_ cl^=(s(RP)) before ℛRP was extracted from Open. Let ℛ0=ℛ′,ℛ1,ℛ2,…ℛk=ℛRP_0=RP ,RP_1,RP_2,…RP_k=RP be the sequence of rule-apex-realization pairs extracted since then. Because ℛ′RP is still in Gcl=(s(ℛ))G_ cl^=(s(RP)), the Line 5 of the Algorithm 5 never held. According to Lemma 1 and since the heuristic function is consistent, it follows that f1(ℛi)=f1(ℛi+1)f_1(RP_i)=f_1(RP_i+1) for all i<ki<k. Thus, f1(ℛ′)=f1(ℛ)f_1(RP )=f_1(RP) which along with the premise in the lemma implies (ℛ′)≲ℛ(ℛ)f(RP ) _Rf(RP). Lemma 3 If there exists a rule-apex-realization pair ℛ′RP in Gcl<(s(ℛ))G_ cl^<(s(RP)) the residual f-value of which weakly rule-dominates the residual f-value of some rule-apex-realization pair ℛRP on Line 5 of the Algorithm 5, then it also holds that the f-value of ℛ′RP weakly rule-dominates the f-value of ℛRP. Proof Since ℛ′RP was previously expanded and added to Gcl<(s(ℛ))G_ cl^<(s(RP)), the condition on Line 5 of the Algorithm 5 held at least once. According to Lemma 1 and because the heuristic function is consistent, it holds that f1(ℛ′)<f1(ℛ)f_1(RP )<f_1(RP). Thus, the f-value of ℛ′RP weakly rule-dominates the one of ℛRP. We then turn to the correctness of the solution-set maintenance. Lemma 4 Let ℛ=⟨,x⟩RP= ,x be a rule-apex-realization pair and y be any realization such that ≲ℛ(y)r _Rc_R(y). If we merge ℛRP with another rule-apex-realization pair then the rule apex of the resulting rule-apex-realization pair will still weakly rule-dominate (≲ℛ _R) y. Proof The rule apex of the resulting rule-apex-realization pair is the component-wise minimum of the two merged rule apexes. The next lemma shows that -rule-dominance satisfies one-sided transitivity with respect to exact rule-dominance. In other words, approximate dominance is preserved when composed with exact dominance. This property allows RA*pex to reason about sets of realizations using rule-apex-realization pairs and is crucial for establishing the algorithm’s approximation guarantees. Specifically, for a given ε -bounded rule-apex-realization pair ℛ=⟨,x⟩RP= ,x , it allows the representative realization x to -rule-dominate all the realizations that the pair represents. Lemma 5 Let x,y,zx,y,z be realizations such that x≲ℛyx _R y and y≲ℛzy _Rz, then x≲ℛzx _R z. Proof Let ℛ=⟨R,≤⟩R= R,≤ be a rulebook with R=r1,…,rNR=\r_1,…,r_N\. Assume x≲ℛyx _R y and y≲ℛzy _Rz. To show that x≲ℝzx _R z, suppose there is a rule ri∈Rr_i∈ R such that ri(x)>(1+εi)ri(z)r_i(x)>(1+ _i)r_i(z). We need to show that there exists a more important rule rj>rir_j>r_i such that rj(x)<(1+εj)rj(z)r_j(x)<(1+ _j)r_j(z). Consider two possibilities. • ri(x)≠(1+εi)ri(y)r_i(x) =(1+ _i)r_i(y). If ri(x)>(1+εi)ri(y)r_i(x)>(1+ _i)r_i(y), then x≲ℛεyx _R y guarantees that there exists a rule rk>rir_k>r_i such that rk(x)<(1+εk)rk(y)r_k(x)<(1+ _k)r_k(y). If instead ri(x)<(1+εi)ri(y)r_i(x)<(1+ _i)r_i(y), then we can set rk=rir_k=r_i. Thus, in either case, there exists rk≥rir_k≥ r_i such that rk(x)<(1+εk)rk(y)r_k(x)<(1+ _k)r_k(y). We are done if rk(y)≤rk(z)r_k(y)≤ r_k(z), since we can take rj=rkr_j=r_k. Otherwise, rk(y)>rk(z)r_k(y)>r_k(z) and y≲ℛzy _Rz imply that there exists rl>rkr_l>r_k such that rl(y)<rl(z)r_l(y)<r_l(z). Again, we are done if rl(x)≤(1+εl)rl(y)r_l(x)≤(1+ _l)r_l(y), and if not, there has to be some rule rm>rlr_m>r_l such that rm(x)<(1+εm)rm(y)r_m(x)<(1+ _m)r_m(y). Repeating this argument construncts an increasing chain ri≤rk<rl<rm…r_i≤ r_k<r_l<r_m…. Since R is finite, the chain has to stop, which is only possible if there exists n∈1,…,Nn∈\1,…,N\ such that rn(x)<(1+εn)rn(z)r_n(x)<(1+ _n)r_n(z). • ri(x)=(1+εi)ri(y)r_i(x)=(1+ _i)r_i(y). Then ri(x)>(1+εi)ri(z)r_i(x)>(1+ _i)r_i(z) implies that ri(y)>ri(z)r_i(y)>r_i(z). Because y≲ℛzy _Rz, there must exist a rule rk>rir_k>r_i such that rk(y)<rk(z)r_k(y)<r_k(z). We are done if rk(x)≤(1+εk)rk(y)r_k(x)≤(1+ _k)r_k(y), since one can take rj=rkr_j=r_k. Otherwise, there must exist a rule rl>rkr_l>r_k such that rl(x)<(1+εl)rl(y)r_l(x)<(1+ _l)r_l(y). Applying the same reasoning as in the previous case, we again obtain an increasing chain ri≤rk<rl…r_i≤ r_k<r_l… which must terminate at some rnr_n with rn(x)<(1+εn)rn(z)r_n(x)<(1+ _n)r_n(z). Lemma 6 For any prefix xl=[s1,s2…sl]x_l=[s_1,s_2… s_l] of any solution x=[s1(=sstart),s2…sL(=sgoal)]x=[s_1(=s_start),s_2… s_L(=s_goal)] with 1≤l≤L1≤ l≤ L, when the algorithm terminates, there exists either (Case 1:) an expanded rule-apex-realization pair ℛRP (that is, one that reaches Line 1 of the Alg 1) that ends at the state sls_l and whose rule apex weakly rule-dominates the g-value of the realization xlx_l or (Case 2:) a rule-apex-realization pair ℛRP in the solution set such that the f-value of its representative realization -rule-dominates the f-value of the realization xlx_l. Proof The proof is done via induction. The lemma holds for l=1l=1 and any solution since the realization pair ℛ=⟨,[sstart]⟩RP= 0,[s_start] gets expanded and has the properties required for Case 1. Now assume that the lemma holds for some l<Ll<L and any solution. Then, we prove that it is also true for l+1l+1 and this solution. Assume that Case 1 holds for l and consider both ℛRP - the realization-pair mentioned there and its potential child realization pair ℛ′RP created on Line 1 of the Algorithm 1 for s′=sl+1s =s_l+1. The realization pair ℛ′RP ends at the state sl+1s_l+1 and its rule apex weakly rule-dominates the g-value of the realization xl+1x_l+1, which implies that its f-value weakly rule-dominates the f-value of the realization xl+1x_l+1. We distinguish three cases: 1. First, the condition on Line 5 in Alg 5 (or Line 2 in the Alg 2) holds for some realization pair in the solution set, meaning, the f-value of the representative path of this realization pair -rule-dominates the f-value of the realization pair ℛ′RP . The algorithm replaces this realization pair with a new realization-pair ℛ′RP in the solution set on Line 5 in the Alg 5 (or Line 2 in the Alg 2). The pair ℛ′RP stays in the solution set but the algorithm might merge it several times with other rule-apex-realization pairs on Line 4 of Algorithm 4 before it terminates. The rule apex of the pair ℛ′RP weakly rule-dominates the f-value of the realization xl+1x_l+1 (since this rule apex is the component-wise minimum of the f-value of the pair ℛ′RP and another rule apex, and hence weakly rule-dominates the f-value of the pair ℛ′RP , which in turn weakly rule-dominates the f-value of the realization xl+1x_l+1) and merging it with other realization-pairs does not change this property according to Lemma 4. Since the pair ℛ′RP also remains -bounded, the f-value of its representative path always -rule-dominates the f-value of itself, which equals its rule-apex. Put together, according to Lemma 5 the f-value of its representative path -rule-dominates the f-value of the realization xl+1x_l+1. Thus, the merged realization pair satisfies Case 2 for l+1l+1. 2. Second, the condition on Line 5 or Line 5 of the Alg 5 (or Line 2 in the Alg 2) holds , meaning, there exists a rule-apex-realization realization pair ℛ=RP^= in Gcl=(s(ℛ′))G_ cl^=(s(RP )) the truncated f-value of which weakly rule-dominates the truncated f-value of the rule-apex-realization pair ℛ′RP or there exists a rule-apex-realization pair ℛ<RP^< in Grmcl<(s(ℛ′))G_rmcl^<(s(RP )) the residual f-value of which weakly rule-dominates that of the pair ℛ′RP . In either case, the expanded pairs ℛ=RP^= and ℛ<RP^< ending at the state sl+1s_l+1 have f-values that weakly rule-dominate the f-value of the pair ℛ′RP according to Lemmas 2 and 3 respectively. Thus, their rule apex weakly rule-dominate the rule apex of the pair ℛ′RP . Thus, either ℛ=RP^= or ℛ<RP^< satisfies Case 1 for l+1l+1 since the rule apex of the pair ℛ′RP in turn weakly rule-dominates the g-value of the realization xl+1x_l+1. 3. Otherwise, the algorithm executes Line 1 of the Alg 1 for the rule-apex-realization pair ℛ′RP , where the pair is inserted into Open, perhaps after having been merged with another realization-pair in the Algorithm 4. The algorithm might merge it several more times before finally extracting it. Its rule apex weakly rule-dominates the g-value of the realization xl+1x_l+1 and merging it with other realization pairs does not change this property according to Lemma 4. Thus, if this realization pair is expanded, it satisfies Case 1 for l+1l+1. If it is extracted but not expanded, then the pruning conditions in the Alg 5 (or the Alg 2) hold, and as we have already proved, Case 1 or Case 2 holds. Assume that Case 2 holds for l and consider the rule-apex-realization pair mentioned there. The f-value of the representative realization of this pair -rule-dominates the f-value of the realization xlx_l. Since the heuristic function is consistent, the f-value of the realization xlx_l in turn weakly rule-dominates the f-value of the realization xl+1x_l+1. Thus, according to Lemma 5, this realization-pair satisfies Case 2 for l+1l+1. Finally, we combine these results to prove Theorem 5.1. Theorem 5.1 Upon termination of RA*pex, for every solution y∈Σsoly∈ _sol, there exists a rule-apex-realization ℛ=⟨,x⟩∈solutionRP= ,x ∈ solution whose representative path -rule-dominates y, i.e, x≲ℛyx _R y. Proof Lemma 6 holds for prefix xL=x_L=x of any solution x. In case its Case 2 holds, the theorem holds by definition for realization x since the f-values of the solutions are equal to their costs. In case its Case 1 holds, consider the rule-apex-realization pair as mentioned. This pair ends at the the goal state, and the algorithm thus executed the Line 1 in Alg 1 for it, where the pair was inserted into the solution set, maybe after having been merged with another rule-apex-realization pair on Line 4 of the Algorithm 4. The pair stays in the solution set, and might be merged several more times with other rule-apex-realization pairs before the algorithm terminates. The rule apex of the pair weakly rule-dominates the g-value of the path x according to Lemma 6 and merging it with other pairs does not change this fact according to Lemma 4. Since the pair also remains -bounded (due to the conditions on Line 4 in Alg 4, Line 5 in Alg 5, Lemma 1, and the consistency of the heuristic function), the f-value of its representative realization always -rule-dominates the f-value of itself, which equals its rule apex. Putting it all together, the f-value of its representative realization -rule-dominates the g-value of the realization x according to Lemma 5. Thus, the theorem holds by definition for the realization x since the g- and f-values of the solutions are equal to their costs. 6 Experimental Results We evaluate the efficiency of RA*pex across three different problem settings that differ in both the presence of an objective hierarchy and the use of approximation. In setting (S1) objectives are non-hierarchical while in setting (S2) and (S3) objectives are hierarchical and we do not / do allow an approximation, respectively. Consequentially, we compare RA*pex against a state-of-the-art algorithm appropriate for each setting: in (S1) against A*pex, in (S2) against rulebook-based complete control synthesis [19], which we refer to as RB-Exact and in (S3) against an approximate extension of RB-Exact, which we refer to as RB-Approx. The experiments were conducted on the BAY roadmap from the 9th DIMACS Implementation Challenge: Shortest Path [7], as well as on randomly generated graphs. All experiments were run on the Macbook Air with an Apple M4 Chip, 24GB of memory, and a five-minute runtime limit per instance. All algorithms were implemented in C++, reusing common code from A*pex and RB-Exact wherever possible.111https://github.com/Infus3d/Rulebook_approximation We used the same 25 generated 3-objective roadmap instances that Zhang et al. [20] used with randomly selected start and goal states for each roadmap. A fourth objective was added by assigning to each edge a value randomly drawn from 0,1\0,1\. The heuristic function h was set as a vector, where each component corresponds to a single objective and is given by the minimum achievable cost from a state s to the goal with respect to that objective, computed using Dijkstra’s algorithm. Since computing h accounted for only a small fraction of the total runtime, all reported runtimes exclude this preprocessing step. While RA*pex outperforms the existing methods in both settings (S2) and (S3), we observed that it performs the best in the setting (S3) since the approximated planning takes advantage of the grouping of the similar cost paths in the search frontier, making it up to two orders of magnitude faster than the exact planning in (S2) on the 4-objective roadmap instances from the BAY dataset. 10−410^-410−310^-310−210^-210−110^-10112233445566778899ε runtime (seconds)A*pexRA*pex 10−410^-410−310^-310−210^-210−110^-102020404060608080100100120120140140ε solution set sizeA*pexRA*pex Figure 1: Comparison of average runtimes (left) and average solution set sizes (right) on 3-objective roadmap instances with 321,270 states and 794,830 edges, for different approximation factors ε . Setting (S1): Approximate Planning without Objective Hierarchy Fig. 1 shows the average runtimes (in seconds) of A*pex and RA*pex over all roadmap instances in the BAY dataset, plotted as a function of the approximation factor. In these experiments, is a vector whose components are set to the same scalar value ε , which is now represented on the x-axis for clarity.. Across all instances, the runtime of RA*pex is within 1.5×1.5× the runtime of A*pex while producing approximate solution sets of comparable size. This shows that, in the absence of objective hierarchies, RA*pex incurs only modest overhead relative to A*pex while maintaining similar solution quality. Setting (S2): Exact Planning with Hierarchical Objectives Fig. 2 (Left) compares RA*pex and RB-Exact on 3-objective random graph instances of increasing size, reporting both runtime (in seconds) and the size of the returned solution sets. The rule hierarchy is r1>r2r_1>r_2 and r1>r3r_1>r_3. On the smallest instances, both algorithms exhibit comparable runtimes. As graph size increases, however, the runtime of RB-Exact grows rapidly, becoming more than two orders of magnitude slower than RA*pex on the largest instances. Fig. 2 (Right) shows detailed results for 4-objective roadmap instances from the BAY dataset, with rule hierarchy r4>r1r_4>r_1, r4>r2r_4>r_2, and r4>r3r_4>r_3. In all of the instances, RB-Exact failed to finish within five minutes, while RA*pex completed all but the three largest instances. For instances with up to one million explored nodes, RA*pex found the solution set in about a minute, while for instances with up to 100,000 explored nodes, it completed in under 5 seconds. 0505010010015015020020025025030030035035040040045045050050055055060060065065070070075075010−410^-410−310^-310−210^-210−110^-110010^010110^110210^2Graph sizeRuntime (seconds)RB-Exact runtimeRA*pex runtimeSolution set size2.52.5333.53.5444.54.5555.55.5666.56.5777.57.5888.58.5999.59.5Solution set size 11223344556677889900.51.01.5InstanceNumber of nodes (×106× 10^6)Nodes exploredNodes expandedRA*pex runtime10110^110210^2Runtime (seconds) Figure 2: (Left) Runtimes (in seconds) and sizes of solution sets for RB-Exact and RA*pex on random graphs with 3 rules (r1>r2,r3r_1>r_2,r_3) under exact dominance (i.e., for = =0). (Right) Runtimes (in seconds) for RA*pex on roadmap instances with 4 rules (r4>r1,r2,r3r_4>r_1,r_2,r_3), along with the number of nodes explored and expanded during the search. r3r4r1r2 100100150150200200250250300300350350400400450450500500777.57.5888.58.5999.59.5101010.510.5111111.511.51212Graph sizeAverage solution set sizeRB-Exact (solution)RB-Approx (solution)RA*pex (solution)RB-Approx (runtime)RA*pex (runtime)10−210^-210−110^-110010^0Average runtime (seconds) Figure 3: (Left) A preorder of four rules in (S3)). (Right) The average solution set sizes and runtimes for RB-Exact, RB-Approx and RA*pex on random graphs with this rulebook under the approximation =[0.01,0.01,0.01,0.01] =[0.01,0.01,0.01,0.01]. Setting (S3): Approximate Planning with Hierarchical Objectives Lastly, we report the performance of RA*pex in the presence of rule hierarchies with non-zero approximation vector . Due to the absence of a prior work done on this, we compared the results against the approximate extension of RB-Exact, where an additional global dominance check was incorporated. In this variant, which we call RB-Approx, whenever a new candidate realization x is constructed, this global dominance check examines whether or not the cost of x is approximately dominated by some realization x′x already present in the solution set. If so, then the realization x is discarded since the cost of any realization with the prefix x will also be approximately dominated by x′x . Consequently, RB-Approx not only finds an -approximate rulebook-optimal solution set but also guarantees that every solution is rulebook-optimal. For this experiment, we randomly generated graphs of varying sizes with 4 objectives. The rule hierarchy assigns equal importance to r3r_3 and r4r_4, while r1r_1 and r2r_2 have lower priority than both. Specifically, the hierarchy (illustrated in Fig. 3) is given by r3≲r4r_3 r_4, r4≲r3r_4 r_3, r2<r3r_2<r_3, r1<r4r_1<r_4. Fig. 3 shows the average runtimes and the solution sizes for RB-Approx and RA*pex. In all of them, RA*pex runs more than an order of magnitude faster than RB-Approx, with the difference growing more and going up to 16× the runtime of RB-Approx on the largest graph. The solution set sizes, however, remain relatively comparable, with RA*pex having a slight advantage on average while RB-Approx being closer to the rulebook-optimal frontier sizes. This makes sense when we consider that the solution set returned by RB-Approx is also a subset of the rulebook-optimal frontier, and hence might require more solutions from the frontier to cover what a few solutions not on the frontier could approximately cover. We also evaluate the effect of dimensionality reduction in RA*pex by comparing it against a baseline version that operates in the full objective space. As shown in Figure 4, dimensionality reduction leads to a substantial decrease in runtime, often by an order of magnitude (up to 17×) for better factors, while producing solution sets of comparable size. Although the extent of this improvement depends on the specific rule hierarchy, these results demonstrate that exploiting rulebook structure to reduce effective dimensionality can significantly improve computational efficiency without sacrificing solution quality. 1x5x17x10−110^-110010^010110^110210^210−110^-110010^010110^110210^2Baseline RA*pexRA*pexε = 0.01ε = 0.001ε = 0.0001 1x10010^010110^110210^210010^010110^110210^2Baseline RA*pexRA*pexε = 0.01ε = 0.001ε = 0.0001 Figure 4: Individual runtimes (left) and solution sizes (right) of the baseline RA*pex and RA*pex with dimensionality reduction on 4-objective road map instances with 321,270 states and 794,830 edges for varying approximations with the rule hierarchy being r1∼r2r_1 r_2, r1>r3r_1>r_3, r2>r4r_2>r_4 (similar to Figure 3). 7 Conclusions We presented RA*pex, an approximate multi-objective search algorithm that leverages the rulebook formalism to precisely express complex relationships among objectives, while providing provable approximation guarantees. RA*pex generalizes A*pex to settings where objectives are partially ordered by priority. A key theoretical contribution of this work is the identification of one-sided transitivity as a crucial structural property for approximate rule-dominance. We showed that the proposed definition of -rule-dominance satisfies one-sided transitivity with respect to exact rule-dominance, which allows dominance relations to be safely propagated across search expansions and establish the correctness of RA*pex. Our experimental results evaluated RA*pex across three problem settings that vary in the presence of objective hierarchy and the use of approximation. Across all settings, RA*pex consistently matched or significantly outperformed specialized state-of-the-art algorithms. Overall, RA*pex bridges the gap between exact rulebook-based planning and approximate multi-objective search, offering a principled and efficient approach to approximate multi-objective search under rulebooks. We believe this approach opens the door to scalable planning and control synthesis in complex systems where objectives are partially ordered and exact optimality is neither required nor tractable. credits This work was supported in part by NSF under Grant CNS-2141153. References [1] S. Ahmadi, G. Tack, D. Harabor, and P. Kilby (2021) Bi-objective search with bi-directional A*. In European Symposium on Algorithms (ESA), LIPIcs, Vol. 204, p. 3:1–3:15. Cited by: §2.1.1. [2] T. Breugem, T. Dollevoet, and W. van den Heuvel (2017) Analysis of fptases for the multi-objective shortest path problem. Computers & Operations Research 78, p. 44–58. Cited by: §1. [3] A. Censi, K. Slutsky, T. Wongpiromsarn, D. Yershov, S. Pendleton, J. Fu, and E. Frazzoli (2019) Liability, ethics, and culture-aware behavior specification using rulebooks. In 2019 International Conference on Robotics and Automation (ICRA), Vol. , p. 8536–8542. Cited by: §1, §2.2, §2. [4] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (2022) Introduction to algorithms. 4th edition, The MIT Press. Cited by: §4.2. [5] P. M. de las Casas, A. Sedeño-Noda, and R. Borndörfer (2021) An improved multiobjective shortest path algorithm. Comput. Oper. Res. 135, p. 105424. Cited by: §2.1.1. [6] P. M. de las Casas, L. Kraus, A. Sedeño-Noda, and R. Borndörfer (2023) Targeted multiobjective dijkstra algorithm. Networks 82 (3), p. 277–298. Cited by: §2.1.1. [7] DIMACS implementation challenge: shortest paths. Note: https://w.diag.uniroma1.it/challenge9/download.shtml Cited by: §6. [8] M. Ehrgott (2005) Multicriteria optimization (2nd ed.). Springer. Cited by: §1. [9] B. Goldin and O. Salzman (2021) Approximate bi-criteria search by efficient representation of subsets of the Pareto-optimal frontier. In International Conference on Automated Planning and Scheduling (ICAPS), p. 149–158. Cited by: §1. [10] P. E. Hart, N. J. Nilsson, and B. Raphael (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics 4 (2), p. 100–107. Cited by: §2.1.1. [11] C. Hernández, W. Yeoh, J. A. Baier, H. Zhang, L. Suazo, S. Koenig, and O. Salzman (2023) Simple and efficient bi-objective search algorithms via fast dominance checks. Artificial intelligence 314, p. 103807. Cited by: §2.1.1. [12] L. Mandow and J. L. P. De La Cruz (2005) A new approach to multiobjective A* search. In International Joint Conferences on Artificial Intelligence (IJCAI), p. 218–223. Cited by: §2.1.1. [13] L. Mandow and J. L. P. De La Cruz (2010) Multiobjective A* search with consistent heuristics. Journal of the ACM 57 (5), p. 1–25. Cited by: §2.1.1. [14] H. Peer, E. Weiss, R. Alterovitz, and O. Salzman (2025) Generalizing multi-objective search via objective-aggregation functions. CoRR abs/2509.22085. Cited by: §1. [15] F. J. Pulido, L. Mandow, and J. L. Pérez-de-la-Cruz (2015) Dimensionality reduction in multiobjective shortest path search. Computers & Operations Research 64, p. 60–70. Cited by: §2.1.1. [16] Z. Ren, C. Hernández, M. Likhachev, A. Felner, S. Koenig, O. Salzman, S. Rathinam, and H. Choset (2025) EMOA*: a framework for search-based multi-objective path planning. Artificial intelligence 339, p. 104260. Cited by: §2.1.1. [17] O. Salzman, A. Felner, C. Hernández, H. Zhang, S. Chan, and S. Koenig (2023) Heuristic-search approaches for the multi-objective shortest-path problem: progress and research opportunities. In International Joint Conferences on Artificial Intelligence (IJCAI), p. 6759–6768. Cited by: §2.1.1, §2. [18] K. Slutsky, D. Yershov, T. Wongpiromsarn, and E. Frazzoli (2021) Hierarchical multiobjective shortest path problems. In Algorithmic Foundations of Robotics XIV, S. M. LaValle, M. Lin, T. Ojala, D. Shell, and J. Yu (Eds.), Cham, p. 261–276. Cited by: §1. [19] T. Wongpiromsarn, K. Slutsky, and E. Frazzoli (2026) Formal specification and control synthesis of autonomous robots using rulebooks. IEEE Trans. Robotics. Note: to appear, included in supplementary material Cited by: §1, §2.2, §2, §6. [20] H. Zhang, O. Salzman, T. S. Kumar, A. Felner, C. H. Ulloa, and S. Koenig (2022) A*pex: efficient approximate multi-objective search on graphs. In International Conference on Automated Planning and Scheduling (ICAPS), Vol. 32, p. 394–403. Cited by: §1, §2.1.2, §6.