本发明涉及一种航天器任务规划修复的弧一致时间约束松弛处理方法，属于航空航天。
背景技术：
1、由于航天器所处环境存在动态性、不确定性和不可控性，在遇到突发事件时继续执行原有任务规划结果可能无法达成目标。此时，通过地面遥测控制的方式已经很难满足任务的实时性和安全性要求。例如火星探路者号就由于未考虑到实际执行时的环境影响，任务规划结果执行失败。因此，为了增强航天器自主能力、提高航天任务回报率，需要将规划与执行结合在一起，使航天器具备自主规划修复的能力，智能处理规划结果执行失败的问题。
2、航天器规划修复是指在任务规划结果执行失败时，对已有规划结果做预定修改，例如活动时间约束收紧和松弛、活动添加和删除等，从而得以继续执行任务的一项技术。其核心之一在于对已有规划结果的可执行活动间的时间约束进行表达，并在规划修复过程中对调整的活动时间约束进行推理，判断是否满足时间约束一致性要求。现有研究大部分基于简单时间网络stn对时间变量及时间约束进行定量表示和推理，例如“深空1号”探测器搭载的远程智能体规划系统及nasa开发的europa规划调度平台。目前时间约束推理方法主要包括以p3c方法为代表的路径一致和以acstp为代表的弧一致两大类。其中，弧一致在约束推理过程中不改变原活动间约束的权值，且推理效率更高，因此更适合航天器规划修复领域。
3、但在规划修复过程中，每调整一个活动就需要对当前网络所有时间变量进行一次遍历计算，随着约束的增加，时间约束的计算量会急剧上升，从而影响到规划修复效率。针对这一问题，有学者提出了时间约束网络增量式维护方法，如：增量部分路径一致、增量弧一致一致等。然而，增量式方法仅能处理时间约束收紧和添加的情况，在实际的规划修复过程中，时间约束也可能会松弛甚至删除(松弛至[-∞，+∞])，此时若对当前网络重新进行一次遍历计算，会耗费大量时间，影响规划修复的效率，不满足航天任务的实时性和安全性。
技术实现思路
1、针对现有的航天器任务规划修复的时间约束推理方法对于约束松弛处理慢的问题，本发明的目的是提供一种航天器任务规划修复的弧一致时间约束松弛处理方法，该方法能够快速处理航天器规划修复过程中的时间约束松弛和删除情况，基于弧一致方法对时间约束网络进行减量式约束推理，从而快速扩展变量值域，减少了时间约束推理次数，进而提高航天器自主规划修复效率，保证航天器在轨自主运行的安全性。
2、本发明的目的是通过下述技术方案实现的：
3、本发明公开的航天器任务规划修复的弧一致时间约束松弛处理方法，建立航天器时间规划修复问题模型，包括航天器状态、系统可执行活动时间变量、活动的时间约束、执行失败后的航天器状态和修复目标状态。将模型中活动时间变量及时间约束表示为简单时间网络stn中的变量点与边，构建原始时间网络。由原始时间网络计算得到最小时间网络，在此过程中保存造成每个变量值域上下界收紧的邻居节点集合，构建变量值域支持列表。在网络中松弛规划修复过程中的时间约束时，根据约束对变量值域上下界的影响，在变量值域支持列表中选取有影响的邻居节点变量进行推理，从而限制约束松弛对变量值域的扩展范围，并通过判断变量值域扩展与否来限制约束传播，只对扩展后的变量邻居节点进行约束传播，减少时间约束推理次数，提高航天器任务规划修复效率，提高航天任务的安全性。
4、本发明公开的航天器任务规划修复的弧一致时间约束松弛处理方法，包括如下步骤：
5、步骤一、建立航天器时间规划修复问题模型，规划修复过程基于航天器时间规划修复问题模型，在规划执行失败时对已有规划结果做预定修改，使航天器继续执行任务。所述航天器时间规划修复问题模型包括航天器状态、可执行活动时间变量、活动的时间约束、执行失败后的航天器状态和修复目标状态。
6、时间规划修复问题定义为五元组：∑＝(s,v,c,sf,sg)；其中，s表示航天器状态集合；v表示航天器可执行的活动时间变量集合，对于航天器的任意活动vi具有开始时间点si，结束时间点ei，持续时长di，即vi＝{si,ei,di}；c为活动的时间约束集合；sf表示规划执行失败后的航天器状态，也是规划修复的初始状态；sg表示规划修复的目标状态。规划修复过程即为由初始状态开始，通过搜索和推理，对已有规划结果做预定修改，所述预定修改包括：活动时间约束收紧和松弛、活动添加和删除，使航天器从失败中恢复，从而得以继续执行任务。
7、步骤二、对步骤一中规划修复问题的可执行活动时间变量和时间约束分别表示为简单时间网络stn中的顶点与边，构建原始时间网络。
8、对于航天器任务规划修复来说，每个活动x包括两个时间点变量：xs表示活动开始时间点变量；xe表示活动结束时间点变量。设置参考时间零点为z后，一共存在三种约束：对于可执行时间值域为[a,b]的时间点变量xs，即a<xs-z<b，xs的自身值域约束表示为izs＝[a,b]；对于两个时间点变量之间的活动约束，xs与xe所表示的活动持续时间约束c<xe-xs<d，表示为ixexs＝[c,d]，且ixexs与ixsxe表示的是同一个约束，满足ixsxe＝ixexs1＝[-d,-c]；同理，对于不同活动之间的约束，e<ys-xe<f，表示为iysxe＝[e,f]。
9、将规划修复问题的可执行活动时间变量及时间约束分别表示为简单时间网络stn中的顶点与边，构建原始时间网络g＝＜v,e＞。其中，v表示航天器可执行时间变量集合，包括步骤一中规划修复的初始状态sf和目标状态sg对应的每个活动的开始时间点和结束时间点，并加入参考时间零点z；e表示变量间时间约束关系的边集，包括活动变量的值域约束、活动间约束、活动内部约束，约束数值表示为每条边的权重。
10、步骤三、由原始时间网络g计算得到最小时间网络，在此过程中保存造成每个变量值域上下界收紧的邻居节点集合，构建变量值域支持列表。
11、步骤3.1：取原始时间网络g中的一个变量i∈v，若i与其它变量j∈v之间存在约束iij∈c，则称j为i的邻居变量，变量i的邻居变量集合为ne(i)。
12、步骤3.2：取变量i的一个邻居变量j∈ne(i)，计算在j影响下的变量i的新值域其中，符号表示对两个区间的端点分别进行求和，izi表示变量i的原值域，izj表示变量j的值域，iji表示变量i与变量j之间的约束。
13、步骤3.3：若izi'相比于izi上界缩小，则将变量j加入变量i的上界支持列表spupp(i)中；若izi'相比于izi下界增大，则将变量j加入变量i的下界支持列表splow(i)中；若izi'相比于izi上界缩小且下界增大，则将变量j同时加入变量i的上界支持列表spupp(i)和下界支持列表splow(i)中。
14、步骤3.4：重复执行步骤3.2至步骤3.3，直到变量i的邻居变量集ne(i)中所有变量对变量i的影响均计算完成后，取所有新值域的交集即为最小时间网络中变量i的值域。
15、步骤3.5：重复执行步骤3.1至步骤3.4，直到原始时间约束网络g中的所有变量i∈v的新值域均计算完成，此时即得到最小时间网络g’。
16、步骤四、规划修复过程中选择松弛约束{u，v}，根据约束对变量值域上下界的影响，在变量值域支持列表中选取有影响的邻居节点变量进行推理，并创建变量值域更新列表up，通过判断值域扩展与否来限制约束传播，只对扩展后的变量邻居节点进行约束传播，减少时间约束推理次数。
17、步骤4.1：计算松弛约束{u，v}后变量u扩展后的新值域。
18、在最小时间网络g’中，记变量u的值域为izu＝[x1,y1]，变量v的值域为izv＝[x2,y2]，约束{u，v}松弛前为iuv＝[x3,y3]，松弛后为iuv'＝[x3',y3']，则ivu＝[-y3,-x3]，ivu'＝[-y4,-x4]。izv与松弛前的约束ivu进行推理的结果为izv与松弛后的约束ivu'推理结果为izu与的关系分为三种情况：
19、若x1＝x2-y3且y1<y2-x3，执行步骤4.1.1；
20、若x1>x2-y3且y1＝y2-x3，执行步骤4.1.2；
21、若x1＝x2-y3且y1＝y2-x3，执行步骤4.1.3。
22、上述符号中，x1和y1分别表示变量u值域的下界和上界；x2和y2分别表示变量v值域的下界和上界；x3和y3分别表示约束{u，v}松弛前的下界和上界；x3'和y3'分别表示约束{u，v}松弛后的下界和上界。
23、步骤4.1.1：若x1＝x2-y3且y1<y2-x3，即izu与的下界相同，但izu的上界小于说明在约束松弛前的最小时间网络的计算过程中，变量u的值域下界是由约束ivu收到最紧的，而值域上界是由ivu以外的其它约束收到最紧的。因此，在约束{u，v}松弛后，变量u的值域下界能够扩展，而上界不能扩展。此时扩展后的变量u的值域为izu'＝[max(x2-y3',x1o),y1]。其中x1o是原始时间网络g中变量u的值域下界，若x2-y3'≤x1o，则将变量v从变量u的下界支持列表splow(u)中删除。再考虑变量u的邻居节点中对u的值域下界有影响的其它变量，即下界支持列表splow(u)，计算即为变量u最终扩展后的新值域izu”。其中，k表示变量u的下界支持列表splow(u)中的变量，izk表示变量k的值域，iku表示变量k与变量u之间的约束。
24、步骤4.1.2：若x1>x2-y3且y1＝y2-x3，即izu与的上界相同，但izu的下界小于说明在约束松弛前的最小时间网络的计算过程中，变量u的值域上界是由约束ivu收到最紧的，而值域下界是由ivu以外的其它约束收到最紧的。因此，在约束{u，v}松弛后，变量u的值域上界能够扩展，而下界不能扩展。此时扩展后的变量u的值域为izu'＝[x1,min(y2-x3',y1o)]。其中y1o是原始时间约束网络g中变量u的值域上界，若y2-x3'≥y1o，则将变量v从变量u的上界支持列表spupp(u)中删除。再考虑变量u的邻居节点中对u的值域上界有影响的其它变量，即上界支持列表spupp(u)，计算即为变量u最终扩展后的新值域izu”。其中，m表示变量u的上界支持列表spupp(u)中的变量，izm表示变量m的值域，imu表示变量m与变量u之间的约束。
25、步骤4.1.3：若x1＝x2-y3且y1＝y2-x3，即izu与的上下界均相同，说明在约束松弛前的最小时间网络的计算过程中，变量u的值域上下界均是由约束ivu收到最紧的。因此，在约束{u，v}松弛后，变量u的值域上下界均能够扩展。此时扩展后的变量u的值域为izu'＝[max(x2-y3',x1o),min(y2-x3',y1o)]。其中x1o是原始时间约束网络g中变量u的值域下界，y1o是原始时间约束网络g中变量u的值域上界。若x2-y3'≤x1o，则将变量v从变量u的下界支持列表splow(u)中删除；若y2-x3'≥y1o，则将变量v从变量u的上界支持列表spupp(u)中删除。再考虑变量u的邻居节点中对u的值域上下界有影响的其它变量，即上界支持列表spupp(u)和下界支持列表splow(u)。计算即为变量u最终扩展后的新值域izu”。其中，n表示变量u的上界支持列表spupp(u)中与下界支持列表splow(u)的并集中的变量，izn表示变量n的值域，inu表示变量n与变量u之间的约束。
26、步骤4.2：若izu”≠izu，则将变量u其加入变量值域更新列表up中。同理，计算松弛约束{u，v}后变量v扩展后的新值域，若izv”≠izv，则将变量v也加入变量值域更新列表up中。
27、步骤4.3：若变量值域更新列表up为空，则表明约束松弛后的变量值域更新完毕，若列表非空则执行步骤4.4直到变量值域更新列表up为空。
28、步骤4.4：对于变量值域更新列表up中的每个变量p，执行步骤4.5，直至up中的所有变量均遍历。
29、步骤4.5：对于变量p的邻居列表ne(p)中的变量q，判断变量p是否在q的变量值域支持列表中。若p∈spupp(q)，计算的上界值作为变量q的新上界值；若p∈splow(q)，计算的下界值作为变量q的新下界值。若变量q值域发生变化，则将变量q也加入变量值域更新列表up。继续计算ne(p)中的其它变量直至所有变量q均遍历，然后将变量p移出变量值域更新列表up。
30、其中，spupp(q)表示变量q的上界支持列表，r表示spupp(q)中的变量，izr表示变量r的值域，irq表示变量r与变量q之间的约束，splow(q)表示变量q的下界支持列表，t表示splow(q)中的变量，izt表示变量t的值域，itq表示变量t与变量q之间的约束。
31、步骤五、对于航天器规划修复过程中动态松弛的时间约束网络，基于步骤四进行减量式弧一致时间约束推理，减少时间约束推理次数，提高航天器自主规划修复效率，从而提高航天任务的实时性和安全性。
32、有益效果：
33、1、本发明公开的航天器任务规划修复的弧一致时间约束松弛处理方法，建立航天器时间规划修复问题模型，包括航天器状态、系统可执行活动时间变量、活动的时间约束、执行失败后的航天器状态和修复目标状态。将模型中活动时间变量及时间约束表示为简单时间网络stn中的变量点与边，构建原始时间网络。并在由原始时间网络计算最小时间网络的过程中保存造成每个变量值域上下界收紧的邻居节点集合，构建变量值域支持列表。在此基础上基于减量式的弧一致方法进行时间约束推理，实现规划修复过程中时间约束松弛后对变量扩展值域的快速求解，提高航天器任务规划修复效率，进而保证航天器在轨自主运行的实时性和安全性。
34、2、本发明公开的航天器任务规划修复的弧一致时间约束松弛处理方法，构建变量值域支持列表，根据约束对变量值域上下界的影响，在变量值域支持列表中选取有影响的邻居节点变量进行推理，从而限制约束松弛对变量值域的扩展范围，减少不必要的时间约束推理，快速计算变量值域的扩展范围。
35、3、本发明公开的航天器任务规划修复的弧一致时间约束松弛处理方法，在计算变量值域的扩展范围过程中，能够动态更新变量值域支持列表和变量值域更新列表，从而在规划修复过程中能够基于列表进行约束的动态松弛计算，避免了从头开始推理，减少不必要的计算，节省航天器上有限的计算资源，提高航天器任务规划修复过程中的时间约束推理效率。
1.航天器任务规划修复的弧一致时间约束松弛处理方法，其特征在于：包括如下步骤，
2.如权利要求1所述的航天器任务规划修复的弧一致时间约束松弛处理方法，其特征在于：步骤一实现方法为，
3.如权利要求2所述的航天器任务规划修复的弧一致时间约束松弛处理方法，其特征在于：步骤二实现方法为，
4.如权利要求3所述的航天器任务规划修复的弧一致时间约束松弛处理方法，其特征在于：步骤三实现方法为，
5.如权利要求4所述的航天器任务规划修复的弧一致时间约束松弛处理方法，其特征在于：步骤四实现方法为，
