Knowledge-Based Policies for Qualitative Decentralized POMDPs
Authors: Abdallah Saffidine, François Schwarzentruber, Bruno Zanuttini
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove that this representation is as succinct as standard ones, e.g., joint policies trees, and we give families of problems for which it is exponentially more succinct. Contrary to standard representations, determining the action to execute next is nontrivial in MAKBPs, as it involves explicit reasoning about other agents knowledge. We then investigate the complexity of this execution problem and that of verifying whether a given MAKBP solves a given QDec-POMDP, and we show that both these essential problems are intractable: both are PSPACE-complete if the horizon is bounded, and verification is undecidable otherwise. |
| Researcher Affiliation | Academia | Abdallah Saffidine University of New South Wales, Sydney, Australia Franc ois Schwarzentruber Univ. Rennes, CNRS, IRISA France Bruno Zanuttini Normandie Univ UNICAEN, ENSICAEN, CNRS, GREYC 14000 Caen, France |
| Pseudocode | No | The paper defines formal concepts and structures but does not include explicitly labeled pseudocode or algorithm blocks. |
| Open Source Code | No | A simple demonstration of executions of KBPs can be found in the tool Hintikka s world (http://people.irisa.fr/Francois. Schwarzentruber/hintikkasworld/). This is a reference to an existing tool, not the release of the code for the specific methodology proposed in this paper. |
| Open Datasets | No | The paper describes theoretical concepts and does not involve the use of publicly available datasets for training. |
| Dataset Splits | No | The paper does not describe experiments with datasets, and therefore no information on validation splits is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper describes theoretical concepts and does not specify software dependencies with version numbers for experimental replication. |
| Experiment Setup | No | The paper is theoretical and does not describe experimental setup details such as hyperparameters or training settings. |