Reachability and Coverage Planning for Connected Agents
Authors: Tristan Charrier, Arthur Queffelec, Ocan Sankur, François Schwarzentruber
IJCAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We establish the complexity of these problems on known classes, and introduce a new class called sight-moveable graphs which admit efficient algorithms. Our main result in this paper is the definition of a class of topological graphs which is well adapted and realistic for UAV missions, and for which the coverage and reachability problems admit efficient algorithms. For this class, we prove that both the reachability and coverage problems are in LOGSPACE. This drastically changes the status of this problem since by LOGSPACE NC (this is the class of problems solvable in polylogarithmic time in a parallel machine with a polynomial number of processors), one can build an efficient parallel algorithm [Cook, 1979]. The bounded versions are NP-complete. |
| Researcher Affiliation | Academia | Univ Rennes, CNRS, IRISA1, Univ Rennes, Inria, CNRS, IRISA2 |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper provides a link to an extended version on arXiv (https://arxiv.org/abs/1903.04300), but no explicit statement or link for the open-sourcing of the code used for the methodology described in the paper. |
| Open Datasets | No | This is a theoretical paper focusing on computational complexity and graph properties, and therefore does not involve the use of datasets, training data, or public datasets for experimental purposes. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical experiments requiring dataset splits. |
| Hardware Specification | No | This is a theoretical paper and does not describe or report on any empirical experiments that would require specific hardware specifications. |
| Software Dependencies | No | This is a theoretical paper and does not describe any software dependencies with specific version numbers, as it does not involve implementation or empirical evaluation. |
| Experiment Setup | No | This is a theoretical paper and does not involve empirical experiments, therefore no experimental setup details like hyperparameters or training configurations are provided. |