Iterated Multi-Robot Auctions for Precedence-Constrained Task Scheduling

被引：0

作者：

McIntire, Mitchell ^{[1
]}

Nunes, Ernesto ^{[1
]}

Gini, Maria ^{[1
]}

机构：

[1] Univ Minnesota, 200 Union St SE, Minneapolis, MN 55455 USA

来源：

AAMAS'16: PROCEEDINGS OF THE 2016 INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS & MULTIAGENT SYSTEMS | 2016年

关键词：

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider the multi-robot task scheduling problem with precedence constraints, and introduce a general algorithm to approximate a solution to this problem. Our algorithm utilizes an iterated auction scheme, in which a batch of tasks that are pairwise unconstrained is selected in each iteration and scheduled using a modified sequential single-item auction. This algorithm also gains flexibility by allowing the use of task prioritization to order the scheduling process. We demonstrate the effectiveness of this iterated auction scheme empirically using existing 100- and 1000-task data sets that we have modified to include precedence constraints.

引用

页码：1078 / 1086

页数：9

共 50 条

[1] SCHEDULING OF PRECEDENCE-CONSTRAINED TASKS ON MULTIPROCESSORS
PRICE, CC
SALAMA, MA
COMPUTER JOURNAL, 1990, 33 (03): : 219 - 229
[2] Energy Efficient Multi-Robot Task Allocation Constrained by Time Window and Precedence
Zhang, Lixuan
Zhao, Jianzhuang
Lamon, Edoardo
Wang, Yabin
Hong, Xiaopeng
IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2023, : 1 - 12
[3] Multi-Robot Task Allocation and Scheduling Considering Cooperative Tasks and Precedence Constraints
Bischoff, Esther Y.
Meyer, Fabian
Inga, Jairo
Hohmann, Soren
2020 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS (SMC), 2020, : 3949 - 3956
[4] Multi-Robot Task Scheduling
Zhang, Yu
Parker, Lynne E.
2013 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION (ICRA), 2013, : 2992 - 2998
[5] The multiprocessor scheduling of precedence-constrained task systems in the presence of interprocessor communication delays
Baruah, SK
OPERATIONS RESEARCH, 1998, 46 (01) : 65 - 72
[6] Precedence-Constrained Scheduling of Malleable Jobs with Preemption
Makarychev, Konstantin
Panigrahi, Debmalya
AUTOMATA, LANGUAGES, AND PROGRAMMING (ICALP 2014), PT I, 2014, 8572 : 823 - 834
[7] A scheduling method for multi-robot assembly of aircraft structures with soft task precedence constraints
Tereshchuk, Veniamin
Bykov, Nikolay
Pedigo, Samuel
Devasia, Santosh
Banerjee, Ashis G.
ROBOTICS AND COMPUTER-INTEGRATED MANUFACTURING, 2021, 71
[8] Multi-Robot Coordination and Cooperation with Task Precedence Relationships
Gosrich, Walker
Mayya, Siddharth
Narayan, Saaketh
Malencia, Matthew
Agarwal, Saurav
Kumar, Vijay
2023 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION, ICRA, 2023, : 5800 - 5806
[9] Approximating precedence-constrained single machine scheduling by coloring
Ambuhl, Christoph
Mastrolilli, Monaldo
Svensson, Ola
APPROXIMATION, RANDOMIZATION AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES, 2006, 4110 : 15 - 26
[10] Scheduling Recurrent Precedence-Constrained Task Graphs on a Symmetric Shared-Memory Multiprocessor
Devi, UmaMaheswari C.
EURO-PAR 2009: PARALLEL PROCESSING, PROCEEDINGS, 2009, 5704 : 265 - 280

← 1 2 3 4 5 →