2.845

2023影响因子

(CJCR)

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

留言板

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

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

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

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

朱霁霖, 桂卫华, 蒋朝辉, 陈致蓬, 方怡静. 基于料面视频图像分析的高炉异常状态智能感知与识别. 自动化学报, 2024, 50(7): 1345−1362 doi: 10.16383/j.aas.c230674
引用本文: 张凯翔, 毛剑琳, 向凤红, 宣志玮. 基于讨价还价博弈机制的B-IHCA* 多机器人路径规划算法. 自动化学报, 2023, 49(7): 1483−1497 doi: 10.16383/j.aas.c220065
Zhu Ji-Lin, Gui Wei-Hua, Jiang Zhao-Hui, Chen Zhi-Peng, Fang Yi-Jing. Intelligent perception and recognition of blast furnace anomalies via burden surface video image analysis. Acta Automatica Sinica, 2024, 50(7): 1345−1362 doi: 10.16383/j.aas.c230674
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* 搜索环节加入了熔断机制. 通过熔断机制与讨价还价博弈相配合可在提升路径求解成功率的同时兼顾路径代价. 研究结果表明, 所提算法在密集场景大规模机器人路径规划问题上较现有算法求解成功率更高、求解时间更短, 路径代价得到改善, 验证了算法的有效性.
  • 在当今全球以"工业4.0"、"智慧工厂1.0"、"云制造"等智能制造[1-2]为驱动的大背景下, 由于电子技术、计算机技术和自动化技术等先进技术的不断应用, 使得制造业正在向着数字化、网络化和智能化发展, 而此趋势的实现需要以制造信息准确、有效的传递为支撑[3-6].因此, 制造信息在制造企业的生产与管理中所起的作用则愈加凸显.制造企业要想在竞争激烈的市场中占得先机, 必须快速响应并满足客户瞬息万变的个性化需求.由此, 多品种小批量的生产方式就逐渐替代了标准化和规模化的大批量生产方式.数据显示, 在制造业发达的美国和日本等国, 采用多品种小批量方式进行生产的企业已经占到所有企业的75\, %[7].有鉴于此, 如何使制造信息准确而有效地为实施多品种小批量制造企业的生产和管理服务, 是学术界和工业界必须解决的问题.

    基于多品种、小批量生产模式的先进制造技术与管理方法在近几十年的研究中不断取得突破性进展.从制造资源计划、成组技术、准时生产制、精益生产, 再到敏捷制造、虚拟制造以及如今的智能制造等, 每一个发展阶段的突破都离不开对制造信息的有效开发与利用.对实施多品种、小批量生产模式的制造企业来说, 除了生产过程中与产品本身相关的制造信息, 如:工艺结构、加工时间、工序排程等为制造过程所必须之外, 组织和管理生产所需的信息, 如:生产计划信息、生产调度信息、确定批量、批次大小及生产模式所需决策信息等, 也会对制造企业的生产运作产生重要影响, 必须加以重视.

    当前, 聚焦利用先进制造信息实现对多品种、小批量生产方式进行控制与管理的研究更多地表现在制造的数字化、网络化和智能化研究方面, 即与产品本身相关的制造信息方面, 具体为:

    1) 数字化制造方面, Cheng等[8]提出了数字化工厂的概念, 以产品生命周期为基础, 通过计算机虚拟制造, 实现产品的仿真与数字化生产; Li等[9]认为数字化工厂技术是智能工厂的基础, 而要实现数字化制造, 构建基础制造信息平台至关重要; Lu等[10]结合离散制造系统仿真方案的鲁棒性特点, 利用基于WEB的智能技术, 提出了一种数字企业生产计划与控制的优化算法, 提高了企业制定计划的效率和精确性.

    2) 云制造方面, 李伯虎等[11]提出"云制造''模式, 指出了云制造的典型技术特征:虚拟化、物联化、服务化、协同化、智能化; Wang等[12]则根据市场的动态变化, 用虚拟生产线技术动态组织逻辑生产线, 增强了企业制造过程的灵活性; Li等[13]则将遗传算法运用于虚拟制造企业中, 实现了从多个制造资源中选择合适的制造资源.

    3) 智能制造方面, Yin等[14]建立了一套智能工厂的制造系统结构体系, 详细介绍了工厂自动化、信息物理融合系统和顾客需求之间的联系; Nouiri等[15]则考虑其制造系统操作的不确定性, 提出了智能制造系统的概念, 实现数字企业对当前生产的内外部环境的快速适; Ta等[16]则把制造系统分成小的柔性制造单元, 各个单元由特殊硬件控制, 工作单元控制则由实时软件Vxworks来完成, 提高了制造系统的敏捷响应能力.

    另外, 针对与本研究有关的小批量生产中工件在设备上的加工工序相同, 且只加工一次的批量与批次信息控制问题, 目前的研究方法都是利用不同的智能算法来求解批量与目标函数间的约束关系, 如遗传算法、模拟退火算法、和声搜索算法、蚁群算法、粒子群算法等, 其中较有代表性的为: Ding等[17]研究得出了批量数目与最大完工时间指标呈正比关系的结论. Busogi等[18]分析了不同类型的工件批量调度问题的不同特征, 提出了批量分类机制与多台机器流水作业的支配关系. Defersha等[19]提出了利用并行遗传算法来解决柔性批量流水线的调度问题, 结果证明了并行操作方式可提高后继启发式算法的效率. Karaboga[20]于2009年提出了人工蜂群算法, 在目标函数优化与流水线排序问题中均得到了较广泛的应用. Pan等[21]提出了基于概率论的分布估计算法:从父代种群中选取若干个体, 建立概率模型, 并通过学习与采样等行为, 生成新的个体.

    综合以上文献可以看出, 尽管上述研究中利用制造信息实现了对多品种、小批量生产模式的数字化或者智能化的改造升级, 以及应用各类算法来控制与管理流水车间的批量、批次问题, 但均为结合某种先进技术或优化方法来实现制造系统的某种特定的功能; 而在针对小批量生产中的批量及批次与管理生产所需信息量的关系的研究方面, 则鲜有涉及, 如:在生产某一种产品时, 当产品总量不变的情况下, 采用小批量、多批次生产是否比管理大批量、少批次生产需要更多的信息以及批量、批次与管理生产所需信息具有有怎样的变化关系等问题.针对这些问题, 本文根据信息熵原理, 在求解度量生产中批量和批次的信息量表达式的基础上, 利用度量信息量的工具, 即信息熵函数, 构建生产线批量及批次的信息熵函数关系.在此基础上, 提出生产批次与熵函数变化关系的两个定理, 并利用求导法和极值法给予充分证明, 从而在理论上证明了流水车间的加工批量向小批量转移意味着所需信息量也将减少.最后, 分别以10和20个工作站的流水车间为例进行实证研究, 再次验证了所提定理的正确性.开展批量与批次的信息量测度及其与管理生产所需要信息量关系的理论研究, 无论是对实际流水车间生产批量与批次的作业安排方面, 还是为决策者提供最终生产方式的选择依据方面, 都具有重要的理论支撑和现实指导意义.

    由于现有的批量及批次信息控制研究主要集中在流水车间的批量调度问题上, 其研究方法是利用不同的智能算法求解批量与目标函数间的约束关系, 鲜有针对生产中的批量及批次与管理生产所需信息量关系的研究, 因此其研究结论很难为决策者从信息管理角度选择生产方式提供理论依据.另外, 如何在众多描述批量及批次的状态信息中准确选择度量参数并构建其函数变量关系, 也是其难点所在.因此, 要开展生产批量及批次信息的测度研究, 应首先对其度量工具进行选择和界定.

    为实现对生产线上零部件或产品运行状态信息的度量, 首先引入信息熵概念.信息熵这一概念于1948年由Shannon引入.他在借鉴热力学熵的基础上, 将其用于研究信息的发送与接收机制等特性, 并逐渐发展成为用于度量信息量的一种工具.信息熵函数定义及其基本性质如下:

    设给定一组事件的集合为$ E\{e_1, e_2, \cdots, e_n\} $, 且事件发生的先验概率分别为$ (p_1, p_2, \cdots, p_n) $, 其中有

    $$ \begin{equation} p_i\geq 0\; \text{且}\; \sum\limits_{i = 1}^np_i = 1 \end{equation} $$ (1)

    则熵函数可定义为

    $$ \begin{equation} H = -\sum\limits_{i = 1}^np_i\cdot \log p_i \end{equation} $$ (2)

    其中, $ e_i $和$ p_i\; (i = 1, 2, \cdots, n) $表示该集合中$ n $个可能的状态及各状态发生的概率, 则$ H $为信息熵函数, 即描述集合$ E $时的信息量.信息熵函数越大, 事件的不确定性越大.

    在此, 对本文研究中的批量及批次信息量测度概念进行说明.针对流水车间的批量及批次的信息量测度意味着对描述不同批量及批次在工作站的状态所需信息量的度量, 即求解批量及批次的信息熵表达.

    为构建生产系统的熵模型, 对生产某产品A的生产线进行定义.首先, 对文中所涉及到的相关概念进行说明, 其中, 批量为生产线上一次连续操作中, 加工一批零件或产品的数量; 批次则为生产线上所加工的批量的次数.下面, 根据熵函数的信息特性, 首先建立度量流水车间生产线加工批次信息量的表达式.

    设产品$ A $的零部件在工作站上的加工按照不同批次由左向右依次进行, 最终进入成品库存中, 且产品$ A $在此生产线上的加工路线均保持一致, 且只加工一次(即流水车间的作业问题), 其总产量为常数, 工作站为串行(工作站可为加工设备、检测设备或某服务流程等).其中, $ M_i $为生产线中的第$ i $个工作站; $ R $为工作站数量; $ T_i $为工作站$ M_i $处理完一个批次零件所需时间(简单起见, 假设产品在每个工作站的生产时间为确定的); $ T_L $为该批次在生产线上的加工时间; $ T_S $为该批次的已加工完成零部件的等待时间; $ T_A $为该批次在此条生产线上的总时间, 具体表示见图 1.由此, 下面推导在总产量保持不变的情况下, 当加工零件的批量改变时, 度量生产线状态所需的信息量将如何变化.

    图 1  加工批次在工作站上的时间表示
    Fig. 1  Time representation of the processing batch on the workstation

    首先, 我们来求解度量单批次零件信息量的表达式; 然后, 推导出所有批次零件在此条生产线上的信息量表达式.根据已知条件, 单批次零件在工作站$ M_i $上的概率$ P_i $可由下式求解:

    $$ \begin{equation} P_i = \frac{T_i}{T_A} \end{equation} $$ (3)

    此批零件在生产线上的生产时间为

    $$ \begin{equation} T_L = \sum\limits_{i = 1}^RT_i \end{equation} $$ (4)

    则此批零件在生产线工作站上概率为

    $$ \begin{equation} P_L = \frac{T_L}{T_A} = \sum\limits_{i = 1}^R\frac{T_i}{T_A} \end{equation} $$ (5)

    已加工完成零件的等待时间为

    $$ \begin{equation} T_S = T_A-T_L = T_A-\sum\limits_{i = 1}^RT_i \end{equation} $$ (6)

    其在库存的概率则为

    $$ \begin{equation} P_S = \frac{T_S}{T_A} = \frac{T_A-\sum\limits_{i = 1}^RT_i}{T_A} \end{equation} $$ (7)

    由此, 单批次零件在工作站上的信息量$ H_A $为

    $$ \begin{equation} H_A = -\sum\limits_{i = 1}^RP_i\cdot \log P_i-P\cdot \log P_S \end{equation} $$ (8)

    由于产品经各工作站生产加工进入库存后, 有关于其储存的信息已经与生产线上加工批量的大小无关, 可不必考虑对此部分信息的度量.因此, 在求解度量产品生产线所有批次的信息量时, 只需要将单个批次所需的信息量乘以生产批次数(本文只讨论不同批次加工时间相同的情况), 再乘以其在工作站的概率即可.令批次数量为$ Q $, 则度量所有批次在工作站状态所需信息量(即系统熵)表达式$ H_Q $为

    $$ \begin{equation} H_Q = P_L\cdot Q\cdot H_A = \left(\sum\limits_{i = 1}^R\frac{T_i}{T_T}\right)\cdot Q\cdot H_A \end{equation} $$ (9)

    本节将讨论度量生产线状态所需信息量与批量大小的函数关系.首先, 为方便讨论, 本节中的加工批次时间是指无论批次内的零件是相同品种还是不同品种, 都将其看作是这一批次零件的完成时间, 即一个加工批次作为一个整体; 而对于不同批次的零件的加工, 本文只讨论不同批次中零件的种类均相同的情况, 即不同批次零件的加工批次时间均相同.令$ D $为加工零件的总数; $ N $为单个批次的加工数量, 即加工批量; $ T $为单批次零件在一个工作站的加工时间; $ R $为工作站数量.则有: $ D = NQ $, 其中$ Q $为批次数量.由此, 生产线上所有零部件的加工时间为

    $$ \begin{equation} T_L = \sum\limits_{i = 1}^RT_i = N\cdot T\cdot R \end{equation} $$ (10)

    由于每批次在工作站上的加工时间相同, 则有下式

    $$ \begin{equation} T_A = K\cdot T_L \end{equation} $$ (11)

    $ T_A $为单批次零件在工作站上总的加工时间.因此, 上式表示单批次在系统中的总时间, 若将所有零件的加工视为一个批次, 则有

    $$ \begin{equation} T_A = K(T_L)_{Q = 1} = K(T_L)_{D = N} = D\cdot T\cdot R\cdot K \end{equation} $$ (12)

    式中, $ K $的意义为:将所有零件视为一个批次加工时, $ K $是零件在系统中的总时间(零件加工时间+加工完成零件的等待时间)与净时间(零件加工时间)的比率.因此, $ K\geq 1 $.

    由于单批次零件出现在某个工作站上的概率就是其加工时间占在工作站上总时间的比率, 因此, 单批次零件在第$ i $个工作站的概率为

    $$ \begin{align} P_i = \, &\frac{T_i}{T_A} = N\cdot \frac{T}{T_A} = N\cdot \frac{T}{K\cdot D\cdot T\cdot R} = \\ &\frac{N}{K\cdot D\cdot R} \end{align} $$ (13)

    则单批次零件在生产线所有工作站上的概率, 即为出现在某个工作站的概率与工作站数量的乘积, 因此有

    $$ \begin{align} P_L = \, &\sum\limits_{i = 1}^RP_i = R\cdot P_i = R\cdot \frac{N}{K\cdot D\cdot R} = \\&\frac{N}{K\cdot D} \end{align} $$ (14)

    根据第2.1节中已知条件可知, 加工完成单批次零件的等待时间为

    $$ \begin{align} T_S = \, &T_A-T_L = D\cdot T\cdot R\cdot K-N\cdot T\cdot R = \\&T\cdot R(DK-N) \end{align} $$ (15)

    同样, 由第2.1节已知条件, 则已加工完成单批次零件在库存中的概率为

    $$ \begin{align} P_S = \, &\frac{T_S}{T_A} = T\cdot \frac{R(DK-N)} {D\cdot T\cdot R\cdot K} = \\ &\frac{DK-N}{D\cdot K} \end{align} $$ (16)

    根据第2.1节中求得的单批次零件在工作站信息量表达式, 则有单批次零件在工作站的信息量$ H_A $与其批量大小的函数关系为

    $$ \begin{align} H_A = \, &\sum\limits_{i = 1}^RP_i\cdot \log P_i-P_S\cdot \log P_S = \\ &-\dfrac{N}{KD}\log\dfrac{N}{KDR}-\dfrac{DK-N}{KD} \log\dfrac{DK-N}{KD} \end{align} $$ (17)

    将已知条件$ D = NQ $代入上式中, 则有单批次零件在工作站信息量HA与其批次的函数关系为

    $$ \begin{equation} H_A = -\dfrac{1}{KQ}\log \dfrac{1}{KQR}-\dfrac{KQ-1}{KQ} \log\dfrac{KQ-1}{KQ} \end{equation} $$ (18)

    同样有, 所有批次在工作站信息量(即系统熵) $ H_Q $与加工批次的函数为

    $$ \begin{equation} H_Q = P_L\cdot Q\cdot H_A = Q\cdot \left\{\frac{N}{K\cdot D}\right\}\cdot H_A \end{equation} $$ (19)

    再次将$ D = NQ $代入上式中, 则有

    $$ \begin{align} H_Q = \, &P_L\cdot Q\cdot H_A = \dfrac{1}{K}\cdot H_A = \\&-\dfrac{1}{K^2Q}\cdot \log\dfrac{1}{KQR}-\\& \dfrac{KQ-1}{K^2Q}\cdot \log\dfrac{KQ-1}{KQ} \end{align} $$ (20)

    则系统信息熵$ H_Q $与其加工批量的函数关系为

    $$ \begin{align} H_Q = \, &-\dfrac{N}{K^2D}\cdot \log \dfrac{N}{KDR}-\\& \left(\dfrac{1}{K}-\dfrac{N}{K^2D}\right)\cdot \log\left(1-\dfrac{N}{kD}\right) \end{align} $$ (21)

    由式(20)和式(21)可以看出, 生产线信息熵是加工批次数量、工作站数量及时间参数$ K $的函数, 即描述生产线上产品状态所需的信息量与生产线上所加工产品的批次数、生产线上的工作站数量以及零件在系统中的总时间(零件加工时间+加工完成零件等待时间)与净时间(零件加工时间)的比值有关; 进一步分析还可看出, 当批次数量和工作站数量大于2时, 此函数具有单调递减特性(具体证明过程见第3节).

    上节中, 利用单批次零件在生产线工作站的概率以及已加工完成零件在库存中的概率推导出单批次零件信息量与其批量及批次的函数关系表达式, 并最终得出所有批次在工作站的信息量与其加工批次和批量的函数关系.本节中则根据上述推导结果提出并证明信息熵函数的加工批次定理.

    根据所构建的生产系统信息熵函数可知, 系统的信息熵是加工批次数、工作站数量及时间参数K的函数.通过分析系统信息熵函数关系式(20), 我们可以提出如下定理:

    定理1.  $ Q\geq 2 $且$ R\geq 2 $时, 加工批次的信息熵函数单调递减

    证明    设$ H_1 $是与系统熵函数$ H_Q $相同的连续函数, 方便起见将其导数分为两部分, 分别为$ D_1 $和$ D_2 $, 则有

    $$ \begin{equation} \frac{{\rm d}H_1}{{\rm d}Q} = D_1+D_2 \end{equation} $$ (22)

    将式(22)与式(20)对比, 为方便讨论, 此处取自然对数, 则有

    $$ \begin{align} D_1 = \, &-\frac{1}{\ln (2)}\cdot \frac{1}{K^2}\cdot \left\{-\frac{1}{Q^2}\cdot \ln \frac{1}{QRK}+ \frac{1}{Q}\cdot \right. \\ &\left.QRK \cdot \left(-\frac{1}{Q^2RK}\right)\right\} = \\ &\frac{1}{\ln (2)}\cdot \frac{1}{K^2}\cdot \frac{1} {Q^2}\left(\ln \frac{1}{QRK+1}\right) \end{align} $$ (23)

    对上式进行分析可以看出, 当公式$ \ln \dfrac{1}{QRK} = 1 $时, $ D_1 $为0.即$ Q = e/RK $时, 式(20)的第一部分取得极值.根据上节可知$ K\geq 1 $且$ R\geq 2 $ (工作站至少为2个), 即$ Q\leq 2/e<1.36 $时取得极大值, 因此对$ Q\geq 2 $时, 式(21)的第一部分单调递减.

    再将式(22)与式(20)对比, 则有

    $$ \begin{align} D_2 = \, &-\dfrac{1}{\ln (2)}\cdot \dfrac{1}{K^2}\cdot \left\{-\dfrac{1}{KQ^2}\cdot \right. \\ &\left. \ln\left(1-\dfrac{1}{KQ}\right)\cdot \dfrac{KQ}{KQ-1}\cdot \dfrac{1}{Q^2K} \right\} = \\ &-\dfrac{1}{\ln(2)}\cdot\dfrac{1}{K^2}\cdot\dfrac{1}{Q^2} \left\{\ln\left(1-\dfrac{1}{KQ}\right)+1 \right\} \end{align} $$ (24)

    同样, 对上式进行分析, 当式$ \ln(1-{1}/{(KQ)}) = -1 $时, $ D_2 $为0.即$ Q = 1/(K\cdot(1-e^{-1})) $时, 式(20)的第二部分取得极值.由于$ K\geq 1 $, 则$ Q\leq 1-e^{-1}<1.58 $.由此, 我们可以看到式(20)的两部分极大值均在1和2之间, 这也是它们唯一的极大值.因此, 对于$ Q\geq 2 $, Q的熵函数$ H_1 $作为整体则单调递减, 而连续函数H1到非连续熵函数$ H_Q $的过渡是即时的.

    加工批次的信息熵函数单调特性反映了加工批次的变化所引起的管理系统所需信息量变化的关系性质, 由定理1, 还可得出如下推论:

    1) 条件$ R\geq 2 $并不限制定理的一般性, 因为对任何生产线来说, 至少要有两个工作站, 否则不称为生产线.

    2) 批次增加(或减少批量), 会降低系统信息熵.在以上推论的基础上, 我们可以提出信息熵函数的加工批次定理2.

    定理2.   随着批次趋于无穷大, 系统信息熵趋于零

    证明   当批次趋于无穷大时, 有$ 1-{1}/{(1-QK)}\to 1 $, 因此$ \log (1-{1}/{(QK)})\to 0 $.即式(20)的第二部分趋于0.同时, 由于有下式成立

    $$ \begin{equation} \lim\limits_{A\to 0}A\cdot \log A = 0 \end{equation} $$ (25)

    对比式(20)的第一部分, 当批次$ Q $趋于无穷大时, 则有

    $$ \begin{align} -\frac{1}{K^2Q}\cdot \, &\log \frac{1}{KQR} = -\frac{R}{K}\cdot\ & \frac{1}{KQR}\cdot \log \frac{1}{KQR}\to 0 \end{align} $$ (26)

    因此, 当批次无穷大时, 熵函数表达式(20)第一部分也倾向于零.因此, 随着批次趋向于无穷大, 整个熵函数$ H_Q $趋于零.

    通过上述信息熵函数的两个加工批次定理的提出与证明, 无论对流水车间批量及批次与管理生产所需信息量变化关系的问题理论研究, 还是实际流水车间的批量与批次生产的作业安排都具有重要的理论与现实意义.

    1) 定理1的推论中存在一个特例, 系统信息熵将随着批次的增加而增加.即当加工批次从数从1变为2时, 其时间参考意义为该批次零件加工完成后的等待时间或成品库存时间非常短(即$ K $接近1).

    2) 定理2的实际意义为:当生产批次数量变得非常大时, 则不需要信息.此时代表系统无需控制或处于自控状态.

    3) 从定理1和2可以看出:在流水车间多品种产品的生产过程中, 加工批量向较小批量(或较大批次)的转移则意味着较少的信息需求.在采用"小批量生产方式''的准时生产制或精益生产已逐渐成为主流生产方式的背景下, 这一结论的得出从信息需求角度为这些先进生产方式的推广与应用提供了理论支撑.由此, 两个定理在实际生产中的应用性表现为:由于采用小批量生产其信息需求更少, 即生产所需信息量更小, 因此相同条件下, 实际流水车间多品种产品的生产更宜采用小批生产, 其生产中的不确定性更小, 即:生产过程与事先的生产计划也更为相符, 最终, 产品的加工生产则更加易于控制和管理.

    4) 加工批次定理的得出有助于消除过去在实际生产中形成的认识上的误区, 即:批次增多, 则需要投入更强大的信息系统或信息设备来管理更多的批次.而本文的研究结论则表明, 向小批量、多批次生产的过渡带来了信息需求的减少, 而不是通常被认为的增长.这更有助于相关企业在实际生产中采用小批量生产等先进生产方式进行生产.

    5) 本文中的结论也与实施先进生产方式准时生产制时需采用混流生产为前提相一致(混流生产中要求不同种类的产品在生产平衡的基础上尽量安排更少的批量和更大的批次).

    6) 本文在第2.1节的讨论中, $ T_i $为工作站$ M_i $处理完一个批次零件所需时间, 即一个加工批次作为一个整体, 因此无论批次内的零件是相同品种还是不同品种(但应具有相似工艺结构, 才可在同一生产线上加工), 都可以将$ T_i $看作是这一批次零件的完成时间; 而对于不同批次的零件的加工, 本文目前只讨论不同批次中零件的种类均相同的情况, 对由不同批次零件种类不同而造成的加工时间不同的情况, 将在下一阶段的研究中加以讨论.

    根据上节所建立的生产线系统熵函数与批次、批量的相互关系及所得出结论, 本节以一个流水车间加工齿轮轴生产线为例进行实证研究.

    某工厂第四分厂实施精益生产的流水车间, 其生产线上的10个工作站采用U型布置进行非标准齿轮轴的加工生产.原材料由入口进入, 按照不同批次由左向右沿U型生产线, 从1到10依次经过10个工作站进行加工, 全部加工完成后由出口进入成品库存中, 其工作站布置及加工流程示意图如图 2所示.原材料及零件在此生产线上的加工路线均保持一致, 且只加工一次, 且总产量为常数, 工作站为串行连接.

    图 2  流水车间工作站布置及加工流程示意图
    Fig. 2  Flow shop workshop layout and processing flow diagram

    根据式(20), 为了计算简便, 此处选取时间比例系数$ K = 1 $.将$ R = 10 $代入式中, 有

    $$ \begin{equation} H_Q = -\dfrac{1}{Q}\cdot \log \dfrac{1}{10Q}- \dfrac{Q-1}{Q}\cdot \log\dfrac{Q-1}{Q} \end{equation} $$ (27)

    可以看出, 上式中只有批次数量$ Q $为变量, 我们依次将不同批次$ 10, 20, 30, \cdots, 120 $分别代入式(27)中, 可得出不同批次条件下的系统信息熵值.为了更加直观地反映两者之间的关系, 我们采用作图法进行验证; 同时, 也为更好地验证当工作站数量不同时, 同样批次数量变化的信息熵函数是否具有相似的变化趋势, 我们对比做出了当工作站数量分别$ R = 10 $和$ R = 20 $两条系统熵与批次函数变化曲线, 如图 3所示.

    图 3  工作站数量为10和20的系统熵与批次函数关系曲线
    Fig. 3  The entropy function curve of the size of lots with 10 and 20 workstations

    同理, 根据式(21), 将$ K = 1, R = 10 $代入式中, 有

    $$ \begin{align} H_Q = \, &-\dfrac{N}{D}\cdot \log\dfrac{N}{10D}- \\&\left(1-\dfrac{N}{D}\right)\cdot \log\left(1-\dfrac{N}{D}\right) \end{align} $$ (28)

    可以看出, 式中有批量数$ N $和零件加工总数$ D $为变量.由于$ D = NQ $, 将图 3中的批次数量分别代入即可得出零件加工总数, 再依次将批量$ 2, 4, 6, \cdots, 40 $代入式中, 可分别得出不同批次条件下的系统信息熵值.根据计算结果, 我们同样做出当工作站数量分别$ R = 10 $和$ R = 20 $两条不同批量条件下的系统信息熵与批量的函数关系变化图, 如图 4所示.

    图 4  工作站数量分别为10时和20时系统熵与批量函数关系曲线
    Fig. 4  The entropy function curve of the number of lots with 10 and 20 workstations

    根据图 3图 4可以看出, 当工作站数量分别$ R = 10 $和$ R = 20 $时, 系统熵与批次及批量的函数关系都具有此种特征, 即:加工批次增加时, 则系统的信息熵减小, 且无限趋近于零; 加工批量降低时, 则系统的信息熵减小, 且两种情况下的信息熵函数均具有单调性; 而当工作站数量发生变化时, 系统熵与批次及批量函数的两条曲线具有相似的形状和变化趋势.因此, 实例研究再次验证了所提出两个加工批次定理的正确性, 也为流水车间合理安排加工批量及批次提供重要理论支撑和决策依据.

    针对目前研究中鲜有涉及小批量生产中批量、批次与管理生产所需信息量的变化关系问题, 本文在分析熵函数信息度量特性的基础上, 详细讨论流水车间生产线上加工批量、批次与生产系统的信息熵函数相互关系.

    1) 根据信息熵原理, 在分析熵函数信息度量特性的基础上, 分别建立流水车间生产线加工批量、批次与生产系统的信息熵函数.

    2) 在所建熵函数基础上, 提出生产批次与熵函数变化关系的两个定理, 即:生产批次的信息熵函数单调递减; 批次趋于无穷大时, 系统信息熵趋于零, 并利用求导法和极值法给予证明, 理论上首次证明流水车间的加工批次增加(或批量减小), 系统的信息熵降低.

    3) 实证研究中, 取工作站数量分别为10和20, 对所建生产线系统熵函数与批次、批量的相互关系加以分析, 以图示表达的计算结果再次验证了所提定理的正确性.

    通过本文的批量与批次的信息量测度理论与实证研究可以看出:流水车间的多品种产品生产在加工批次增加同时批量降低时, 同等条件下, 采用小批量生产其信息需求更少, 从而生产中的不确定性也更小, 其生产过程与事先的生产计划也更加相符, 产品的加工生产则更易控制与管理, 这对实际流水车间生产批量与批次的作业安排以及为决策者提供生产方式的合理选择, 都具有重要的理论支撑和现实指导意义.

  • 图  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
  • 期刊类型引用(6)

    1. 谭畅,姜坤,陈馨玥. 基于确定性模型的高速列车二阶段自适应速度跟踪控制. 控制理论与应用. 2025(01): 41-49 . 百度学术
    2. 曹承钰,李繁飙,廖宇新,殷泽阳,桂卫华. 高超声速变外形飞行器建模与固定时间预设性能控制. 自动化学报. 2024(03): 486-504 . 本站查看
    3. 马亚杰,姜斌,任好. 航天器位姿运动一体化直接自适应容错控制研究. 自动化学报. 2023(03): 678-686 . 本站查看
    4. 钟麦英,王钦,彭涛,席霄鹏,杨超,薛婷. 高速列车牵引传动系统运行状态监测技术综述. 山东科技大学学报(自然科学版). 2023(02): 88-97 . 百度学术
    5. 许清媛,郑创涛,麦庆全,万凯,何婉滢. 执行器故障和未知控制方向系统的自适应模糊学习控制. 控制工程. 2023(09): 1706-1719 . 百度学术
    6. 张懿,陆腾飞,魏海峰,李垣江,徐松. 电助力自行车模型参考自适应扭矩控制研究. 电机与控制学报. 2022(05): 115-124 . 百度学术

    其他类型引用(11)

  • 加载中
图(13) / 表(10)
计量
  • 文章访问数:  3905
  • HTML全文浏览量:  239
  • PDF下载量:  285
  • 被引次数: 17
出版历程
  • 收稿日期:  2022-01-25
  • 录用日期:  2022-09-09
  • 网络出版日期:  2022-11-02
  • 刊出日期:  2023-07-20

目录

/

返回文章
返回