An Approximation Algorithm for the Subpath Planning Problem
Authors: Masoud Safilian, S. Mehdi Hashemi, Sepehr Eghbali, Aliakbar Safilian
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In addition to complexity analysis and proving the approximation bound of CSPP, we empirically compare it with the method proposed in [Gyorfiet al., 2010] over various workspaces with different numbers of subpaths. The results indicate that CSPP is more efficient than the other existing methods both in terms of cost of the solution and running time. |
| Researcher Affiliation | Academia | Amirkabir University of Technology, Tehran, Iran University of Waterloo, Ontario, Canada Mc Master University, Ontario, Canada |
| Pseudocode | Yes | Algorithm 1 CSPP |
| Open Source Code | No | The paper does not provide any explicit statement about releasing source code or a link to a code repository. |
| Open Datasets | No | In our experiments, we use different sets of workspaces including 3 environments with 20 subpaths, 3 environments with 50 subpaths and 3 environments with 80 subpaths. The length and the location of the subpaths are chosen randomly. |
| Dataset Splits | No | The paper describes environments with different numbers of subpaths for experiments but does not provide specific training, validation, or test dataset splits. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., CPU, GPU models, or memory specifications) used for running the experiments. |
| Software Dependencies | No | The paper mentions comparing with a 'GA-based method proposed in [Gyorfiet al., 2010]' and uses algorithms like Kruskal, Prim, Fleury, and Micali and Vazirani, but it does not specify any software names with version numbers (e.g., 'Python 3.8, CPLEX 12.4') that would be required for reproducibility. |
| Experiment Setup | Yes | Parameter setting for the operation rates of GA are chosen to be 0.5 for crossover, 0.25 for inversion, 0.25 for rotation, 0.5 for mutation and 0.5 for subpath reversal. |