本发明涉及无人集群复杂系统的协同任务分配技术，具体涉及一种基于形式化语言描述任务，并考虑复杂任务约束的无人集群任务最短时间决策方法及系统。
背景技术：
1、集群任务决策是一个复杂的系统问题，集群任务可以由各类异构的无人车，无人机，有人车等等组成。其中需要解决的关键技术主要有形式化处理任务要求，任务理解与拆解，复杂多约束下任务分配，以及任务执行动态自适应。目前国内外诸多专家学者对上述关键技术开展了大量理论研究。而任务理解与分配是其中的核心部分，因此这里主要对这两点进行分析：
2、形式化语言是通常具有自然语言的可理解性以及机器语言的准确性，常用于对任务的描述，常见的形式化语言有线性时序逻辑（linear temporal logic, ltl）等。目前相对成熟的形式化方法集群任务理解与分配方法有乘积法（productbased），采样法（sampling based），并行法（simultaneous based）。乘积法理论简单，逻辑完备，能处理小型集群的任务决策方法，但是，随着智能体数量增加，系统整体状态空间会指数爆炸使得最终无法计算；采样法在乘积法上进行了改进，能处理较多智能体的情况，但是最优性不一定有乘积法好；并行法能将任务拆分成一系列的并行部分，计算效率更快，但是不能处理需要协同的任务，即需要不同智能体同时执行的任务。目前现有的方法因为无法直接获取任务的时序关系而总是生成过大的状态空间，导致其无法处理大规模的集群协同任务。时序关系是指从形式化语言中获取一系列任务，判断他们执行的必要顺序以及冲突关系。目前最好的方法还只能判断几个任务序列之间是否能并行执行，还达不到单个任务的粒度。就此需要设计一种基于任务理解的形式化语言决策算法，在保证形式化语言的准确性的情况下，获取精确的任务时序关系，实现计算速度的数量级提升。
技术实现思路
1、本发明的目的是提供一种在形式化语言约束下的集群协同任务最小时间决策方法，用以解决具有异构多智能体的集群系统协同任务决策问题，可大幅度提高异构多智能体集群协同任务的计算效率。
2、本发明基于形式化方法，首先通过加入时序分析的方法，对自动机进行减枝，实现对状态空间的大幅度削减，从而保证算法的计算效率；其次利用具有任意时间（anytime）性质的分支定界法设计任务分配算法，将任务分配给异构的多智能体集群，并保证方案的可行性与最优性；最后通过针对环境不确定性的自适应机制，基于在线同步以及分布式沟通的同步协议以及计划自适应调整算法，严格保证任务执行的正确性。
3、本发明提供的技术方案如下：
4、一种基于形式化方法的集群协同任务最短时间决策方法，给定无人集群（多智能体系统）的协同任务，生成每个智能体的运动和动作序列，使得多智能体系统满足的任务要求花费的总时间值最小；包括如下步骤：
5、1）将原始协同任务分解为多个子任务（子任务序列）；包括：
6、11）将原始协同任务表示为非确定性自动机，再对自动机进行减枝处理。包括：
7、11a）首先根据线性时序逻辑ltl公式转换得到非确定性自动机（，简称nba）：，其中表示自动机中的状态，表示ltl公式的完成程度；为初始状态，表示ltl公式尚未开始被满足；是所有的原子命题，代表着智能体所有可执行的动作；是状态转移的边，对应智能体的动作；是可接受的状态，表示ltl公式已经被满足。能使得nba初始状态转移到可接受状态的动作序列，即能满足ltl公式。
8、11b）对自动机进行减枝处理；包括三个步骤：
9、11b1）移除不可执行的转移边，不可执行的转移关系指的是其要求的标签没有智能体能够产生；
10、11b2）移除无效的状态，无效状态指的是无法从初始状态到达的节点或者无法到达任何可以自循环重复到达可接受状态的节点；
11、11b3）移除可分解的转移边，可分解的转移边定义为：一个从到的可分解的，当且仅当有另外一个节点满足:且。
12、因此经过减枝之后最终只会保留不可分解的边，也就是无法拆分的最小的能推动整体任务发展的任务单元。经过减枝处理得到的自动机记为。
13、12）针对修剪后的自动机，设计一个任意时间的偏序分析算法，在给定的时间预算内生成至少找到一个子任务分解，并生成对应的含有最少偏序关系的偏序集（r-poset），同时在时间允许的情况下搜索更多的子任务分解和对应的偏序集。
14、偏序集表示为：，其中，是需要执行的子任务序列，都为偏序关系，表示子任务需要按照顺序关系执行，表示子任务不可同时执行。偏序关系中含有越多的元素代表子任务执行过程中有越多的时序约束，意味着任务并行的可能性越低，而导致执行效率很低。
15、包涵生成所有偏序集和对应的子任务序列的完整集的计算包含从初始状态集到接受状态集的所有简单路径的计算，计算成本很高。给定剪枝自动机，最坏情况下计算复杂度为o( q+ f)，其中q为自动机的状态数量，f为自动机的边数量。因此，对于实时应用程序，本发明设计一种可以随时截止的算法，被称为anytime算法，即任意时间的偏序分析算法，用于在给定的时间预算内生成至少一个有效的偏序集，同时在时间允许的情况下增加更多的偏序集，具体如下：
16、121）输入：修剪后的自动机；
17、122）生成已发现的接受词集合，偏序集和子任务序列的完整集；
18、123）从初始状态集合遍历状态：若当前时间超出时间预算，则跳出循环；从点开始在深度优先搜索直到找到一个可接受的词；
19、124）当深度优先搜索尚未结束：
20、若不在内，将加入中
21、初始化子任务序列
22、初始化严格的偏序集合，其中，被初始化为全序，即，总有或，
23、遍历每一对偏序关系：
24、核验去除该关系后，偏序集合所对应语言是否都可接受，其中表示所有的满足的子任务排列。
25、若接受则去除该偏序关系
26、若不接受则保留该偏序关系
27、将加入到中；
28、将当前偏序集合加入到完整集合中；
29、继续深度搜索；
30、125）输出：包涵所有搜索到的偏序集和对应的子任务序列的完整集合。
31、13）分解得到的子任务表示为二元数组：
32、
33、其中是子任务的序号，且子任务（系统的动作集）满足两个条件：(i),(ii)，其中。
34、2）设计一个基于分支定界法的任意时间的任务分配算法，将多个子任务分配给各个智能体，使得所有的偏序关系都被满足，且所有任务的完成时间最小化；包括：
35、21）输入：偏序集合，搜索时间预算；
36、22）初始化当前最优解和最优值，搜索的节点序列；
37、23）当没有超过时间预算时：
38、231）从序列中根据分支方法选取节点；
39、232）计算节点的下界；若下界小于最优解，计算节点的上界，更新最优解和最优值；对节点进行节点拓展，将子节点加入到序列中；
40、24）返回 最优解, 最优值；即输出：当前最优的任务序列，执行时长；
41、根据上述步骤，即可得到无人集群协同任务自适应后的分配方案。
42、上述基于分支定界法的任意时间的任务分配算法中，分支定界法的四个元素包括：节点拓展（扩展）、分支方法、节点的上界、节点的下界；分别定义如下：
43、①节点扩展
44、节点表示为：，其中是该节点分配给智能体的任务系列，为了保证在分配的过程中任务满足偏序关系，本发明中：i) 对于当前节点的任务分配而言，若()∈≤φ，则分配完任务之后才会对进行分配；ii) 对于的下一个扩展节点的任务分配而言，要求所分配任务的父任务（要求在之前开始执行的任务）在中都已分配完成。
45、②分支方法
46、分支方法决定了子节点的访问顺序。本发明中采用a*算法，因为其启发式函数与后文中定义的下界比较匹配，具体而言，子节点是以预估的所有任务完成时间为标准进行排序扩展的。此外，本发明定义了一个并行水平的概念作为子节点选取的指标，计算内容为：，其中是智能体完成节点分配给它的任务序列所需要的时间，取所有智能体完成时间的最大值即完成节点任务所需的时间，通过给定的每个任务的持续时间和所需智能体数量计算了节点分配的所有子任务的执行总时间，用所有子任务的执行总时间除以完成任务的时间得到并行水平。本发明选择值最高的子节点进行扩展。
47、③上界
48、由节点生成的所有解的上界可表示为：，其中是所有子任务的分配情况，它的结构与相同，是完成所有子任务需要的时间，记录了每个子任务的开始时间。上界算法将会获得一个可行解，并会和当前的最优可行解进行比对，若当前节点得到的上界和当前的最优的可行解相比更优，选取当前上界作为最优解。
49、④下界
50、从某个节点生成的所有解的任务完成时间的下界是通过两种对原始问题的放松得到的，一种是只考虑偏序约束而忽略智能体的能力，另一种是只考虑能力而忽略约束。若当前节点的下界值超过了最优解，则意味着我们无法从这个节点出发获取一更优的解，因此会将该节点从搜索中删去，不再进行节点拓展。
51、具体实施时，上述基于分支定界法的任意时间的任务分配算法可以在python语言中通过凸优化函数包cvxopt以及与之配套的求解器glpk_mi进行求解。二者可以在极短时间内获取初始可行解，并快速收敛到优化解中。较短时间获取，并且具有极高的可靠性。
52、本发明还提供了一种实现上述的基于形式化方法的集群协同任务最短时间决策方法的系统，包括：偏序分析模块、任务分配模块、在线适应模块。其中，偏序分析模块负责将输入的ltl公式转换为拟偏序集，以获取满足ltl公式所必要的子任务和子任务之间的时序关系；任务分配模块负责将偏序分析模块计算得到的拟偏序集结合多智能体集群的功能、分布，以及环境特征，利用分支定界法计算获取到一个满足拟偏序集，智能体特征的任务计划，并加以输出；在线适应模块负责在执行过程中处理环境中的不确定性，以保证任务计划的正确执行，并在出现智能体损毁的情况下重新规划任务计划。这三个模块互相协作，最终能引导智能体集群执行一系列动作，使得ltl公式被满足。
53、本发明的有益效果：
54、本发明提出了一种基于形式化方法的集群协同任务最小时间决策方法。首先通过对自动机进行减枝，大幅度减少了自动机中状态和边的数量，降低了后续计算的复杂度。其次提出了一个任意时间的偏序分析算法，能够在给定的时间预算内生成至少一个有效的偏序集，同时在时间允许的情况下增加更多的偏序集，且这些偏序集中的偏序关系经过放松，这意味着子任务的执行有更多并行的可能，提升了效率。接着，本发明提出了一个基于分支定界法的任意时间的任务分配算法，它能够在时间预算内不断迭代每个偏序集的最优任务分配方案。最后提出了一种基于在线同步以及分布式沟通的同步协议以及计划自适应调整算法来保证在任务执行过程中执行时间出现偏差或有智能体出现故障时系统能够自适应地去解决这些问题。这一方法可以保证无人集群协同任务的时间最小化以及任务的完成度，特别适用于动态环境、复杂任务情况下的任务规划。可以应用到如多导弹协同打击、多机器人协同运输、多无人机协同侦察等场景。
1.一种基于形式化方法的集群协同任务最短时间决策方法，其特征是，针对无人集群即多智能体系统的协同任务，通过加入时序分析的方法，将协同任务分解为多个子任务；基于分支定界法设计任务分配算法，将多个子任务分配给各个智能体，生成每个智能体的运动和动作序列，使得所有的偏序关系均满足且所有任务的完成时间最小；再通过针对环境不确定性的自适应机制，基于在线同步及分布式沟通同步协议，设计计划自适应调整算法，得到无人集群协同任务自适应后的任务分配方案；包括如下步骤：
2.如权利要求1所述基于形式化方法的集群协同任务最短时间决策方法，其特征是，步骤11）的过程包括：
3.如权利要求2所述基于形式化方法的集群协同任务最短时间决策方法，其特征是，步骤12）的任意时间的偏序分析算法中，将子任务分解的偏序集表示为：，其中， 均表示偏序关系；偏序关系中含有越多的元素代表子任务执行过程中有越多的时序约束，即表示任务并行的可能性越低。
4.如权利要求3所述基于形式化方法的集群协同任务最短时间决策方法，其特征是，步骤12）找到一个使得偏序集含有最少的偏序关系的子任务分解的方法的具体过程包括：
5.如权利要求3所述基于形式化方法的集群协同任务最短时间决策方法，其特征是，所述分支定界法中的四个元素包括：节点拓展、分支方法、节点的上界、节点的下界；其中：
6.如权利要求5所述基于形式化方法的集群协同任务最短时间决策方法，其特征是，
7.如权利要求6所述基于形式化方法的集群协同任务最短时间决策方法，其特征是，基于分支定界法的任意时间的任务分配算法具体是在python语言中通过凸优化函数包cvxopt和求解器glpk_mi进行求解。
8.一种采用权利要求1所述基于形式化方法的集群协同任务最短时间决策方法实现的系统，其特征是，包括：偏序分析模块、任务分配模块、在线适应模块；其中，
