多智能体探测器任务规划的分层异步时间约束处理方法

1.本发明涉及一种适用于多智能体探测器任务规划的分层异步时间约束处理方法，属于航空航天技术领域。

背景技术：

2.探测小天体对于研究太阳系的起源有着重要的意义。近些年来，nasa，jaxa和esa已经实施了许多小天体探测任务，探测形式也由飞越探测发展为就位探测、采样返回等多种形式。针对目前小天体着陆的两大主要难题：(1)小天体引力十分微弱且不规则，探测器很容易发生弹跳和逃逸，(2)是表面土壤性质不完全确知。地表特征复杂多样，多碎石、沟槽等，采用传统的刚性附着策略易造成探测器的翻滚、倾覆。因此有学者提出柔性连接的多节点探测器，在这一探测器系统中包含有多个节点，节点间具有柔性机构连接，通过柔性机构在着陆瞬间吸收探测器动能，以达到抑制着陆反弹，提高着陆稳定性的目的。
3.多节点探测器的每个节点均具备独立的计算能力，将每个节点看作一个智能体，考虑到小天体与地球间通信的长时延，为实现在小天体表面的自主稳定附着，多节点探测器需具备自主任务规划能力。在规划过程中大部分采用简单时间网络(stn)对时间变量及时间约束进行定量表示，并在此基础上进行时间约束处理，判断当前时间约束是否满足一致性要求。目前时间约束处理方法主要包括路径一致与弧一致两大类。路径一致方法最典型的是floyd-warshall算法，基于stn计算全网络最短路径，其时间复杂度为o(n3)，该方法约束检测数多，计算效率较低。因此bliek提出部分路径一致算法(ppc)，有效降低了约束检测数。δstp算法结合ppc及stn图的三角化，以存储资源为代价提高了计算效率，时间复杂度为o(t2)。p3c算法在三角化的stn上结合有向路径一致(ppc)强制执行部分路径一致，约束网络中每个三角形只需执行两次约束处理，进一步提高了时间约束一致性处理效率，其时间复杂度为o(t)。而弧一致方法通过约束传播收紧时间变量值域从而判断在当前约束下问题是否有解，主要方法包括ac-1到ac-7、ac-2000、ac-2001、acstp等。以上述时间约束处理方法为核心，在多智能体领域衍生出分布式处理方法及其变种，如dδdpc、dδppc、disacstp等算法。但在多智能体领域除了提高时间约束处理效率外，还需关注智能体内部隐私性和智能体间通信代价。以路径一致为基础的算法在计算过程中可能会额外增加新的约束，从而增加通信开销，甚至导致原本无需通信的智能体间产生通信，不利于智能体的隐私性。为解决该问题，基于弧一致的分布式算法有效避免了这一缺陷，但其在计算过程中未对约束传播进行判断，执行了许多无效约束检测，造成了计算资源及通信资源的浪费。而小天体多节点探测器计算资源有限，着陆任务实时性要求较高，因此在满足智能体隐私性的前提下，提高多节点探测器规划过程中时间约束处理效率，降低节点间通信信息数是一个复杂的问题。

技术实现要素：

4.本发明的主要目的是提供一种多智能体探测器任务规划的分层异步时间约束处
理方法，通过建立多节点探测器时间规划问题模型，对时间约束问题进行多智能体简单时间网络等效表达，对多智能体简单时间网络进行分层表示，求解异步处理的智能体计算顺序，进而在此顺序基础上基于弧一致算法对当前智能体时间约束网络进行处理，通过增加变量值域更新标志减少不必要的约束检测，进而能够提高约束检测效率，从而实现多节点探测器自主规划过程中复杂时间约束的快速处理，提高规划效率。
5.本发明的目的是通过下述技术方案实现的。
6.本发明公开的多智能体探测器任务规划的分层异步时间约束处理方法，首先建立多节点探测器时间规划问题模型，包括节点id、节点状态变量、初始状态、目标状态、可执行活动变量以及活动约束等。在进行时间约束处理前将活动时间变量及时间约束表示为多智能体简单时间网络mastn中的变量点与边，而后根据智能体间的共享变量关系定义上层智能体网络，根据该网络的智能体出度与智能体的共享变量数求解异步处理时的智能体计算顺序。在此顺序基础上基于弧一致算法对当前智能体时间约束网络进行处理，通过增加变量值域更新标志减少不必要的约束检测，求解活动时间变量是否存在值域，根据处理结果判断规划过程中时间约束是否一致。由于约束处理过程减少不必要的约束检测，进而能够提高约束检测效率，从而实现多节点探测器自主规划过程中复杂时间约束的快速处理，提高规划效率。
7.本发明公开的多智能体探测器任务规划的分层异步时间约束处理方法，包括如下步骤：
8.步骤一、建立多节点探测器时间规划问题模型，并将所述多节点探测器时间规划问题定义为六元组。所述多节点探测器时间规划问题模型包括节点id、节点状态变量、初始状态、目标状态、可执行活动时间变量和活动时间约束。
9.将多节点探测器时间规划问题定义为以下六元组
10.π＝[p,st,o,c,s0,g](1)
[0011]
其中，p＝{a1,...,am}表示探测器节点id集合，表示探测器m个节点的状态变量集合，表示探测器m个节点可执行的活动时间变量集合，对于任意节点的任意活动具有开始时间点结束时间点持续时长即表示任意两个活动间的时间约束关系，s0表示多节点探测器初始状态，g表示目标状态。
[0012]
步骤二、将步骤一中的活动时间变量、时间约束表示为多智能体简单时间网络，从而将时间约束处理问题转化为图的路径问题，以便于后续步骤三、四求解。所述活动时间变量具有变量值域。
[0013]
步骤2.1：对于单节点内部活动时间变量、时间约束建立单智能体简单时间网络stn。
[0014]
对于任意两个时间变量u,w，定义时间零点z，则其值域分别为i
zu
,i
zw
。若存在时间约束关系a≤w-u≤b，则约束表示为区间i
uw
＝[a,b]，若u,w属于同一活动，则i
uw
表示的是活动内部约束，即活动持续时长，若u,w属于不同活动，则i
uw
表示活动间约束。将单节点的活动时间变量及时间约束表示为stn中的变量点与边，即s＝＜v,d,c＞，v表示该节点所包含的
所有时间变量集合所述时间变量集合包括活动开始时间点、结束时间点和时间零点，d表示所述时间变量的值域集合，该值域集合包括所有变量点与时间零点间边的权重，c表示时间变量间的约束关系集合，该集合包括变量点间边的权重。
[0015]
步骤2.2：在步骤2.1得到智能体简单时间网络的基础上，考虑节点间的活动时间约束，建立多智能体简单时间网络mastn，从而将时间约束处理问题转化为图的路径问题，以便于后续步骤三、四求解。
[0016]
针对多智能体时间网络需考虑智能体的隐私性，智能体间仅交换共享信息，因此对stn中的变量及约束进行区分。对于智能体i的简单时间网络si＝＜vi,di,ci＞，若任意变量vi∈vi与其他智能体的变量间存在约束ci∈ci，则该变量称为共享变量，加入共享变量集合v
is
，若变量vi的所有约束均属于智能体i，则该变量称为私有变量，加入私有变量集合v
ip
。对于不属于智能体i，但与智能体i的变量存在约束的其他智能体变量称为外部变量，加入外部变量集合v
ix
，智能体i所包含的所有变量称为内部变量，加入内部变量集合v
il
，则智能体i的所有变量集合vi＝v
ix
∪v
il
＝v
ix
∪(v
is
∪v
ip
)。同理，若约束ci∈ci其中一个端点变量vi∈v
ix
，则加入外部约束集合若约束ci∈ci两个端点变量vi,vj∈v
il
，则加入内部约束集合合
[0017]
步骤三、对步骤二得到的多智能体简单时间网络进行智能体层抽象表示，根据该网络的智能体出度与智能体的共享变量数求解异步处理时的智能体计算顺序。求解异步处理的智能体分层计算顺序集合order，基于多智能体简单时间网络，通过智能体局部约束网络的异步计算，部分智能体能够使用已更新的外部变量值域进行求解，其内部变量值域削减更接近于最终值域，从而减少单个智能体约束检测数。
[0018]
步骤3.1：对步骤二得到的多智能体简单时间网络进行智能体层抽象表示，根据智能体间的约束关系建立上层智能体网络p＝＜a,e＞，a＝{1,2,...,n}表示智能体id集合，e＝{...,(i,j),...}表示智能体间的连接关系集合，(i,j)表示智能体i与j间存在约束。
[0019]
步骤3.2：根据步骤3.1得到的网络p计算所有智能体出度od，也即与智能体i存在约束的智能体个数。
[0020][0021]
其中，若(i,j)∈e，则e(i)(j)＝1，否则e(i)(j)＝0。
[0022]
步骤3.3：求解异步处理的智能体分层计算顺序集合order，将出度最高的智能体置于order第一层，并将其id从集合a中移除，而后将集合a中与第一层智能体存在约束关系的智能体置于order第二层，并将这些智能体的id从集合a中移除，下层以此类推，直至集合a为空集，由此获得异步处理的智能体分层计算顺序集合order。以便步骤四通过智能体局部约束网络的异步计算，部分智能体能够使用已更新的外部变量值域进行求解，其内部变量值域削减更接近于最终值域，从而减少单个智能体约束检测数。
[0023]
步骤四、根据步骤三得到的顺序集合order，基于弧一致算法对智能体i时间约束网络进行约束处理，通过增加变量值域更新标志减少不必要的约束检测，进而由步骤二的变量值域削减求解活动时间变量是否存在值域，根据约束处理结果判断规划过程中时间约束是否一致。
[0024]
步骤4.1：根据步骤三获得的集合order进行智能体间的信息通信。对智能体i所有变量vi∈v
il
添加更新标记signv＝true，只有当共享变量更新标记signv＝true时才发送该变量值域。
[0025]
步骤4.1.1：若智能体i处于order第一层，则将共享变量的值域发送到本层的邻居智能体，接收本层及下层邻居智能体发送的外部变量值域并添加至当前时间网络中。而后执行步骤4.2，将更新后的变量值域发送至下层智能体。
[0026]
步骤4.1.2：若智能体i不处于order第一层，则将共享变量的值域发送到本层及上层的邻居智能体，等待上层发送的更新后变量值域，而后执行步骤4.3。
[0027]
步骤4.2：对于所有变量ri∈v
ix
，记录其他智能体发送的变量值域i
zr
，并与上轮迭代接收的该变量值域i
′
zr
对比，若i
′
zr
＝i
zr
，则更新标记signr＝false，反之不进行操作。对于智能体i的mastn建立空列表qi。
[0028]
步骤4.3：通过约束传播对时间变量的可行值域进行削减。
[0029]
步骤4.3.1：选择未计算值域的变量ui∈v
il
，将其值域i
zu
赋值给i
′
zu
。
[0030]
步骤4.3.2：对于变量wi∈vi，若ui和wi间存在约束，且signw＝true，则计算符号表示对两个区间的端点分别进行求和。例：i
zw
＝[a,b]，i
wu
＝[c,d]，则而后将该结果与i
zu
求交集，直至所有变量wi均遍历。若交集为空，则说明当前无可行解，结束时间约束处理过程，返回约束不一致的结论。
[0031]
步骤4.3.3：将上一步更新后的值域i
zu
与i
′
zu
进行比较，若i
′
zu
＝i
zu
，则更新标记signv＝false，并将变量ui加入列表qi，若i
′
zu
≠i
zu
，则说明变量值域被更新，若变量ui在列表qi中，则将变量ui从列表qi中移除，否则不进行操作。
[0032]
步骤4.3.4：返回步骤4.3.1，直至所有变量ui∈v
il
均遍历。
[0033]
步骤4.4：当本轮所有智能体均完成约束处理，计算每个智能体集合v
il
与列表qi中的变量数，若所有智能体均满足v
il
和qi中的变量数相等，则计算完成，返回一致性网络，若二者不等，则返回步骤4.3执行新一轮迭代。
[0034]
还包括步骤五：通过步骤一至步骤四的约束处理减少多节点探测器自主规划过程中不必要的约束检测，从而实现多节点探测器自主规划过程中复杂时间约束的快速处理，提高规划效率。
[0035]
有益效果：
[0036]
1、本发明公开的适用于多智能体探测器任务规划的分层异步时间约束处理方法，通过建立多节点探测器时间规划问题模型，包括节点id、初始状态、目标状态、可执行活动变量以及活动约束等。在进行时间约束处理前将活动时间变量及时间约束表示为多智能体简单时间网络mastn中的变量点与边，而后根据智能体间的共享变量关系定义上层智能体网络，根据该网络的智能体出度求解异步处理时的智能体计算顺序。进而在此顺序基础上基于弧一致算法对当前智能体时间约束网络进行处理，求解活动时间变量是否存在值域，根据处理结果判断规划过程中时间约束是否一致。从而实现多节点探测器自主规划过程中复杂时间约束的快速处理，提高规划效率。
[0037]
2、本发明公开的适用于多智能体探测器任务规划的分层异步时间约束处理方法，基于多智能体简单时间网络，通过智能体局部约束网的异步计算，部分智能体可以使用已更新的外部变量值域进行求解，其内部变量值域削减更接近于最终结果，由于只有当变量
值域发生改变才会将信息发送至其他智能体，因此该方法减少智能体间的通信信息数，能够有效的解决现有分布式弧一致算法通信资源浪费的问题。
[0038]
3、本发明公开的适用于多智能体探测器任务规划的分层异步时间约束处理方法，对步骤二建立的多智能体简单时间网络中的时间变量添加值域更新标记，约束处理过程中根据更新标记的true和false值判断是否对该变量进行处理，对于上轮迭代未更新的变量值域不做计算，减少不必要的约束检测，有效节省多节点探测器有限的计算资源，提高约束处理效率。
附图说明
[0039]
图1是多智能体探测器任务规划的分层异步时间约束处理方法流程图
[0040]
图2是单智能体简单时间网络示意图。
[0041]
图3是多智能体简单时间网络示意图。
[0042]
图4是本发明所采用的实施例约束关系图。
具体实施方式
[0043]
为了更好的说明本发明的目的和优点，下面结合附图和实施例对发明内容做进一步说明。
[0044]
为了验证方法的可行性，如图4所示，选择三节点探测器为例，采用本发明的方法对规划过程中的时间约束进行一致性判断，实现时间约束分层异步快速处理，提高规划效率。
[0045]
如图4所示，本实施例公开的适用于多智能体探测器任务规划的分层异步时间约束处理方法，具体实现步骤如下：
[0046]
步骤一、建立多节点探测器时间规划问题模型，并将所述多节点探测器时间规划问题定义为六元组。所述多节点探测器时间规划问题模型包括节点id、节点状态变量、初始状态、目标状态、可执行活动时间变量和活动时间约束。
[0047]
将三节点探测器时间规划问题定义为以下六元组
[0048]
π＝[p,st,o,c,s0,g](3)
[0049]
其中，p＝{1,2,3}表示探测器节点id集合，表示探测器三个节点的状态变量集合，表示探测器三个节点可执行的活动变量集合，对于节点2的活动具有开始时间点as，结束时间点ae，持续时长da＝[1,1]，即表示活动1与活动2间的时间约束关系，s0表示多节点探测器初始状态，g表示目标状态。
[0050]
步骤二、将步骤一中的活动时间变量、时间约束表示为多智能体简单时间网络，从而将时间约束处理问题转化为图的路径问题，以便于后续步骤三、四求解。所述活动时间变量具有变量值域。
[0051]
步骤2.1：对于单节点内部活动时间变量、时间约束建立单智能体简单时间网络stn。
[0052]
对于两个时间变量as,ae，定义时间零点z，则其值域分别为i
zas
,i
zae
。存在时间约束关系1≤a
e-as≤1，则约束表示为区间i
asbs
＝[1,1]，as,ae属于同一活动，因此i
asbs
表示的是活动内部约束，即活动持续时长。对于变量as,bs，属于不同活动，则i
asbs
＝[1,∞]表示活动间约束。将单节点的活动时间变量及时间约束表示为stn中的变量点与边(如图2)，即s＝＜v,d,c＞，v表示该节点所包含的所有时间变量集合所述时间变量集合包括活动开始时间点、结束时间点和时间零点，d表示所述时间变量的值域集合，该值域集合包括所有变量点与时间零点间边的权重，c表示时间变量间的约束关系集合，该集合包括变量点间边的权重。
[0053]
步骤2.2：在步骤2.1得到智能体简单时间网络的基础上，考虑节点间的活动时间约束，建立多智能体简单时间网络mastn，从而将时间约束处理问题转化为图的路径问题，以便于后续步骤三、四求解。
[0054]
针对多智能体时间网络需考虑智能体的隐私性，智能体间仅交换共享信息，因此对stn中的变量及约束进行区分(如图3)。以智能体2为例，对于智能体2的简单时间网络s2＝＜v2,d2,c2＞，变量as∈v2与智能体3的变量fs∈v3间存在约束[0,0]，则变量as称为共享变量，加入共享变量集合变量ae的所有约束均属于智能体2，则该变量称为私有变量，加入私有变量集合对于不属于智能体2，但与智能体2的变量存在约束的其他智能体变量称为外部变量(如变量fs)，加入外部变量集合智能体2所包含的所有变量称为内部变量，加入内部变量集合则智能体2的所有变量集合同理，约束c
asfs
∈c2其中一个端点变量则加入外部约束集合约束c
asae
∈c2，两个端点变量则加入内部约束集合则加入内部约束集合
[0055]
本发明所采用的实施例时间约束变量和时间约束见表1。
[0056]
表1实施例时间约束变量和时间约束
[0057][0058][0059]
步骤三、对步骤二得到的多智能体简单时间网络进行智能体层抽象表示，根据该网络的智能体出度与智能体的共享变量数求解异步处理时的智能体计算顺序。求解异步处理的智能体分层计算顺序集合order，基于多智能体简单时间网络，通过智能体局部约束网络的异步计算，部分智能体能够使用已更新的外部变量值域进行求解，其内部变量值域削减更接近于最终值域，从而减少单个智能体约束检测数。
[0060]
步骤3.1：对步骤二得到的多智能体简单时间网络进行智能体层抽象表示，根据智
能体间的约束关系建立上层智能体网络p＝＜a,e＞，a＝{1,2,3}表示智能体id集合，e＝{(1,2),(2,1),(2,3),(3,2)}表示智能体间的连接关系集合。
[0061]
步骤3.2：根据网络p计算所有智能体出度od，也即与智能体i存在约束的智能体个数。
[0062][0063]
其中，若(i,j)∈e，则e(i)(j)＝1，否则e(i)(j)＝0。
[0064]
根据集合e，智能体1，2，3的出度分别为1，2，1。
[0065]
步骤3.3：求解异步处理的智能体分层计算顺序集合order，将出度最高的智能体2置于order第一层，并将其id从集合a中移除，而后将集合a中与第一层智能体存在约束关系的智能体1和智能体3置于order第二层，并将这些智能体的id从集合a中移除，此时集合a为空集，由此获得异步处理的智能体分层计算顺序集合order。以便步骤四通过智能体局部约束网络的异步计算，部分智能体能够使用已更新的外部变量值域进行求解，其内部变量值域削减更接近于最终值域，从而减少单个智能体约束检测数。
[0066]
步骤四、根据步骤三得到的顺序集合order，基于弧一致算法对智能体i时间约束网络进行约束处理，通过增加变量值域更新标志减少不必要的约束检测，进而由步骤二的变量值域削减求解活动时间变量是否存在值域，根据约束处理结果判断规划过程中时间约束是否一致。
[0067]
步骤4.1：根据步骤三获得的集合order进行智能体间的信息通信。对智能体i所有变量vi∈v
il
添加更新标记signv＝true，只有当共享变量更新标记signv＝true时才发送该变量值域。
[0068]
步骤4.1.1：智能体2处于order第一层，则将共享变量的值域发送到本层的邻居智能体，由于本层无邻居智能体，因此不进行发送，接收下层智能体1和智能体3发送的外部变量值域i
zxe
及i
zfs
并添加至当前时间网络中。而后执行步骤4.3，将更新后的变量值域发送至下层智能体。
[0069]
步骤4.1.2：智能体1和智能体3处于order第二层，在本层均无邻居智能体，因此分别将共享变量xe及fs的值域发送到上层智能体1，等待上层发送的更新后变量值域i
zas
及i
zbs
，而后执行步骤4.2。
[0070]
步骤4.2：对于智能体i的所有变量ri∈v
ix
，记录其他智能体发送的变量值域i
zr
，并与上轮迭代接收的该变量值域i
′
ze
对比，若i
′
ze
＝i
ze
，则更新标记signe＝false，反之不进行操作。对于智能体i的mastn建立空列表qi。
[0071]
步骤4.3：通过约束传播对时间变量的可行值域进行削减。该步骤以智能体2为例。
[0072]
步骤4.3.1：选择未计算值域的变量此处选择as，将其值域i
zas
＝[8,11]赋值给i
′
zas
。
[0073]
步骤4.3.2：对于变量wi∈vi，若as和wi间存在约束，且sign
ae
＝true，则计算符号表示对两个区间的端点分别进行求和。例：i
zae
＝[8,12]，i
aeas
＝[-1,-1]，则而后将该结果与i
zas
求交集，直至所有变量wi均遍历，计算交集后的值域更新为i
zas
＝[8,9.5]。
[0074]
步骤4.3.3：将上一步更新后的值域i
zas
与i
′
zas
进行比较，若i
′
zas
＝i
zas
，则更新标记sign
as
＝false，并将变量as加入列表q2，若i
′
zas
≠i
zas
，则说明变量值域被更新，若变量as在列表q2中，则将变量as从列表q2中移除，否则不进行操作。
[0075]
显然i
′
zas
≠i
zas
，此时列表q2中不包含变量as，因此不进行操作。
[0076]
步骤4.3.4：返回步骤4.3.1，直至所有变量均遍历。
[0077]
步骤4.4：当本轮所有智能体均完成约束处理，计算每个智能体集合v
il
与列表qi中的变量数，若所有智能体均满足v
il
和qi中的变量数相等，则计算完成，返回一致性网络，若二者不等，则返回步骤4.3执行新一轮迭代。计算完成后各变量的值域见表2。
[0078]
表2时间变量值域计算结果
[0079][0080][0081]
还包括步骤五：通过步骤一至步骤四的约束处理减少多节点探测器自主规划过程中不必要的约束检测，从而实现多节点探测器自主规划过程中复杂时间约束的快速处理，提高规划效率。
[0082]
根据上述步骤，对于多智能体规划过程中的时间约束网络，采取分层异步约束一致性判断方法，部分智能体可以使用已更新的外部变量值域进行求解，其变量值域相较于同步方法更接近于最终结果，并通过为变量增加更新标志的方法剔除无需重复计算的约束，减少单个智能体的约束检测数，降低智能体间的通信信息数，有效实现了多节点探测器规划过程中时间约束一致性的快速判断，提高了规划速度。
[0083]
本发明方法下，对于所采用实施例进行多智能体分层异步约束处理后，约束处理数、约束处理时间及通信信息数见表3，其中，进行一次运算，记一次约束处理，智能体i向智能体j发送一个变量的值域记两条通信信息数。
[0084]
表3约束处理数、约束处理时间及通信信息数
[0085]
方法同步计算分层异步计算约束处理数7242约束处理时间107.3ms98.9ms通信信息数24条14条
[0086]
由表中数据可知，相较于基于弧一致的分布式同步计算方法，本发明提出的分层异步弧一致时间约束处理方法减少约束处理数量，提高约束处理效率，降低智能体间的通信信息数，能够有效加快规划速度。
[0087]
以上所述的具体描述，对发明的目的、技术方案和有益效果进行进一步详细说明，所应理解的是，以上所述仅为本发明的具体实施例而已，并不用于限定本发明的保护范围，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

技术特征：

1.多智能体探测器任务规划的分层异步时间约束处理方法，其特征在于：包括如下步骤，步骤一、建立多节点探测器时间规划问题模型，并将所述多节点探测器时间规划问题定义为六元组；所述多节点探测器时间规划问题模型包括节点id、节点状态变量、初始状态、目标状态、可执行活动时间变量和活动时间约束；步骤二、将步骤一中的活动时间变量、时间约束表示为多智能体简单时间网络，从而将时间约束处理问题转化为图的路径问题，以便于后续步骤三、四求解；所述活动时间变量具有变量值域；步骤三、对步骤二得到的多智能体简单时间网络进行智能体层抽象表示，根据该网络的智能体出度与智能体的共享变量数求解异步处理时的智能体计算顺序；求解异步处理的智能体分层计算顺序集合order，基于多智能体简单时间网络，通过智能体局部约束网络的异步计算，部分智能体能够使用已更新的外部变量值域进行求解，其内部变量值域削减更接近于最终值域，从而减少单个智能体约束检测数；步骤四、根据步骤三得到的顺序集合order，基于弧一致算法对智能体i时间约束网络进行约束处理，通过增加变量值域更新标志减少不必要的约束检测，进而由步骤二的变量值域削减求解活动时间变量是否存在值域，根据约束处理结果判断规划过程中时间约束是否一致。2.如权利要求1所述的多智能体探测器任务规划的分层异步时间约束处理方法，其特征在于：还包括步骤五，通过步骤一至步骤四的约束处理减少多节点探测器自主规划过程中不必要的约束检测，从而实现多节点探测器自主规划过程中复杂时间约束的快速处理，提高规划效率。3.如权利要求2所述的多智能体探测器任务规划的分层异步时间约束处理方法，其特征在于：步骤一实现方法为，将多节点探测器时间规划问题定义为以下六元组π＝[p,st,o,c,s0,g](1)其中，p＝{a1,...,a
m
}表示探测器节点id集合，表示探测器m个节点的状态变量集合，表示探测器m个节点可执行的活动时间变量集合，对于任意节点的任意活动具有开始时间点结束时间点持续时长即表示任意两个活动间的时间约束关系，s0表示多节点探测器初始状态，g表示目标状态。4.如权利要求3所述的多智能体探测器任务规划的分层异步时间约束处理方法，其特征在于：步骤二实现方法为，步骤2.1：对于单节点内部活动时间变量、时间约束建立单智能体简单时间网络stn；对于任意两个时间变量u,w，定义时间零点z，则其值域分别为i
zu
,i
zw
；若存在时间约束关系a≤w-u≤b，则约束表示为区间i
uw
＝[a,b]，若u,w属于同一活动，则i
uw
表示的是活动内部约束，即活动持续时长，若u,w属于不同活动，则i
uw
表示活动间约束；将单节点的活动时间变量及时间约束表示为stn中的变量点与边，即s＝＜v,d,c＞，v表示该节点所包含的所有
时间变量集合所述时间变量集合包括活动开始时间点、结束时间点和时间零点，d表示所述时间变量的值域集合，该值域集合包括所有变量点与时间零点间边的权重，c表示时间变量间的约束关系集合，该集合包括变量点间边的权重；步骤2.2：在步骤2.1得到智能体简单时间网络的基础上，考虑节点间的活动时间约束，建立多智能体简单时间网络mastn，从而将时间约束处理问题转化为图的路径问题，以便于后续步骤三、四求解；针对多智能体时间网络需考虑智能体的隐私性，智能体间仅交换共享信息，因此对stn中的变量及约束进行区分；对于智能体i的简单时间网络s
i
＝＜v
i
,d
i
,c
i
＞，若任意变量v
i
∈v
i
与其他智能体的变量间存在约束c
i
∈c
i
，则该变量称为共享变量，加入共享变量集合v
is
，若变量v
i
的所有约束均属于智能体i，则该变量称为私有变量，加入私有变量集合v
ip
；对于不属于智能体i，但与智能体i的变量存在约束的其他智能体变量称为外部变量，加入外部变量集合v
ix
，智能体i所包含的所有变量称为内部变量，加入内部变量集合v
il
，则智能体i的所有变量集合v
i
＝v
ix
∪v
il
＝v
ix
∪(v
is
∪v
ip
)；同理，若约束c
i
∈c
i
其中一个端点变量v
i
∈v
ix
，则加入外部约束集合若约束c
i
∈c
i
两个端点变量v
i
,v
j
∈v
il
，则加入内部约束集合则加入内部约束集合5.如权利要求4所述的多智能体探测器任务规划的分层异步时间约束处理方法，其特征在于：步骤三实现方法为，步骤3.1：对步骤二得到的多智能体简单时间网络进行智能体层抽象表示，根据智能体间的约束关系建立上层智能体网络p＝＜a,e＞，a＝{1,2,...,n}表示智能体id集合，e＝{...,(i,j),...}表示智能体间的连接关系集合，(i,j)表示智能体i与j间存在约束；步骤3.2：根据步骤3.1得到的网络p计算所有智能体出度od，也即与智能体i存在约束的智能体个数；其中，若(i,j)∈e，则e(i)(j)＝1，否则e(i)(j)＝0；步骤3.3：求解异步处理的智能体分层计算顺序集合order，将出度最高的智能体置于order第一层，并将其id从集合a中移除，而后将集合a中与第一层智能体存在约束关系的智能体置于order第二层，并将这些智能体的id从集合a中移除，下层以此类推，直至集合a为空集，由此获得异步处理的智能体分层计算顺序集合order；以便步骤四通过智能体局部约束网络的异步计算，部分智能体能够使用已更新的外部变量值域进行求解，其内部变量值域削减更接近于最终值域，从而减少单个智能体约束检测数。6.如权利要求5所述的多智能体探测器任务规划的分层异步时间约束处理方法，其特征在于：步骤四实现方法为，步骤4.1：根据步骤三获得的集合order进行智能体间的信息通信；对智能体i所有变量v
i
∈v
il
添加更新标记sign
v
＝true，只有当共享变量更新标记sign
v
＝true时才发送该变量值域；步骤4.1.1：若智能体i处于order第一层，则将共享变量的值域发送到本层的邻居智能体，接收本层及下层邻居智能体发送的外部变量值域并添加至当前时间网络中；而后执行
步骤4.2，将更新后的变量值域发送至下层智能体；步骤4.1.2：若智能体i不处于order第一层，则将共享变量的值域发送到本层及上层的邻居智能体，等待上层发送的更新后变量值域，而后执行步骤4.3；步骤4.2：对于所有变量r
i
∈v
ix
，记录其他智能体发送的变量值域i
zr
，并与上轮迭代接收的该变量值域i
′
zr
对比，若i
′
zr
＝i
zr
，则更新标记sign
r
＝false，反之不进行操作；对于智能体i的mastn建立空列表q
i
；步骤4.3：通过约束传播对时间变量的可行值域进行削减；步骤4.3.1：选择未计算值域的变量u
i
∈v
il
，将其值域i
zu
赋值给i
′
zu
；步骤4.3.2：对于变量w
i
∈v
i
，若u
i
和w
i
间存在约束，且sign
w
＝true，则计算符号表示对两个区间的端点分别进行求和；例：i
zw
＝[a,b]，i
wu
＝[c,d]，则而后将该结果与i
zu
求交集，直至所有变量w
i
均遍历；若交集为空，则说明当前无可行解，结束时间约束处理过程，返回约束不一致的结论；步骤4.3.3：将上一步更新后的值域i
zu
与i
′
zu
进行比较，若i
′
zu
＝i
zu
，则更新标记sign
v
＝false，并将变量u
i
加入列表q
i
，若i
′
zu
≠i
zu
，则说明变量值域被更新，若变量u
i
在列表q
i
中，则将变量u
i
从列表q
i
中移除，否则不进行操作；步骤4.3.4：返回步骤4.3.1，直至所有变量u
i
∈v
il
均遍历；步骤4.4：当本轮所有智能体均完成约束处理，计算每个智能体集合v
il
与列表q
i
中的变量数，若所有智能体均满足v
il
和q
i
中的变量数相等，则返回一致性网络，若二者不等，则返回步骤4.3执行新一轮迭代。

技术总结

本发明公开的多智能体探测器任务规划的分层异步时间约束处理方法，属于航空航天技术领域。本发明实现方法为：建立多节点探测器时间规划问题模型，对时间约束问题进行多智能体简单时间网络等效表达，对多智能体简单时间网络进行分层表示，求解异步处理的智能体计算顺序；根据智能体计算顺序，基于弧一致算法对当前智能体时间约束网络进行约束处理，从而判断当前规划是否满足时间约束一致性。通过本发明实现多节点探测器分层异步弧一致时间约束处理，通过增加变量值域更新标志减少不必要的约束检测，能够减少单个智能体约束检测数，提高约束检测效率，从而实现多节点探测器自主规划过程中复杂时间约束的快速处理，提高多智能体探测器任务规划效率。探测器任务规划效率。探测器任务规划效率。