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 条

[41] Period/Dynamic Planning Problem: Formal Representation and Complexity Analysis
Chen, Aixiang
Chen, Qingliang
ICICTA: 2009 SECOND INTERNATIONAL CONFERENCE ON INTELLIGENT COMPUTATION TECHNOLOGY AND AUTOMATION, VOL IV, PROCEEDINGS, 2009, : 227 - +
[42] PLANNING THE ACTIVITIES OF INTELLECTUAL AGENTS IN THE ELECTRONIC COMMERCE SYSTEMS
Berko, A.
Vysotska, V.
Lytvyn, V.
Naum, O.
RADIO ELECTRONICS COMPUTER SCIENCE CONTROL, 2018, (04) : 143 - 158
[43] A MULTIAGENT TASK PLANNING METHOD FOR AGENTS WITH DISPARATE CAPABILITIES
KAMEL, M
SYED, A
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 1994, 9 (06) : 408 - 420
[44] Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal with It
Tateo, Davide
Banfi, Jacopo
Riva, Alessandro
Amigoni, Francesco
Bonarini, Andrea
THIRTY-SECOND AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTIETH INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / EIGHTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, 2018, : 4735 - 4742
[45] Distributed Maneuver Planning With Connected and Automated Vehicles for Boosting Traffic Efficiency
Goulet, Nathan
Ayalew, Beshah
IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS, 2022, 23 (08) : 10887 - 10901
[46] Augmented Agents: Contextual Perception and Planning for BDI Architectures
Casals, Arthur
El Fallah-Seghrouchni, Amal
Brandao, Anarosa A. F.
ENGINEERING MULTI-AGENT SYSTEMS, EMAS 2017, 2018, 10738 : 38 - 55
[47] Argumentation-based negotiation planning for autonomous agents
Monteserin, Ariel
Amandi, Analia
DECISION SUPPORT SYSTEMS, 2011, 51 (03) : 532 - 548
[48] Motion Planning for Connected Automated Vehicles at Occluded Intersections With Infrastructure Sensors
Mueller, Johannes
Strohbeck, Jan
Herrmann, Martin
Buchholz, Michael
IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS, 2022, 23 (10) : 17479 - 17490
[49] Application of Lissajous curves in trajectory planning of multiple agents
Borkar, Aseem Vivek
Sinha, Arpita
Vachhani, Leena
Arya, Hemendra
AUTONOMOUS ROBOTS, 2020, 44 (02) : 233 - 250
[50] The effect of planning sub-processes on L2 writing fluency, grammatical complexity, and lexical complexity
Johnson, Mark D.
Mercado, Leonardo
Acevedo, Anthony
JOURNAL OF SECOND LANGUAGE WRITING, 2012, 21 (03) : 264 - 282

← 1 2 3 4 5 →