(19)中华人民共和国国家知识产权局
(12)发明专利申请
(10)申请公布号 (43)申请公布日 (21)申请号 201910378048.9
(22)申请日 2019.05.08
(71)申请人 胡贤良
地址 310027 浙江省杭州市西湖区浙大路
38号
申请人 梁克维 虞钉钉
(72)发明人 胡贤良 梁克维 虞钉钉
(51)Int.Cl.
G01C 21/20(2006.01)
(54)发明名称
(57)摘要
一种多机器人系统的路径规划方法。
技术方案包括如下步骤：如下步骤：首先，接收当前系统
的地图信息，将系统地图信息进行建模，得到相
应的图G(V ,E)；其次，根据系统的任务要求，重新
构建路径规划方法中的指导函数，使其能更好地
引导路径规划算法地搜索，满足系统要求；最后
根据该指导函数，利用动态规划思想，进行路径
地快速搜索，最后得到相应的路径。本发明充分
利用了指导函数，改进了经典算法只考虑距离的
局限性，
提高了整个系统的效率。权利要求书1页 说明书3页 附图3页CN 111912407 A 2020.11.10
C N 111912407
A
1.一种多机器人系统的路径规划方法，其特征在于，包括以下步骤：接收当前系统的地图信息，将系统
地图信息进行建模，得到相应的图G(V ,E)；根据系统的任务要求，重新构建路径规划方法中的指导函数，使其能更好地引导路径规划算法地搜索，满足系统要求；根据该指导函数，利用动态规划思想，进行路径地快速搜索，最后得到相应的路径。
2.根据权利要求1所述的一种多机器人系统的路径规划方法，其特征在于，所述根据地图信息建模是将系统所在空间按一定长度长方形进行划分，将每个正方形的中心标记为图中的顶点，构成顶点集V，每个顶点都带有相关属性，顶点与相邻顶点之间的连线构成边集E。 3.根据权利要求1所述的一种多机器人系统的路径规划方法，其特征在于，指导函数的构建公式为：
W(n) = O(n) + H(n) + G(n)
其中，n为当前计算顶点，O(n)是从起点到当前点的最优路径的权重估计，H(n)是从当前点n到终点的最优路径的权重估计, G(n)是根据任务要求所设计的额外指导项。
4.根据权利要求1所述的一种多机器人系统的路径规划方法，其特征在于，多机器人系统的机器人数量为1~1000。
5.根据权利要求2所述的一种多机器人系统的路径规划方法，其特征在于，空间划分的长方形的距离可以是0.1m -5m。
6.根据权利要求2所述的一种多机器人系统的路径规划方法，其特征在于，顶点集V的顶点属性包括：顶点的功能属性、顶点的位置属性。
7.根据权利要求2所述的一种多机器人系统的路径规划方法，其特征在于，边集E中的边包含了权重属性。
8.根据权利要求3所述的一种多机器人系统的路径规划方法，其特征在于，针对于时间最小的任务要求，W(n),G(n)的定义公式如下：
H(n) = |x1-x2| + |y1-y2|
G(n) = seg + c*d
其中，(x1,y1)表示顶点n的坐标，（x2,y2）表示终点的坐标, n为当前计算顶点，seg为当前路径的直线段数目，c为当前路径的拥挤程度，d表示沿着n的父顶点到达起点的路径p 的总距离。
9.根据权利要求7所述的一种多机器人系统的路径规划方法，其特征在于，c的范围为0~1。
权 利 要 求 书1/1页CN 111912407 A
一种多机器人系统的路径规划方法
技术领域
[0001]本发明属于路径规划技术领域，具体地说，本发明涉及一种多机器人系统的路径规划方法。
背景技术
[0002]机器人是自动执行工作的机器装置。它既可以接受人类指挥，又可以运行预先编排的程序，也可以根据以人工智能技术制定的原则纲领行动。它的任务是协助或取代人类工作的工作，例如生产业、建筑业，或是危险的工作。随着科技发展，越来越多的智能机器人被应用于人们的日常工作和生活中。
[0003]机器人由于其方便及智能性，被广泛用于仓储、物流、工厂等环境中。在这些应用场景中，机器人多被用于搬运工作，大量重复、费力费时的体力工作都被机器人所代替。在仓储中，机器人被用于搬运货架到指定区域，如亚马逊的kiva机器人，天猫的geek+机器人；在物流中，各式各样的物流机器人被用于搬运货物；在工厂中，叉车机器人等也被广泛应用。
[0004]机器人的应用需要有一个完整的多机器人系统来支撑，其中机器人的路径规划是系统核心之一。通过路径规划方法，多机器人系统可以计算出起点到终点的路径，并将其发送给机器人，使机器人能沿着相应的路径运行。在运行中，机器人可能会遇到一些特殊情况，而此时需要路径规划方法能快速计算出新的可行路径。
[0005]自动导航小车的路径规划通常会采用静态路径规划方法。多机器人系统的路径规划问题和车辆路径问题有关系，而车辆路径问题是一个NP-hard问题，因此，对于多机器人系统的路径规划问题主要分为确定性算法和不确定算法，其中不确定性算法又包含启发式算法、智能算法等等，其中最短路径算法是应用最多的路径规划方法之一。目前，路径规划方法以基于最短路径算法为主，然而上述方法只能计算距离最短的路径，很多情形下，并不是满足系统要求的最优路径，影响了整个系统的效率；而且上述方法无法根据系统要求，进行调整，计算出合适的路径，鲁棒性很差。
发明内容
[0006]本发明的目的在于，针对现有的应用最短路径算法进行路径规划的局限性，提出一种多机器人系统的路径规划方法，这种方法能根据不同场景的要求，通过构建合适的指导函数，计算出符合系统要求的路径，提高系统的运行效率。
[0007]为实现所述目的，本发明的技术解决方案是一种多机器人系统的路径规划方法，该方法包含以下步骤：首先，接收当前系统的地图信息，将系统地图信息进行建模，得到相应的图G(V,E)；其次，根据多机器人系统的任务要求，重新构建路径规划方法中的指导函数，使其能更好地引导路径规划算法地搜索，满足系统要求；最后根据该指导函数，利用动态规划思想，进行路径地快速搜索，最后得到相应的路径。
[0008]与现有技术相比，本发明的有益效果在于：1，本发明通过对地图的建模，能最大化
利用场地，提高整个系统的运行效率；2，本发明，运算速度快，运算所需的平均资源少，能满足各种多机器人系统的要求，能同时支持上百个机器人同时运行，利于集成，具有很强的实用性；3，本发明能基于系统的要求，构建出合适的指导函数，计算出更符合系统要求的路径，提高整个系统的效率。
附图说明
[0009]图1为本发明多机器人系统的路径规划方法流程图；
图2为本发明一个实施例的地图建模可视化图；
图3为本发明一个实施例路径规划方法核心算法流程图；
图4为本发明一个实施例与经典最短路径算法的系统效率对比图。
具体实施方式
[0010]下面结合附图和具体实施例，对本发明提供的一种多机器人系统的路径规划方法作进一步详细的解释。
[0011]首先根据系统的地图信息进行地图构建。系统的地图信息包含以下信息：地图的长度和宽度、地图的不同区域信息、地图的道路信息、道路的可通行方向信息。根据上述信息，构建出相应的图G(V,E)，其中V表示顶点集，每个顶点都拥有一个坐标（x,y）以及相应的区域属性，通过该属性可以获知该顶点的所属区域的功能；E是边集，每条边都连接着两个顶点，同时包含着方向信息。
[0012]其次，根据多机器人系统的任务要求，重新构建路径规划方法中的指导函数W。指导函数W是路径规划方法中的核心，每个顶点n都对应于一个指导函数值W(n)，通过该指导函数值W(n)，路径规划方法可以确定路径搜索的方向，生成合适的路径。路径的生成就是寻到从起点到终点总指导函数值最小的路径。指导函数W(n)可以由下式给出：W(n) = O(n) + H(n) + G(n)
其中，O(n)表示从起点到当前点的最优路径的权重估计，H(n)是从当前点n到终点的最优路径的权重估计, G(n)是根据任务要求所设计的额外指导项。O(n)、H(n)、G(n)三个函数估计越好，则生成的路径更好。若O(n)，H(n)，G(n)没有估计误差，则通过指导函数W(n)，就可以得到从起点到终点途中经过节点n的最优路径的权重；根据这个信息，只要选择所有顶点中W最小的顶点，就可以生成适合系统要求的最优路径。由于误差的存在，W(n)只是从起点到终点途中经过节点n的最优路径的权重估计，但在一定误差范围内，通过指导函数W (n)，路径规划算法仍可以快速生成一条满足系统要求的路径。
[0013]指导函数是根据多机器人系统要求来进行构建，不同系统要求构建的指导函数不同。系统中距离
信息是最容易获得也是最稳定的信息，因此，指导函数的构建可以基于距离信息，然后根据不同系统的要求进行相应的改进就可以获得更适用于系统的指导函数。如果系统需要机器人的距离最短，则指导函数W就是对路径距离的估计，可以直接利用距离信息得到相应的O和H的值，此时G的值为0；如果系统需要机器人运行时间最短，则指导函数W 就需要基于距离信息进行改进。由于距离和运行时间是正相关的，所以可以利用容易采集到的距离信息，同时做出一些改进，如G的值会随着当前路径拥挤程度的增加而增加，在同样距离情况下，如果路径涉及的直线段越多，则G的值也越大。经过上述改进，指导函数W所
产生的路径能更加满足系统的要求；如果系统需要机器人电量消耗最少，则指导函数W也可以基于电量的消耗函数和距离做出相应的改进。
[0014]最后根据该指导函数，利用动态规划思想，进行路径地快速搜索，最后得到相应的路径。路径搜索会涉及到两个列表L1和L2：L1中的顶点是待搜索的顶点，而L2中的顶点是已经搜索过的顶点。具体过程如下：(1)将输入的起点s放入列表L1中，计算指导函数值W(s)；
(2)选择列表L1中指导函数值最小的顶点n; (3)如果n就是终点e，将n放入列表L2中，结束算法；(4)否则，将n放入列表L2中，并且到顶点n可通过一条边就可以到达的所有顶点，对这些顶点x做如下操作：计算顶点x的指导函数值W(x)，若顶点x不在列表L2也不在列表L1中，则将顶点x加入列表L1中，并
且顶点n是顶点x的父顶点；若顶点x在列表L2中或列表L1中，且新计算的指导函数值小于原来的指导函数值，则将x放入列表L1中，且更新顶点x的指导函数值，并且将顶点n设置为顶点x的父顶点。不断重复(2)-(4)直到算法结束，最后从终点e开始沿着父顶点就可以得到一条满足要求的路径。
[0015]下面通过仿真的方法对本发明做进一步验证。由图2所示，仓储的地图信息经过建模，再进行可视化以后，可以分为三个区域：方块的打包区域、星星的货架区域、圆圈的道路区域。其中顶点与顶点之间的箭头表明了该顶点可通行的方向。对于仓储这样的场景，机器人完成单个搬运任务的时间越短越好，因此，基于时间的要求，指导函数W需要做出相应改进。O，H，G的值将有下面公式给出：
O(n) = d
H(n) = |x1-x2| + |y1-y2|
G(n) = seg + c*d
其中，d表示沿着n的父顶点到达起点的路径p的总距离；seg表示路径p的直线段数目，直线段数目越多，机器人完成该路径的时间越多；c表示路径p的拥挤程度，拥挤程度越高，机器人运行所需时间越长；(x1,y1)表示顶点n的坐标，（x2,y2）表示终点的坐标。
[0016]在该实例中，机器人需要搬运货架到指定的打包区域。当机器人没有负载货架时，其可以在地图
的道路区域和货架区域移动，而当机器人负载货架时，机器人无法进入货架区域，否则会造成碰撞。针对这个特点，为了提高效率，当机器人没有负载货架时，其运行范围会更加广泛，而运行范围的增大会使得机器人可以选择的路径会更多，可以选择更优的路径。图3是针对本仿真实例的路径规划算法流程图，其原理如前文所述，通过指导函数W的值，不断地递归进行搜索W值最小的顶点，最终得到满足要求的路径。通过指导函数的改进，算法生成的路径直线段数会减少，同时总距离保持不变，以此来减少机器人的转弯次数，以及增加机器人的最大速度运行时间，从而提高了整体效率。图4是仿真案例分别采用改进后算法和原始算法的结果对比图。实线是采用改进后算法在不同机器人数目下完成一定数量任务所需时间，从图中可以发现，在相同任务数目，相同机器人数量下，采用改进后算法可以比采用原始算法节省约10%的时间，确实提高了整个多机器人系统的效率。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议