Partition satellite mission planning method for earliest completion of regional target coverage

Abstract

The present invention discloses a partition satellite mission planning method for earliest completion of regional target coverage, which includes the following steps: 1. partitioning a to-be-observed rectangular region; 2. allocating observation resources to different regions and selecting certain coverage opportunities and coverage modes thereof to minimize completion time corresponding to a formed coverage solution. The present invention can obtain a satisfactory solution capable of finishing complete coverage of regional targets as early as possible with sufficient observation resources through suitable calculation resources and achieve balance between the consumption of calculation resources and optimality of solutions, so that satellite resources can be fully used to conduct the quick and effective coverage search for important regional targets in a real environment.

Claims

1. A partition satellite mission planning method for earliest completion of regional target coverage, wherein the partition satellite mission planning method comprises: step 1: partitioning a to-be-observed rectangular region R; step 2: allocating observation resources to different regions, and selecting a coverage opportunity and a coverage mode thereof to minimize a completion time of a formed coverage solution, comprising: step 2.1: randomly allocating the coverage opportunity to each subregion to form an initial current allocation solution Y={y.sub.s|∇s∈S}, wherein the value of y.sub.s represents the subregion where the coverage opportunity s is allocated, and S represents a coverage opportunity set; step 2.2: calculating the coverage opportunity set S*(Y) selected under the current allocation solution Y, a better coverage mode set C*(Y) and corresponding completion time F(Y); step 2.3: setting maximum iteration times k and initial annealing temperature T.sub.1, and setting iteration times of a current outer cycle as k=1; step 2.4: if k>k, carrying out step 2.9; otherwise, carrying out step 2.5; step 2.5: using an insert operator and an exchange operator to construct a plurality of neighbor allocation solutions of the current allocation solution Y; step 2.6: calculating the coverage opportunity set selected under each neighbor allocation solution, better coverage mode set and corresponding completion time separately, and selecting the neighbor allocation solution with minimum completion time as the optimal neighbor allocation solution Y*; step 2.7: comparing the completion time of the optimal neighbor allocation solution Y* with the completion time of the current allocation solution Y; if F(Y*)≤F(Y), assigning the optimal neighbor allocation solution Y* to the current allocation solution Y, and then carrying out step 2.8 directly; otherwise, carrying out step 2.8 after the step 2.7.1-step 2.7.2; step 2.7.1: calculating an inferior solution accept rate $P_{k} = \exp {\frac{F (Y) - F ({\overline{Y}}^{*})}{T_{k}}}$ k.sup.th iteration; step 2.7.2: generating a random number r.sub.k of 0-1 at k.sup.th times; if r.sub.k≤p.sub.k, assigning the optimal neighbor allocation solution Y* to the current allocation solution Y; step 2.8: assigning k+1 to k, and updating the annealing temperature T.sub.k=T.sub.k-1×λ, wherein λ is a cooling coefficient and is a fixed value less than 1 and greater than 0; and then carrying out step 2.4; step 2.9: outputting the current allocation solution Y as well as the overall selected coverage opportunity set S*(Y) under the allocation solution, better coverage modes C*(Y) of each coverage opportunity and corresponding completion time F(Y).

2. The partition satellite mission planning method according to claim 1, wherein the step 1 is carried out as follows: step 1.1: setting length L.sub.p and width W.sub.p of each subregion; step 1.2: calculating the length L.sub.R and width W.sub.R of the to-be-observed rectangular region R according to the coordinates of four vertexes of the to-be-observed rectangular region R; step 1.3: dividing L.sub.p by L.sub.R to obtain length section number D.sub.L and remainder R.sub.L of the subregion; if the remainder $R_{L} \geq \frac{D_{L}}{2 D_{L} + 1} L_{p},$ assigning D.sub.L+1 to D.sub.L; dividing W.sub.p by W.sub.R to obtain width section number D.sub.W and remainder R.sub.W of the subregion, and if the remainder $R_{W} \geq \frac{D_{W}}{2 D_{W} + 1} W_{p},$ assigning D.sub.W+1 to D.sub.W; step 1.4: dividing L.sub.R by D.sub.L to obtain length L.sub.f of the final subregion, and dividing W.sub.R by D.sub.W to obtain width W.sub.f of the final subregion; step 1.5: according to the length L.sub.f and width W.sub.f of the final subregion, equally partitioning the to-be-observed rectangular region R, thereby obtaining the coordinates of four vertexes of each subregion, comprising: step 1.5.1: if i=1, using the left upper corner coordinate LU(R) of the to-be-observed rectangular region R as the left upper corner coordinate LU(n.sub.i) of the i.sup.th subregion n.sub.i; step 1.5.2: adding an abscissa value of the left upper corner coordinate LU(n.sub.i) of the i.sup.th subregion n.sub.i, and L.sub.f to obtain the right upper corner coordinate RU(n.sub.i) thereof; adding an ordinate value of the left upper corner coordinate LU(n.sub.i) and W.sub.f to obtain the left lower corner coordinate LD(n.sub.i) thereof; and adding the ordinate value of the right upper corner coordinate RU(n.sub.i) and W.sub.f to obtain the right lower coordinate RD(n.sub.i); step 1.5.3: if the right lower corner coordinate RD(n.sub.i) of the i.sup.th subregion n.sub.i is equal to the right lower corner coordinate RD(R) of the to-be-observed rectangular region R, carrying out step 1.5.6; otherwise, carrying out step 1.5.4; step 1.5.4: if the abscissa value of the right upper corner coordinate RU(n.sub.i) of the i.sup.th subregion n.sub.i is equal to the abscissa value of the right upper corner coordinate RU(R) of the to-be-observed rectangular region R, using LD(n.sub.(i−D.sub.L.sub.+1)) as the left upper corner coordinate LU(n.sub.i+1) of the (i+1).sup.th subregion n.sub.i+1; otherwise, using the right upper corner coordinate RU(n.sub.i) of the i.sup.th subregion n.sub.i as the left upper corner coordinate LU(n.sub.i+1) of the (i+1).sup.th subregion n.sub.i+1; step 1.5.5: after i+1 is assigned to i, carrying out step 1.5.2 to construct the coordinates of four vertexes of a next subregion; step 1.5.6: ending the partitioning, and outputting the coordinates of four vertexes of each subregion; step 1.6: obtaining a set N of the subregions, and the total number of the subregions of |N|=D.sub.L×D.sub.W.

3. The partition satellite mission planning method according to claim 1, wherein the step 2.5 is carried out as follows: step 2.5.1: setting the number of the to-be-constructed neighbor allocation solutions as m, and setting the number of the constructed neighbor allocation solutions as m, and m=0; step 2.5.2: using the insert operator to construct the neighbor allocation solution, comprising step 2.5.2.1-step 2.5.2.4: step 2.5.2.1: finding an idle coverage opportunity ŝ from an unselected coverage opportunity set S′(Y)={S/S*(Y)} under the current allocation solution Y, wherein the end time β(ŝ) of the idle coverage opportunity ŝ is smaller than the overall completion time F(Y) but greater than the completion time F.sub.y.sub.ŝ(Y) that the idle coverage opportunity ŝ is allocated to the subregion y.sub.ŝ; if the idle coverage opportunity is not found, carrying out step 2.5.2.4; otherwise, carrying out step 2.5.2.2; step 2.5.2.2: assigning m+1 to m, and randomly allocating the idle coverage opportunity ŝ in the current allocation solutions Y to one subregion, wherein the end time β(ŝ) of the idle coverage opportunity ŝ is smaller than the completion time of the allocated subregion, thereby forming a neighbor allocation solution Y.sub.m; step 2.5.2.3: removing the idle coverage opportunity s from the coverage opportunity set S′(Y), and then carrying out step 2.5.2.1; step 2.5.2.4: outputting all neighbor allocation solutions obtained by utilizing the insert operator; step 2.5.3: using the exchange operator to construct the neighbor allocation solution, comprising step 2.5.3.1-step 2.5.3.3: step 2.5.3.1: if m≥m, carrying out step 2.5.3.3; otherwise, carrying out step 2.5.3.2; step 2.5.3.2: assigning m+1 to m; randomly selecting two subregions n.sub.i and n.sub.j from the subregion set N; randomly selecting one coverage opportunity s.sub.i from the coverage opportunity set {s|y.sub.s=n.sub.i} allocated to the subregion n.sub.i; randomly selecting one coverage opportunity s.sub.j from the coverage opportunity set {s|y.sub.s=n.sub.j} allocated to the subregion n.sub.j; exchanging s.sub.i and s.sub.j in the current allocation solution Y, that is, assigning n.sub.j to y.sub.s.sub.i, and assigning n.sub.i to y.sub.s.sub.j, thereby forming a neighbor coverage solution Y.sub.m, and then carrying out step 2.5.3.1; step 2.5.3.3: outputting all neighbor allocation solutions obtained by using the exchange operator.

4. The partition satellite mission planning method according to claim 1, wherein the step 2.2 and the step 2.6 of calculating the selected coverage opportunity set under the given allocation solution, a better coverage mode set selected for each coverage opportunity and corresponding completion time are carried out as follows: step a: using different subregions and the set of coverage opportunities allocated to different subregions as inputs to construct grids, and using a two-phase heuristic algorithm to calculate the coverage opportunity set selected for local part of different subregions as well as the better coverage solution and corresponding completion time; step a.1: dividing the i.sup.th subregion n.sub.i into a plurality of consistent square grids to obtain a grid set J.sub.i; step a.2: according to the divided grid set J.sub.i, generating a longest basic coverage mode for the coverage opportunity set S.sub.i allocated to the i.sup.th subregion n.sub.i, and forming an optional coverage mode set C.sub.i, wherein the longest basic coverage mode refers to that the length is equal to the maximum length r.sub.s, and the following two types of grids exist: (1) one type of grids is completely covered by the coverage mode, that is, the four vertexes are within the area covered by the coverage mode; (2) one grid has a vertex located on a left border of the coverage mode and is named left grid, and the other grid has a vertex located on an upper border of the coverage mode and is named upper grid, wherein the left grid and the upper grid is overlapped; step a.3: by utilizing the grid set J.sub.i separated from i.sup.th subregion n.sub.i as well as the coverage opportunity set S.sub.i={s|y.sub.s=n.sub.i, s∈S} allocated to i.sup.th subregion n.sub.i and the optional coverage mode set C.sub.i as inputs, determining the coverage opportunity subset S.sub.i* selected by the i.sup.th subregion n.sub.i by the two-phase heuristic algorithm, and selecting the coverage mode of each coverage opportunity, in order to obtain the better coverage mode set C.sub.i* and the completion time F.sub.i thereof; step b: combining the coverage opportunity sets {S.sub.i*|i=1, 2, . . . , |N|} selected by all subregions to obtain an overall selected coverage opportunity set S*; combining the coverage solutions {C.sub.i*|i=1, 2, . . . , |N|} of all subregions to obtain an overall coverage solution C* of the to-be-observed rectangular region R; and using the maximum value of the completion time {F.sub.i*|i=1, 2, . . . , |N|} corresponding to the coverage solutions of all subregions as the overall completion time F of the to-be-observed rectangular region R.

5. The partition satellite mission planning method according to claim 4, wherein the step a.2 of generating a longest basic coverage mode for the coverage opportunity set according to the grid set and forming the optional coverage mode set is carried out as follows: step a.2.1: if S.sub.i=Ø, carrying out step a.2.4; otherwise, carrying out step a.2.2; step a.2.2: selecting one of coverage opportunities s∈S.sub.i and according to the type of the coverage opportunity s, using methods in step a.2.2.1 to step a.2.2.10 to construct a longest basic coverage mode set C.sub.s based on the grid set J.sub.i for the coverage opportunity s; step a.2.2.1: judging the type of the coverage opportunity s according to a sub-satellite point track o.sub.s of the coverage opportunity s, and the types including a right lower corner oblique type and a left lower corner oblique type; step a.2.2.2: making the longest basic coverage mode set as C.sub.s=Ø; step a.2.2.3: selecting subsets J.sub.s from the grid set J.sub.i, and using each grid in the subsets J.sub.s as the left grid of the longest basic coverage mode of the coverage opportunity s; step a.2.2.3.1: setting J.sub.s=Ø; step a.2.2.3.2: traversing the set J.sub.i, and calculating a camera roll angle $σ_{s} (u) = \arctan \frac{d_{s}^{u}}{h_{s}} - \frac{w_{s}}{2}$ of the coverage opportunity S when each grid u is used as the left grid of the coverage mode, wherein if the coverage opportunity is the left lower corner oblique type, d.sub.s.sup.u is a distance between the left lower corner vertex LD(u) of the grid u and the sub-satellite point track o.sub.s of the coverage opportunity s; if the coverage opportunity is the left lower corner oblique type, d.sub.s.sup.u is a distance between the left upper corner vertex LU(u) of the grid u and the sub-satellite point track o.sub.s of the coverage opportunity s; if |σ.sub.s(u)|≤v.sub.s, adding the grid u into the subset J.sub.s of the left grid; step a.2.2.4: if J.sub.s=Ø, carrying out step a.2.2.10; otherwise, after one grid P in J.sub.s is selected, carrying out step 2.2.1.2.2.5; step a.2.2.5: according to the grid p, selecting the grid subset J.sub.s.sup.p from the grid set J.sub.i, and when p is used as the left grid, using each grid in J.sub.s.sup.p as the upper grid to form a longest basic coverage mode of the coverage opportunity s together with p; step a.2.2.6: if J.sub.s.sup.p=Ø, carrying out step a.2.2.9; otherwise, after one grid q in J.sub.s.sup.p is selected, carrying out step a.2.2.7; step a.2.2.7: based on the grids p and q, constructing the longest basic coverage c.sub.s(p,q) belonging to the coverage opportunity s; step a.2.2.8: adding c.sub.s(p,q) into C.sub.s, removing the grid q from J.sub.s.sup.p, and then carrying out step a.2.2.6; step a.2.2.9: removing the grid p from J.sub.s, and then carrying out step a.2.2.4; step a.2.2.10: outputting the coverage mode set C.sub.s; step a.2.3: removing the coverage mode opportunity s from S.sub.i, and then carrying out step a.2.1; step a.2.4: if C.sub.i{c.sub.s|∀c.sub.s∈C.sub.s,∀s∈S.sub.i}, outputting the coverage mode set C.sub.i.

6. The partition satellite mission planning method according to claim 5, wherein the step a.2.2.5 is carried out as follows: step a.2.2.5.1: setting J.sub.s.sup.p=Ø; step a.2.2.5.2: calculating a strip width n.sub.s(p) of the coverage mode when the grid p is used as the left grid by using the formula (1): $\begin{matrix} η_{s} (p) = {\begin{matrix} d_{s}^{p} - h_{s} .Math. \tan (\arctan \frac{d_{s}^{p}}{h_{s}} - w_{s}), & \arctan \frac{d_{s}^{p}}{h_{s}} > w_{s} \\ d_{s}^{p} + h_{s} .Math. \tan (w_{s} - \arctan \frac{d_{s}^{p}}{h_{s}} - w_{s}), & \arctan \frac{d_{s}^{p}}{h_{s}} \leq w_{s} \end{matrix} & (1) \end{matrix}$ step a.2.2.5.3: traversing the set J.sub.i; checking whether one grid t satisfies the following four conditions; if all conditions are satisfied, adding the grid t into J.sub.s.sup.p; otherwise, checking the next grid; if the coverage opportunity is the right lower corner oblique type, the four conditions are: (1) making the straight line L.sub.p∥o.sub.s through the left lower corner vertex of the grid p, making the straight line L.sub.t′∥o.sub.s through the right upper corner vertex of t, and ensuring that the distance between the straight lines L.sub.p and L.sub.t′ do not exceed the width η.sub.s(p) of the strip; (2) making the straight lines L.sub.p′⊥s and L.sub.t⊥o.sub.s respectively through the left upper corner vertexes of the grids p and t, and enabling L.sub.t to be above L.sub.p′; (3) making the straight line L.sub.t∥o.sub.s through the left lower corner vertex of the grid t, and enabling the straight line L.sub.t to be at the right side of L.sub.p; (4) making the straight line L.sub.p⊥o.sub.s through the right lower corner vertex of the grid p, and ensuring that the distance between the straight lines L.sub.p and L.sub.t do not exceed the length l.sub.s of the strip, wherein “∥” indicates a parallel relation, and “⊥” indicates a vertical relation; if the coverage opportunity is the left lower corner oblique type, the four conditions are: (1) making the straight line L.sub.p∥o.sub.s through the left upper corner vertex of the grid p, making the straight line L.sub.t′∥o.sub.s through the right upper corner vertex of t, and ensuring that the distance between the straight lines L.sub.p and L.sub.t′ do not exceed the width η.sub.s(p) of the strip; (2) making the straight lines L.sub.p′⊥o.sub.s and L.sub.t⊥o.sub.s respectively through the right upper corner vertexes of the grids p and t, and enabling L.sub.t to be above L.sub.p′; (3) making the straight line L.sub.t∥o.sub.s through the left upper corner vertex of the grid t, and enabling the straight line L.sub.t to be at the right side of L.sub.p; (4) making the straight line L.sub.p⊥o.sub.s through the left lower corner vertex of the grid p, and ensuring that the distance between the straight lines L.sub.p and L.sub.t do not exceed the length l.sub.s of the strip, wherein “∥” indicates a parallel relation, and “⊥” indicates a vertical relation.

7. The partition satellite mission planning method according to claim 5, wherein the step a.2.2.7 is carried out as follows: step a.2.2.7.1: if the coverage opportunity is the right lower corner oblique type, making the straight line L.sub.p∥o.sub.s through the left lower corner vertex LD(p) of the grid p, and making the straight line L.sub.q⊥o.sub.s through the left upper corner vertex LU(q) of the grid q; if the coverage opportunity is the left lower corner oblique type, making the straight line L.sub.p∥o.sub.s is made through the left upper corner vertex LU(p) of the grid p, and making the straight line L.sub.q⊥o.sub.s through the right upper corner vertex RU(q) of the grid q; step a.2.2.7.2: calculating the strip width η.sub.s(p) of the coverage mode when the grid p is used as the left grid; step a.2.2.7.3: making the straight line L.sub.p in order to satisfy: (1) L.sub.p∥L.sub.p; (2) the distance between L.sub.p and L.sub.p is equal to η.sub.s(p); (3) L.sub.p is at the right side of L.sub.p; step a.2.2.7.4: making the straight line L.sub.q in order to satisfy: (1) L.sub.q∥L.sub.q; (2) the distance between L.sub.q and L.sub.q is equal to l.sub.s; (3) L.sub.q is at the lower side of L.sub.q; step a.2.2.7.5: using four straight lines of L.sub.p, L.sub.p, L.sub.q, L.sub.q as four sides of the rectangle, and using intersections of the four straight lines as four vertexes of the rectangle to construct the coverage mode c.sub.s(p,q).

8. The partition satellite mission planning method according to claim 4, wherein the step a.3 is carried out as follows: step a.3.1: by utilizing the grid set J.sub.i, the coverage opportunity set S.sub.i and the corresponding coverage mode set C.sub.i as inputs, calculating the selected coverage opportunity subsets S.sub.i*, the selected coverage mode sets C.sub.i* and the number A.sub.i of corresponding coverable grids with the heuristic algorithm; step a.3.2: if A.sub.i<|J.sub.i|, with |J.sub.i| indicating the number of elements in the set carrying out step a.3.4; otherwise, carrying out step a.3.3; step a.3.3: optimizing S.sub.i* and C.sub.i* by using a promotion algorithm; step a.3.3.1: removing one coverage opportunity $s_{m} = \arg \max_{\forall s \in S_{i}^{*}} β (s)$ with maximum end time in S.sub.i* from S.sub.i* to obtain the coverage opportunity set S.sub.i; step a.3.3.2: by utilizing the grid set J.sub.i, the coverage opportunity set S.sub.i and the optional coverage mode set C.sub.i={c|∀c∈C.sub.s,∀s∈S.sub.i} corresponding to S.sub.i as inputs, calculating the selected coverage opportunity subsets S.sub.i*, the selected coverage mode set C.sub.i* and the number A.sub.i of the corresponding coverable grids with the heuristic algorithm; step a.3.3.3: if A.sub.i=|J.sub.i|, assigning S.sub.i* to S.sub.i*, and assigning C.sub.i* to C.sub.i*; carrying out step a.3.3.1; otherwise, carrying out step a.3.4; step a.3.4: outputting the selected coverage opportunity set S.sub.i* and the coverage mode set C.sub.i*; and using the maximum value of the end time of the coverage opportunity in S.sub.i* as the completion time F.sub.i.

9. The partition satellite mission planning method according to claim 8, wherein the step a.3.1 is carried out as follows: step a.3.1.1: sorting all coverage opportunities in S.sub.i in a non-descending order according to the end time to obtain $\overset{.Math.}{S_{i}} = {s_{1}, s_{2}, .Math., s_{| \overset{.Math.}{s_{i} |}}};$ step a.3.1.2: setting the state of all grids in J.sub.i as “uncovered”; g=0, wherein g indicates the subscript of the g.sup.th coverage mode in the coverage mode set C.sub.i* ; C.sub.i*=Ø; step a.3.1.3: assigning g+1 to g; extracting the coverage opportunity s.sub.g from S.sub.i; traversing the optional coverage mode set C.sub.s.sub.g; for each coverage mode c.sub.s.sub.g, selecting the grid capable of being completely covered by c.sub.s.sub.g and with the state of “uncovered” from the grid set J.sub.i and marking as valid grid sets V(c.sub.s.sub.g), and marking the number as |V(c.sub.s.sub.g)|; step a.3.1.4: selecting the coverage mode $c_{s_{g}}^{*} = \arg \max_{\forall c_{s_{g}} \in C_{s_{g}}} | V (c_{s_{g}}) |$ covering the most valid grids from C.sub.s.sub.g to serve as the coverage mode selected by the coverage opportunity s.sub.g; after c.sub.s.sub.g* is added into C.sub.i*, changing the state of all grids in the valid grid sets V(c.sub.s.sub.g) of the coverage mode c.sub.s.sub.g* as “covered”; step a.3.1.5: calculating the number of all grids with the state of “covered” in J.sub.i and marking as A.sub.i; step a.3.1.6: if A.sub.i=|J.sub.i| or g=|S.sub.i|, carrying out step a.3.1.7; otherwise, carrying out step a.3.1.3; step a.3.1.7: outputting the coverage opportunity subset S.sub.i*={s.sub.1, s.sub.2, . . . , s.sub.g} as well as the coverage mode set C.sub.i* thereof and the number A.sub.i of covered grids.

10. The partition satellite mission planning method according to claim 8, wherein the step a.3.3.2 is carried out as follows: step a.3.3.2.1: setting the state of all grids in J.sub.i as “uncovered”, and C.sub.i*=Ø; step a.3.3.2.2: g=1, wherein g indicates the subscript of the g.sup.th coverage mode in the coverage mode set C.sub.i*; step a.3.3.2.3: if g>|C.sub.i|, carrying out step a.3.3.2.5; otherwise, carrying out step a.3.3.2.4; step a.3.3.2.4: selecting the g.sup.th coverage mode in C.sub.i, and selecting the grids capable of being completely covered by the g.sup.th coverage mode and with the state of “uncovered” from the grid set J.sub.i and marking as valid grid set V(g), and marking the number as |V(g)|; assigning g+1 to g; and carrying out step a.3.3.2.3; step a.3.3.2.5: if C.sub.i=Ø, carrying out step a.3.3.2.8; otherwise, carrying out step a.3.3.2.6; step a.3.3.2.6: selecting the coverage mode ${\overline{g}}^{*} = \arg \max_{\forall \overline{g} \in \overline{C_{i}}} | V (\overline{g}) |$ with most valid grids in C.sub.i to serve as the coverage mode selected by the corresponding coverage opportunity s*; adding g* into C.sub.i*, and changing the state of all grids in the valid grid set V(g*) of the coverage mode g* to be “covered”; step a.3.3.2.7: removing the coverage mode set C.sub.s* corresponding to the coverage opportunity s* from the optional coverage mode set C.sub.i, and then carrying out step a.3.3.2.2; step a.3.3.2.8: outputting the coverage mode set C.sub.i* selected by each coverage opportunity, that is the final coverage solution; and calculating the number of all “covered” grids in J.sub.i and marking as A.sub.i.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a flow chart of a partition satellite mission planning method for earliest completion of regional target coverage of the present invention;

(2) FIG. 2a is a schematic diagram of left lower corner oblique coverage of a region target of the present invention;

(3) FIG. 2b is a schematic diagram of right lower corner oblique coverage of the region target of the present invention;

(4) FIG. 2c is a schematic diagram of multi-satellite collaborative coverage of the present invention;

(5) FIG. 3a is a schematic diagram of formation of coverage modes of the present invention;

(6) FIG. 3b is a schematic diagram of a longest coverage mode length of the present invention;

(7) FIG. 3c is a schematic diagram of side-sway of satellites of the present invention;

(8) FIG. 3d is a schematic diagram of a maximum roll angle of the present invention;

(9) FIG. 4a is a schematic diagram of a longest basic coverage mode of a right lower corner oblique type of the present invention;

(10) FIG. 4b is a schematic diagram of the longest basic coverage mode of a left lower corner oblique type of the present invention;

(11) FIG. 5a is a schematic diagram of calculation of a roll angle under one condition of the present invention;

(12) FIG. 5b is a schematic diagram of calculation of a roll angle under another condition of the present invention;

(13) FIG. 6a is a schematic diagram of a feasible upper grid condition 1 of the present invention;

(14) FIG. 6b is a schematic diagram of a feasible upper grid condition 2 of the present invention;

(15) FIG. 6c is a schematic diagram of a feasible upper grid condition 3 of the present invention;

(16) FIG. 6d is a schematic diagram of a feasible upper grid condition 4 of the present invention.

DETAILED DESCRIPTION OF THE PRESENT INVENTION

(17) As shown in FIG. 2a, FIG. 2b and FIG. 2c, in the present embodiment, a partition satellite mission planning method for earliest completion of regional target coverage is used to select a subset from sufficient coverage opportunity set S and to plan corresponding coverage modes for completely covering a to-be-observed region R. The optimization purpose of this method is to minimize the completion time. The coverage opportunity refers to an opportunity for a satellite to perform the coverage observation when passing over the to-be-observed region. As shown in FIG. 2c, an area of the to-be-observed region R is large. The single coverage opportunity can only cover a small part, so that a plurality of coverage opportunities are needed for collaborative observation.

(18) As shown in FIG. 3a, FIG. 3b, FIG. 3c and FIG. 3d, each coverage opportunity s∈s has own attribute and includes sub-satellite point track o.sub.s, height h.sub.s of the satellite to the ground and maximum power-on time m.sub.s, corresponding to a maximum length of coverage mode r.sub.s, maximum roll angle v.sub.s and camera field angle w.sub.s. The satellite orbits around the Earth, and a track formed by sub-satellite points on the ground should be a curve actually, but it can be approximated to a straight line in a small range inside the to-be-observed region. In order to simplify the problem, the sub-satellite point track o.sub.s of the coverage opportunity is considered as the straight line in the present embodiment of the present invention. As shown in FIG. 2a and FIG. 2b, each coverage opportunity has a start time α(s) and an end time β(s) for the to-be-observed region R.

(19) The so-called coverage mode c is a rectangular strip photographed by the satellites and determined by a certain roll angle and on/off time selected by one coverage opportunity.

(20) A coordinate system o-xy is established by adopting any vertex of the to-be-observed rectangular region R as an origin o and two sides adjacent to the origin as axis x and axis y. The coordinates of four vertexes of the to-be-observed rectangular region R are marked as left upper corner vertex LU(R), left lower corner vertex LD(R), right upper corner vertex RU(R) and right lower corner vertex RD(R) respectively. The partition satellite mission planning method includes the following steps:

(21) Step 1: a to-be-observed rectangular region R is partitioned.

(22) Step 1.1: length L.sub.p and width W.sub.p of each subregion are set.

(23) Step 1.2: the length L.sub.R and width W.sub.R of the to-be-observed rectangular region R are calculated according to the coordinates of four vertexes of the to-be-observed rectangular region R.

(24) Step 1.3: L.sub.p is divided by L.sub.R to obtain length section number D.sub.L and remainder R.sub.L of the subregion. If the remainder

(25) $R_{L} \geq \frac{D_{L}}{2 D_{L} + 1} L_{p}, D_{L} + 1$
is assigned to D.sub.L. W.sub.p is divided by W.sub.R to obtain width section number D.sub.W and remainder R.sub.W of the subregion, and if the remainder

(26) $R_{W} \geq \frac{D_{W}}{2 D_{W} + 1} W_{p}, D_{W} + 1$
is assigned to D.sub.W.

(27) Step 1.4: L.sub.R is divided by D.sub.L to obtain length L.sub.f of the final subregion, and W.sub.R is divided by D.sub.W to obtain width W.sub.f of the final subregion.

(28) Step 1.5: according to the length L.sub.f and width W.sub.f of the final subregion, the to-be-observed rectangular region R is equally partitioned, thereby obtaining the coordinates of four vertexes of each subregion.

(29) Step 1.5.1: let i=1, the left upper corner coordinate LU(R) of the to-be-observed rectangular region R is used as the left upper corner coordinate LU(n.sub.i) of the i.sup.th subregion n.sub.i.

(30) Step 1.5.2: the abscissa value of the left upper corner coordinate LU(n.sub.i) of the i.sup.th subregion n.sub.i is added with L.sub.f to obtain the right upper corner coordinate RU(n.sub.i) thereof. The ordinate value of the left upper corner coordinate LU(n.sub.i) is added with W.sub.f to obtain the left lower corner coordinate LD(n.sub.i) thereof. The ordinate value of the right upper corner coordinate RU(n.sub.i) is added with f to obtain the right lower coordinate RD(n.sub.i).

(31) Step 1.5.3: if the right lower corner coordinate RD(n.sub.i) of the i.sup.th subregion n.sub.i is equal to the right lower corner coordinate RD(R) of the to-be-observed rectangular region R, step 1.5.6 is carried out; otherwise, step 1.5.4 is carried out.

(32) Step 1.5.4: if the abscissa value of the right upper corner coordinate RU(n.sub.i) of the i.sup.th subregion n.sub.i is equal to the abscissa value of the right upper corner coordinate RU(R) of the to-be-observed rectangular region R, LD(n.sub.(i−D.sub.L.sub.+1)) is used as the left upper corner coordinate LU(n.sub.i+1) of the (i+1).sup.th subregion n.sub.i+1; otherwise, the right upper corner coordinate RU(n.sub.i) of the i.sup.th subregion n.sub.i is used as the left upper corner coordinate LU(n.sub.i+1) of the (i+1).sup.th subregion n.sub.i+1.

(33) Step 1.5.5: after i+1 is assigned to i, step 1.5.2 is carried out to construct the coordinates of four vertexes of a next subregion.

(34) Step 1.5.6: the partitioning is ended, and the coordinates of four vertexes of each subregion are outputted.

(35) Step 1.6: a set N of the subregions is obtained, and the total number of the subregions is |N|=D.sub.L×D.sub.W.

(36) Step 2: observation resources are allocated to different regions, and a certain subset of coverage opportunities and corresponding coverage modes are selected to minimize the completion time of a formed coverage solution. That is, different coverage opportunities are responsible for covering different subregions, while different allocation solutions may finally lead to different coverage solutions which correspond to different completion time. Therefore, a simulated annealing method is used to search an optimum allocation solution here.

(37) Step 2.1: the coverage opportunities are randomly allocated to each subregion to form an initial current allocation solution Y={y.sup.s|∀s∈S} wherein the value of y.sub.s represents the subregion where the coverage opportunity s is allocated.

(38) Step 2.2: the coverage opportunity set S*(Y) selected under the current allocation solution Y, a desirable coverage mode set C*(Y) and corresponding completion time F(Y) are calculated.

(39) Step 2.2.1: different subregions and the set of coverage opportunities allocated to different subregions are used as inputs to construct grids, and a two-phase heuristic algorithm is used to calculate the coverage opportunity set selected for different subregions as well as the desirable coverage solution and corresponding completion time.

(40) Step 2.2.1.1: the i.sup.th subregion is divided into a plurality of consistent square grids to obtain a grid set J.sub.i, wherein a side length of each grid should be minimized. The existing grids are ensured to be completely covered by the coverage modes.

(41) If the to-be-observed region was not partitioned into subregions, the whole large region may form a large number of grids A large number of coverage modes may be generated based on these grids, which consumes vast calculation resources. Some large-scale calculation examples cannot even obtain a solution within a rational time, so that embodiments of the present invention are proposed on the basis of solving strategies based on the partition.

(42) Step 2.2.1.2: according to the divided grid set J.sub.i, a set of longest basic coverage modes is generated for each coverage opportunity in set S.sub.i allocated to the i.sup.th subregion n.sub.i, and jointly form a main set C.sub.i of the optional coverage modes.

(43) As shown in FIG. 4a and FIG. 4b, the longest basic coverage mode refers to that the length is equal to the maximum length r.sub.s, and there are two grids that satisfy the following two conditions:

(44) {circle around (1)} Both grids are completely covered by the coverage mode, that is, the four vertexes are within the area covered by the coverage mode;

(45) {circle around (2)} one grid has a vertex located on a left border of the coverage mode and is named left grid, and the other grid has a vertex located on an upper border of the coverage mode and is named upper grid. The left grid and the upper grid can be the same.

(46) Each coverage opportunity can select infinitely many on/off time and roll angles, so each coverage opportunity may actually correspond to an infinite number of coverage modes. However, all coverage modes cannot be enumerated. Therefore, the solving method of the problem is difficult to design on the basis of the universal set of all coverage modes. The longest basic coverage mode is a special coverage mode and can substitute a majority of non-longest basic coverage modes and is limited in quantity. A majority of non-longest basic coverage modes may be slightly adjusted to be the corresponding longest basic coverage modes without reducing the number of completely covered grids.

(47) Step 2.2.1.2.1: if S.sub.i=Ø, step 2.2.1.2.4 is carried out; otherwise, step 2.2.1.2.2 is carried out.

(48) Step 2.2.1.2.2: one of coverage opportunities s∈S.sub.i is selected, and according to the type of the coverage opportunity s, methods in step 2.2.1.2.2.1 to step 2.2.1.2.2.10 are used to construct a longest basic coverage mode set C.sub.s based on the grid set J.sub.i for the coverage opportunity s.

(49) Step 2.2.1.2.2.1: the type of the coverage opportunity s is judged according to the sub-satellite point track o.sub.s of the coverage opportunity s, and the types include a right lower corner oblique type and a left lower corner oblique type.

(50) Step 2.2.1.2.2.2: let set C.sub.s=Ø.

(51) Step 2.2.1.2.2.3: subsets J.sub.s are selected from the grid set J.sub.i, and each grid in the subsets J.sub.s may be used as the left grid of a longest basic coverage mode of the coverage opportunity s.

(52) Step 2.2.1.2.2.3.1: let J.sub.s=Ø.

(53) Step 2.2.1.2.2.3.2: the set J.sub.i is traversed, and the camera roll angle

(54) $σ_{s} (u) = \arctan \frac{d_{s}^{u}}{h_{s}} - \frac{w_{s}}{2}$
of the coverage opportunity s is calculated when each grid u is used as the left grid of the coverage mode. If the coverage opportunity is the right lower corner oblique type, as shown in FIG. 4a, d.sub.s.sup.u is a distance between the left lower corner vertex LD(u) of the grid u and the sub-satellite point track o.sub.s of the coverage opportunity s. If the coverage opportunity is the left lower corner oblique type, as shown in FIG. 4b, d.sub.s.sup.u is a distance between the left upper corner vertex LU(u) of the grid u and the sub-satellite point track o.sub.s of the coverage opportunity s. If |σ.sub.s(u)|≤v.sub.s, the grid u is added into the subset J.sub.s of the left grid.

(55) Step 2.2.1.2.2.4: if J.sub.s=Ø, step 2.2.1.2.2.10 is carried out; otherwise, after one grid p in J.sub.s is selected, step 2.2.1.2.2.5 is carried out.

(56) Step 2.2.1.2.2.5: according to the grid p, the grid subset J.sub.s.sup.p is selected from the grid set J.sub.i, and when p is used as the left grid, each grid in J.sub.s.sup.p may be used as the upper grid to form a longest basic coverage mode of the coverage opportunity s together with p.

(57) Step 2.2.1.2.2.5.1: let J.sub.s.sup.p=Ø.

(58) Step 2.2.1.2.2.5.2: a strip width η.sub.s(p) of the coverage mode when the grid p is used as the left grid is calculated by using the formula (1):

(59) $\begin{matrix} η_{s} (p) = {\begin{matrix} d_{s}^{p} - h_{s} .Math. \tan (\arctan \frac{d_{s}^{p}}{h_{s}} - w_{s}), \arctan \frac{d_{s}^{p}}{h_{s}} > w_{s} \\ d_{s}^{p} + h_{s} .Math. \tan (w_{s} - \arctan \frac{d_{s}^{p}}{h_{s}}), \arctan \frac{d_{s}^{p}}{h_{s}} \leq w_{s} \end{matrix} & (1) \end{matrix}$

(60) As shown in FIG. 5a and FIG. 5b, when the grid u is used as the left grid of the coverage mode, a calculation formula of the camera roll angle σ.sub.s(u) of the coverage opportunity s and the strip width η.sub.s(u) of the coverage mode can both be obtained by elementary geometry. OB is a vertical line, and the length of OB is the height of the satellite to the ground, i.e. h.sub.s. The length of AB is a distance between the straight lines L.sub.u and o.sub.s, i.e. d.sub.s.sup.u. Apparently, ∠ABO is a right angle, so it is easy to get:

(61) $∠ AOB = \arctan \frac{d_{s}^{u}}{h_{s}},$
and the camera roll angle

(62) $σ_{s} (u) = \arctan \frac{d_{s}^{u}}{h_{s}} - \frac{w_{s}}{2} .$

(63) In FIG. 5a, ∠AOC is a field angle, i.e. w.sub.s, while ∠AOB>w.sub.s. The width of the strip is the length of AC at this moment.

(64) $A C = d_{s}^{u} - B C = d_{s}^{u} - h_{s} .Math. \tan ∠ BOC = d_{s}^{u} - h_{s} .Math. \tan (∠ AOB - w_{s}) = d_{s}^{u} - h_{s} .Math. \tan (\arctan \frac{d_{s}^{u}}{h_{s}} - w_{s})$

(65) In FIG. 5b, ∠AOD is a field angle, i.e. w.sub.s. OC is an angular bisector of ∠AOD, i.e.

(66) $∠ A O C = \frac{w_{s}}{2} .$
The width of the strip is length of AD at this moment.

(67) $∠ AOB = \arctan \frac{d_{s}^{u}}{h_{s}}, ∠ DOB = w_{s} - ∠ AOB,$
so it can obtain: BD=h.sub.s.Math.tan ∠DOB, and it can further obtain:

(68) 0 $AD = d_{s}^{u} + BD = d_{s}^{u} + h_{s} .Math. \tan ∠ BOD = d_{s}^{u} + h_{s} .Math. \tan (w_{s} - ∠ AOB) = d_{s}^{u} + h_{s} .Math. \tan (w_{s} - \arctan \frac{d_{s}^{u}}{h_{s}})$

(69) Step 2.2.1.2.2.5.3: the set J.sub.i is traversed. Whether one grid t satisfies the following four conditions is checked. If all conditions are satisfied, the grid t is added into J.sub.s.sup.p; otherwise, the next grid is checked.

(70) If the coverage opportunity is the right lower corner oblique type, the four conditions are:

(71) {circle around (1)} as shown in FIG. 6a, the straight line L.sub.p∥o.sub.s is made through the left lower corner vertex of the grid p, the straight line L.sub.t′∥o.sub.s is made through the right upper corner vertex of t, and the distance between the straight lines L.sub.p and L.sub.t′ cannot exceed the width η.sub.s(p) of the strip.

(72) {circle around (2)} as shown in FIG. 6b, the straight lines L.sub.p′⊥o.sub.s and L.sub.t⊥o.sub.s are made respectively through the left upper corner vertexes of the grids p and t, and L.sub.t is above L.sub.p′.

(73) {circle around (3)} as shown in FIG. 6c, the straight line L.sub.t∥o.sub.s is made through the left lower corner vertex of the grid t, and the straight line L.sub.t is at the right side of L.sub.p.

(74) {circle around (4)} as shown in FIG. 6d, the straight line L.sub.p⊥o.sub.s is made through the right lower corner vertex of the grid p, and the distance between the straight lines L.sub.p and L.sub.t cannot exceed the length l.sub.s of the strip. “∥” indicates a parallel relation, and “⊥” indicates a vertical relation.

(75) If the coverage opportunity is the left lower corner oblique type, the four conditions are:

(76) {circle around (1)} The straight line L.sub.p∥o.sub.s is made through the left upper corner vertex of the grid p, the straight line L.sub.t′∥o.sub.s is made through the right upper corner vertex of t, and the distance between the straight lines L.sub.p and L.sub.t′ cannot exceed the width η.sub.s(p) of the strip.

(77) {circle around (2)} The straight lines L.sub.p′⊥o.sub.s and L.sub.t⊥o.sub.s are made respectively through the right upper corner vertexes of the grids p and t, and L.sub.t is above L.sub.p′.

(78) {circle around (3)} The straight line L.sub.t∥o.sub.s is made through the left upper corner vertex of the grid t, and the straight line L.sub.t is at the right side of L.sub.p.

(79) {circle around (4)} The straight line L.sub.p⊥o.sub.s is made through the left lower corner vertex of the grid p, and the distance between the straight lines L.sub.p and L.sub.t cannot exceed the length l.sub.s of the strip. “∥” indicates a parallel relation, and “⊥” indicates a vertical relation.

(80) Apparently, the grid p also satisfies the four conditions.

(81) Step 2.2.1.2.2.6: if J.sub.s.sup.p=Ø, step 2.2.1.2.2.9 is carried out; otherwise, after one grid q in J.sub.s.sup.p is selected, step 2.2.1.2.2.7 is carried out.

(82) Step 2.2.1.2.2.7: based on the grids P and q, the longest basic coverage c.sub.s(p,q) belonging to the coverage opportunity s is constructed.

(83) Step 2.2.1.2.2.7.1: if the coverage opportunity is the right lower corner oblique type, the straight line L.sub.p∥o.sub.s is made through the left lower corner vertex LD(p) of the grid p, and the straight line L.sub.q⊥o.sub.s is made through the left upper corner vertex LU(q) of the grid q. If the coverage opportunity is the left lower corner oblique type, the straight line L.sub.p∥o.sub.s is made through the left upper corner vertex LU(p) of the grid p, and the straight line L.sub.q ⊥o.sub.s is made through the right upper corner vertex RU(q) of the grid q.

(84) Step 2.2.1.2.2.7.2: the strip width η.sub.s(p) of the coverage mode when the grid p is used as the left grid is calculated.

(85) Step 2.2.1.2.2.7.3: the straight line L.sub.p is made so as to satisfy:

(86) {circle around (1)} L.sub.p∥L.sub.p;

(87) {circle around (2)} (the distance between L.sub.p and L.sub.p is equal to η.sub.s(p);

(88) {circle around (3)} L.sub.p is at the right side of L.sub.p.

(89) Step 2.2.1.2.2.7.4: the straight line L.sub.q is made so as to satisfy:

(90) {circle around (1)} L.sub.q∥L.sub.q;

(91) {circle around (2)} (the distance between L.sub.q and L.sub.q is equal to l.sub.s;

(92) {circle around (3)} L.sub.q is at the lower side of L.sub.q.

(93) Step 2.2.1.2.2.7.5: four straight lines of L.sub.p, L.sub.p, L.sub.q, L.sub.q are used as four sides of the rectangle, and intersections of the four straight lines are used as four vertexes of the rectangle to construct the coverage mode c.sub.s(p,q).

(94) Step 2.2.1.2.2.8: c.sub.s (p,q) is added into C.sub.s, the grid q is removed from J.sub.s.sup.p, and then step 2.2.1.2.2.6 is carried out.

(95) Step 2.2.1.2.2.9: the grid p is removed from J.sub.s, and then step 2.2.1.2.2.4 is carried out.

(96) Step 2.2.1.2.2.10: the coverage mode set C.sub.s is outputted.

(97) Step 2.2.1.2.3: the coverage mode opportunity s is removed from S.sub.i, and then step 2.2.1.2.1 is carried out.

(98) Step 2.2.1.2.4: let, the coverage mode set C.sub.i is outputted.

(99) Step 2.2.1.3: by utilizing the grid set J.sub.i separated from i.sub.th subregion n.sub.i as well as the coverage opportunity set S.sub.i={s|y.sub.s=n.sub.i, s∈S} allocated to i.sup.th subregion n.sub.i and optional coverage mode set C.sub.i as inputs, the coverage opportunity subset S.sub.i* selected by the i.sup.th subregion n.sub.i is determined by the two-phase heuristic algorithm, and the coverage mode of each coverage opportunity is selected, so that the desirable coverage mode set C.sub.i* is obtained, and the completion time F.sub.i thereof can be obtained at the same time.

(100) Step 2.2.1.3.1: by utilizing the grid set J.sub.i, the coverage opportunity set S.sub.i and the corresponding coverage mode set C.sub.i as inputs, the selected coverage opportunity subsets S.sub.i*, the selected coverage mode sets C.sub.i* and the number A.sub.i of corresponding coverable grids can be calculated with the heuristic algorithm.

(101) Step 2.2.1.3.1.1: all coverage opportunities in S.sub.i are sorted in a non-descending order according to the end time to obtain

(102) $\overset{.Math.}{S_{i}} = {s_{1}, s_{2}, .Math., s_{| \overset{.Math.}{s_{i} |}}} .$

(103) Step 2.2.1.3.1.2: the state of all grids in J.sub.i is set as “uncovered”, let g=0, and C.sub.i*=Ø.

(104) Step 2.2.1.3.1.3: g+1 is assigned to g, the coverage opportunity s.sub.g is extracted from {right arrow over (S.sub.i)}, and the optional coverage mode set C.sub.s.sub.g is traversed. For each coverage mode C.sub.s.sub.g, the grid capable of being completely covered by C.sub.s.sub.g and with the state of “uncovered” is selected from the grid set J.sub.i and marked as valid grid sets V(c.sub.s.sub.g), while the number is marked as |V(c.sub.s.sub.g)|.

(105) Step 2.2.1.3.1.4: the coverage mode

(106) $c_{s_{g}}^{*} = \arg \max_{\forall c_{s_{g}} \in C_{s_{g}}} | V (c_{s_{g}}) |$
covering the most valid grids is selected from C.sub.s.sub.g and used as the coverage mode selected by the coverage opportunity s.sub.g. After c.sub.s.sub.g* is added into C.sub.i*, the state of all grids in the valid grid sets V(c.sub.s.sub.g) of the coverage mode c.sub.s.sub.g* is changed as “covered”.

(107) Step 2.2.1.3.1.5: the number of all grids with the state of “covered” in J.sub.i is calculated and marked as A.sub.i.

(108) Step 2.2.1.3.1.6: if A.sub.i=|J.sub.i| or g=|{right arrow over (S.sub.i)}|, step 2.2.1.3.1.7 is carried out; otherwise, step 2.2.1.3.1.3 is carried out.

(109) Step 2.2.1.3.1.7: the coverage opportunity subset S.sub.i*={s.sub.1, s.sub.2, . . . , s.sub.g} as well as the coverage mode set C.sub.i* thereof and the number A.sub.i of covered grids are outputted.

(110) Step 2.2.1.3.2: if A.sub.i<|J.sub.i|, step 2.2.1.3.4 is carried out; otherwise, step 2.2.1.3.3 is carried out.

(111) On the premise of sufficient coverage opportunities, the coverage opportunities that are randomly allocated to each subregion generally can completely cover the subregion, that is, A.sub.i=|J.sub.i|. If some subregions cannot be completely covered, they may be improved in neighbor allocation solutions constructed by an insert operator and an exchange operator at the simulated annealing phase.

(112) Step 2.2.1.3.3: S.sub.i* and C.sub.i* are optimized by using a promotion algorithm.

(113) Step 2.2.1.3.3.1: one coverage opportunity

(114) $s_{m} = \arg \max_{\forall s \in S_{i}^{*}} β (s)$
with maximum end time in S.sub.i* is removed from S.sub.i* to obtain the coverage opportunity set S.sub.i.

(115) Step 2.2.1.3.3.2: by utilizing the grid set J.sub.i, the coverage opportunity set S.sub.i and the optional coverage mode set C.sub.i={c|∀c∀C.sub.s, ∀s∈S.sub.i} corresponding to S.sub.i as inputs, the selected coverage opportunity subsets S.sub.i*, the selected coverage mode set C.sub.i*, and the number A.sub.i of the corresponding coverable grids can be calculated with the heuristic algorithm.

(116) Step 2.2.1.3.3.2.1: the state of all grids in J.sub.i is set as “uncovered”, and C.sub.i*=Ø.

(117) Step 2.2.1.3.3.2.2: let g=1.

(118) Step 2.2.1.3.3.2.3: if g>|C.sub.i|, step a.3.3.2.5 is carried out; otherwise, step a.3.3.2.4 is carried out.

(119) Step 2.2.1.3.3.2.4: the g.sup.th coverage mode in C.sub.i is selected, and the grids capable of being completely covered by the g.sup.th coverage mode and with the state of “uncovered” are selected from the grid set J.sub.i and marked as valid grid set V(g), while its number is marked as |V(g)|. g+1 is assigned to g. Thereafter step a.3.3.2.3 is carried out.

(120) Step 2.2.1.3.3.2.5: if C.sub.i=Ø, step a.3.3.2.8 is carried out; otherwise, step a.3.3.2.6 is carried out.

(121) Step 2.2.1.3.3.2.6: the coverage mode

(122) ${\overline{g}}^{*} = \arg \max_{\forall \overline{g} \in \overline{C_{i}}} | V (\overline{g}) |$
with most valid grids in C.sub.i is selected and used as the coverage mode selected by the corresponding coverage opportunity s*. g* is added into C.sub.i*, and the state of all grids in the valid grid set V(g*) of the coverage mode g* is changed to be “covered”.

(123) Step 2.2.1.3.3.2.7: the coverage mode set C.sub.s* corresponding to the coverage opportunity s* is removed from the optional coverage mode set C.sub.i, and then step a.3.3.2.2 is carried out.

(124) Step 2.2.1.3.3.2.8: the coverage mode set C.sub.i*, selected by each coverage opportunity is outputted, i.e. the final coverage solution. The number of all “covered” grids in J.sub.i is calculated and marked as A.sub.i.

(125) Step 2.2.1.3.3.3: if A.sub.i=|J.sub.i|, S.sub.i* is assigned to S.sub.i* , and C.sub.i* is assigned to C.sub.i*. Thereafter, step 2.2.1.3.3.1 is carried out; otherwise, step 2.2.1.3.4 is carried out.

(126) Step 2.2.1.3.4: the selected coverage opportunity set S.sub.i* and the coverage mode set C.sub.i* are outputted. The maximum value of the end time of the coverage opportunity in S.sub.i* is used as the completion time F.sub.i.

(127) The first phase of the two-phase heuristic algorithm in step 2.2.1.3 utilizes the rule based on dynamic greed. The coverage mode covering most valid grids is selected at each time. Once the coverage opportunity selects one coverage mode, the coverage opportunity may exit the subsequent selection activities. Once the grid is covered in the previous selection, the grid exits the subsequent selection activities. The method is simple, fast and effective and very suitable for rapidly obtaining the desirable feasible coverage solution under the current environment. At the second phase, on the basis of the solution obtained at the first phase, after the selected coverage opportunity with maximum end time is deleted, the complete coverage solution is re-planned to search a better solution space of the solution.

(128) Step 2.2.2: the coverage opportunity sets {S.sub.i*|i=1, 2, . . . , |N|} selected by all subregions are combined to obtain an overall selected coverage opportunity set S*. The coverage solutions {C.sub.i*|i=1, 2, . . . , |N|} of all subregions are combined to obtain an overall coverage solution C* of the to-be-observed rectangular region R. The maximum value of the completion time {F.sub.i|i=1, 2, . . . , |N|} corresponding to the coverage solutions of all subregions is used as the overall completion time F of the to-be-observed rectangular region R.

(129) The solution space of the allocation solution is searched below by utilizing the simulated annealing method to obtain a better allocation solution, so that the completion time corresponding to the formed coverage solution is minimized, which specifically includes step 2.3-step 2.9:

(130) Step 2.3: maximum iteration times k and initial annealing temperature T.sub.1 are set, and the iteration times of the current outer cycle is set as k=1.

(131) Step 2.4: if k>k, step 2.9 is carried out; otherwise, step 2.5 is carried out.

(132) Step 2.5: the insert operator and the exchange operator are used to construct a plurality of neighbor allocation solutions of the current allocation solution Y.

(133) Step 2.5.1: the number of the to-be-constructed neighbor allocation solutions is set as m, and the number of the constructed neighbor allocation solutions is set as m, and m=0.

(134) Step 2.5.2: the insert operator is used to construct the neighbor allocation solution.

(135) Step 2.5.2.1: an idle coverage opportunity ŝ is found from the unselected coverage opportunity set S′(Y)={S/S*(Y)} under the current allocation solution Y. The end time β(ŝ) of the idle coverage opportunity ŝ is smaller than the overall completion time F(Y) but greater than the completion time F.sub.y.sub.ŝ(Y) that the idle coverage opportunity ŝ is allocated to the subregion y.sub.ŝ. If the idle coverage opportunity cannot be found, step 2.5.2.4 is carried out; otherwise, step 2.5.2.2 is carried out.

(136) Step 2.5.2.2: m+1 is assigned to m, and the idle coverage opportunity ŝ in the current allocation solutions Y is randomly allocated to one subregion, and the end time β(ŝ) of the idle coverage opportunity ŝ is smaller than the completion time of the allocated subregion, thereby forming a neighbor allocation solution Y.sub.m.

(137) Step 2.5.2.3: the idle coverage opportunity ŝ is removed from the coverage opportunity set S′(Y), and then step 2.5.2.1 is carried out.

(138) Step 2.5.2.4: all neighbor allocation solutions obtained by utilizing the insert operator are outputted.

(139) Step 2.5.3: the exchange operator is used to construct the neighbor allocation solution.

(140) Step 2.5.3.1: if m≥m, step 2.5.3.3 is carried out; otherwise, step 2.5.3.2 is carried out.

(141) Step 2.5.3.2: m+1 is assigned to m. Two subregions n.sub.i and n.sub.j are randomly selected from the subregion set N. One coverage opportunity s.sub.i is randomly selected from the coverage opportunity set {s|y.sub.s=n.sub.i} allocated to the subregion n.sub.i. One coverage opportunity s.sub.j is randomly selected from the coverage opportunity set {s|y.sub.s=n.sub.j} allocated to the subregion n.sub.j. s.sub.i and s.sub.j are exchanged in the current allocation solution Y, that is, n.sub.j is assigned to y.sub.s.sub.i, and n.sub.i is assigned to y.sub.s.sub.j, thereby forming a neighbor coverage solution Y.sub.m, and then step 2.5.3.1 is carried out.

(142) Step 2.5.3.3: all neighbor allocation solutions obtained by using the exchange operator are outputted.

(143) Step 2.6: the coverage opportunity set selected under each neighbor allocation solution, desirable coverage mode set and corresponding completion time are calculated separately, and the neighbor allocation solution with minimum completion time is selected as the optimal neighbor allocation solution Y*. The specific steps refer to step 2.2 and are not repeated here.

(144) Step 2.7: The completion time of the optimal neighbor allocation solution Y* is compared with the completion time of the current allocation solution Y. If F(Y*)≤F(Y) the optimal neighbor allocation solution Y* is assigned to the current allocation solution Y, and then step 2.8 is directly carried out; otherwise, step 2.8 is carried out after the step 2.7.1-step 2.7.2.

(145) Step 2.7.1: an inferior solution accept rate

(146) $P_{k} = \exp {\frac{F (Y) - F ({\overline{Y}}^{*})}{T_{k}}}$
at k.sup.th iteration is calculated.

(147) Step 2.7.2: a random number r.sub.k of 0-1 is generated at k.sup.th times. If r.sub.k≤p.sub.k, the optimal neighbor allocation solution Y* is assigned to the current allocation solution Y.

(148) Step 2.8: k+1 is assigned to k, and the annealing temperature T.sub.k=T.sub.k-1×λ is updated. λ is a cooling coefficient and is a fixed value less than 1 and greater than 0, and then step 2.4 is carried out.

(149) The annealing temperature represents randomness for searching the solution space. If the requirement for the final solution quality is high, λ may be set to be large, and the iteration times may be increased. If the rapid convergence is required, λ is set to be small.

(150) Step 2.9: the current allocation solution Y as well as the overall selected coverage opportunity set S*(Y) under the allocation solution, better coverage modes C*(Y) of each coverage opportunity and corresponding completion time F(Y) are outputted.

Partition satellite mission planning method for earliest completion of regional target coverage

Assignee

Inventors

Cpc classification

Classification Explorer

B64G1/1021

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

G01C21/3852

PHYSICS

Classification Explorer

B64G2001/1028

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

G06V20/13

PHYSICS

International classification

Classification Explorer

G06V20/13

PHYSICS

Classification Explorer

B64G1/10

PERFORMING OPERATIONS; TRANSPORTING

Abstract

Claims

Description