基于拓扑地图的多移动机器人调度方法及系统

摘要

本发明公开了一种基于拓扑地图的多移动机器人调度方法，包括获取待调度区域的地图并建模得到拓扑地图；对获取的拓扑地图进行处理得到压缩宏环图；当待调度区域内的移动机器人接受到新指令或移动到当前连边的设定位置时为移动机器人规划多条候选路径；对多条候选路径进行安全性判断并给移动机器人下达下一步的控制指令；重复上述步骤完成待调度区域内多移动机器人的调度。本发明还公开了一种包括了所述基于拓扑地图的多移动机器人调度方法的系统。本发明通过创新性的算法，在拓扑地图下完全避免了死锁的发生，提高了多移动机器人调度过程的可靠性、灵活性和效率。

权利要求

1.一种基于拓扑地图的多移动机器人调度方法，其特征在于包括如下步骤：S1. 获取待调度区域的地图，并建模得到拓扑地图；

S2. 对步骤S1获取的拓扑地图进行处理得到压缩宏环图；具体为为每个叶子节点添加自环生成图 ，然后分离自环生成图 中的所有桥边，得到宏环集，其中 为宏环且 ， 为宏环 的顶点集合， 为宏环 的连边集合，为宏环 的连边的数量；最后，在自环生成图 中将所有宏环压缩为节点，从而得到压缩宏环图CMG；

S3. 当待调度区域内的移动机器人接受到新指令或移动到当前连边的设定位置时，为移动机器人规划多条候选路径；具体为当待调度区域内的移动机器人接受到新指令，或者当调度区域内的移动机器人在当前连边上移动的距离超过了当前连边的x%时，采用Dijkstra算法为移动机器人规划多条候选路径；x为(0,100)上的正数；

具体为采用如下步骤为移动机器人规划多条候选路径：A. 在步骤S2得到的拓扑地图G中，在每次进行候选路径规划时，均将移动机器人所在边的前向首节点作为源点s；

B. 根据拓扑地图G的邻接矩阵，采用现有的Dijkstra算法为移动机器人规划一条从源点s至目标点d的最短路径p1；

C. 根据步骤B得到的最短路径p1上的第一个分叉点，以第一个分叉点为第一源点继续规划若干条不同的从第一源点至目标点d的路径，从而得到若干条从源点s至目标点d的路径，构成可选路径集合P；具体为采用如下步骤构成可选路径集合P：C1. 找到最短路径p1上的第一个分叉点v，此时源点s到第一分叉点v仅有一条前向路径p0；

C2. 将第一分叉点v作为第一源点；

C3. 在拓扑图中删除第一源点v后最短路径p1上的第一条边，采用现有的Dijkstra算法为移动机器人规划一条从第一源点v至目标点d的最短路径p2；

C4. 在拓扑图中删除步骤C3得到的最短路径p2的首个连边，并将路径p0与p2拼接后存入可选路径集合P；

C5. 重复步骤C3~C4直至最短路径p2为空，从而得到最终的可选路径集合P；

S4. 对步骤S3得到的多条候选路径进行安全性判断，从而给移动机器人下达下一步的控制指令；具体为采用如下步骤进行安全性判断并给移动机器人下达下一步的控制指令：a. 获取待调度区域的所有移动机器人的数据信息；

b. 在自环生成图 中，将移动机器人所在的连边转化为对应其移动方向的有向边，生成部分有向图D用于表示当前状态；

c. 根据宏环集M，将可选路径集合P中的路径pi分离为pib、piu、pibub、ui1和ui2；其中pib为路径pi的第一个宏环前的路径，piu为路径pi的第一个宏环内的路径，pibub为路径pi的第一个宏环和第二个宏环之间的桥边，ui1为路径pi的第一个宏环，ui2为路径pi的第二个宏环；

d. 采用如下步骤判断路径pi的安全性：d1. 若路径pi上的第一条边没有被任何移动机器人占领，则采用如下步骤继续进行d2~d3的判定；否则，判定路径pi为不安全；

d2. 若路径pib为空，则对路径piu进行判定：若路径piu为空，则判定路径pi为安全；

若路径piu不为空，则采用如下步骤继续进行d2‑1~ d2‑4的判定：d2‑1. 在部分有向图D内标记宏环ui1内涉及到的所有的边和节点，得到部分有向图D的子图 ：

d2‑2. 将当前所有处于宏环ui1内的移动机器人构成集合ui1_controller；

d2‑3. 遍历宏环ui1内路径piu上的连边：若连边已经被其他移动机器人占有，则判定路径pi为不安全；

若连边未被其他移动机器人占有，则在子图 上将相应连边转换为相应方向的有向边并得到第一子图 ，再进行判断：若集合ui1_controller内所有移动机器人在第一子图中均能够按照路径达到虚拟前进连边且子图 为强连通图，则判定路径pi为安全，同时将当前遍历的连边设置为移动机器人的虚拟前进边；否则，重复步骤d2‑3直至所有连边均遍历完成；

d2‑4. 若宏环ui2的容量大于0且pibub上不存在与当前移动机器人相反方向移动的机器人，则判定路径pi为安全，同时设pibub的首条边为当前移动机器人的虚拟前进边；否则，判定路径pi为不安全；

d3. 路径pib不为空，则采用如下步骤继续进行的判定：d3‑1. 若宏环ui1的容量小于1，则判定路径pi为不安全；否则，采用后续的步骤d3‑2~d3‑3进行判断：

d3‑2. 针对所有当前处于桥边的移动机器人，将移动机器人当前连边前方首节点作为源点，以路径上最近的宏环作为目标点，构成二元组集合b_controller；

d3‑3. 基于压缩宏环图CMG，判断二元组集合b_controller中所有的二元组能否按照任意顺序完成配对关系，完成配对关系的定义为：每个二元组的源点能够与其他二元组无交互地到达对应的目标点：若不能，则判定路径pi为不安全；否则，采用步骤d2中对于路径piu的判定方法，对路径piu进行判定；

e. 采用如下规则给移动机器人下达下一步的控制指令：将第一个被判定为安全的路径pi直接分配给移动机器人，作为下一步的控制指令；

若所有路径都被判定为不安全，则移动机器人暂停移动，直至收到下一步的控制指令；

S5. 重复步骤S3 S4，完成待调度区域内多移动机器人的调度。

~

2.根据权利要求1所述的基于拓扑地图的多移动机器人调度方法，其特征在于步骤S1所述的获取待调度区域的地图，并建模得到拓扑地图，具体为获取待调度区域的地图，并将拓扑地图用加权无向图G=(V,E,W)表示，其中V为节点集合，E为连边集合，W为连边上的权重集合；同时规定在拓扑地图上连边权重值不小于移动机器人的长度的数值，且每条边同一时刻只允许容纳一台移动机器人。

3.根据权利要求2所述的基于拓扑地图的多移动机器人调度方法，其特征在于所述的为每个叶子节点添加自环生成图 ，具体为在后续的调度过程中，均以自环生成图 为参考工作环境，移动机器人的所处位置都在自环生成图 的连边上，地图的节点用于当作过渡且机器人不在节点上停留。

4.根据权利要求3所述的基于拓扑地图的多移动机器人调度方法，其特征在于步骤d3‑

3中所述的判断二元组集合b_controller中所有的二元组能否完成配对关系，具体为采用银行家算法判断二元组集合b_controller中所有的二元组能否完成配对关系。

5.一种系统，其特征在于包括了权利要求1 4之一所述的基于拓扑地图的多移动机器~

人调度方法。

说明书

基于拓扑地图的多移动机器人调度方法及系统

技术领域

[0001] 本发明属于移动机器人调度领域，具体涉及一种基于拓扑地图的多移动机器人调度方法及系统。

背景技术

[0002] 随着经济技术的发展和人们生活水平的提高，智能制造已经得到了广泛发展。伴随着工业4.0的提出，智能化的生产方式正逐步取代传统劳动密集型的生产方式，成为企业
降低成本获取更多利润的重要手段。企业内物流调度作为生产制造过程中的核心环节，主
要承担器械补料与产品运送的任务。在传统制造业中，尤其是大型高端装备制造业中，超过
95%的时间用于物料的搬运配送，仅有不到5%的时间用于加工与装配作业。因此，利用移动
机器人进行工厂内物流调度，是提高物料的运输配送效率的重要方式。

[0003] 一般地，多移动机器人调度是指多移动机器人在共享一个环境的前提下，协调它们的运动并使所有机器人都能达到目标位置。多移动机器人调度主要分为三个功能部分，
具体为任务分配，路径规划和调度：任务分配主要用于完成移动机器人与任务之间的匹配；
路径规划用于为给定的两点规划路径；调度用于处理机器人之间冲突的问题。在多移动机
器人调度中，移动机器人的冲突问题是非常突出的，而一旦发生冲突，整个调度系统将面临
崩溃或急需人工干预的情况，对生产效率的影响将造成巨大的损失。

[0004] 因此，许多国内外专家都致力于研究多移动机器人调度控制算法，以避免碰撞和死锁的问题。目前，大多数的算法都是基于时间窗的预防性策略；但是这样的算法往往限制
较为严格，不够灵活，而且可能会导致系统资源利用率和系统吞吐量降低；此外，这些类型
的方法具有随网络规模增大而指数增长的计算复杂度，且无法应对突发事件。

发明内容

[0005] 本发明的目的之一在于提供一种可靠性高、灵活性高且效率较高的基于拓扑地图的多移动机器人调度方法。

[0006] 本发明的目的之二在于提供一种包括了所述基于拓扑地图的多移动机器人调度方法的系统。

[0007] 本发明提供的这种基于拓扑地图的多移动机器人调度方法，包括如下步骤：

[0008] S1. 获取待调度区域的地图，并建模得到拓扑地图；

[0009] S2. 对步骤S1获取的拓扑地图进行处理得到压缩宏环图；

[0010] S3. 当待调度区域内的移动机器人接受到新指令或移动到当前连边的设定位置时，为移动机器人规划多条候选路径；

[0011] S4. 对步骤S3得到的多条候选路径进行安全性判断，从而给移动机器人下达下一步的控制指令；

[0012] S5. 重复步骤S3 S4，完成待调度区域内多移动机器人的调度。~

[0013] 步骤S1所述的获取待调度区域的地图，并建模得到拓扑地图，具体为获取待调度区域的地图，并将拓扑地图用加权无向图G=(V,E,W)表示，其中V为节点集合，E为连边集合，
W为连边上的权重集合；同时规定在拓扑地图上连边权重值不小于移动机器人的长度，且每
条边同一时刻只允许容纳一台移动机器人。

[0014] 步骤S2所述的对步骤S1获取的拓扑地图进行处理得到压缩宏环图，具体为为每个叶子节点添加自环生成图 ，然后分离自环生成图 中的所有桥边，得到宏环集
，其中 为宏环且 ， 为宏环 的顶点集合， 为
宏环 的连边集合， 为宏环 的连边的数量；最后，在自环生成图 中将所有宏环压
缩为节点，从而得到压缩宏环图CMG。

[0015] 所述的为每个叶子节点添加自环生成图 ，具体为在后续的调度过程中，均以自环生成图 为参考工作环境，移动机器人的所处位置都在自环生成图 的连边上，地图的
节点用于当作过渡且机器人不在节点上停留。

[0016] 步骤S3所述的当待调度区域内的移动机器人接受到新指令或移动到当前连边的设定位置时，为移动机器人规划多条候选路径，具体为当待调度区域内的移动机器人接受
到新指令，或者当调度区域内的移动机器人在当前连边上移动的距离超过了当前连边的x%
时，采用Dijkstra算法为移动机器人规划多条候选路径；x为(0,100)上的正数。

[0017] 所述的采用Dijkstra算法为移动机器人规划多条候选路径，具体为采用如下步骤为移动机器人规划多条候选路径：

[0018] A. 在步骤S2得到的拓扑地图G中，在每次进行候选路径规划时，均将移动机器人所在边的前向首节点作为源点s；

[0019] B. 根据拓扑地图G的邻接矩阵，采用现有的Dijkstra算法为移动机器人规划一条从源点s至目标点d的最短路径p1；

[0020] C. 根据步骤B得到的最短路径p1上的第一个分叉点，以第一个分叉点为第一源点继续规划若干条不同的从第一源点至目标点d的路径，从而得到若干条从源点s至目标点d
的路径，构成可选路径集合P。

[0021] 步骤C所述的根据步骤B得到的最短路径p1上的第一个分叉点，以第一个分叉点为第一源点继续规划若干条不同的从第一源点至目标点d的路径，从而得到若干条从源点s至
目标点d的路径，构成可选路径集合P，具体为采用如下步骤构成可选路径集合P：

[0022] C1. 找到最短路径p1上的第一个分叉点v，此时源点s到第一分叉点v仅有一条前向路径p0；

[0023] C2. 将第一分叉点v作为第一源点；

[0024] C3.  在拓扑图中删除第一源点v后最短路径p1上的第一条边，采用现有的Dijkstra算法为移动机器人规划一条从第一源点v至目标点d的最短路径p2；

[0025] C4. 在拓扑图中删除步骤C3得到的最短路径p2的首个连边，并将路径p0与p2拼接后存入可选路径集合P；

[0026] C5. 重复步骤C3~C4直至最短路径p2为空，从而得到最终的可选路径集合P。

[0027] 步骤S4所述的对步骤S3得到的多条候选路径进行安全性判断，从而给移动机器人下达下一步的控制指令，具体为采用如下步骤进行安全性判断并给移动机器人下达下一步
的控制指令：

[0028] a. 获取待调度区域的所有移动机器人的数据信息；

[0029] b. 在自环生成图 中，将移动机器人所在的连边转化为对应其移动方向的有向边，生成部分有向图D用于表示当前状态；

[0030] c. 根据宏环集M，将可选路径集合P中的路径pi分离为pib、piu、pibub、ui1和ui2；其中pib为路径pi的第一个宏环前的路径，piu为路径pi的第一个宏环内的路径，pibub为路径pi的第
一个宏环和第二个宏环之间的桥边，ui1为路径pi的第一个宏环，ui2为路径pi的第二个宏环；

[0031] d. 采用如下步骤判断路径pi的安全性：

[0032] d1. 若路径pi上的第一条边没有被任何移动机器人占领，则采用如下步骤继续进行d2~d3的判定；否则，判定路径pi为不安全；

[0033] d2. 若路径pib为空，则对路径piu进行判定：

[0034] 若路径piu为空（意味着下一个点即为目标点），则判定路径pi为安全；

[0035] 若路径piu不为空，则采用如下步骤继续进行d2‑1~ d2‑4的判定：

[0036] d2‑1. 在部分有向图D内标记宏环ui1内涉及到的所有的边和节点，得到部分有向图D的子图 ：

[0037] d2‑2. 将当前所有处于宏环ui1内的移动机器人构成集合ui1_controller；

[0038] d2‑3. 遍历宏环ui1内路径piu上的连边：

[0039] 若连边已经被其他移动机器人占有，则判定路径pi为不安全；

[0040] 若连边未被其他移动机器人占有，则在子图 上将相应连边转换为相应方向的有向边并得到第一子图 ，再进行判断：若集合ui1_controller内所有移动机器人在第一
子图 中均能够按照路径达到虚拟前进连边且子图 为强连通图，则判定路径pi为安
全，同时将当前遍历的连边设置为移动机器人的虚拟前进边；否则，重复步骤d2‑3直至所有
连边均遍历完成；

[0041] d2‑4. 若宏环ui2的容量大于0且pibub上不存在与当前移动机器人相反方向移动的机器人，则判定路径pi为安全，同时设pibub的首条边为当前移动机器人的虚拟前进边；否则，
判定路径pi为不安全；

[0042] d3. 路径pib不为空，则采用如下步骤继续进行的判定：

[0043] d3‑1. 若宏环ui1的容量小于1，则判定路径pi为不安全；否则，采用后续的步骤d3‑2 d3‑3进行判断：
~

[0044] d3‑2. 针对所有当前处于桥边的移动机器人，将移动机器人当前连边前方首节点作为源点（即路径pi的第一个节点），以路径上最近的宏环（即ui1）作为目标点，构成二元组
集合b_controller；

[0045] d3‑3. 基于压缩宏环图CMG，判断二元组集合b_controller中所有的二元组能否按照任意顺序完成配对关系，完成配对关系的定义为：每个二元组的源点能够与其他二元
组无交互地到达对应的目标点：若不能，则判定路径pi为不安全；否则，采用步骤d2中对于
路径piu的判定方法（不考虑路径pib的状态），对路径piu进行判定；

[0046] e. 采用如下规则给移动机器人下达下一步的控制指令：

[0047] 将第一个被判定为安全的路径pi直接分配给移动机器人，作为下一步的控制指令；

[0048] 若所有路径都被判定为不安全，则移动机器人暂停移动，直至收到下一步的控制指令。

[0049] 步骤d3‑3中所述的判断二元组集合b_controller中所有的二元组能否完成配对关系，具体为采用银行家算法判断二元组集合b_controller中所有的二元组能否完成配对
关系。

[0050] 本发明还提供了一种包括了所述基于拓扑地图的多移动机器人调度方法的系统。

[0051] 本发明提供的这种基于拓扑地图的多移动机器人调度方法及系统，通过创新性的算法，在拓扑地图下完全避免了死锁的发生，提高了多移动机器人调度过程的可靠性、灵活
性和效率。

附图说明

[0052] 图1为本发明的调度方法的方法流程示意图。

[0053] 图2为本发明的调度方法的实施例的拓扑地图以及预处理的示意图。

[0054] 图3为本发明的调度方法的系统状态示意图。

具体实施方式

[0055] 如图1所示为本发明的调度方法的方法流程示意图：本发明提供的这种基于拓扑地图的多移动机器人调度方法，包括如下步骤：

[0056] S1. 获取待调度区域的地图，并建模得到拓扑地图；具体为获取待调度区域的地图，并将拓扑地图用加权无向图G=(V,E,W)表示，其中V为节点集合，E为连边集合，W为连边
上的权重集合；同时规定在拓扑地图上连边权重值不小于移动机器人的长度，且每条边同
一时刻只允许容纳一台移动机器人；

[0057] S2. 对步骤S1获取的拓扑地图进行处理得到压缩宏环图；具体为为每个叶子节点添加自环生成图 ，然后分离自环生成图 中的所有桥边，得到宏环集
，其中 为宏环且 ， 为宏环 的顶点集合， 为宏环 的连边集合，
为宏环 的连边的数量；最后，在自环生成图 中将所有宏环压缩为节点，从而得到压缩
宏环图CMG；

[0058] 具体实施时，在后续的调度过程中，均以自环生成图 为参考工作环境，移动机器人的所处位置都在自环生成图 的连边上，地图的节点用于当作过渡且机器人不在节点上
停留；

[0059] S3. 当待调度区域内的移动机器人接受到新指令或移动到当前连边的设定位置时，为移动机器人规划多条候选路径；具体为当待调度区域内的移动机器人接受到新指令，
或者当调度区域内的移动机器人在当前连边上移动的距离超过了当前连边的x%时，采用
Dijkstra算法为移动机器人规划多条候选路径；x为0 100的正数；
~

[0060] 具体实施时，采用如下步骤为移动机器人规划多条候选路径：

[0061] A. 在步骤S2得到的拓扑地图G中，在每次进行候选路径规划时，均将移动机器人所在边的前向首节点作为源点s；

[0062] B. 根据拓扑地图G的邻接矩阵，采用现有的Dijkstra算法为移动机器人规划一条从源点s至目标点d的最短路径p1；

[0063] C. 根据步骤B得到的最短路径p1上的第一个分叉点，以第一个分叉点为第一源点继续规划若干条不同的从第一源点至目标点d的路径，从而得到若干条从源点s至目标点d
的路径，构成可选路径集合P；具体为采用如下步骤构成可选路径集合P：

[0064] C1. 找到最短路径p1上的第一个分叉点v，此时源点s到第一分叉点v仅有一条前向路径p0；

[0065] C2. 将第一分叉点v作为第一源点；

[0066] C3.  在拓扑图中删除第一源点v后最短路径p1上的第一条边，采用现有的Dijkstra算法为移动机器人规划一条从第一源点v至目标点d的最短路径p2；

[0067] C4. 在拓扑图中删除步骤C3得到的最短路径p2的首个连边，并将路径p0与p2拼接后存入可选路径集合P；

[0068] C5. 重复步骤C3~C4直至最短路径p2为空，从而得到最终的可选路径集合P；

[0069] S4. 对步骤S3得到的多条候选路径进行安全性判断，从而给移动机器人下达下一步的控制指令；具体为采用如下步骤进行安全性判断并给移动机器人下达下一步的控制指
令：

[0070] a. 获取待调度区域的所有移动机器人的数据信息；包括位置，执行路径，以及虚拟前进连边等；

[0071] b. 在自环生成图 中，将移动机器人所在的连边转化为对应其移动方向的有向边，生成部分有向图D用于表示当前状态；显然，自环生成图 和部分有向图D之间的顶点和
连边依然存在一一对应关系；

[0072] c. 根据宏环集M，将可选路径集合P中的路径pi分离为pib、piu、pibub、ui1和ui2；其中pib为路径pi的第一个宏环前的路径，piu为路径pi的第一个宏环内的路径，pibub为路径pi的第
一个宏环和第二个宏环之间的桥边，ui1为路径pi的第一个宏环，ui2为路径pi的第二个宏环；

[0073] d. 采用如下步骤判断路径pi的安全性：

[0074] d1. 若路径pi上的第一条边没有被任何移动机器人占领，则采用如下步骤继续进行d2~d3的判定；否则，判定路径pi为不安全；

[0075] d2. 若路径pib为空，则对路径piu进行判定：

[0076] 若路径piu为空（意味着下一个点即为目标点），则判定路径pi为安全；

[0077] 若路径piu不为空，则采用如下步骤继续进行d2‑1~ d2‑4的判定：

[0078] d2‑1. 在部分有向图D内标记宏环ui1内涉及到的所有的边和节点，得到部分有向图D的子图 ：

[0079] d2‑2. 将当前所有处于宏环ui1内的移动机器人构成集合ui1_controller；

[0080] d2‑3. 遍历宏环ui1内路径piu上的连边：

[0081] 若连边已经被其他移动机器人占有，则判定路径pi为不安全；

[0082] 若连边未被其他移动机器人占有，则在子图 上将相应连边转换为相应方向的有向边并得到第一子图 ，再进行判断：若集合ui1_controller内所有移动机器人在第一
子图 中均能够按照路径达到虚拟前进连边且子图 为强连通图，则判定路径pi为安
全，同时将当前遍历的连边设置为移动机器人的虚拟前进边；否则，重复步骤d2‑3直至所有
连边均遍历完成；

[0083] d2‑4. 若宏环ui2的容量大于0且pibub上不存在与当前移动机器人相反方向移动的机器人，则判定路径pi为安全，同时设pibub的首条边为当前移动机器人的虚拟前进边；否则，
判定路径pi为不安全；

[0084] d3. 路径pib不为空，则采用如下步骤继续进行的判定：

[0085] d3‑1. 若宏环ui1的容量小于1，则判定路径pi为不安全；否则，采用后续的步骤d3‑2 d3‑3进行判断：
~

[0086] d3‑2. 针对所有当前处于桥边的移动机器人，将移动机器人当前连边前方首节点作为源点（即路径pi的第一个节点），以路径上最近的宏环（即ui1）作为目标点，构成二元组
集合b_controller；

[0087] d3‑3. 基于压缩宏环图CMG，判断二元组集合b_controller中所有的二元组能否按照任意顺序完成配对关系，完成配对关系的定义为：每个二元组的源点能够与其他二元
组无交互地到达对应的目标点：若不能，则判定路径pi为不安全；否则，采用步骤d2中对于
路径piu的判定方法（不考虑路径pib的状态），对路径piu进行判定；其中，判定能否完成配对
关系的过程，为采用银行家算法进行判断；

[0088] e. 采用如下规则给移动机器人下达下一步的控制指令：

[0089] 将第一个被判定为安全的路径pi直接分配给移动机器人，作为下一步的控制指令；

[0090] 若所有路径都被判定为不安全，则移动机器人暂停移动，直至收到下一步的控制指令；

[0091] S5. 重复步骤S3 S4，完成待调度区域内多移动机器人的调度。~

[0092] 以下结合一个实施例，对本发明方法进行进一步说明：

[0093] 多移动机器人系统示例拓扑地图如图2所示，为了避免碰撞，提高系统的可预测性，移动机器人被限制在连边上移动，并且采用区域控制使每条连边同时只允许一个移动
机器人进入，系统中的移动机器人按照指令实现在拓扑地图节点间的无碰撞和无死锁移
动。

[0094] 首先，对拓扑地图作G预处理，如图2所示。给拓扑地图G的每个叶子节点添加自环生成图 ；然后，分离出 中的所有桥边，得到一个宏环集 ；如宏环
，其中V2，E2，W2分别为 的顶点集、连边集和初始容量（即宏环内连边的数
量），更加具体而言，E2={(2,3),(2,6),(3,4),(3,7),(4,10),(6,7),(6,8),(7,9),(8,9),
(9,10),}，W2=10，V2={2,3,4,6,7,8,9,10}。进一步地，将所有宏环压缩为结点，使用桥边连
接压缩的结点生成压缩宏环图CMG。

[0095] 假设当前状态下，移动机器人C2的可执行路径pc2={3,4,5}，虚拟前进连边为None；移动机器人C3的可执行路径pc3={8,6,2,1}，虚拟前进连边为None。根据当前系统状
态信息生成部分有向图D（如图3所示）。另外假设此时移动机器人C1接到调度指令，从当前
位置移动到节点1。因此，源点s=5，目的点d=1。根据拓扑地图G的邻接矩阵，采用标准的
Dijkstra算法为移动机器人规划一条从源点s至目标点d的最短路径p01={5,4,3,2,1}。将其
放入可选路径集合P。

[0096] 然后，遍历路径p01，找到p01路径上第一个分叉点v=4（即度大于2的节点），并且在拓扑图中暂时删去v点后p01的第一条边，即连边(4,3)。显然，s到v有且仅有一条前向路径，
表示为p0=(5,4)。将v作为源点，继续采用标准的Dijkstra算法为移动机器人规划一条从v
至d的最短路径p2={4,10,9,8,6,2,1}，并且在拓扑图中暂时删除p2的首个连边(4,10)，将p0
与p2拼接后得到的p02={5,4,10,9,8,6,2,1}的存入可选路径集合P。最后再也找不到从v到d
的路径，因此停止规划路径。将可执行路径集P按照权重之和的大小排序后，对路径进行安
全判断。

[0097] 最后，进行路径安全性判断。根据系统信息以及拓扑地图获得部分有向图D代表当前系统状态。

[0098] 针对于可选路径集P中的第一条路径p01={5,4,3,2,1}。根据宏环集M，将p01分离为pb=(5,4)，pu=(4,3,2)，pbub=(2,1)， ， ；由于pu的首条边被占领，因此p01是不
安全路径。

[0099] 针对p02={5,4,10,9,8,6,2,1}，分离可得pb=(5,4)，pu=(4,10,9,8,6,2)，pbub=(2,1)， ， ；因为p02依次满足多个条件，即1). 宏环u1的容量大于0；2). 假设pb
的首条边被占领后，整个系统所有位于桥边的移动机器人能依次进入各自最近的宏环；3). 
在pu内能找到一条连边(4,10)，宏环u1内其他移动机器人能够顺利移动到虚拟前进边，并且
为强连通图；因此，p02是安全的，可用于移动机器人C1执行。

[0100] 如果不存在安全可执行路径，则移动机器人将原地等待。

[0101] 每当系统状态改变或者移动机器人前进到当前连边的80%，将重复上述步骤，持续进行调度，避免碰撞和死锁发生。