Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Dynamic Controllability of Temporal Plans in Uncertain and Partially Observable Environments
Authors: Arthur Bit-Monnot, Paul Morris
JAIR 2023 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | A sound and complete polynomial algorithm to determining the Dynamic Controllability of POSTNUs has not previously been known; we present one in this paper. This answers an open problem that has been posed in the literature. The approach we take factors the problem into Strong Controllability micro-problems in an overall Dynamic Controllability macro-problem framework. It generalizes the notion of labeled distance graph from STNUs. The generalized labels are expressed as max/min expressions involving the observables. The paper introduces sound generalized reduction rules that act on the generalized labels. These incorporate tightenings based on observability that preserve dynamic viable strategies. It is shown that if the generalized reduction rules reach quiescence without exposing an inconsistency, then the POSTNU is Dynamically Controllable (DC). The paper also presents algorithms that apply the reduction rules in an organized way and reach quiescence in a polynomial number of steps if the POSTNU is Dynamically Controllable. We have presented two algorithms for this determination that run in polynomial time, including an adaption of the STNU recursive backward Dijkstra approach of Morris (2014). Given a POSTNU with N timepoints, this second algorithm has a worst-case complexity in O(N5) in the general case. In the common case where the individual non-observable components of the network have a bounded size, its complexity reduces to O(N3). |
| Researcher Affiliation | Academia | Arthur Bit-Monnot EMAIL LAAS-CNRS, Universit e de Toulouse, CNRS, INSA, Toulouse, France, Paul Morris Formerly at NASA Ames Research Center, Moffett Field, CA 94035 USA |
| Pseudocode | Yes | Algorithm 1 Partition contingent links of a POSTNU into hidden groups, Algorithm 2 Construction of the labeled distance graph of a POSTNU Π, Algorithm 3 A single round of reduction in the POSTNU generalized labeled graph., Algorithm 4 Na ıve implementation of Dynamic Controllability checking of the generalized labeled graph of a POSTNU., Algorithm 5 Improved algorithm for DC checking of POSTNUs, based on the recursive derivation of tightest edges., Algorithm 6 Helper functions for the recursive algorithm. |
| Open Source Code | No | The paper does not contain any explicit statement about providing source code or a link to a code repository for the described methodology. |
| Open Datasets | No | The paper uses examples (e.g., the 'post office example') to illustrate concepts but does not refer to or provide access information for any publicly available or open datasets used for experimental validation. |
| Dataset Splits | No | The paper does not conduct empirical experiments using datasets, therefore it does not provide any training/test/validation dataset splits. |
| Hardware Specification | No | The paper focuses on theoretical contributions and algorithm design; it does not describe any experimental setup that would require specific hardware specifications. |
| Software Dependencies | No | The paper presents theoretical algorithms and their complexity. It does not describe an experimental setup or provide specific software dependencies with version numbers needed for replication. |
| Experiment Setup | No | The paper focuses on theoretical algorithms and their complexity analysis. It does not include an experimental section with specific setup details like hyperparameters, model initialization, or training schedules. |