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 条
  • [1] Complexity of planning for connected agents
    Tristan Charrier
    Arthur Queffelec
    Ocan Sankur
    François Schwarzentruber
    Autonomous Agents and Multi-Agent Systems, 2020, 34
  • [2] Framework and complexity results for coordinating non-cooperative planning agents
    Steenhuisen, J. Renze
    Witteveen, Cees
    ter Mors, Adriaan W.
    Valk, Jeroen M.
    MULTIAGENT SYSTEM TECHNOLOGIES, PROCEEDINGS, 2006, 4196 : 98 - 109
  • [3] COMPLEXITY RESULTS FOR SAS(+) PLANNING
    BACKSTROM, C
    NEBEL, B
    COMPUTATIONAL INTELLIGENCE, 1995, 11 (04) : 625 - 655
  • [4] Planning agents in JAMES
    Schattenberg, B
    Uhrmacher, AM
    PROCEEDINGS OF THE IEEE, 2001, 89 (02) : 158 - 173
  • [5] Computational complexity of planning and approximate planning in the presence of incompleteness
    Baral, C
    Kreinovich, V
    Trejo, R
    ARTIFICIAL INTELLIGENCE, 2000, 122 (1-2) : 241 - 267
  • [6] The influence of k-dependence on the complexity of planning
    Gimenez, Omer
    Jonsson, Anders
    ARTIFICIAL INTELLIGENCE, 2012, 177 : 25 - 45
  • [7] Monitoring agents using declarative planning
    Dix, JG
    Eiter, T
    Fink, M
    Polleres, A
    Zhang, YQ
    KI 2003: ADVANCES IN ARTIFICIAL INTELLIGENCE, 2003, 2821 : 646 - 660
  • [8] Monitoring agents using declarative planning
    Dix, J
    Eiter, T
    Fink, M
    Polleres, A
    Zhang, YQ
    FUNDAMENTA INFORMATICAE, 2003, 57 (2-4) : 345 - 370
  • [9] Distributed Search Planning in 3-D Environments With a Dynamically Varying Number of Agents
    Papaioannou, Savvas
    Kolios, Panayiotis
    Theocharides, Theocharis
    Panayiotou, Christos G.
    Polycarpou, Marios M.
    IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS, 2023, 53 (07): : 4117 - 4130
  • [10] Opportunism in planning agents
    Lawton, JH
    7TH WORLD MULTICONFERENCE ON SYSTEMICS, CYBERNETICS AND INFORMATICS, VOL XII, PROCEEDINGS: INFORMATION SYSTEMS, TECHNOLOGIES AND APPLICATIONS: II, 2003, : 496 - 501
12345