Complexity of planning for connected agents

被引：5
|
作者：
Charrier, Tristan [1 ]
Queffelec, Arthur [1 ]
Sankur, Ocan [1 ]
Schwarzentruber, Francois [1 ]
机构：
[1] Univ Rennes, Inria, CNRS, IRISA, 263 Ave Gen Leclerc, F-35000 Rennes, France
来源：
AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS | 2020年 / 34卷 / 02期
关键词：
Artifical intelligence; Multi-agent systems; Planning; Computational complexity; MULTIROBOT EXPLORATION; COVERAGE; INTRACTABILITY;
D O I：
10.1007/s10458-020-09468-5
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We study a variant of the multi-agent path finding (MAPF) problem in which the group of agents are required to stay connected with a supervising base station throughout the execution. In addition, we consider the problem of covering an area with the same connectivity constraint. We show that both problems are PSPACE-complete on directed and undirected topological graphs while checking the existence of a bounded plan is NP-complete when the bound is given in unary (and PSPACE-hard when the encoding is in binary). Moreover, we identify a realistic class of topological graphs on which the decision problem falls in NLOGSPACE although the bounded versions remain NP-complete for unary encoding.
引用
收藏
页数：31
相关论文
共 50 条
  • [31] Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs
    Le, Hoang-Oanh
    Le, Van Bang
    THEORY OF COMPUTING SYSTEMS, 2024, 68 (02) : 250 - 270
  • [32] Quantified coalition logic for bdi-agents: Completeness and complexity
    Chen, Qingliang
    Li, Qun
    Su, Kaile
    Luo, Xiangyu
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014, 8862 : 871 - 876
  • [33] Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs
    Hoang-Oanh Le
    Van Bang Le
    Theory of Computing Systems, 2024, 68 : 250 - 270
  • [34] The complexity of connected dominating sets and total dominating sets with specified induced subgraphs
    Schaudt, Oliver
    Schrader, Rainer
    INFORMATION PROCESSING LETTERS, 2012, 112 (24) : 953 - 957
  • [35] Quantified Coalition Logic for BDI-Agents: Completeness and Complexity
    Chen, Qingliang
    Li, Qun
    Su, Kaile
    Luo, Xiangyu
    PRICAI 2014: TRENDS IN ARTIFICIAL INTELLIGENCE, 2014, 8862 : 871 - 876
  • [36] Adaptive consensus of multi-agents in networks with jointly connected topologies
    Yu, Hui
    Xia, Xiaohua
    AUTOMATICA, 2012, 48 (08) : 1783 - 1790
  • [37] Refining complexity analyses in planning by exploiting the exponential time hypothesis
    Meysam Aghighi
    Christer Bäckström
    Peter Jonsson
    Simon Ståhlberg
    Annals of Mathematics and Artificial Intelligence, 2016, 78 : 157 - 175
  • [38] Decentralized Navigation with Optimality for Multiple Holonomic Agents in Simply Connected Workspaces
    Kotsinis, Dimitrios
    Bechlioulis, Charalampos P.
    SENSORS, 2024, 24 (10)
  • [39] Refining complexity analyses in planning by exploiting the exponential time hypothesis
    Aghighi, Meysam
    Backstrom, Christer
    Jonsson, Peter
    Stahlberg, Simon
    ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2016, 78 (02) : 157 - 175
  • [40] The effect of task complexity on planning in preterm-born children
    Sheehan, John C.
    Kerns, Kimberly A.
    Muller, Ulrich
    CLINICAL NEUROPSYCHOLOGIST, 2017, 31 (02) : 438 - 458
12345