Stepwise Large-Scale Multi-Agent Task Planning Using Neighborhood Search

被引:3
作者
Zeng, Fan [1 ]
Shirafuji, Shouhei [2 ]
Fan, Changxiang [3 ]
Nishio, Masahiro [4 ]
Ota, Jun [5 ]
机构
[1] Univ Tokyo, Grad Sch Engn, Dept Precis Engn, Tokyo 1138656, Japan
[2] Kansai Univ, Dept Engn Mech, Fac Engn Sci, Osaka 5650842, Japan
[3] Guangdong Acad Agr Sci, Inst Facil Agr, Guangzhou 510640, Peoples R China
[4] Toyota Motor Co Ltd, Adv R&D & Engn Co, R&D & Engn Management Div, Strateg R&D Planning Dept, Toyota 4710826, Japan
[5] Univ Tokyo, Sch Engn, Res Artifacts, Ctr Engn RACE, Tokyo 1138656, Japan
来源
IEEE ROBOTICS AND AUTOMATION LETTERS | 2024年 / 9卷 / 01期
关键词
Heuristic search; multi-agent system; neighborhood search; plangraph; task planning; STRIPS;
D O I
10.1109/LRA.2023.3331900
中图分类号
TP24 [机器人技术];
学科分类号
080202 ; 1405 ;
摘要
This letter presents a novel stepwise multi-agent task planning method that incorporates neighborhood search to address large-scale problems, thereby reducing computation time. With an increasing number of agents, the search space for task planning expands exponentially. Hence, conventional methods aiming to find globally optimal solutions, especially for some large-scale problems, incur extremely high computational costs and may even fail. In this letter, the proposed method easily achieves the goals of multi-agent task planning by solving an initial problem using a minimal number of agents. Subsequently, tasks are reallocated among all agents based on this solution and the solutions are iteratively optimized using a neighborhood search. While aiming to find a near-optimal solution rather than an optimal one, the method substantially reduces the time complexity of searching to a polynomial level. Moreover, the effectiveness of the proposed method is demonstrated by solving some benchmark problems and comparing the results obtained using the proposed method with those obtained using other state-of-the-art methods.
引用
收藏
页码:111 / 118
页数:8
相关论文
共 26 条
  • [1] Benton J., 2012, ICAPS 2012
  • [2] Blanco D. F., 2018, P 13 WORKSH CONSTR S, P11
  • [3] Bonet B, 2000, LECT NOTES ARTIF INT, V1809, P360
  • [4] THE COMPUTATIONAL-COMPLEXITY OF PROPOSITIONAL STRIPS PLANNING
    BYLANDER, T
    [J]. ARTIFICIAL INTELLIGENCE, 1994, 69 (1-2) : 165 - 204
  • [5] Multi-Agent Strategy for Marine Applications via Temporal Planning
    Carreno, Yaniel
    Petrick, Ronald P. A.
    Petillot, Yvan
    [J]. 2019 IEEE SECOND INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND KNOWLEDGE ENGINEERING (AIKE), 2019, : 243 - 250
  • [6] Cashmore M, 2020, J ARTIF INTELL RES, V67, P235
  • [7] Coles A., 2011, P INT C AUT PLAN SCH, P34
  • [8] Eyerich P, 2012, SPRINGER TRAC ADV RO, V76, P49
  • [9] STRIPS - NEW APPROACH TO APPLICATION OF THEOREM PROVING TO PROBLEM SOLVING
    FIKES, RE
    NILSSON, NJ
    [J]. ARTIFICIAL INTELLIGENCE, 1971, 2 (3-4) : 189 - 208
  • [10] PDDL2.1: An extension to PDDL for expressing temporal planning domains
    Fox, M
    Long, D
    [J]. JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2003, 20 : 61 - 124