一种基于双向爬虫的移动机器人路径规划方法

1.本发明属于移动机器人导航技术领域，具体涉及一种基于双向爬虫的移动机器人路径规划方法。


背景技术：

2.移动机器人广泛应用于人们工作和生活的方方面面，物流机器人、安防机器人、政企服务机器人、巡检机器人、教学平台机器人等等均需移动机器人技术作为支撑，在实际应用中，可用于家庭卫生的清洁、老年人轮椅的运动实现、火灾现场的救援、工厂物料或快递的搬运等等，移动机器人已成为当前的研究热点。
3.在移动机器人的研究领域中，路径规划是一个重要的研究分支。其目的是移动机器人在有障碍物的工作环境中，依据行走路径最短、所用代价最小等评价标准，寻找一条从包括位置和姿态的起始状态到达目标状态的最优无障碍路径，是其完成自主导航与避障任务的基础。路径长度、实时性以及工作代价值等是评估路径规划算法的性能指标。爬虫系列方法具有明显的实时计算优势，也是局部路径规划中常见的算法，具体包括bug1、bug2、dist-bug和rev-bug等。虽然爬虫系列方法在计算实时性能上有非常突出的表现，但由于其完全应激的基本特性，得到的路径长度较长。


技术实现要素：

4.本发明的目的是为了克服现有技术存在的缺点和不足，而提供一种基于双向爬虫的移动机器人路径规划方法。
5.本发明所采取的技术方案如下：一种基于双向爬虫的移动机器人路径规划方法，包括以下步骤：
6.(1)求得关键点：构建机器人移动地图，将障碍物简化为无凹形结构的多边形结构，设定a为起点，b为终点，采用基于爬虫的路径规划方法从移动机器人起点和终点出发，获得两条移动路径，并对两条路径中的所经过的拐点进行提取；将上述拐点与障碍物的边角点进行综合，获得关键点，即既是路径拐点又是障碍物边角点的点称为关键点；
7.(2)关键点编号：依据从起点到终点路径上关键点连接的顺序对关键点进行编号，并将同一障碍物上关键点标记为同号，保证移动机器人在规划路径上只经过障碍物一次；
8.(3)移动路径一关键点选择：以起点为起始点，按照终点-起点-关键点三点进行连线，对该角度进行对比，选取令角度最小的关键点作为选中关键点，并将该选中关键点作为新的起点，对比下一编号的关键点，以此类推，获得路径上所有的关键点，连接关键点得到移动路径一；
9.(4)路径二关键点选择：以终点为起始点，按照起点-终点-关键点三点进行连线，对该角度进行对比，选取令角度最小的关键点作为选中关键点，并将该选中关键点作为新的起点，对比下一编号的关键点，以此类推，获得路径上所有的关键点，连接关键点得到移动路径二；
10.(5)路径对比确定：采用步骤(3)选择的对从起点到终点的移动路径一和从终点到起点的移动路径二分别进行求解，并对两条路径进行比较，得到移动长度短的路径作为最终移动机器人移动路径；
11.其中，步骤(3)和步骤(4)中，若是同一编号关键点只有一个，且新的起点与下一编号的关键点的连线上不存在障碍物，则将该关键点与下一编号关键点进行比较选取；若是同一编号关键点只有一个，且新的起点与下一障碍物的所有关键点的连线上均存在障碍物，则该关键点无需与下一编号关键点进行比较选取，直接选取该关键点；若是同一编号关键点有两个，则对这两个关键点进行比较选取。
12.步骤(3)和步骤(4)中，角度对比的计算过程以步骤(3)为例具体如下：
13.假设起点a坐标为(0，0)，终点b坐标为(x1，y1)，关键点1坐标为(x2，y2)，关键点2坐标为(x3，y3)，则可通过如下公式对关键点进行选择：
14.k1＝y1/x1
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(1)
15.k2＝y2
′
/x2
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(2)
16.k3＝y3/x3
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(3)
17.tan(α1)＝|k2-k1|/|1+k1
×
k2|
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(4)
18.tan(α2)＝|k3-k1|/|1+k1
×
k3|
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(5)
19.以起点a作为坐标原点，终点b与a连线的斜率为k1，关键点1与a连线的斜率为k2，关键点2与a连线的斜率为k3，α1为斜率为k1和k2两线的夹角，α2为斜率为k1和k3两线的夹角，在夹角小于90
°
时公式(4)和(5)成立，若是夹角大于90
°
，则代表移动方向与目标方向相反，可首先排除，tan函数在角度为0-90
°
的范围内单调递增，因此只需比较公式(4)和(5)的值就可以求得α1和α2两个角度的大小。
20.本发明的有益效果如下：本发明综合爬虫算法的优势和劣势，采用双爬虫模式，在降低一定计算优势的基础上，获得较优的移动路径，为移动机器人路径规划方法提供一种参考。
附图说明
21.为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，根据这些附图获得其他的附图仍属于本发明的范畴。
22.图1为本发明的流程示意图；
23.图2为实施例1构建的移动地图；
24.图3为实施例1基于现有技术中的爬虫方法a到b的移动路径；
25.图4为实施例1基于现有技术中的爬虫方法b到a移动路径；
26.图5为实施例1中的关键点位置图；
27.图6为实施例1中移动路径一关键点1选择示意图；
28.图7为实施例1中移动路径一关键点2选择示意图；
29.图8为实施例1中确定的移动路径一；
30.图9为实施例1中确定的移动路径二。
具体实施方式
31.为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明作进一步地详细描述。
32.实施例1：
33.构建机器人移动地图，以图1所示的地图为例，其中a点代表移动机器人移动起点，b点代表终点，将障碍物简化为无凹形结构的多边形结构，图中蓝色方块代表障碍物，红色虚线代表最优移动路径。
34.首先采用传统爬虫算法进行移动机器人路径规划，从a点到b点的移动路径如图2所示，从b点到a点的移动路径如图3所示，图中带箭头实线代表移动机器人移动路径，虚线代表从每一个拐点处到终点的辅助线。
35.然后依据本发明所提供的基于双向爬虫的移动机器人路径规划方法进行规划路径，具体过程如下所示：
36.(1)求得关键点：采用基于爬虫的路径规划方法从移动机器人起点和终点出发，获得两条移动路径，并对两条路径中的所经过的拐点进行提取；将上述拐点与障碍物的边角点进行综合，获得关键点，即既是路径拐点又是障碍物边角点的点称为关键点；
37.(2)关键点编号：依据从起点到终点路径上关键点连接的顺序对关键点进行编号，并将同一障碍物上关键点标记为同号，保证移动机器人在规划路径上只经过障碍物一次，如图4所示；
38.(3)移动路径一关键点选择：以起点为起始点，按照终点-起点-关键点三点进行连线，对该角度进行对比，选取令角度最小的关键点作为选中关键点，并将该选中关键点作为新的起点，对比下一编号的关键点，以此类推，获得路径上所有的关键点，连接关键点得到移动路径一；
39.假设起点a坐标为(0，0)，终点b坐标为(x1，y1)，关键点1坐标为(x2，y2)，关键点2坐标为(x3，y3)，则可通过如下公式对关键点进行选择：
40.k1＝y1/x1
ꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(1)
41.k2＝y2/x2
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(2)
42.k3＝y3/x3
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(3)
43.tan(α1)＝|k2-k1|/|1+k1
×
k2|
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(4)
44.tan(α2)＝|k3-k1|/|1+k1
×
k3|
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(5)
45.以起点a作为坐标原点，终点b与a连线的斜率为k1，关键点1与a连线的斜率为k2，关键点2与a连线的斜率为k3，α1为斜率为k1和k2两线的夹角，α2为斜率为k1和k3两线的夹角，在夹角小于90
°
时公式(4)和(5)成立，若是夹角大于90
°
，则代表移动方向与目标方向相反，可首先排除，tan函数在角度为0-90
°
的范围内单调递增，因此只需比较公式(4)和(5)的值就可以求得α1和α2两个角度的大小；
46.如5所示，因1号关键点个数为1，因此需与2号关键点进行比较，1号关键点角度代表1号关键点到a点到b点的角度，2号关键点角度代表2号关键点到a点到b点的角度，通过上述计算公式可得，1号关键点角度更小，因此，选取1号关键点作为移动路径关键点；接着以1号关键点作为起点，将两个2号关键点做比较，如图7所示，2号上关键点角度代表2号上关键点到1号关键点到b点的角度，2号下关键点角度代表2号下关键点到1号关键点到b点的角
度，同样采用上述步骤4中公式进行对比可得，2号上关键点具有更小的角度，因此选取2号上关键点作为移动路径关键点；以此类推，最终关键点为1号、2号上、3号下、4号下，移动路线如图7中带箭头实线所示。
47.(4)路径二关键点选择：以终点为起始点，按照起点-终点-关键点三点进行连线，对该角度进行对比，选取令角度最小的关键点作为选中关键点，并将该选中关键点作为新的起点，对比下一编号的关键点，以此类推，获得路径上所有的关键点，连接关键点得到移动路径二；采用步骤(3)中相同的思路，通过各个关键点与a点角度的比较，最终选取的关键点为4号下、3号下、2号下，移动路线图如图8中带箭头实线所示。
48.(5)路径对比确定：采用步骤(3)选择的对从起点到终点的移动路径一和从终点到起点的移动路径二分别进行求解，并对两条路径进行比较，得到移动长度短的路径作为最终移动机器人移动路径；
49.在本实施例中，从a点到b点的移动路径距离为25.5，从b点到a点的移动路径距离为25.4，因此，最终移动机器人的移动路径如图8所示。
50.该地图从a点到b点的最优路径为a到2号下到3号下到b，由于关键点3号下、4号下与b点接近处于一条直线，因此与最优路径相差仅为0.08，本发明所提出的方法取得了不错的效果。
51.本领域普通技术人员可以理解实现上述实施例方法中的全部或部分步骤是可以通过程序来指令相关的硬件来完成，所述的程序可以存储于一计算机可读取存储介质中，所述的存储介质，如rom/ram、磁盘、光盘等。
52.以上所揭露的仅为本发明较佳实施例而已，当然不能以此来限定本发明之权利范围，因此依本发明权利要求所作的等同变化，仍属本发明所涵盖的范围。

技术特征：
1.一种基于双向爬虫的移动机器人路径规划方法，其特征在于包括以下步骤：(1)求得关键点：构建机器人移动地图，将障碍物简化为无凹形结构的多边形结构，设定a为起点，b为终点，采用基于爬虫的路径规划方法从移动机器人起点和终点出发，获得两条移动路径，并对两条路径中的所经过的拐点进行提取；将上述拐点与障碍物的边角点进行综合，获得关键点，即既是路径拐点又是障碍物边角点的点称为关键点；(2)关键点编号：依据从起点到终点路径上关键点连接的顺序对关键点进行编号，并将同一障碍物上关键点标记为同号，保证移动机器人在规划路径上只经过障碍物一次；(3)移动路径一关键点选择：以起点为起始点，按照终点-起点-关键点三点进行连线，对该角度进行对比，选取令角度最小的关键点作为选中关键点，并将该选中关键点作为新的起点，对比下一编号的关键点，以此类推，获得路径上所有的关键点，连接关键点得到移动路径一；(4)路径二关键点选择：以终点为起始点，按照起点-终点-关键点三点进行连线，对该角度进行对比，选取令角度最小的关键点作为选中关键点，并将该选中关键点作为新的起点，对比下一编号的关键点，以此类推，获得路径上所有的关键点，连接关键点得到移动路径二；(5)路径对比确定：采用步骤(3)选择的对从起点到终点的移动路径一和从终点到起点的移动路径二分别进行求解，并对两条路径进行比较，得到移动长度短的路径作为最终移动机器人移动路径；其中，步骤(3)和步骤(4)中，若是同一编号关键点只有一个，且新的起点与下一编号的关键点的连线上不存在障碍物，则将该关键点与下一编号关键点进行比较选取；若是同一编号关键点只有一个，且新的起点与下一障碍物的所有关键点的连线上均存在障碍物，则该关键点无需与下一编号关键点进行比较选取，直接选取该关键点；若是同一编号关键点有两个，则对这两个关键点进行比较选取。2.根据权利要求1所述的基于双向爬虫的移动机器人路径规划方法，其特征在于：步骤(3)和步骤(4)中，角度对比的计算过程以步骤(3)为例具体如下：假设起点a坐标为(0，0)，终点b坐标为(x1，y1)，关键点1坐标为(x2，y2)，关键点2坐标为(x3，y3)，则可通过如下公式对关键点进行选择：k1＝y1/x1
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(1)k2＝y2/x2
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(2)k3＝y3/x3
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(3)tan(α1)＝|k2-k1|/|1+k1
×
k2|
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(4)tan(α2)|k3-k1|/|1+k1
×
k3|
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(5)以起点a作为坐标原点，终点b与a连线的斜率为k1，关键点1与a连线的斜率为k2，关键点2与a连线的斜率为k3，α1为斜率为k1和k2两线的夹角，α2为斜率为k1和k3两线的夹角，在夹角小于90
°
时公式(4)和(5)成立，若是夹角大于90
°
，则代表移动方向与目标方向相反，可首先排除，tan函数在角度为0-90
°
的范围内单调递增，因此只需比较公式(4)和(5)的值就可以求得α1和α2两个角度的大小。

技术总结
本发明属于移动机器人研究技术领域，具体涉及一种基于双向爬虫的移动机器人路径规划方法。其基于双向爬虫确定分别以起点为起始点的移动路径一和以终点为起始点的移动路径二，然后通过移动路径一和移动路径二的比较确定最终移动机器人移动路径，其中，移动路径一和移动路径二的确定步骤如下：基于爬虫的路径规划方法确定关键点，然后基于以起始点为角点进行角度对比选择合适的关键点，将起点、确定的关键点、终点依次连线后分别得到移动路径一移动路径二。本发明综合爬虫算法的优势和劣势，采用双爬虫模式，在降低一定计算优势的基础上，获得较优的移动路径，为移动机器人路径规划方法提供一种参考。划方法提供一种参考。划方法提供一种参考。


技术研发人员：孙玉冰 郑钰彤
受保护的技术使用者：温州大学
技术研发日：2021.10.29
技术公布日：2022/1/28