1、第 45 卷第 2 期 2024 年 2 月宇 航 学 报Journal of AstronauticsNo.22024FebruaryVol.45小天体柔性着陆任务规划的动态时间约束推理方法王棒1,2,徐瑞1,2,李朝玉1,2,朱圣英1,2,梁子璇1,2(1.北京理工大学宇航学院,北京 100081;2.深空自主导航与控制工信部重点实验室(北京理工大学),北京 100081)摘要:针对小天体柔性着陆任务规划中的复杂耦合时间约束一致性推理效率问题,建立任务规划时间约束网络,通过划分时间约束类型,设计约束动态添加策略,提出动态弧一致时间约束推理方法,限制新添加约束的传播范围,局部求解时间网络一致
2、性,实现规划过程中时间约束网络一致性的高效维护。最后,构建小天体着陆规划场景,生成着陆任务规划活动及时间约束。仿真结果表明,与现有时间约束推理方法相比,所提出方法提高了时间约束推理效率,进而可为小天体柔性着陆任务规划提供支撑。关键词:小天体探测;柔性着陆器;着陆任务规划;动态弧一致;时间约束推理中图分类号:TP18;V476.4 文献标识码:A 文章编号:1000-1328(2024)02-0212-10 DOI:10.3873/j.issn.1000-1328.2024.02.006Dynamic Temporal Constraint Reasoning Method for Flexib
3、le Landing Mission Planning of Small Celestial BodyWANG Bang1,2,XU Rui1,2,LI Zhaoyu1,2,ZHU Shengying1,2,LIANG Zixuan1,2(1.School of Aerospace Engineering,Beijing Institute of Technology,Beijing 100081,China;2.Key Laboratory of Autonomous Navigation and Control for Deep Space Exploration(Beijing Inst
4、itute of Technology),Ministry of Industry and Information Technology,Beijing 100081,China)Abstract:To address the complex coupled temporal constraint consistency reasoning problem in the planning of the small celestial body flexible landing mission,a mission planning temporal constraint network is c
5、onstructed,temporal constraint types are classified,and a constraint dynamic addition strategy is established.A dynamic arc-consistent temporal constraint reasoning method is proposed to limit the propagation range of newly added constraints,locally solve the temporal network consistency,and maintai
6、n the temporal constraint network in the planning process dynamically.Finally,a small celestial body landing planning scenario is designed with the landing planning activities and temporal constraints.Simulation results show that compared with the existing temporal constraint reasoning method,the me
7、thod in this paper improves the computational efficiency,which supports the planning of small celestial body flexible landing missions.Key words:Small celestial body exploration;Flexible lander;Landing mission planning;Dynamic arc-consistency;Temporal constraint reasoning0引言小天体探测是深空探测的重要内容之一。实施小天体表面
8、探测具有重要的科学与工程意义,对空间科学、行星科学、材料科学等领域的发展均有着促进作用1。迄今为止,各航天机构已实施了多项小天体探测任务,在这些任务中,有些探测器已经与小天体表面进行了接触或者向其投放了小型收稿日期:2023-07-16;修回日期:2023-10-26基金项目:国家重点研发计划(2019YFA0706500);国家自然科学基金(62006019);空间碎片专项(KJSP2020020302)212第 2 期王棒等:小天体柔性着陆任务规划的动态时间约束推理方法探测装置2。中国也以2016HO3小行星及311P彗星为目标推进小天体探测任务。相较于飞越和环绕探测,着陆探测无疑能够获得
9、更全面和准确的小天体科学数据。目前小天体着陆的主要难题在于其复杂弱引力环境以及未知的表面土壤性质,着陆器易发生反弹和逃逸。欧空局“罗塞塔”探测器释放的“菲莱”着陆器3-4接触到了 67P 彗星的表面,但是锚定机构未能按计划展开,在表面发生了明显的翻滚弹跳。日本的“隼鸟”号5、“隼鸟”2号6以及美国的OSIRIS-REx探测器7仅接触小天体表面进行采样,并未实现长时间的表面稳定着陆。为解决传统“刚性+缓冲”及“接触即走”着陆方式带来的不足,崔平远等8提出了柔性着陆的概念,文献 9 围绕该着陆方式对自主导航与制导控制等关键技术的研究进展与难点进行了总结和分析。如图1所示,着陆器由质量聚集区(节点)
10、及智能柔性材料两部分组成,通过增大与小天体表面的接触面积降低倾覆翻滚的风险,同时柔性材料可消耗着陆的残余动能,避免着陆器反弹逃逸。该着陆器具有节点间活动并行、约束耦合复杂、柔性干扰不确定等特点,因此着陆器需具备任务规划技术以提高其自主决策能力,实现复杂小天体环境下的安全着陆。相较于传统刚性着陆器,柔性连接的存在使得柔性着陆器活动间的时间约束更加严格、耦合。例如:t1,t2,t3分别为3个节点的着陆时间约束,如图2所示,为满足柔性连接约束,在着陆整个过程中还需保证3个时间的相互差值在一定范围内。在柔性着陆器的规划过程中,每步规划均是在规划空间中搜索满足要求的活动来改变或扩展当前的部分规划,该过程
11、的活动和时间约束信息是动态变化的。并且由于柔性连接约束不确定性的影响,节点的规划序列执行过程不是完全可控的,当执行出现偏差时,需要修复当前已有规划,对不确定性的干扰做出动态响应,快速确定规划修复后的活动执行区间,以提高着陆任务的安全性。因此,规划过程中时间约束推理的效率提升直接影响到规划速度。时间约束推理是任务规划技术的重要组成部分,深空一号的远程智能体证明了自主任务规划问题中时间信息传播高效处理的重要性10。目前时间约束推理方法主要包括路径一致与弧一致两大类。Floyd-Warshall算法11可以计算时间约束网络中任意两个顶点间的最短路径,该方法约束传播次数多,计算效率较低。因此部分路径一
12、致概念被应用于时间约束求解。STP算法12以部分路径一致求解为核心,以存储资源为代价提高了计算效率,有效降低了约束推理次数。P3C算法13采用有向路径一致(DPC),强制执行部分路径一致,进一步提高了时间约束推理效率。弧一致算法也通常被用于进行一致性判断,该类算法主要包括AC-1到AC-7、AC-2000、AC-2001等14。Kong等15提出了ACSTP算法用以解决时间约束问题,在减少约束推理次数方面优于现有算法。美国火星探测车使用的MAPGEN16规划系统使用了基于弧一致的算法保证时间约束的一致,并保留了最大的时间灵活性。但在动态的规划过程中,对于以上方法,每添加一个活动就需要对当前网络
13、所有时间变量进行一次遍历计算,随着约束的增加,时间约束的计算量显著增加,从而影响到规划效率。针对这一问题,有学者提出了时间约束网络增量式维护方法。增量全路径一致(IFPC)算法17通过更新部分网络来维护全路径一致,增量部分路径一致(IPPC)算法18在添加新约束或收紧现有约束时保持部分路径一致性来维护当前网络。Xu等19提出时间约束几何分组动态推理(GDAC)算法,减少时间约束推理过程中的重复计算等。现有增量式方法大多以路径一致为基础,在计算过程中会额外增加新的约束,从而增加计算代价,基于弧一致的算法可有效避免这一缺陷。透视图质量聚集区(节点)图1柔性着陆器示意图Fig.1Illustrati
14、on of the flexible multi-node landert1=s1,e1t2=s2,e2t3=s3,e3 t1t2 t2t3 t1t3(a)无柔性连接(b)有柔性连接图2时间约束耦合Fig.2Temporal constraints coupling213宇航学报第 45 卷本文针对小天体柔性着陆器着陆任务规划中的复杂时间约束推理问题,建立任务规划中的活动时间约束网络,进而划分约束类型,分析不同类型约束在时间网络中的传播特点,设计零点约束优先添加策略,减小规划过程中的时间约束传播范围。提出动态弧一致时间约束推理方法,局部求解时间约束网络一致性,获得着陆器系统可执行活动的最小可行
15、区间。最后构建小天体着陆规划场景,从多方面验证了所提方法的有效性和高效性。1问题描述及模型建立1.1任务规划问题描述本文主要研究小天体柔性着陆器着陆任务规划中的时间约束一致性推理问题。柔性着陆器着陆规划需要在复杂约束条件下求解每个系统待执行活动的可行起止时间。每个活动的时间信息可以由集合s,d,e来表示(s,d,e分别表示活动的开始时间、持续时间、结束时间),不同活动间存在复杂时间约束关系。例如:节点相机成像活动的开始时刻必须在姿态机动活动的结束时刻之后,并且每个节点的成像活动必须同时进行,以获得同时刻的图像用于着陆导航。首先描述柔性着陆器任务规划问题如下:定义1.小天体着陆任务规划问题A可采
16、用如下元组表示:A=A,Sa|a A,Ox,Cx,Ix,Gx|x Sa(1)式中:A为着陆器节点集合,Sa为节点包含的系统集合,Ox为系统可执行活动集合,Cx为活动的时间约束集合,Ix为系统初始状态,Gx为系统目标状态。定义2.系统可执行活动oi Ox的时间信息可表示为如下元组:oi=si,ei,di,Ci(2)式中:si为活动oi的开始时间点,ei为结束时间点,di为活动的持续时间,Ci为该活动与其他活动间的时间约束关系集合。定义3.柔性着陆器着陆任务规划中的时间约束问题S=定义为一个一组有限时间点变量集合X=x1,x2,xn和一组时间变量上的约束C=c1,c2,cm。每个变量代表一个规划活
17、动的开始或结束时间点,变量间的约束代表时间点之间的关系,对于定义在连续域上的时间点变量u,v X,其约束关系为一组线性不等式:a v-u b(3)其中,a,b均为实数。若存在时间变量赋值 x1=r1,x2=r2,xn=rn满足所有约束,则当前规划活动的时间约束问题是一致的。1.2时间约束网络构建为求解上述时间约束问题的一致性,并获得每个活动起止时间的最小可行区间,将该问题表示为加权有向图,也即时间约束网络G=。V为图的顶点集合,E为顶点间的边集合。时间变量u X表示为图中的顶点,变量间约束表示为边。对于时间变量u,v,约束表示为区间Iuv=a,b,若u,v属于同一活动,则Iuv表示的是活动内部
18、约束,即活动持续时长,若u,v属于不同活动,则Iuv表示活动间约束。如图3所示,定义着陆任务执行的时间零点z,则活动的起止可执行时间为时间变量与时间零点间的约束关系,也即变量值域Iu=Izu,Iv=Izv。每个活动的开始时间点与结束时间点变量si,ei V,V=s1,e1,si,ei,sn,en z,n为当前部分规划中包含的活动数。变量间的时间约束表示为网络中顶点间的有向边权重,wsiei=bsiei,weisi=-asiei或Isiei=-weisi,wsiei=-Ieisi。根据变量间的时间约束关系进一步划分约束类型,如图4所示。As,Ae和Bs,Be分别表示活动A和活动B的开始及结束时间
19、点。其中,变量点与时间零点z间的约束称为零点约束(Cz),如IzAs=8,11表示活动A的开始执行区间;同一活动的时间点变zwsieiweisisieiwzsiweizwzeiwsiz(a)权重形式(b)区间形式zsieiIzsi=wsiz,wzsiIzei=weiz,wzeiIsiei=weisi,wsiei图3时间约束网络示例Fig.3Temporal constraint network example214第 2 期王棒等:小天体柔性着陆任务规划的动态时间约束推理方法量间约束称为内部约束(CI),如IBsBe=1.5,2表示活动B的可持续时间;不同活动的时间点变量间约束称为外部约束(C
20、E),如IAsBs=)1,表示活动B至少在活动 A 开始执行 1 个单位时间之后再开始执行。从而时间约束网络G的边集表示为式(4),每条边(u,v)绑定约束类型Tuv,TuvCz,CI,CE。E=(u,v)|u,v V,Iuv C(4)对于定义在图G上的时间变量u,v V,存在路径 uv,其距离为Iuv。若存在时间变量j V,使得路径ujv有更短的距离,则更新Iuv。时间约束一致性推理的本质在于通过式(5)和(6)收紧原始约束,判断是否当前规划的所有活动约束都得到满足,并且求解当前网络中每个活动开始与结束的最小可行时间区间。Iujv=Iuj Ijv-wju-wvj,wuj+wjv(5)Iuv=
21、Iuv Iujv=min wvu,wju+wvj,min wuv,wuj+wjv(6)其中,运算符定义为 a,b c,d a+c,b+d,并且 a,b ,若存在Iuv=,则说明当前规划中活动的时间约束是不一致的,执行一次式(6)称为一次约束推理。根据柔性着陆器每个系统的初始状态与目标状态初始化时间网络,随着规划活动的添加,逐步扩展网络规模并求解时间约束问题。2动态弧一致时间约束推理柔性着陆器的规划过程中活动和时间约束都是动态变化的,约束信息的传播会影响当前已有规划活动的执行区间,若每次改变都对全局时间网络进行一次推理,则计算效率严重降低,本文提出一种动态弧一致时间约束推理方法,设计零点约束优先
22、添加策略,根据添加的约束类型不同限制约束传播范围,仅对局部约束网络进行推理,减少规划中活动动态变化的影响范围,提高时间问题的求解效率。2.1时间网络弧一致弧一致算法仅需求解每个变量值域的最小区间。也即,仅对变量与时间零点间的约束区间进行求交计算。定义4.对于时间约束网络G=,u,v V,且值域分别为Iu,Iv,存在约束Iuv C。若对于任意tu Iu,存在tv Iv使得tv-tu Iuv,则Iuv相对于Iu和Iv是弧一致的。若对于任意约束Iuv C,Iuv和Ivu都是弧一致的,则约束网络G是弧一致的。对于变量i V,构建其邻居变量集合Nei=j|()i,j E。弧一致算法在迭代中通过式(7)计
23、算每个变量的新值域,若所有变量值域都计算完成后i V,且Ii Ii,则继续下一次迭代,直到对于i V满足条件Ii=Ii。Ii=Ii(j Nei()Ij Iji)(7)2.2约束添加策略规划过程中的活动是逐步添加的,如图5所示,对于当前规划的待添加活动oi Ox,需要执行约束推理的时间网络包含两部分:当前部分规划中活动的时间变量和约束构建的原网络G0=以及待添加活动的时间变量和与G0中变量相关的局部约束网络Gp=。为实现时间约束网络的局部动态维护,将活动oi相关的3类约束逐条添加至原网络,从而对于每条新添加的约束而言,其对应的原网络G0=为G0与已添加至G0中的前序约束的并集。定义新添加约束的两
24、个变量为u,v,边为euv,则该约束与G0存在以下3类从属关系。1)u,v V0且euv E0,该约束的添加不会对G0已有活动的时间可行区间造成影响,该情况下无需执行时间约束推理,约束推理次数为0。2)u V0,v V0且euv E0,该情况有两种可z1.5,28,118,128,128,10.51,10,)1,)AsAeBsBe零点约束内部约束外部约束图4约束类型划分Fig.4Constraint typezsiei时间零点原网络变量待添加变量原网络约束待处理约束原网络图5待处理约束Fig.5Pending constraints215宇航学报第 45 卷能,当Tuv=Cz时,时间变量v与G
25、0中任意变量都不存在约束关系,因此该约束的添加不会影响G0中的时间区间,无需执行时间约束推理,约束推理次数为0;当Tuv=CI或Tuv=CE时,变量u的值域通过边euv传播,根据Iv=Iu Iuv推理变量v的值域,约束推理次数为1。3)u,v V0,同样存在两种可能,当Tuv=Cz时,根据第二种情况的分析可知,由于该活动前序约束的添加,变量v的值域Iv已通过约束推理得出,此时euv E0。因此该约束首先与已有值域Iv进行求交计算,若计算后的值域Iv=Iv,则该约束不影响G0中的时间区间,约束推理次数为1;若Iv Iv,则该约束必定在网络中传播,推理变量v的邻居变量值域,若邻居变量值域也发生改变
26、,则约束进一步传播,约束推理次数为式(8)。rZ=1+bi=1|V0bi|Nei v(8)其中,|V0|表示集合V0中的元素个数,b与bi为布尔值。若新约束添加后变量值域发生改变,则b=1,反之b=0;若变量i的值域发生改变,则bi=1,反之bi=0。当Tuv=CI或Tuv=CE时,需要分别计算变量u,v对互相值域的影响,进而根据区间减小与否执行约束传播,约束推理次数为式(9)。rIE=2+bi=1|V0bi|Nei v(9)根据上述3类从属关系下约束推理次数不同的分析可知,不同类型约束的添加顺序会影响约束的传播范围。对于活动oi Ox,根据定义的约束类型TuvCz,CI,CE,存在 2条零点
27、约束、1条内部约束及m条外部约束,有以下6种添加顺序,其约束推理次数分别为式(10)至式(15)。1)零点约束内部约束外部约束r1=2+2m+j=1mbjex()i=1n0+2bi|Neji aj(10)2)零点约束外部约束内部约束r2=2+2m+j=1mbjex()i=1n0+2bi|Neji aj+bini=1n0+2bi|Nemi am(11)3)内部约束零点约束外部约束r3=2+2m+j=1mbjex()i=1n0+2bi|Nejiaj+b0i u,vbi|Ne0ia0(12)4)内部约束外部约束零点约束r4=2+2m+j=1mbjex()i=1n0+2bi|Nejiaj+2b0i=1
28、n0+2bi|Nemiam(13)5)外部约束零点约束内部约束r5=2+2m+j=1mbjex()i=1n0+2bi|Nejiaj+2b0i=1n0+2bi|Nemiam+bini=1n0+2bi|Nemiam(14)6)外部约束内部约束零点约束r6=2+2m+j=1mbjex()i=1n0+2bi|Nejiaj+bini=1n0+2bi|Nemiam+2b0i=1n0+2bi|Nemiam(15)其中,n0为活动oi添加前的时间约束网络中变量数;ax(x=0,1,m)表示第x条外部约束添加后值域发生改变的变量;b0,bin,bjex均为布尔值,分别表示零点约束、内部约束及第j条外部约束添加后
29、是否改变原网络中的变量值域,若发生改变,则为1,反之则为0;Nexi,Nexi(x=0,1,m)分别表示未添加内部约束和已添加内部约束时,第x条外部约束添加后第i个变量的邻居变量集合。计算上述6种添加顺序下的约束推理次数,易得式(16)。r3 r1r4 r1r5 r2r6 r2(16)对于r1,r2而言,分3种情况讨论:1)最小时间网络来自于内部约束传播,则外部约束的添加不会改变原网络中的变量值域,即bjex=0,式(17)成立。r1=2+2m r2(17)2)最小时间网络来自于外部约束传播,则内部约束的添加不会改变原网络中的变量值域,即bin=0,式(18)成立。216第 2 期王棒等:小天
30、体柔性着陆任务规划的动态时间约束推理方法r2=2+2m+j=1mbjex()i=1n0+2bi|Neji aj r1(18)3)最小时间网络来自于零点约束,也即初始值域为最小值域,约束不传播,bin=bjex=0,式(19)成立。r1=2+2m=r2(19)内部约束与外部约束添加造成的约束传播范围与实际问题中的约束关系和约束数值有关,理论推导无法比较r1,r2的大小。因此,提出动态时间约束推理中的零点约束优先策略,以尽可能减小规划活动的约束传播范围,内部约束及外部约束可随机添加。针对柔性着陆器着陆任务,考虑规划过程中逐步添加的16个系统活动,包括96条约束。图6显示了6种添加顺序下的约束推理次
31、数曲线,进一步验证了所提策略的有效性。2.3动态约束推理综合上述分析及约束添加策略,根据新约束变量与原网络变量的从属关系以及新约束的类型,判断新约束在原网络中的传播范围,仅执行必要的局部约束传播,减少无效的一致性计算,有效降低约束推理次数,进而提出动态弧一致时间约束推理方法(DAC),逐步动态维护当前部分规划的时间约束网络一致性,并快速求解每个活动执行起止时间的最小可行区间,时间约束推理流程见图7,其中具体步骤如下:1)构建当前部分规划所包含活动的时间约束网络G0以及下一步规划待添加活动的局部网络Gp。2)按照零点约束优先策略生成待添加活动的约束集合,并顺序取出添加至约束网络G0。3)判断约束
32、类型及变量与G0的从属关系,若u,v V0或u V0,v V0且Tuv=Cz,无需执行约束推理,执行步骤 4;若u V0,v V0且Tuv=CI或CE,则计算变量v的值域,执行步骤4;若u,v V0,则执行步骤5。4)判断待处理约束集合是否为空,若为空则输出每个活动执行起止时间的最小可行区间,否则执0204060801000100200300400500600700约束推理次数约束添加数 零点-内部-外部 零点-外部-内部 内部-零点-外部 内部-外部-零点 外部-零点-内部 外部-内部-零点图66种添加顺序下的约束推理次数Fig.6Number of constraint reasoning
33、 in six add orders开始零点约束优先策略构建当前部分规划的时间网络G0及活动oi的局部网络Gp顺序取出Ep,中约束边euv及对应变量u,v并加入G0u,v V0或u V0,vV0,Tuv=CzuV0,vV0Tuv=CI或CE求非零点变量的值域Iv=IvIu IuvIjIj且IjIv=Iv=Iv将变量v加入列表Q遍历列表Qk中的变量iIj=IjIi Iij,j Nei将变量j 加入列表Q将变量i移出列表Q输出每个活动执行起止时间的最小可行区间结束时间约束不一致,重新选择规划活动是是否否是是是否否否否否是是QkQQ=Ep=图7动态弧一致算法流程图Fig.7Flow chart of
34、 dynamic arc-consistent algorithm217宇航学报第 45 卷行步骤2。5)首先求解新添加约束对其两个变量的值域影响(假设影响变量v),若Iv=,说明变量v不存在取值满足当前规划的时间约束,也即时间约束不一致,则执步骤7;若Iv=Iv,说明当前添加的约束不会影响变量v的时间区间,无需进一步推理,执行步骤4;若Iv Iv且Iv,则该约束在网络中传播,将变量v加入变量值域更新列表Q,并执行步骤6。6)通过列表Q对约束传播进行判断,计算新约束影响范围内的变量值域,判断变量计算后值域削减与否来限制约束传播,缩小约束传播范围,减少时间约束推理次数,节省着陆器有限的计算资源,
35、提高复杂时间约束推理效率。将Q赋值给列表Qk,遍历所有变量i Qk,计算值域Ii对所有邻居变量值域Ij,j Nei的影响,若Ij=,则时间约束不一致,执行步骤7;若Ij Ij且Ij,约束继续传播,将变量j加入Q。当集合Nei遍历完成后,将变量i移出集合Q并判断Q是否为空,若Q=,约束传播结束,所有变量的值域都已计算至最小,执行步骤 4;若Q ,Q中变量值域继续传播,重新执行步骤6。7)重新进行规划搜索选取合适的活动,执行步骤1。该方法以网络弧一致为基础,通过对规划过程中待添加活动的时间约束类型划分以及零点约束优先添加策略,在推理过程中无需增加额外的网络边,同时尽可能限制约束的传播范围,减少规划
36、中时间约束推理耗时,有效提高柔性约束下柔性着陆器着陆任务规划的实时性。3仿真实验3.1场景设计为了说明所提DAC方法的效果,设计柔性着陆器着陆任务进行仿真。着陆器包含3个节点,每个节点包含若干分系统。以规划中的成像系统为例,每个节点均携带光学相机,在着陆器着陆过程中获取小天体表面信息,提取规划问题中3个相机的成像准备和成像工作两个活动,其初始时间约束关系如图8所示,图中xs,xe分别表示活动x的开始时间点与结束时间点变量,其余类推。随着规划搜索的进行,在成像系统的部分规划中动态添加上述两个活动,并进行时间约束网络的一致性判断,求解每个活动执行起止时间的最小可行区间,部分规划活动的甘特图如图9所
37、示,满足相机A、B同时开始工作的约束,活动的最小可行区间如图10所示,结果证明了DAC方法的有效性。为进一步证明DAC算法对于柔性着陆器在不同任务场景下的适应性,以公开的时间网络数据集为基础20,设计着陆器着陆任务规划中活动间时间约束关系数值,分3种不同情况进行仿真对比,多方面验证 DAC 算法效率,从而体现 DAC 算法的动态性能。情况一:验证规划过程中新添加的活动数对时间约束推理效率的影响。活动数体现了着陆任务的复杂度,着陆器在相同目标状态下改变着陆过程中各系统所需执行的任务,并生成具有不同活动数和不同约束数的数据集,如表1所示。情况二:验证系统间时间约束耦合程度对时间约束推理效率的影响。
38、假设着陆器节点总共具有16个系统,每个系统具有10个不同的可执行活动,对于同一着陆任务,改变系统间的约束数,如表 2所示。情况三:验证着陆器节点不同系统组成对时间约束推理效率的影响。每个系统同样具有10个可执行活动,改变单个节点包含的系统数,系统间约束数M与系统数N满足关系M=50(N-1)。如表3所示。3.2对比分析为了验证时间约束推理方法的高效性,本节将图8三个相机的活动时间约束Fig.8Temporal constraints of three cameras activities218第 2 期王棒等:小天体柔性着陆任务规划的动态时间约束推理方法所提的 DAC 算法与 NASA 建立的
39、 EUROPA 规划器中采用的动态适应单源最短路径时间约束推理算法(ABF)20进行比较。如图11所示,当规划过程中新添加活动数不同时,DAC算法相较EUROPA算法,运行时间平均减少90.7%,且随着活动数的增加,差距进一步增大,DAC算法耗时增长更慢。图12显示了108个活动下每条约束添加至原网络中时,执行约束推理所需的时间,虚线表示单条约束平均推理时间,实线表示单条约束推理时间的标准差,DAC算法效率显著提高,且算法稳定性更好。对于不同系统间约束数,DAC算法平均效率提高78.8%,如图13所示。当系统数不同时,DAC算2040608010012005010015020025030035
40、0400活动数 DAC ABF运行时间/ms图11不同活动数的算法运行时间Fig.11Running time of the algorithms with different number of activities图10活动的最小可行区间Fig.10Minimum feasible intervals of activities相机C相机B相机A成像关机成像准备开始 成像准备结束成像工作开始 成像工作结束7008009001 2001 0001 100时间/s图9部分规划结果Fig.9Partial planning results表1规划添加的活动数Table 1Number of ac
41、tivities the system can execute任务编号12345678910活动数162432404856647288108约束数961923204806728961 1521 4402 1123 132表2系统间约束数Table 2Number of inter-system constraints系统数16任务编号123456系统间约束数501002004008001 600表3单节点包含的系统数Table 3Number of systems contained in a single node任务编号12345系统数48121620系统间约束数1503505507509
42、50219宇航学报第 45 卷法效率依然占优,平均提高78.5%,且随着系统数的增多,优势更加明显,如图14所示。柔性着陆器相较于传统单体着陆器具有系统多、约束耦合强、规划活动多的特点,因此,DAC算法能够更好地适应柔性着陆器着陆任务,提高任务规划过程中的时间约束推理效率,进而增强着陆器着陆任务规划的实时性。4结论本文针对小天体柔性着陆器的复杂时间约束推理问题,提出动态弧一致时间约束推理方法。提取规划活动的时间约束信息,构建部分规划与待添加活动的时间约束网络;分析活动约束与时间网络的从属关系,避免无效推理;设计了零点约束优先添加策略,进一步减小时间约束的传播范围,从而实现规划过程中动态活动添加
43、的局部时间约束推理,提高了约束推理效率。本文提出的方法能够快速判断时间约束一致性并求解规划活动可执行的最小可行区间,可为提高柔性着陆器着陆任务规划的实时性、增强着陆器自主决策能力提供技术支持。参 考 文 献1 ANTHONY N,EMAMI M R.Asteroid engineering:The state-of-the-art of Near-Earth Asteroids science and technologyJ.Progress in Aerospace Sciences,2018,100:1-17.2 徐瑞,朱圣英,崔平远,等.深空探测技术概论 M.北京:高等教育出版社,202
44、1:25-29.3 ROLL R,WITTE L.ROSETTA lander Philae:Touch-down reconstructionJ.Planetary and Space Science,2016,125:12-19.4 BOEHNHARDT H,BIBRING J P,APATHY I,et al.The Philae lander mission and science overviewJ.Philosophical Transactions of The Royal Society A:Mathematical,Physical and Engineering Scien
45、ces,2017,375(2097):20160248.5 KAWAGUCHI J,FUJIWARA A,UESUGI T.Hayabusa:Its technology and science accomplishment summary and Hayabusa-2 J.Acta Astronautica,2008,62(10/11):639-647.6 TSUDA Y,SAIKI T,TERUI F,et al.Hayabusa2 mission status:Landing,roving and cratering on asteroid RyuguJ.Acta Astronautic
46、a,2020,171:42-54.7 BIERHAUS E B,CLARK B C,HARRIS J W,et al.The OSIRIS-REx spacecraft and the touch-and-go sample acquisition mechanism(TAGSAM)J.Space Science Reviews,2018,214(7):107.8 崔平远,陆晓萱,朱圣英,等.小天体柔性附着状态协同估计方法 J.宇航学报,2022,43(9):1219-1226.CUI Pingyuan,LU Xiaoxuan,ZHU Shengying,et al.Cooperative s
47、tate estimation method for small celestial body flexible landingJ.Journal of Astronautics,2022,43(9):1219-1226.9 崔平远,张成宇,朱圣英,等.小天体柔性附着技术 J.宇 DAC ABF510152005001 0001 5002 0002 5003 0003 500系统数运行时间/ms图14不同系统数的算法运行时间Fig.14Running time of the algorithms with different number of systems DAC ABF04008001
48、2001 60005001 0001 5002 0002 5003 000系统间约束数运行时间/ms图13不同约束数的算法运行时间Fig.13Running time of the algorithms with different number of constraints05001 0001 5002 0002 5003 0003 5000.0410.006 DAC约束添加数05001 0001 5002 0002 5003 0003 500约束添加数0.3760.196 ABF时间/ms101101102100时间/ms100102103104101(a)ABF算法单步推理时间(b)DA
49、C算法单步推理时间图12单步约束推理时间(108个活动)Fig.12Single-step constraint reasoning time(108 activities)220第 2 期王棒等:小天体柔性着陆任务规划的动态时间约束推理方法航学报,2023,44(6):805-816.CUI Pingyuan,ZHANG Chengyu,ZHU Shengying,et al.Technologies for flexible landing on small celestial bodiesJ.Journal of Astronautics,2023,44(6):805-816.10 MU
50、SCETTOLA N,MORRIS P H,TSAMARDINOS I.Reformulating temporal plans for efficient execution C.The Sixth International Conference on Principles of Knowledge Representation and Reasoning,Trento,Italy,June 2-5,1998.11 HOUGARDY S.The Floyd-Warshall algorithm on graphs with negative cyclesJ.Information Proc