スペースデブリ観測レーダーの 最適操作

スペースデブリ観測レーダーの 最適操作

指導教員 福嶋雅夫 教授 山下信雄 助手

池端 祐介

京都大学大学院情報学研究科 数理工学専攻 修士課程

平成１５年度４月入学

KYOTO UNIVER SITY FO

U N^KYOTODED 1^JAPAN897

平成１７年２月

摘要

近年，「宇宙のゴミ

(

)

1

1

2

さらに，理論的な上界値との差は

0

1

目 次

1

1

2

2

2.1

. . . . 2 2.2

. . . . 3

3

5

3.1

. . . . 5 3.2

. . . . 9

4

14

5

17

A

20

B

21

C

22

D joint procedure 23

E find procedure 24

F

26

1

20

5,000

500

2,500

[1]

[1, 11]

36,000km/h

に衝突したり，地上に落下したりする危険性がある．スペースデブリ対策はもはや放置でき ない緊急課題である．スペースデブリ対策として重要なことは，スペースデブリの正確な軌 道情報を得ることである．各国ではレーダーや望遠鏡を使ってスペースデブリの観測を行い，

それらの軌道のカタログを作っている

[1]

米国ではカタログ作成のための定常観測を世界各地にあるレーダーのネットワークを用い て行なっている．そのスペースデブリのカタログは国防省

/

Space-Track Website

[9]

1

[6, 7]

1

1

1

本研究では，スペースデブリの大域的な情報を利用してより多くのスペースデブリを観測 する手法を提案する．具体的には，まず，スペースデブリをノードとした有向グラフを作成 し，そのグラフの最長路問題を解くことによって，スペースデブリを観測する順番を求める．

次に，その順番に基づいたレーダーの操作計画を作成する．

本論文の構成は以下のとおりである．第

2

3

4

5

2

この節では，本論文で扱うスペースデブリ観測計画問題を説明する．さらに，その問題に 対する従来の手法とその問題点について述べる．

2.1

スペースデブリ観測計画問題とは，

1

1.

2.

S

/s

3.

S

/s (

S

≤ S

)

±h

4. 1

T ₀

5.

±C

(≥ 180

)

1

4

T 0

秒間以上連続してスペースデブリを捕捉したデータが必要となるためである．以下では，「ス ペースデブリを観測する」とは，

T 0

2,3,5

観測期間中の各スペースデブリの予報値にはその属性として，カタログ番号・予報値時刻・

方位角があるものとする．各データは離散時間において与えられているものとする．実際，

米国の国防省

/

Space-Track Website[9]

本論文では，予報値に関連して以下の記号を用いる．

T :

t = 1

; n :

;

l i :

i

;

t _i,1 :

i(i = 1, . . . , n)

; t _i,l

:

i(i = 1, . . . , n)

;

d _i (t _i,k ) :

t _i,k (k = 1, 2, . . . , l _i )

i

;

方位角は

0

180

−180

5

0

±C

(≥ 180

)

方位角は

±C

180

−180

[C, −C]

1

C = 270

t

曲線は，捕捉可能なスペースデブリの軌道を表わしている．このとき，図

1

i

1

2

250 200 150 100 50 0 50 100 150 200 250

デブリ

t Az

図

1:

ここで，

x(t)

t

x = (x(1), x(2), · · · , x(T ))

x

f (x)

max f (x)

s.t. |x(t) − x(t + 1)| ≤ S

(t = 1, . . . , T − 1)

−C ≤ x(t) ≤ C (t = 1, . . . , T )

(1)

x

T

T

(1)

f

2.2

日本において現在使用している手法は，以下のアルゴリズムである

[3]

A

マスターデブリ追跡法

step 0 t := 1;

step 1 t = T

step 2

step 2

i

スペースデブリ

i

t _i,l

i

x(t)

step 3

t := t + 1

step 1

step 3

るならば，最も方位角方向が離れた

2

x(t)

step 4

step 4 t = t _i,l

|d _i (t) − x(t)| > h

t := t + 1

step 1

この手法では，各時刻のスペースデブリのデータしか用いていないので，求まったレー ダー軌道

x(t)

2(a)

h

1

2(b)

2

1

2.785 2.79 2.795 2.8 2.805 2.81 x 10⁴

‑180

‑160

‑140

‑120

‑100

‑80

‑60

‑40

‑20 0 20

[t]

[Az]

観測可能なレーダーの軌道 マスターデブリ法のレーダーの軌道

hを超えてしまう

6.65 6.655 6.66 6.665 6.67 6.675 6.68 x 10⁴ 20

40 60 80 100 120 140 160 180 200 220

[t]

[Az]

観測可能なレーダーの軌道 マスターデブリ法のレーダーの軌道

h以上

(a) (b)

図

2:

3

この節では，観測期間中のスペースデブリの大域的な情報を用いる手法を提案する．提案 手法では，まず，スペースデブリを観測する順番を決め，その結果を用いて実際のレーダー 軌道を決定することを考える．その手順を以下で述べる．

3.1

スペースデブリをノードとした有向グラフ

G = (V, E)

(

3)

250 200 150 100 50 0 50 100 150 200 250

1 2

3 4

5

6 7

8 s

t

図

3:

集合

V

s

t

1, 2, . . . , n

V = {s, 1, 2, . . . , n, t}

E

E _s = {(s, j) | j ∈ V }

E t = {(i, t) | i ∈ V }

E d = {(i, j) ∈ V × V |

i

j

i

}

E = E s ∪ E t ∪ E d (2)

で定義される．図

3

n = 8

上のように定義されるグラフ

G = (V, E)

(i, j) ∈ E

1

s ∈ V

t ∈ V

(i ₁ , i ₂ , · · · , i _N )

(i ₁ , i ₂ ) ∈ E, (i ₂ , i ₃ ) ∈ E, · · · , (i _N−1 , i _N ) ∈ E

i a 6= i _b (a 6= b)

このとき，最長路問題は次のような

0-1

max ^X

(i,j)∈E

y ij

s.t. ^X

{j|(i,j)∈E}

y _ij − ^X

{j|(j,i)∈E}

y _ji = 0, ∀i ∈ V \ ({s} ∪ {t}) X

{j|(s,j)∈E}

y ij = 1, ^X

{j|(j,t)∈E}

y jt = 1 X

{j|(i,j)∈E}

y ij ≤ 1

y _ij ∈ {0, 1}, (i, j ) ∈ E.

(3)

ここで，変数

y ij

(i, j)

y ij = 1

y ij = 0

等式制約は各ノードにおける流量保存を表わしており，不等式制約は，パスが各ノードに

2

(3)

{y ij }

y si

= y i

i

= y _i

_i

= · · · = y _i

_t = 1

π = (i ₁ , i ₂ , · · · , i _n

)

π

(3)

最長路

π

n

(1)

π

4(a)

4(b)

π = (i ₁ , i ₂ , i ₃ )

i ₁

i ₂

i ₂

s

(

5(a))

i ₂

i ₃

i 2

s

(

5(b))

i 1 , i 2

i ₃

(3)

π

(1)

x(t)

π

π

{y ij }

(3)

(3)

π

n

(1)

最長路を用いてレーダー軌道を決定する計算手順は，以下のようにまとめられる．

最長路法（プロトタイプ）

step 1

step 1-1

V

(2)

E

G = (V, E)

step 1-2

(3)

π

step 2 π

x

step 2

x

ことが困難なときは，レーダー軌道

x

π

3.2.5

200 150 100 50 0 50 100 150 200 250

Az

t スペースデブリ

i 1

i 3

i 2

i 1

i 3

i 2

(a)

(b)

4:

200 150 100 50 0 50 100 150 200 250

スペースデブリ 捕捉可能な範囲 レーダー軌道

i

i

i

Az

t 200 150 100 50 0 50 100 150 200 250

スペースデブリ 捕捉可能な範囲 レーダー軌道

t Az

s

i

i

i

(a) i ₁

i ₂

(b) i ₂

i ₃

捕捉可能範囲 捕捉可能範囲

図

5:

一般のグラフに対する最長路問題は

NP

[5]

n

step 1

2

T 0

[1, T ]

[1, T ₁ ], [T ₁ , T ₂ ], · · · , [T _m−1 , T m ]

[1, T ₁ ]

1

[T _k−1 , T _k ] (k = 2, . . . , m)

k

(1)

S

/s

T

= 2C/S

ˆ t

(

6)

ˆ t

t l

ˆ t

t s

このとき，

t _s − t _l > T

ˆ t

t ˆ

250 200 150 100 50 0 50 100 150 200 250

t

t ˆ t

T

t

図

6:

[1,ˆ t],[ˆ t,T]

以上のアイデアを組み込んだ提案手法は以下のアルゴリズムとなる．

最長路法

step 0

期間

[1, T ]

m

b := 1.

step 1

step 1-1

b

V

と

(2)

E

G = (V, E)

step 1-2

(3)

π ^b

step

2

step 2 π ^b

x ^b

b = m

step 3

b := b + 1

step 1

step 3

[1, T ]

3.2

本副節では，最長路法の各ステップの詳細について述べる．

3.2.1

最長路法で重要な役割を果たすのが，各スペースデブリを観測できるレーダー軌道の上限 と下限である．この上限と下限によって観測不可能なスペースデブリの発見や，枝

E

step 2

x ^b

時刻

s

i

t

U _s ⁱ (t)

L ⁱ _s (t)

U _s ⁱ (t) ≥ x(t) ≥ L ⁱ _s (t), t = s, . . . , s + (T ₀ − 1)

|x(t) − x(t + 1)| ≤ S

, t = s, . . . , s + (T 0 − 2) (4)

x(t)

i

U _s ⁱ (a) < x(a)

x(a) < L ⁱ _s (a)

a ∈ {s, . . . , s + (T ₀ − 1)}

x(t)

i

s

i = 1, . . . , n

s = t _i,1 , . . . , t _i,l

− (T ₀ − 1)

以下では

U _s ⁱ (t), L ⁱ _s (t)

0

1

(

7)

8

(

B

)

U _s ⁱ (t)

まず，

t = s

U _s ⁱ (s) = d i (s) + h

t = k (k = s + 1, . . . , s + (T 0 − 1))

U _s ⁱ (k − 1)

i

S

(

8,

A)

U _s ⁱ (k) = U _s ⁱ (k − 1) + S

S

i

(

8,

B)

U _s ⁱ (k) = U _s ⁱ (k − 1) + S

(

8,

C)

i

U _s ⁱ (k) = U _s ⁱ (k − 1) + |d i (k) − d i (k − 1)|

L ⁱ _s (t)

U _s ⁱ (t) < L ⁱ _s (t)

t ∈ {s, . . . , s + (T 0 − 1)}

スペースデブリ

i

s

ここで，上記のように決めた

U _s ⁱ (t), L ⁱ _s (t)

真の上限と下限を

U ¯ _s ⁱ (t), L ¯ ⁱ _s (t)

U _s ⁱ (t), L ⁱ _s (t)

(4)

x(t)

i

t = s, . . . , s+(T ₀ −1)

U ¯ _s ⁱ (t) ≥ U _s ⁱ (t)

L ⁱ _s (t) ≥ L ¯ ⁱ _s (t)

a ∈ {s, . . . , s+(T ₀ − 1)}

で

L ¯ ⁱ _s (a) < L ⁱ _s (a)

U _s ⁱ (a) < U ¯ _s ⁱ (a)

a

200 150 100 50 0 50

s

s + ( T

− 1 )

) (t U

) (t L

スペースデブリ

t Az

0 50 100 150 200 250

) 1 (

− + T

s

) (t U

) (t L

スペースデブリ Az

t

(a) (b)

図

7:

L ¯ ⁱ _s (a) ≤ x(a) < L ⁱ _s (a)

x

(

9)

a

9

A,C

B

ケース

A,C :

s ≤ a ≤ t ˆ ₁

t ˆ ₂ ≤ a ≤ s + (T ₀ − 1)

d i (a) − x(a) > h

i

ケース

B :

t ˆ ₁ < a < t ˆ ₂

S

t ˆ ₂

x( ˆ t ₂ ) < L ⁱ _s ( ˆ t ₂ )

d i ( ˆ t ₂ ) − x( ˆ t ₂ ) > h

これは，

L ¯ ⁱ _s (t)

U _s ⁱ (t), L ⁱ _s (t)

3.2.2

(step 0)

次の

(i)

(ii)

i = 1, . . . , n

(i)

T 0

l i < T 0

(ii)

s ∈ {t _i,1 , . . . , t _i,l

}

U _s ⁱ (t) < L ⁱ _s (t)

t ∈ {s, . . . , s+

(T 0 − 1)}

(

10)

(

T 0

)

そこで

step 0

ブロック分けの説明は副節

3.1

200 150 100 50 0 50

h

ケース A ケース B

ケース C ケース C

t Az

スペースデブリ

s s + ( T

− 1 )

) (t U

図

8:

3.2.3

(step 1-1)

3.1

E d

(i, j) ∈ E d

(i)

(ii)

i

j

s _i , s _j

(i) i

j

| L ⁱ _s

(s i + (T 0 − 1)) − U _s ^j

(s j ) |≤ S

(s j − (s i + (T 0 − 1))) (5)

| L ^j _s

(s _j ) − U _s ⁱ

(s _i + (T ₀ − 1)) |≤ S

(s _j − (s _i + (T ₀ − 1))) (6)

(

11(a))

(ii) i

j

s i ≤ s j + (T ₀ − 1)

t = s j , . . . , s i + (T ₀ − 1)

L ⁱ _s

(t) ≤ U _s ^j

(t) ≤ U _s ⁱ

(t) (7)

L ^j _s

(t) ≤ U _s ⁱ

(t) ≤ U _s ^j

(t) (8)

(

11(b))

すべてのノード

i, j ∈ V

(i)

(ii)

s _i , s _j

(i, j)

E _d

ケース A ケース B ケース C

ˆ

t t ˆ

s s + ₍ T

− _{1 )}

h

h

t Az

) (a x

) (t L

図

9: L ⁱ _s (t)

x

60 80 100 120 140 160 180 200 220 240 260

Az

s s + ( T

− 1 )

) (t U

) (t L

スペースデブリ

図

10: (ii)

(3.2.2

)

250 200 150 100 50 0 50 100 150 200

Az

t スペースデブリ

sj sj+(T0−1) )

1 (0− +T si

si

) (t U_sⁱ_i

) (t

Lⁱ_si U_s^j_j(t)

) (t L^j_sj

250 200 150 100 50 0 50

スペースデブリ Az

t

si sj s_i+(T₀−1) sj+(T0−1)

) (t Usⁱi

) (t Lⁱsi

) (t U_s^j_j

) (t L^j_sj

(a) (b)

図

11: 2

3.2.4

(step 1-2)

ブロック化により最長路問題の規模は小さくなるので，すべての単純パスを調べる列挙法 によって最長路を現実時間内で求めることが期待できる．実際，現実のデータ

(4

)

6

[10]

3.2.5

(step 2)

ブロック

b

π ^b

π ^b

x ^b

π ^b = (1, 2, . . . , n b )

π ^b

P

(π ^b ∈ P

)

v ∈ P

n _b

P

v ∈ P

v ∈ P

u = (s 1 , s 2 , . . . , s _n

b

)

まず，

v = (1, 2)

(1, 2) ∈ E

1

2

3.2.3

(i)

(ii)

s ₁ , s ₂

(s ₁ , s ₂ )

s ₁ , s ₂

u = (s ₁ , s ₂ )

(3, 4, . . . , n _b )

v

v

u

v

u

i

i

v

s i

u

i

i

この操作によって得られた

v

u

v

U (t), L(t) ∀t ∈ [s 1 , s m

+ (T 0 − 1)]

s m

v

12

(1, 2, 3, 4)

v = (1, 2, 4)

U (t), L(t)

C

(

C

v, u

U (t), L(t)

)

U (t), L(t)

b

x(t) = U (t) + L(t)

2 , ∀t ∈ [s ₁ , s m

+ (T ₀ − 1)] (9)

x(t)

v

150 100 50 0 50 100 150 200 250

Az

t スペースデブリ

) (t U

) (t L

) 1 (

4

+ T −

s s

1

2

3

4

図

12: U (t), L(t)

3.2.6

(step 3)

ブロックごとに決定した軌道を直線でつなぎあわせることによって，観測期間

[1, T ]

4

この節では，提案手法の有効性を確かめるため，実際のデータを用いて行なった数値実験 の結果を報告する．

実験は上齋原スペースガードセンター

[4]

/

Space-Track Website[9]

ペース・オブジェクト（人工衛星・デブリなど）の軌道情報を基に，宇宙航空研究開発機構

(JAXA)[2]

ラントレンジが

1350km

15

75

T = 86940, S

= 9.5, S

= 1.0, C = 270, h = 45, T ₀ = 180

MATLAB 6.5

Pentium4 CPU 2.80GHz

1GB

2

実験

1：実際のデータを用いた実験

表

1

2

データ番号 観測期間

データ

1 2005/01/06, 11:00:00

2005/01/07, 11:09:00

2 2005/01/07, 11:00:00

2005/01/08, 11:09:00

3 2005/01/08, 11:00:00

2005/01/09, 11:09:00

4 2005/01/09, 11:00:00

2005/01/10, 11:09:00

5 2005/01/10, 11:00:00

2005/01/11, 11:09:00

6 2005/01/11, 11:00:00

2005/01/12, 11:09:00

表

1:

データ番号

1 2 3 4 5 6

スペースデブリ数

146 132 141 130 127 133

102 96 97 89 82 86

ブロック数

67 69 72 60 54 64

最大デブリ数

4 5 5 4 6 4

3

9 5 5 9 7 3

表

2:

データ番号

1 2 3 4 5 6

上界値

84 83 79 70 67 71

マスターデブリ法

40 44 31 34 32 36

提案手法

83 83 79 70 67 71

表

3:

表

2

3.2.2

ペースデブリ数である．「ブロック数」とは，

3.1

m

3

3

2

127

146

60

6

よって，最長路問題を解く手法は列挙法で十分であることがわかる．また，「

3

9

各データに対して提案手法とマスターデブリ法

(2.2

)

3

(1)

1

x(t)

F

表

3

2

マスターデブリ法では，ブロック内に観測可能なスペースデブリが

1

そのスペースデブリを観測できない場合があった．一方，提案手法は，ブロック内にあるス ペースデブリ数が

2

1,2

5

1

1

20

30

300

将来的には，レーダーの性能が向上し，捕捉可能なスペースデブリ数が増大することが予 想される．そのときの提案手法の有効性を調べるために，以下の実験

2

実験

2：スペースデブリ数を増やしたデータを用いた実験

本実験では，レーダーの性能が向上し，観測期間中に捕捉できるスペースデブリ数が

2

3

1

1

3

A,B

A

[1, 86940]

1,2

B

1,2,3

4

A

B

1

A

2

B

3

3

データ番号

A B

278 414

観測可能な数

198 290

98 112

5 13 3

16 39

表

4:

A B

155 215

153 209

表

5:

表

5

A

B

5

A

90

B

190

300

2

3

5

この論文では，最長路によってスペースデブリ観測レーダーの操作計画を立案する手法を 提案した．また，実際のデータに対して数値実験を行ない，日本で現在使用されている手法 よりも良いレーダー軌道を求められることを確かめた．さらに，将来，レーダーの性能が向 上した場合でも提案手法が有効であることを確認した．

提案手法にはまだいくつか改良する点がある．最長路問題は

NP

レーダー軌道の作成には，ヒューリスティックスな手法

(3.2.5

)

1

現実的な課題として，以下のものが挙げられる．スペースデブリの中には危険度が高く，

必ず観測しなければならないものがある．そのようなスペースデブリを必ず観測するために

は，アルゴリズムを修正する必要がある．また，複数のレーダーによって観測する場合への 提案手法の拡張も今後の課題である．そのときは複数のパスを含む最長路を求める問題に定 式化し，運搬経路問題に対する手法のアイデアを適用することが考えられる．