一种深空探测器自主任务规划时间约束几何处理方法
一种深空探测器自主任务规划时间约束几何处理方法
【技术领域】
[0001 ] 本发明涉及一种深空探测器自主任务规划时间约束几何处理方法，属于深空探测
技术领域。
【背景技术】
[0002] 在深空环境下，深空探测器与目标距离远、飞行时间长、所处环境动态多变，传统 地面站-航天器这样的控制方法已经无法满足操作费用、实时性、通讯网络等各项要求。为 达到较高的实时性要求，在探测器中应用自主技术成为重要途径。而自主任务规划技术是 自主技术的关键技术之一。
[0003] 在深空探测领域中，采用自主任务规划，需要对时间进行表示、并对时间约束进行 处理。目前，时间约束网方法是探测器自主任务规划中采用的时间表示和处理方法，并已经 应用到了探索太空的项目中，如深空一号中自治远程代理系统、美国规划、调度和约束推理 平台EUR0PA等。时间约束网方法的一个缺点是如果改变其中一个点的约束或者新加入变量 点，就要对所有点的值进行计算，若在规划过程中引入一个活动，就会引入2个变量点，2*(n +1)个约束弧(η为原来的变量点），导致计算量急剧增加，不适合快速处理时间约束。
[0004] 由于时间在二维情况下能够明确表示出时间的开始点、结束点和持续时间，因此 提出利用二维坐标系对时间进行表示并用几何方法处理时间约束。该方法首先由Rit提出， 后来Pu jari、Kumari和Sattar进一步讨论了一下，其他只是简单进行了介绍，而最近 Ullberg使用了该方法表示少量的定量约束解决环境识别问题中的区间推理问题。上述研 究中虽然做了一定研究，但是没有详细给出利用二维坐标系表示时间和处理时间约束的方 法。
【发明内容】
[0005] 本发明的目的是针对目前深空探测器自主任务规划中时间约束处理问题，为了克 服时间约束网计算量大且计算时间长的缺点，提出一种深空探测器自主任务规划时间约束 几何处理方法，是一种验证时间约束一致性(活动变量值域能够满足所有约束)和约束几何 处理方法，在任务规划活动变量众多的情况下，快速实现时间约束处理，从而满足探测器实 时性要求。
[0006] 本发明通过设计时间约束几何处理方法实现，具体实现步骤如下：
[0007] 步骤1，建立深空探测器时间规划问题模型。
[0008] 深空探测器时间规划问题由探测器系统状态集合、探测器可执行活动变量集合、 活动间的约束集合、探测器初始状态以及目标状态组成，即V= {V1，v2，. . .，vm}。
[0009] 其中，V={V1，V2, . . .，vm}为状态变量集合，且VeDv，Dv为探测器能达到的状态值 域，m为状态变量的数量;0= {〇1，〇2,...，on}为探测器可执行的活动变量集合，η为活动变量 的数量，任意一个探测器活动〇χ具有开始点s x、结束点ex、持续时间dx，即ox = {sx，ex，dx}; C为 探测器活动间的约束集合，此处约束为两个活动间的时间约束，即C(〇x，〇y) = "〇x Cons 〇y"，〇x与〇y为活动间约束对，Cons为活动间约束关系；s。为探测器初始状态，即当时间为Ο (相对零点）时，探测器状态变量都对应相应的值;g为目标状态，即探测器各个变量需要达 到的值。
[0010] 步骤2，对步骤1中探测器活动变量及活动间的时间约束进行表示。
[0011] 在处理时间约束之前，需要对探测器活动变量及时间约束进行表示。
[0012] 1.对探测器活动变量及活动自身约束进行表示。
[0013] 设探测器活动变量集合0= {〇1，02, . . .，Οη}中任意一个探测器活动Ox，且Ox= {sx, ex,dx}。将活动变量ox在二维坐标系下进行表示:横坐标x为开始点，纵坐标y为结束点，y = x +dx与纵坐标交点的值为持续时间。
[0014] 对于探测器活动变量ox= {sx，ex，dx}，自身约束为sxe [slx，s2x]、exE [elx，e2x]和 dxe [dlx，d2x]。其中，slx，s2x为活动o x开始点值域的下界和上界;elx，e2x为活动ox结束点值 域的下界和上界;dl x，d2x为活动ox持续时间值域的下界和上界。如果有相对零点，则slx 2 s2x2 0;slx = s2x时，表示开始点的值域只有一个时刻；同理eld e2x 2 0，dlx2 d2x2 0。
[0015] 2.对深空探测器活动间约束进行表示。
[0016] 设探测器两个活动变量ox= {sx，ex，dx}和oy= {sy，ey，dy}。活动间约束包括ox开始 点对〇y开始点的约束[ss 1，ss2 ]，ss 1，ss2为约束值域的下界和上界;ox开始点对Oy结束点的 约束[sel，se2]，sel，se2为约束值域的下界和上界;o x结束点对oy开始点的约束[esl，es2]， esl，es2为约束值域的下界和上界;ox结束点点对oy结束点的约束[eel，ee2]，eel，ee2为约 束值域的下界和上界。（ssl，ss2，sel，se2，esl，es2，eel，ee2为任意实数）。
[0017] 步骤3，根据探测器活动变量自身约束，对所有探测器活动变量值域进行自我削 减。
[0018] 自我削减方法为：活动变量~={&，&，心}初始值域为^已[81^82」、^已[ 61^ e2x]和dxe [dlx，d2x]。利用几何表示方法，二维坐标系下开始点值域范围界限为x = slx与X =82。结束点值域范围界限为7 = 6]^与7 = 62\，持续时间值域范围界限为7 = 1+(1]^与7 =叉+ d2x。六条直线相交于12个交点。从12个交点中挑选满足条件的交点：Xe[elx，e2 x]，ye [elx，e2x]，y￡ [x+dlx，x+d2x]。剩余η个点(η < 12)，其中任意一点表示为(xn，yn)。
[0019] 经自我削减后，探测器活动变量0x值域为Sxe[ srx，s2'x]、exe[ el'x，e2'xWPdxe ,sl ,x = min(xn),s2 ,x = max(xn) ,el ,x = min(yn),e2 ,x=max(yn) ,(11^ = min(yn_xn)，d2 'X=max(yn-xn)。其中min表示最小值，max表示最大值。
[0020] 步骤4，从深空探测器活动间约束对中任意选择一对以〇\，<^) = 〃<^〇118(^〃根据(^ 值域和约束关系Cons推导〇y的值域。分别推导〇y的开始点值域、结束点值域和持续时间值 域。
[0021 ]步骤4.1，对于Oy的开始点值域[sly，s2y]，ox和约束[ssl，ss2]、[esl，es2]对[sly, s2y]有影响。在坐标系中，为了两个约束同时满足，〇y的开始点可行区域
[0022] Availablex= [slx+ssl，s2x+ss2] Π [elx+esl，e2x+es2] (1)
[0023] 如果交集为空，则表示没有值同时满足两个约束，整个时间约束处理过程结束，结 论为时间约束不一致，即无法得到满足所有时间约束的活动值域。如果交集不为空，则进行 步骤4.2。
[0024] 步骤4.2,对于oy的结束点值域[ely，e2 y]，ox和约束[sel，se2]和[eel，ee2]对其有 影响。在坐标系中，为了两个约束同时满足，0y的结束点可行区域为
[0025] Availabley= [slx+sel，s2x+se2] Π [elx+eel，e2x+ee2] (2)
[0026] 如果交集为空，则表示没有值同时满足两个约束，整个时间约束处理过程结束，结 论为时间约束不一致，即无法得到满足所有时间约束的活动值域。如果交集不为空，则进行 步骤4.3。
[0027]步骤4.3，对〇y的持续时间值域，由式(3)获得。
[0028] Availabled = dl Π d2 Π d3 Π d4 (3)
[0029] 其中，dl = [sel_ss2, se2_ssl ]，d2=[eel_es2, ee2_esl ]，d3 = [d31，d32]，d4 = [d41，d42];且
[0030] d31=min(dlx-ssl+eel，dlx-ssl+ee2，dlx-ss2+eel，dl x-ss2+ee2)，
[0031 ] d32=max(d2x-ssl+eel，d2x-ssl+ee2，d2x-ss2+eel，d2 x-ss2+ee2)，
[0032] d41=min(-dlx-esl+sel，-dlx-esl+se2，-dlx-es2+sel，-dl x-es2+se2)，
[0033] d42=max(-d2x-esl+sel，-d2x-esl+se2，-d2x-es2+sel，-d2 x-es2+se2) 〇
[0034] min表示几个值中的最小值，max表示几个值中的最大值。
[0035]根据式（1)_(3)，得〇y最后可行值域
[0036] Avai lable= Avai lab lex Π Availabley Π Availablea (4)
[0037] 如果交集为空，则表示没有值同时满足两个约束，整个时间约束处理过程结束，结 论为时间约束不一致，即无法得到满足所有时间约束的活动值域。如果交集不为空，则进行 步骤5。
[0038] 步骤5,步骤4中求出的oy可行值域Available与oy原值域s ye [sly，s2y]，eye [ely, e2y]和dye [dly, d2y]进行几何相交。探测器活动oy开始点新值域为Intersect ionx = Availablex Π [sly，s2y]，探测器活动oy结束点新值域为Intersectiony = Availabley Π [ely，e2y]，探测器活动oy持续时间新值域为Intersectiond = Availabled Π [dly，d2y]。最终 求得〇y新值域Intersection:IntersectionxΠ Intersectiony Π Intersectiond。如果交集 为空，整个时间约束处理过程结束，结论为时间约束不一致，即无法得到满足所有时间约束 的活动值域。如果交集不为空，则进行步骤6。
[0039]步骤6,比较Oy新值域Intersection与原值域是否相同，若不同，则将与Oy相关的约 束对再次加入到约束对集合C中。同时，将约束 对C(〇x，〇y) = "〇xC〇ns 〇/从约束对集合C中 删除。如果相同，则将约束对C(〇x，〇y) = "〇xC〇ns 〇/从约束对集合C中删除即可。
[0040] 步骤7，重复步骤4，、步骤5和步骤6，直到约束对集合C为空。如果步骤中4与步骤5 中没有返回"时间约束不一致"结论，则表示深空探测器所有活动变量满足约束关系，时间 约束一致，所有活动变量得到新值域;如果步骤4与步骤5中返回"时间约束不一致"结论，则 表示深空探测器活动变量无法满足所有约束关系，所有活动变量无法得到新值域，时间规 划结束。
[0041 ] 有益效果
[0042]本发明设计了一种验证时间约束一致性(活动变量值域能够满足所有约束)和约 束几何处理方法，能够快速验证深空探测器规划过程中时间约束的一致性并处理时间约 束，得到活动变量最终值域，弥补采用时间约束网处理大量活动变量时计算时间长的缺点。 与基于时间约束网的时间处理方法相比较，解决同样的时间约束问题，计算时间短、效率 高，更加适合实时性要求高的深空探测器。
【附图说明】
[0043] 图1为本发明方法中活动变量在二维坐标系下的表示方法；
[0044] 图2为【具体实施方式】中四种活动间约束在二维坐标系下的表示方法，其中（a)为步 骤4.1中根据〇x和约束[ssl， SS2]求〇y开始点值域的方法图示，（b)为步骤4.1中根据〇x和约 束[681，682]求0\开始点值域的方法图示，（(3)为步骤4.2中根据(^和约束[861，862]求(^结 束点值域的方法图示，（d)为步骤4.2中根据 〇x和约束[eel，ee2]求〇y结束点值域的方法图 示；
[0045] 图3为【具体实施方式】中活动〇y新值域求解方法；
[0046] 图4为【具体实施方式】中时间约束几何处理方法与时间约束网方法解决相同时间约 束问题的时间比较图。
【具体实施方式】
[0047]本发明的目的是针对目前深空探测器自主任务规划中时间约束处理问题，提出一 种验证时间约束一致性(活动变量值域能够满足所有约束)和约束几何处理方法，是一种在 任务规划活动变量众多的情况下，快速实现时间约束处理，从而满足探测器实时性要求的 方法。
[0048]本发明通过设计时间约束几何处理方法实现，具体实现步骤如下：
[0049] 步骤1，建立深空探测器时间规划问题模型。
[0050] 针对深空探测中的火星探测器建立模型，由探测器系统状态集合、探测器可执行 活动变量集合、活动之间约束集合、初始状态以及目标状态组成，即V={vi，V2, . . .，Vm}。
[0051] 其中，￥={^^2，...，^}为状态变量集合，且7已0￥，0 ￥为火星探测器可达到的状态 值域，m = 28为状态变量的数量，该模型中具有28个状态变量，如探测器姿态系统可处于的 状态有定向、转动等;〇= {〇i，〇2,.. .，on}为探测器可执行活动变量集合，n = 288为活动变量 的数量，即在规划过程中需要处理288个探测器的活动，任意一个探测器活动〇x具有开始点 sx、结束点ex、持续时间dx，即ox= {sx，ex，dx} ;C为探测器活动间的约束集合，此处约束为两 个活动间的时间约束，即C(ox，〇y) = 〃ox Cons oy〃，ox与oy为活动间约束对，Cons为活动间约 束关系，该模型中处理13种约束关系，如表1所示;s。为探测器初始状态，即当时间为0(相对 零点）时，探测器状态变量都对应相应的值;g为目标状态，即探测器各个变量需要达到的 值。
[0052]表1火星探测器活动间约束关系
[0054] 步骤2，对步骤1中探测器活动变量及活动间的时间约束进行表示。
[0055] 在处理时间约束之前，需要对探测器活动变量及时间约束进行表示。
[0056] 1.对探测器活动变量及活动自身约束进行表示。
[0057] 假设探测器活动变量集合0={〇1，〇2，. . .，〇"}中任意一个探测器活动〇x，且〇x = i Sx，ex，dx}。sx为活动〇x的开始点，e x为活动〇x的结束点，dx为活动〇x的持续时间。将活动变量 0x在二维坐标系下进行表示:横坐标为开始点，纵坐标为结束点，y = x+d与纵坐标交点的值 为持续时间。
[0058] 对于探测器活动变量ox= {sx，ex，dx}，自身约束为sxe [slx，s2x]、exe [elx，e2x]和 dxe [dlx，d2x]。其中，slx，s2x为活动o x开始点值域的下界和上界;elx，e2x为活动ox结束点值 域的下界和上界;dl x，d2x为活动ox持续时间值域的下界和上界。如果有相对零点，则slx 2 s2x2 0，slx = s2x时，表示开始点的值域只有一个时刻；同理elx2 e2x 2 0，dlx2 d2x2 0。
[0059] 2.对深空探测器活动间约束进行表示。
[0060] 假设探测器两个活动变量<^={8\&，(^}和(^={8\^，(^}。活动间约束包括(^开 始点对〇y开始点的约束[sS1，SS2 ]，SS 1，SS2为约束值域的下界和上界;ox开始点对Oy结束点 的约束[sel，se2]，sel，se2为约束值域的下界和上界;ox结束点对Oy开始点的约束[esl， es2]，esl，es2为约束值域的下界和上界;ox结束点点对oy结束点的约束[eel，ee2]，eel，ee2 为约束值域的下界和上界。（ssl，ss2，sel，se2，esl，es2，eel，ee2为任意一实数）。
[0061 ]步骤3，根据探测器活动变量自身约束，对所有探测器活动变量值域进行自我削 减。
[0062] 活动变量ox= {sx, ex, dx}初始值域为sxe [slx，s2x]、exe[elx，e2xHPdxe[dlx， d2x]。利用几何表示方法，二维坐标系下开始点值域范围界限为x = s 1 x与x = s2X，结束点值 域范围界限为y = elx与y = e2x，持续时间值域范围界限为y = x+dlx与y = x+d2x。六条直线相 交于12个交点。从12个交点中挑选满足条件的交点：xe[el x，e2x]，ye[elx，e2 x]，ye[x+ dlx，x+d2x]。剩余η个点(η < 12)，其中任意一点表示为(xn，yn)。
[0063] 经自我削减后，探测器活动变量〇x值域为sxe [si 'x，s2'x]、exE [el 'x，e2'x]和dxe ,sl ,x = min(xn),s2 ,x = max(xn) ,el ,x = min(yn),e2 ,x=max(yn) ,(11^ = min(yn_xn)，d2 'X=max(yn-xn)。其中min表示最小值，max表示最大值。
[0064] 步骤4，从深空探测器活动间约束对中任意选择一对C(ox，〇y) = 〃oxCons oy〃，其中 Cons指步骤2中活动间的约束关系。根据〇x值域和约束关系Cons推导〇y的值域。推导时分三 种情况进行，即推导〇y的开始点值域、结束点值域和持续时间值域。
[0065] 步骤4.1，对于Oy的开始点值域[sly，s2y]，〇x和约束[ssl，ss2]和[esl，es2]对[sly, s2y]有影响。在坐标系中，为了两个约束同时满足，〇y的开始点可行区域
[0066] Availablex= [slx+ssl，s2x+ss2] Π [elx+esl，e2x+es2] (1)
[0067] 如果交集为空，则表示没有值同时满足两个约束，整个时间约束处理过程结束，结 论为时间约束不一致，即无法得到满足所有时间约束的活动值域。如果交集不为空，则进行 后续步骤。
[0068] 步骤4.2，同理，对于％的结束点值域[61^62」，0\和约束[861，862]和[661，662] 对[el y，e2y]有影响。在坐标系中，为了两个约束同时满足，Oy的结束点可行区域为
[0069] Availabley= [slx+sel，s2x+se2] Π [elx+eel，e2x+ee2] (2)
[0070] 如果交集为空，则表示没有值同时满足两个约束，整个时间约束处理过程结束，结 论为时间约束不一致，即无法得到满足所有时间约束的活动值域。如果交集不为空，则进行 后续步骤。
[0071 ]步骤4.3，对〇y的持续时间值域，由式(3)获得。
[0072] Availabled = dl Π d2 Π d3 Π d4 (3)
[0073] 其中，dl = [sel_ss2, se2_ssl ]，d2=[eel_es2, ee2_esl ]，d3 = [d31，d32]，d4 = [d41，d42];且
[0074] d31=min(dlx-ssl+eel，dlx-ssl+ee2，dlx-ss2+eel，dl x-ss2+ee2)，
[0075] d32=max(d2x-ssl+eel，d2x-ssl+ee2，d2x-ss2+eel，d2 x-ss2+ee2)，
[0076] d41=min(-dlx-esl+sel，-dlx-esl+se2，-dlx-es2+sel，-dl x-es2+se2)，
[0077] d42=max(-d2x-esl+sel，-d2x-esl+se2，-d2x-es2+sel，-d2 x-es2+se2) 〇
[0078] min表示几个值中的最小值，max表示几个值中的最大值。
[0079]根据式（1)-(3)，得〇y最后可行值域
[0080] Avai lable= Avai lab lex Π Availabley Π Availablea (4)
[0081] 如果交集为空，则表示没有值同时满足两个约束，整个时间约束处理过程结束，结 论为时间约束不一致，即无法得到满足所有时间约束的活动值域。如果交集不为空，则进行 后续步骤。
[0082] 步骤5,步骤4中求出的oy可行值域Available与oy原值域s ye [sly，s2y]，eye [ely, e2y]和dye [dly, d2y]进行几何相交。探测器活动oy开始点新值域为Intersect ionx = Availablex Π [sly，s2y]，探测器活动oy结束点新值域为Intersectiony = Availabley Π [ely，e2y]，探测器活动oy持续时间新值域为Intersec tiond = Availabled Π [dly，d2y]。最终 求得〇y新值域Intersection:IntersectionxΠ Intersectiony Π Intersectiond。如果交集 为空，整个时间约束处理过程结束，结论为时间约束不一致，即无法得到满足所有时间约束 的活动值域。如果交集不为空，则进行后续步骤。
[0083] 步骤6,比较〇y新值域Intersection与原值域是否相同，若不同，则将与〇y相关的约 束对再次加入到约束对集合C中。同时，将约束对C( 〇x，〇y) = "〇xC〇ns 〇/从约束对集合C中 删除。如果相同，则将约束对C(〇x，〇y) = "〇xC〇ns 〇/从约束对集合C中删除即可。
[0084] 步骤7，重复步骤4，步骤5和步骤6，直到约束对集合C为空，步骤中4与步骤5中没有 返回"时间约束不一致"结论，深空探测器所有活动变量满足约束关系，时间约束一致，所有 活动变量得到新值域。
[0085] 在该例子中，活动变量数为288，计算时间为16.732383s，利用时间约束网时间为 950.28626s，效率提高了一个数量级，更加适合火星探测实时性要求。
[0086]图4是时间约束几何处理方法与时间约束网方法解决相同时间约束问题的时间比 较图。图中：虚线部分表示时间约束几何处理方法;实线部分表示时间约束网方法。横坐标 是问题中的活动变量数，纵坐标是计算时间（取e为底对数）。由图中可看出，时间约束几何 处理方法比时间约束网方法计算时间低三个数量级，随着活动数量增加，几何处理方法时 间保持平稳，而时间约束网方法不断增加。
【主权项】
1.一种深空探测器自主任务规划时间约束几何处理方法，其特征在于：具体实现步骤 如下： 步骤1，建立深空探测器时间规划问题模型； 深空探测器时间规划问题由探测器系统状态集合、探测器可执行活动变量集合、活动 间的约束集合、探测器初始状态以及目标状态组成，即V= {V1，V2，. . .，Vm}; 其中，V= {V1，V2，. . .，Vm}为状态变量集合，且VeDv，Dv为探测器能达到的状态值域，m为 状态变量的数量;0= {〇1，02,...，〇n}为探测器可执行的活动变量集合，η为活动变量的数 量，任意一个探测器活动〇\具有开始点8\、结束点6\、持续时间(^，即0\={8\，6\，(1山(：为探测 器活动间的约束集合，此处约束为两个活动间的时间约束，即c(〇x，〇y) =〃〇xCons〇y〃，〇χ与 〇y为活动间约束对，Cons为活动间约束关系;S。为探测器初始状态，即当相对零点时，探测器 状态变量都对应相应的值;g为目标状态，即探测器各个变量需要达到的值； 步骤2,对步骤1中探测器活动变量及活动间的时间约束进行表示； 在处理时间约束之前，需要对探测器活动变量及时间约束进行表示；1. 对探测器活动变量及活动自身约束进行表示； 设探测器活动变量集合〇= {〇1，〇2, . . .，〇n}中任意一个探测器活动0X，且0X= {sx，ex,dx};将活动变量0X在二维坐标系下进行表示:横坐标X为开始点，纵坐标y为结束点，y=x+dx 与纵坐标交点的值为持续时间； 对于探测器活动变量〇x= {sx，ex，dx}，自身约束为sxe[slx，s2x]、exe[elx，e2x]和dxe [d1x，d2x];其中，s1x，s2X为活动ox开始点值域的下界和上界;e1x，e2X为活动ox结束点值域的 下界和上界;dlx，d2x为活动〇x持续时间值域的下界和上界;如果有相对零点，则slx2s2x2 0;slx=s2x时，表示开始点的值域只有一个时亥IJ;同理elx 2e2x 2 0，dlx 2d2x 2 0;2. 对深空探测器活动间约束进行表示； 设探测器两个活动变量〇\={8\，6\，(^}和(^={8\，6\，(^};活动间约束包括(^开始点对(^ 开始点的约束[Ss1，ss2 ]，ss1，ss2为约束值域的下界和上界;ox开始点对〇y结束点的约束 [sel，se2]，sel，se2为约束值域的下界和上界;ox结束点对oy开始点的约束[esl，es2]，esl， es2为约束值域的下界和上界;ox结束点点对oy结束点的约束[eel，ee2]，eel，ee2为约束值 域的下界和上界;ssl，ss2，sel，se2，esl，es2，eel，ee2为任意实数； 步骤3，根据探测器活动变量自身约束，对所有探测器活动变量值域进行自我削减； 自我削减方法为:活动变量〇x= {sx，ex，dx}初始值域为sxe[Slx，S2X]、exe[elx，e2x]和dxe[dlx，d2x];利用几何表示方法，二维坐标系下开始点值域范围界限为x=slx与x=s2x， 结束点值域范围界限为y=elx与y=e2x，持续时间值域范围界限为y=x+dlx与y=x+d2x;六 条直线相交于12个交点;从12个交点中挑选满足条件的交点:Xe[elx，e2x]，ye[elx，e2x]， ye[x+dlx，x+d2x];剩余η个点，η< 12,其中任意一点表示为(xn，yn); 经自我削减后，探测器活动变量〇χ值域为sxe[sl'x，s2'x]、exe[el'x，e2'x^Pdxe ,sl,x =min(xn),s2,x =max(xn),el,x =min(yn),e2 ,x=max(yn) ,(11^ = min(yn-xn)，d2'x=max(yn-xn);其中min表示最小值，max表示最大值； 步骤4,从深空探测器活动间约束对中任意选择一对C(〇x，〇y) = "〇xC〇ns〇y"根据〇x值域 和约束关系Cons推导〇y的值域;分别推导〇y的开始点值域、结束点值域和持续时间值域； 步骤4.1，对于Oy的开始点值域[sly，s2y]，ox和约束[ssl，ss2]、[esl，es2]对[sly，s2y] 有影响;在坐标系中，为了两个约束同时满足，0y的开始点可行区域 Availablex = [slx+ssl，s2x+ss2]Π[elx+esl，e2x+es2] (1) 如果交集为空，则表示没有值同时满足两个约束，整个时间约束处理过程结束，结论为 时间约束不一致，即无法得到满足所有时间约束的活动值域;如果交集不为空，则进行步骤 4.2； 步骤4.2,对于oy的结束点值域[ely，e2y]，ox和约束[sel，se2]和[eel，ee2]对其有影响； 在坐标系中，为了两个约束同时满足，〇y的结束点可行区域为 Availabley= [slx+sel，s2x+se2]Π[elx+eel，e2x+ee2] (2) 如果交集为空，则表示没有值同时满足两个约束，整个时间约束处理过程结束，结论为 时间约束不一致，即无法得到满足所有时间约束的活动值域;如果交集不为空，则进行步骤 4.3； 步骤4.3，对〇y的持续时间值域，由式(3)获得； Availabled=dlΠd2Πd3Πd4 (3) 其中，dl = [sel_ss2, se2_ssl ]，d2=[eel_es2, ee2_esl ]，d3= [d31，d32]，d4 = [d41，d42];且d31=min(dlx-ssl+eel，dlx-ssl+ee2，dlx-ss2+eel，dlx-ss2+ee2)，d32=max(d2x-ssl+eel，d2x-ssl+ee2，d2x_ss2+eel，d2x-ss2+ee2)，d41=min(-dlx-esl+sel，_dlx-esl + se2，_dlx-es2+sel，_dlx-es2+se2)，d42 = max(-d2x-esl+sel，_d2x-esl+se2，_d2x-es2+ sel，-d2x_es2+se2) ;min表示几个值中的最小值，max表示几个值中的最大值； 根据式(1)-(3)，得〇y最后可行值域 Available=AvailablexΠAvailableyΠAvailablea(4) 如果交集为空，则表示没有值同时满足两个约束，整个时间约束处理过程结束，结论为 时间约束不一致，即无法得到满足所有时间约束的活动值域;如果交集不为空，则进行步骤 5； 步骤5,步骤4中求出的Oy可行值域Available与Oy原值域Sye[sly，s2y]，ey￡ [ely，e2y] 和dy￡ [dly，d2y]进行几何相交;探测器活动〇y开始点新值域为Intersectionx=Availablex Π[sly，s2y]，探测器活动〇y结束点新值域为Intersectiony =AvailableyΠ[ely，e2y]，探测 器活动〇y持续时间新值域为Intersectiond=AvailabledΠ[dly，d2y];最终求得oy新值域 Intersection=IntersectionxΠIntersectionyΠIntersectiond;如果交集为空，整个时 间约束处理过程结束，结论为时间约束不一致，即无法得到满足所有时间约束的活动值域； 如果交集不为空，则进行步骤6; 步骤6,比较〇y新值域Intersection与原值域是否相同，若不同，则将与〇y相关的约束对 再次加入到约束对集合C中；同时，将约束对C(〇x，〇y) = "〇xC〇ns〇/从约束对集合C中删除； 如果相同，则将约束对C(〇x，〇y) = "〇xC〇ns〇/从约束对集合C中删除即可； 步骤7，重复步骤4，、步骤5和步骤6，直到约束对集合C为空；如果步骤中4与步骤5中没 有返回"时间约束不一致"结论，则表示深空探测器所有活动变量满足约束关系，时间约束 一致，所有活动变量得到新值域;如果步骤4与步骤5中返回"时间约束不一致"结论，则表示 深空探测器活动变量无法满足所有约束关系，所有活动变量无法得到新值域，时间规划结 束。
【专利摘要】本发明涉及一种深空探测器自主任务规划时间约束几何处理方法，属于深空探测技术领域。本发明设计了一种验证时间约束一致性(活动变量值域能够满足所有约束)和约束几何处理方法，能够快速验证深空探测器规划过程中时间约束的一致性并处理时间约束，得到活动变量最终值域，弥补采用时间约束网处理大量活动变量时计算时间长的缺点。与基于时间约束网的时间处理方法相比较，解决同样的时间约束问题，计算时间短、效率高，更加适合实时性要求高的深空探测器。
【IPC分类】G05D1/08, G05D1/10
【公开号】CN105487546
【申请号】CN201510883280
【发明人】徐瑞, 李朝玉, 崔平远, 朱圣英, 高艾, 乔栋, 尚海滨
【申请人】北京理工大学
【公开日】2016年4月13日
【申请日】2015年12月4日
【技术领域】
[0001 ] 本发明涉及一种深空探测器自主任务规划时间约束几何处理方法，属于深空探测
技术领域。
【背景技术】
[0002] 在深空环境下，深空探测器与目标距离远、飞行时间长、所处环境动态多变，传统 地面站-航天器这样的控制方法已经无法满足操作费用、实时性、通讯网络等各项要求。为 达到较高的实时性要求，在探测器中应用自主技术成为重要途径。而自主任务规划技术是 自主技术的关键技术之一。
[0003] 在深空探测领域中，采用自主任务规划，需要对时间进行表示、并对时间约束进行 处理。目前，时间约束网方法是探测器自主任务规划中采用的时间表示和处理方法，并已经 应用到了探索太空的项目中，如深空一号中自治远程代理系统、美国规划、调度和约束推理 平台EUR0PA等。时间约束网方法的一个缺点是如果改变其中一个点的约束或者新加入变量 点，就要对所有点的值进行计算，若在规划过程中引入一个活动，就会引入2个变量点，2*(n +1)个约束弧(η为原来的变量点），导致计算量急剧增加，不适合快速处理时间约束。
[0004] 由于时间在二维情况下能够明确表示出时间的开始点、结束点和持续时间，因此 提出利用二维坐标系对时间进行表示并用几何方法处理时间约束。该方法首先由Rit提出， 后来Pu jari、Kumari和Sattar进一步讨论了一下，其他只是简单进行了介绍，而最近 Ullberg使用了该方法表示少量的定量约束解决环境识别问题中的区间推理问题。上述研 究中虽然做了一定研究，但是没有详细给出利用二维坐标系表示时间和处理时间约束的方 法。
【发明内容】
[0005] 本发明的目的是针对目前深空探测器自主任务规划中时间约束处理问题，为了克 服时间约束网计算量大且计算时间长的缺点，提出一种深空探测器自主任务规划时间约束 几何处理方法，是一种验证时间约束一致性(活动变量值域能够满足所有约束)和约束几何 处理方法，在任务规划活动变量众多的情况下，快速实现时间约束处理，从而满足探测器实 时性要求。
[0006] 本发明通过设计时间约束几何处理方法实现，具体实现步骤如下：
[0007] 步骤1，建立深空探测器时间规划问题模型。
[0008] 深空探测器时间规划问题由探测器系统状态集合、探测器可执行活动变量集合、 活动间的约束集合、探测器初始状态以及目标状态组成，即V= {V1，v2，. . .，vm}。
[0009] 其中，V={V1，V2, . . .，vm}为状态变量集合，且VeDv，Dv为探测器能达到的状态值 域，m为状态变量的数量;0= {〇1，〇2,...，on}为探测器可执行的活动变量集合，η为活动变量 的数量，任意一个探测器活动〇χ具有开始点s x、结束点ex、持续时间dx，即ox = {sx，ex，dx}; C为 探测器活动间的约束集合，此处约束为两个活动间的时间约束，即C(〇x，〇y) = "〇x Cons 〇y"，〇x与〇y为活动间约束对，Cons为活动间约束关系；s。为探测器初始状态，即当时间为Ο (相对零点）时，探测器状态变量都对应相应的值;g为目标状态，即探测器各个变量需要达 到的值。
[0010] 步骤2，对步骤1中探测器活动变量及活动间的时间约束进行表示。
[0011] 在处理时间约束之前，需要对探测器活动变量及时间约束进行表示。
[0012] 1.对探测器活动变量及活动自身约束进行表示。
[0013] 设探测器活动变量集合0= {〇1，02, . . .，Οη}中任意一个探测器活动Ox，且Ox= {sx, ex,dx}。将活动变量ox在二维坐标系下进行表示:横坐标x为开始点，纵坐标y为结束点，y = x +dx与纵坐标交点的值为持续时间。
[0014] 对于探测器活动变量ox= {sx，ex，dx}，自身约束为sxe [slx，s2x]、exE [elx，e2x]和 dxe [dlx，d2x]。其中，slx，s2x为活动o x开始点值域的下界和上界;elx，e2x为活动ox结束点值 域的下界和上界;dl x，d2x为活动ox持续时间值域的下界和上界。如果有相对零点，则slx 2 s2x2 0;slx = s2x时，表示开始点的值域只有一个时刻；同理eld e2x 2 0，dlx2 d2x2 0。
[0015] 2.对深空探测器活动间约束进行表示。
[0016] 设探测器两个活动变量ox= {sx，ex，dx}和oy= {sy，ey，dy}。活动间约束包括ox开始 点对〇y开始点的约束[ss 1，ss2 ]，ss 1，ss2为约束值域的下界和上界;ox开始点对Oy结束点的 约束[sel，se2]，sel，se2为约束值域的下界和上界;o x结束点对oy开始点的约束[esl，es2]， esl，es2为约束值域的下界和上界;ox结束点点对oy结束点的约束[eel，ee2]，eel，ee2为约 束值域的下界和上界。（ssl，ss2，sel，se2，esl，es2，eel，ee2为任意实数）。
[0017] 步骤3，根据探测器活动变量自身约束，对所有探测器活动变量值域进行自我削 减。
[0018] 自我削减方法为：活动变量~={&，&，心}初始值域为^已[81^82」、^已[ 61^ e2x]和dxe [dlx，d2x]。利用几何表示方法，二维坐标系下开始点值域范围界限为x = slx与X =82。结束点值域范围界限为7 = 6]^与7 = 62\，持续时间值域范围界限为7 = 1+(1]^与7 =叉+ d2x。六条直线相交于12个交点。从12个交点中挑选满足条件的交点：Xe[elx，e2 x]，ye [elx，e2x]，y￡ [x+dlx，x+d2x]。剩余η个点(η < 12)，其中任意一点表示为(xn，yn)。
[0019] 经自我削减后，探测器活动变量0x值域为Sxe[ srx，s2'x]、exe[ el'x，e2'xWPdxe ,sl ,x = min(xn),s2 ,x = max(xn) ,el ,x = min(yn),e2 ,x=max(yn) ,(11^ = min(yn_xn)，d2 'X=max(yn-xn)。其中min表示最小值，max表示最大值。
[0020] 步骤4，从深空探测器活动间约束对中任意选择一对以〇\，<^) = 〃<^〇118(^〃根据(^ 值域和约束关系Cons推导〇y的值域。分别推导〇y的开始点值域、结束点值域和持续时间值 域。
[0021 ]步骤4.1，对于Oy的开始点值域[sly，s2y]，ox和约束[ssl，ss2]、[esl，es2]对[sly, s2y]有影响。在坐标系中，为了两个约束同时满足，〇y的开始点可行区域
[0022] Availablex= [slx+ssl，s2x+ss2] Π [elx+esl，e2x+es2] (1)
[0023] 如果交集为空，则表示没有值同时满足两个约束，整个时间约束处理过程结束，结 论为时间约束不一致，即无法得到满足所有时间约束的活动值域。如果交集不为空，则进行 步骤4.2。
[0024] 步骤4.2,对于oy的结束点值域[ely，e2 y]，ox和约束[sel，se2]和[eel，ee2]对其有 影响。在坐标系中，为了两个约束同时满足，0y的结束点可行区域为
[0025] Availabley= [slx+sel，s2x+se2] Π [elx+eel，e2x+ee2] (2)
[0026] 如果交集为空，则表示没有值同时满足两个约束，整个时间约束处理过程结束，结 论为时间约束不一致，即无法得到满足所有时间约束的活动值域。如果交集不为空，则进行 步骤4.3。
[0027]步骤4.3，对〇y的持续时间值域，由式(3)获得。
[0028] Availabled = dl Π d2 Π d3 Π d4 (3)
[0029] 其中，dl = [sel_ss2, se2_ssl ]，d2=[eel_es2, ee2_esl ]，d3 = [d31，d32]，d4 = [d41，d42];且
[0030] d31=min(dlx-ssl+eel，dlx-ssl+ee2，dlx-ss2+eel，dl x-ss2+ee2)，
[0031 ] d32=max(d2x-ssl+eel，d2x-ssl+ee2，d2x-ss2+eel，d2 x-ss2+ee2)，
[0032] d41=min(-dlx-esl+sel，-dlx-esl+se2，-dlx-es2+sel，-dl x-es2+se2)，
[0033] d42=max(-d2x-esl+sel，-d2x-esl+se2，-d2x-es2+sel，-d2 x-es2+se2) 〇
[0034] min表示几个值中的最小值，max表示几个值中的最大值。
[0035]根据式（1)_(3)，得〇y最后可行值域
[0036] Avai lable= Avai lab lex Π Availabley Π Availablea (4)
[0037] 如果交集为空，则表示没有值同时满足两个约束，整个时间约束处理过程结束，结 论为时间约束不一致，即无法得到满足所有时间约束的活动值域。如果交集不为空，则进行 步骤5。
[0038] 步骤5,步骤4中求出的oy可行值域Available与oy原值域s ye [sly，s2y]，eye [ely, e2y]和dye [dly, d2y]进行几何相交。探测器活动oy开始点新值域为Intersect ionx = Availablex Π [sly，s2y]，探测器活动oy结束点新值域为Intersectiony = Availabley Π [ely，e2y]，探测器活动oy持续时间新值域为Intersectiond = Availabled Π [dly，d2y]。最终 求得〇y新值域Intersection:IntersectionxΠ Intersectiony Π Intersectiond。如果交集 为空，整个时间约束处理过程结束，结论为时间约束不一致，即无法得到满足所有时间约束 的活动值域。如果交集不为空，则进行步骤6。
[0039]步骤6,比较Oy新值域Intersection与原值域是否相同，若不同，则将与Oy相关的约 束对再次加入到约束对集合C中。同时，将约束 对C(〇x，〇y) = "〇xC〇ns 〇/从约束对集合C中 删除。如果相同，则将约束对C(〇x，〇y) = "〇xC〇ns 〇/从约束对集合C中删除即可。
[0040] 步骤7，重复步骤4，、步骤5和步骤6，直到约束对集合C为空。如果步骤中4与步骤5 中没有返回"时间约束不一致"结论，则表示深空探测器所有活动变量满足约束关系，时间 约束一致，所有活动变量得到新值域;如果步骤4与步骤5中返回"时间约束不一致"结论，则 表示深空探测器活动变量无法满足所有约束关系，所有活动变量无法得到新值域，时间规 划结束。
[0041 ] 有益效果
[0042]本发明设计了一种验证时间约束一致性(活动变量值域能够满足所有约束)和约 束几何处理方法，能够快速验证深空探测器规划过程中时间约束的一致性并处理时间约 束，得到活动变量最终值域，弥补采用时间约束网处理大量活动变量时计算时间长的缺点。 与基于时间约束网的时间处理方法相比较，解决同样的时间约束问题，计算时间短、效率 高，更加适合实时性要求高的深空探测器。
【附图说明】
[0043] 图1为本发明方法中活动变量在二维坐标系下的表示方法；
[0044] 图2为【具体实施方式】中四种活动间约束在二维坐标系下的表示方法，其中（a)为步 骤4.1中根据〇x和约束[ssl， SS2]求〇y开始点值域的方法图示，（b)为步骤4.1中根据〇x和约 束[681，682]求0\开始点值域的方法图示，（(3)为步骤4.2中根据(^和约束[861，862]求(^结 束点值域的方法图示，（d)为步骤4.2中根据 〇x和约束[eel，ee2]求〇y结束点值域的方法图 示；
[0045] 图3为【具体实施方式】中活动〇y新值域求解方法；
[0046] 图4为【具体实施方式】中时间约束几何处理方法与时间约束网方法解决相同时间约 束问题的时间比较图。
【具体实施方式】
[0047]本发明的目的是针对目前深空探测器自主任务规划中时间约束处理问题，提出一 种验证时间约束一致性(活动变量值域能够满足所有约束)和约束几何处理方法，是一种在 任务规划活动变量众多的情况下，快速实现时间约束处理，从而满足探测器实时性要求的 方法。
[0048]本发明通过设计时间约束几何处理方法实现，具体实现步骤如下：
[0049] 步骤1，建立深空探测器时间规划问题模型。
[0050] 针对深空探测中的火星探测器建立模型，由探测器系统状态集合、探测器可执行 活动变量集合、活动之间约束集合、初始状态以及目标状态组成，即V={vi，V2, . . .，Vm}。
[0051] 其中，￥={^^2，...，^}为状态变量集合，且7已0￥，0 ￥为火星探测器可达到的状态 值域，m = 28为状态变量的数量，该模型中具有28个状态变量，如探测器姿态系统可处于的 状态有定向、转动等;〇= {〇i，〇2,.. .，on}为探测器可执行活动变量集合，n = 288为活动变量 的数量，即在规划过程中需要处理288个探测器的活动，任意一个探测器活动〇x具有开始点 sx、结束点ex、持续时间dx，即ox= {sx，ex，dx} ;C为探测器活动间的约束集合，此处约束为两 个活动间的时间约束，即C(ox，〇y) = 〃ox Cons oy〃，ox与oy为活动间约束对，Cons为活动间约 束关系，该模型中处理13种约束关系，如表1所示;s。为探测器初始状态，即当时间为0(相对 零点）时，探测器状态变量都对应相应的值;g为目标状态，即探测器各个变量需要达到的 值。
[0052]表1火星探测器活动间约束关系
[0054] 步骤2，对步骤1中探测器活动变量及活动间的时间约束进行表示。
[0055] 在处理时间约束之前，需要对探测器活动变量及时间约束进行表示。
[0056] 1.对探测器活动变量及活动自身约束进行表示。
[0057] 假设探测器活动变量集合0={〇1，〇2，. . .，〇"}中任意一个探测器活动〇x，且〇x = i Sx，ex，dx}。sx为活动〇x的开始点，e x为活动〇x的结束点，dx为活动〇x的持续时间。将活动变量 0x在二维坐标系下进行表示:横坐标为开始点，纵坐标为结束点，y = x+d与纵坐标交点的值 为持续时间。
[0058] 对于探测器活动变量ox= {sx，ex，dx}，自身约束为sxe [slx，s2x]、exe [elx，e2x]和 dxe [dlx，d2x]。其中，slx，s2x为活动o x开始点值域的下界和上界;elx，e2x为活动ox结束点值 域的下界和上界;dl x，d2x为活动ox持续时间值域的下界和上界。如果有相对零点，则slx 2 s2x2 0，slx = s2x时，表示开始点的值域只有一个时刻；同理elx2 e2x 2 0，dlx2 d2x2 0。
[0059] 2.对深空探测器活动间约束进行表示。
[0060] 假设探测器两个活动变量<^={8\&，(^}和(^={8\^，(^}。活动间约束包括(^开 始点对〇y开始点的约束[sS1，SS2 ]，SS 1，SS2为约束值域的下界和上界;ox开始点对Oy结束点 的约束[sel，se2]，sel，se2为约束值域的下界和上界;ox结束点对Oy开始点的约束[esl， es2]，esl，es2为约束值域的下界和上界;ox结束点点对oy结束点的约束[eel，ee2]，eel，ee2 为约束值域的下界和上界。（ssl，ss2，sel，se2，esl，es2，eel，ee2为任意一实数）。
[0061 ]步骤3，根据探测器活动变量自身约束，对所有探测器活动变量值域进行自我削 减。
[0062] 活动变量ox= {sx, ex, dx}初始值域为sxe [slx，s2x]、exe[elx，e2xHPdxe[dlx， d2x]。利用几何表示方法，二维坐标系下开始点值域范围界限为x = s 1 x与x = s2X，结束点值 域范围界限为y = elx与y = e2x，持续时间值域范围界限为y = x+dlx与y = x+d2x。六条直线相 交于12个交点。从12个交点中挑选满足条件的交点：xe[el x，e2x]，ye[elx，e2 x]，ye[x+ dlx，x+d2x]。剩余η个点(η < 12)，其中任意一点表示为(xn，yn)。
[0063] 经自我削减后，探测器活动变量〇x值域为sxe [si 'x，s2'x]、exE [el 'x，e2'x]和dxe ,sl ,x = min(xn),s2 ,x = max(xn) ,el ,x = min(yn),e2 ,x=max(yn) ,(11^ = min(yn_xn)，d2 'X=max(yn-xn)。其中min表示最小值，max表示最大值。
[0064] 步骤4，从深空探测器活动间约束对中任意选择一对C(ox，〇y) = 〃oxCons oy〃，其中 Cons指步骤2中活动间的约束关系。根据〇x值域和约束关系Cons推导〇y的值域。推导时分三 种情况进行，即推导〇y的开始点值域、结束点值域和持续时间值域。
[0065] 步骤4.1，对于Oy的开始点值域[sly，s2y]，〇x和约束[ssl，ss2]和[esl，es2]对[sly, s2y]有影响。在坐标系中，为了两个约束同时满足，〇y的开始点可行区域
[0066] Availablex= [slx+ssl，s2x+ss2] Π [elx+esl，e2x+es2] (1)
[0067] 如果交集为空，则表示没有值同时满足两个约束，整个时间约束处理过程结束，结 论为时间约束不一致，即无法得到满足所有时间约束的活动值域。如果交集不为空，则进行 后续步骤。
[0068] 步骤4.2，同理，对于％的结束点值域[61^62」，0\和约束[861，862]和[661，662] 对[el y，e2y]有影响。在坐标系中，为了两个约束同时满足，Oy的结束点可行区域为
[0069] Availabley= [slx+sel，s2x+se2] Π [elx+eel，e2x+ee2] (2)
[0070] 如果交集为空，则表示没有值同时满足两个约束，整个时间约束处理过程结束，结 论为时间约束不一致，即无法得到满足所有时间约束的活动值域。如果交集不为空，则进行 后续步骤。
[0071 ]步骤4.3，对〇y的持续时间值域，由式(3)获得。
[0072] Availabled = dl Π d2 Π d3 Π d4 (3)
[0073] 其中，dl = [sel_ss2, se2_ssl ]，d2=[eel_es2, ee2_esl ]，d3 = [d31，d32]，d4 = [d41，d42];且
[0074] d31=min(dlx-ssl+eel，dlx-ssl+ee2，dlx-ss2+eel，dl x-ss2+ee2)，
[0075] d32=max(d2x-ssl+eel，d2x-ssl+ee2，d2x-ss2+eel，d2 x-ss2+ee2)，
[0076] d41=min(-dlx-esl+sel，-dlx-esl+se2，-dlx-es2+sel，-dl x-es2+se2)，
[0077] d42=max(-d2x-esl+sel，-d2x-esl+se2，-d2x-es2+sel，-d2 x-es2+se2) 〇
[0078] min表示几个值中的最小值，max表示几个值中的最大值。
[0079]根据式（1)-(3)，得〇y最后可行值域
[0080] Avai lable= Avai lab lex Π Availabley Π Availablea (4)
[0081] 如果交集为空，则表示没有值同时满足两个约束，整个时间约束处理过程结束，结 论为时间约束不一致，即无法得到满足所有时间约束的活动值域。如果交集不为空，则进行 后续步骤。
[0082] 步骤5,步骤4中求出的oy可行值域Available与oy原值域s ye [sly，s2y]，eye [ely, e2y]和dye [dly, d2y]进行几何相交。探测器活动oy开始点新值域为Intersect ionx = Availablex Π [sly，s2y]，探测器活动oy结束点新值域为Intersectiony = Availabley Π [ely，e2y]，探测器活动oy持续时间新值域为Intersec tiond = Availabled Π [dly，d2y]。最终 求得〇y新值域Intersection:IntersectionxΠ Intersectiony Π Intersectiond。如果交集 为空，整个时间约束处理过程结束，结论为时间约束不一致，即无法得到满足所有时间约束 的活动值域。如果交集不为空，则进行后续步骤。
[0083] 步骤6,比较〇y新值域Intersection与原值域是否相同，若不同，则将与〇y相关的约 束对再次加入到约束对集合C中。同时，将约束对C( 〇x，〇y) = "〇xC〇ns 〇/从约束对集合C中 删除。如果相同，则将约束对C(〇x，〇y) = "〇xC〇ns 〇/从约束对集合C中删除即可。
[0084] 步骤7，重复步骤4，步骤5和步骤6，直到约束对集合C为空，步骤中4与步骤5中没有 返回"时间约束不一致"结论，深空探测器所有活动变量满足约束关系，时间约束一致，所有 活动变量得到新值域。
[0085] 在该例子中，活动变量数为288，计算时间为16.732383s，利用时间约束网时间为 950.28626s，效率提高了一个数量级，更加适合火星探测实时性要求。
[0086]图4是时间约束几何处理方法与时间约束网方法解决相同时间约束问题的时间比 较图。图中：虚线部分表示时间约束几何处理方法;实线部分表示时间约束网方法。横坐标 是问题中的活动变量数，纵坐标是计算时间（取e为底对数）。由图中可看出，时间约束几何 处理方法比时间约束网方法计算时间低三个数量级，随着活动数量增加，几何处理方法时 间保持平稳，而时间约束网方法不断增加。
【主权项】
1.一种深空探测器自主任务规划时间约束几何处理方法，其特征在于：具体实现步骤 如下： 步骤1，建立深空探测器时间规划问题模型； 深空探测器时间规划问题由探测器系统状态集合、探测器可执行活动变量集合、活动 间的约束集合、探测器初始状态以及目标状态组成，即V= {V1，V2，. . .，Vm}; 其中，V= {V1，V2，. . .，Vm}为状态变量集合，且VeDv，Dv为探测器能达到的状态值域，m为 状态变量的数量;0= {〇1，02,...，〇n}为探测器可执行的活动变量集合，η为活动变量的数 量，任意一个探测器活动〇\具有开始点8\、结束点6\、持续时间(^，即0\={8\，6\，(1山(：为探测 器活动间的约束集合，此处约束为两个活动间的时间约束，即c(〇x，〇y) =〃〇xCons〇y〃，〇χ与 〇y为活动间约束对，Cons为活动间约束关系;S。为探测器初始状态，即当相对零点时，探测器 状态变量都对应相应的值;g为目标状态，即探测器各个变量需要达到的值； 步骤2,对步骤1中探测器活动变量及活动间的时间约束进行表示； 在处理时间约束之前，需要对探测器活动变量及时间约束进行表示；1. 对探测器活动变量及活动自身约束进行表示； 设探测器活动变量集合〇= {〇1，〇2, . . .，〇n}中任意一个探测器活动0X，且0X= {sx，ex,dx};将活动变量0X在二维坐标系下进行表示:横坐标X为开始点，纵坐标y为结束点，y=x+dx 与纵坐标交点的值为持续时间； 对于探测器活动变量〇x= {sx，ex，dx}，自身约束为sxe[slx，s2x]、exe[elx，e2x]和dxe [d1x，d2x];其中，s1x，s2X为活动ox开始点值域的下界和上界;e1x，e2X为活动ox结束点值域的 下界和上界;dlx，d2x为活动〇x持续时间值域的下界和上界;如果有相对零点，则slx2s2x2 0;slx=s2x时，表示开始点的值域只有一个时亥IJ;同理elx 2e2x 2 0，dlx 2d2x 2 0;2. 对深空探测器活动间约束进行表示； 设探测器两个活动变量〇\={8\，6\，(^}和(^={8\，6\，(^};活动间约束包括(^开始点对(^ 开始点的约束[Ss1，ss2 ]，ss1，ss2为约束值域的下界和上界;ox开始点对〇y结束点的约束 [sel，se2]，sel，se2为约束值域的下界和上界;ox结束点对oy开始点的约束[esl，es2]，esl， es2为约束值域的下界和上界;ox结束点点对oy结束点的约束[eel，ee2]，eel，ee2为约束值 域的下界和上界;ssl，ss2，sel，se2，esl，es2，eel，ee2为任意实数； 步骤3，根据探测器活动变量自身约束，对所有探测器活动变量值域进行自我削减； 自我削减方法为:活动变量〇x= {sx，ex，dx}初始值域为sxe[Slx，S2X]、exe[elx，e2x]和dxe[dlx，d2x];利用几何表示方法，二维坐标系下开始点值域范围界限为x=slx与x=s2x， 结束点值域范围界限为y=elx与y=e2x，持续时间值域范围界限为y=x+dlx与y=x+d2x;六 条直线相交于12个交点;从12个交点中挑选满足条件的交点:Xe[elx，e2x]，ye[elx，e2x]， ye[x+dlx，x+d2x];剩余η个点，η< 12,其中任意一点表示为(xn，yn); 经自我削减后，探测器活动变量〇χ值域为sxe[sl'x，s2'x]、exe[el'x，e2'x^Pdxe ,sl,x =min(xn),s2,x =max(xn),el,x =min(yn),e2 ,x=max(yn) ,(11^ = min(yn-xn)，d2'x=max(yn-xn);其中min表示最小值，max表示最大值； 步骤4,从深空探测器活动间约束对中任意选择一对C(〇x，〇y) = "〇xC〇ns〇y"根据〇x值域 和约束关系Cons推导〇y的值域;分别推导〇y的开始点值域、结束点值域和持续时间值域； 步骤4.1，对于Oy的开始点值域[sly，s2y]，ox和约束[ssl，ss2]、[esl，es2]对[sly，s2y] 有影响;在坐标系中，为了两个约束同时满足，0y的开始点可行区域 Availablex = [slx+ssl，s2x+ss2]Π[elx+esl，e2x+es2] (1) 如果交集为空，则表示没有值同时满足两个约束，整个时间约束处理过程结束，结论为 时间约束不一致，即无法得到满足所有时间约束的活动值域;如果交集不为空，则进行步骤 4.2； 步骤4.2,对于oy的结束点值域[ely，e2y]，ox和约束[sel，se2]和[eel，ee2]对其有影响； 在坐标系中，为了两个约束同时满足，〇y的结束点可行区域为 Availabley= [slx+sel，s2x+se2]Π[elx+eel，e2x+ee2] (2) 如果交集为空，则表示没有值同时满足两个约束，整个时间约束处理过程结束，结论为 时间约束不一致，即无法得到满足所有时间约束的活动值域;如果交集不为空，则进行步骤 4.3； 步骤4.3，对〇y的持续时间值域，由式(3)获得； Availabled=dlΠd2Πd3Πd4 (3) 其中，dl = [sel_ss2, se2_ssl ]，d2=[eel_es2, ee2_esl ]，d3= [d31，d32]，d4 = [d41，d42];且d31=min(dlx-ssl+eel，dlx-ssl+ee2，dlx-ss2+eel，dlx-ss2+ee2)，d32=max(d2x-ssl+eel，d2x-ssl+ee2，d2x_ss2+eel，d2x-ss2+ee2)，d41=min(-dlx-esl+sel，_dlx-esl + se2，_dlx-es2+sel，_dlx-es2+se2)，d42 = max(-d2x-esl+sel，_d2x-esl+se2，_d2x-es2+ sel，-d2x_es2+se2) ;min表示几个值中的最小值，max表示几个值中的最大值； 根据式(1)-(3)，得〇y最后可行值域 Available=AvailablexΠAvailableyΠAvailablea(4) 如果交集为空，则表示没有值同时满足两个约束，整个时间约束处理过程结束，结论为 时间约束不一致，即无法得到满足所有时间约束的活动值域;如果交集不为空，则进行步骤 5； 步骤5,步骤4中求出的Oy可行值域Available与Oy原值域Sye[sly，s2y]，ey￡ [ely，e2y] 和dy￡ [dly，d2y]进行几何相交;探测器活动〇y开始点新值域为Intersectionx=Availablex Π[sly，s2y]，探测器活动〇y结束点新值域为Intersectiony =AvailableyΠ[ely，e2y]，探测 器活动〇y持续时间新值域为Intersectiond=AvailabledΠ[dly，d2y];最终求得oy新值域 Intersection=IntersectionxΠIntersectionyΠIntersectiond;如果交集为空，整个时 间约束处理过程结束，结论为时间约束不一致，即无法得到满足所有时间约束的活动值域； 如果交集不为空，则进行步骤6; 步骤6,比较〇y新值域Intersection与原值域是否相同，若不同，则将与〇y相关的约束对 再次加入到约束对集合C中；同时，将约束对C(〇x，〇y) = "〇xC〇ns〇/从约束对集合C中删除； 如果相同，则将约束对C(〇x，〇y) = "〇xC〇ns〇/从约束对集合C中删除即可； 步骤7，重复步骤4，、步骤5和步骤6，直到约束对集合C为空；如果步骤中4与步骤5中没 有返回"时间约束不一致"结论，则表示深空探测器所有活动变量满足约束关系，时间约束 一致，所有活动变量得到新值域;如果步骤4与步骤5中返回"时间约束不一致"结论，则表示 深空探测器活动变量无法满足所有约束关系，所有活动变量无法得到新值域，时间规划结 束。
【专利摘要】本发明涉及一种深空探测器自主任务规划时间约束几何处理方法，属于深空探测技术领域。本发明设计了一种验证时间约束一致性(活动变量值域能够满足所有约束)和约束几何处理方法，能够快速验证深空探测器规划过程中时间约束的一致性并处理时间约束，得到活动变量最终值域，弥补采用时间约束网处理大量活动变量时计算时间长的缺点。与基于时间约束网的时间处理方法相比较，解决同样的时间约束问题，计算时间短、效率高，更加适合实时性要求高的深空探测器。
【IPC分类】G05D1/08, G05D1/10
【公开号】CN105487546
【申请号】CN201510883280
【发明人】徐瑞, 李朝玉, 崔平远, 朱圣英, 高艾, 乔栋, 尚海滨
【申请人】北京理工大学
【公开日】2016年4月13日
【申请日】2015年12月4日
最新回复(0)