1 Introduction↩︎

Planning for autonomous systems in complex, unstructured environments—such as high-speed off-road autonomy [1], [2] and aerial robotics [3]—is challenging due to complex, nonlinear dynamics. We are motivated by kinodynamic planning for high-speed off-road autonomous vehicles, where precomputing motion trees is often infeasible because the terrain, friction, and obstacle geometry continuously evolve [1], [4]. In many such settings, the planner has access only to a computationally expensive forward dynamics model rather than a fast analytical solution to the two-point boundary value problem (2pBVP).

For such problems, directly applying A*search in continuous kinodynamic spaces is computationally prohibitive due to the curse of dimensionality. Hybrid A*(HA*) [5] addressed this challenge by using approximate dominance [6]; discretizing the state space into grid cells, with each cell only retaining the lowest cost vertex. However, performance depends critically on discretization; Too coarse, and you may prune a vertex leading to the goal with because of its higher cost, and end up expanding a misaligned vertex. Too fine and you increase the overall computational burden. Incremental Generalized Hybrid A*(IGHA*) [2] mitigates this tradeoff by organizing search over a hierarchy of resolutions in an anytime fashion, and decoupling dominance and tree generation outside the per-resolution search process. While IGHA* does not prune locally suboptimal vertices at a resolution, it does freeze them, preventing them from being expanded at that search iteration.

A concrete illustration of this effect is shown in Fig. 1, where a vehicle must reach a goal configuration defined in \((x,y,\theta)\) using a Reeds–Shepp distance threshold. Although the search appears to pass near the goal region, it freezes a crucial vertex, preventing it from reaching a vertex satisfying the goal condition, and instead expands a misaligned vertex instead leading to far more expansions. While this example involves an orientation-constrained passage, the underlying phenomenon is more general: frozen vertices can hide solution-supporting vertices from the search; we term this the frozen vertex barrier.

In this work we show that bidirectionality fundamentally changes this behavior. We propose Bidirectional Incremental Generalized Hybrid A* (Bi-IGHA*), consisting two IGHA* searches (Forward, Backward) progressing in opposite directions, sharing information for branch-and-bound and for detecting near-meets that connect the two trees (Alg. 3). Classical bidirectional search is typically motivated by reduced effective search depth. Our key insight is that Bi-IGHA* additionally benefits from a mitigation of the frozen vertex barrier through near-meets. Bi-IGHA*preserves the core guarantees of IGHA*, including monotonic improvement of solution cost and termination. Empirical results in \(\mathbb{R}^3\), \(\mathbb{R}^4\), and \(\mathbb{R}^6\) planning problems demonstrate substantial reductions in vertex expansions. In closed-loop kinodynamic car planning for high-speed off-road autonomy, Bi-IGHA*achieves equivalent solution quality to IGHA*while requiring significantly fewer expansions.

2 Related Work↩︎

2.1 Bidirectional Graph Search↩︎

Bidirectional graph search (see, e.g., [8]–[14]) algorithms have long been employed to improve search efficiency. Recent theoretical advances in this domain have primarily followed two distinct conceptual frameworks [15], [16]. The first, grounded in the theory of Must-Expand Pairs (MEP) [17], led to algorithms like Near-Optimal Bidirectional Search (NBS) [18]. NBS introduced mechanisms to certify optimality even when the two search frontiers do not meet exactly at a vertex. The second framework focuses on the Meet-in-the-Middle Property (MMP), which guarantees that no state is expanded if its cost exceeds half the optimal solution cost [19], with recent work [16] showing ways to reduce computational burden of computing termination conditions [20], [21]. However, both MEP and MMP approaches typically assume a static graph in which vertices can be checked for exact overlap. This assumption often breaks down in kinodynamic planning for off-road autonomy

2.2 Kinodynamic Bidirectional Motion-Planning↩︎

In kinodynamic planning, unlike geometric graph search, the forward and backward trees in continuous do not share exact states. Consequently, establishing a connection requires solving a local BVP to bridge the gap between the two trees [22]. Early work on Kinodynamic Bi-RRT utilized the property of a local controllability radius(LCR) to assume that if two states are sufficiently close, they can be connected [23]. Similarly, recent sampling-based methods verify a connection between vertices using trajectory optimization [24], or exploit the reverse tree only when vertices fall within a specific radius [25]. Approaches such as idB-A* [26], [27] rely on the concept of bounded discontinuity for connecting motion primitives. At their core, they all rely on the ability to connect vertices within some LCR, either by assuming that a connection is possible or at least to filter out unpromising candidates. Our algorithm also uses the notion of LCR, but remains orthogonal to how the connection is actually verified.

2.3 Kinodynamic planning & off road autonomy↩︎

For unstructured and ever changing environments with complex dynamics, such as in the case of off-road autonomy [1], [28], precomputing motion primitives [26], [27] is often computationally infeasible [29] as the motion primitives/graph becomes invalid as soon as a new map is provided by the perception system. Algorithms like Hybrid \(A^*\) (HA*) [5] and SST[30] commit to tree search with with the system’s dynamics model, and leverage the notion of approximate dominance [6] to reduce the computational complexity of these problems, However, these approaches couple the tree discovery with the discretization resolution. While the IGHA* [2] breaks this coupling outside the inner search process, it is still susceptible to the frozen-vertex-barrier. In this work, we extend the IGHA* framework into the bidirectional setting, and show how it mitigates this issue.

3 Concise overview of IGHA*↩︎

The Incremental Generalized Hybrid A* (IGHA*) [2]  is shown in Alg. 3, and the left half of the flow chart in Fig. 2, without the portions highlighted in green. Here, the state space is discretized at some resolution \(R\) and a function \(\hat{v} : V \times \mathbb{N} \rightarrow V\) maps a vertex \(v\) to the vertex that currently dominates \(v\)’s region (in implementation, this “region” is a grid cell). When a new vertex \(v'\) enters this region, if \((v'.g < v.g)\), \(v'\) becomes the dominant vertex, otherwise \(v\) remains dominant. IGHA* can move up and down levels \(\mathbf{\ell}=[\ell_0,\ell_1,\dots \ell_N]\) of resolution corresponding resolutions \(\mathbf{R} = [R_0, R_2, \dots, R_N]\)  (we use “level” and “resolution” interchangeably). IGHA* retains non-dominant vertices generated during search but marks them as InActive (it maintains \(Q_v.\text{Active},~Q_v.\text{InActive}\) queues separately) or Frozen. Vertices in \(Q_v\) are ordered by \(f\)-value, where \(f=v.g+h(v)\), where \(v.g\) is \(v\)’s cost-to-come and \(h(v)\) is its heuristic cost-to-go.

The search is started at level 0, corresponding to \(R_0\), and \(Q_v\) is initialized with \(v_r\) (root vertex), which is then Activated. The planner enters the forward search (Line [ll:igha95search95loop95start]), expands vertices by order of priority from \(Q_v.\text{Active}\), marking the newly generated vertices as active or inactive (frozen) based on approximate dominance. The search continues until we’ve either run out of vertices to expand, the \(f\)-value of the best active vertex in \(Q_v\), (\(Q_v.\text{Active}.\mathrm{\small peek}().f\)) exceeds the best cost path \(w(\hat{\pi})\) (Branch-and-Bound) we’ve satisfied the goal check condition and generated a path (EmitPath), or Shift decides to break the search loop (Lines [ll:igha95search95loop95start],  [ll:igha95peek95active], [ll:igha95goal95check], [ll:shift95call] resp). Shift decides what the search resolution will be for the next iteration of the search (Line [ll:igha95search95loop95start]).

When the loop is broken, IGHA* removes all vertices worse than \(w(\hat{\pi})\) (Branch-and-Bound  Line [ll:igha95bound]), the vertices are projected to the new resolution (Line [ll:igha95project]), and the inner search loop (Line [ll:igha95search95loop95start]) is bootstrapped with newly Activated (Line [ll:igha95activate]) vertices. This process continues until \(Q_v=\emptyset\). We refer the reader to the original work [2] for a detailed review of the method. Importantly, IGHA* provides guarantees on monotonic cost improvement, and termination with finite number of expansions when at least one solution has been found.

4 Bidirectional IGHA*(Bi-IGHA*)↩︎

In this work, we aim to improve the efficiency of IGHA* by extending it into the bidirectional setting. Importantly, the tenets behind our design decisions are to retain the theoretical guarantees of IGHA* and to keep it as simple as possible. Throughout the text, we use Forward and Backward to refer to Bi-IGHA*’s internal searches, and forward/reverse to refer to instances of IGHA*.

4.1 Problem Statement↩︎

We consider the problem of computing near-optimal paths over two implicitly-defined trees \(T_f, T_b\) (Forward and Backward resp.), where for both trees, \(T = (V, E)\), where each edge \((u, v) \in E\) has an associated positive cost given by a function \(w : E \rightarrow \mathbb{R}^+\). \(T_f\) is rooted at a (given) start vertex \(v_s \in V_s,~V_s\subseteq V\), and the objective is to reach any vertex in a goal set \(V_g \subseteq V\) while minimizing the accumulated edge cost. The Backward search flips this process. \(T_b\) is rooted at a (given) goal vertex \(v_g \in V_g,~V_g\subseteq V\), and the objective is to reach any vertex in a start set \(V_s\) while minimizing the accumulated edge cost. The tree structures are defined implicitly by a successor function \(\mathop{\mathrm{\mathrm{\small Succ}}}\) that returns the set of valid children for any given vertex, and is reversible. With slight abuse of notation, we set \(w(\pi)\) to be the cost of a path \(\pi = \langle v_1, v_2, \ldots, v_n \rangle\). Namely, \(w(\pi):=\sum_{i=1}^{n-1} w(v_i, v_{i+1})\) and define \(w(\emptyset) = \infty\) to denote the cost of failure. We assume that obtaining a path from \(v_s\) to \(V_g\) is functionally equivalent to obtaining a path from \(v_g\) to \(V_s\). We assume access to a heuristic function \(h: V \rightarrow \mathbb{R}_{\ge 0}\) that is admissible, providing an estimate of the remaining cost to the goal for the Forward search (\(h_f\)) and to the start for the Backward search (\(h_b\)).

4.2 Challenges in making IGHA* bidirectional↩︎

While bidirectional search offers the potential of exponential speed-ups [16], [19] through the reduction of the search depth, these techniques typically assume a static graph, where vertices overlap exactly, and that the dynamics are symmetric forward and backward [31]. Once a vertex is reached, it is assumed that calling \(\mathop{\mathrm{\mathrm{\small Succ}}}\) would produce the same neighbours from both sides, and so we no longer have to continue the search through that vertex. The requirement of exact overlap is important for efficiency in finding a path, and the requirement of producing the same neighbours on both sides is important for reducing search effort after finding the best path (early termination).

We leverage the notion of a local controllability radius, standard in kinodynamic planning [22], for detecting and verifying near meets to achieve efficiency in finding a path. While various ways of detecting a near meet exist (assuming a connection is possible [22], [27], or trajectory optimization [24]), at their core, these approaches filter candidates when vertices from the opposing trees are outside some distance metric (\(R_{LCR}\)) of each other.

After this connection, we can’t assume that the neighbours from either direction for the connected vertices will be identical, as the vertices aren’t exactly the same. Thus, the techniques mentioned earlier for reducing the search effort after the connection can’t be used within our setting. As the dynamically generated (sub)-trees in IGHA* are always subject to activation and approximate dominance, the \(g\) value of the vertex is always an upper bound, not a lower bound; thus it would make for an inadmissible heuristic and can not be used in our setting.

4.3 The Bi-IGHA* Framework↩︎

The Bidirectional IGHA* (Bi-IGHA*) (Alg. 3, Fig. 2) runs two (Forward, Backward) IGHA* searches (Line [ll:biigha95forward95backward95parallel]) that share tree information for detecting near meets and the current best cost \(w(\hat{\pi})\)–this information sharing is an ever-present background process. The root vertex \(v_r \gets v_s\) and the target set \(V_T \gets V_g\) for Forward, and for the \(v_r \gets v_g\) and \(V_T \gets V_s\) for the Backward search. For simplicity, we pop vertices from the Forward and Backward\(Q_v\) symmetrically. The NearMeet (Line [ll:biigha95near95meet95check]) is a blackbox function for detecting and verifying tree connections. When a NearMeet exists between a vertex \(v \in T\) and multiple vertices \(V_\mathrm{\small NearMeet}\) in the opposing tree \(\bar{T}\), GetNearMeetVertex returns the vertex \(\bar{v}^* = \mathop{\mathrm{arg\,min}}_{\bar{v} \in V_\mathrm{\small NearMeet}} \big( v.g + \bar{v}.g + w(v,\bar{v}) \big),\) i.e., the one minimizing the Forward-Backward path cost \(\pi_{LCR}\) (Line [ll:get95near95meet95cost]). Note that the Forward and BackwardIGHA* are not level-locked; they can change levels independently. If one terminates before the other, the remainder continues running to termination, as a path may exist in one tree that does not exist in the other direction’s tree. Intuitively, Bi-IGHA* retains IGHA*’s guarantees on monotonic cost improvement and termination because near meets still ensure monotonic cost improvement (Line [ll:biigha95near95meet95monotonic95improvement]), and one IGHA* does not directly affect the other IGHA*’s Shift or Activate.

5 Formal Guarantees and Structural Analysis↩︎

We first show that Bi-IGHA* preserves the core guarantees of IGHA*. We then formalize the structural interaction between discretization and freezing that motivates bidirectionality. Throughout this section we assume:

1. The heuristics \(h_f,h_b\) never overestimate the true cost-to-go to \(V_g\), \(V_s\) resp.

2. Each vertex has at most \(b<\infty\) successors under \(\mathrm{Succ}(\cdot)\).

3. Every edge cost satisfies \(w(u,v)\ge \epsilon > 0\).

These are identical to the assumptions in [2]. From [2], the (relevant) invariants of IGHA* are:

1. Only vertices are expanded during search.

2. At least one vertex is Activated until \(Q_v=\emptyset\).

5.1 Near-Meets and Stitching↩︎

5.2 Equivalence to IGHA*↩︎

5.3 Freezing as a Structural Barrier↩︎

Obs. 1 implies that if vertex \(v\) is part of a solution path and it is frozen, then that solution path cannot be discovered at that iteration. We construct a family of planning instances for the forward search that expose this effect.

Existence of forward-backward NearMeet opportunities is typical in practice [32]. In the general configuration, with a naive rule, \(v\in Q_v\) does not contain direct information about where its successors lead. The sequence of plots in Fig. [fig:igha95anecdote953DoF950]-[fig:igha95anecdote953DoF957] shows a concrete example of this. IGHA*’s search tree passes near the goal region (Fig. [fig:igha95anecdote953DoF951]), but freezes a crucial vertex leading to the goal (Fig. [fig:igha95anecdote953DoF953]). Now, IGHA* explores all the dead-end nodes (Fig. [fig:igha95anecdote953DoF954]) before refining resolution and finally expanding the crucial vertex (Fig. [fig:igha95anecdote953DoF957]). The blowup arises from freezing, not from search depth alone.

This separation shows that the improvement of Bi-IGHA* is not solely due to reduced effective depth. Our key insight is that bidirectionality alters how goal-reachability information propagates through the incremental dominance structure, mitigating resolution-induced freezing effects; we term this phenomenon Bidirectional Mitigation. When it comes to Bi-IGHA*, even when the resolution is too coarse for IGHA* to find any path from \(v_s\) to \(V_g\) in the forward tree (Fig. 4 (a)), requiring it to go to a finer resolution (Fig. 4 (c)), Bi-IGHA* may find a path from \(v_s\) to \(v_g\) through \(\Pi_{fb}\)(Fig. 4 (b)), or from \(v_g\) to \(V_s\) in the Backward tree (Fig. 4 (d)). Importantly, while IGHA* may have to go to a very high resolution to encounter the best cost solution (Fig. 4 (e)), Bidirectional Mitigation allows at least one of the searches in Bi-IGHA* to encounter an equivalent cost solution at a lower resolution (Fig. 4 (f)). At lower resolutions, the effective branching factor of Bi-IGHA*’s Forward and Backward searches can be much lower via approximate dominance, which also contributes to the speed up. We will show empirically in Sec. 7 that this (mitigation) happens very often when there is a speed up.

6 Surprising Branching factors↩︎

We defer experimental details to Sec. 7, anecdotally illustrate the impact of Bidirectional mitigation. Across \(\mathbb{R}^3\), \(\mathbb{R}^4\), and \(\mathbb{R}^6\) systems, Fig. 6 shows that, as intuition may suggest, increasing \(R_{LCR}\) raises the likelihood of near-meets and thus the speed-up, until we examine effective branching factors.

We define the empirical effective unidirectional branching factor \(b_{\text{uni}}\) for a given run of a unidirectional search as follows: Let \(E_\text{uni}\) be the number of node expansions and \(d_\text{uni}\) be the number of nodes of the path returned. Then, \(b_{\text{uni}}\) is the solution to the following equation: \(E_\text{uni}=\sum^{n=d_\text{uni}-1}_{n=0} (b_\text{uni})^n\). Given \(b_{\text{uni}}\), we can compute \(E^\text{ideal}_\text{bi}\), the number of expected node expansion under an optimal symmetric bidirectional search. Specifically, \(E^\text{ideal}_\text{bi}:=2\sum^{n=d_\text{uni}/2-1}_{n=0}(b_\text{uni})^n\). Given \(E^\text{ideal}_\text{bi}\), we define the estimated effective bidirectional branching factor as the solution to the following equation: \(E^\text{ideal}_\text{bi}=\sum^{n=d_\text{uni}-1}_{n=0} (b^\text{ideal}_\text{bi})^n\). In a completely analogous way to the unidirectional setting, we define the empirical effective bidirectional branching factor \(b_{\text{bi}}\) for a given run of a bidirectional search as follows: Let \(E_\text{bi}\) be the number of node expansions and \(d_\text{bi}\) be the number of nodes of the path returned. Then, \(b_{\text{bi}}\) is the solution to the following equation: \(E_\text{bi}=\sum^{n=d_\text{bi}-1}_{n=0} (b_\text{bi})^n\).

Now, consider the the ratio \(B^*=\frac{b^\text{ideal}_\text{bi}}{b_\text{bi}}\). Since \(b^\text{ideal}_{\text{bi}}\) assumes an optimal symmetric bidirectional search, we expect that \(B^* \leq 1\). Surprisingly, empirical values recorded and reported in Fig. 5 demonstrate instances for which \(B^* > 1\). The reason for this phenomenon is that in the computation of \(B^*\), we implicitly assumed that both planners operate on the same search structure; this is typically true for search on a static graph, but is not the case here due mitigation of the frozen vertex barrier. Nonetheless, as Bi-IGHA* does not explicitly enforce MMP, at a first glance of Alg. 3 and flow chart Fig. 2, one would never expect this result from it. We used Fig. 5 to show that because of the bidirectional mitigation, Bi-IGHA*is a simply surprising and surprisingly simple algorithm.

7 Experiments↩︎

We evaluate Bi-IGHA* in both open and closed-loop settings, consider IGHA* as our baseline, and use 95\(\%\) confidence intervals. We count the expansions of the forward and reverse search separately. For physical dimensions, we use S.I units.

7.1 Open Loop Evaluations↩︎

We present both an ablation of Bi-IGHA* with respect to LCR and a comparison against IGHA* across three systems. First, a kinematic car [34] in \(\mathbb{R}^3\) (\((x,y,\theta)\)) on urban city maps from the Moving AI benchmark [35] (e.g., Fig. 1), with \(R_{LCR}=(1.0, 1.0, \pi/2)\). Second, a kinodynamic car [36] in \(\mathbb{R}^4\) (\((x,y,\theta,v)\)), assuming no sideslip or body-frame vertical velocity, evaluated on off-road maps taken from BeamNG [37] (e.g. Fig. 10 (d)), with \(R_{LCR}=(1.0, 1.0, \pi/2, 2.5)\). Third, a hovercraft [23] in \(\mathbb{R}^6\) (\((x,y,\theta,v_x,v_y,\dot{\theta})\)), with maps from Moving AI [35] and BeamNG [37], with \(R_{LCR}=(1.0, 1.0, \pi/2, 2.5, 2.5, \pi/2)\). In all environments, the vehicle dimensions (length, width) are \(2.6\times1.6~\text{m}^2\). Each environment contains 200 problems, with a 50k expansion limit. We evaluate two extreme hysteresis settings (\(\infty, 250\)) for IGHA* [2] and use the same values for Bi-IGHA*(both directions). To compare across \(\mathbb{R}^3/\mathbb{R}^4/\mathbb{R}^6\), we report LCR in terms of induced volume: LCR (base resolution), LCR/8 (\(1/8^\text{th}\) volume), and LCR/64 (\(1/64^\text{th}\) volume). Note that our edges are usually longer than 1.0 meter(\(\approx5\)m). Here, for simplicity, NearMeet declares \((u,v)\) feasible if \(\|u-v\|<R_{LCR}\).

Let \(n_{first}(\text{ALG})\) be the number of expansions required by an algorithm (either IGHA* or Bi-IGHA*) to obtain a solution. Here, Speedup \(:=n_{first}(\textsf{IGHA*})/n_{first}(\textsf{Bi-IGHA*})\). Let \(n_{best}(\textsf{IGHA*})\) be the number of expansions required by IGHA* to reach its best path cost within the expansion budget, and let \(n_{best}(\textsf{Bi-IGHA*})\) be the expansions required by Bi-IGHA* to reach an equivalent-or-better cost. Here, the Speedup \(:=n_{best}(\textsf{IGHA*})/n_{best}(\textsf{Bi-IGHA*})\). We additionally record the solution level (\(\text{level}_{\textsf{Bi-IGHA*}}, \text{level}_{\textsf{IGHA*}}\)) for both first and best solutions. We are interested in knowing how often bidirectional mitigation happens when there is a Speedup. Bidirectional mitigation manifests empirically as follows: when a solution is found, either Forward or Backward search operates at a level (\(\text{level}_{\textsf{Bi-IGHA*}}\)) lower than IGHA*’s (\(\text{level}_{\textsf{IGHA*}}\)). We define \(\mu_\leq:=\hat{p}(\text{level}_{\textsf{Bi-IGHA*}}\leq \text{level}_{\textsf{IGHA*}}\mid \text{Speedup}>1)\) and \(\mu_<:=\hat{p}(\text{level}_{\textsf{Bi-IGHA*}}< \text{level}_{\textsf{IGHA*}}\mid \text{Speedup}>1)\). We make the above comparisons against the best of forward and reverse IGHA*, as if an oracle informed IGHA* on whether to run forwards or backwards. Since the first solution admits any cost, we compare Bi-IGHA* against the faster of forward/backward to the first (any) solution. For the best solution, we compare the expansions taken by Bi-IGHA* with those of the forward/reverse IGHA* that achieves the lowest cost. We do this comparison to show that Bi-IGHA* is not fast just by hedging a bet in both directions. In this section, we test the following hypotheses:

1. A variant of Bi-IGHA* achieves Speedup\(>1\).

2. \(\hat{p}(\text{Speedup}>1)>0.5\).

3. \(\mu_\leq>0.5\).

4. \(\mu_< >0.5\).

Result: Fig. 6 shows that generally Speedup\(>1\) for the first and best path, often approaching an order of magnitude, confirming [hyp:speedup95meas]. Fig. 7 shows that [hyp:speedup95prob] is always true for the first path, and often true for the best path. For both of the above plots, increasing LCR increases speed up, and the speed up (or its likelihood) dips when compared to the best of forward/reverse IGHA*. Fig. 8 shows that [hyp:level95prob95lax], [hyp:level95prob95strict] are always true, and provides context on the stricter condition of \(\mu_<\). Fig. 9 shows a more conventional comparison and provides additional nuance to show that the results in Fig. 7, 6 are pessimistic.

7.2 Closed Loop Evaluations↩︎

We evaluate the planners using the \(\mathbb{R}^4\) kinodynamic car model in off-road environments. Planning runs in closed loop with MPPI [38] (1.5 s horizon, 1024 rollouts) in BeamNG [37], assuming ground-truth state and body-centric bird’s-eye-view cost and elevation maps (\(100{\times}100\,\text{m}^2\), 25 Hz). We use the same benchmarking setup as used by the authors in  [2] (30 scenarios, 4 trials) and reuse its reported results for IGHA*, along with SST [30] as a point of reference. Here, similar to  [27], NearMeet for \((u,v)\) additionally collision checks interpolated states between \(u\) and \(v\) to avoid near-meets over thin obstacles. The vehicle dimensions are \(2.6\times1.6\text{m}^2\), and the \(R_{LCR}\) for \((x,y,\theta,v)\) is \((1.0,1.0,\pi/8,1.25)\approx\text{LCR}/8\). We use the same hysteresis value of 100 as used by IGHA* in  [2], and the rate of expansions (\(\approx\)​20k/sec) on our computer matches what was reported in [2]. To bring out the difference between IGHA* and Bi-IGHA*, we operate both at 5k, 2.5k, and 1.25k expansions – we arrive at this range of expansions by looking at the success/cost plots on playback data (Fig. 10 (a), 10 (b)). When running the planner with fewer than 5k expansions, we slow down the rate of expansions to simulate a slower computer, such that the overall compute time remains identical. The hypothesis we want to test here is:

5. Bi-IGHA* achieves higher success rates than IGHA*for a given expansion budget.

Result: Fig. 10 (c) shows that while IGHA*’s mission speed (slope of the curves) is generally close to Bi-IGHA*’s, Bi-IGHA* consistently attains higher success rates under equal compute budgets, reaching comparable reliability in less time, confirming [hyp:closed95loop95succ]. Fig. 10 (d) uses an anecdote to show how IGHA*’s starvation and stalling can put the vehicle into a precarious situation, while Bi-IGHA* keeps the vehicle moving with its rapid planning.

8 Discussion↩︎

Bi-IGHA* presents a straightforward way to extend the IGHA* framework into the bidirectional setting. As it builds on top of the IGHA* framework, as long as the assumptions of IGHA* are met, Bi-IGHA* retains its guarantees of monotonic cost improvement and termination. For the sake of simplicity, our work here keeps the Forward and Backward search identical in both rate of expansions as well as the Shift and Activate methods used. However, the guarantees of Bi-IGHA* don’t rely on this.

Understandably, the actual utility of the planner depends on the reliability of the NearMeet implementation. In our work, we treat the NearMeet method as a black box, as it is not the focus of our work. However, we show that useful speed-ups are achievable with a range of LCR values, and show that the chosen values are reasonable by using the middle value (LCR/8) in our closed loop experiment, with a fairly simple collision-checked NearMeet.

Acknowledgements↩︎

This work was (partially) funded by the National Science Foundation NRI (#2132848) and CHS (#2007011), DARPA RACER (#HR0011-21-C-0171), the Office of Naval Research (#N00014-17-1-2617-P00004 and #2022-016-01 UW), Amazon, Technion Autonomous Systems Program (TASP), and the United States-Israel Binational Science Foundation (BSF) grant (#2021643).

References↩︎