Planning High-Level Paths in Hostile, Dynamic, and Uncertain Environments
Authors: Jacopo Banfi, Vikram Shree, Mark Campbell
JAIR 2020 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, in Section 6, we show the results of an extensive validation campaign in a simulated intrusion scenario: for the general problem, we show the limits of the MINLP approach in dealing with large scale problem instances, and evaluate the optimality losses introduced by the heuristic also comparing it against two baselines (a Monte Carlo Tree Search algorithm and a sampling-based approach); for the two limit cases, instead, we show the computational advantages offered by more specialized algorithms over slight variations of the general MINLP approach. |
| Researcher Affiliation | Academia | Jacopo Banfi EMAIL Vikram Shree EMAIL Mark Campbell EMAIL Cornell University, Ithaca, NY 14853 USA |
| Pseudocode | Yes | Algorithm 1: A history-independent heuristic for solving PPHE. Algorithm 2: A heuristic for solving PPHE able to take into account the agent s belief about possible interception events. Algorithm 3: A pseudo-polynomial time algorithm deciding PPHE-D1. |
| Open Source Code | No | The heuristic is implemented in Python, using Num Py and the Python interface of the freely available igraph C library (Csardi & Nepusz, 2006). This sentence indicates the tools used but does not state that the authors' own code for the methodology is open-source or provide a link. |
| Open Datasets | Yes | We also test our algorithms on two real indoor environments/graphs, dubbed Office and Museum, first introduced by Hollinger et al. (2009) in the evaluation of strategies for a related multirobot search problem (which can be thought as the dual of the problem considered in this work; see Remark 2.5.1). |
| Dataset Splits | No | The paper describes generating 'randomly generated grid instances' and using 'real indoor environments/graphs' from a cited work. However, it does not specify explicit training/test/validation splits in the context of machine learning experiments, which are typical for reproducibility. The mention of '20 random instances' refers to different problem instantiations for testing, not data splits within a single dataset. |
| Hardware Specification | Yes | All MI(N)LPs are solved with the SCIP solver (vers. 6.0.0) (Gleixner et al., 2018) with a 30 minutes timeout on a machine equipped with two Intel Xeon processors and 64 GB RAM. |
| Software Dependencies | Yes | All MI(N)LPs are solved with the SCIP solver (vers. 6.0.0) (Gleixner et al., 2018) ... The heuristic is implemented in Python, using Num Py and the Python interface of the freely available igraph C library (Csardi & Nepusz, 2006). |
| Experiment Setup | Yes | All MI(N)LPs are solved with the SCIP solver (vers. 6.0.0) (Gleixner et al., 2018) with a 30 minutes timeout...The remaining SCIP parameters are kept at their default values. In the MCTS Baseline...Preliminary experiments show that the combination Cp = 0.5, τ = 4 is the one that works best. In our experiments, we run it for a number of iterations linear in the deadline, precisely 25T. In the SB Baseline...we use = 1 for both Algorithm 2 and the SB baseline. For grid instances...the 4x4 black squares are separated by a corridor whose width is a single grid cell; for any s S, |V (s)| = 1 and ps is randomly chosen in {0.05, 0.1}; all dynamic obstacles have the same probability of existence pd, and can intercept the agent within (Manhattan) distance r; 5% of the empty grid cells are populated with a static probabilistic obstacle, and 30% of the 4x4 black squares are associated with dynamic ones. The latter have initial belief centered in a single cell, and move around the corresponding black square according to the following motion pattern (representing a probabilistic delay): move in the next cell with probability 1 θ, and stay at the current cell with probability θ; for each combination of parameters, tests are performed on 20 random instances. |