一种基于冲突的移动机器人路径规划方法及系统

1.本发明属于机器人路径规划技术领域，尤其涉及一种基于冲突的移动机器人路径规划方法及系统。

背景技术：

2.本部分的陈述仅仅是提供了与本发明相关的背景技术信息，不必然构成已经成为本领域一般技术人员所公知的现有技术。
3.随着物流行业的快速发展，传统的“人到货”的拣选系统已经不能满足市场增长的需求，在工业自动化与制造业的需求下，智能仓储的战略地位提高，“货到人”拣选方式在逐步取代“人到货”的拣选方式，智能仓储及拣选系统已经成为智能系统研究领域的热点问题。
4.在全球范围内，多移动机器人的智能仓储系已经得到了得到广泛应用，路径规划是重要的优化环节之一。对于多移动机器人路径规划问题，可以抽象为多智能体路径规划问题(multi-agent path finding，mapf)，mapf把仓库布局抽象成无向图，把移动机器人抽象为智能体。多个智能体分布在无向图中，每个智能体都有一个起始位置和一个目标位置，每个智能体都需要到一条路径，机器人在移动过程中不能发生碰撞。
5.目前，机器人路径规划算法主要有a*算法、d*算法、蚁算法、代价搜索树算法、基于冲突的搜索算法(conflict-based search，cbs)等。发明人发现，d*算法和蚁算法是动态路径规划算法，可以规避障碍，但是无法到全局最优路径，智能仓库是由多移动机器人和货架组成的障碍物多且实时变化的高度动态的环境，机器人数量越多，上述动态规划算法越容易出现交通堵塞和路径规划中的震荡。a*算法是启发式搜索算法，可以到全局最优路径，但是多机器人工作在一个动态的环境中，a*算法可能会造成死锁，并且随着机器人数量的增加，求解难度指数级上升。代价搜索树算法和基于冲突的搜索算法与a*算法都是分为高层次搜索和低层次搜索两层算法，两者均适用于中等规模的多机器人路径规划问题。此外，现有的路径规划方法仅考虑了路径冲突和死锁问题，而忽略因路径拥堵对分拣效率的影响。

技术实现要素：

6.为了解决上述问题，本发明的第一方面提供一种基于冲突的移动机器人路径规划方法，能够确定出高效、无冲突的多机器人拣选路径，提高移动机器人拣选系统的拣选效率。
7.为了实现上述目的，本发明主要包括以下几个方面：
8.第一方面，本发明实施例提供一种基于冲突的移动机器人路径规划方法，包括：
9.根据待分配的任务和各机器人的状态信息，确定用于完成该任务的目标机器人，更新所述目标机器人的状态信息；
10.构建路径规划模型，所述路径规划模型包括上层搜索和下层搜索；所述上层搜索
是搜索约束树，所述约束树包括若干个节点，每个节点包括一组约束和符合约束的路径，该路径由下层搜索得到；所述下层搜索根据各机器人的状态信息，分任务进行路径规划求解；
11.通过求解所述路径规划模型，得到目标机器人的拣选路径。
12.在一种可能的实施方式中，在所述根据待分配的任务和各机器人的状态信息，确定用于完成该任务的目标机器人，更新所述目标机器人的状态信息之前，还包括：
13.根据机器人所处的阶段，确定与机器人对应的状态信息；其中，所述状态信息包括空闲状态、寻货架状态、承载货架后送到拣选点状态、拣选完成送到最近可放置货架的货位状态、任务完成回到充电区状态、电量不足状态和充电状态。
14.在一种可能的实施方式中，所述节点包括子节点、父节点和根节点，所述根节点包括一组空的约束，子节点继承父节点的约束，并为机器人添加一个新的约束。
15.在一种可能的实施方式中，所述搜索约束树的具体方式包括：
16.初始化时，约束树的根节点不包含任何约束，生成一个解并且求出它的代价值；
17.初始化结束后，获取代价值最低的节点，判断该节点中的解是否有冲突；若有冲突，则以该节点为父节点扩展出子节点，所述子节点继承父节点的约束，并添加新的约束，所述新的约束是根据冲突确定的；调用下层搜索重新规划子节点的路径，路径更新之后更新子节点的代价值，判断子节点中的解是否有冲突，若有冲突则以该子节点为父节点扩展子节点，直到返回没有冲突产生的节点。
18.在一种可能的实施方式中，在判断节点中的解是否有冲突时，根据机器人的状态信息确定该冲突的优先级；按照冲突的优先级确定冲突的解决策略。
19.在一种可能的实施方式中，所述下层搜索在进行路径规划求解时，引入机器人全局状态表，对机器人时间和位置进行约束；机器人从初始点到目标点到代价函数为机器人所在位置节点距离起点的代价、机器人所在位置节点距离终点的代价和机器人的转向代价之和。
20.在一种可能的实施方式中，所述下层搜索的路径规划求解过程包括：
21.获取栅格地图，输入栅格地图数据；初始位置s，目标位置g，生成时间状态为t，含有坐标和f值的节点s，初始化优先级队列open和close；其中，open表示待遍历的节点，close表示已经遍历过的节点，open队列的节点以f值升序排列；
22.将节点s放入open队列中；
23.若open队列不为空，取出头节点h，将头节点h保存到close队列中，检查当前节点是不是目标位置g，若是目标位置，则算法终止；
24.若不是目标位置g，则遍历头节点h的相邻节点；
25.如果相邻节点l是障碍物或相邻节点l已保存在close列表中，忽略该节点；
26.若相邻节点l不在open列表中且没有约束，计算相邻节点l的代价值；将相邻节点l添加到open列表中，标记相邻节点l的父节点为头节点h；
27.若相邻节点l不在open列表中但存在约束，即在该时间节点该位置不能搜索；查节点h是否在close列表中，若不在则遍历新的相邻节点；若在将节点h从close列表中删除，将时间状态更新的节点h’放入open列表中表示等待，标记节点h’的父节点为节点h；
28.若相邻节点l在open列表中，检查从开始节点s到节点l的原有代价和经过头节点h到达相邻节点l的代价，更新节点代价值和父子关系；
29.根据节点从属关系反向回溯到开始节点得到路径。
30.第二方面，本发明实施例还提供一种基于冲突的移动机器人路径规划系统，包括：
31.状态更新模块，用于根据待分配的任务和各机器人的状态信息，确定用于完成该任务的目标机器人，更新所述目标机器人的状态信息；
32.模型构建模块，用于构建路径规划模型，所述路径规划模型包括上层搜索和下层搜索；所述上层搜索是搜索约束树，所述约束树包括若干个节点，每个节点包括一组约束和符合约束的路径，该路径由下层搜索得到；所述下层搜索根据各机器人的状态信息，分任务进行路径规划求解；
33.路径获取模块，用于通过求解所述路径规划模型，得到目标机器人的拣选路径。
34.第三方面，本发明实施例提供一种计算机设备，包括：处理器、存储器和总线，所述存储器存储有所述处理器可执行的机器可读指令，当计算机设备运行时，所述处理器与所述存储器之间通过总线通信，所述机器可读指令被所述处理器执行时执行如上述第一方面和第一方面任一种可能的实施方式中所述的基于冲突的移动机器人路径规划方法的步骤。
35.第四方面，本发明实施例提供一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器运行时执行如上述第一方面和第一方面任一种可能的实施方式中所述的基于冲突的移动机器人路径规划方法的步骤。
36.基于上述技术方案，本发明具有以下有益效果：
37.1、考虑到物流分拣应用场景的动态特征，本发明对于静态的多机器人路径规划问题进行了扩展，提出一种基于冲突的移动机器人路径规划方法，在动态问题中，添加了对环境中执行任务的机器人数量和任务发生变化的考虑，将机器人不同阶段划分为不同状态，根据待分配的任务和各机器人的状态信息，确定用于完成该任务的目标机器人，更新所述目标机器人的状态信息。并且，通过构建包括上层搜索和下层搜索的路径规划模型，并求解得到目标机器人的拣选路径，可以快速地确定出高效、无冲突的多机器人拣选路径，提高移动机器人拣选系统的拣选效率。
38.2、根据机器人的状态信息确定冲突的优先级，并按照冲突的优先级确定冲突的解决策略，可以更高效的解决冲突。
39.3、下层搜索在进行路径规划求解时，引入机器人全局状态表，对机器人时间和位置进行约束，并且机器人从初始点到目标点到代价函数中添加了转向代价，可以使机器人的路径更加平滑。
40.4、本发明适用于类kiva移动机器人“货到人”拣选系统的路径规划，对其他移动机器人拣选系统有借鉴作用。
附图说明
41.构成本发明的一部分的说明书附图用来提供对本发明的进一步理解，本发明的示意性实施例及其说明用于解释本发明，并不构成对本发明的不当限定。
42.图1是本发明实施例所提供的仓库布局图；
43.图2是本发明实施例所提供的基于冲突的移动机器人路径规划方法的流程示意图；
44.图3是本发明实施例所提供的任务流程图；
45.图4(a)-4(b)是本发明实施例所提供的冲突示意图；
46.图5是本发明实施例所提供的实验路径图；
47.图6是本发明实施例所提供的基于冲突的移动机器人路径规划系统的结构示意图；
48.图7是本发明实施例所提供的一种计算机设备的结构示意图。
49.附图标记：1-拣选台；2-十字路口；3-充电区；4-过道；5-移动机器人；6-货架。
具体实施方式
50.下面结合附图与实施例对本发明作进一步说明。
51.应该指出，以下详细说明都是例示性的，旨在对本发明提供进一步的说明。除非另有指明，本文使用的所有技术和科学术语具有与本发明所属技术领域的普通技术人员通常理解的相同含义。
52.需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非意图限制根据本发明的示例性实施方式。如在这里所使用的，除非上下文另外明确指出，否则单数形式也意图包括复数形式，此外，还应当理解的是，当在本说明书中使用术语“包含”和/或“包括”时，其指明存在特征、步骤、操作、器件、组件和/或它们的组合。
53.本发明主要针对拣选中心分拣任务这个场景下的多机器人路径规划，如图1所示(示意图，以实际为准)。拣选中心地下铺设有大量磁钉，移动机器人5通过感知自己所在的位置进行导航。工作流程是移动机器人在充电区3等待任务，当一组订单到来后由系统进行任务分配，通过中央电脑给机器人计算路径后传递给机器人，接着机器人便按照指定的路径移动。具体移动过程为机器人收到命令立即从当前位置移动到目标货架6，承载起目标货架6之后移动到目标拣选台1，最后将拣选完成的货架送至货架区。对于多个机器人规划路径问题，单个机器人如果能更快的将完成任务，便能更快地投入到下一轮的任务当中去，就能使得分拣效率得到提高，所以目标是使所有路径的平均代价最小。依据应用特点，本发明选用了已有的多机器人路径规划模型作为问题模型，并以最小化路径代价和为目标函数。
54.请参阅图2，图2是本发明实施例所提供的基于冲突的移动机器人路径规划方法的流程示意图，如图2中所示，本实施例所提供的基于冲突的移动机器人路径规划方法，具体包括以下步骤：
55.s201：根据待分配的任务和各机器人的状态信息，确定用于完成该任务的目标机器人，更新所述目标机器人的状态信息。
56.在具体实施中，考虑到物流分拣这个应用场景的动态特征，本实施例对于静态的多机器人路径规划问题进行了扩展，提出了一种动态的多机器人路径规划方法。在动态问题中，添加了对环境中执行任务的机器人数量和任务发生变化的考虑，将机器人的不同阶段分别划分成不同的状态，根据待分配的任务和各机器人的状态信息，确定用于完成该任务的目标机器人，更新所述目标机器人的状态信息。
57.作为一可选实施方式，在所述根据待分配的任务和各机器人的状态信息，确定用于完成该任务的目标机器人，更新所述目标机器人的状态信息之前，还包括：
58.根据机器人所处的阶段，确定与机器人对应的状态信息；其中，所述状态信息包括空闲状态、寻货架状态、承载货架后送到拣选点状态、拣选完成送到最近可放置货架的货
位状态、任务完成回到充电区状态、电量不足状态和充电状态。
59.在具体实施方式中，将机器人划分成7个状态：空闲状态标志为0、寻货架状态标志为1、承载货架后送到拣选点状态标志为2、拣选完成送到最近可放置货架的货位状态标志为3、任务完成回到充电区状态标志为4、电量不足状态标志为5、充电状态为6。如图3中所示，机器人具体工作步骤如下：
60.(1)更新机器人状态，若可用机器人能够完成该任务，则下发任务，否则不下发；
61.(2)系统将任务下发给状态为0和4的目标机器人，将对应机器人的状态更新为1；
62.(3)机器人寻到货架承载后状态更新为2，将货架运送到拣选台；
63.(4)机器人运送的货架拣选完成后机器人状态更新为3，将货架送往货架区对应的位置；
64.(5)机器人完成将货架返回任务后状态更新为4，回到充电区状态更新为0；若中途收到任务则回到步骤(2)；
65.(6)机器人状态4的情况下，电量不足将状态更新为5，回到充电区充电，开始充电状态更新为6，充电完成状态更新为0。
66.多机器人路径规划问题可以描述为：给定一个无向图空间g＝(v,e),这里，v是图中的顶点集，e是连接顶点的边集，在这个空间里，分布着一定数量的机器人，假设有n个机器人，这些机器人用集合r＝(r1,r2,
…
,rn)来表示，每次分配任务给k个机器人，用集合tr＝(r1,r2,
…
,rk)表示。每个机器人都需要执行一个从起始点到目的点的任务，其路径由τi＝{si,gi}表示,其中si∈v表示ri的初始位置，gi∈v表示ri需要执行任务的目的位置。t＝{0,1,2
…
}是离散化的时间序列，ri的路径τi:t
→
v是从时间序列t到顶点集v的一个映射，τi(t)表示t时刻机器人ri的位置。任意时刻机器人可以选择停留在当前位置或者移动到相邻位置。cost(τi)定义为路径τi的代价，路径的代价用时间来计算，假设ts为所有机器人路径的起始时间，为路径τi的结束时间，即τi(ts)＝si，则多机器人路径规划问题就是需要给每个机器人到一条从起始位置到目的位置的路径的可行解，可行解是指多机器人的路径之间没有任何冲突。所有机器人路径之间无冲突定义如下:
[0067][0068][0069]
第一条约束说明路径上不允许发生节点冲突，即任意一个时刻的任意一个节点只允许被一个机器人占据；第二条约束说明路径上不允许发生换位冲突，即任意时刻不允许两个机器人互换了位置，如图4所示(a为节点冲突；b为换位冲突)。
[0070]
s202：构建路径规划模型，所述路径规划模型包括上层搜索和下层搜索；所述上层搜索是搜索约束树，所述约束树包括若干个节点，每个节点包括一组约束和符合约束的路径，该路径由下层搜索得到；所述下层搜索根据各机器人的状态信息，分任务进行路径规划求解。可选的，节点包括子节点、父节点和根节点，所述根节点包括一组空的约束，子节点继承父节点的约束，并为机器人添加一个新的约束。
[0071]
在具体实施中，本实施例是基于冲突的搜索算法(cbs)优化的一个改进的两阶段
算法，改进的算法可以实现多机器人多任务的动态计算，称为lcbs(loop conflict-based search)，首先来介绍上层搜索：
[0072]
上层搜索是搜索约束树节点(ct node)，每个节点内部包含2个信息：
[0073]
(1)一组约束(n.constraints)。每个约束都属于单个机器人。ct的根包含一组空的约束，ct中节点的子节点继承父节点的约束，并为一个机器人添加一个新的约束。
[0074]
(2)解决方案(n.solution)。一组k条机器人路径的集合，每个机器人一条路径。代理的路径必须符合约束。这些路径可以通过下层搜索到。
[0075]
多机器人路径优化的目标函数是路径代价和最小，总成本(n.cost)当前解决方案(总计所有单机器人路径成本)，此成本称为节点n的代价，即
[0076]
初始化时，创建约束树的根节点，节点不包含任何约束，然后生成一个解并且求出它的代价值，初始节点中的解的每个机器人的路径是忽略其他机器人的存在而求出的。初始化结束后算法不断地从open的队列中取出一个代价最低的节点，假设为n，判断该节点中的解是否有冲突。节点冲突表示为一个4元组(ri,rj,v,t)，意为ri和rj在t时刻同时占用了节点v；换位冲突表示为一个5元组(ri,rj,vj,vi,t)，意为ri和rj在t时刻交换了节点位置。在该节点中到的任意一个冲突，假设为conflit＝(ri,rj,v,t)，我们由该节点扩展出左右两个子节点，这两个字节点均继承父节点的约束。对于左右子节点分别添加约束(ri,v,t)和(rj,v,t)(表示机器人r在时间节点t不能占据节点v),由于约束集中对于ri和rj的约束个数发生了改变，因此需要调用下层改进a*搜索给ri和rj重新规划路径，路径更新之后更新节点的cost值。换位冲突同理，最后都会对节点产生一组约束。当多机器人正在运行的过程中，如果突然下发了新的任务，前一个任务的路径不变，根据下层的改进a*算法计算出机器人的路径，将两个任务的路径合并形成新的节点，寻冲突后解决，直到返回没有新冲突产生的节点。
[0077]
机器人状态的不同会导致处理冲突的难度发生变化，作为一可选实施方式，在判断节点中的解是否有冲突时，根据机器人的状态信息确定该冲突的优先级；按照冲突的优先级确定冲突的解决策略。举例而言，先解决易解决的冲突，使总的冲突数量减少，最后解决相对困难的冲突。机器人有7种状态，其中可以移动的为5种，这五种又分为两类，以是否承载机器人作为区分。当两个机器人发生冲突时，空机器人在规划路径时没有障碍物，发生冲突时基本只需等待或者移动一次就能解决冲突，承载货架的机器人在过道发生换位冲突解决难度最高，最后再解决这类冲突，这样，可以提高冲突的解决效率。
[0078]
为了实现动态的路径规划，我们引入机器人状态全局表，该表上可以记录当前到所有任务结束之间所有时间节点机器人的位置和状态，也记录了该时间节点任务的开始位置与目标位置，示意表如表1所示。当新任务发给对应机器人之后，系统可以根据上述静态多机器人路径规划方法重新进行计算，以当前机器人的节点为开始位置，目标位置不变，根据状态判断障碍物分布与冲突的优先级，进行两阶段求解，得到新的解决方案，实现动态的路径求解。
[0079]
表1机器人状态全局表
[0080][0081]
下层搜索采用改进的a*算法，对路径的节点引入了时间状态，考虑到了转向代价，加入转向代价是为了让机器人行走路径更加平滑，避免不必要的转向，符合现实场景的需求。
[0082]
机器人从初始点到目标点到代价函数为：
[0083]
f(n)＝g(n)+h(n)+c(n)
[0084]
式中：f(n)代表由出发点途经当前点并到达目标点的总代价值；g(n)是机器人所在位置节点n距离起点的代价；h(n)是机器人所在位置节点n距离终点的预计代价；c(n)是机器人的转向代价。
[0085]
g(n)＝∣x
s-xn∣+∣y
s-yn∣；
[0086]
h(n)＝∣x
g-xn∣+∣y
g-yn∣；
[0087][0088]
研究模型为栅格地图，每个节点的位置可以用坐标表示，即(x,y)。机器人只能向四个方向移动，所以g(n)和g(n)均为曼哈顿距离，c(n)需要判断是否是拐点，只需与上个节点的坐标与邻近节点进行比较，均不相同即为拐点，否则便是走直线。若是直线行走或者拐向终点，代价为0，若是拐点，代价为1。
[0089]
改进的a*算法的流程如下：
[0090]
step 1：输入栅格地图数据g＝(v,e)，初始位置s，目标位置g；生成时间状态为t，含有坐标和总代价f值的节点s，初始化优先级队列open和close(分别表示待遍历的节点和已经遍历过的节点)，其中open队列的节点以f值升序排列。
[0091]
step 2：将节点s放入open列表中。
[0092]
step 3：若open不为空，取出头节点h(优先级最高的节点)，将头节点h保存到close列表中，检查当前节点是不是目标节点g，若是目标节点，算法终止，跳转到step 5。
[0093]
step 4：遍历节点h的相邻节点。
[0094]
step 4.1：如果相邻节点l是障碍物或节点l已保存在close列表中，忽略该节点。
[0095]
step 4.2：若节点l不在open列表中且没有约束，计算节点l的代价值。将节点l添加到open列表中，标记节点l的父节点为节点h。
[0096]
step 4.3：若节点l不在open列表中但存在约束，即在该时间节点该位置不能搜索。查节点h是否在close列表中，若不在则遍历新的相邻节点；若在将节点h从close列表
中删除，将时间状态更新的节点h’放入open列表中表示等待，标记节点h’的父节点为节点h。
[0097]
step 4.4：若节点l在open列表中，检查从开始节点s到节点l的原有代价和经过节点h到达节点l的代价的大小，更新节点代价值和父子关系。
[0098]
step 4.4：相邻节点遍历完毕后，跳转到step 3。
[0099]
step 5：若算法查成功，根据节点从属关系反向回溯到开始节点得到路径；否则，算法无解。
[0100]
s203：通过求解所述路径规划模型，得到目标机器人的拣选路径。
[0101]
这里，在step 3中，open为空表示所有节点都遍历结束，此刻表示已经到终点。open在到终点前不可能为空，这里在到终点前其实是作为一个无限循环。取出头节点就是取出优先级最高的点来遍历其邻近节点，若邻近节点均满足约束，开始下一个循环，否则从close中删除该节点，重新放入open中等待。
[0102]
本技术实施例提出一种基于冲突的移动机器人路径规划方法，在动态问题中，添加了对环境中执行任务的机器人数量和任务发生变化的考虑，将机器人不同阶段划分为不同状态，根据待分配的任务和各机器人的状态信息，确定用于完成该任务的目标机器人，更新所述目标机器人的状态信息。并且，通过构建包括上层搜索和下层搜索的路径规划模型，并求解得到目标机器人的拣选路径，可以快速地确定出高效、无冲突的多机器人拣选路径，提高移动机器人拣选系统的拣选效率。
[0103]
实验地图如图1所示。利用本发明的方法求解五个机器人四个任务的路径。机器人的作业流程为从充电区到货架区对应货架，从货架区到拣选台，然后将货架从拣选台送至货架区对应位置，最后移动机器人回到对应充电区，任务下发由系统自动下发，本方法只实现路径规划。机器人任务表如表2所示：
[0104]
表2机器人任务表
[0105][0106]
实验结果如下表所示：
[0107]
表3机器人路径表
[0108]
[0109]
[0110][0111]
其中，机器人1代价为90，机器人2代价为85，机器人3代价为87，机器人4代价为94，机器人5代价为90，总代价为446。利用matplotlib库画出机器人行走路径示意图，如图5所示。设置为当每一个任务组后完成时改变颜，在颜改变之前其他四个机器人已经完成，并已经开始下一个任务。
[0112]
请参阅图6，图6是本发明实施例所提供的基于冲突的移动机器人路径规划系统的结构示意图，如图6中所示，本实施例还提供一种基于冲突的移动机器人路径规划系统，该移动机器人路径规划系统600包括：
[0113]
状态更新模块610，用于根据待分配的任务和各机器人的状态信息，确定用于完成该任务的目标机器人，更新所述目标机器人的状态信息；
[0114]
模型构建模块620，用于构建路径规划模型，所述路径规划模型包括上层搜索和下层搜索；所述上层搜索是搜索约束树，所述约束树包括若干个节点，每个节点包括一组约束和符合约束的路径，该路径由下层搜索得到；所述下层搜索根据各机器人的状态信息，分任务进行路径规划求解；
[0115]
路径获取模块630，用于通过求解所述路径规划模型，得到目标机器人的拣选路径。
[0116]
本实施例提供的基于冲突的移动机器人路径规划系统用于实现前述的基于冲突的移动机器人路径规划方法，因此基于基于冲突的移动机器人路径规划系统的具体实施方式可见前文中的基于冲突的移动机器人路径规划方法的实施例部分，在此不再进行赘述。
[0117]
请参阅图7，图7是本发明实施例所提供的一种计算机设备的结构示意图。如图7中所示，所述计算机设备700包括处理器710、存储器720和总线730。
[0118]
所述存储器720存储有所述处理器710可执行的机器可读指令，当计算机设备700运行时，所述处理器710与所述存储器720之间通过总线730通信，所述机器可读指令被所述
处理器710执行时，可以执行如上述图2所示方法实施例中的基于冲突的移动机器人路径规划方法的步骤，具体实现方式可参见方法实施例，在此不再赘述。
[0119]
基于同一发明构思，本发明实施例还提供一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器运行时执行上述方法实施例中所述的基于冲突的移动机器人路径规划方法的步骤。
[0120]
本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的程序可存储于一计算机可读取存储介质中，该程序在执行时，可包括如上述各方法的实施例的流程。其中，所述的存储介质可为磁碟、光盘、只读存储记忆体(read-only memory，rom)或随机存储记忆体(random accessmemory，ram)等。
[0121]
以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

技术特征：

1.一种基于冲突的移动机器人路径规划方法，其特征在于，包括：根据待分配的任务和各机器人的状态信息，确定用于完成该任务的目标机器人，更新所述目标机器人的状态信息；构建路径规划模型，所述路径规划模型包括上层搜索和下层搜索；所述上层搜索是搜索约束树，所述约束树包括若干个节点，每个节点包括一组约束和符合约束的路径，该路径由下层搜索得到；所述下层搜索根据各机器人的状态信息，分任务进行路径规划求解；通过求解所述路径规划模型，得到目标机器人的拣选路径。2.如权利要求1所述的基于冲突的移动机器人路径规划方法，其特征在于，在所述根据待分配的任务和各机器人的状态信息，确定用于完成该任务的目标机器人，更新所述目标机器人的状态信息之前，还包括：根据机器人所处的阶段，确定与机器人对应的状态信息；其中，所述状态信息包括空闲状态、寻货架状态、承载货架后送到拣选点状态、拣选完成送到最近可放置货架的货位状态、任务完成回到充电区状态、电量不足状态和充电状态。3.如权利要求1所述的基于冲突的移动机器人路径规划方法，其特征在于，所述节点包括子节点、父节点和根节点，所述根节点包括一组空的约束，子节点继承父节点的约束，并为机器人添加一个新的约束。4.如权利要求3所述的基于冲突的移动机器人路径规划方法，其特征在于，所述搜索约束树的具体方式包括：初始化时，约束树的根节点不包含任何约束，生成一个解并且求出它的代价值；初始化结束后，获取代价值最低的节点，判断该节点中的解是否有冲突；若有冲突，则以该节点为父节点扩展出子节点，所述子节点继承父节点的约束，并添加新的约束，所述新的约束是根据冲突确定的；调用下层搜索重新规划子节点的路径，路径更新之后更新子节点的代价值，判断子节点中的解是否有冲突，若有冲突则以该子节点为父节点扩展子节点，直到返回没有冲突产生的节点。5.如权利要求4所述的基于冲突的移动机器人路径规划方法，其特征在于，在判断节点中的解是否有冲突时，根据机器人的状态信息确定该冲突的优先级；按照冲突的优先级确定冲突的解决策略。6.如权利要求1所述的基于冲突的移动机器人路径规划方法，其特征在于，所述下层搜索在进行路径规划求解时，引入机器人全局状态表，对机器人时间和位置进行约束；机器人从初始点到目标点到代价函数为机器人所在位置节点距离起点的代价、机器人所在位置节点距离终点的代价和机器人的转向代价之和。7.如权利要求6所述的基于冲突的移动机器人路径规划方法，其特征在于，所述下层搜索的路径规划求解过程包括：获取栅格地图，输入栅格地图数据；初始位置s，目标位置g，生成时间状态为t，含有坐标和总代价f值的节点s，初始化优先级队列open和close；其中，open表示待遍历的节点，close表示已经遍历过的节点，open队列的节点以f值升序排列；将节点s放入open队列中；若open队列不为空，取出头节点h，将头节点h保存到close队列中，检查当前节点是不是目标位置g，若是目标位置，则算法终止；
若不是目标位置g，则遍历头节点h的相邻节点；如果相邻节点l是障碍物或相邻节点l已保存在close列表中，忽略该节点；若相邻节点l不在open列表中且没有约束，计算相邻节点l的代价值；将相邻节点l添加到open列表中，标记相邻节点l的父节点为头节点h；若相邻节点l不在open列表中但存在约束，即在该时间节点该位置不能搜索；将头节点h从close列表中删除，将时间状态更新的节点h’放入open列表中表示等待，标记节点h’的父节点为头节点h；若相邻节点l在open列表中，检查从开始节点s到节点l的原有代价和经过头节点h到达相邻节点l的代价，更新节点代价值和父子关系；根据节点从属关系反向回溯到开始节点得到路径。8.一种基于冲突的移动机器人路径规划系统，其特征在于，包括：状态更新模块，用于根据待分配的任务和各机器人的状态信息，确定用于完成该任务的目标机器人，更新所述目标机器人的状态信息；模型构建模块，用于构建路径规划模型，所述路径规划模型包括上层搜索和下层搜索；所述上层搜索是搜索约束树，所述约束树包括若干个节点，每个节点包括一组约束和符合约束的路径，该路径由下层搜索得到；所述下层搜索根据各机器人的状态信息，分任务进行路径规划求解；路径获取模块，用于通过求解所述路径规划模型，得到目标机器人的拣选路径。9.一种计算机设备，其特征在于，包括：处理器、存储器和总线，所述存储器存储有所述处理器可执行的机器可读指令，当计算机设备运行时，所述处理器与所述存储器之间通过总线通信，所述机器可读指令被所述处理器执行时执行如权利要求1至7任一项所述的基于冲突的移动机器人路径规划方法的步骤。10.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器运行时执行如权利要求1至7任一项所述的基于冲突的移动机器人路径规划方法的步骤。

技术总结

本发明提供一种基于冲突的移动机器人路径规划方法及系统，涉及机器人路径规划技术领域，该方法包括：根据待分配的任务和各机器人的状态信息，确定用于完成该任务的目标机器人，更新目标机器人的状态信息；构建路径规划模型，路径规划模型包括上层搜索和下层搜索；上层搜索是搜索约束树，约束树包括若干个节点，每个节点包括一组约束和符合约束的路径，该路径由下层搜索得到；下层搜索根据各机器人的状态信息，分任务进行路径规划求解；通过求解路径规划模型，得到目标机器人的拣选路径。通过该方式，可以快速地确定出高效、无冲突的多机器人拣选路径，提高移动机器人拣选系统的拣选效率。拣选效率。拣选效率。