Solving the Watchman Route Problem with Heuristic Search
Authors: Shawn Skyler, Dor Atzmon, Tamir Yaffe, Ariel Felner
JAIR 2022 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We theoretically and empirically investigate these heuristics. Then, we show how the optimal methods can be modified (by intelligently pruning away large sub-trees) to obtain various suboptimal solvers with and without bound guarantees. These suboptimal solvers are much faster and expand fewer nodes than the optimal solver with only minor reduction in the quality of the solution. |
| Researcher Affiliation | Academia | Shawn Skyler EMAIL Dor Atzmon EMAIL Tamir Yaffe EMAIL Ariel Felner EMAIL Ben-Gurion University of the Negev, Be er-Sheva Israel |
| Pseudocode | No | The paper describes algorithms and methods in prose and through figures, but it does not contain explicit, structured pseudocode or algorithm blocks with numbered steps labeled as such. |
| Open Source Code | No | The paper mentions using "our implementation" and an "off-the-shelf TSP solver (Michail, Kinable, Naveh, & Sichi, 2020)" but does not provide an explicit statement about releasing their own code or a link to a code repository for the methodology described. |
| Open Datasets | Yes | We experimented with WA*, XDP and XUP on the Den405d map (Sturtevant, 2012) (Figure 16) with different values for W. In our implementation we did not allow to reopen closed nodes. |
| Dataset Splits | No | The paper discusses generating instances from a base maze, e.g., "71 instances (1 . . . 71) where instance #n only had n obstacles randomized from the 71 obstacle set" and averaging results "over 25 trials that randomly chose the subset of obstacles." While it describes how experiment instances are selected, it does not specify conventional training/test/validation dataset splits (e.g., percentages or counts) typically used for machine learning models. |
| Hardware Specification | No | The paper mentions "BFS and Singleton exhausted the available memory of 2GB and a failure was reported" and reports "CPU time". However, it does not specify any particular CPU or GPU models, or other detailed hardware specifications used for running the experiments. |
| Software Dependencies | No | We used an off-the-shelf TSP solver (Michail, Kinable, Naveh, & Sichi, 2020), based on an algorithm by Held and Karp (1970) that finds the optimal TSP tour. In our experiments below, we never had more than 12 pivots. |
| Experiment Setup | Yes | In our implementation, the APSP table was built lazily but the LOS tables were built in a preprocessing phase. We next experiment on an 11x11 maze map shown in Figure 11a with a specific start state (the Green cell at the top left corner). In our implementation we did not allow to reopen closed nodes. Let distance factor (DF) be a constant factor. We now connect S.location only to jump points whose edges have costs C such that C DF ϵ(S). Table 9 compares combining WA* with all our methods tested on Den020d which is a complex large map with 3,100 free cells, shown in Figure 23. Both IW and WR are used and the tested parameters are DF and W for WA*. Increasing W somewhat speeds up the search at a cost of a longer solution. Reducing DF also speeds up the search but tends to better preserve the solution quality. |