Approximately Optimal Risk-Averse Routing Policies via Adaptive Discretization
Authors: Darrell Hoy, Evdokia Nikolova
AAAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments We tested Algorithm 3 on m n grid graphs, routing from the (0, 0) vertex to (m 1, n 1) vertex. We compare adaptive discretization to uniform time based discretization, where time discretization is done with L(s)/ϵ steps to achieve a policy of about the same size as the adaptive policy. The distribution on each edge is an independent gammadistribution with lower support of 10, mean drawn uniformly between 25 and 35 and shape parameter drawn uniformly between 1 and 100. A 0-1 utility is used with a deadline of 30 ((m 1) + (n 1)), ensuring a reasonable chance of arriving on time. 5 different graphs are tested for each configuration. Errors given are the standard deviation over these 5 graphs. Expected utilities are calculated by following the policy for 50000 realizations of delays on the graph. |
| Researcher Affiliation | Academia | Darrell Hoy Electrical Engineering and Computer Science Northwestern University darrell.hoy@u.northwestern.edu Evdokia Nikolova Electrical and Computer Engineering University of Texas at Austin nikolova@austin.utexas.edu |
| Pseudocode | Yes | Algorithm 1 BESTNEIGHBOR (v, t) Calculate best neighbor from vertex v at time t Algorithm 2 ADAPTIVEDISC (v, (a, b)) Adaptively discretize vertex v for times in interval (a, b). Algorithm 3 UPDATEDAGPOLICY (G) |
| Open Source Code | No | The paper does not provide any explicit statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | The paper describes the generation of synthetic graph data for its experiments ('The distribution on each edge is an independent gammadistribution with lower support of 10, mean drawn uniformly between 25 and 35 and shape parameter drawn uniformly between 1 and 100.') but does not provide access information (link, citation) to a publicly available dataset. |
| Dataset Splits | No | The paper describes testing its algorithm on randomly generated 'm n grid graphs' with specific edge cost distributions. It does not mention traditional train/validation/test dataset splits, as it validates an algorithm on generated graph instances rather than a pre-existing dataset. |
| Hardware Specification | Yes | The implementation is in Python and single-threaded, and execution times are on an Intel Xeon E5-2630 2.3GHz processor. |
| Software Dependencies | No | The paper only mentions 'Python' as the implementation language but does not provide specific version numbers for Python or any other software libraries or dependencies used. |
| Experiment Setup | Yes | The distribution on each edge is an independent gammadistribution with lower support of 10, mean drawn uniformly between 25 and 35 and shape parameter drawn uniformly between 1 and 100. A 0-1 utility is used with a deadline of 30 ((m 1) + (n 1)), ensuring a reasonable chance of arriving on time. and The graphs tested are grid graphs with fixed width 10, and fixed error bound ϵ = 1/8. |