2.765

2022影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于讨价还价博弈机制的B-IHCA* 多机器人路径规划算法

张凯翔 毛剑琳 向凤红 宣志玮

张凯翔, 毛剑琳, 向凤红, 宣志玮. 基于讨价还价博弈机制的B-IHCA* 多机器人路径规划算法. 自动化学报, 2023, 49(7): 1483−1497 doi: 10.16383/j.aas.c220065
引用本文: 张凯翔, 毛剑琳, 向凤红, 宣志玮. 基于讨价还价博弈机制的B-IHCA* 多机器人路径规划算法. 自动化学报, 2023, 49(7): 1483−1497 doi: 10.16383/j.aas.c220065
Zhang Kai-Xiang, Mao Jian-Lin, Xiang Feng-Hong, Xuan Zhi-Wei. B-IHCA*, a bargaining game based multi-agent path finding algorithm. Acta Automatica Sinica, 2023, 49(7): 1483−1497 doi: 10.16383/j.aas.c220065
Citation: Zhang Kai-Xiang, Mao Jian-Lin, Xiang Feng-Hong, Xuan Zhi-Wei. B-IHCA*, a bargaining game based multi-agent path finding algorithm. Acta Automatica Sinica, 2023, 49(7): 1483−1497 doi: 10.16383/j.aas.c220065

基于讨价还价博弈机制的B-IHCA* 多机器人路径规划算法

doi: 10.16383/j.aas.c220065
基金项目: 云南省重点研发计划项目(202002AC080001), 国家自然科学基金(62263017)资助
详细信息
    作者简介:

    张凯翔:昆明理工大学机电工程学院博士研究生. 主要研究方向为移动机器人路径规划. E-mail: kaixiangzhang35@163.com

    毛剑琳:昆明理工大学信息工程与自动化学院教授. 主要研究方向为通信网络资源分配与协议优化, 智能优化与调度算法, 多机器人系统协同控制研究. 本文通信作者. E-mail: jlmao@kmust.edu.cn

    向凤红:昆明理工大学信息工程与自动化学院教授. 主要研究方向为智能控制理论与应用, 计算机网络控制系统. E-mail: xiangfh5447@sina.com

    宣志玮:昆明理工大学信息工程与自动化学院硕士研究生. 主要研究方向为移动机器人路径规划. E-mail: rangxuan@foxmail.com

B-IHCA*, a Bargaining Game Based Multi-agent Path Finding Algorithm

Funds: Supported by Provincial Major Research Program of Yunnan (202002AC080001) and National Natural Science Foundation of China (62263017)
More Information
    Author Bio:

    ZHANG Kai-Xiang Ph.D. candidate at the Faculty of Mechanical and Electrical Engineering, Kunming University of Science and Technology. His main research interest is mobile robot path planning

    MAO Jian-Lin Professor at the Faculty of Information Engineering and Automation, Kunming University of Science and Technology. Her research interest covers communication network resource allocation and protocol optimization, intelligent optimization and scheduling algorithm, and cooperative control of multi-agent systems. Corresponding author of this paper

    XIANG Feng-Hong Professor at the Faculty of Information Engineering and Automation, Kunming University of Science and Technology. His research interest covers intelligent control theory and its applications, control system of computer network

    XUAN Zhi-Wei Master student at the Faculty of Information Engineering and Automation, Kunming University of Science and Technology. His main research interest is mobile robot path planning

  • 摘要: 针对密集场景中大规模冲突导致多机器人路径规划(Multi-agent path finding, MAPF) 成功率低的问题, 引入讨价还价博弈机制并以层级协作A* (Hierarchical cooperative A*, HCA*) 算法为内核, 提出一种基于讨价还价博弈机制的改进层级协作A* (Bargaining game based improving HCA*, B-IHCA*) 算法. 首先, 在HCA* 算法基础上, 对导致路径无解的冲突双方或多方进行讨价还价博弈. 由高优先级机器人先出价, 当低优先级机器人在该条件下无法求解时, 则其将不接受该出价, 并通过降约束求解方式进行还价. 再由其他冲突方对此做进一步还价, 直至各冲突方都能协调得到可接受的路径方案. 其次, 为避免原始HCA* 算法由于高优先级的阻碍陷于过长或反复无效搜索状态, 在底层A* 搜索环节加入了熔断机制. 通过熔断机制与讨价还价博弈相配合可在提升路径求解成功率的同时兼顾路径代价. 研究结果表明, 所提算法在密集场景大规模机器人路径规划问题上较现有算法求解成功率更高、求解时间更短, 路径代价得到改善, 验证了算法的有效性.
  • 图  1  MAPF问题描述

    Fig.  1  MAPF problem description

    图  2  One-shot类型MAPF问题的终点占位现象

    Fig.  2  Goal occupations in one-shot MAPF problem

    图  3  拥塞问题示例

    Fig.  3  Example of congestion problem

    图  4  约束表使用与更新

    Fig.  4  Use and update of constraint tables

    图  5  密集场景中典型封堵问题

    Fig.  5  Typical blocking problems in dense scenarios

    图  6  讨价还价博弈基本思路

    Fig.  6  Basic example of bargaining game process

    图  7  单点多封堵求解过程

    Fig.  7  Solving process of the single-site and multi-blocking

    图  8  多点多封堵问题降约束个体二次规划

    Fig.  8  Replanning of reduced constraint individuals for the multi-site and multi-blocking

    图  9  HCA* 底层算法低效搜索状态

    Fig.  9  Inefficient searching in underlying of HCA*

    图  10  $ 8 \times 8$地图[11]及任务设置

    Fig.  10  $ 8 \times 8$ map[11] and its tasks

    图  11  大规模随机任务实验地图

    Fig.  11  Maps for large scale randomized tasks

    图  12  各算法测试成功率及求解时间离散分布统计

    Fig.  12  Statistics on success rate and solution time of the tested algorithms

    图  13  4类地图最高数量B-IHCA* 算法求解路径图

    Fig.  13  Path scheme of B-IHCA* algorithm for four tested maps in case of the highest number of robots

    表  1  单点单封堵类型路径规划结果

    Table  1  Solution of the single-site and single-blocking

    机器人路径具体方案
    ${a_1}$${p_{1, 1} }$[(3, 2), (3, 2), (3, 1), (3, 2), (4, 2)]
    ${a_2}$${p_{2, 1} }$[(1, 2), (2, 2), (3, 2), (4, 2), (5, 2)]
    下载: 导出CSV

    表  2  单点多封堵类型路径规划结果

    Table  2  Solution of the single-site and multi-blocking

    机器人路径具体方案
    ${a_1}$${p_{1, 1} }$     [(3, 3), (3, 2), (3, 3), (3, 2), (3, 3), (3, 3), (3, 3), (3, 3), (3, 4), (3, 3), (4, 3)]
    ${a_2}$${p_{2, 1} }$     [(2, 3), (3, 3), (4, 3), (5, 3), (5, 4), (6, 4)]
    ${a_3}$${p_{3, 1} }$     [(1, 2), (1, 3), (2, 3), (3, 3), (4, 3), (5, 3), (5, 2), (5, 1)]
    ${a_4}$${p_{4, 1} }$     [(5, 2), (5, 3), (5, 3), (5, 2), (5, 3), (5, 4), (5, 3), (4, 3), (3, 3), (3, 2), (3, 1), (2, 1)]
    下载: 导出CSV

    表  3  多点多封堵类型路径规划结果

    Table  3  Solution of the multi-site and multi-blocking

    机器人路径具体方案
    ${a_1}$${p_{1, 1} }$ [(3, 3), (3, 3), (3, 4), (3, 4), (3, 4), (3, 4), (3, 3), (4, 3)]
    ${a_2}$${p_{2, 1} }$ [(1, 2), (1, 3), (2, 3), (3, 3), (3, 2), (3, 3), (4, 3), (5, 3)]
    ${a_3}$${p_{3, 1} }$ [(1, 3), (2, 3), (3, 3), (4, 3), (5, 3), (5, 2)]
    ${a_4}$${p_{4, 1} }$ [(1, 1), (1, 2), (1, 3), (2, 3), (3, 3),
    (4, 3), (5, 3), (5, 4), (6, 4)]
    下载: 导出CSV

    表  4  不同$N_{\rm{robot}}$规模对应的求解限制时间

    Table  4  Time limits for different sizes of $N_{\rm{robot}}$

    机器人个数 限制时间(s)
    $0 < {N_{\rm{robot}}} \le 50$ 150
    $50 < {N_{\rm{robot}}} \le 100$ 300
    ${N_{\rm{robot}}} > 100$ 500
    下载: 导出CSV

    表  5  实验I参数设置

    Table  5  Parameters for Experiment I

    地图类型$N_{\rm{robot}}$$\alpha$ (%)$\beta$ (%)$\omega $${R_L}$
    $8 \times 8$ grid1023.437520.408236000
    下载: 导出CSV

    表  6  实验I求解结果

    Table  6  Results of Experiment I

    算法路径总代价 (步)求解时间 (s)
    HCA*NANA
    CBSNANA
    CBS-DS62132.0
    WdSIPP $(w = 1.01)$NANA
    WdSIPP $(w = 1.75)$NANA
    B-IHCA*730.1
    下载: 导出CSV

    表  7  B-IHCA* 求解过程路径与冲突信息

    Table  7  Path and conflict information during the solving process of B-IHCA*

    求解阶段信息类型信息值
    顺序求解全约束路径${p_{1, 0} },{p_{2, 0} },{p_{5,0} },{p_{6,0} },{p_{7, 0} },{p_{9, 0} },{p_{10, 0} }$
    欠约束路径$p_{3, 0}^u,p_{4, 0}^u,p_{8, 0}^u$
    零约束路径$\emptyset $
    冲突机器人$({a_2},{a_3}),({a_2},{a_4}),({a_5},{a_8})$
    全约束路径${p_{1, 1}}$, ${p_{2, 1}}$, ${p_{3, 1}}$, ${p_{4, 1}}$, ${p_{5, 1}}$,
    ${p_{6, 1}}$, ${p_{7, 1}}$, ${p_{8, 1}}$, ${p_{9, 1}}$, ${p_{10, 1}}$
    讨价还价欠约束路径$\emptyset $
    第 1 轮零约束路径$\emptyset $
    冲突机器人$\emptyset $
    下载: 导出CSV

    表  8  实验II参数设置 (1)

    Table  8  The parameters for Experiment II (1)

    地图类型$\alpha $ (%)$R_L$
    $20 \times 20$ blocked-10 地图9.750010000
    $20 \times 20$ random-15 地图15.000015000
    $32 \times 32$ blocked-20 地图19.921915000
    $32 \times 32$ room 地图33.398415000
    下载: 导出CSV

    表  9  实验II参数设置 (2)

    Table  9  The parameters for Experiment II (2)

    $20 \times 20$ blocked-10 地图$20 \times 20$ random-15 地图$32 \times 32$ blocked-20 地图$32 \times 32$ room 地图
    $N_{\rm{robot}}$$\beta $ (%)$\omega $$N_{\rm{robot}}$$\beta$ (%)$\omega $$N_{\rm{robot}}$$\beta$ (%)$\omega $$N_{\rm{robot}}$$\beta$ (%)$\omega $
    205.54022154.41182303.65854101.46634
    4011.08034308.82355506.09765202.93265
    6016.620564513.23536708.53666304.39886
    8022.160766017.647169010.97566405.86518
    10027.700877522.0588811013.41468507.331410
    12033.241089026.47061013015.853710608.797712
    下载: 导出CSV

    表  10  算法路径质量统计

    Table  10  Path cost statistics of the tested algorithms

    地图类型$N_{\rm{robot}}$公共算例数平均总代价 (步)平均求解轮数
    CBSCBS-DSHCA*WdSIPP (1.01)WdSIPP (1.75)B-IHCA*公共算例非公共算例
    $20 \times 20$ blocked-102013263.1267.1273.0275.8281.5267.21.541.43
    4017NANA603.8604.9622.1591.91.411.67
    6019NANA933.2928.2969.5926.31.322.00
    8010NANA1340.91347.71392.31327.81.402.00
    1006NANA1731.31744.21820.71731.31.002.62
    $20 \times 20$ random-151518209.1211.1219.1220.1224.4213.71.501.00
    3018NANA473.0472.8488.2470.21.332.50
    4515NANA745.2745.1771.3737.51.272.25
    6011NANA1076.81072.31115.21055.91.912.22
    759NANA1391.21390.41437.41386.71.332.09
    $32 \times 32$ blocked-20306618.3626.2630.0655.7623.71.171.29
    5018NANA1237.21342.91311.61234.01.111.50
    7017NANA1781.51778.61881.81763.01.412.50
    9014NANA2396.92383.52538.52368.11.642.80
    1109NANA3010.33008.63190.32981.81.892.33
    1306NANA3596.33555.53757.73558.51.672.70
    $32 \times 32$ room1017248.7249.9253.1254.6264.2252.51.061.67
    206550.5566.5563.7585.8558.21.501.62
    3015NANA841.1838.5874.7830.81.402.00
    4014NANA1188.31174.51208.91175.61.431.83
    5011NANA1536.31528.31573.71512.41.912.43
    606NANA1891.51892.81949.71881.21.672.83
    下载: 导出CSV
  • [1] 施伟, 冯旸赫, 程光权, 黄红蓝, 黄金才, 刘忠, 等. 基于深度强化学习的多机协同空战方法研究. 自动化学报, 2021, 47(7): 1610-1623 doi: 10.16383/j.aas.c201059

    Shi Wei, Feng Yang-He, Cheng Guang-Quan, Huang Hong-Lan, Huang Jin-Cai, Liu Zhong, et al. Research on multi-aircraft cooperative air combat method based on deep reinforcement learning. Acta Automatica Sinica, 2021, 47(7): 1610-1623 doi: 10.16383/j.aas.c201059
    [2] Li J Y, Surynek P, Felner A, Ma H, Kumar T K S, Koenig S. Multi-agent path finding for large agents. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI). Hono lulu, USA: AAAI, 2019. 7627−7634
    [3] Yu J, LaValle S M. Optimal multi-robot path planning on graphs: Complete algorithms and effective heuristics. IEEE Transactions on Robotics, 2016, 32(5): 1163-1177 doi: 10.1109/TRO.2016.2593448
    [4] 李昆鹏, 刘腾博, 阮炎秋. 半导体生产车间智能AGV路径规划与调度. 计算机集成制造系统, 2022, 28(9): 2970-2980

    Li Kun-Peng, Liu Teng-Bo, Ruan Yan-Qiu. Research on intelligent AGV routing scheduling with applications in semi-conductor production. Computer Integrated Manufacturing Systems, 2022, 28(9): 2970-2980
    [5] Morris R, Pasareanu C S, Luckow K, Malik W, Ma H, Kumar T K S, et al. Planning, scheduling and monitoring for airport surface operations. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI). Phoenix, USA: AAAI, 2016. 608−614
    [6] Yu J J, LaValle S M. Structure and intractability of optimal multi-robot path planning on graphs. In: Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI). Bellevue Washington, USA: AAAI, 2013. 1443−1449
    [7] Wagner G, Choset H. Subdimensional expansion for multirobot path planning. Artificial Intelligence, 2015, 219: 1-24 doi: 10.1016/j.artint.2014.11.001
    [8] Han S D, Rodriguez E J, Yu J J. SEAR: A polynomial-time multi-robot path planning algorithm with expected constant-factor optimality guarantee. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Madrid, Spain: IEEE, 2018. 7967−7974
    [9] 段书用, 王启帆, 韩旭, 刘桂荣. 具有确保安全距离的A*路径优化方法. 机械工程学报, 2020, 56(18): 205-215 doi: 10.3901/JME.2020.18.205

    Duan Shu-Yong, Wang Qi-Fan, Han Xu, Liu Gui-Rong. Improved A-star algorithm for safety insured optimal path with smoothed corner turns. Chinese Journal of Mechanical Engineering, 2020, 56(18): 205-215 doi: 10.3901/JME.2020.18.205
    [10] Standley T, Korf R E. Complete algorithms for cooperative pathfinding problems. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI). Barcelona, Spain: AAAI, 2011. 668−673
    [11] Standley T. Finding optimal solutions to cooperative pathfinding problems. In: Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI). Atlanta, GA, USA: AAAI, 2010. 173−178
    [12] Sharon G, Stern R, Goldenberg M, Felner A. The increasing cost tree search for optimal multi-agent pathfinding. Artificial Intelligence, 2013, 195: 470-495 doi: 10.1016/j.artint.2012.11.006
    [13] Sharon G, Stern R, Felner A, Sturtevant N R. Meta-agent conflict-based search for optimal multi-agent path finding. In: Proceedings of the 5th Annual Symposium on Combinatorial Search (SoCS). Niagara Falls, Ontario, Canada: AAAI, 2012. 97−104
    [14] Sharon G, Stern R, Felner A, Sturtevant N R. Conflict- based search for optimal multi-agent pathfinding. Artificial Intelligence, 2015, 219: 40-66 doi: 10.1016/j.artint.2014.11.006
    [15] Ma H, Harabor D, Stuckey P J, Li J Y, Koenig S. Searching with consistent prioritization for multi-agent path finding. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI). New Orleans, USA: AAAI, 2018. 7643−7650
    [16] Li J, Harabor D, Stuckey P J, Ma H, Koenig S. Disjoint splitting for multi-agent path finding with conflict-based search. In: Proceedings of the 29th International Conference on Automated Planning and Scheduling (ICAPS). Berkeley, USA: AAAI, 2019. 279−283
    [17] Boyarski E, Felner A, Stern R, Sharon G, Tolpin D, Betzalel O, et al. ICBS: Improved conflict-based search algorithm for multi-agent pathfinding. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI). Buenos Aires, Argentina: AAAI, 2015. 740−746
    [18] Andreychuk A, Yakovlev K, Boyarski E, Stern R. Improving continuous-time conflict based search. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI). Virtually, USA: AAAI, 2021. 11220−11227
    [19] Silver D. Cooperative pathfinding. In: Proceedings of the 1st AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE). California, USA: AAAI, 2005. 117−122
    [20] Erdmann M A, Lozano-Pérez T. On multiple moving objects. Algorithmica, 1987, 2: 477-521 doi: 10.1007/BF01840371
    [21] Sharon G. Novel Search Techniques for Path Finding in Complex Environment [Ph.D. dissertation], Ben-Gurion University, Israel, 2015
    [22] Čáp M, Novák P, Kleiner A, Selecký M. Prioritized planning algorithms for trajectory coordination of multiple mobile robots. IEEE Transactions on Automation Science and Engineering, 2015, 12(3): 835-849 doi: 10.1109/TASE.2015.2445780
    [23] Li H, Long T, Xu G T, Wang Y J. Coupling-degree-based heuristic prioritized planning method for UAV swarm path generation. In: Proceedings of the Chinese Automation Congress (CAC). Hangzhou, China: IEEE, 2019. 3636−3641
    [24] Wu W Y, Bhattacharya S, Prorok A. Multi-robot path deconfliction through prioritization by path prospects. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA). Paris, France: IEEE, 2020. 9809−9815
    [25] Yakovlev K, Andreychuk A, Stern R. Revisiting bounded-suboptimal safe interval path planning. In: Proceedings of the 30th International Conference on Automated Planning and Scheduling (ICAPS). Nancy, France, USA: AAAI, 2020. 279−283
    [26] 李珣, 南恺恺, 赵征凡, 王晓华, 景军锋. 多智能体博弈的纺织车间搬运机器人任务分配. 纺织学报, 2020, 41(7): 78-87 doi: 10.13475/j.fzxb.20190800210

    Li Xun, Nan Kai-Kai, Zhao Zheng-Fan, Wang Xiao-Hua, Jing Jun-Feng. Task allocation of handling robot in textile workshop based on multi-agent game theory. Journal of Textile Research, 2020, 41(7): 78-87 doi: 10.13475/j.fzxb.20190800210
    [27] Wu H, Shang H. Potential game for dynamic task allocation in multi-agent system. ISA Transactions, 2020, 102: 208-220 doi: 10.1016/j.isatra.2020.03.004
    [28] 郑延斌, 王林林, 席鹏雪, 樊文鑫, 韩梦云. 基于蚁群算法及博弈论的多Agent路径规划算法. 计算机应用, 2019, 39(3): 681-687 doi: 10.11772/j.issn.1001-9081.2018071601

    Zheng Yan-Bin, Wang Lin-Lin, Xi Peng-Xue, Fan Wen-Xin, Han Meng-Yun. Multi-agent path planning algorithm based on ant colony algorithm and game theory. Journal of Computer Applications, 2019, 39(3): 681-687 doi: 10.11772/j.issn.1001-9081.2018071601
    [29] Kaduri O, Boyarski E, Stern R. Experimental evaluation of classical multi agent path finding algorithms. In: Proceedings of the 14th International Symposium on Combinatorial Search (SoCS). Guangzhou, China: AAAI, 2021. 126−130
    [30] Li J Y, Andrew T, Scott K, Durham J W, Kumar T K S, Koenig S. Lifelong multi-agent path finding in large-scale warehouses. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI). Virtually, USA: AAAI, 2021. 11272−11281
    [31] 万千. 基于CBS算法的物流分拣多AGV路径规划的研究 [硕士学位论文], 哈尔滨工业大学, 中国, 2018

    Wan Qian. Research on Multi-AGV Path Planning for Logistics Sorting Based on CBS Algorithm [Master thesis], Harbin Institute of Technology, China, 2018
    [32] Ma H. Target Assignment and Path Planning for Navigation Tasks With Teams of Agents [Ph.D. dissertation], University of Southern California, USA, 2020
    [33] Sturtevant N R. Benchmarks for grid-based pathfinding. IEEE Transactions on Computational Intelligence and AI in Games, 2012, 4: 144-148 doi: 10.1109/TCIAIG.2012.2197681
  • 加载中
图(13) / 表(10)
计量
  • 文章访问数:  626
  • HTML全文浏览量:  170
  • PDF下载量:  196
  • 被引次数: 0
出版历程
  • 收稿日期:  2022-01-25
  • 录用日期:  2022-09-09
  • 网络出版日期:  2022-11-02
  • 刊出日期:  2023-07-20

目录

    /

    返回文章
    返回