1.一种基于改进冲突搜索法的多机器人路径规划方法,其特征在于,包括:S1、改进A*算法;将机器人的工作类型分为空载和负载两种类型,对空载机器人的行走路径进行改进,使空载机器人优先选择货架下的路径;
S2、引入优先级导向搜索改进CBS算法;根据机器人的工作类型、冲突类型和避让策略三个条件对优先级进行划分,后针对点冲突与边冲突的不同情形,提出消解策略,确定扩展节点数以及优先导向;其中,所述冲突类型包括点冲突和边冲突,所述避让策略包括等待和路径重新规划;
S3、结合S1中的改进A*算法以及S2中的优先级导向搜索的改进CBS算法确定多机器人路径规划流程。
2.根据权利要求1所述的基于改进冲突搜索法的多机器人路径规划方法,其特征在于,所述S1还包括:确定多机器人冲突类型,将追尾冲突、侧向冲突、对向冲突和占位冲突四种情形归纳为点冲突与边冲突。
3.根据权利要求2所述的基于改进冲突搜索法的多机器人路径规划方法,其特征在于,所述S2中的引入优先级导向搜索改进CBS算法具体包括:S21、设置算法的总代价为解决方案中所有机器人路径的总时间并确定优先级导向搜索的方向为代价值增加较小的方向;
S22、按照机器人的工作类型、冲突类型和避让策略三个条件对优先级进行划分;
S23、针对不同避让策略使得代价值的增加进行分析;等待策略为机器人在原地等待,带来代价的增加;路径重新规划的代价是否增加受到机器人的起始点和目标点影响;
S24、针对不同机器人工作类型影响代价值的增加进行分析;
S25、根据单最短路径负载机器人、单最短路径空载机器人、多最短路径负载机器人、多最短路径空载机器人四种不同优先级的机器人,进行两两组合以及考虑同等优先级机器人发生冲突,确定多种点冲突的情形;
S26、确定点冲突的消解策略与CBS算法扩展方向;
S27、确定边冲突的消解策略与CBS算法扩展方向。
4.根据权利要求3所述的基于改进冲突搜索法的多机器人路径规划方法,其特征在于,所述S24中针对不同机器人工作类型影响代价值的增加进行分析具体包括:对于负载机器人:当机器人的起始点和终点间的水平方向坐标之差大于障碍货架的水平栅格长度,垂直方向的坐标之差大于障碍货架的垂直栅格长度时,机器人拥有多条最短路径;设一排仓储货架的水平长度为xc,垂直长度为yc,机器人起始点坐标为(xstart,ystart),终点坐标为(xgoal,ygoal),当满足如下公式时:|xgoal‑xstart|>xc
|ygoal‑ystart|>yc
表明此机器人在此场景中存在多条最短路径;
对于空载机器人:其在水平方向和垂直方向的起终点坐标差大于0时,存在多条最短路径,需满足公式如下:|xgoal‑xstart|>0
|ygoal‑ystart|>0
设置单最短路径的机器人为高优先级,令多最短路径的机器人进行避让;设置负载机器人相比于空载机器人拥有更高的优先级,令空载机器人进行避让;设置单最短路径负载机器人优先级依次大于单最短路径空载机器人,大于多最短路径负载机器人,大于多最短路径空载机器人。
5.根据权利要求3所述的基于改进冲突搜索法的多机器人路径规划方法,其特征在于,所述S27中确定边冲突的消解策略与CBS算法扩展方向包括:将冲突消解策略中的等待策略替换为路径更换,更换的路径为代价增加的非最短路径,设置消解策略为代价值增加较小的机器人更换路径;CBS算法扩展两个节点,后续选择代价增加较小的节点继续扩展。
6.根据权利要求1所述的基于改进冲突搜索法的多机器人路径规划方法,其特征在于,所述S3中确定多机器人路径规划流程包括:S31、构建目标场景,输入各机器人的初始点与目标点;
S32、根据改进后的A*算法生成每个机器人的初始路径,作为根节点放入OPEN表;
S33、当OPEN表非空时,循环进行如下步骤:
计算各节点的cost值,选择cost值最小节点作为当前点;
如果当前节点无冲突,则返回当前解solution,即得到最优无冲突路径,跳出循环;
如果当前节点有冲突,则进行判断机器人冲突类型,选取对应冲突消解方案,生成消解方案对应的约束子节点及扩展优先级,将子节点放入OPEN表,结束本次循环;
S34、待循环过程完全结束后,输出多机器人的全局最优无冲突路径。
7.一种电子设备,包括存储器、处理器及存储在所述存储器上并可在所述处理器上运行的计算机程序,其特征在于,所述处理器执行所述计算机程序时实现上述权利要求1‑6任一项所述的方法的步骤。
8.一种具有处理器可执行的非易失的程序代码的计算机可读介质,其特征在于,所述程序代码使所述处理器执行所述权利要求1‑6任一项所述的方法。