多自移动设备的路径规划方法、装置、自移动设备与流程

1.本技术涉及路径规划技术领域，尤其涉及一种多自移动设备的路径规划方法、装置、自移动设备和存储介质。

背景技术：

2.在对多个自移动设备在同一工作区域内的路径进行规划时，会出现不同自移动设备的路径交叉，而在交叉的位置可能出现自移动设备碰撞的风险，影响自移动设备作业的安全性。
3.目前有通过自移动设备的传感器实时检测周围的环境，在判断有可能发生碰撞时及时调整运动状态，但是此类方式对自移动设备的要求较高，而且作业效率较低。

技术实现要素：

4.本技术实施例提供一种多自移动设备的路径规划方法、装置、自移动设备和存储介质，能够降低自移动设备碰撞的几率，提高作业效率。
5.第一方面，本技术提供了一种多自移动设备的路径规划方法，所述方法包括：
6.获取每个自移动设备的规划路径以及运动数据；
7.根据每个所述自移动设备的规划路径以及运动数据，获取各所述自移动设备之间的预测碰撞位置；
8.根据所述预测碰撞位置确定多个围绕所述预测碰撞位置的可选避障点；
9.根据各所述可选避障点与各所述自移动设备的规划路径的位置关系，确定各所述自移动设备的目标避障点；各所述自移动设备的目标避障点为不同位置的点；
10.根据各所述自移动设备的目标避障点更新对应所述自移动设备的规划路径。
11.第二方面，本技术提供了一种路径规划装置，包括：
12.一个或多个处理器，一个或多个处理器单独地或共同地工作，用于实现前述的多自移动设备的路径规划方法的步骤。
13.第三方面，本技术提供了一种自移动设备，包括：
14.一个或多个处理器，一个或多个处理器单独地或共同地工作，用于实现前述的多自移动设备的路径规划方法的步骤。
15.第四方面，本技术提供了一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，所述计算机程序被处理器执行时使所述处理器实现上述的多自移动设备的路径规划方法的步骤。
16.本技术公开了一种多自移动设备的路径规划方法、装置、自移动设备和存储介质，方法包括：根据每个自移动设备的规划路径以及运动数据，获取各所述自移动设备之间的预测碰撞位置；根据预测碰撞位置确定多个可选避障点；根据各所述可选避障点、所述预测碰撞位置与各所述自移动设备的规划路径的位置关系，确定各所述自移动设备的目标避障点；各所述自移动设备的目标避障点为不同位置的点；根据各所述自移动设备的目标避障
点更新对应所述自移动设备的规划路径。本技术实施例通过提前预测碰撞位置，根据碰撞位置给不同的自移动设备设置不同的目标避障点，以及根据目标避障点更新各自移动设备的路径，可以防止得到的路径之间产生交叉，因此在自移动设备在沿着根据该目标避障点规划的路径运行时，碰撞的几率大大降低；而且根据目标避障点更新路径，可以使自移动设备减少避撞的调整动作，提高作业效率。
附图说明
17.为了更清楚地说明本技术实施例的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本技术的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
18.图1为本技术实施例的多自移动设备的路径规划方法的流程示意图；
19.图2为一实施方式中自移动设备之间的预测碰撞位置的示意图；
20.图3为一实施方式中确定可选避障点的示意图；
21.图4为一实施方式中根据目标避障点更新规划路径的示意图；
22.图5为另一实施方式中确定可选避障点的示意图；
23.图6为一实施方式中根据目标避障点更新规划路径的示意图；
24.图7为另一实施方式中根据目标避障点更新规划路径的示意图；
25.图8为一实施方式中基于栅格地图的八邻域搜索方式的示意图；
26.图9为一实施方式中路径转折线段优化的示意图；
27.图10为本技术实施例提供的一种路径规划装置的示意性框图。；
28.图11为本技术实施例提供的自移动设备的示意性框图。
具体实施方式
29.下面将结合本技术实施例中的附图，对本技术实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本技术一部分实施例，而不是全部的实施例。基于本技术中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本技术保护的范围。
30.附图中所示的流程图仅是示例说明，不是必须包括所有的内容和操作/步骤，也不是必须按所描述的顺序执行。例如，有的操作/步骤还可以分解、组合或部分合并，因此实际执行的顺序有可能根据实际情况改变。
31.本技术的实施例提供了一种多自移动设备的路径规划方法、装置、自移动设备和存储介质。通过提前预测碰撞位置，根据碰撞位置给不同的自移动设备设置不同的目标避障点，以及根据目标避障点更新各自移动设备的路径，根据不同的目标避障点规划路径可以防止得到的路径之间产生交叉，因此在自移动设备在沿着根据该目标避障点规划的路径运行时，碰撞的几率大大降低；而且根据目标避障点更新路径，可以使自移动设备减少避撞的调整动作，提高作业效率。
32.请参阅图1，图1是本技术的实施例提供的一种多自移动设备的路径规划方法的流程示意图。多自移动设备的路径规划方法用于更新多个自移动设备的规划路径，以降低自移动设备碰撞的几率，提高作业效率。为便于说明，本技术实施例主要以更新两个自移动设
备的规划路径为例进行说明，应当理解多自移动设备不限于包括两个自移动设备。
33.本技术实施例提供的多自移动设备的路径规划方法可以应用于路径规划装置中，路径规划装置例如为自移动设备中的芯片或者电路，或者，也可以为控制设备或者控制设备中的芯片或者电路。
34.本技术实施例提供的多自移动设备的路径规划方法可以应用于自移动设备中，自移动设备例如包括机器人，如割草机器人、扫地机器人、排雷机器人、巡航机器人等，本实施例对此不做特别限定。
35.本技术实施例提供的多自移动设备的路径规划方法可以应用于终端或服务器等自移动设备的控制设备。终端可以是手机、平板电脑、笔记本电脑、台式电脑、个人数字助理等控制设备；服务器可以为独立的服务器，也可以为服务器集。
36.下面结合附图，对本技术的一些实施方式作详细说明。在不冲突的情况下，下述的实施例及实施例中的特征可以相互组合。
37.如图1所示，多自移动设备的路径规划方法包括以下步骤s110至步骤s150。
38.步骤s110、获取每个自移动设备的规划路径以及运动数据。
39.在一些实施方式中，多个自移动设备能够进行通信，或者多个自移动设备均能够与控制设备进行通信，以便自移动设备或者控制设备获取每个自移动设备的规划路径以及运动数据。
40.在一些实施方式中，各自移动设备存储有各自的规划路径以及运动数据，可以将各自的规划路径以及运动数据传输给应用路径规划方法的自移动设备。或者，各自移动设备可以将各自的规划路径以及运动数据传输给应用路径规划方法的控制设备，或者该控制设备存储有每个自移动设备的规划路径以及运动数据，控制设备根据每个自移动设备的规划路径以及运动数据执行路径规划方法的步骤。
41.示例性的，自移动设备的规划路径可以为用户输入的路径，或者为自移动设备自动规划的路径，例如自移动设备可以通过雷达、视觉传感器等传感器对工作环境进行探索，以及根据工作环境的信息规划得到所述规划路径。当然也不限于此，例如所述自移动设备的规划路径也可以为本技术实施例的路径规划方法更新得到的路径，例如在路径规划方法更新多个自移动设备的规划路径后，增加了新的自移动设备，或者自移动设备的运动数据改变，则可以再次根据所述路径规划方法对每个自移动设备的规划路径进行更新。
42.举例而言，所述自移动设备的运动数据包括但不限于一下至少一种：在起点的出发时间、移动速度、在暂停位置的暂停时间。自移动设备的运动数据可以由用户指定，或者也可以根据自移动设备的任务需求确定。
43.步骤s120、根据每个所述自移动设备的规划路径以及运动数据，获取各所述自移动设备之间的预测碰撞位置。
44.请参阅图2，自移动设备m1的起点e，终点h之间的规划路径以实线表示，自移动设备m2的起点f，终点g之间的规划路径以虚线表示。
45.示例性的，可以根据每个所述自移动设备的规划路径以及运动数据进行仿真计算，得到各自移动设备之间的预测碰撞位置。
46.举例而言，当自移动设备m1、自移动设备m2在各自的起点同时出发，且移动速度相等，以及自移动设备m1、自移动设备m2的规划路径的交叉点与自移动设备m1的起点e、自移
动设备m2的起点f之间的路径长度相等时，可以确定所述自移动设备m1、自移动设备m2的规划路径的交叉点为所述预测碰撞位置。
47.步骤s130、根据所述预测碰撞位置确定多个围绕所述预测碰撞位置的可选避障点。
48.请参阅图3，多个围绕所述预测碰撞位置的可选避障点包括可选避障点a、可选避障点b、可选避障点c和可选避障点d。
49.步骤s140、根据各所述可选避障点与各所述自移动设备的规划路径的位置关系，确定各所述自移动设备的目标避障点；各所述自移动设备的目标避障点为不同位置的点。
50.在一些实施方式中，各自移动设备的目标避障点均在各自移动设备的规划路径的左侧，例如确定可选避障点d为自移动设备m1的目标避障点，确定可选避障点a为自移动设备m2的目标避障点；或者各自移动设备的目标避障点均在各自移动设备的规划路径的右侧，例如确定可选避障点b为自移动设备m1的目标避障点，确定可选避障点c为自移动设备m2的目标避障点。
51.步骤s150、根据各所述自移动设备的目标避障点更新对应所述自移动设备的规划路径。
52.在一些实施方式中，各自移动设备的目标避障点位于对应自移动设备的更新后的规划路径上，或者与更新后的规划路径的距离小于预设值，如目标避障点位于更新后的规划路径的附近，也可以实现避撞的效果。
53.举例而言，请参阅图4，自移动设备m1的更新后的规划路径依次经过起点e、位置a、自移动设备m1的位置d、位置c、以及终点h；自移动设备m2的更新后的规划路径依次经过起点f、位置b、自移动设备m2的位置a、位置d、以及终点g。
54.举例而言，在自移动设备m1、自移动设备m2沿着各自的更新后的规划路径运行时，自移动设备m1到达位置a时，自移动设备m2到达位置b。之后自移动设备m1由位置a向位置d移动，自移动设备m2由位置b向位置a移动，以及自移动设备m1到达位置d时，自移动设备m2到达位置a。之后自移动设备m1由位置d向位置c移动，自移动设备m2由位置a向位置d移动，可以确定自移动设备m1、自移动设备m2沿着各自的更新后的规划路径运行，可以防止自移动设备m1、自移动设备m2发生碰撞。期间，自移动设备m1仅需在位置a、位置d、位置c调整运动状态，如转向，自移动设备m2仅需在位置b、位置a、位置d调整运动状态,可以确定自移动设备m1、自移动设备m2沿着各自的更新后的规划路径运行，能够降低自移动设备调整运动状态的频次，提高作业效率。
55.在一些实施方式中，所述根据所述预测碰撞位置确定多个围绕所述预测碰撞位置设置的可选避障点中：各所述可选避障点与所述预测碰撞位置的距离相同。可以降低确定各可选避障点时的计算复杂度。请参阅图5，例如可以以所述预测碰撞位置为圆心，以预设距离为半径确定一圆周，以及在该圆周上确定所述多个围绕所述预测碰撞位置设置的可选避障点。可以理解的，各可选避障点与所述预测碰撞位置的距离均等于所述预设距离。
56.示例性的，所述预设距离与所述自移动设备的作业区域大小成正相关关系。自移动设备的作业区域可以根据自移动设备作业时的形状、体积、转弯半径等中的至少一项确定。
57.通过根据所述自移动设备的作业区域确定各可选避障点与所述预测碰撞位置的
距离，可以使自移动设备在移动至与所述预测碰撞位置具有合适的距离时转向，防止在有自移动设备与所述预测碰撞位置的距离较近时，在转向时由于自移动设备的形状等发生碰撞，如在自移动设备的前方延伸出的割草装置相互碰撞。
58.在一些实施方式中，所述根据所述预测碰撞位置确定多个围绕所述预测碰撞位置设置的可选避障点中：各所述可选避障点位于各自移动设备的规划路径上。
59.示例性的，各所述可选避障点与所述预测碰撞位置的距离相同，且各所述可选避障点位于各自移动设备的规划路径上。
60.请参阅图3至图5，可选避障点a、可选避障点c位于自移动设备m1的规划路径上，可选避障点b、可选避障点d位于自移动设备m2的规划路径上。通过在所述自移动设备的规划路径上确定所述可选避障点，可以降低确定各可选避障点时的计算复杂度。
61.示例性的，所述根据所述预测碰撞位置确定多个围绕所述预测碰撞位置设置的可选避障点，包括：以所述预测碰撞位置为圆心，以预设距离为半径确定所述可选避障点所在的圆周；所述预设距离与所述自移动设备的作业区域大小成正相关关系；将所述圆周上与每个所述自移动设备的规划路径的交点确定为可选避障点。如图5所示，确定所述圆周与自移动设备m1的规划路径的交点为可选避障点a、可选避障点c，确定所述圆周与自移动设备m2的规划路径的交点为可选避障点b、可选避障点d。
62.在一些实施方式中，所述步骤s140根据各所述可选避障点与各所述自移动设备的规划路径的位置关系，确定各所述自移动设备的目标避障点，包括：确定每个所述自移动设备的规划路径与所述圆周的交点，并将第一个经过的交点作为目标路径点；在各所述可选避障点中，确定与每个所述自移动设备的目标路径点相邻的可选避障点为所述自移动设备的目标避障点，且每个所述自移动设备的目标避障点与对应的目标路径点均以所述预测碰撞位置为中心呈顺时针方向分布，或者均以所述预测碰撞位置为中心呈逆时针方向分布。
63.如图5所示，例如所述圆周与自移动设备m1的规划路径的第一个交点a为自移动设备m1的目标路径点a，确定与目标路径点a相邻的可选避障点d为所述自移动设备的目标避障点d,自移动设备m1的目标避障点d与目标路径点a以所述预测碰撞位置为中心呈顺时针方向分布；所述圆周与自移动设备m2的规划路径的第一个交点b为自移动设备m2的目标路径点b，确定与目标路径点b相邻的可选避障点a为所述自移动设备的目标避障点a,自移动设备m2的目标避障点a与目标路径点b以所述预测碰撞位置为中心也呈顺时针方向分布。
64.通过每个所述自移动设备的目标避障点与对应的目标路径点均以所述预测碰撞位置为中心呈顺时针方向分布，或者均以所述预测碰撞位置为中心呈逆时针方向分布，可以使得自移动设备在沿着更新后的规划路径运行时，在与所述预测碰撞位置一定距离时，以相同的方向绕行所述预测碰撞位置，以防止发生碰撞。
65.在另一些实施方式中，可以确定所述预测碰撞位置对应的多个自移动设备中的部分自移动设备的目标避障点，以及根据所述部分自移动设备的目标避障点更新所述部分自移动设备的规划路径。所述预测碰撞位置对应的多个自移动设备中的其他自移动设备的规划路径可以不更新。请参阅图5，预测碰撞位置对应的自移动设备包括自移动设备m1和自移动设备m2，可以确定圆周与自移动设备m2的规划路径的第一个交点b，同时也是自移动设备m2的目标路径点b。确定与目标路径点b相邻的可选避障点a，同时也是所述自移动设备的目标避障点a。自移动设备m2的更新后的规划路径可以表示为f-b-a-d-g。自移动设备m1的规
划路径可以保持为e-a-c-h，举例而言，自移动设备m1到达位置a时，自移动设备m2到达位置b；之后自移动设备m1由位置a向位置c移动，自移动设备m2由位置b向位置a移动，以及自移动设备m2到达位置a时，自移动设备m1位于位置a和位置c之间。之后自移动设备m2到达位置c时，自移动设备m2位于位置a和位置d之间，可以防止自移动设备m1、自移动设备m2发生碰撞。期间，自移动设备m2仅需在位置b、位置a、位置d调整运动状态,能够降低自移动设备调整运动状态的频次，提高作业效率。
66.在一些实施方式中，所述规划路径上的原始路径点包括起点、若干中间点以及终点。如图6所示，规划路径上的原始路径点包括起点p0、中间点p1、中间点p2、以及终点p0'。
67.需要说明的是，所述若干中间点可以包括规划路径上除起点和终点外的预设位置，或者可以包括规划路径上除起点和终点外的任意一个或多个位置，例如可以根据所述圆周与所述规划路径的交点确定所述中间点。请参阅图5，所述若干中间点可以包括所述圆周与自移动设备的规划路径的交点，如交点a和交点c。
68.在根据各所述自移动设备的目标避障点更新对应所述自移动设备的规划路径时，根据所述规划路径上的原始路径点以及所述自移动设备的目标避障点进行路径规划，得到更新后的规划路径。
69.示例性的，所述根据各所述自移动设备的目标避障点更新对应所述自移动设备的规划路径，包括：根据所述起点，所述目标避障点以及位于所述起点和所述目标避障点之间的中间点向所述终点延伸的方向，获取第一路径；根据所述终点，所述目标避障点以及位于所述起点和所述目标避障点之间的中间点向所述起点延伸的方向，获取第二路径；当所述第一路径与所述第二路径延伸到同一中间点或所述目标避障点时，对所述第一路径和所述第二路径拼接，得到更新后的规划路径。通过从所述起点开始规划第一路径，以及从所述终点开始规划第二路径，可以实现双向路径规划，以提高规划效率；以及便于在路径规划过程中加入目标避障点的约束，以使更新后的路径可以在所述目标避障点绕行。更稳定有效地减少了路径规划的时间，快速规划出更优的路径。
70.举例而言，如图6所示，根据所述起点p0，所述目标避障点d以及位于所述起点p0和所述目标避障点d之间的中间点p1、中间点p2向所述终点p0’延伸的方向，获取第一路径。可以先确定中间点p1、中间点p2中距离起点p0最近的中间点，如中间点p1，则先规划起点p0与中间点p1之间的子路径作为所述第一路径的子路径。之后确定距离中间点p1(可以称为当前起始点)最近的中间点，如中间点p2，以及规划中间点p1与中间点p2之间的子路径，将中间点p1与中间点p2之间的子路径更新到所述第一路径，例如与起点p0与中间点p1之间的子路径拼接。当位于所述起点p0和所述目标避障点d之间的中间点均已规划路径时，可以规划其中最后一个中间点，如中间点p1至目标避障点d之间的子路径，以及将中间点p1至目标避障点d之间的子路径更新到所述第一路径。根据所述终点，所述目标避障点以及位于所述起点和所述目标避障点之间的中间点向所述起点延伸的方向，获取第二路径的步骤可以参照获取第一路径的步骤，在此不做赘述。当所述第一路径与所述第二路径延伸到同一中间点或所述目标避障点时，对所述第一路径和所述第二路径拼接。
71.通过根据距离最近原则选取中间点和规划当前点与距离最近的中间点之间的路径，即优先对距离最短的路径进行规划，可以在原始路径点包括多个中间点时也能得到较优的路径。
72.可选的，当所述第一路径与所述第二路径延伸到同一中间点或所述目标避障点时，即正向路径规划的当前起始点与反向路径规划的当前起始点相同时，进一步判断是否存在中间点没规划完成，若存在，则将第一路径中当前起始点(如目标避障点d)之前规划的一段子路径(如中间点p1至目标避障点d之间的子路径)删除，即回退当前起始点(如将中间点p1作为当前起始点)，以及重新规划剩下目标点，例如将与当前起始点p1之间距离第二短的目标点或目标避障点d作为当前起始点p1的下一目标点；可以将全部的中间点均规划到更新后的规划路径中，防止遗漏中间点影响自移动设备完成工作任务。
73.在另一些实施方式中，所述规划路径上的原始路径点包括起点和若干中间点。如图7所示，规划路径上的原始路径点包括起点p0、中间点p1、中间点p2、以及中间点p3。
74.示例性的，所述根据各所述自移动设备的目标避障点更新对应所述自移动设备的规划路径，包括：将所述目标避障点更新为所述自移动设备的规划路径中的中间点；在各中间点中，确定距离所述起点最近的点为第一规划路径点；在剩余中间点中，确定距离上一规划路径点最近的点为下一规划路径点，直至所有中心点都被确定为规划路径点；确定各规划路径点之间的子路径；依次对所述子路径拼接，得到更新后的规划路径。
75.请参阅图7，将目标避障点d更新为所述自移动设备的规划路径中的中间点d，在中间点p1、中间点p2、中间点p3、中间点d中，确定距离起点p0最近的点，如中间点p1为第一规划路径点，确定起点p0和中间点p1之间的子路径。在剩余中间点p2、中间点p3、中间点d中，确定距离上一规划路径点中间点p1最近的点如中间点p2为下一规划路径点，确定中间点p1和中间点p2之间的子路径。在剩余中间点p3、中间点d中，确定距离上一规划路径点中间点p2最近的点如中间点d为下一规划路径点，确定中间点p2和中间点d之间的子路径。这笔后确定中间点d与中间点p3之间的子路径；通过依次拼接起点p0、中间点p1、中间点p2、中间点d、中间点p3之间的子路径拼接，得到更新后的规划路径。通过根据距离最近原则选取规划路径点，规划出一条经过多个中间点的路径，可以实现多目标的全局路径搜索，通过优先对距离最短的路径进行规划，可以得到较优的路径。
76.在一些实施方式中，所述方法还包括：在所述规划路径上的原始路径点和所述目标避障点中确定第一目标点和第二目标点；根据预设的曼哈顿(manhattan)距离函数和预设的欧式(euclidean)距离函数，确定更新后的所述第一目标点至所述第二目标点之间的规划路径。通过在规划第一目标点至所述第二目标点之间的规划路径时，基于曼哈顿距离和欧式距离对规划路径的搜寻方向进行决策，可以规划出更优的全局路径，例如规划得到的规划路径可以兼顾了可通行区域和障碍物区域。更稳定有效地减少了路径规划的时间，快速规划出更优的路径。
77.示例性的，请参阅图8，将所述第一目标点的位置确定为当前规划位置。基于曼哈顿距离函数，根据栅格地图中当前规划位置相邻的第一栅格到所述第二目标点的曼哈顿距离，确定所述第一栅格到所述第二目标点的第一估价值；所述栅格地图为所述规划路径对应的场地的栅格地图；根据所述第一栅格到所述第二目标点的第一估价值，以及所述第一目标点至所述第一栅格的实际代价值，确定所述第一目标点经所述第一栅格到所述第二目标点的第二估价值。基于欧式距离函数，根据所述栅格地图中所述当前规划位置相邻的第二栅格到所述第二目标点的欧式距离，确定所述第二栅格到所述第二目标点的第三估价值；根据所述第二栅格到所述第二目标点的第三估价值，以及所述第一目标点至所述第二
栅格的实际代价值，确定所述第一目标点经所述第二栅格到所述第二目标点的第四估价值。根据所述第一栅格对应的第二估价值和/或所述第二栅格对应的第四估价值，将最小的第二估价值对应的第一栅格或最小的第四估价值对应的第二栅格确定为所述当前规划位置的下一规划位置。连接所述当前规划位置和所述下一规划位置，以及将所述下一规划位置确定为当前规划位置。
78.可选的，所述根据所述第一栅格对应的第二估价值和/或所述第二栅格对应的第四估价值，将最小的第二估价值对应的第一栅格或最小的第四估价值对应的第二栅格确定为所述当前规划位置的下一规划位置，包括：若所述当前规划位置相邻的第一栅格存在障碍物，则将最小的第二估价值对应的第一栅格确定为所述当前规划位置的下一规划位置；若所述当前规划位置相邻的第一栅格均不存在障碍物，则将最小的第四估价值对应的第二栅格确定为所述当前规划位置的下一规划位置。
79.请参阅图8，采用基于栅格地图的八邻域搜索方式，即从当前规划位置同时向周围的沿上、下、左、右、左上、右上、左下、右下八个栅格搜索方向；结合euclidean距离和manhattan距离,在不同的搜索方向中使用不同的但保持一定比例的距离加权值,通过两种方式的改进,设计出的智能启发函数能很好的兼顾可通行区域和障碍物区域,到最适合通行的路径。
80.改进的距离定义智能启发函数的具体形式如式(1)和式(2)所示，式(3)和式(4)是将改进的距离定义智能启发函数融入a*算法估价函数的具体形式：
81.h
km
(n)＝nk
×
(|n
x-g
x
|+|n
y-gy|)
ꢀꢀꢀꢀ
式(1)
[0082][0083]fkm
(n)＝g(n)+h
km
(n)
ꢀꢀꢀ
式(3)
[0084]fke
(n)＝g(n)+h
ke
(n)
ꢀꢀꢀ
式(4)
[0085]
其中，k表示距离加权值，h
km
(n)是采用曼哈顿距离加权方式计算从节点(栅格地图中每一个栅格表示一个节点)n到目标位置的启发函数估价值；h
ke
(n)是采用采用欧式距离加权方式计算从节点n到目标位置的启发函数估价值；f
km
(n)是采用曼哈顿距离加权方式计算从起始位置到目标位置的估价值；f
ke
(n)是采用欧式距离加权方式计算从起始位置到目标位置的估价值；g(n)是从起始位置到节点n的实际代价值，n
x
是节点n的横坐标，ny是节点n的纵坐标，g
x
是目标点的横坐标，gy是目标点的纵坐标。
[0086]
其中，式(1)表示改进了搜索方向上所采用的距离方式，在当前栅格的上、下、左、右四个方向上，通过采用manhattan距离进行定义；在当前栅格的左上、右上、左下、右下四个方向上，通过采用欧几里得距离进行定义；式(2)改进之处是在euclidean距离和manhattan距离定义的基础上，使euclidean距离定义的启发函数和manhattan距离定义的启发函数保持一定比例。
[0087]
式(3)和(4)是将式(1)和(2)修改的启发函数代入a*算法总的估价函数中，是改进a*算法估价函数的具体实现形式，即式(3)是在当前栅格的上、下、左、右四个方向上进行使用，式(4)是在当前栅格的左上、右上、左下、右下四个方向上进行使用；因此改进后的距离定义启发函数更为智能，提高了搜索的效率，缩短了路径规划时间。
[0088]
在一些实施方式中，所述方法还包括：优化所述规划路径中的转折曲线为圆弧，以
最大限度地平滑更新的所述规划路径。举例而言，路径转折线段优化如图9所示。
[0089]
路径转折线段优化策略是依据数学上的边弧优化原理，对之前融入智能启发函数后规划生成的初始路径进行边弧优化。关键步骤是计算出路径转折处节点间的转折角度α，并通过式(5)求出其余弦值，式(5)如下：
[0090][0091]
其中，(x1,y1),(x2,y2),(x3,y3)为初始路径三个相邻节点的坐标。由于割草机等自移动设备在栅格地图中转动的角度只存在0
°
、45
°
和90
°
这三种情况，因此只需根据节点间的夹角和方向，便可以采用边弧优化理论计算出所有转弯情况的半径，圆心和转弯的弧度，具体实现过程如下：
[0092]
(1)当α》0
°
时，自移动设备向左转动，并根据α值的大小，控制转动的角度，例如左转45
°
或左转90
°
；
[0093]
(2)当α＝0
°
时，自移动设备行驶方向保持不变；
[0094]
(3)当α《0
°
时，自移动设备向右转动，并根据值的大小，控制转动的角度，例如右转45
°
或右转90
°
。
[0095]
在一些实施方式中，平滑规划生成的路径依然无法保证不与障碍物发生碰撞,对此,进一步优化算法的路径生成策略,使改进后的算法规划生成的路径与障碍物保持最少半个栅格的距离，即本技术实施例还提供了安全避障的路径生成策略，以保证自移动设备在运行的过程中不碰到障碍物,安全地到达目标位置,提升自移动设备的避障性能。
[0096]
示例性的，安全避障路径生成策略主要是对子节点的估价值进行调整。实现方法如下：
[0097]
(1)若当前的节点与相邻节点的方向和当前节点与其父节点方向相同,则减小式(3)和式(4)中g(n)的估价值，若方向相反，则增加g(n)的估价值。
[0098]
(2)初始路径转折点间的转弯程度与g(n)的估价值呈正比例相关，转弯程度越大，g(n)的估价值也越大。
[0099]
(3)扩展子节点的过程中，优先扩展垂直水平方向上的节点，随后根据垂直水平方向上是否存在障碍物，如果存在，则不扩展与障碍物相邻的对角线节点；如果不存在，则扩展对角线方向节点。
[0100]
本技术实施例提供的多自移动设备的路径规划方法，包括：获取每个自移动设备的规划路径以及运动数据；根据每个所述自移动设备的规划路径以及运动数据，获取各所述自移动设备之间的预测碰撞位置；根据所述预测碰撞位置确定多个围绕所述预测碰撞位置的可选避障点；根据各所述可选避障点与各所述自移动设备的规划路径的位置关系，确定各所述自移动设备的目标避障点；各所述自移动设备的目标避障点为不同位置的点；根据各所述自移动设备的目标避障点更新对应所述自移动设备的规划路径。通过提前预测碰撞位置，根据碰撞位置给不同的自移动设备设置不同的目标避障点，以及根据目标避障点更新各自移动设备的路径，根据不同的目标避障点规划路径可以防止得到的路径之间产生交叉，因此在自移动设备在沿着根据该目标避障点规划的路径运行时，碰撞的几率大大降低；而且根据目标避障点更新路径，可以使自移动设备以较低的频次调整运动状态即可避撞，提高作业效率。
[0101]
在一些实施方式中，本技术实施例针对a*算法路径规划过程中局限于规划单一目标点，耗时较长,路径不够平滑,避障性能不足等问题，提出一种兼顾多目标和避障最优的改进a*算法，兼顾安全性、实时性、平滑性等问题，对基于八邻域(如图8所示)搜索方向的a*算法进行了以下至少一方面的改进及优化：
[0102]
a.结合euclidean距离和manhattan距离,在不同的搜索方向中使用不同的但保持一定比例的距离加权值,设计出一种距离定义启发函数，使得改进a*算法能够在搜寻路径的过程中,兼顾了可通行区域和障碍物区域，规划出最优的初始全局路径；
[0103]
b.优化所述规划路径中的转折曲线为圆弧,以最大限度地平滑更新的所述规划路径；
[0104]
c.优化算法的路径生成策略,使改进后的算法规划生成的路径与障碍物保持最少半个栅格的距离，提升算法的避障性能；
[0105]
d.根据距离最近原则在多个中间点中选取中间点和规划当前点与距离最近的中间点之间的路径，实现一种基于多目标的全局路径搜索方法；
[0106]
e.通过从所述起点开始规划第一路径，以及从所述终点开始规划第二路径，可以实现双向路径规划，以提高规划效率；
[0107]
f.通过提前预测碰撞位置，根据碰撞位置给不同的自移动设备设置不同的目标避障点，以及根据目标避障点更新各自移动设备的路径，实现基于避障最优的多自移动设备的全局路径规划策略。
[0108]
请结合上述实施例参阅图10，图10是本技术实施例提供的路径规划装置600的示意性框图。该路径规划装置600包括一个或多个处理器601，一个或多个处理器601单独地或共同地工作，用于实现所述多自移动设备的路径规划方法步骤。
[0109]
示例性的，路径规划装置600还可以包括存储器602。
[0110]
示例性的，处理器601和存储器602通过总线603连接，该总线603比如为i2c(inter-integrated circuit)总线。
[0111]
具体地，处理器601可以是微控制单元(micro-controller unit，mcu)、中央处理单元(central processing unit，cpu)或数字信号处理器(digital signal processor，dsp)等。
[0112]
具体地，存储器602可以是flash芯片、只读存储器(rom，read-only memory)磁盘、光盘、u盘或移动硬盘等。
[0113]
其中，所述处理器601用于运行存储在存储器602中的计算机程序，并在执行所述计算机程序时实现前述多自移动设备的路径规划方法的步骤。
[0114]
示例性的，所述处理器601用于运行存储在存储器602中的计算机程序，并在执行所述计算机程序时实现如下步骤：
[0115]
获取每个自移动设备的规划路径以及运动数据；
[0116]
根据每个所述自移动设备的规划路径以及运动数据，获取各所述自移动设备之间的预测碰撞位置；
[0117]
根据所述预测碰撞位置确定多个围绕所述预测碰撞位置的可选避障点；
[0118]
根据各所述可选避障点与各所述自移动设备的规划路径的位置关系，确定各所述自移动设备的目标避障点；各所述自移动设备的目标避障点为不同位置的点；
[0119]
根据各所述自移动设备的目标避障点更新对应所述自移动设备的规划路径。
[0120]
本技术实施例提供的路径规划装置的具体原理和实现方式均与前述实施例的多自移动设备的路径规划方法类似，此处不再赘述。
[0121]
请结合上述实施例参阅图11，图11是本技术实施例提供的自移动设备700的示意性框图。该自移动设备700包括一个或多个处理器701，一个或多个处理器701单独地或共同地工作，用于实现所述多自移动设备的路径规划方法步骤。
[0122]
自移动设备700例如包括机器人，如割草机器人、扫地机器人、排雷机器人、巡航机器人等，本实施例对此不做特别限定。
[0123]
示例性的，自移动设备700还可以包括存储器702。
[0124]
示例性的，处理器701和存储器702通过总线703连接，该总线703比如为i2c(inter-integrated circuit)总线。
[0125]
具体地，处理器701可以是微控制单元(micro-controller unit，mcu)、中央处理单元(central processing unit，cpu)或数字信号处理器(digital signal processor，dsp)等。
[0126]
具体地，存储器702可以是flash芯片、只读存储器(rom，read-only memory)磁盘、光盘、u盘或移动硬盘等。
[0127]
其中，所述处理器701用于运行存储在存储器702中的计算机程序，并在执行所述计算机程序时实现前述多自移动设备的路径规划方法的步骤。
[0128]
示例性的，所述处理器701用于运行存储在存储器702中的计算机程序，并在执行所述计算机程序时实现如下步骤：
[0129]
获取每个自移动设备的规划路径以及运动数据；
[0130]
根据每个所述自移动设备的规划路径以及运动数据，获取各所述自移动设备之间的预测碰撞位置；
[0131]
根据所述预测碰撞位置确定多个围绕所述预测碰撞位置的可选避障点；
[0132]
根据各所述可选避障点与各所述自移动设备的规划路径的位置关系，确定各所述自移动设备的目标避障点；各所述自移动设备的目标避障点为不同位置的点；
[0133]
根据各所述自移动设备的目标避障点更新对应所述自移动设备的规划路径。
[0134]
本技术实施例提供的自移动设备的具体原理和实现方式均与前述实施例的多自移动设备的路径规划方法类似，此处不再赘述。
[0135]
本技术实施例还提供一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，所述计算机程序中包括程序指令，所述计算机程序被处理器执行时使所述处理器实现上述实施例提供的多自移动设备的路径规划方法的步骤。
[0136]
其中，所述计算机可读存储介质可以是前述任一实施例所述的路径规划装置或自移动设备的内部存储单元，例如所述自移动设备的硬盘或内存。所述计算机可读存储介质也可以是所述路径规划装置或自移动设备的外部存储设备，例如所述路径规划装置上配备的插接式硬盘，智能存储卡(smart media card，smc)，安全数字(secure digital，sd)卡，闪存卡(flash card)等。
[0137]
应当理解，在此本技术中所使用的术语仅仅是出于描述特定实施例的目的而并不意在限制本技术。
[0138]
还应当理解，在本技术和所附权利要求书中使用的术语“和/或”是指相关联列出的项中的一个或多个的任何组合以及所有可能组合，并且包括这些组合。
[0139]
以上所述，仅为本技术的具体实施方式，但本技术的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本技术揭露的技术范围内，可轻易想到各种等效的修改或替换，这些修改或替换都应涵盖在本技术的保护范围之内。因此，本技术的保护范围应以权利要求的保护范围为准。

技术特征：

1.一种多自移动设备的路径规划方法，其特征在于，包括：获取每个自移动设备的规划路径以及运动数据；根据每个所述自移动设备的规划路径以及运动数据，获取各所述自移动设备之间的预测碰撞位置；根据所述预测碰撞位置确定多个围绕所述预测碰撞位置的可选避障点；根据各所述可选避障点、所述预测碰撞位置与各所述自移动设备的规划路径的位置关系，确定各所述自移动设备的目标避障点；各所述自移动设备的目标避障点为不同位置的点；根据各所述自移动设备的目标避障点更新对应所述自移动设备的规划路径。2.根据权利要求1所述的路径规划方法，其特征在于，所述根据所述预测碰撞位置确定多个围绕所述预测碰撞位置设置的可选避障点中：各所述可选避障点与所述预测碰撞位置的距离相同；且各所述可选避障点位于各自移动设备的规划路径上。3.根据权利要求1所述的路径规划方法，其特征在于，所述根据所述预测碰撞位置确定多个围绕所述预测碰撞位置设置的可选避障点，包括：以所述预测碰撞位置为圆心，以预设距离为半径确定所述可选避障点所在的圆周；所述预设距离与所述自移动设备的作业区域大小成正相关关系；将所述圆周上与每个所述自移动设备的规划路径的交点确定为可选避障点。4.根据权利要求3所述的路径规划方法，其特征在于，所述根据各所述可选避障点、所述预测碰撞位置与各所述自移动设备的规划路径的位置关系，确定各所述自移动设备的目标避障点，包括：确定每个所述自移动设备的规划路径与所述圆周的交点，并将第一个经过的交点作为目标路径点；在各所述可选避障点中，确定与每个所述自移动设备的目标路径点相邻的可选避障点为所述自移动设备的目标避障点，且每个所述自移动设备的目标避障点与对应的目标路径点均以所述预测碰撞位置为中心呈顺时针方向分布，或者均以所述预测碰撞位置为中心呈逆时针方向分布。5.根据权利要求1所述的路径规划方法，其特征在于，所述规划路径上的原始路径点包括起点、若干中间点以及终点；所述根据各所述自移动设备的目标避障点更新对应所述自移动设备的规划路径，包括：根据所述起点，所述目标避障点以及位于所述起点和所述目标避障点之间的中间点向所述终点延伸的方向，获取第一路径；根据所述终点，所述目标避障点以及位于所述起点和所述目标避障点之间的中间点向所述起点延伸的方向，获取第二路径；当所述第一路径与所述第二路径延伸到同一中间点或所述目标避障点时，对所述第一路径和所述第二路径拼接，得到更新后的规划路径。6.根据权利要求1所述的路径规划方法，其特征在于，所述规划路径上的原始路径点包括起点和若干中间点；
所述根据各所述自移动设备的目标避障点更新对应所述自移动设备的规划路径，包括：将所述目标避障点更新为所述自移动设备的规划路径中的中间点；在各中间点中，确定距离所述起点最近的点为第一规划路径点；在剩余中间点中，确定距离上一规划路径点最近的点为下一规划路径点，直至所有中心点都被确定为规划路径点；确定各规划路径点之间的子路径；依次对所述子路径拼接，得到更新后的规划路径。7.根据权利要求1所述的路径规划方法，其特征在于，所述方法还包括：在所述规划路径上的原始路径点和所述目标避障点中确定第一目标点和第二目标点；根据预设的曼哈顿距离函数和预设的欧式距离函数，确定更新后的所述第一目标点至所述第二目标点之间的规划路径。8.一种路径规划装置，其特征在于，包括：一个或多个处理器，一个或多个处理器单独地或共同地工作，用于实现如权利要求1至7中任一项所述的多自移动设备的路径规划方法的步骤。9.一种自移动设备，其特征在于，包括：一个或多个处理器，一个或多个处理器单独地或共同地工作，用于实现如权利要求1至7中任一项所述的多自移动设备的路径规划方法的步骤。10.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质存储有计算机程序，所述计算机程序被处理器执行时使所述处理器实现：如权利要求1-7中任一项所述的多自移动设备的路径规划方法的步骤。

技术总结

本申请实施例提供了一种多自移动设备的路径规划方法、装置、自移动设备，方法包括：根据每个自移动设备的规划路径以及运动数据，获取各自移动设备之间的预测碰撞位置；根据预测碰撞位置确定多个可选避障点；根据各可选避障点、预测碰撞位置与各自移动设备的规划路径的位置关系,确定各自移动设备的目标避障点；根据各自移动设备的目标避障点更新对应自移动设备的规划路径。通过提前预测碰撞位置，根据碰撞位置给不同的自移动设备设置不同的目标避障点，以及根据目标避障点更新各自移动设备的路径，可以防止路径之间产生交叉，降低自移动设备运行时发生碰撞的几率，同时降低自移动设备调整运动状态的频次，提高作业效率。提高作业效率。提高作业效率。