Resource Constrained Pathfinding with Enhanced Bidirectional A* Search
Authors: Saman Ahmadi, Andrea Raith, Guido Tack, Mahdi Jalili
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | This section evaluates the performance of our proposed algorithm and compares it against the state of the art. For the baseline, we consider the recent ERCA* algorithm (Ren et al. 2023) and the improved version of RCBDA* (Thomas, Calogiuri, and Hewitt 2019) we presented in Algorithm 1. Benchmark: We use the instances of Ahmadi et al. (2024c), which are defined over the road networks from the 9th DIMACS Implementation Challenge (DIMACS 2005). We choose 20 (start,goal) pairs over three maps, with the largest map containing over 400K nodes and 1M edges. We study two RCSP scenarios: k = 3 (two resources) and k = 4 (three resources). [...] We report the number of solved cases |S| and runtime statistics (in seconds, including the initialization time). |
| Researcher Affiliation | Academia | Saman Ahmadi1, Andrea Raith2, Guido Tack3, Mahdi Jalili1 1 School of Engineering, RMIT University, Australia 2 Department of Engineering Science, University of Auckland, New Zealand 3 Department of Data Science and AI, Monash University, Australia |
| Pseudocode | Yes | Although the authors did not discuss the pruning rules as part of their label-setting approach, we have provided in Algorithm 1 a refined pseudocode closest to their description, including both pruning rules. ... Algorithm 2: Is Dominated ... We present in Algorithm 3 our proposed initialization phase for RCEBDA*. ... A pseudocode of RCEBDA* is provided in Algorithm 4, with the symbol next to specific line numbers indicating our proposed changes. ... As shown in Algorithm 5, RCEBDA* joins x with all non-dominated nodes of the opposite direction d , stored in X d (s(x)) and X d Dom(s(x)). |
| Open Source Code | Yes | Our code is publicly available1. |
| Open Datasets | Yes | Benchmark: We use the instances of Ahmadi et al. (2024c), which are defined over the road networks from the 9th DIMACS Implementation Challenge (DIMACS 2005). |
| Dataset Splits | Yes | We choose 20 (start,goal) pairs over three maps, with the largest map containing over 400K nodes and 1M edges. We study two RCSP scenarios: k = 3 (two resources) and k = 4 (three resources). [...] Each (start,goal) pair is evaluated on five tightness levels, yielding 100 instances per map per scenario. Following the literature, we define for each resource i {1, . . . , k 1} the budget Ri based on the tightness of the constraint δ as: δ = Ri costmin i+1 costmax i+1 costmin i+1 for δ {10%, 30%, . . . , 90%} |
| Hardware Specification | Yes | We ran all experiments once on a single core of an Intel Xeon Platinum 8488C processor running at 2.4 GHz, with 32 GB of RAM and a one-hour timeout. |
| Software Dependencies | Yes | We implemented our RCEBDA* and the improved version of RCBDA* in C++ and used the publicly available C++ implementations of ERCA*. All C++ code was compiled using the GCC7.5 compiler with O3 optimization settings. |
| Experiment Setup | Yes | We choose the last edge attribute as the critical resource in both RCBDA* and RCEBDA*. In addition, following Ahmadi et al. (2024b), we store non-dominated nodes of each state in a dynamic array, in which nodes are maintained in lexicographical order of their truncated cost vector. ... Similar to the extended parallel weight constrained search in Ahmadi et al. (2024c), we allocate one thread to each direction and allow the forward (resp. backward) search to work on Openf (resp. Openb) independently. The overall search in this framework terminates when both concurrent searches have exited (see Ahmadi et al. (2024c) for more details). |