Chance-Constrained Probabilistic Simple Temporal Problems
Authors: Cheng Fang, Peng Yu, Brian Williams
AAAI 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this paper we present the probabilistic Simple Temporal Network (p STN), a probabilistic formalism for representing temporal problems with bounded risk and a utility over event timing. We introduce a constrained optimisation algorithm for p STNs that achieves compactness and efficiency through a problem encoding in terms of a parameterised STNU and its reformulation as a parameterised STN. We demonstrate through a car sharing application that our chance-constrained approach runs in the same time as the previous probabilistic approach, yields solutions with utility improvements of at least 5% over previous arts, while guaranteeing operation within the specified risk bound. |
| Researcher Affiliation | Academia | Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 32 Vassar Street, Cambridge, MA 02139 {cfang,yupeng,williams}@mit.edu |
| Pseudocode | Yes | Algorithm 1: Approximating cc-p STP |
| Open Source Code | No | The paper does not provide any links to open-source code or explicit statements about releasing code. |
| Open Datasets | No | The paper states: |
| Dataset Splits | No | The paper mentions generating 1800 p STNs but does not specify training, validation, or test splits. |
| Hardware Specification | No | The paper mentions |
| Software Dependencies | No | The paper mentions |
| Experiment Setup | Yes | In each scenario we schedule for a 6 hour period, with the number of cars ranging from 1 to 20, each with up to 5 users. For each user, up to three goal locations were generated based on a simplified open source map of Boston. A p STN was generated for each scenario. The traversal activities were modelled as normally distributed uncertain durations, with the means of u Dns determined by length and speed limits of the roads taken, and standard deviations at 5% of the mean. A total of 1800 p STNs were generated. ... For each p STN, we constructed three cc-p STPs, with chance-constraints 10%, 20% and 40%. |