一种基于最小费用最大流的无人机任务分配方法

技术领域

本发明属于无人机在执行任务前的任务分配技术领域，尤其涉及一种基于最小费用最大流的无人机任务分配方法。

背景技术

尽管无人机技术在不断的发展，飞行时间越来越长，但无人机的能耗仍是一个挑战。

在执行任务过程中，考虑到无人机的能源有限并且在不断的消耗中以及回收问题，无人机需要频繁返回补给点进行能源与物资的补充。现有研究多令无人机执行任务后返回出发点进行补给，这将无人机的活动范围限制在出发点周围，导致无人机无法执行较远距离的任务，限制了无人机的利用率。综上，由于无人机存储的能源有限，如何在考虑无人机能源限制的前提下，为无人机分配远距离的任务，扩大无人机的活动范围成为了主要的技术问题。

发明内容

发明目的：本发明所要解决的技术问题是针对现有技术的不足，提供一种基于最小费用最大流的无人机任务分配方法，能够在有限的能源的前提下，在已知区域中提前规划无人机的飞行路径，减少无人机能源的消耗，完成远距离任务，防止无人机因为能源不足而无法完成任务或无法回收。

为了解决上述技术问题，本发明公开了一种基于最小费用最大流的无人机任务分配方法，包括如下步骤：

步骤1，定义任务区域内共有N个不同的任务目标构成集合L＝{L

步骤2，根据任务区域内的任务与无人机基站构建一个相应的最小费用最大流模型；

步骤3，将完成的任务数量建模为流量，利用步骤2中构建的最小费用最大流模型，将任务区域内的任务和无人机基站划分为若干个“起飞无人机基站-任务集合-降落无人机基站”组合；

步骤4，将步骤3中得到的“起飞无人机基站-任务集合-降落无人机基站”组合中能够顺序执行的“起飞无人机基站-任务集合-降落无人机基站”组合构建为一条初始路径I；

步骤5，若初始路径I包含所有步骤3得到的“起飞无人机基站-任务集合-降落无人机基站”组合，则初始路径I即为无人机执行所有任务的最终路径F；否则将步骤3得到的且未被初始路径I包含的“起飞无人机基站-任务集合-降落无人机基站”组合记为候选“起飞无人机基站-任务集合-降落无人机基站”组合，构成集合CLS＝{c

作为本发明的一种优选方案，步骤2所述最小费用最大流模型的构建如下：

(1)构建最小费用最大流模型的节点

1)添加源节点s与终点节点t作为辅助节点。

2)添加无人机基站集合节点作为一级节点。

每一个无人机基站集合节点代表一个无人机基站集合，每一个无人机基站集合由两个无人机基站构成，这两个无人机基站可以相同也可以不同。M个不同的无人机基站能构成

3)添加任务集合节点作为二级节点。

对于无人机基站集合SU

每一个任务集合节点代表一个任务集合，假设所有无人机基站对应的任务集合的总个数为P，那么模型中共有P个不同的任务集合构成集合LU＝{LU

4)添加任务节点作为三级节点。每一个任务节点表示L中的一个任务，共有N个任务节点。

(2)构建最小费用最大流模型的边

1)添加从源节点出发的边

源节点s与每个无人机基站集合节点之间都存在边。源节点s与无人机基站集合节点之间的边的容量均为N，费用均为0。

2)添加从无人机基站集合节点出发的边

每个无人机基站集合节点与其对应的任务集合节点之间都存在边，即无人机基站集合SU

3)添加从任务集合节点出发的边

每个任务集合节点p仅会与任务集合中包含的任务对应的任务节点间存在边，即一共有|LU

4)添加从任务节点出发的边

每个任务节点与终点节点t之间都存在边。任务节点与终点节点t之间边的容量均为1，费用均为0。

作为本发明的一种优选方案，步骤3包括：

(1)构建相应的最小费用最大流模型G＝(V,E,$,W)。

(2)初始化无人机U的初始停靠无人机基站为S

(3)将完成的任务数量建模为流量，基于最小费用最大流模型，获得最小费用最大流模型中费用最小的“起飞无人机基站-任务集合-降落无人机基站”组合的集合，具体步骤如下：

1)初始化可行流f为零流，此时可行流f的费用0。

2)初始化Cost

获得包含若干个“起飞无人机基站-任务集合-降落无人机基站”组合的可行流f

a)易知可行流f

b)选择剩余的流网络G

c)将增广路径p

3)通过循环对LS中“起飞无人机基站-任务集合-降落无人机基站”组合LS

d)获得一个“起飞无人机基站-任务集合-降落无人机基站”LS

e)如果LS

f)将可行流f中所有与LS

4)若有部分任务不在f中，则针对未被选择的任务L

作为本发明的一种优选方案，步骤4所述初始路径I的构成方法如下：

(1)判断步骤3得到的“起飞无人机基站-任务集合-降落无人机基站”组合中是否存在一个组合，它的起飞无人机基站或降落无人机基站中任意一个是无人机U的初始停靠无人机基站S

(2)将所有能够顺序执行“起飞无人机基站-任务集合-降落无人机基站”组合构建为一条初始路径，记为I＝{i

1)初始化初始路径I为空。

2)对于每一个被选中的“起飞无人机基站-任务集合-降落无人机基站”组合中的每个组合LS

若S

若S

若S

作为本发明的一种优选方案，步骤5所述将“候选起飞无人机基站-任务集合-降落无人机基站”组合c

候选“起飞无人机基站-任务集合-降落无人机基站”组合c

(1)插入初始路径I的开头。

用S

若S

若S

其中D(I∨

若S

其中

(2)插入初始路径I的结尾。

用S

若S

D(I∨

若S

若S

(3)插入初始路径I中两个相邻的“起飞无人机基站-任务集合-降落无人机基站”组合中间。

用S

若S

若S

若S

若S

有益效果：

提供了一种基于最小费用最大流的无人机任务分配方法。使无人机能够在有限的能源的前提下，在已知区域中提前规划无人机的飞行路径，从而有效减少无人机能源的消耗，较好的完成远距离任务，防止无人机因为能源不足而无法完成任务或无法回收的问题。拓展了无人机的任务距离，扩大了无人机的活动范围。

附图说明

下面结合附图和具体实施方式对本发明做更进一步的具体说明，本发明的上述和/或其他方面的优点将会变得更加清楚。

图1是将任务区域内的任务与无人机基站划分为若干个“无人机基站-任务集-无人机基站”集合使用的最小费用最大流模型。

图2是本发明实施例提供的一种基于最小费用最大流的无人机任务分配方法的流程示意图。

图3是将候选“起飞无人机基站-任务集合-降落无人机基站”组合插入初始路径时的第一种情况。

图4是将候选“起飞无人机基站-任务集合-降落无人机基站”组合插入初始路径时的第二种情况。

图5是将候选“起飞无人机基站-任务集合-降落无人机基站”组合插入初始路径时的第三种情况。

具体实施方式

下面详细描述本发明的实施方式，所述实施方式的示例在附图中示出。下面通过参考附图描述的实施方式是示例性的，仅用于解释本发明，而不能解释为对本发明的限制。

图1为将任务区域内的任务与无人机基站划分为若干个“无人机基站-任务集-无人机基站”集合使用的最小费用最大流模型。最小费用最大流模型构成的流网络是一个有向图G＝(V,E,$,W)，其中V表示图中的节点，E表示图中的边，$表示边的费用，W表示边的容量。有向图G中每条边都具有容量，流量和费用三个属性。构建最小费用最大流模型对应的流网络G＝(V,E,$,W)的具体步骤如下：

(1)构建系统模型

1)任务区域内有N个不同的任务目标构成集合L＝{L

2)任务区域内有M个不同的无人机基站构成集合S＝{S

3)任务区域内有一架准备执行任务的无人机U(为了简化，假设不考虑无人机起飞降落时以及飞行中受到自然因素影响的能耗，无人机的能耗能等价为无人机的飞行距离)，在能源充满的前提下，无人机U的最长飞行距离为

(1)构建最小费用最大流模型的节点

1)添加源节点s与终点节点t作为辅助节点。

2)添加无人机基站集合节点作为一级节点。

每一个无人机基站集合节点代表一个无人机基站集合，每一个无人机基站集合由两个无人机基站构成，这两个无人机基站可以相同也可以不同。M个不同的无人机基站能构成

3)添加任务集合节点作为二级节点。。

对于无人机基站集合SU

每一个任务集合节点代表一个任务集合，假设所有无人机基站对应的任务集合的总个数为P，那么模型中共有P个不同的任务集合构成集合LU＝{LU

4)添加任务节点作为三级节点。每一个任务节点表示L中的一个任务，共有N个任务节点。

(2)构建最小费用最大流模型的边

1)添加从源节点出发的边

源节点s与每个无人机基站集合节点之间都存在边。源节点s与无人机基站集合节点之间的边的容量均为N，费用均为0。

2)添加从无人机基站集合节点出发的边

每个无人机基站集合节点与其对应的任务集合节点之间都存在边，即无人机基站集合SU

3)添加从任务集合节点出发的边

每个任务集合节点p仅会与任务集合中包含的任务对应的任务节点间存在边，即一共有|LU

4)添加从任务节点出发的边

每个任务节点与终点节点t之间都存在边。任务节点与终点节点t之间边的容量均为1，费用均为0。

如图2所示，本发明提出一种基于最小费用最大流的无人机任务分配方法，其具体步骤如下：

(1)初始化无人机U的初始停靠无人机基站S

(2)构建相应的最小费用最大流模型。

(3)将完成的任务数量建模为流量，基于最小费用最大流模型，将任务区域内的任务与无人机基站划分为若干个“起飞无人机基站-任务集合-降落无人机基站”组合，具体步骤如下：

(1)构建相应的最小费用最大流模型G＝(V,E,$,W)。

(2)初始化无人机U的初始停靠无人机基站为S

(3)将完成的任务数量建模为流量，基于最小费用最大流模型，获得最小费用最大流模型中费用最小的“起飞无人机基站-任务集合-降落无人机基站”组合的集合，具体步骤如下：

1)初始化可行流f为零流，此时可行流f的费用0。

2)初始化Cost

获得包含若干个“起飞无人机基站-任务集合-降落无人机基站”组合的可行流f

a)易知可行流f

b)选择剩余的流网络G

c)将增广路径p

3)通过循环对LS中“起飞无人机基站-任务集合-降落无人机基站”组合LS

d)获得一个“起飞无人机基站-任务集合-降落无人机基站”LS

e)如果LS

f)将可行流f中所有与LS

4)若全部任务都在f中，则执行(4)；否则针对未被选择的任务L

(4)判断所有得到的“起飞无人机基站-任务集合-降落无人机基站”组合中是否存在一个组合，它的起飞无人机基站或降落无人机基站中任意一个是初始停靠无人机基站S

1)初始化初始路径I为空。

2)对于每一个被选中的“起飞无人机基站-任务集合-降落无人机基站”组合中的每个组合LS

若S

若S

若S

(5)若初始路径I包含(3)中所有得到“起飞无人机基站-任务集合-降落无人机基站”组合，则初始路径I就是无人机执行所有任务的最终路径F；否则将由(3)得到的未被初始路径I包含的“起飞无人机基站-任务集合-降落无人机基站”组合被记为候选“起飞无人机基站-任务集合-降落无人机基站”组合，构成集合CLS＝{c

图3，图4以及图5是将候选“起飞无人机基站-任务集合-降落无人机基站”组合c

1)插入初始路径I的开头。

插入位置如图3所示。

用S

若S

若S

其中D(I∨

若S

其中

2)插入初始路径I的结尾。

插入位置如图4所示。用S

若S

D(I∨

若S

若S

3)插入初始路径I中两个相邻的“起飞无人机基站-任务集合-降落无人机基站”组合中间。

插入位置如图5所示。用S

若S

若S

若S

若S

本发明提供了一种基于最小费用最大流的无人机任务分配方法，具体实现该技术方案的方法和途径很多，以上所述仅是本发明的具体实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。本实施例中未明确的各组成部分均可用现有技术加以实现。