Rectangle Search: An Anytime Beam Search
Authors: Sofia Lemons, Wheeler Ruml, Rob Holte, Carlos Linares Lopez
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments using a variety of popular search benchmarks suggest that rectangle search is competitive with fixed-width beam search and often performs better than the previous best anytime search algorithms. We study rectangle search s performance experimentally on seven popular heuristic search benchmarks. |
| Researcher Affiliation | Academia | 1 University of New Hampshire 2 Earlham College 3 University of Alberta, Alberta Machine Intelligence Institute (Amii) 4 Computer Science and Engineering Department, Universidad Carlos III de Madrid |
| Pseudocode | Yes | Algorithm 1: Pseudocode for rectangle search. Algorithm 2: Node selection & expansion. |
| Open Source Code | Yes | 1Code available at https://github.com/snlemons/search. |
| Open Datasets | No | The paper refers to common problem domains like 'Sliding Tile Puzzle', 'Blocks World', and 'The Pancake Problem', and states that '100 random blocks world instances with 20 blocks' were used, but it does not provide specific access information (links, citations with authors/year) for the datasets or problem instances used in the experiments. |
| Dataset Splits | No | The paper does not mention training, validation, or test dataset splits; it evaluates search algorithms on problem instances until a time limit is reached. |
| Hardware Specification | Yes | All algorithms were given a 7.5GB memory limit and a 5 minute time limit on a 2.6 GHz Intel Xeon E5-2630v3. |
| Software Dependencies | No | The paper states 'We implemented it and other algorithms in C++', but does not provide specific version numbers for compilers or any other software dependencies. |
| Experiment Setup | Yes | We ran ARA* in several previously-proposed configurations: initial weights of 10 and 2.5 with a decrement of 0.02 (Likhachev, Gordon, and Thrun 2004) and a weight schedule of 5, 3, 2, 1.5, 1 (Thayer, Benton, and Helmert 2012). Rectangle search was tested with aspect values of 1 and 500 (selected through preliminary tests). |