基于密集存储区域的多移动机器人路径冲突解决方法

摘要

本发明涉及一种基于密集存储区域的多移动机器人路径冲突解决方法，其技术特点包括以下步骤：1、调度服务器建立一初始化网状路径图；2、检测存取货物任务并将任务划分若干个子任务；3、使用图搜索法输出当前子任务的任务路径；4、判断子任务目标点是否被上一个的任务释放掉；5、使用任务编号标记每个任务路经；6、标记完所有任务路径后返回步骤2；7、执行任务队列的各任务抢占资源变量；8、划分冲突区；9、判断冲突区是否释放干净；10、向移动机器人发送执行任务的命令；11、释放资源变量给调度服务器后返回步骤7。本发明设计合理，能够做到随时分发任务、随时规划任务和随时避免冲突，具有精确度高、运算简洁、实时性强等特点。

权利要求

1.一种基于密集存储区域的多移动机器人路径冲突解决方法，其特征在于：包括以下步骤：步骤1：调度服务器建立一初始化网状路径图；包括以下处理过程：⑴获得密集存储区域的存储位图纸；

⑵建立存储点：取每个存储位中心点作为存储点；

⑶建立路点：在巷道上与存储点区域大小相同的可行走区域的中心点作为路点，该路点沿直线方向在与其姿态相同的临近路点区域以外；

每个路点根据其与其他路点的位置关系，又分以下特殊路点：可转路点、相干路点、交叉路点；

⑴可转路点：如果两个路点位置重合且两个路点区域姿态可以相互转换时，则上述路点为可转路点；

⑵相干路点：当两个路点区域叠加交错分布时，上述路点互为对方的相干路点；

⑶交叉路点：当线路交叉且交叉点不通过路点本身、并且交叉点为姿态限定点时，则该交叉点作为交叉路点；

⑷建立连通性：将具有连通性的两个相邻点进行连线构成初始化网状路径图；

步骤2：调度线程检测到有存取货物任务时，获取起始点和目标点信息并将任务划分若干个子任务，每个子任务又设有各自的起始点和目标点，每个子任务为空车寻货子任务或负载运货子任务；

步骤3：调度线程根据子任务的起始点、目标点及输入参数使用图搜索法输出当前子任务的任务路径；

步骤4：调度线程判断该子任务目标点是否被上一个的任务释放掉，如果没有被释放，等待释放，如果已经被释放，则进入步骤5；

步骤5：调度线程使用携带方向和排序特征的任务编号标记每个任务路经，被标记的点包括当前任务路径上的点以及它的相干点；

步骤6：调度线程标记完所有任务路径后，将标记后的任务送入执行队列，返回步骤2；

步骤7：执行线程执行任务队列的各任务抢占资源变量；

步骤8：执行线程将所有路点上被标记至少两个任务编号、并且方向相反的路点组合的区域划分为冲突区；

步骤9：执行线程判断冲突区是否释放干净，如果释放干净转入步骤10；如果没有释放干净，转入步骤11；

步骤10：执行线程向移动机器人发送执行任务的命令；

步骤11：执行线程释放资源变量给调度服务器，返回步骤7。

2.根据权利要求1所述的基于密集存储区域的多移动机器人路径冲突解决方法，其特征在于：所述的相干路点非独立存在，其依托于另外一个与它相干的路点；所述的可转路点和交叉路点可以独立存在，也可以非独立存在，当它作为相干点时是非独立存在的。

3.根据权利要求1所述的基于密集存储区域的多移动机器人路径冲突解决方法，其特征在于：所述的具有连通性的两个相邻点包括：两个姿态不限定点、一个姿态不限定点和一个姿态限定点、姿态相同的两个姿态限定点。

4.根据权利要求1所述的基于密集存储区域的多移动机器人路径冲突解决方法，其特征在于：所述步骤3中的输入参数包括存储点、路点、携带方向和排序特征的任务编号、带有权值的网状路径图。

5.根据权利要求1所述的基于密集存储区域的多移动机器人路径冲突解决方法，其特征在于：所述的路点区域之间具有相干性：路点占用连同相干路点一起占用，路径上的点为主动占用，该点的相干路点为从属占用，相干点可以是路径以外的点，也可以是路径上的点。

6.根据权利要求1所述的基于密集存储区域的多移动机器人路径冲突解决方法，其特征在于：所述的任务路径包括移动机器人空载路径和移动机器人负载路径，移动机器人负载路径包括无障碍物存储位之间的路径和巷道路径；移动机器人空载路径包括所有存储位之间的路径和巷道路径。

7.根据权利要求1至6任一项所述的基于密集存储区域的多移动机器人路径冲突解决方法，其特征在于：所述的移动机器人为全自动搬运车，所述的货物托盘由四条托盘腿支撑地面且四条托盘腿略高于移动机器人的高度。

说明书

基于密集存储区域的多移动机器人路径冲突解决方法

技术领域

[0001] 本发明属于移动机器人领域，尤其是一种基于密集存储区域的多移动机器人路径冲突解决方法。

背景技术

[0002] 密集存储区域多机器人避碰规划的条件是：(1)机器人的运动限制在二维空间，属于平面运动；(2)密集存储区域巷道不仅狭窄并且还具有相干性，所谓狭窄，就是有的地方其宽度只允许一个机器人平躺着通过；所谓相干性就是某几个路点区域组合的区域是由不同姿态的区域交错叠加而成：机器人可以以不同姿态通过这个区域；(3)机器人的碰撞指由于在同一条巷道上相向而行和交错而行引起的任务死锁，不考虑同向而行的情况；(4)运动的机器人组成了其它机器人成员的动态障碍；(5)机器人和服务器之间通过无限网络进行通讯。

[0003] 在多机器人运动系统中，可能会出现死锁的运动冲突情况。所谓死锁是指两个以显示方式通讯的机器人相向而行，当它们距离足够近时，各自停了下来，相互无休止地循环等待，最后导致机器人的运动完全停止，此种情况称之为任务死锁。多机器人路径冲突解决策略就是要解决当多机器人在同一条路径上相向而行和交错而行时，在保证互不发生死锁的情况下，安全顺畅地执行任务，从起始点到达目标点的问题。

[0004] 根据机器人工作环境的不同，冲突消解可分为两种:集中管理式冲突消解和分布式冲突消解。集中管理式方法通常可以寻找最优解，但是需要预先知道环境的准确信息，并且计算量很大，实时性差，其典型应用是将机器人的运动路径分段，然后按冲突消解要求对机器人通过各段的时间进行约束，通过调整机器人各段的时间进行冲突消解，从而将冲突消解问题转化为高维线性空间的优化问题，并进一步转化为线性方程的求解。分布式冲突消解方法侧重于考虑机器人当前的局部环境信息，让机器人具有良好的冲突消解能力，和集中管理式方法向比较，分布式方法更具有实时性和实用性。分布式冲突消解方法通常有三种解决方法：交通规则法、速率调整法和优先级法（见哈尔滨工程大学论文《多机器人协调避碰与任务协作研究》）。交通规则法就是给多机器人制定共同遵守的规则，保持群体的有序性，有了这些规则，就能使有自控意愿的个体保持有序，交通规则法虽然可以避免死锁现象发生，但机器人行走通道必须保证右侧通行，当两个相向而行的机器人在同一条通道上行走时，只有各占其道才能保证不发生死锁，如果通道的宽度不能容纳两个机器人的宽度而只能让一个机器人通过时，交通规则法此时显然失效。速率调整法和优先级法是结合一起使用的，其速率调整包括加速、减速、停止甚至是倒退，当两个相向而行的机器人发生死锁时，优先级别高的有权让级别低的退让到宽阔地带，而使其自身优先通过，此方法不足在于，仅仅依靠局部信息，会产生局部极点，无法保证机器人顺利到达目的地，例如：机器人其中一个必须退回到开阔地带才可以解决问题，但机器人作倒退运动的环境条件在当前局部信息中无法获得：在倒退过程中如何保证途中不再和其它机器人发生碰撞?机器人倒退到哪里最为经济合理？如何保证倒退目标点是有效目标点等一系列问题，由于分布式冲突消解方法仅仅依靠局部信息无法真正实现任务，还增加了难度，在实际运行中，此种方法很少被采纳。

[0005] 综上所述，集中管理式方法最为精确，但运算复杂且实时性差，而分布式方法虽然运算简单、实时性和灵活性强，但由于会出现局部极点，往往无法完整地完成任务。

发明内容

[0006] 本发明的目的在于克服现有技术的不足，提供一种精确程度高、运算简洁、实时性强的的基于密集存储区域的多移动机器人路径冲突解决方法。

[0007] 本发明解决其技术问题是采取以下技术方案实现的：

[0008] 一种基于密集存储区域的多移动机器人路径冲突解决方法，包括以下步骤：

[0009] 步骤1：调度服务器建立一初始化网状路径图；

[0010] 步骤2：调度线程检测到有存取货物任务时，获取起始点和目标点信息并将任务划分若干个子任务，每个子任务又设有各自的起始点和目标点，每个子任务为空车寻货子任务或负载运货子任务；

[0011] 步骤3：调度线程根据子任务的起始点、目标点及参数使用图搜索法输出当前子任务的任务路径；

[0012] 步骤4：调度线程判断该子任务目标点是否被上一个的任务释放掉，如果没有被释放，等待释放，如果已经被释放，则进入步骤5；

[0013] 步骤5：调度线程使用携带方向和排序特征的任务编号标记每个任务路经，被标记的点包括当前任务路径上的点以及它的相干点；

[0014] 步骤6：调度线程标记完所有任务路径后，将标记后的任务送入执行队列，返回步骤2；

[0015] 步骤7：执行线程执行任务队列的各任务抢占资源变量；

[0016] 步骤8：执行线程将所有一个路点上被标记至少两个任务编号、并且方向相反的路点组合的区域划分为冲突区。

[0017] 步骤9：执行线程判断冲突区是否释放干净，如果释放干净转入步骤10；如果没有释放干净，转入步骤11；

[0018] 步骤10：执行线程向移动机器人发送执行任务的命令；

[0019] 步骤11：执行线程释放资源变量给调度服务器，返回步骤7。

[0020] 而且，所述步骤1建立初始化网状路径图的方法包括以下处理过程：

[0021] ⑴获得密集存储区域的存储位图纸；

[0022] ⑵建立存储点：取每个存储位中心点作为存储点；

[0023] ⑶建立路点：在巷道上与存储点区域大小相同的可行走区域的中心点作为路点，该路点沿直线方向在与其姿态相同的临近路点区域以外；

[0024] ⑷建立连通性：将具有连通性的两个相邻点进行连线构成初始化网状路径图。

[0025] 而且，所述的路点包括以下特殊路点：可转路点、相干路点、交叉路点。

[0026] 而且，所述的相干路点非独立存在，其依托于另外一个与它相干的路点；所述的可转路点和交叉路点可以独立存在，也可以非独立存在，当它作为相干点时是非独立存在的。

[0027] 而且，所述的具有连通性的两个相邻点包括：两个姿态不限定点、一个姿态不限定点和一个姿态限定点、姿态相同的两个姿态限定点。

[0028] 而且，所述步骤3中的输入参数包括存储点、路点、携带方向和排序特征的任务编号、带有权值的网状路径图。

[0029] 而且，所述的路点区域之间具有相干性，路点占用连同相干路点一起占用，路径上的点为主动占用，该点的相干路点为从属占用，相干点可以是路径以外的点，也可以是路径上的点。

[0030] 而且，所述的任务路径包括移动机器人空载路径和移动机器人负载路径，移动机器人负载路径包括无障碍物存储位之间的路径和巷道路径；移动机器人空载路径包括所有存储位之间的路径和巷道路径。

[0031] 而且，所述的移动机器人为全自动搬运车，所述的货物托盘由四条托盘腿支撑地面且四条托盘腿略高于移动机器人的高度。

[0032] 本发明的优点和积极效果是：

[0033] 1、本发明采用抢占资源变量的方法实现了多机器人系统的高效率：当某一任务抢先获得了资源变量后，其它任务在片刻时间内处于等待状态，当获得资源变量的该任务在很短时间内完成了路径搜索和任务标记任务后，又很快将资源变量释放给调度服务器，由调度服务器其它任务继续抢占资源变量，其它任务在获得资源变量后同样在片刻时间内获得了独占权，又在片刻时间内释放了独占权，这样周而复始地进行下去，从而保证了多机器人系统的高效率：宏观上多任务并发执行，微观上多任务串行执行。

[0034] 2、本发明采用分步式资源抢占的方法实现了多机器人系统的合理性：分步式路径冲突消解方法分为两个阶段，第一个阶段抢占资源变量，实现了宏观上多任务并发执行，微观上多任务串行执行，第二个阶段按照自然距离法抢占冲突区，哪个任务距离冲突区距离最近，哪个任务就最先进入冲突区，一旦冲突区被占用，冲突区以外的其它任务必须等待，谁先进入冲突区谁就获得了第二阶段的优先权，其它任务必须等待冲突区完全被释放，才可以进入冲突区。由于以上第一阶段和第二阶段时间相差微小，既保证了多机器人系统高效率并发执行的可行性，又避免了多机器人在局部范围的路径冲突或任务死锁。

[0035] 3、本发明采用多线程方法划分动态冲突区，保证了多机器人系统的实时性：调度线程实时接收任务，包括任务接收、任务规划、任务标记并将该任务实时送往任务队列，这样周而复始地进行下去，从而保证了系统接收任务和规划任务的实时性；执行线程通过执行任务队列的各任务抢占资源变量、获得独占权、划分冲突区、发送命令、释放资源变量，这样周而复始地进行下去，从而保证了系统消解冲突和发送任务的实时性；通过两个线程的有机配合，使得该系统能够做到随时分发任务、随时规划任务、随时避免冲突。

附图说明

[0036] 图1是调度服务器的初始化网状路径图；

[0037] 图2是调度服务器的处理流程图；

[0038] 图3是调度服务器的一个存取货物任务示意图；

[0039] 图4是调度服务器使用图搜索法给出的A子任务路径示意图；

[0040] 图5是调度服务器判断目标点被占用时等待目标点货物被移出示意图；

[0041] 图6是A子任务路径上应该标记的所有点；

[0042] 图7是调度服务器使用任务编号标记A任务的示意图；

[0043] 图8是调度服务器使用图搜索法给出的B子任务路径示意图；

[0044] 图9是B子任务路径上应该标记的所有点；

[0045] 图10是调度服务器使用任务编号标记B任务的示意图；

[0046] 图11是调度服务器使用任务编号标记A任务和B任务的示意图；

[0047] 图12是A任务和B任务的冲突区；

[0048] 图13是本发明多机器人避碰示意图1；

[0049] 图14是本发明多机器人避碰示意图2；

具体实施方式

[0050] 以下结合附图对本发明实施例做进一步详述：

[0051] 一种基于密集存储区域的多移动机器人路径冲突解决方法，基于在先专利申请（专利名称：一种高密度自动立体仓储系统，申请号：201210052054.3）。移动机器人采用全自动搬运车，能够在保证车身不动的情况下，通过扭转车轮角度使货物斜线平移、水平横移和原地半径旋转运动。货物均放置在货物托盘上，货物托盘由四条托盘腿支撑地面，四条托盘腿的高度略高于移动机器人的高度，移动机器人可以在任意两条托盘腿之间行走。

[0052] 如图1所示，基于密集存储区域的多移动机器人路径冲突解决方法包括以下步骤：

[0053] 步骤1：调度服务器建立一初始化网状路径图。

[0054] 如图2所示，调度服务器采用如下处理过程建立初始化网状路径图：

[0055] 1、获得密集存储区域的存储位图纸；

[0056] 2、建立存储点：取每个存储位中心点作为存储点；

[0057] 3、建立路点：在巷道上与存储点区域大小相同的可行走区域的中心点作为路点，该路点沿直线方向在与其姿态相同的临近路点区域以外。每个路点根据其与其他路点的位置关系，又分以下特殊路点：可转路点、相干路点、交叉路点

[0058] （1）可转路点：如果两个路点位置重合且两个路点区域姿态可以相互转换时，则上述路点为可转路点；

[0059] （2）相干路点：当两个路点区域叠加交错分布时，上述路点互为对方的相干路点。

[0060] （3）交叉路点：当线路交叉且交叉点不通过路点本身、并且交叉点为姿态限定点时，则该交叉点作为交叉路点；

[0061] 以上所述的相干路点不可以独立存在，它必须依托于另外一个与它相干的路点；所述的可转路点和交叉路点可以独立存在，也可以非独立存在，当它作为相干点时是非独立存在的。

[0062] 上述存储点和路点均具有一定的姿态属性，即具有特定方向的长度和宽度。对于可转路点，由于其姿态属性可以改变，因此，可转路点为姿态不限定点；而其它路点和存储点的姿态属性均不可以改变，因此，均为姿态限定点。

[0063] 3、建立连通性：姿态不限定点之间可连通；姿态不限定点和姿态限定点之间可连通；姿态相同的姿态限定点之间可连通；其他情况均不可连通（即姿态不相同的姿态限定点不可连通）。将具有连通性的两个相邻点进行连线构成初始化网状路径图。

[0064] 所述网状路径图上的每条线段设有权值，该权值等于距离的长度。权值的计算方法为：⑴当任务类型为负载送货任务时，在当前路径有障碍物的条件下，权值为无穷大；在当前路径无障碍物的条件下，其权值为连线的实际距离；⑵当任务类型为空车寻货时，其权值为连线的实际距离。

[0065] 通过上述处理过程建立包括存储点、路点、可转路点、相干路点、交叉路点以及具有连通性的两个相邻点之间连线的初始化网状路径图。

[0066] 调度服务器建立初始化网状路径图后，同步处理调度线程（步骤2至步骤6）和执行线程（步骤7至步骤11）。

[0067] 步骤2：调度线程检测到有存取货物任务时，获取起始点和目标点信息并将任务划分若干个子任务，每个子任务又设有各自的起始点和目标点，每个子任务为空车寻货子任务或负载运货子任务。

[0068] 在本步骤中，调度线程获取当前任务时，根据起始点和目标点信息将当前任务划分为多个子任务，这些子任务包括空车寻货子任务和负载运货子任务，如图3所示。由于移动机器人在空车运行时，既可以沿巷道行走，也可以在货物下方行走，因此，所述移动机器人在执行空车寻货子任务时，可以采用如下方式执行：移动机器人钻入货物托盘下面，在货物托盘下面行走；移动机器人在执行负载送货子任务时，采用如下方式执行：移动机器人钻入货物托盘下方并顶起货物托盘及其上面的货物沿巷道路径行走。

[0069] 当机器人行走在货物托盘下面的路径上时，机器人从货物托盘下面的空隙中纵横穿过，此时，冲突区的产生只是来自同一路径上的相向而行的情况；当机器人行走在巷道路径上时，冲突区的产生来自相向而行或交错而行的情况。

[0070] 步骤3：调度线程根据子任务的起始点、目标点及参数使用图搜索法输出当前子任务的任务路径。

[0071] 在本步骤中，调度线程根据输入的参数：存储点、路点、可转路点、相干路点、交叉路点、权值以及网状路径图，使用图搜索法给出当前子任务的任务路径（从起始点到目标点），如图4或图8所示。

[0072] 所述的任务路径包括移动机器人空载路径和移动机器人负载路径，移动机器人负载路径包括无障碍物存储位之间的路径和巷道路径；移动机器人空载路径包括所有存储位之间的路径和巷道路径。

[0073] 步骤4：调度线程判断该子任务目标点是否被上一个的任务释放掉，如果没有被释放，等待释放，如果已经被释放，则进入步骤5，如图5所示。

[0074] 在本步骤中，移动机器人每经过一个点（存储点、路点、可转路点、相干路点、交叉路点）后，就会向调度服务器释放当前点，直到任务执行完毕并释放所有点。

[0075] 步骤5：调度线程使用携带方向和排序特征的任务编号标记每个任务路经，被标记的点包括当前任务路径上的点以及它的相干点；如图6、图7、图9、图10、图11所示。

[0076] 步骤6：调度线程标记完所有任务路径后，将标记后的任务送入执行队列，返回步骤2；

[0077] 步骤7：执行线程执行任务队列的各任务抢占资源变量；

[0078] 步骤8：执行线程将所有路点上被标记至少两个任务编号、并且方向相反的路点组合的区域划分为冲突区。如图12所示。

[0079] 步骤9：执行线程判断冲突区是否释放干净，如果释放干净转入步骤10；如果没有释放干净转入步骤11。

[0080] 在本步骤中，移动机器人每经过一个点（存储点、路点、可转路点、相干路点、交叉路点）后，就会向调度服务器释放当前点，直到任务执行完毕释放所有点。

[0081] 步骤10：执行线程向移动机器人发送执行任务的命令。

[0082] 步骤11：执行线程释放资源变量给调度服务器，返回步骤7。

[0083] 调度服务器采用同步处理方式执行调度线程和执行线程，完成了基于密集存储区域的多移动机器人的货物存取任务，有效地解决了多移动机器人路径冲突问题。

[0084] 下面以停车场为例，对本发明的多移动机器人路径冲突解决方法进行具体说明，说明本方法如何解决A、B两个任务当它们相向而行和交错而行时，如何解决避碰问题。

[0085] 步骤1：调度服务器建立一初始化网状路径图，如图1所示。密集停车场的上部和下部并排设有停车位（存储位），中间为巷道和墙体，在停车场的出入口处设有车辆存取间。在初始化网状路径图中，每个停车位中心点为存储点，在巷道中间设有路点（其中35、39、42和46为可转路点，75和76是交叉路点）。

[0086] 步骤2：调度线程检测到有存取货物任务时，获取起始点和目标点信息并将任务划分若干个子任务，如图3所示，其中C任务是上一个尚未完成且正在执行的任务；A任务和B任务是本次发生的任务。A任务中的一段子任务是将货物从A1搬运到A2；B任务中的一段子任务是将货物从B1搬运到B2。

[0087] 步骤3：调度线程根据子任务的起始点、目标点及参数使用图搜索法输出当前子任务的任务路径。

[0088] A子任务的任务路径，如图4所示，首先为图搜索法输入相关参数：包括网状图和A任务的起始点、目标点；然后，图搜索法输出路径顺序为：27、47、46、33、32、76、31、30、39、38、52。机器人识别路径方法为：从27到47机器人沿着前进方向行驶，保持姿态不变，因为
47和27都是90度姿态限定点；从47到46，机器人横向左移，保持姿态不变，当两点姿态（路点一般有两个属性，如X、Y值属性、姿态是否限定属性，如果机器人在该点上只能是水平或垂直的角度，则称其为姿态限定，如果小车可以旋转，则称其为姿态不限定点）不同时，如果目标点为姿态不限定点，机器人在目标点时可以保持原来的姿态不变；从46到33机器人必须先旋转90度，再竖直向上移动到33点：当两点姿态属性不同时，如果目标点为姿态限定点，而起始点为姿态不限定点，机器人必须先旋转角度，再移动到目标点；33、32、76、31、
30都为姿态相同的限定点，因此机器人从33运动到30时，可以一直保持姿态不变，做横向左移动运动；从30到39，由于两点姿态属性不同，并且目标点为姿态不限定点，因此机器人在到达目标点39时可以保持原来的姿态不变；从39到38，由于两点姿态属性不同，此时目标点为姿态限定点，而起始点为姿态不限定点，因此机器人必须在起始点39先旋转角度，再移动到38;从38到52，由于两点都为姿态相同的限定点，可以保持姿态不变而下移。

[0089] B子任务的任务路径，如图8所示，首先为图搜索法输入相关参数：包括网状图和B子任务的起始点、目标点；然后，图搜索法输出路径顺序为：48、36、35、28、29、75、30、31、42、43、44、23、10、11。机器人识别路径方法：48、36都为姿态限定点，机器人可保持90度姿态不变，上移到36点；36为姿态限定点，35为姿态不限定点，由于两点姿态属性不同，此时起始点为姿态限定点，目标点为姿态不限定点，机器人可以保持姿态不变横向左移到目标点；35为姿态不限定点，28为180度姿态限定点，由于两点姿态属性不同，并且目标点为姿态限定点，因此机器人必须在起始点35旋转姿态后再到达目标点28；28、29、75、30、31都为
180度姿态限定点，机器人作横向右移，保持姿态不变；31为姿态限定点，42为姿态不限定点，由于两点姿态属性不同，此时起始点31为姿态限定点，目标点42为姿态不限定点，因此机器人可以保持180度姿态不变向下平移到42点；42为姿态不限定点，43为姿态限定点，由于两点姿态属性不同，起始点42为姿态不限定点，目标点43为姿态限定点，因此机器人必须在起始点42旋转姿态为90度后到达目标点43；43、44、23、10、11都为姿态限定点，因此机器人在从43移动到11时，姿态保持90度不变。

[0090] 步骤4：调度线程判断该子任务目标点是否被上一个的任务释放掉，如图4所示，由于A任务目标点被占用，因此，需要等待A任务目标点移出再进行任务标记，当目标点被释放后，进入步骤5。

[0091] 步骤5：调度线程使用携带方向和排序特征的任务编号标记每个任务路经，被标记的点包括当前任务路径上的点以及它的相干点；

[0092] 如图6、图7所示，A任务目标点已经被释放，则执行任务标记。标记任务路线时，不仅要标记路径上的点（图搜索指出的路径上各个点），还要标记这条路径的所有相干路点，A任务路径上的相干路点从右到左顺序为：45、44、43、42、41、40、75，其中，42可转点在此作为31的相干点，在这个任务中，为从属占用方式，同时，42也可以是独立于本任务之外的独立可转点。用任务编号标记A任务如图7所示，例如44是76的相干路点，其排序值等同于76的排序值，都为A6；75是38的相干点，其排序值等同于38的排序值，都为A10。

[0093] 如图9、图10所示，用任务编号标记B任务路线的路径：标记任务路线时，不仅要标记路径上的点（图搜索指出的路径上各个点），还要标记这条路径的所有相干路点。B任务路径上的相干路点从左到右顺序为：34、37、38、39、40、41、76；其中，39可转点在此作为30的相干点，76交叉路点在此作为44的相干点，它们在这个任务中，都为从属占用方式；同时，39和76也可以是独立于本任务之外的独立可转点和独立交叉路点。用任务编号标记B任务如图10所示。

[0094] 如图11所示，该图标注A任务和B任务标记的状态图。

[0095] 步骤6：调度线程标记完所有任务路径后，将标记后的任务送入执行队列，返回步骤2；

[0096] 步骤7：执行线程执行任务队列中的各任务抢占资源变量；

[0097] 步骤8：执行线程将所有路点上被标记至少两个任务编号、并且方向相反的路点组合的区域划分为冲突区，如图12所示。

[0098] 步骤9：执行线程判断冲突区是否释放干净，如果释放干净转入步骤10；如果没有释放干净转入步骤11。

[0099] 步骤10：执行线程向移动机器人发送执行任务的命令。

[0100] 步骤11：执行线程释放资源变量给调度服务器，返回步骤7。

[0101] 本发明的工作原理是：如图13、图14所示，假设B任务抢先获得了资源变量,但A任务距离冲突区近一些,因此A任务先进入冲突区,当B任务接受调度服务器关于A任务已经进已经进入冲突区的信息后,B任务原地等待A任务走过冲突区才继续执行任务，由此解决避碰问题。

[0102] 需要强调的是，本发明所述的实施例是说明性的，而不是限定性的，因此本发明并不限于具体实施方式中所述的实施例，凡是由本领域技术人员根据本发明的技术方案得出的其他实施方式，同样属于本发明保护的范围。