Efficient Optimal Search under Expensive Edge Cost Computation
Authors: Masataro Asai, Akihiro Kishimoto, Adi Botea, Radu Marinescu, Elizabeth M. Daly, Spyros Kotoulas
IJCAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 5 Experimental Results We evaluate DEA* s performance in the MWRP and in domain-independent planning. Experiments are conducted on an Intel Xeon CPU cluster, with a time and memory limit of one hour and 1.5 million in-memory states per instance. |
| Researcher Affiliation | Collaboration | Masataro Asai , Akihiro Kishimoto , Adi Botea , Radu Marinescu , Elizabeth M. Daly and Spyros Kotoulas Graduate School of Arts and Sciences, The University of Tokyo IBM Research, Ireland guicho2.71828@gmail.com, {akihirok, adibotea, radu.marinescu, elizabeth.daly, spyros.kotoulas}@ie.ibm.com |
| Pseudocode | Yes | Algorithm 1 DEA* Input: n0 1: Initialize OPEN , g(n0) 0, ( n = n0; g(n) ) 2: insert(n0, OPEN), Mark s0 as standard (i.e., not temporary) 3: while OPEN = do 4: n delete Min(OPEN) 5: if n has a duplicate n CLOSED and g(n ) g(n) then 6: Continue 7: else if n is temporary then 8: g(n) g(parent(n)) + ca(parent(n), n) 9: Adjust s(n), h(n), f(n) based on ca 10: insert(n, OPEN), Mark n as standard (i.e., not temporary) 11: Continue 12: else 13: Add n to CLOSED, Update g(n) in CLOSED if better g-value is found 14: if n is a goal then 15: Extract and return solution 16: Generate successors(n) based on ch 17: for each m successors(n) do 18: gh g(n) + ch(n, m) 19: g(m) gh, parent(m) n 20: insert(m, OPEN), Mark m as temporary |
| Open Source Code | No | The paper does not contain any statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | The paper mentions using 'real road-map and transportation data from three European cities (Table 1)' and describes how instances were generated, but does not provide concrete access information (e.g., link, DOI, specific citation to the dataset source with authors and year) for this data. |
| Dataset Splits | No | The paper does not specify exact dataset split percentages, absolute sample counts for validation, or any cross-validation setup. |
| Hardware Specification | No | The paper mentions 'an Intel Xeon CPU cluster' but does not provide specific details such as exact CPU models, memory specifications, or GPU information used for the experiments. |
| Software Dependencies | No | The paper mentions using the 'DIJA journey planning system' and 'Fast Downward planner' but does not provide specific version numbers for these software components or any other ancillary software. |
| Experiment Setup | Yes | We generated a total of 180 instances with the real road-map and transportation data from three European cities (Table 1). In each instance, there are either 6 or 12 workers, while the number of patients was varied between 8 24. ... Appointment times are randomly set between 10 11AM. Workers start times are fixed at 10AM. ... Experiments are conducted on an Intel Xeon CPU cluster, with a time and memory limit of one hour and 1.5 million in-memory states per instance. ... We then assumed that Fast Downward can obtain the heuristic edge cost ch by subtracting a constant c from the actual edge cost ca, i.e. ch = max(0, ca c)... We show results obtained with c = 8 and c = 1 |