CN106092102A - 一种无人机路径规划方法及装置 - Google Patents

Abstract

本发明提供了一种无人机路径规划方法，属于计算机技术领域，包括：将待规划地图区域转化为栅格地图；通过将所述栅格地图中的障碍物标记为背景点、将非障碍物标记为前景点，得到二值化的栅格地图；基于设定的起点、终点以及生成的栅格地图边界，对所述二值化的栅格地图内由所述前景点构成非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径，解决了现有技术中的路径规划方法不适用于精确规划无人机与障碍物碰撞机率最小路径的问题。通过对非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径，保证了飞行安全。

Description

一种无人机路径规划方法及装置

技术领域

本发明涉及无人机技术领域，尤其涉及一种无人机路径规划方法及装置。

背景技术

目前，无人机路径规划方法一般都集中在最优路径规划方面，例如无人机的飞行距离最短、耗时最少、耗能最少等等。在规划最优路径时，使用的路径规划方法有蚁群算法，神经网络算法，人工视场算法，迪杰斯特拉算法、A*算法等等。上述路径规划方法在计算最优路径时，侧重于无人机飞行路径的长短，而对于路径与障碍物之间的距离没有严格要求，比较适用于空旷的飞行环境。可见，对于障碍物较多、地貌复杂的无人机飞行环境，上述路径规划方法并不适用。

当无人机在燃料或电量充足、时间宽裕的条件下，要求无人机最安全地从起点飞到终点执行任务时，需要一种精确规划无人机与障碍物碰撞机率最小路径的方法。

发明内容

本发明实施例提供一种无人机路径规划方法，解决现有技术中的路径规划方法不适用于精确规划无人机与障碍物碰撞机率最小的路径的问题。

第一方面，本发明实施例提供了一种无人机路径规划方法，包括：

将待规划地图区域转化为栅格地图；

通过将所述栅格地图中的障碍物标记为背景点、将非障碍物标记为前景点，得到二值化的栅格地图；

基于设定的起点、终点以及生成的栅格地图边界，对所述二值化的栅格地图内由所述前景点构成的非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径。

第二方面，本发明实施例还提供了一种无人机路径规划装置，包括：

栅格化模块，用于将待规划地图区域转化为栅格地图；

二值化模块，用于通过将所述栅格化模块得到的栅格地图中的障碍物标记为背景点、将非障碍物标记为前景点，得到二值化的栅格地图；

路径细化模块，用于基于设定的起点、终点以及生成的栅格地图边界，对所述二值化的栅格地图内由所述前景点构成的非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径。

这样，本发明实施例通过将待规划地图区域转化为栅格地图；通过将所述栅格地图中的障碍物标记为背景点、将非障碍物标记为前景点，得到二值化的栅格地图；基于设定的起点、终点以及生成的栅格地图边界，对所述二值化的栅格地图内由所述前景点构成非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径，解决了现有技术中的路径规划方法不适用于精确规划无人机与障碍物之间碰撞机率最小的路径的问题。通过对非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径，作为无人机的飞行路径，保证了无人机飞行的安全性。

附图说明

为了更清楚地说明本发明实施例的技术方案，下面将对本发明实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1是本发明实施例一的无人机路径规划方法流程图；

图2是本发明实施例二的无人机路径规划方法流程图；

图3是本发明实施例二中二值化后的栅格地图示意图；

图4是本发明实施例二中标记了边界和起点、终点的栅格地图示意图；

图5是本发明实施例二中前景点P的八邻域像素点示意图；

图6是本发明实施例二中得到的碰撞机率最小的路径示意图；

图7是本发明实施例二中验证碰撞机率最小的路径结果示意图；

图8是本发明实施例三无人机路径规划装置结构图之一；

图9是本发明实施例三无人机路径规划装置结构图之二。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

实施例一：

如图1所示，本发明实施例公开了一种无人机路径规划方法，包括：步骤100至步骤120。

步骤100，将待规划地图区域转化为栅格地图。

目前用于导航的地图多为矢量图，地图的信息量很大，其中，包括：地理位置信息、地貌信息。矢量图是由一系列坐标及函数绘制的线、面、体，可以无限缩放，清晰度高。本发明实施例中，仅需要了解某一地理位置的地貌信息，不需要对地图进行缩放操作，因此，可以使用栅格地图。并且，基于像素的栅格地图便于进行细化。

具体实施时，可以通过现有的地图软件提供的接口读取电子地图数据、扫描现有地图获取地图数据、直接读取电子版地图数据等方式获取待规划的无人机飞行地图数据。待规划的地图数据可以为交通地图数据，也可以是某些建筑物的内部结构地图。然后确定地图中待规划的地图区域，再采用现有技术中的方法，将所述待规划的地图区域转化为栅格地图。

步骤110，通过将所述栅格地图中的障碍物标记为背景点、将非障碍物标记为前景点，得到二值化的栅格地图。

矢量地图转化为栅格地图之后，地图中各地理位置的地貌信息依然保留，仅仅是地图数据的存储格式不同。通过对栅格地图中各地理位置的空间地貌信息进行判断，可以确定地图中某个位置是无人机飞行时的障碍物，还是非障碍物。因为无人机通常在一个特定的高度飞行，具体实施时，在地图的某个位置，无人机飞行的高度平面有遮挡，例如树木，建筑等，则该位置为障碍物，如果在无人机飞行的高度平面为空旷区域，那么该位置为非障碍物区域。将所述栅格地图中的障碍物标记为背景点、将非障碍物标记为前景点，用不同的像素值表示背景点和前景点，可以得到二值化的栅格地图。

步骤120，基于设定的起点、终点以及生成的栅格地图边界，对所述二值化的栅格地图内由所述前景点构成的非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径。

在二值化后的栅格地图中，所有背景点构成的区域为障碍物区域，所有前景点构成的区域为非障碍物区域。通过对非障碍物区域进行细化或对障碍物区域进行膨胀，可以得到二值化后的栅格地图中的所有安全飞行路径。基于设定的起点、终点以及生成的栅格地图边界对非障碍物区域进行细化或对障碍物区域进行膨胀，可以得到连通起点和终点的无人机与障碍物碰撞机率最小的路径，即安全的飞行路径。

本发明实施例公开的无人机路径规划方法，通过将待规划地图区域转化为栅格地图；通过将所述栅格地图中的障碍物标记为背景点、将非障碍物标记为前景点，得到二值化的栅格地图；基于设定的起点、终点以及生成的栅格地图边界，对所述二值化的栅格地图内由所述前景点构成非障碍物区域进行细化，得到从所述起点到终点碰撞机率最小的所有路径，解决了现有技术中的路径规划方法不适用于精确规划无人机与障碍物碰撞机率最小的路径的问题。通过对非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径作为无人机的可飞行路径，保证了飞行的安全性。

实施例二：

如图2所示，本发明实施例公开了一种无人机路径规划方法，包括：步骤200至步骤260。

步骤200，根据设定的起点和终点，确定地图上的待规划地图区域；

首先，根据设定的路径的起点和终点，在用于规划飞行路径的地图上包括起点和终点、范围略大于起点和终点确定的范围的一块区域，作为待规划地图区域。例如，设定的起点为北京，终点为天津，则只需要选择河北省和北京市的地图范围作为待规划地图区域即可。具体实施时，可以根据设定的起点和终点确定一个包括所述起点和终点的最小圆形或矩形区域，然后，将该圆形或矩形区域沿上、下、左、右四个方向下外扩展预设距离，使得扩展后的圆形或矩形区域的面积增加至2倍，或者更大倍数，将扩展后的圆形或矩形区域确定为待规划地图区域。

步骤210，将所述待规划地图区域转化为栅格地图。

对于确定的待规划地图区域进行栅格化，将矢量地图转化为栅格地图，减小存储空间和数据运算量，同时保留地图中的地理位置的地貌信息。将矢量地图转化为栅格地图时可以采用现有技术中的方案，本发明实施例不再赘述。本发明对将所述待规划地图区域转化为栅格地图的具体实施方案不做限定。

步骤220，通过将所述栅格地图中的障碍物标记为背景点、将非障碍物标记为前景点，得到二值化的栅格地图。

转化后得到的待规划地图区域的栅格地图中，依然保留着每个像素点所在位置的地貌信息，如某个像素点所在位置为建筑物、为山丘，或为河流、为草原等。在本发明中，无人机飞行的地图上的障碍物至少包括：建筑物、树木、山丘等遮挡区域。对于地图上的其他地貌，则可以认为是非障碍物。具体实施时，通过将所述栅格地图中的障碍物标记为背景点、将非障碍物标记为前景点，得到二值化的栅格地图，具体包括：根据栅格地图中的地图信息，将无人机飞行的高度平面有遮挡的位置对应的像素点标记为背景点，将无人机飞行的高度平面为空旷区域的位置对应的像素点标记为前景点。采用不同的像素值标记背景点和前景点，例如：像素值为1表示该点为前景点，像素值为0表示该点为背景点，将得到一幅二值化的黑白栅格地图，如图3所示。在栅格地图300中，所有背景点构成的区域为障碍物区域，如图3中的301；所有前景点构成的区域为非障碍物区域，即可飞行区域，如图3中的302。

然后，对所述前景点构成非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径。具体实施时，对所述前景点构成非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径包括：将所述二值化的栅格地图向四周扩展单像素宽度，并将扩展的像素区域标记为背景点，以生成栅格地图边界；将所述二值化的栅格地图内，所述起点和终点所在位置对应的像素点标记为背景点；对扩展后的所述二值化的栅格地图内，由所述前景点构成的非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径。

步骤230，将所述二值化的栅格地图向四周扩展单像素宽度，并将扩展的像素区域标记为背景点，以生成栅格地图边界。

对于得到的二值化的黑白栅格地图，沿上、下、左、右四个方向分别向外扩展单像素宽度，得到扩展后的栅格地图。若得到的栅格地图的大小为i行，j列即C(i,j)，在细化前对地图进行添加边界处理。即将原栅格地图C(i,j)变为C(i+2,j+2)：在栅格地图的第一行前插入一行，最后一行增后加一行，第一列前插入一列，最后一列后增加一列。原栅格地图的第一行，变为当扩展后的栅格地图的第二行，原栅格地图的第一列变为扩展后的栅格地图的第二列，原栅格地图的最后一行变为扩展后的栅格地图的倒数第二行，原栅格地图的最后一列变为扩展后的栅格地图的倒数第二列。

然后将扩展的像素区域标记为背景点，得到添加了边界的扩展后的栅格地图，如图4所示。其中，401障碍物区域，402为非障碍物区域，403为扩展后的二值化的栅格地图边界。

步骤240，将所述设定的起点和终点所在位置对应的扩展后的所述二值化的栅格地图内的像素点标记为背景点。

然后，将设定的起点和终点所在位置对应的扩展后的所述二值化的栅格地图内的像素点标记为背景点。如图4中的起点404和终点405。

步骤250，对扩展后的所述二值化的栅格地图内，由所述前景点构成的非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径。

所述对扩展后的所述二值化的栅格地图内，由所述前景点构成的非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径，包括：通过快速并行细化算法，从扩展后的所述二值化的栅格地图的上、下、左、右四个方向开始，对由所述前景点构成的非障碍物区域进行并行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径。

具体实施时，从扩展后的所述二值化的栅格地图的上、下、左、右四个边界开始，逐点考察所述栅格地图上的每个前景点P，当所述前景点P满足第一预设条件时，将该前景点标记为背景点；当所有前景点考察一遍后，再一次从扩展后的所述二值化的栅格地图的上、下、左、右四个边界开始，逐点考察所述栅格地图上的每个前景点P，当所述前景点P满足第二预设条件时，将该前景点标记为背景点。重复执行前述两个考察像素点的步骤，直至没有符合第一预设条件和第二预设条件的像素点。所述第一预设条件为：前景点P的八邻域像素点中包括预设数量的背景点、顺时针或逆时针遍历前景点P八邻域的像素点，像素值的跳变次数等于1、像素点P上、下、右邻域的像素点的像素值乘积等于0且像素点P左、右、下邻域的像素点的像素值乘积等于0。所述第二预设条件为：前景点P的八邻域像素点中包括预设数量的背景点、顺时针或逆时针遍历前景点P八邻域的像素点，像素值的跳变次数等于1、像素点P上、左、右邻域的像素点的像素值乘积等于0且像素点P左、上、下邻域的像素点的像素值乘积等于0。

具体实施时，以像素点P的八邻域的像素点表示为P0～P7为例，像素点P和其八邻域的像素点P0～P7的位置关系如图5所示。首先从图4所示的设置了边界条件的栅格地图的上、下和左、右四个边界起，分别取每个边界上一个点作为前景点P，考察该前景点P和其八邻域的各像素点的像素值的关系。具体实施时，为了提高考察的效率，采用四个分布式计算系统或四个线程，每个计算系统或线程对应一个边界，同时从四个边界起向栅格地图的中心开始考察。

第一步，根据右下边界和左上角的点细化前景区域。如果前景点P的八邻域像素点同时满足以下四个条件：

2≤B(P)≤6； (条件1)

A(P)＝1； (条件2)

P0×P2×P6＝0； (条件3)

P0×P4×P6＝0； (条件4)

则将如果前景点标记为背景点。其中，表示前景点P八邻域的像素点中前景点的个数；表示顺时针遍历前景点P八邻域的像素点，像素值从0到1的跳变次数。条件1是为了保留孤立点(即B(P)＝0)、端点(即B(P)＝1)、近似内点(即B(P)＝7)和内点(即B(P)＝8)；条件2是为了保留栅格地图中前景骨架点(即路径骨架点)；条件3和4是为了保证删除右下边界和左上角的点，使路径细化。

当从上、下两个边界同时向栅格地图中间的像素点考察，或从左、右两个边界同时向栅格地图中间的像素点考察时，相应计算系统或线程在栅格地图的中间位置处理到同一个点，表示一次考察完成。

第二步，根据左上边界和右下角的点细化前景区域。再一次启动四个分布式计算系统或四个线程，每个计算系统或线程对应一个边界，同时从四个边界起向栅格地图的中心开始考察。如果前景点P的八邻域像素点同时满足以下四个条件：

2≤B(P)≤6； (条件5)

A(P)＝1； (条件6)

P0×P2×P4＝0； (条件7)

P2×P4×P6＝0； (条件8)

则将前景点标记为背景点。其中，表示前景点P八邻域的像素点中前景点的个数；表示顺时针遍历前景点P八邻域的像素点，像素值从0到1的跳变次数。条件5是为了保留孤立点(即B(P)＝0)、端点(即B(P)＝1)、近似内点(即B(P)＝7)和内点(即B(P)＝8)；条件6是为了保留栅格地图中前景骨架点(即路径骨架点)；条件7和8是为了保证删除左上边界和右下角的点，使路径细化。

当从上、下两个边界同时向栅格地图中间的像素点考察，或从左、右两个边界同时向栅格地图中间的像素点考察时，相应计算系统或线程在栅格地图的中间位置处理到同一个点，表示一次考察完成。

以上两步不断循环，直至执行一遍上述两个步骤后，没有发现被标记为背景点的前景点(即没有符合第一预设条件和第二预设条件的前景点)，则细化过程结束。得到如图6所示的多条可飞行的无人机与障碍物碰撞机率最小的路径601，602为膨胀后的背景区域。

具体实施时，八邻域像素的标识不同，前述第一步中的条件3和4、及第二步中的条件7和8略有不同。本领域技术人员可以在本发明公开的实施例基础上经过简单变换或替换，得到其他八邻域标识方法及条件公式，都适用于本发明。

当对扩展后的所述二值化的栅格地图内，由所述前景点构成的非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径仅有一条时，则将得到从所述起点到终点无人机与障碍物碰撞机率最小的路径作为无人机飞行的安全路径。当得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径多于一条时，优选的，选择最短的一条路径作为无人机飞行的安全路径。

步骤260,从得到的从所述起点到终点无人机与障碍物碰撞机率最小的所有路径中选择一条最短路径。通常，从起点到终点的无人机与障碍物碰撞机率最小的路径不是唯一的，图6中从起点到终点的白色路径为多条无人机与障碍物碰撞机率最小的路径，此时需要从多条路径中选取出一条路径作为无人机的飞行路径。具体实施时，可以利用A*(A-star寻路算法)或者其他最短路径搜寻方法，获得的最短且与障碍物碰撞机率最小的路径。本发明对从多条无人机与障碍物碰撞机率最小的路径中选择一条最短的路径的具体方法不做限定。

本发明实施例公开的无人机路径规划方法，本发明实施例公开的无人机路径规划方法，通过将待规划地图区域转化为栅格地图；通过将所述栅格地图中的障碍物标记为背景点、将非障碍物标记为前景点，得到二值化的栅格地图；基于设定的起点、终点以及生成的栅格地图边界，对所述二值化的栅格地图内由所述前景点构成非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径，解决了现有技术中的路径规划方法不适用于精确规划无人机与障碍物碰撞机率最小的路径的问题。通过对非障碍物区域进行细化，得到多条无人机与障碍物碰撞机率最小的路径，然后，在多条无人机与障碍物碰撞机率最小的路径中选择一条最短的路径，作为无人机的飞行路径，即保证了飞行的安全性，又节约了能源。

快速并行细化算法在图像处理领域已经得到广泛的应用，该算法的特点是从图像的上、下、左、右4个方向同时对前景进行细化，直到最后得到单像素宽度的前景特征，对前景点进行细化的过程，也可以看作是背景点不断膨胀的过程。但是现有技术中利用并行细化算法进行前景细化时，仅能得到离散的单像素宽度的骨架，例如笔迹鉴定，指纹识别等，不能直接用于路径规划。本发明通过对现有并行细化算法进行改进，通过设置规划地图区域的边界判断条件，结合路径的起点和终点的处理，利用并行细化算法可以得到无人机可飞行的连通的与障碍物碰撞机率最小的路径，即无人机飞行的最安全路径。

利用快速并行细化算法进行路径规划，从4个方向同时细化的特点，得到细化后的单像素宽度的路径，此路径与障碍物的距离最远；具体过程可看作为前后左右4个方向障碍物同时以相同的速度进行膨胀，直到4个方向的障碍物相互碰撞。相互碰撞的点为上、下方向，或左、右方向障碍物的中间位置点。同时也可以看作将无人机可飞行区域进行细化后得到的骨架区域离障碍物的位置最远的点。如图7所示，图7中A,B为障碍物，A,B之间的区域为非障碍物区域，A,B同时以相同的速度膨胀，相交区域为C。其中，C距离A和B的距离相等。或者，可以表述为对AB中间的区域进行细化，最后细化得到单像素宽度的区域C；若AB间的距离为L，那么CA＝L/2，CB＝L/2；若C为AB间任意一点，C到A间的距离为m，那么C到B之间的距离为L-m；定义目标函数为:F越小表示目标点C与A,B碰撞的机率越小，反之F越大表示C与A,B碰撞的机率越大。所以目标函数取最小值，则可以实现无人机与障碍物碰撞的机率最小，此时的轨迹为最安全的轨迹。改写目标函数可以得到:可以看出若使F取值最小，那么唯一条件为即m点必须位于AB的中点,而这正满足细化算法的结果。

通过前述目标函数对得到的无人机的多条无人机与障碍物碰撞机率最小的路径进行验证，将障碍物看作为背景点，将无人机可以飞行的区域看作前景点，前景点构成的区域为可飞行区域，即待细化的区域。细化后得到的无人机与障碍物碰撞机率最小的路径满足的条件，则细化得到的无人机与障碍物碰撞机率最小的路径为无人机可飞行的最安全的轨迹。

实施例三：

相应的，参见图8，本发明还公开了一种无人机路径规划装置，包括：

栅格化模块800，用于将待规划地图区域转化为栅格地图；

二值化模块810，用于通过将所述栅格化模块800得到的栅格地图中的障碍物标记为背景点、将非障碍物标记为前景点，得到二值化的栅格地图；

路径细化模块820，用于基于设定的起点、终点以及生成的栅格地图边界，对所述二值化的栅格地图内由所述前景点构成的非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径。

可选地，如图9所示，所述路径细化模块820包括：

条件设置单元8201，用于将所述二值化的栅格地图向四周扩展单像素宽度，并将扩展的像素区域标记为背景点，以生成栅格地图边界；

所述条件设置单元8201，还用于将所述二值化的栅格地图内，所述起点和终点所在位置对应的像素点标记为背景点；

细化单元8202，用于对扩展后的所述二值化的栅格地图内，由所述前景点构成的非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径。

可选的，所述细化单元8202具体用于：

通过快速并行细化算法，从扩展后的所述二值化的栅格地图的上、下、左、右四个方向开始，对由所述前景点构成的非障碍物区域进行并行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径。

可选地，如图9所示，所述无人机路径规划装置还包括：

待规划地图区域确定模块840，用于根据设定的起点和终点，确定地图上的待规划地图区域。

可选地，所述二值化模块810，用于：

根据栅格地图中的地图信息，将无人机飞行的高度平面有遮挡的位置对应的像素点标记为背景点，将无人机飞行的高度平面为空旷区域的位置对应的像素点标记为前景点。

可选地，所述装置还包括路径选择模块830，用于当所述路径细化模块820得到的从所述起点到终点无人机与障碍物碰撞机率最小的所有路径多于一条时，从得到的从所述起点到终点无人机与障碍物碰撞机率最小的所有路径中选择一条最短路径。

本发明实施例公开的无人机路径规划装置，通过将待规划地图区域转化为栅格地图；通过将所述栅格地图中的障碍物标记为背景点、将非障碍物标记为前景点，得到二值化的栅格地图；基于设定的起点、终点以及生成的栅格地图边界，对所述二值化的栅格地图内由所述前景点构成的非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径，解决了现有技术中的路径规划方法不适用于精确规划无人机与障碍物碰撞机率最小的路径的问题。通过对非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径，保证了飞行的安全性。当在从所述起点到终点无人机与障碍物碰撞机率最小的所有路径多于一条时，选择一条从所述起点到终点无人机与障碍物碰撞机率最小的最短路径，作为无人机的可飞行的连通的安全路径，即保证了飞行的安全性，又节约了能源。

本发明的装置实施例与方法相对应，装置实施例中各模块的具体实现方式参见方法是实施例，此处不再赘述。

本领域普通技术人员可以意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、或者计算机软件和电子硬件的结合来实现。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本发明的范围。

本领域普通技术人员可以理解，在本申请所提供的实施例中，所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，即可以位于一个地方，或者也可以分布到多个网络单元上。另外，在本发明各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。

所述功能如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、ROM、RAM、磁碟或者光盘等各种可以存储程序代码的介质。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，不经过创造性劳动想到变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应以权利要求的保护范围为准。

Claims (12)

1.一种无人机路径规划方法，其特征在于，包括：

将待规划地图区域转化为栅格地图；

通过将所述栅格地图中的障碍物标记为背景点、将非障碍物标记为前景点，得到二值化的栅格地图；

基于设定的起点、终点以及生成的栅格地图边界，对所述二值化的栅格地图内由所述前景点构成的非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径。

2.根据权利要求1所述的方法，其特征在于，所述基于设定的起点、终点以及生成的栅格地图边界，对所述二值化的栅格地图内由所述前景点构成的非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径的步骤，包括：

将所述二值化的栅格地图向四周扩展单像素宽度，并将扩展的像素区域标记为背景点，以生成栅格地图边界；

将所述二值化的栅格地图内，与所述起点和终点所在位置对应的像素点标记为背景点；

对扩展后的所述二值化的栅格地图内，由所述前景点构成的非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径。

3.根据权利要求2所述的方法，其特征在于，所述对扩展后的所述二值化的栅格地图内，由所述前景点构成的非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径的步骤，包括：

通过快速并行细化算法，从扩展后的所述二值化的栅格地图的上、下、左、右四个方向开始，对由所述前景点构成的非障碍物区域进行并行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径。

4.根据权利要求1所述的方法，其特征在于，所述将待规划地图区域转化为栅格地图的步骤之前，还包括：

根据设定的起点和终点，确定地图上的待规划地图区域。

5.根据权利要求1所述的方法，其特征在于，所述通过将所述栅格地图中的障碍物标记为背景点、将非障碍物标记为前景点，得到二值化的栅格地图的步骤，包括：

根据栅格地图中的地图信息，将无人机飞行高度平面有遮挡的位置对应的像素点标记为背景点，将无人机飞行的高度平面为空旷区域的位置对应的像素点标记为前景点。

6.根据权利要求1至5任意一项权利要求所述的方法，其特征在于，当得到的从所述起点到终点无人机与障碍物碰撞机率最小的所有路径多于一条时，所述方法还包括：从得到的从所述起点到终点无人机与障碍物碰撞机率最小的所有路径中选择一条最短路径。

7.一种无人机路径规划装置，其特征在于，包括：

栅格化模块，用于将待规划地图区域转化为栅格地图；

二值化模块，用于通过将所述栅格化模块得到的栅格地图中的障碍物标记为背景点、将非障碍物标记为前景点，得到二值化的栅格地图；

路径细化模块，用于基于设定的起点、终点以及生成的栅格地图边界，对所述二值化的栅格地图内由所述前景点构成的非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径。

8.根据权利要求7所述的装置，其特征在于，所述路径细化模块包括：

条件设置单元，用于将所述二值化的栅格地图向四周扩展单像素宽度，并将扩展的像素区域标记为背景点，以生成栅格地图边界；

所述条件设置单元，还用于将所述二值化的栅格地图内，所述起点和终点所在位置对应的像素点标记为背景点；

细化单元，用于对扩展后的所述二值化的栅格地图内，由所述前景点构成的非障碍物区域进行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径。

9.根据权利要求8所述的装置，其特征在于，所述细化单元用于：

通过快速并行细化算法，从扩展后的所述二值化的栅格地图的上、下、左、右四个方向开始，对由所述前景点构成的非障碍物区域进行并行细化，得到从所述起点到终点无人机与障碍物碰撞机率最小的所有路径。

10.根据权利要求7所述的装置，其特征在于，还包括：

待规划地图区域确定模块，用于根据设定的起点和终点，确定地图上的待规划地图区域。

11.根据权利要求7所述的装置，其特征在于，所述二值化模块用于：

根据栅格地图中的地图信息，将无人机飞行的高度平面有遮挡的位置对应的像素点标记为背景点，将无人机飞行的高度平面为空旷区域的位置对应的像素点标记为前景点。

12.根据权利要求7至11任意一项权利要求所述的装置，其特征在于，所述装置还包括：

路径选择模块，用于当所述路径细化模块得到的从所述起点到终点无人机与障碍物碰撞机率最小的所有路径多于一条时，从得到的从所述起点到终点无人机与障碍物碰撞机率最小的所有路径中选择一条最短路径。