面向突发任务的空间站任务重规划方法

牟帅,卜慧蛟,张进,罗亚中*

国防科学技术大学 航天科学与工程学院,长沙 410073

面向突发任务的空间站任务重规划方法

牟帅,卜慧蛟,张进,罗亚中*

国防科学技术大学 航天科学与工程学院,长沙 410073

针对空间站在轨运营出现突发任务的情况,提出一种基于启发式规则的任务重规划方法,满足了方案重规划的快速响应需求。根据任务执行的连续性特点和冲突状态,建立了空间站突发任务规划领域模型。考虑重规划过程中任务包含活动间复杂约束关系传播的影响,提出了时间回溯迭代冲突化解策略,同时依据任务执行时间间隔,提出针对间隔插空的时间冗余启发式规则。基于时间回溯迭代冲突化解策略和时间冗余启发式规则,对原任务执行计划进行实时重规划,实现了突发任务的快速响应。应用算例分析表明,提出的重规划方法可以成功地满足空间站突发任务规划需求,实现实时更新空间站在轨任务执行详单的目的。

空间站;任务规划;启发式;突发任务;快速响应

空间站任务规划是空间站长期运营、有效管理的关键技术,当前的空间站任务规划研究主要满足国际空间站运营需求。国际空间站已经在轨运行多年,参加运营的主要国家和组织已经开发了多种任务运营规划系统。美国约翰逊中心开发的集成规划系统(Integrated Planning System,IPS)是国际空间站的核心任务规划系统[1]。JPL人工智能部开发了连续活动调度规划执行和重规划系统[2-3]。欧洲航天局针对其运营舱段,开发了运营准备与规划系统(Operations Preparation and Planning System,OPPS)[4]。但是,上述文献主要介绍了国际空间站软件系统的功能架构,公开的国外文献中很少有针对空间站任务规划具体模型和方法的研究论述。

而国内在空间站任务规划方面的研究还处在起步阶段。文献[5-6]结合国外空间站运营任务规划概念和典型的空间站任务规划系统,对中国空间站运营任务规划关键技术提出了发展建议。文献[7-8]对空间站长期运营任务规划及建模进行了研究。文献[9-10]对空间站短期任务规划进行了分析研究,提出了基于本体模型的任务规划模型和基于时间迭代的任务冲突化解策略。

上述研究中没有考虑空间站任务执行过程中出现突发情况的影响,而在工程实际中,空间站在轨设备可能会发生故障,人员操作失误等也难以完全避免。当这些突发情况发生时,航天员必须首先处理突发事件,这样就会造成当前执行任务延迟或取消,原始的任务执行计划便失去了时效性。所以,寻找一种应对突发任务的快速重规划方法是十分必要的。在其他领域,文献[11-13]对面向动态需求的卫星滚动式重调度方法进行了研究。文献[14]解决了高空飞艇的应急调度问题。但是,这些研究主要针对包含单个活动的观测任务,对于时效性强、包含活动多、约束复杂的空间站在轨运营任务,这些方法则不能完全适用。文献[15-17]对深空探测器复杂约束和启发式任务规划方法进行了研究。但是,这些方法没有考虑重规划过程中约束传播以及突发任务对原任务执行计划带来的影响,也不能直接应用于空间站任务重规划。

本文主要针对空间站运营过程中出现突发情况时,对原任务执行计划进行快速地重新规划。提出时间回溯迭代冲突化解策略,以解决重规划过程中复杂约束关系传播造成的影响,提出时间冗余启发式规则,以实现对突发任务的快速响应,并维持原任务执行计划的相对稳定性。

1 问题描述

面向突发任务的空间站任务重规划问题是指在空间站在轨运行期间,当设备故障、人员操作失误、外部环境改变等不确定因素发生时,快速对突发情况进行分析处理,并对任务执行计划进行重新规划。

1.1 重规划问题描述

重规划问题可以视为一个快速求解的约束满足问题,即不仅要求规划方案结果满足各项约束条件,还要求重规划时间尽可能短并维持原任务执行计划的相对稳定性,以实现对突发任务的快速响应。重规划问题描述如图1所示。

图1 重规划问题示意图Fig.1 Illustration of re-planning problem

初始条件为原在轨任务执行详单,当突发时刻(Pop-up Moment)有突发任务发生时,根据资源等约束条件对正在执行任务进行模型重构,并应用合理有效的规划求解策略,对突发任务、重构后任务以及原计划执行任务进行实时重新规划,输出新的、满足要求的在轨任务执行详单。

1.2 概念模型描述

文献[8]应用本体模型对空间站短期任务规划概念进行了详细描述,建立了任务、活动、资源、约束等概念本体模型,并应用属性集合和关系集合分别对各概念模型进行描述。本文在其工作基础上增加了任务类型,明确了任务优先级定义,提出了任务连续性等概念,建立了面向突发任务的空间站任务重规划模型。

任务概念描述如下:

式中:M 为任务;dM.I.为任务编号;NM.N.为任务名称;tM.ST.为任务最早开始时间;tM.ET.为任务最晚结束时间;EM.P.为任务优先级,取值在0～100范围内;OM.OI.为其他任务信息;SM.T.为任务类型,并根据任务重要级别分层定义其优先级:vCr为5级突发型(90～100),vEm为4级紧急型(70～89),vDa为3级日常维护型(50～69),vPa为2级载荷型(20～49),vUn为1级未知型(0～19);SM.C.为任务连续性类型:vNo为禁断型,即如果任务执行过程中受到干扰不能连续执行,则该任务执行失败,放入不可执行任务集合,vAl为允断型,即任务在执行过程中可以暂停执行,而不影响其后续执行和任务结果,vNe为重拾型,即如果任务执行过程中受到干扰不能连续执行,其已经完成操作会对后面操作产生较大影响,不能继续执行,但是在轨资源和任务执行条件允许该任务重新执行;A为任务包含活动。

活动概念描述如下:

式中:dA.I.为活动编号;DA.D.为活动持续时间;tA.S.为活动开始时间;OA.OI.为其他活动信息;SA.R.为活动间时序关系类型:vEq为与关系任务同时发生,vBe为早于关系任务发生,vAf为晚于关系任务发生;R为活动占用资源。

资源概念描述如下:

式中:dR.I.为资源编号;CR.Max.为资源额定容量;pR.P.为资源功耗;QR.Th.为资源散热;OR.OI.为其他资源信息;SR.T.为资源类型:vSt为平台型,vPa为载荷型,vUk为未知型。

1.3 规划模型描述

1)设计变量

将突发任务开始时刻和由突发任务引起原任务执行计划中发生调整任务的重新开始时刻作为设计变量。设计变量描述如下:

式中:X为设计变量;t(i)为第i个重规划任务开始时刻;tM.ST.(i)为第i个重规划任务最早开始时刻;tM.ET.(i)为第i个重规划任务最晚结束时刻;n为由突发任务引起原任务执行计划中发生调整任务总数。

2)约束分析

约束分析主要考虑空间站在轨运营功耗、散热、数据传输带宽、资源额定容量、天地通信窗口、活动间先验关系等约束。各项约束描述如下:

式中:t为规划时刻;nw为t时刻正在执行任务数;pR.P.(i)为t时刻正在执行任务功耗;pMax为额定功耗;QR.Th.(i)为t时刻正在执行任务散热;QMax为额定散热;bB.W.(i)为t时刻数据传输任务占用带宽;bMax为额定带宽;CR.A.(i)为t时刻资源占用量;tC.C.(j)为第j个通信任务执行时间;[tC.S.(j),tC.E.(j)]为通信窗口;m为通信任务个数。

3)目标函数

考虑空间站长期在轨运营的安全性与稳定性,应该尽量减小突发任务对原任务执行计划产生的影响,因此本文提出任务执行计划稳定性指标作为规划的目标函数。

式中:f为稳定性指标;tri为执行时间发生改变任务的重排后开始时间;ti为执行时间发生改变任务的原开始时间;δm为任务重要级别系数;nc为取消执行任务总数。

2 重规划方法

面向突发任务的空间站任务重规划是当空间站在轨运营有突发任务发生时,对与突发任务存在约束冲突的正在执行任务相关参数进行实时更新,即任务模型重构,并对突发任务以及重构后任务进行合理再安排,并通过一系列快速、有效的冲突化解策略,得到不存在任何约束冲突的规划结果,实时更新在轨任务执行详单。

2.1 突发任务预处理策略

空间站在轨运营有突发任务发生时,首先对与突发任务存在约束冲突的正在执行任务进行搜索,再根据任务连续性对冲突任务相关参数进行实时更新,建立冲突任务重构模型。

1)冲突任务搜索。根据突发任务发生时刻搜索此时正在执行的任务,依次判断此时资源、功耗、散热、传输带宽等约束条件是否满足,如果有约束超出额定值,则依据任务优先级将其中最小优先级任务暂停执行并放入重构集合,循环判断各约束条件直至无约束冲突存在。冲突任务搜索流程如图2所示。

2)冲突任务模型重构。依次判断上文得到的重构集合中任务连续性性质,若其为禁断型,则直接取消执行该任务,并宣布任务执行失败,放入不可执行任务集合;若其为允断型,则依据未执行活动对该任务包含活动、活动的持续时间以及资源占用等相关参数信息进行更新,得到重构后任务;若其为重拾型,则不考虑其已经执行过活动,直接将该任务整体推迟;并将重构后任务和推迟后任务放入重规划集合。冲突任务模型重构流程如图3所示。

图2 冲突任务搜索流程图Fig.2 Flow chart of conflict mission search

2.2 时间回溯迭代冲突化解策略

针对每个空间站任务由多个活动组成,不同任务包含活动间存在一定的约束关系,在冲突化解过程中,由于任务执行时间调整可能会产生新的约束冲突的情况,提出基于时间回溯迭代的冲突化解策略。冲突化解流程如图4所示。

图4中,M1、M2为执行时间存在重叠的2个任务,且 M1优先级大于 M2。a11、a12、a13、a14、a15、a16为 M1包含活动,a21、a22、a23、a24、a25、a26为M2包含活动,a13与a21存在约束冲突,a15与a24存在约束冲突。时间回溯迭代冲突化解策略按照一定步长在时间线上推进,判断每一个时间节点上正在执行任务活动的资源占用、功耗、散热和传输带宽等约束条件,如果存在约束冲突,如M2中a24与M1中a15存在约束冲突,则将正在执行任务中优先级最小的任务(M2)推迟一个步长,同时返回到任务的开始时刻进行回溯迭代,重新判断每个时间节点上约束情况,直至无约束冲突存在,如M″2所示。

图3 冲突任务模型重构示意图Fig.3 Illustration of re-construction of conflict mission model

图4 时间回溯迭代冲突化解策略示意图Fig.4 Illustration of time backtrack iteration strategy

2.3 时间冗余启发式规则

为了尽量减小突发任务对原任务执行计划的影响,应尽可能地将2.1节中得到的重规划任务安排在任务允许发生时间范围内占用资源冗余量最大的时间段内。即遍历任务占用资源,在时间线上找出每种资源冗余量最大时间段,取几个时间段中最短的时间范围,将重规划任务首先安排在该时间段的起始时刻,并用时间回溯迭代冲突化解策略对所有任务进行约束冲突化解,以得到新的满足约束条件的在轨任务执行详单。其具体规划流程如图5所示。图中:nrp为2.1节中重规划任务集合中任务总数;nrw为正在执行的重规划任务;tx为时间节点;Δt为时间步长;T为规划结束时间。

步骤1 将2.1节中得到的重规划任务集合中任务按优先级由大到小排列,并首先安排优先级最大的任务。

步骤2 根据重规划任务中最大优先级任务占用的资源,在时间线上找到任务允许发生时间范围内每种资源被占用时间段,从而找出每种资源占用最大冗余时间段。

步骤3 根据每种资源占用最大冗余时间段找出几个时间段中最短的时间范围,将重规划任务安排在时间线上该时间段的起始时刻。

步骤4 从重规划任务开始时刻开始,对时间线上每个时间迭代步长节点的约束冲突情况进行判断。

步骤5 若存在约束冲突,则搜索存在约束冲突的正在执行任务,并将其中优先级最小任务的开始时间推迟一个时间步长。

步骤6 若任务执行时间超出允许发生时间范围,则取消任务执行,放入不可执行任务集合,继续执行步骤8。否则,执行步骤7。

步骤7 迭代时间返回到该任务的开始时刻,并重新对时间线上每个时间迭代步长节点的约束冲突情况进行判断,直到规划结束时间。

步骤8 依据任务优先级依次对重规划任务集合中任务进行安排,直到所有重规划任务安排结束。

步骤9 输出更新后的在轨任务执行详单。

图5 时间冗余启发式算法流程图Fig.5 Flow chart of interval time heuristic algorithm

3 算例分析

为验证本文方法的有效性和优越性,同时用本文提出的面向突发任务的空间站任务重规划方法、文献[10]中应用的时间迭代启发式方法和文献[9]中应用的改进遗传算法对同一个算例进行测试。测试环境为Windows 7 32位操作系统,Intel(R)Core(TM)i7-4790 CPU3.60 GHz,内存为4 G,编程环境为Visual C++6.0。

3.1 算例配置

为方便分析,将任务周期压缩,选取24 h内执行日常维护、载荷试验等15项完整任务进行分析,其中包含单次执行活动25项,占用仪器、设备、物资等资源10种,涉及功耗、散热、活动顺序等约束条件8种。设置突发任务1项,突发时刻为10:00,空间站额定功耗为5 000 W,额定散热能力为4 500 W,时间迭代步长为0.05 h。

3.2 规划结果

为了更直观地展现空间站任务间关系、活动间执行顺序以及资源约束等关系,给出3种任务规划方法规划后的在轨任务执行详单信息,如图6所示。图中:R1～R10代表10种不同资源;M1～M14和M01代表15个规划任务(M01代表突发任务);a1～a23、a91和a92代表任务包含的25项活动;灰色框单元代表原任务执行详单;黑色框单元代表更新后任务执行详单;红色单元代表突发任务。

为了方便对比分析3种规划方法中不同算法策略对规划结果的影响,将重规划结果中各项参数信息统计如表1所示。

图6 在轨任务执行详单示意图Fig.6 Illustration of onboard mission list

表1 3种不同方法规划结果对比Table 1 Comparison of planning results of three methods

3.3 结果分析

1)规划结果任务详单分析

将图6(b)中本文方法规划结果任务详单与图6(a)中原任务详单对比可知,当在任务执行过程中有突发任务(M01)发生时,通过本文提出的突发任务预处理策略,首先对突发任务进行了安排,同时暂停执行与突发任务存在约束冲突的正在执行任务(M3～M6),并对其进行任务模型重构,有效减少了冲突任务直接取消产生的影响。进一步可以看出,应用本文提出的时间回溯迭代冲突化解策略,除M5由于任务本身性质取消执行外,其余冲突任务均通过合理地推迟部分原任务而得到重新安排,显著提高了任务执行计划的稳定性。

将图6(c)中文献[10]方法规划结果任务详单与图6(a)中原任务详单对比可知,当在任务执行过程中有突发任务(M01)发生时,由于该方法没有对突发任务的预处理策略和对重规划任务的回溯迭代过程,所以与突发任务存在约束冲突的4项任务(M3～M6)均取消执行,如此将使任务的完成率明显降低。

将图6(d)中文献[9]方法规划结果任务详单与图6(a)中原任务详单对比可知,该方法与本文方法结果基本相同,保证了原任务执行计划的相对稳定性。

2)3种不同方法结果对比分析

从表1中本文方法和文献[10]方法规划结果数据对比可以看出,虽然本文方法计算时间比文献[10]方法计算时间长,但前者规划结果中任务的完成率明显高于后者,并且规划结果中稳定性指标后者显著高于前者。因此,本文方法比文献[10]方法具有更好的稳定性。

从表1中本文方法和文献[9]方法规划结果数据对比可以看出,虽然后者的稳定性指标略优于前者,但是其计算时间明显大于前者,计算效率较低,不能满足任务重规划快速响应的需求。因此,本文方法比文献[9]方法具有更好的时效性。

4 结 论

1)提出的突发任务预处理策略,有效减少了冲突任务直接取消对空间站产生的影响。

2)提出的时间回溯迭代冲突化解策略,显著提高了空间站任务执行计划的稳定性。

3)提出的时间冗余启发式规则,可以有效减少任务重规划时间。

4)本文方法可以同时满足空间站任务重规划快速响应和稳定性需求,具有一定的工程实用价值。

[1] SAINT R.Lessons learned in developing an international planning software system[C]//Proceedings of the 7th International Conference on Space Operations,2002:1-10.

[2] CHIEN S A,KNIGHT R,STECHERT A,et al.Using iterative repair to improve the responsiveness of planning and scheduling[C]//Proceedings of the 5th International Conference on Artificial Intelligence Planning and Scheduling,2000:300-307.

[3] KNIGHT S,RABIDEAU G,CHIEN S,et al.Space exploration through continuous planning[J].IEEE Intelligent Systems,2001,16(5):70-75.

[4] ZOESCHINGER G A,WICKLER M,KOEHLER A,et al.A planning system for payload and system planning of the Columbus module on ISS[C]//Proceedings of the 8th International Conference on Space Operations,2004:1-6.

[5] 罗亚中,林鲲鹏,唐国金.空间站运营任务规划技术评述[J].载人航天,2012,18(2):7-13.

LUO Y Z,LIN K P,TANG G J.Review on space station mission planning technology[J].Manned Spaceflight,2012,18(2):7-13(in Chinese).

[6] 田坤黉,侯永青.国际空间站运营管理体系架构分析[J].载人航天,2011,17(1):10-15.

TIAN K H,HOU Y Q.Analysis of international space station operation architecture[J].Manned Spaceflight,2011,17(1):10-15(in Chinese).

[7] LIN K P,LUO Y Z,TANG G J.Optimization of logistics strategies for long-duration space station operation[J].Journal of Spacecraft and Rockets,2014,51(5):1709-1720.

[8] 李志海,侯永青,严厚民,等.空间站长期运营任务规划建模初步研究[J].载人航天,2013,19(5):52-58.

LI Z H,HOU Y Q,YAN H M,et al.Preliminary modeling study on long-term operation mission planning of space station[J].Manned Spaceflight,2013,19(5):52-58(in Chinese).

[9] BU H J,ZHANG J,LIN K P,et al.Short-term planning of the space station operation mission based on genetic algorithm[C]//Proceedings of 64th International Astronautical Congress,2013:1-9.

[10] BU H J,ZHANG J,LUO Y Z.Space station short-term mission planning using ontology modelling and time iteration[J].Journal of Systems Engineering and Electronics,2016,27(2):407-421.

[11] VERFAILLIE G,PRALET C,LEMAITRE M.Constraint-based modeling of discrete event dynamic systems[J].Journal of Intelligent Manufacturing,2010,21(1):31-47.

[12] 习婷,李菊芳.面向动态需求的成像卫星滚动式重调度方法研究[J].中国管理科学,2015,23(专辑):269-274.

XI T,LI J F.The rolling horizon method for EOS scheduling with dynamic request[J].Chinese Journal of Management Science,2015,23(Special Issue):269-274(in Chinese).

[13] 王建江,朱晓敏,吴朝波,等.面向应急条件的多星动态调度方法[J].航空学报,2013,34(5):1151-1164.

WANG J J,ZHU X M,WU C B,et al.Multi-satellite dynamic scheduling method for emergencies[J].Acta Aeronautica et Astronautica Sinica,2013,34(5):1151-1164(in Chinese).

[14] 贺川,邱涤珊,许光,等.面向对地成像观测任务的高空飞艇应急调度[J].航空学报,2012,33(11):2082-2092.

HE C,QIU D S,XU G,et al.Emergency scheduling of earth-observing imaging tasks on high-altitude airships[J].Acta Aeronautica et Astronautica Sinica,2012,33(11):2082-2092(in Chinese).

[15] 赵凡宇,徐瑞,崔平远.启发式深空探测器任务规划方法[J].宇航学报,2015,36(5):496-503.

ZHAO F Y,XU R,CUI P Y.Heuristic mission planning approach for deep space explorer[J].Journal of Astronautics,2015,36(5):496-503(in Chinese).

[16] 傅阳光,周成平,王长青,等.考虑时间约束的无人飞行器航迹规划[J].宇航学报,2011,32(4):749-755.

FU Y G,ZHOU C P,WANG C Q,et al.Path planning for UAV considering time constraint[J].Journal of Astronautics,2011,32(4):749-755(in Chinese).

[17] 王晓晖,李爽.深空探测器约束简化与任务规划方法研究[J].宇航学报,2016,37(7):768-774.

WANG X H,LI S.Research on constraint simplification and mission planning method for deep space explorer[J].Journal of Astronautics,2016,37(7):768-774(in Chinese).

Re-planning method for space station pop-up missions

MU Shuai,BU Huijiao,ZHANG Jin,LUO Yazhong*

College of Aerospace Science and Engineering,National University of Defense Technology,Changsha 410073,China

Considering pop-up missions in space station operation,a re-planning method based on heuristic algorithm is proposed to satisfy the requirement for fast responses of mission re-planning.According to the continuity characteristic and conflict condition in mission execution,a model for space station pop-up mission planning domain is constructed.Considering the propagation effects of complicated constraints between the activities of missions,the time backtrack iteration strategy is adopted to solve the conflicts,and then an interval time heuristic algorithm is proposed according to the interval time between missions'execution.A fast response to the pop-up mission is achieved using the time backtrack iteration strategy and the interval time heuristic algorithm to re-plan the missions.The results show that the proposed mission re-planning method can successfully satisfy the requirement for pop-up mission planning and real-time updating of the onboard mission list.

space station;mission planning;heuristic;pop-up mission;fast response

2016-09-19;Revised:2016-10-18;Accepted:2016-12-07;Published online:2016-12-19 16:13

URL:www.cnki.net/kcms/detail/11.1929.V.20161219.1613.002.html

s:National Natural Science Foundation of China(11402295);National Basic Research Program of China(2013CB733100);Natural Science Foundation of Hunan Province of China(2015JJ3020)

V423.7

A

1000-6893(2017)07-320793-08

10.7527/S1000-6893.2016.320793

2016-09-19;退修日期:2016-10-18;录用日期:2016-12-07;网络出版时间:2016-12-19 16:13

www.cnki.net/kcms/detail/11.1929.V.20161219.1613.002.html

国家自然科学基金 (11402295);国家“973”计划 (2013CB733100);湖南省自然科学基金 (2015JJ3020)

*通讯作者.E-mail:luoyz@nudt.edu.cn

牟帅,卜慧蛟,张进,等.面向突发任务的空间站任务重规划方法[J].航空学报,2017,38(7):320793.MU S,BU H J,ZHANG J,et al.Re-planning method for space station pop-up missions[J].Acta Aeronautica et Astronautica Sinica,2017,38(7):320793.

(责任编辑:张玉)

*Corresponding author.E-mail:luoyz@nudt.edu.cn