Research map / Architectures and efficiency / Neural architecture search
Resource Constrained Pathfinding with Enhanced Bidirectional A* Search
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes RCEBDA*, an enhanced bidirectional A* algorithm for resource constrained shortest path with improved initialization, dominance pruning, and path matching, reporting large speed-ups over RCBDA* and ERCA* on road networks.
Problem
Resource constrained shortest path (RCSP): find a cost-optimal start-goal path whose resource consumption stays within given limits, which is NP-hard and slow on large networks.
Approach
Extends perimeter-based bidirectional A* (RCBDA*) with resource-based network reduction during heuristic initialization, truncated-vector dominance checks exploiting f1 ordering with lazy dominance checking at extraction, and a two-stage path matching that keeps non-dominated node pairs.
Key results
- RCEBDA* solves 100/100 instances on all three maps in both scenarios, while RCBDA* solves 79-100 and ERCA* 73-97.
- Average runtime on COL with three resources: RCEBDA* 76.70 s vs RCBDA* 851.59 s and ERCA* 1094.83 s.
- Speed-ups over RCBDA* reported as above two orders of magnitude on the more challenging instances.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RCEBDA* instead of RCBDA* | RCSP search on NY, k=3 · NY, k=3 | average runtime (seconds): 153.76 vs 1.82 | Helped |
| Use RCEBDA* instead of RCBDA* | RCSP search on BAY, k=3 · BAY, k=3 | average runtime (seconds): 67.82 vs 3.12 | Helped |
| Use RCEBDA* instead of RCBDA* | RCSP search on COL, k=3 · COL, k=3 | solved cases (out of 100): 90 vs 100 | Helped |
| Use RCEBDA* instead of RCBDA* | RCSP search on COL, k=3 · COL, k=3 | average runtime (seconds): 541.77 vs 15.57 | Helped |
| Use RCEBDA* instead of RCBDA* | RCSP search on NY, k=4 · NY, k=4 | solved cases (out of 100): 94 vs 100 | Helped |
| Use RCEBDA* instead of RCBDA* | RCSP search on NY, k=4 · NY, k=4 | average runtime (seconds): 368.90 vs 7.30 | Helped |
| Use RCEBDA* instead of RCBDA* | RCSP search on BAY, k=4 · BAY, k=4 | average runtime (seconds): 335.70 vs 11.68 | Helped |
| Use RCEBDA* instead of RCBDA* | RCSP search on COL, k=4 · COL, k=4 | solved cases (out of 100): 80 vs 100 | Helped |
| Use RCEBDA* instead of RCBDA* | RCSP search on COL, k=4 · COL, k=4 | average runtime (seconds): 851.59 vs 76.70 | Helped |
| Disable state upper-bound pruning during initialization (ablation) | RCEBDA* · k=4, especially tightness 10% and 30% | runtime slowdown: average slowdown exceeding a factor of two | Hurt |
Surprising findings
- The improved RCBDA* consistently outperformed ERCA* in solved cases and average runtime on all maps.
- Disabling state upper-bound pruning in initialization leads to an average slowdown above 2x at tight constraints.
Limitations
- Evaluated only on three road-network maps with 20 start-goal pairs.
- Relies on a fixed critical resource (last attribute) for perimeter splitting.
Experimental setup
Datasets: 9th DIMACS Implementation Challenge road networks (NY, BAY, COL)
Benchmarks: DIMACS road networks NY, BAY, COL with 2 and 3 resources
Metrics: solved instances runtime (s) slowdown factor vs virtual best oracle
Baselines: RCBDA* ERCA* improved RCBDA*
Builds on: RCBDA* ERCA* BiPulse Pulse perimeter search
Closest papers by meaning
- A Fast Exact Algorithm for the Resource Constrained Shortest Path Problem (AAAI 2021 · similarity 0.89)
- Sublinear Search Spaces for Shortest Path Planning in Grid and Road Networks (AAAI 2018 · similarity 0.85)
- Anchor Search: A Unified Framework for Suboptimal Bidirectional Search (AAAI 2025 · similarity 0.82)
- Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks (AAAI 2025 · similarity 0.81)
- Efficient Constraint Generation for Stochastic Shortest Path Problems (AAAI 2024 · similarity 0.81)
- Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures (AAAI 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.