# Focus on Relevant Road Users with Multi-Rules Reachable Sets

Monica Fossati, Ezio Malis, Philippe Martinet

<figure><img src="image_1.png" /></figure>

## ► To cite this version:

Monica Fossati, Ezio Malis, Philippe Martinet. Focus on Relevant Road Users with Multi-Rules Reachable Sets. IEEE IV 2026 - IEEE Intelligent Vehicles Symposium, Jun 2026, Detroit, United States. hal-05485918

HAL Id: hal-05485918

https://hal.science/hal-05485918v1

Submitted on 30 Jan 2026

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Focus on Relevant Road Users with Multi-Rules Reachable Sets

Monica Fossati, Ezio Malis and Philippe Martinet

*Abstract*—Autonomous driving in urban environments poses significant challenges due to the presence of numerous heterogeneous agents, which may or may not comply with traffic rules. Considering all agents in the scene when exploring possible future scenarios can be computationally prohibitive for decision-making approaches. To address this issue, we propose a method to selectively filter relevant agents based on multi-rules reachable sets derived from Lanelet maps and kinematic constraints, focusing only on those likely to interact with the ego vehicle within the planning horizon. Relevance is formally defined through spatio-temporal intersections between reachable sets, enabling a principled categorization of potential conflicts. To enhance the accuracy of this filtering, we introduce refined temporal and spatial discretization of the reachable sets, reducing over-approximation while preserving high computational efficiency. This combination of formal relevance filtering and precise reachability representation enables more robust and scalable autonomous vehicle decision-making in complex urban environments.

# I. INTRODUCTION

In urban traffic, autonomous vehicles face a highly dynamic and structured environment. The diversity of road users creates a vast space of possible interactions, and naively accounting for all of them leads to a combinatorial explosion of future scenarios [1], overwhelming real-time decision-making. In contrast to unstructured environments, urban trajectories are largely constrained by road topology and traffic rules, so spatial proximity alone is not a reliable indicator of relevance. Yet human behavior does not always conform to these rules, introducing uncertainties that cannot be fully captured by reasoning limited to the prescribed set of traffic rules. Ensuring safety without sacrificing efficiency therefore requires identifying which agents are truly relevant for the ego vehicle, accounting both for rule-compliant motion and for physically feasible deviations. Reachable sets offer a principled way to represent the space each agent may plausibly occupy within the planning horizon [2], enabling the system to focus only on those users that could realistically interact with the ego vehicle.

In the literature of autonomous navigation, determining which agents are relevant in a scene often relies on methods based on spatial proximity, as in [3], [4], while others use collision indicators, such as the Time-To-Collision (TTC) [5]. These simple metrics work well in unstructured or simple environments. However, in structured urban settings, traffic rules and infrastructure constrain road users' trajectories, making detailed maps essential and requiring relevance criteria that consider the road layout and traffic rules.

High-definition map standards such as Lanelet2 [6] capture this structure by representing lane topology, semantics, and routing information. The Lanelet2 framework also supports pathfinding and the computation of reachable sets under traffic rules [7]. While it provides a solid foundation for offline, rule-based reachability, it does not incorporate online kinematic information of road users. Moreover, although custom rules can be defined thanks to its modularity, the standard implementation provides only traffic rules.

Koschi et al. [8], [9] provide a strong geometric and kinematic basis for lanelet-based reachability, inspiring our spatio-temporal discretization. Their method does not anticipate rule violations: constraints are removed only when violated, and violations of map boundaries reduce the problem to free-space motion with only kinematic limits. This lack of a framework for physically feasible reachability motivated Fossati et al. [10], who, alongside conventional traffic rules, proposed a complementary set of rules based on map semantics. These rules allow the modeling of movements that remain physically possible even when traffic rules are violated, bridging the gap between kinematic feasibility and the structured constraints of the urban environment.

Philipp et al. [11] use Lanelet maps and traffic rules to identify areas where interacting road users are likely to appear and weight perception errors according to user relevance. However, focused on perception evaluation, their approach does not leverage perception-derived information such as observed kinematics, nor does it account for potential traffic rule violations.

Building on and extending previous work on multi-rules reachability [10], this paper introduces a **relevance-filtering framework** for urban driving. Unlike [10], which focused on the representation of multi-rules reachable sets, here we exploit them to support decision-making by formally assessing which road users are relevant through refined spatio-temporal reachability. The main contributions are:

* **Refined multi-rules formulation:** A spatio-temporal refinement reduces over-approximation and improves interaction detection, providing a more precise basis for relevance assessment.

* **Formal relevance filtering:** Relevance is defined through spatio-temporal intersections between refined multi-rules reachable sets, enabling a principled categorization of road users.

* **Experimental validation:** Experiments on real-world data validate the refined formulation and assess its impact on agent reduction and scenario space.

Authors are with ACENTAURI team at Centre Inria d'Université Côte d'Azur, Sophia-Antipolis, France given-name.family-name@inria.fr
## II. CONCEPTUAL FRAMEWORK

### A. Relevance of Road Users

Decision-making in urban traffic is inherently complex because of the many interacting road users. One way to make this process more tractable is to limit the number of agents explicitly considered during planning, while ensuring that no potentially safety-critical interactions are overlooked. This calls for a formal notion of relevance and clear operational criteria to identify which road users should be taken into account. Ulbrich et al. [12] provide a conceptual basis by distinguishing between a *scene*, which comprises all static and dynamic elements, and a *situation*, which includes only the subset of elements that matter for the ego vehicle. An element is deemed *relevant* if it has the potential to affect the ego vehicle’s decisions within the current context.

Building on this concept, we define a *relevant road user* as any dynamic actor capable of affecting, or being affected by, the ego vehicle. Operationally, relevance can be assessed using *reachable sets* [10], which capture all positions a road user could plausibly occupy within a given time horizon.

Formally, let $R_i(t)$ denote the reachable set of road user $i$ over a horizon $t \in [0, T]$. A road user $j$ is considered relevant for the ego vehicle if

$$ \exists t \in [0, T] : R_{\text{ego}}(t) \cap R_j(t) \neq \emptyset \quad (1) $$

In other words, relevance is determined by the potential for interaction: if the reachable sets of the ego vehicle and another road user overlap, a potential interaction exists.

This view is consistent with Markkula et al. [13], who define interaction as two road users potentially attempting to occupy the same spatial region simultaneously.

### B. Relevance Beyond Traffic Rules

Since relevance is determined by intersections between reachable sets, the next step is to define how these sets should be computed in practice. A suitable foundation for this task is the formulation of Koschi et al. [9], which combines traffic rules with kinematic constraints within the Lanelet2 map framework. This approach, which also considers occlusions, represents one of the most mature and geometrically precise methods currently available. However, it implicitly assumes that all road users strictly comply with traffic rules, addressing violations only reactively by removing the corresponding constraint once they occur. In urban traffic, this assumption is often too restrictive for identifying relevant road users. Human road users frequently adapt their motion to the context rather than strictly adhering to prescribed rules, and focusing solely on legally expected interactions can overlook safety-critical or cooperative situations. For example, a child running toward the road requires anticipation well before crossing the lane. Under a reactive violation-handling approach [9], the child would become relevant only after stepping onto the road, leaving insufficient time to react safely. Similar issues arise when pedestrians or cyclists temporarily enter the roadway to bypass obstacles, or when vehicles partially

invade restricted areas to prevent deadlocks. In such cases, the ego vehicle must identify likely rule-violating scenarios early to enable safe and proactive behavior. To overcome these limitations, the multi-rules reachable set [10] was introduced, combining legal and physical reachability to account for both compliant and plausible non-compliant movements. In the following subsection, we extend this concept to formally determine road user relevance, distinguishing between legally and physically relevant agents and establishing the foundation for the proposed filtering method.

### C. Multi-Rules Reachability for Relevance

Multi-rules reachability [10] introduces two reachable sets for each road user:

* **Legal reachable set $R_{\text{legal}}$**: the space attainable while fully complying with traffic rules.

* **Physically feasible reachable set $R_{\text{phys}}$**: the space attainable under the road user’s kinematic and dynamic constraints, potentially violating traffic rules.

These two sets can be compared with the ego vehicle’s reachable set $R_{\text{ego}}$ to define different types of relevance for surrounding road users:

* **Legally relevant road users**: These are road users whose legal reachable set overlaps with the ego vehicle’s reachable set, indicating potential interactions under full rule compliance.

* **Physically relevant road users**: These are road users whose physically feasible reachable set overlaps with the ego vehicle’s reachable set. These users may interact with the ego vehicle through physically feasible maneuvers that may violate the traffic rules.

This distinction allows the ego vehicle to prioritize legally relevant interactions while still accounting for potential risks posed by physically relevant road users.

<figure><img src="image_3.png" /><figcaption>Fig. 1: Illustrative example of a reduction from *scene* to *situation* [12]. The road users are classified according to their relevance for the ego vehicle.</figcaption></figure>

Figure 1 illustrates an urban scenario where the ego vehicle intends to go straight. In this context, the motorcyclist is *legally relevant*, as an interaction with the ego vehicle is possible while complying with traffic rules, whereas the cyclist is *physically relevant*, since he could enter the roadway from the sidewalk despite being expected to remain on it. Other
<figure><img src="image_4.png" /><figcaption>Fig. 2: Example of the reachable set discretization process for the interval $[t_1, t_2]$. Starting from the multi-rules reachability output (left), the reachable set is discretized into map-constrained and free-space components (middle). This procedure is applied separately to the legal (green) and physical (blue) reachable sets, yielding the corresponding discretized reachability representations (right). In this example, the cyclist is legally allowed to remain only in the current lane, while the adjacent lanes are physically reachable.</figcaption></figure>

participants are not relevant: the pedestrian crossing the road does not intersect the ego vehicle's planned trajectory and would become relevant only if the ego intended to turn, while the woman with the dog, although the closest to the ego vehicle, cannot interact due to the presence of a fence.

Multi-rules reachable sets were proposed as a conceptual basis for assessing road users' relevance, offering a more comprehensive perspective than legal reachability alone [10]. However, the previous implementation did not include a formal filtering method for relevant users, and the discretization adopted results in a significant over-approximation of the reachable space that can lead to false positives in interaction detection.

Based on this theoretical foundation, the next section introduces our proposed method, which reduces the over-approximation of multi-rules reachability through spatio-temporal discretization and efficiently filters relevant road users in urban traffic scenarios.

### III. PROPOSED APPROACH

#### A. Reachable Sets Discretization

Building on the multi-rules reachability formulation introduced in Sec. II-C, we refine the reachable set representation to obtain a more precise estimate of potential interactions. Previous approaches [10] evaluated reachability over entire lanelets and the full horizon $[0, T] (T = 3 \text{ s})$, which can often lead to false positives: two agents might appear to interact simply because they share a map primitive, even if they reach it at different times or positions. To this end, we build on the discretization concepts introduced by Althoff and Magdici [2], adapting them to the multi-rules reachability formulation.

We apply a two-dimensional discretization:

* **Temporal discretization:** subdivides the horizon into smaller intervals, aligning interaction checks in time.

* **Spatial discretization:** restricts reachable sets to specific lanelet segments and areas that can be occupied within each interval.

Two complementary models are combined:

1. **Map-constrained reachability:** motion restricted along precomputed paths from the routing graph.

2. **Free-space reachability:** dynamically feasible 2D motion without map constraints.

Figure 2 provides a concrete example to help visualize the discretization process.

The following procedure is applied to both legal and physical reachable sets.

**Longitudinal Reachable Distances.** The prediction horizon $[0, T]$ is partitioned into $N$ intervals of duration $\Delta t$. Each interval is denoted by $[t_k, t_{k+1}]$, where $t_k = k\Delta t$ and $t_{k+1} = (k+1)\Delta t$, with $k \in \{0, 1, \dots, N-1\}$.

For each interval, we compute the maximum and minimum distances the agent can reach longitudinally, based on its current state $(v_0, a_0)$ and kinematic constraints: longitudinal acceleration $(a_{\min}, a_{\max})$, velocity $(0, v_{\max})$, and jerk $(j_\uparrow, j_\downarrow)$.

The **maximum reachable distance** at the end of the interval $t_{k+1}$ is obtained by sequentially applying admissible motion phases:

$$s_{\max}(t_{k+1}) = s_{j_{\uparrow}} + s_a + s_v, \quad (2)$$

where each term denotes the distance covered in a specific phase:

* $s_{j_\uparrow}$: phase with positive jerk $j_\uparrow$ until $a_{\max}$ or $v_{\max}$ is reached,

* $s_a$: constant-acceleration phase until velocity saturation,

* $s_v$: constant-velocity phase until the end of the interval.

The **minimum reachable distance** at the start of the interval $t_k$ is:

$$s_{\min}(t_k) = s_{j_{\downarrow}} + s_d, \quad (3)$$

with:
* $s_{j_↓}$: phase with negative jerk $j_↓$ until $a_{min}$ or $v = 0$,

* $s_d$: constant-deceleration phase at $a_{min}$ until stop.

Each phase is applied only while its constraint is active; some phases may be absent depending on the initial state.

**Reachability Constrained by Map Topology.** The multi-rules formulation provides a set of reachable primitives within the prediction horizon, along with the corresponding entry cost $c_e$, which is defined as the cumulative distance required to reach the entry of the lanelet along the shortest path from the agent's initial position. For each interval $[t_k, t_{k+1}]$, we then select the portions of the lanelets that are reachable within that interval.

Consider a generic lanelet of length $L$, with a local longitudinal coordinate $\xi \in [0, L]$ (where $\xi = 0$ at the lanelet entry). The global longitudinal coordinate corresponding to a local coordinate $\xi$ is $s(\xi) = c_e + \xi$.

Map-constrained reachability is then defined as the set of points along the lanelet whose global distance lies within the physically reachable interval:

$$ \Xi_{\text{reach}} = \{ \xi \in [0, L] \mid s(\xi) \le s_{\text{max}}(t_{k+1}) \} \quad (4) $$

If $\Xi_{\text{reach}} = \emptyset$, the lanelet is not reachable within the interval. Otherwise, the reachable portion of the lanelet is obtained by trimming its left and right boundaries according to the longitudinal limits defined by $\Xi_{\text{reach}}$, resulting in a new lanelet that represents the accessible subset.

This construction ensures that reachability remains consistent with the underlying map topology. Since areas lack a defined orientation or traversal direction, they cannot be discretized in the same way as lanelets. Instead, they are treated as a single unit and retained if their entry cost does not exceed $s_{\text{max}}(t_{k+1})$.

**Reachability in Free Space.** For each interval $[t_k, t_{k+1}]$, we construct an *occupancy polygon* following [2], using a time-dependent bound on planar acceleration:

$$ a_p(t_k) = a_{p,0}(k^{-\beta}), \quad (5) $$

where $a_{p,0}$ and $\beta$ are class-dependent parameters fitted from data [14]. This trend reflects the empirically observed reduction in average planar acceleration as the prediction horizon increases. In other words, agents tend to sustain lower accelerations over longer time intervals. Importantly, $a_p$ is distinct from the longitudinal acceleration limit $a_{\text{max}}$: it bounds the maximum achievable acceleration in any planar direction, rather than along a single axis.

The resulting polygon is cropped longitudinally by $s_{\text{min}}(t_k)$ and $s_{\text{max}}(t_{k+1})$, and laterally to enforce velocity limits, ensuring constant-speed motion once the maximum speed is reached.

The final reachable set for each interval $[t_k, t_{k+1}]$ is obtained as the intersection of the map-constrained and free-space reachabilities:

$$ \mathcal{R}([t_k, t_{k+1}]) = \mathcal{R}_{\text{free}}([t_k, t_{k+1}]) \cap \mathcal{R}_{\text{map}}([t_k, t_{k+1}]) \quad (6) $$

yielding a unified spatio-temporal representation that is both dynamically feasible and consistent with the road network, suitable for subsequent interaction estimation.

## B. Ego Vehicle's Reachable Set

Since the ego vehicle is under full control, we require it to strictly comply with traffic regulations, with its destination being known. Therefore, its reachable set must be both legal and goal-oriented.

To construct the ego vehicle's reachable set $\mathcal{R}_{\text{ego}}$, we begin by considering its legal reachable set [10], defined as the set of lanelets the vehicle can legally access based on traffic rules within the time horizon. Next, we limit the reachable set to the lanelets that are part of the ego vehicle's route [7] to its destination, excluding those that do not contribute to reaching the goal. Now, the discretization method presented in the previous subsection can be applied to the obtained reachable set.

In exceptional cases, such as the need to avoid an obstacle or resolve a deadlock, the ego vehicle's reachable set may be extended to include its physically feasible reachable set, allowing for alternative paths that could involve non-compliant maneuvers. While the framework naturally supports such an extension, determining the conditions under which it should be applied are beyond the scope of this paper.

## C. Relevance Filter

The multi-rules reachable sets form the basis of our relevance filter, which leverages this information to identify potential interactions between the ego vehicle and other road users. The general structure of the filter is illustrated in Figure 3.

To determine whether a road user is relevant, we check for potential interactions between the ego vehicle and each road user. The operational procedure is based on evaluating overlaps of reachable sets and can be described in two stages:

1) **Coarse selection:** discard road users whose reachable sets do not overlap with the ego vehicle over the full prediction horizon $T$:

$$ \mathcal{R}_{\text{ego}}([0, T]) \cap \mathcal{R}_i([0, T]) = \emptyset \quad (7) $$

2) **Temporal refinement:** for the remaining road users, discretize the horizon into intervals $[t_k, t_{k+1}]$ and retain only those whose reachable sets overlap in at least one interval:

$$ \exists k: \mathcal{R}_{\text{ego}}([t_k, t_{k+1}]) \cap \mathcal{R}_i([t_k, t_{k+1}]) \neq \emptyset \quad (8) $$

This two-stage mechanism defines how potential interactions are detected. In our approach, it is applied separately to the two types of reachable sets defined by the multi-rules framework:

* **Legally relevant road users:** road users whose $\mathcal{R}_{\text{legal},j}(t)$ overlaps with $\mathcal{R}_{\text{ego}}(t)$. These represent interactions that can occur under standard traffic rules. Formally,

$$ \exists t \in [0, T] : \mathcal{R}_{\text{ego}}(t) \cap \mathcal{R}_{\text{legal},j}(t) \neq \emptyset \quad (9) $$
<figure><img src="image_5.png" /><figcaption>Fig. 3: Relevance filter overview</figcaption></figure>

* Physically relevant road users: road users whose $R_{phys,j}(t)$ overlaps with $R_{ego}(t)$ but are not legally relevant. These should be monitored to anticipate high-risk interactions, such as potential violations or emergency maneuvers. Formally,

$$ \exists t \in [0, T]: \begin{cases} R_{ego}(t) \cap R_{phys,j}(t) \neq \emptyset \\ R_{ego}(t) \cap R_{legal,j}(t) = \emptyset \end{cases} \quad (10) $$

This distinction allows the ego vehicle to focus primarily on legally compliant interactions while still monitoring physically feasible but potentially non-compliant maneuvers that may require proactive anticipation.

## D. Impact on Decision-Making

Decision-making methods such as stochastic Model Predictive Control (MPC) [15] and Monte Carlo Tree Search (MCTS) [16] explore multiple future scenarios to identify optimal actions. In urban settings, the number of such scenarios grows combinatorially with the number of agents and the prediction horizon, quickly becoming intractable.

Let $N$ be the number of relevant participants (excluding the ego vehicle), $M_i$ the number of possible trajectories per step for participant $i$, $T$ the prediction horizon, and $A_{ego}$ the number of ego actions per step. The total number of combinations is

$$ \#\text{Scenarios} = \left( A_{\text{ego}} \cdot \prod_{i=1}^{N} M_i \right)^T \approx (A_{\text{ego}} \cdot M^N)^T, \quad (11) $$

assuming $M_i \approx M$ for all participants.

Even small increases in $N$ or $T$ cause exponential growth of the scenario space. The relevance filter in Section III-C reduces $N$, thereby lowering the branching factor in MCTS and the sampling burden in stochastic MPC. This significantly improves tractability while preserving coverage of likely outcomes.

# IV. EXPERIMENTAL RESULTS

## A. Dataset and Preprocessing

The proposed method has been evaluated on the rounD dataset [14], an open-source collection of real-world traffic

recordings at three roundabouts in Germany. This dataset was chosen because it provides a highly structured driving environment featuring interactive scenarios with diverse participant types, including vehicles, pedestrians, and cyclists, while also capturing behaviors where some agents do not strictly follow typical traffic rules, making it a meaningful and challenging benchmark for evaluating our framework.

The Lanelet2 maps provided with the dataset were refined to improve connectivity and better represent pedestrian areas. In particular, missing connections were added, sidewalks were discretized with finer resolution, and semantic inconsistencies between map tags and those expected by the rules were corrected. In this work, we assume the availability of an accurate and up-to-date semantic map; how such a map is obtained, verified, and maintained is outside the scope of this paper and represents an interesting direction for future research.

Trajectory data were preprocessed to ensure quality:

* Removed trajectories outside mapped areas.

* Eliminated clear measurement errors (e.g., vehicles spinning in place).

* Verified and, when necessary, corrected map primitive matches (lanelets or areas) extracted using the probabilistic matching provided by Lanelet2 [7], improving consistency with observed trajectories.

This preprocessing reduces errors from data and matching inconsistencies, ensuring the trajectory data is as accurate and aligned with the map as possible.

## B. Reachable Set Validation

To validate the reachable set computation, bounds on longitudinal acceleration, jerk, and maximum planar acceleration $a_p$ were assigned to each road user category from rounD measurements using a conservative percentile-based procedure. Specifically, limits were defined as high-percentile statistics of the empirical distributions, yielding conservative bounds while remaining robust to rare instantaneous extreme values. Velocity limits were set following [10]. We adopt a prediction horizon of $T = 3$ s, consistent with prior reachability-based prediction works [2], [9], [10].
Road users that remained stationary for more than two minutes were excluded from this analysis, since static agents do not contribute meaningful information to the assessment of reachable motion.

To ensure full coverage of observed trajectories on real-world data, a fixed *robustness offset* of ±1 m was applied to the reachable distance in all methods. This margin compensates for small systematic discrepancies arising from several sources: (i) minor violations of kinematic limits occasionally observed in real traffic (e.g., short rollbacks of heavy vehicles); (ii) geometric approximations introduced by map representation and lane segmentation; (iii) small offsets due to internal processing steps such as projection to the nearest linestring point; and (iv) residual localization and sensor noise. Although applied uniformly for fairness, our method is the most sensitive to its removal, as it enforces stricter physical and kinematic constraints, leading to up to a 1% loss in physical coverage. In contrast, the other methods are less affected due to their coarser overapproximation.

<table><caption>TABLE I: Comparison of *average* predicted reachable sets over a [0, 3] s horizon. For each map, the table reports the mean area of the legal and physical reachable sets (in m²) and the mean percentage of observed future trajectory points contained within each set.</caption><thead><tr><th>Method</th><th>Map</th><th>Legal [m²]</th><th>Physical [m²]</th></tr></thead><tbody><tr><td rowspan="3">[7]</td><td>Kackertstrasse</td><td>416.0 (96.2%)</td><td>-</td></tr><tr><td>Thiergarten</td><td>307.4 (97.5%)</td><td>-</td></tr><tr><td>Neuweiler</td><td>556.6 (98.9%)</td><td>-</td></tr><tr><td rowspan="3">[10]</td><td>Kackertstrasse</td><td>408.2 (96.6%)</td><td>1252.5 (≈ 100%)</td></tr><tr><td>Thiergarten</td><td>297.9 (98.3%)</td><td>1037.2 (≈ 100%)</td></tr><tr><td>Neuweiler</td><td>519.0 (99.8%)</td><td>1063.5 (≈ 100%)</td></tr><tr><td rowspan="3">Our</td><td>Kackertstrasse</td><td>326.0 (96.6%)</td><td>798.3 (≈ 100%)</td></tr><tr><td>Thiergarten</td><td>243.4 (98.3%)</td><td>707.3 (≈ 100%)</td></tr><tr><td>Neuweiler</td><td>447.6 (99.8%)</td><td>699.5 (≈ 100%)</td></tr></tbody></table>

The results in Tab. I show that the baseline approach [7], which estimates reachability based on the starting lanelet and maximum allowed speed, largely overestimates the reachable space while still failing to cover all observed future trajectories. The multi-rules method [10] improves upon this baseline by incorporating both the vehicle's kinematics and its longitudinal position along the lanelet. Under the same traffic-rule constraints, it achieves higher coverage—i.e., a larger fraction of observed trajectory points contained within the predicted reachable set. However, solely relying on legal reachability does not fully cover all trajectories, with about 2-4% still remaining outside the predicted region. The inclusion of physical reachability, which also accounts for dynamically feasible but not strictly rule-compliant behaviors, ensures near-total coverage, with errors below 0.02%. By restricting the analysis to portions of lanelets or areas that are truly reachable, the proposed method reduces the overall reachable area; in particular, the physically reachable subset decreases by about 34% on average compared to [10], achieving higher spatial precision without loss of coverage.

In the following, we analyze how introducing temporal discretization further affects the reachable set estimation.

Temporal discretization further refines the reachable set by introducing a sequence of discrete time steps. Without discretization, the reachable set over the interval [0, 3] s represents all positions that could be reached at any point within the interval, but it does not indicate when each state is actually reachable.

<figure><img src="image_6.png" /><figcaption>Fig. 4: Evolution of the physical reachable area for different temporal discretizations $\Delta t$. Legal reachable area follows a similar trend</figcaption></figure>

Figure 4 illustrates how temporal discretization influences the temporal evolution of the physically reachable area. At the beginning of the horizon, the reachable region is smaller for finer discretizations, reflecting a more accurate representation of short-term motion constraints: with limited time available, agents can cover only a small portion of space, resulting in tighter, more localized sets. Toward the end of the horizon, the total reachable area also decreases as $\Delta t$ becomes smaller. This effect is consistent with the enforcement of realistic braking dynamics—given a nonzero initial velocity, an agent cannot remain at the same position after a few seconds even under maximum deceleration.

Introducing temporal discretization reveals a minor source of error related to the alignment between predicted and observed motion over time. Since the reachable space is evaluated at discrete temporal intervals, some trajectory points may appear in neighboring intervals—spatially correct but slightly shifted in time. Across all discretization levels, however, this temporal misalignment remains negligible: even at the finest step ($\Delta t = 0.1$ s), the average per-map error stays below 0.03%. Both the *legal* and *physical* reachable sets exhibit the same level of robustness, confirming the consistency and stability of the proposed formulation.

### C. Computation Time per Reachable Set

All experiments were performed on a workstation equipped with an Intel Core i9 CPU (13th Gen, 3.0 GHz base frequency, up to 5.4 GHz turbo) and 64 GB of RAM, running Ubuntu 20.04 LTS (64-bit). Initialization of the reachable set computer required on average around 1-2 s, which does not affect per-agent runtime. Table II summarizes the per-agent computation times under different levels of discretization. As expected, runtime increases with finer discretization, but remains in the low-millisecond range per agent, demonstrating that the
approach is efficient and suitable for real-time or near-real-time applications.

<table><caption>TABLE II: Average per-agent runtime for reachable set computation under different discretization configurations (areas enabled). Values are in milliseconds.</caption><thead><tr><th>Discretization</th><th>Legal [ms]</th><th>Physical [ms]</th></tr></thead><tbody><tr><td>[7]</td><td>0.046</td><td>-</td></tr><tr><td>[10]</td><td>0.049</td><td>0.016</td></tr><tr><td>Our (Δt = 3 s)</td><td>0.167</td><td>0.169</td></tr><tr><td>Our (Δt = 1 s)</td><td>0.246</td><td>0.322</td></tr><tr><td>Our (Δt = 0.5 s)</td><td>0.365</td><td>0.552</td></tr><tr><td>Our (Δt = 0.25 s)</td><td>0.584</td><td>1.025</td></tr><tr><td>Our (Δt = 0.1 s)</td><td>1.212</td><td>2.482</td></tr></tbody></table>

## D. Filtering Statistics

After validating the accuracy of the reachable set predictions, the sets are expanded by the corresponding footprint to account for agent size and used to identify potential interactions between the ego vehicle and surrounding road users. Traffic-compliant cars are selected from the rounD dataset [14] as ego surrogates. Their reachable sets are constructed to be legal and goal-oriented, assuming that the ego vehicle knows its goal (approximated by the last lanelet reached) and respects traffic rules. Each surrounding road user's multi-rules reachable sets are then compared with the ego vehicle's reachable sets to assess interaction relevance. Based on this comparison, road users are categorized as legally relevant, physically relevant, or non-relevant. A discretization step of Δt = 0.5 s is adopted for this analysis as it represents a good trade-off between computational cost and temporal precision, consistent with prior work [2]. The chosen step provides sufficient temporal resolution for capturing short-term interactions while maintaining real-time feasibility of the filtering process.

<table><caption>TABLE III: Distribution of road users by relevance category in the rounD dataset.</caption><thead><tr><th>Category</th><th>Number of road users</th><th>Percentage [%]</th></tr></thead><tbody><tr><td>Total participants</td><td>9.22 ± 3.45</td><td>100</td></tr><tr><td>Legally relevant</td><td>3.43 ± 2.09</td><td>38.70 ± 22.04</td></tr><tr><td>Physically relevant</td><td>0.89 ± 1.01</td><td>9.68 ± 11.43</td></tr><tr><td>Non-relevant</td><td>4.90 ± 4.16</td><td>51.63 ± 23.43</td></tr></tbody></table>

Table III summarizes the distribution of road users across categories, with percentages calculated relative to the total number of users per scene. The table reports the mean and standard deviation across all scenes. The results show that more than half of the surrounding road users can be excluded, leaving only a small subset relevant for decision-making. This reduction significantly eases the computational load for downstream planning modules.

Regarding computation times, Fig. 5 reports the overall runtime of the system per simulation step as a function of the number of surrounding agents. The computation time initially increases almost linearly with the number of surrounding agents but tends to plateau beyond approximately 20 participants. This behavior reflects the two-stage structure of the filter: most of the computational cost arises when potential interactions are detected, while agents discarded by

<figure><img src="image_7.png" /><figcaption>Fig. 5: Average computation time vs. number of other road users. The filtering procedure scales efficiently even in crowded scenes.</figcaption></figure>

the coarse selection step contribute only marginally. In denser scenes, the average vehicle speed tends to be lower and the reachable space smaller, which reduces the number of effective interactions and naturally curbs further growth in runtime. As a result, the overall processing time remains well within real-time constraints even in crowded urban configurations.

For qualitative insight, Figure 6 presents example scenes where road users are color-coded by their relevance category, illustrating typical interaction configurations.

<figure><img src="image_8.png" /><figcaption>Fig. 6: Example of road users categorization by relevance.</figcaption></figure>

## E. Scenario Space Reduction

The quantitative impact of relevance filtering on planning complexity can be evaluated by applying the formulation in Eq. (11) to representative experimental conditions. As discussed in Section III-D, the number of scenarios explored by sampling- or optimization-based planners grows exponentially with the number of agents $N$, making exhaustive evaluation quickly infeasible.
Consider a representative urban scene consistent with the average statistics in Table III, comprising nine surrounding road users in total. On average, approximately three are legally relevant and one is physically relevant, corresponding to typical values observed in the dataset. For a prediction horizon of six steps (0–3 s) with $\Delta t = 0.5$ s, five ego actions per step, and three predicted trajectories per other agent, the total number of possible scenarios without filtering is

$$ \#\text{Scenarios}_{\text{all}} = (5 \cdot 3^9)^6 \approx 10^{30}. $$

After applying the proposed relevance filtering, and conservatively including both legally and physically relevant agents in the decision set ($N = 4$), the number of possible scenarios becomes

$$ \#\text{Scenarios}_{\text{filtered}} = (5 \cdot 3^4)^6 \approx 10^{16}, $$

corresponding to a reduction of about **14 orders of magnitude** compared to the unfiltered case.

This substantial reduction confirms that the proposed relevance formulation effectively limits the decision space while keeping all potentially interacting agents within scope. Including all physically relevant users when evaluating planning complexity remains a conservative assumption, yet the introduced distinction between legal and physical relevance provides the foundation for future context-aware risk analysis.

## V. CONCLUSIONS

In this paper, we presented a relevance filtering framework for autonomous driving based on multi-rules reachable sets with refined spatio-temporal discretization. By distinguishing between legally and physically feasible interactions, the approach formally identifies which agents are critical for potential interactions with the ego vehicle, including those that may plausibly violate traffic rules. Experimental results on the roundD dataset showed that the proposed discretization substantially reduces over-approximation while maintaining full coverage of reachable states, and that the relevance filter significantly decreases the number of agents considered by decision-making algorithms. This reduction leads to a dramatic shrinkage of the scenario space, improving the tractability of planning methods such as stochastic MPC and MCTS in urban environments.

Future research will explore incorporating richer contextual information to enhance the identification of high-risk agents among those deemed physically relevant. By leveraging additional environmental cues and situational reasoning, the goal is to anticipate potentially unsafe interactions more accurately, further improving the efficiency and safety of decision-making in complex urban scenarios. Finally, end-to-end experiments integrating the proposed filter within a complete decision-making stack will be needed to quantify its impact on system-level metrics such as safety and planner performance.

## ACKNOWLEDGMENT

This research is part of the ANNAPOLIS project (https://project.inria.fr/annapolis/), funded by the French National Research Agency (ANR-21-CE22-0014).

## REFERENCES

[1] R. E. Bellman, *Adaptive Control Processes*. Princeton: Princeton University Press, 1961. [Online]. Available: https://doi.org/10.1515/9781400874668

[2] M. Althoff and S. Magdici, “Set-based prediction of traffic participants on arbitrary road networks,” *IEEE Transactions on Intelligent Vehicles*, vol. 1, no. 2, pp. 187–202, 2016.

[3] Z. Huang, C. Tang, C. Lv, M. Tomizuka, and W. Zhan, “Learning online belief prediction for efficient pomdp planning in autonomous driving,” *IEEE Robotics and Automation Letters*, vol. PP, pp. 1–8, 08 2024.

[4] E. Fiasché, P. Martinet, and E. Malis, “Towards autonomous robot navigation in human populated environments using an universal sfm and parametrized mpc,” in *IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)*, 2023, pp. 7422–7427.

[5] A. Laureshyn, Å. Svensson, and C. Hydén, “Evaluation of traffic safety, based on micro-level behavioural data: Theoretical framework and first implementation,” *Accident Analysis & Prevention*, vol. 42, no. 6, pp. 1637–1646, 2010.

[6] F. Poggenhans, J.-H. Pauls, J. Janosovits, S. Orf, M. Naumann, F. Kuhnt, and M. Mayr, “Lanelet2: A high-definition map framework for the future of automated driving,” in *IEEE International Conference on Intelligent Transportation Systems*, 2018, pp. 1672–1679.

[7] F. Poggenhans and J. Janosovits, “Pathfinding and routing for automated driving in the lanelet2 map framework,” in *IEEE International Conference on Intelligent Transportation Systems*, 2020, pp. 1–7.

[8] M. Koschi and M. Althoff, “Spot: A tool for set-based prediction of traffic participants,” *IEEE Intelligent Vehicles Symposium*, pp. 1686–1693, 2017.

[9] M. Koschi and M. Althoff, “Set-based prediction of traffic participants considering occlusions and traffic rules,” in *IEEE Transactions on Intelligent Vehicles*, vol. 6, no. 2, 2021, pp. 249–265.

[10] M. Fossati, E. Malis, and P. Martinet, “Multi-rules reachability analysis for road agents using graph-based maps and real-time kinematics,” in *IEEE Intelligent Vehicles Symposium*, 2025.

[11] R. Philipp, J. Rehbein, F. Grün, L. Hartjen, Z. Zhu, F. Schuldt, and F. Howar, “Systematization of relevant road users for the evaluation of autonomous vehicle perception,” in *IEEE International Systems Conference (SysCon)*, 2022, pp. 1–8.

[12] S. Ulbrich, T. Menzel, A. Reschka, F. Schuldt, and M. Maurer, “Defining and substantiating the terms scene, situation, and scenario for automated driving,” in *IEEE International Conference on Intelligent Transportation Systems*, 2015, pp. 982–988.

[13] G. Markkula, R. Madigan, D. Nathanael, E. Portouli, Y. M. Lee, A. Dietrich, J. Billington, A. Schieben, and N. Merat, “Defining interactions: a conceptual framework for understanding interactive behaviour in human and automated road traffic,” *Theoretical Issues in Ergonomics Science*, vol. 21, pp. 728–752, 2020. [Online]. Available: https://api.semanticscholar.org/CorpusID:216159030

[14] R. Krajewski, T. Moers, J. Bock, L. Vater, and L. Eckstein, “The round dataset: A drone dataset of road user trajectories at roundabouts in Germany,” in *IEEE International Conference on Intelligent Transportation Systems*, 2020, pp. 1–6.

[15] A. Mesbah, “Stochastic model predictive control: An overview and perspectives for future research,” *IEEE Control Systems Magazine*, vol. 36, no. 6, pp. 30–44, 2016.

[16] M. Świechowski, K. Godlewski, B. Sawicki, and J. Mańdziuk, “Monte carlo tree search: a review of recent modifications and applications,” *Artificial Intelligence Review*, vol. 56, 07 2022.