基于邻域约束的空地异构机器人系统路径规划方法

摘要

本发明涉及了一种基于邻域约束的空地异构机器人系统路径规划方法，异构机器人系统由至少一台地面移动机器人和至少一台空中飞行机器人组成；其特征在于：地面移动机器人和空中飞行机器人同时从起点出发，依次访问

说明书

技术领域

本发明属于移动机器人路径规划领域，尤其涉及空地异构机器人系统在运动约束条件下基于邻域约束的路径规划方法。

背景技术

随着科技的进步，机器人技术与人类的生活越来越紧密联系在一起。尤其是多种新型机器人的出现，使得以往单一机器人无法完成的复杂任务可以依靠多机器人合作来完成。例如：过去几十年来出现了大量有关多机器人合作的研究，如合作围捕、地图构建、共同覆盖、目标跟踪、通信中继、信息传感、编队、组网等。在过去多机器人系统的研究中，针对同构机器人系统的比较多。而那些异构机器人系统，通常由于各个机器人个体具有不同的功能和外形、不同的载荷和运动能力而拥有差异巨大的动力学和运动学。当这些个体在一起相互协作时会产生冗余与耦合等影响，因此具有很大的挑战。

地面移动机器人和空中飞行机器人是两类典型的异构机器人。地面机器人的运动局限于二维平面，而空中机器人具有强大的三维运动能力。通常情况下，空中机器人运动迅速，响应快捷，不易受到地面障碍的阻挡，但滞空时间往往有限，而且自身定位精度相对较低，获得的目标信息精度也较低。而地面机器人可以携带大量物资，穿越狭窄的通道“边走边完成任务”，针对目标完成准确的识别与跟踪，甚至可完成其它更加精细的任务，但是容易受到地面障碍的阻挡，对目标采集图像信息时视角单一，无法获得全局图像信息。因此，路径规划问题必须考虑空中机器人和地面机器人各自在功能分配上的优势，这给异构系统的研究带来了新的挑战。

目前已有的异构机器人系统路径规划方法主要有两类：一类是建立组合优化模型，然后采用启发式方法求解，因复杂度高，往往只能求得次优解；还有一类便是基于数学规划模型的方法，这一类方法在计算效率方面具有较大的优势，但是通常需要借助于大量的简化和假设。现有的方法，无论是组合优化方法还是数学优化方法，均将各个待访问的目标点当作精确位置，而在实际应用中，目标点通常是一个范围或邻域，比如救援地点、物资投放地点都允许在一定范围内有效，而采用太精确的任务规划，不利于效率提高。

发明内容

本发明为了解决上述技术问题，提供了一种基于邻域约束的空地异构机器人系统路径规划方法。在邻域约束范围内访问任务点，提高了路径规划的效率，减少了路径规划方法的复杂度。

为解决上述技术问题，本发明采用如下技术方案：

一种基于邻域约束的空地异构机器人系统路径规划方法，异构机器人系统由至少一台地面移动机器人和至少一台空中飞行机器人组成；其特征在于：地面移动机器人和空中飞行机器人同时从起点出发，依次访问N个子任务点执行子任务，最后共同到达目的地；为了节省能量，地面移动机器人在设定时间段充当移动平台载着空中飞行机器人运动，当接收到子任务时，空中飞行机器人从地面移动机器人上自主起飞去执行所述子任务，完成子任务后空中飞行机器人再返回地面移动机器人补充能量，并陪同地面移动机器人一起运动继续完成下一个子任务；空中机器人在前往执行某个子任务时，与其搭配的地面移动机器人持续前进以尽可能与空中飞行机器人协调同步；全部任务完成后，所有空中飞行机器人均返回并降落在各自搭配的地面移动机器人上；在此过程中需要计算出地面移动机器人的路径点，以及飞行机器人从地面机器人平台上起飞，执行完所有子任务后再返回的整个航迹点；通过引入二值变量对各个子任务点依次访问，然后分别建立地面机器人和空中机器人的运动约束，以完成对所有子任务点访问的总时间最小为目标函数建立混合整数规划模型；所述设定时间段设置为整个任务过程中空中飞行机器人执行子任务之外的时间段，且以空地双方能够相互识别和定位为前提，每次空中飞行机器人执行子任务的时间须小于其自身最大滞空时间。

上述基于邻域约束的空地异构机器人系统路径规划方法主要包括如下步骤：

步骤1：设置异构机器人系统的系统参数：设置整个异构机器人系统的运动起点、任务点、目标点的位置以及每个子任务点规定的邻域范围大小；设置地面移动机器人与空中飞行机器人各自的最大运动速度；设置空中机器人的最大滞空时间与补充能量的最小时间参数；

步骤2：根据空地异构机器人自身约束与相互间的约束条件，建立混合整数优化模型，具体过程如下：

步骤2-1：异构机器人系统所包含的机器人一起从起始点出发，通过引入二 值变量，保证每个子任务点必须被访问一次，且最多只能访问一次；

步骤2-2：当异构机器人系统一起运动至某一地点时，空中飞行机器人离开运载平台单独执行任务，在满足空中飞行机器人最大滞空时间与最大运动速度的约束条件下，完成对一个或多个子任务点邻域范围内的访问；

步骤2-3：在步骤2-2进行的过程中，地面机器人仍然以最大速度沿直线路径运动，并满足最大运动速度约束条件；

步骤2-4：飞行机器人完成任务之后，返回降落在地面移动机器人平台上，在随地面移动机器人前进的过程中补充能量，为下次任务的到来做准备；为了确保任务的顺利完成，避免半途而废，空中机器人只有在充电完成后才能再次起飞，在充电过程中，需满足最短充电时间约束；同时，在整个协同运动过程中，地面机器人仍需保证最大运动速度约束；

步骤2-5：循环步骤2-2、步骤2-3、步骤2-4，直至异构机器人系统完成对所有子任务点的访问，最终一起到达目标点；

步骤2-6：最后，以完成对所有子任务点访问的总时间最小为代价，建立目标函数；

步骤2-7：以上述步骤2-1至步骤2-6所得的约束条件与目标函数建立混合整数非线性规划模型；

步骤3：根据建立的混合整数优化模型进行路径规划，并利用异构机器人系统执行规划的路径。

上述技术方案中，步骤1中，设定异构机器人系统依次访问多个子任务点：T₁,T₂,...,T_N，最后共同到达目的地T_e；地面移动机器人以最大速度v_c,max运动，空中飞行机器人最大运动速度为v_h,max。

上述技术方案中，步骤2-2中，所述子任务点T_i的邻域以T_i点为圆心，以R_i为半径形成圆形分析窗口，其中，T_i为邻域中心，R_i为邻域半径；空中飞行机器人对某个子任务点的访问只需要落入该子任务点的邻域范围即可。

上述技术方案中，步骤2-2中，空中飞行机器人若同时访问多个子任务点，每个子任务点T_i可能具有不同的邻域半径，即大小各不相同的圆域。

相对于现有技术，本发明基于邻域约束的空地异构机器人系统路径规划方 法，提出了带邻域约束的混合整数规划模型，使得空中机器人与地面机器人合作时，可以发挥各自的优势解决更加复杂的任务。提高了路径规划的效率，减少了算法的复杂度，又在一定程度上实现了节约能源的目的。执行任务的空中机器人只需根据自身约束与地面移动平台的相互约束条件在邻域内完成任务即可返回，节省了时间与能源，在同等的时间段内，完成更多的任务，大大提高了运行效率。

附图说明

图1为本发明的空地异构机器人系统路径规划示意图。

图2为本发明的异构机器人系统在邻域约束条件下的路径规划结果。

图3为未加入邻域约束的异构机器人系统路径规划结果。

具体实施方式

为了进一步说明本发明的技术方案，下面结合附图1-3对本发明进行详细的说明，但不是对本发明的限定。

图1为空地异构机器人系统路径规划示意图。由地面移动机器人搭载无人机从T_S出发，依次访问N个子任务点T₁,T₂,...,T_N，最后共同到达目的地T_e。其中虚线代表地面机器人的路径，每个子任务点周围的实线圆代表各自的邻域范围。在此异构机器人系统中，地面移动机器人以最大速度v_c,max在大的范围内运动，无人机最大运动速度为v_h,max，运行速度敏捷但范围有限，且二者都为匀速运动。

本发明一种基于邻域约束的空地异构机器人系统路径规划方法，具体包括以下步骤：

步骤1：设置异构机器人系统的系统参数：设置整个系统的运动起点、任务点、目标点以及每个子任务点规定的邻域范围；设置地面移动机器人与空中飞行机器人各自的最大运动速度；设置空中机器人的最大滞空时间与补充能量的最小时间参数；具体设置如下所示：

步骤1-1：设定异构机器人系统运动起点T_S、N个子任务点以及目标点T_e的位置如下表1所示(取N＝4)：

表1路径规划的起点、目标点和各子任务点坐标(单位：km)

步骤1-2：取各个子任务点的邻域范围为等大小的圆形区域，且半径为3km；

步骤1-3：设置地面移动机器人与空中飞行机器人的最大运动速度分别为18km/h和90km/h；空中飞行机器人的最大滞空时间为21min，每次充电完成的最短时间为10min；

步骤2：根据空地异构机器人自身约束与相互间的约束条件，建立混合整数优化模型，具体过程如下：

步骤2-1：异构机器人系统所包含的机器人一起从起始点出发，通过引入二值变量，保证每个子任务点必须被访问一次，且最多只能访问一次，具体实现方法如下：

定义N×N维二值变量矩阵α_i,j∈{0,1}，其中α_i,j＝1表示无人机连续访问任务点T_i,T_i+1,...,T_j，1≤i≤j≤N，其它情况下，α_i,j＝0，则有

$\underset{i=1}{\overset{k}{\Sigma }}\underset{j=k}{\overset{N}{\Sigma }}{\alpha }_{i,j}=1---\left(1\right)$

其中，k＝1,2,...,N；

步骤2-2：当达到某一地点时，空中飞行机器人离开运载平台单独执行任务，在满足空中飞行机器人最大滞空时间与最大运动速度的约束条件下，完成不同邻域范围内一个或多个子任务点的访问，其具体实现方法包含了以下步骤：

步骤2-2-1：由于空中飞行器自身携带能源有限，必须在能量耗尽之前返回地面机器人及时补充能量。定义变量矩阵f∈R^N，f_i≥0表示无人机从t_i∈R²点起飞，连续访问子任务点T_i,T_i+1,...,T_j，最后在l_j∈R²点着陆所经过的时间，空中飞行机器人每次起飞执行任务必须满足最大滞空时间约束：

α_i,jf_i≤t_h,max(2)

其中，t_h,max表示允许的最大滞空时间，1≤i≤j≤N；

步骤2-2-2：通过引入任务点邻域的概念，使机器人对子任务点的访问只需 要落入各个子任务点的邻域即可，节省访问时间。设子任务点T_i的邻域点为w_i，满足如下关系：

$\left|\right|T_i-w_i|{|}^2\le R_i^2---\left(3\right)$

其中，R_i为子任务点T_i的邻域范围参数，假设邻域为圆形区域；

步骤2-2-3：设d_i,j表示无人机从子任务点T_i的邻域点w_i一直访问到子任务点T_j的邻域点w_j经过的距离，如下：

$d_{i,j}=\underset{k=i}{\overset{j-1}{\Sigma }}{p}_k---\left(4\right)$

其中，

p_i＝||w_i-w_i+1||,i＝1，2，...,N-1(5)

当i≥j时，d_i,j＝0；

步骤2-2-4：当空中机器人起飞后连续访问多个子任务点的邻域点w_i,w_i+1,...,w_j，则空中机器人的最大运动速度满足以下约束：

$\frac{{\alpha }_{i,j}\left(\right||t_i-w_i||+d_{i,j}+||w_j-l_j|\left|\right)}{f_i}\le v_{h,max}$

即

α_i,j(||t_i-w_i||+d_i,j+||w_j-l_j||)-v_h,maxf_i≤0(6)

步骤2-3：在步骤2-2进行的过程中，地面机器人仍然以最大速度沿直线路径运动，空中机器人脱离运载平台单独执行任务，从t_i点起飞，直到在l_j点着陆，则在这段飞行时间f_i之内，地面机器人满足最大速度约束：

$\frac{{\alpha }_{i,j}\left|\right|t_i-l_j\left|\right|}{f_i}\le v_{c,max}$

即

α_i,j||t_i-l_j||-v_c,maxf_i≤0(7)

其中，v_c，max表示地面机器人的最大运动速度，1≤i≤j≤N；

步骤2-4：飞行机器人完成任务之后，返回降落在地面移动机器人平台上，在随地面移动平台前进的过程中补充能量，为下次任务的到来做准备；在充电过程中，需满足最短充电时间约束；同时，在整个协同运动过程中，地面机器人仍需保证最大运动速度约束；其具体实现方法包含了以下步骤：

步骤2-4-1：为了确保任务的顺利完成，避免半途而废，空中机器人只有在充电完成后才能再次起飞。假设能量补充完成所需最小时间为t_r,min，则还须满足以下约束：

t_r,minα_i,j-s_j≤0(8)

其中，1≤i≤j≤N-1；

步骤2-4-2：当无人机没有外出执行任务时，保持降落并停留在地面机器人平台上随之一起运动。设降落点坐标为l_j，即刚访问过任务点T_j，随着移动平台一起运动，直至下一个起飞点坐标t_j+1。定义变量矩阵s∈R^N-1，s_j≥0表示空中机器人停留在平台上面一起运动的时间。这段时间内地面机器人的运动也须满足最大运动速度约束：

$\frac{{\alpha }_{i,j}\left|\right|l_j-t_{j+1}\left|\right|}{s_j}\le v_{c,max}$

即

α_i,j||l_j-t_j+1||-v_c,maxs_j≤0(9)

其中，1≤i≤j≤N-1；

步骤2-5：循环步骤2-2、步骤2-3、步骤2-4，直至异构机器人系统完成对所有子任务点的访问，最终一起到达目标点；

步骤2-6：最后，以完成对所有子任务点访问的总时间最小为代价，建立目标函数。总的花费时间y由四部分组成：

(1)空中机器人首次起飞之前与地面机器人共同运行的时间

(2)空中机器人最后一次降落在地面机器人上一起运动到达目标点时经过 的时间

(3)空中机器人飞行的总时间

(4)在访问子任务点T₁至T_N过程中，地面机器人载着空中机器人经过的总时间

最终目标函数如式(10)所示：

$\begin{array}{cc}\min & y=\frac{1}{v_{c,max}}\left(\right||T_s-t_1||+||l_N-T_e|\left|\right)+\underset{i=1}{\overset{N}{\Sigma }}{f}_i+\underset{j=1}{\overset{N-1}{\Sigma }}{s}_j\end{array}---\left(10\right)$

步骤2-7：以上述步骤2-1至步骤2-6所得的约束条件与目标函数建立混合整数非线性规划模型，其模型如式(11)所示：

$\begin{array}{cc}\underset{\alpha ,f,s,t,l,d,p}{\min }& y\\ s.t.& \left(1\right)~\left(5\right),\left(7\right)~\left(10\right),\\ & {\alpha }_{i,j}\in \left\{0,1\right\},1\le i,j\le N\\ & f_i\ge 0,1\le i\le N\\ & s_j\ge 0,1\le j\le N-1\\ & d_{i,j}\ge 0,1\le i,j\le N\\ & p_i\ge 0,1\le i\le N-1\end{array}---\left(11\right)$

步骤3：根据建立的模型，利用实验的方法得到路径规划的结果。仿真程序在计算机上运行，借助工具箱OPTI和求解器SCIP获得最终路径规划结果，并利用异构机器人系统执行规划的路径。

模型共包括了66个决策变量，207条约束，机器人的运动路径规划结果如图2所示，其中4个圆圈分别表示各子任务点的邻域。求得的决策变量α如式(12)所示，异构机器人系统完成任务花费5.4595h。空中机器人与地面机器人的分离点、汇合点坐标，以及各邻域点坐标分别如表2和表3所示。

$\alpha =\left(\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right)---\left(12\right)$

表2空中机器人起飞点和着陆点坐标(单位：km)

表3邻域访问点坐标(单位：km)

从图2中可以看出，空中机器人在t₁点离开地面机器人，开始飞向子任务点T₁的邻域点w₁，访问了w₁后接着飞向T₂的邻域点w₂，最后与地面机器人在l₂点汇合，并着陆在地面机器人上面一起运动。当地面机器人拖着空中机器人运动的同时，也给空中机器人补充能量。经过一段时间后空中机器人能量补给完成，在t₃点再次起飞，访问子任务点T₃的邻域点w₃后返回到l₃点与地面机器人汇合。依次类推，直至完成所有任务，地面机器人载着空中机器人到达终点。式(12)所示变量α中取值为1的元素包括α_1,2,α_3,3,α_4,4，表示空中机器人的起飞点分别在访问子任务点T₁,T₃,T₄之前，而着陆点分别在访问子任务点T₂,T₃,T₄之后，与图2所示一致。

如果不考虑邻域约束，求得的路径如图3所示，完成任务所需总时间为5.9130h，与本发明所提出的方法相比，时间略有增加。比较图2和图3可以发现，空中机器人在访问子任务点T₁和T₂时采用的策略是不同的。当有邻域约束时，空中机器人会在一次飞行行动中完成两个邻域点w₁和w₂的访问。如果没有邻域约束，因待访问的两个子任务点与其邻域点相比距离更远，空中机器人分两次完 成任务，中间需要返回地面机器人补充一次能量。地面机器人从l₁运动到t₂所需时间为13.5896min，其中有10min在给空中机器人补充能量。

综上，本发明基于邻域约束的空地异构机器人系统路径规划方法，提出了带邻域约束的混合整数规划模型，使得空中机器人与地面机器人合作时，可以发挥各自的优势解决更加复杂的任务。提高了路径规划的效率，减少了算法的复杂度，又在一定程度上实现了节约能源的目的。