基于冲突搜索算法的多机器人路径规划

基于冲突搜索算法的多机器人路径规划

曹近者

广东建石科技有限公司  佛山市528000

摘要：随着电信平台近几十年的迅速发展，订单数量呈指数级增长，对仓库和物流系统的效率提出了越来越多的要求。此外，人工成本的上升使自动化和智能成为物流系统的趋势。在这方面，无人、智能、智能仓库成为物流领域的热点.自主移动式仓储机器人作为可完全替代人工的高效工具，成为智能仓储系统的研究热点.在基于多机器人系统的智能仓储领域，美国亚马逊、日本大福、国内兰剑智能、极智嘉、菜鸟物流、京东物流等知名电商和物流企业正在加速布局.本文对基于冲突搜索算法的多机器人路径规划进行分析，以供参考。

关键词：多机器人路径规划；双向搜索；路径规划；

引言

多机器人路径规划问题是一个NP-hard问题，通过给每个机器人规划出一条路径规避静态障碍物，保证机器人之间不会发生碰撞，并最小化总运行成本。传统方法是采用机器人单独规划方法，采用避障算法给每个机器人从起点到终点规划出最短路径。如果两个机器人发生碰撞，就采用一些简单的交通规则进行处理。这种方法适用于简单工作系统，一旦机器人数量增大，就会出现拥堵，从而导致整个系统的效率变低。

1基于冲突搜索算法简介

使用基于冲突的搜索算法解决多主体路径规划中的问题。该算法有一个双层结构，该结构在具有约束节点、所有智能体路径的解决方案和三个成本区域的两个树结构之后构建在更高的层次上。所有智能都通过一个集中的联网通信拓扑传输到每个智能体，这意味着每个智能体都可以访问其他智能体的全局信息。算法的顶层根据智能对象的全局路径信息确定智能对象之间是否存在路径冲突。检查解决方案中是否存在路径冲突，然后将两个子节点添加到OPEN优先级队列中，根据最佳优先级标识策略选择节点，添加相关性并展开节点，直到解决方案中不存在路径冲突。在所有非冲突节点中，选择成本最低的目标节点。目标节点是避免多智能冲突的最佳方法。该算法的底层使用A*路径规划算法为顶层节点提供符合约束条件的路径。

2动态环境下基于ＩＶＳ算法的多机器人路径规划

随着时间的推移，许多领域已开始应用移动机器人技术，特别是在路径规划方面。在生产领域，AGV用于车辆无人拣选的物资运输和快速出口中的机器人运输。根据生产要求利用环境，确保遵守标准的路径规划、建模、规划和执行过程。根据路径配置环境是否已知，可以将其分为全局和局部路径规划。根据路径配置环境中是否存在动态障碍，可以将它们分为静态路径计划和动态路径计划。改进a '算法，基于a '两级优化和动态窗口臂方法，通过一级或二级全局优化减少机器人路径的过渡次数，验证动态和静态环境的方法，确保有效的回避空间和路径规划；(a)提供一种改进算法，根据基于时间的烟草控制战略优化蚂蚁配置，以改进搜索弱点，并应用网格预测模型，解决与动态环境下殖民化路径规划有关的缓慢收敛、全球搜索能力不足和未知动态障碍等问题；提出了一种频带校正(MFB)算法，该算法在环境中无障碍物时生成机器人路径，并在检测到障碍物时打开第二种回避模式。提出的算法使规划路径缩短，过程中不发生碰撞。一种动态环境下移动机器人的前瞻性路径规划算法，基于移动机器人自身的速度和动态障碍，提出了简单的运动预测，加快了路径规划，降低了成本和发生冲突的可能性。在动态和未知环境中，介绍了一种基于蝗虫算法的路径规划新方法，与应用相比，在可用性、稳定性和效率方面效果良好。

3冲突搜索算法（CBS）

CBS算法为解决MAPF最优解算法。在CBS中，给机器人添加约束条件以解决两个机器人之间的碰撞。一个机器人的约束表示机器人

不能在时间t位于点v，或者机器人从时刻t到时刻t+1不能经过边v。机器人的连续路径是满足所有约束的路径，解决方案是仅由连续路径组成的解决方案。尽管机器人的各条路径都满足各自的约束条件，但机器人之间仍可能存在碰撞，满足约束条件的解决方案可能无效。因此，为了解决机器人之间的碰撞问题，CBS分为两个层次的搜索过程。在低层，其搜索过程与普通的路径规划方法类似，如Dirkstra、A*等，为每个机器人搜索出一条有效路径。但其不同之处在于：(1)、搜索过程中需要考虑额外的约束，即高层次搜索中添加的冲突。(2)、在搜索过程中需要考虑原地等待的情况。

4冲突搜索算法（ECBS）

4.1低层焦点搜索

在低层，ECBS为机器人寻找路径，给高层输出路径的总成本和最优路径成本的下界。低层列表中将节点n按常规启发式的值递增顺序进行排序。设*N为低层列表中最小节点，为指定次优因子。在低层焦点搜索开始时，低层列表只有根节点，因此根节点也为*N，函数最小值()为。低层焦点搜索还包含一个低层列表，列表中所有满足的节点N在该列表中。定义为机器人从起点移动到顶点v与其他机器人发生碰撞的次数。将低层列表中的节点优先按递增进行排序。

4.2改进型基于冲突搜索的MAPF算法

基于冲突的搜索(CBS)是一种分为顶部和底部搜索级别的两级算法。在顶层，将分别为每个机器人规划最短路径。然后创建一个双面冲突树(CT)，记录所有机器人路径上的所有时间冲突。然后，将约束套用至两个或多个机器人，这些机器人对应于在叉子上引起冲突的节点，并解决节点冲突。在较低级别上调用路径配置算法(例如B. A*、D*)以在CT条件下重新配置单个机器人路径。关于仓库系统，CBS是解决KIVA系统MAPF问题的高效算法。本文所称模型中的多负载机器人系统与KIVA系统明显不同，因此进行了有针对性的改进，以更好地解决pdpmlamrc（1) 所有机器人型号相同，参数相同; 2) 机器人在空载及不同负载下运行时速度不同; 3) 机器人直行及转向时速度不同; 4) 每件货物的拣货过程有且只有一个机器人执 行和完成; 5) 机器人被指派的货物数量不大于载位数量; 6) 不考虑机器人运行时产生的电能消耗; 7) 所有通道均为单行道; 8) 考虑机器人路径冲突.）问题。改进思路为：:1)通过设计与优先规则相结合的消除冲突战略，提高算法的效率，以寻找容易受到维数爆炸影响的较高级别的cbs；2)设计用于优化A*算法，根据多处理器计算机的多用途特性，从多用途多点触控机器人的角度优化单个机器人路径；3)引入低级搜索刑事程序，指示机器人减少因转换过多而造成的路径时间.

结束语

综上所述，随着智能化仓储快速发展，基于KIVA的“货架到人”模式已无法满足拣选需求.针对这一现象,本文提出一种基于MLAMR（Step 1. 确定每个机器人的优先级；动态规划算 法确定单机器人拣货顺序； Step 2. 改进型A*算法搜索单机器人最优路径； Step 3. 生成多机器人路径冲突树； Step 4. 基于优先级的冲突消解；）“货箱到人”模式的新型拣选-配送MAPF问题,建立数学规划模型,设计一种PCBS（为O(t 2 + n 2 ).）算法进行优化求解.在PCBS高层搜索上,提出一种MLAMR优先级规则,并基于该规则设计冲突消解策略.

参考文献

[1]尹天懿.基于航迹的飞行冲突探测与解脱算法的研究[D].中国民航大学,2016.

[2]韩佳.基于可重构计算硬件的HEVC运动估计算法实现技术研究[D].上海交通大学,2016.

[3]吴彪.基于EFSM的测试用例自动生成方法的研究[D].浙江理工大学,2018.

[4]赵斌,何泾沙,黄娜,屈会芳,刘公政.基于扁平N叉树搜索的RFID防冲突算法[J].北京邮电大学学报,2019,37(05):50-55.