長崎大学工学部研究報告 第

長崎大学工学部研究報告 第

巻 第

号 平 成

1 年

月

分散協調型多体軌跡推定 システムの高機能化

217

山 本 孝 一 *･下 川 俊 彦*

吉 田 爺 己 彦 **

ImprovementofCooperativeSystemforMulti‑Target MotionAnalysュ●s

by

KoichiYAMAMOTO*･ToshihikoSHIMOKAWA*

andNorihikoYOSHIDA**

Trackestimationoftargetsfrom sensordataisacrucialissueinactivedynamicsceneunder‑ standing.Multitargetmotionanalysis,wheretherearemultiplemovingtargetsandmultiplefixedsensors whichonlymeasurebearlngSOfthetargets,istoassociatetargetsandsensordata,andestimatetarget tracksbasedonthatassociation.ThisisanNp‑hardproblem ingeneral,andsolveduslngStepWise relaxation.However,itishardtoobtaintheoptimalsolution,asthemethodeasilygetstrappedinoneof localoptima.

Weappliedthedecentralizedcooperativesearchtechniquetothisproblem,andprovedourmethod effective.Themethodusesmorethanoneprocessors,eachofwhichhasitsownpartialsearchspace, searchingmultiplepossibilitiesinparal

l

1.はじめに

近年 ,方位角のみを検 出す るセンサか らの情報 を利 用 して,移動 す る物体の軌跡 を推定 しようとす る研究 が幾 つかなされている｡ また,方位角を検 出で きるセ ンサの研究 も行なわれている｡

これまでの軌跡推定の研究は,移動 す る

つのセン サか らの方位角情報 を元 に,等速運動 をす る

つの物 体の軌跡 を推定す る単体軌跡推定 がほ とん どであ った が,文献 1)では これを複数 の物体 に対す る多体軌跡 推定 に拡張 を試みている｡

この手法は固定 された複数のセンサか らの方位角情

報 を統合 して,等速運動 をす る複数の物体の移動軌跡 を推定す るものであ る｡

この ように複数のセンサか らの情報 を統合 して適切 な解 を求 め るシ ス テ ム は分 散 セ ン サ ネ ッ トワー ク

略 して

と呼ば れ る｡

これは分散人工知能の分野 に含 まるもので,数 多 く の研究がなされている

) ｡ なかで も通信戦略や情報統 合の統合アルゴ リズムは主な研究テーマ とな ってお り,

) ) はその例題 として有名であ る｡

平 成

1 年

月

日受理

*九州大学大学院 システム情報科学研究科 福 岡市東区箱崎

(GraduateSchooloHnfom ationScienceandElectricalEngineering,KyushuUniversity,Hako2:aki,Fukuoka)

**情報 システム工学科

218

山本 孝 一 ･下川 俊 彦 ･吉 田 禾 己彦

1)で提案 された多体軌跡推定の手法は,全てのセ ンサか らの情報 を 1つの問題解決

に集めて集中的 に処理す るものである｡

推定 にあた ってほ最尤法 を用 いて解 を探索 してい る｡ しか しこの間題 において,解空間には無数の局所 解が存在 している｡そのため局所解 に頻繁 に陥 って し まい,最適解が得 られに くい とい うことが この手法の 大 きな欠点である｡ それを改善するために,

確率的探索である焼鈍法

を導 入 しているが,その結果処理時間が大幅に増大 して し まった｡一般 に分散処理化す ることによる利点 として 解の多様性が増大す ることにより局所解 に陥 る危険が 減少 し,処理の分･ 散化に より処理速度が向上すること がいわれている｡

論文

)では 1)の手法を基 に して,システム内に 複数の問題解決

を存在 させ

同士 が通信 に よ

り協調 を計 る分散協調処理 を提案 した｡

また実際には,最初か らデー タが揃 っているわけで はな くデー タは一 つずつ逐次的 に入力される｡現実の 世界において この ようなシステムを使 うためには この ような入力に対応で きるような入力のシステムが必要 である｡

以下では第

章で多体軌跡推定の問題 を形式化 し, 第

章で従来の集中処理 による推定及び焼鈍法 を含む 手法 を船介する｡第

章で分散協調処理の手法を提案 し,第

章で実時間処理 システムへの改良およびその 実装について述べ,第

章ではそれ らの手法 と従来の 手法 についてそれぞれ実験並びに比較 を行ない,最後 に第

章でま とめ る｡

2.多体軌跡推定間窪

図 1に示 す ように,システムは等速運動 をす る

個の ターゲ ッ トと, ターゲ ッ トの方位角を検出で きる 固定 された S個のセンサか らな る｡各センサは時刻 毎の方位角デー タを得 る｡多体軌跡推定 とは, これ ら 複数のセンサか らのデー タを統合 して各 ターゲ ッ トの 初期状態 ( r br

, aV y ) を求め るものであるO

ここで問額 となるのは,

･センサの得たデー タとターゲ ッ トとの対応 をどの ように とるか

･対応 を とったデー タか ら軌跡 を どの ように推定す るか

の

つである｡

これまでシステムの概略 を述べたが, これ らの間男 をを実際 に形式化す る｡ ターゲ ッ トの状態は位置 ( 稚,

y,f

) と速度

hV f , f )か ら次の ように定義で きる｡

図

ー

ヽノ

一々 ･Q

ィ川Ⅷ■ U

Ⅶ川U

J

一帖

システムの概要

,t = 1,･ ･ ･ ,N

ここで

yf,(A)

‑y f ,(

r f y( k)

v F x( A)

v ,( f A)

(1)

(2)

t は ターゲ ッ ト識別子 , Aはサン′ プ リング間隔,k は 時刻識別子 を表す｡センサの状態 は位置 ( r 去

よ

り

Xi‑

, i

^{( 3)}

と定義で きる｡ ここで iほセンサ識別子 を表す｡セン サ

か ら見たターゲ ッ トtの相対的な状鹿ベ ク トルは

Xt

･ i ( k)‑Xl ( k)‑Xi

か ( k)

rfyi(A)

vf.(k)

v i( k)

(4)

時刻 kにセンサ iがターゲ ッ ト t に関 して観測する方 位角デ‑ タは

pt

･ "k

I

^猪

^{L ･ "k) ( 5 ,}

分散協調型多体軌跡推定 システムの高機能化

とな る. ここで L l

はセンサ iにおけ る白色 ノイ ズであ る｡以上 よ り時刻 kにセンサ

が観測す る観測 ベ ク トル

は式

よ り

(6)

となる｡ また,時刻 kまでの観測ベ ク トルの黒帯 βkを

βk≧(β

l( 1 )I ,‑

I ,‑ , P

( 1 ) ;‑ ,

( 7 ) と定義す る｡

センサの観測 した観測ベ ク トルには,それぞれの観 測値 が どの ターゲ ッ トに対応 しているか とい うデー タ が含 まれていないので,観測ベ ク トル β

( k) に

のみか らな る

の割 り当て行列

を乗 じて や る必要 があ る｡ この

は

通 り存在 す る｡

例 えば

な らば

は以下の

通 りが存在 す

る｡ 10 0 01 0 00 1 010100001 0

001

100

1

001

010

0

100

010 100

010

001 EiiZ8

[ 0' ( k)

は観測ベ ク トル βi ( k) の j番 目の要素 が ターゲ ッ ト

に対応す ることを表 す｡例で示す｡

0

100

001

β 1 ･ i ( k )

β 2･Z(k

)

β 3･i(k)

⊂

⇒

日

⁾

β2

･

(correspondtothetarget1 ーco汀eSpOndtothetarget2 ーco汀eSpOndtothetarget3

割 り当て行列の集合 :

ck 空く C 1( 1 ),･ ･ . , Cl( A) ,‑･ , Cy( 1 ),･ ･ ･ ,Cy( k))

が全観測デー タの ターゲ ッ トに対す る組 み合わせ を決 定す る｡

システム全体は式色ゆで記述で きる.

Xt･Z'(k+1)

‑

,‑,

,･ ･

( 1 0 )

ここで

0‑

0 人 ︼ O 1

A 0 1 0

O 1 0 0

1000

219

は状態遷移行列 を表 す｡

3.

集中処理型の推定

全 てのセンサの情報 を

つの

に集 めて集 中的 に処理 す る参考文献

)の手法 を述べ る｡

ターゲ ッ トの推定初期状態

k .

‑

ここで

ki.‑

,i

‑ 1 ,I ‑,N,

義(o)

a , (

戻(o)

?,(

o)

, J=

1,‑,N,

( 1 1 )

3日琶

が与 え られ る と,センサ

が時刻 jに得 るターゲ ッ ト t に関す る方位角デ‑ タは

BL･Z'O',k o,‑tan‑lgS ]･ ^(13,

と推定 で きる. センサ Sの時刻 j におけ る推定観測ベ ク トルは式柏 よ り

β1･

' O

打nu

丸

S

き

, ' U ,

‑ ^{( 1 4 )}

とな る｡ また時刻 kまでの推定観 測 ベ ク トル の累 積 は

bh(k.)

仝(

,X

;‑,

･ ･ ･ ,

P s(

I

' ,I .

)')'

s

E‑

t Ni 葺

R,I 1

l pL U

I U)

&‑

3日囲

実際の ターゲ ッ トの軌跡 に対す る推定 した初期状態 の確 かさの評価 に平均二乗誤差 ( ASE)を用 いる｡

A( βkE Ck

ie x p ( ‑ ‡ ･ , 妻, f l l P t . O

)

^{0･ G･ , ･ &･ b ･ ･}

^,

･R{.lpiO･ト OIO･)･

約･ ,

s

E‑

去∑

( 1 3

こ こで

Iはセンサ

に おけ る ノイズの共 分散

行列

であ る.E とターゲ ッ トの関係 を考慮 し

て式87 ) を書 き換 える と

220

E‑

S + Nt f

s

i N T t f . I _∑ ^k

⁽

^{( . I .} ･ f l . ･ 3

i j ∑ ^{Tl ＼ q} i

山本 孝一 ･下 川 俊彦 ･吉 田 紀 彦

qE

となるO ここで

は

を表す｡

多体軌跡推定の問題 は, この平均二乗誤差

を最小化する問題である と言い替 えることがで きる｡

まず割 り当て行列 Ckを固定 した場合

法 を用いて ki oを決め ることで E

を最小化すること がで きる｡ つま りターゲ ッ トtについて並べ られた方 位角のデー タ列 か らターゲ ッ トの初期状態

算することがで きる｡ また,式￠郎ま非負の数の加算で あるので,X｡が与 えらた場合に

り こ関 して E を最 小化することは,

に関 して個 々の項 を最小化す ることに等 しい｡ よって次の操作 を行な うことで,初 期状態 9.を固定 した場合に

を最小化する

を求め るこ とがで きる｡

Foral10万)

, i

,･ .

, S , i

,‑

OU)

RL

l

pi

)

0 ' G ^{' )･ bi U' ,}

[

βi

) ‑ O G ^{･ )･ 的 ･ ,}

Next

i

このアルゴ リズムにおいて 鶉 と

Eは ‖司目の繰 り返 しでの

と Chの解である

l)と

の両段階 において

は単調減少 となるので, この繰

り返 しで E は局所的な最小値 には到達 す るこ とが保 証 される｡ しか し, この解空間には局所解が多数存在 してお り, この手法ではかな りの場合に局所解に陥 っ て しまう｡そ こで これを避けるために焼鈍法を含む手 法 が提案 された｡

4.

分散協調 による改良

4,1

分散処理化

分散処理化にあた り,システム内の全センサを複数 のグループに分割する｡分割 されたセンサ群は

つの

に属 す こ とにな り,それ らの デー タの処理 は各

が受け持 つ｡

つのセンサが複数のセンサ群 に含 まれることも許す｡

また,グループ分けす ることに より解に多様性が出 て,局所解に陥 る可能性が減 る とい う利点 もある｡ ま た, これ らの中間解を交換することにより,協調的な 処理 が実現で きるので,効率的なシステムの構築が期 待で きる｡

4.2

通信戦時

4.2,1

分牧歌立型

それぞれのグループがお互いに通信 を行なわない最 も簡単 な分散処理 の手法｡各

は集中処理型 と同 様の反復 を繰 り返す もので,集 中処理型の ものが複数 個集 まっただけの もの と考 え られ る｡

各

はそれぞれのローカル

が最小になるよ うに軌跡 を推定 す る｡通信 を行 なわないので,他の

での結果は軌跡推定 に全 く反映 されない｡ しか し 集中処理型 と比べ る と,センサ群が複数存在するので 解の多様性が得 られる｡ また,処理 を分散 しておこな

っているので処理 コス トも軽減 している｡

4.2.2

ローカル法

ローカル

に基づ く通信戦略である｡

回の軌 跡推定 が終 了す る毎 に各

はその時点の推定初期 状態 を通信 によ り交換 し合 う

はその ように して 得た推定初期状態 か ら自分のセンサ群 におけるローカ ル

を計算する｡結果 として

はシステム内の グループ数だけローカル

を得 るが,その中で最 もローカル

が小 さい ものを次の反復 における初 期状態 として採用す る｡ つま り反復毎 に各

は複 数の初期状態の候補の中か ら自分達のグループに とっ て最 も都合の よい初期状腰 を選んで採用 してい く｡ シ ステム全体 としての利益は考慮 に入れてお らず,それ ぞれの グルー プは利 己的 に働 くといえ る｡ しか しグ ループが複数存在するので,解の多様性が得 られる｡

4.2.3

グ ローバル法

グローバル

に基づ く通信戦略である｡

回の 軌跡推定 が終 了す る毎 に各

はその時点の推定初 期状態 におけるグローバル

を計算する

は 自分の推定初期状態 とそれか ら得 たグローバル

を通信 に よ り交換す る｡通信の結果各

はシステ ム内のグループ数だけ初期状態 と,その時のグローバ ル

を得 る｡その中か ら最 もグローバル

が 小 さい ものを選 んで次の反復の初期状態 として採用す る｡結果 としてシステム全体か ら見て最 も適 した初期 状態が,全てのグループで一様 に採用 される｡ この よ

うにす るこ とで反復毎 に各

で局所解 を避 けて初 期状態が選ばれることになる｡通信に より各グループ はシステム全体 としての 目的を考慮 して振舞 う｡

前述の ような方法で推定 を進めてい くが次に各プロ セ ッサの推定処理 が終 了す るための条件 を以下 に示 す｡

･各プロセ ッサの推定処理 の終了条件 は

分散協調型 多体軌跡推定 システムの高榛能化

変化 )

とす る｡ それ以降 ,その プ ロセ ッ サは推定 しない｡

･その他のプ ロセ ッサは,終了 したプ ロセ ッサの推 定結果 を引続 き利用す る｡

･全プロセ ッサが推定 し終 えた時を終了 とす る｡ こ の時 ,各 プ ロセ ッサ の

と比較 して,最 小

を出 したプ ロセ ッサのデー タを最終推定結 果 とす る｡

今 までのシ ミュレーシ ョンによる実験 では,デー タの 格納は,多次元配列 を用 いていたため,デー タを上書 きしな い限 りその デー タは いつで も参照 可能 で あ っ た｡ さ らに,通信 を必要 とせず,配列参照でデー タ交 換が可能なので,送受信q)タイミングな ども気 にす る 必要 もなかった｡ しか し,実際の分散環境下では,過 信に よるデー タのや りとりを実現す る場合,送信側 と 受信側がそれぞれ然 るべ き処理 を とらなければな らな い.具体的 にはシ ミュレーシ ョンではデー タが欲 しい 側がその部分の配列 を参照す るだけで参照 され る側は 何の処理 も必要なか ったが,分散化 され る と参照 され る側がまずデー タを送信 し,参照す る側 がそのデー タ を受信す る とい う処理手順 にな る｡

実際の分散環境下 では,いつ他のプロセ ッサが終 了 したのかが見 えないので,他のプロセ ッサが終了 した に も関わ らず,デー タを待 ってい る状態 にな る可能性 があ る｡そのためには他のプロセ ッサの状況 を把握 し て,それに応 じた処理 を しなければな らない｡ そ こで プ ロセ ッサの状態 を示す

を導 入 し

を送受 信す るこ とに よって,他のプロセ ッサの状態 を把握 さ せ るように した｡具体的 には

と

があ り,前者 はプ ログ ラム を終 了すべ きか どう かを判定す る

で,後者 はそのプ ロセ ッサでの計 算が終了 したか どうかを示す

であ る｡

サーバが, クラ イアン トか ら

を受 け とるこ とに よって,各プロセ ッサの状態 を知 ることが 出来,全てのプロセ ッサの計算が終了 した時 クライア ン トに

を送信 し,プログラムを終了す る0

5.

実時間処理 システムへの改良

実時間処理 システムへの移行

実時間処理 システム とい うのは,次 々 と入力デー タ が入 り,それ らを次 々と裁 いてい き,解 を求め るよう なシステムの こ とである｡

これを多体軌跡推定で実現 しようとい うのが,今回 のシステムである｡具体的 には,次 々 と得 られ る,固 定 された複数のセンサか らの方位角情報 を統合 して, 等速運動 をす る複数の物体の移動軌跡 を次 々 と推定 す

221

るシステム, と再定義 され る｡

その概要 を下 に述べ る｡

･このシステムへの改 良点を少な くして拡張す る形 で実装す る方法 が望 ま しい

･入力が間欠的 にな り従来 よ り多 くのデー タを連続 的 に扱 わねばな らない｡

一連続的 に入 って くるデー タの中か ら前 システム と同数のデー タを選びだ し推定 を行な うとい う 形 で実装

･このシステムの処理速度が入力デー タに追 い付か ない場合,現在の処理時間 を短縮 しなければな ら ない可能性 もあ る｡

これ らを考慮 しなが ら, 実装を進 めて行 く必要 があ る｡

5.2

分散型実時間処理の入力システムについて 入力はセンサ に よって行なわれ る｡ その過程は次の ようになる｡各センサの入力はグルー ピングに したが って,入力デー タを分散 し,割 り当て られたプロセ ッ サに入力され る｡ それに伴い,各プロv t f ‑ ッサは入力さ れたデー タでそれぞれ推定 を開始す る｡ これまでのシ ステム と今回q )実時間処理 システムの入力の違 いにつ いて述べ る｡

今 までは,デー タは一 つづつ入力され るのではな く, 一定数の入力デー タをま とめてシステムに入力 してい た｡ よって,実時間処理 システムを実現す るに当た っ ては今回 もバ ッチ処理 に よるシ ミュレーシ ョンでシス テムを構築 した｡しか し,実時間処理 を実装す る場合, 推定処理 を進めなが ら次 々と入力され るされ るデー タ を扱 わねば な らない｡ 将来的 にセンサの閉場 や 入 力 デー タの同期 に対応で きるようなモデルを考案 しなけ ればな らない｡

まず,センサか ら送 られて きたデー タを入力システ ムに蓄積す る｡ この

か ら一度の推定 に

が使 うデー タの個数のみを入力す る｡ そのデー タを選 ぶ関数 についてであ るが,以下の ようない くつかのア

イデ ィアが考 え られ る｡

1

.単純 にデー タの個数 を増やす

‑･ ) ｡ これは推定回数 を減 らす ことが出来 る｡

2.n

個 デー タがたまるご とに推定 を行ない,処理 を 終 え る と次 の n個 で推定 を行 な う ( 隣接 した推定 間でのデー タの重 な りがない)｡具体的 にはデー タ をため る部分 と計算部分 を分け,前者はデー タを

個 ず つに区切 りなが らため続 け,後者 はその区切 られた n 個ず つのデー タで推定 を行 ない続 け る.

これ に よ り入 力 され た デー タを無駄 にす る こ とが

な く,正確な推定が可能にな る｡

222

_{山本 孝一 ･下}

_{俊彦 ･吉田 紀彦}

3･queue

の ように S個だけ新 しいデー タを入れ 古 い順 に S個 デー タを破 棄 して推定 を繰 り返 す方法 である｡ この方法の特徴 としては,

･S

の履歴 を記憶 しておいて,動的 に次回の

の値 を決定する方法 も考 え られる｡

各方法の主な短所は以下の通 りになる｡

1.計算量が莫大 になる｡

2.

この方法は入力の頻度が高い場合に処理 が入力に 追い付かない｡

3.

入力デー タを無駄 にする可能性がある｡

上の

つの中で無視で きないのは

1と

の方法で あろう｡ この

つはいずれ もシステムのパフ ォーマン スを下げることになる｡ しか し

の短所は, このシス テムの性質を考 える と重要ではない と考 えられる｡従 って今回は 3の方法を採用 した｡以下 に, この方法で の具体的な実装方法について述べ る｡

まず

については現システムの入力 と同数で考慮｡

次 に Sについては

回 目の推定 と

回 目の間 に新たに入力された数を指定 している｡すなわち,令 推定毎 に新 し く入力されたデー タ数だけず らす とい う ことになる｡実際 には

個のキ ューを用意 し,新た にデー タが入力される度 にキ ュー イング してい く｡ こ の時排 出されたデー タは使わない｡要するに時系列 に 並 んだ最新のデー タの内,新 しい順 に n 個 を選 ぶ と い うことである｡ この方法によ り入力デー タの数 によ らず確実 に一定個数の最新デー タを確保で きる｡その アルゴ リズムを疑似言語で表現すると以下の ようにな る｡

要素数

の配列を用意す る｡

ifnew̲data

for(i‑0;i<n;i++) begin

data[k]‑data[k+1];

datalmax̲data]‑new̲data;

end

5.3

システムの実装

5.2

節 で,入力システムの構成 について述べた｡ こ の構成 を実装 レベルで書 き下す と,

1.最初 に初期位置 と速度ベ ク トルを入力させ, これ を元に予めサンプ リングを作 る｡

2.

それ らの中か ら

を選びだ しシステムに入力

Sの値 についてはプログラムの始めに入力す る ように している｡そ して,推定毎に Sの分だけず ら したデータをシステムへの入力 とした｡

そのアルゴ リズムを疑似言語で表現する と,

j

j

for(i‑0;i<num̲oL target;i十十) for(t‑0;t<n;t++)

sensor.B[i][t]‑sensor.sample

⊥B

で表現で きる｡ ここで

はセンサの 敬

はターゲ ッ トの数 とす る｡

ただ し今回実装 したシステムは実時間的に一 つずつ 入力 され る形式 ではな く,各推定間の入力が S回存 在 した と仮定するシ ミュレーシ ョンである｡従 って, 理論的 なアル ゴ リズム とは入 力の タイ ミングが異 な

る｡

6.

実験 と評価

6.1

シ ミュレーシ ョンとの比較実験

分散環境での実験

まず,論文

)でのシ ミュレーシ ョン と今回実装 し た実際の分散環境でのシステムで性能比較 した｡但 し, 前節で述べた,終了条件は

つのプログラムで実際 に 分散化 されたか どうかを除いて全 く同 じにするために 変更 した.

その際, ターゲ ッ トを

個センサを

個 としてセン サを配置 した｡

ここでは, 1つの例についての実験 を行なった｡ こ の実験でのサンプ リング数 もシ ミュレ‑シ ョソ と同 じ 条件 にす るため

とした｡次 に推定結果 を表す と 図

の ようになる｡ ここで

の推移は図

の よ

うになった｡

また,その推定軌跡 を図

に示す｡ これ らによ り実 際に分散化 して も,性能を落す ことな く推定可能で, その速度比は

であることが分かった｡ この ことは 論文

多体軌跡推定 において,非常 に有効であることを改め て示 している｡その理 由 としては分散処理化 によ り処 理能力が向上 し,局所解に陥 る危険性 が減 った ことが 挙げ られ る｡ また

同士 が協調 す るこ とで さ らに 精度が向上 していることも分かる｡

図

シミュレーシ ョン と分散環境の比較

Time 52.07 21.375

速度比

分散協調型多体軌跡推定 システムの高楼能化

TransitionofASE

山SV

5000 4500 4000 3500

3000 2500 2000 1500 1000 500 0

1(X

X )

4∝)0

2㈱

0

PEl ‥

PE2 ‑‑I‑〜‑‑‑

PE3‑ 日■一一一

5 10

iteration

図

の収束状況

15 20

Truetracksandestimatedtracksofthetargets

0

7x

図

推定軌跡

80(X) 10000

6.2

収束条件 と実行時間の関係

収束条件の変化 に伴 い,時間 も当然変化す る｡条件 が きつい と収束 に時間がかか るが,解の精度は良 くな る｡反対 に,条件が緩 い と収束 には時間がかか らない が,解の精度は悪 くな る｡

一般的に収束条件 を厳 し くすれば, よ り良い解 が得 られ るが,システムに よってはそ こまで厳密な解 を必 要 としない場合 もあ る｡例 えば非常 に入力が多 く,樵 定 を数多 くこな さなければな らない場合,一つの推定 に時間を とって精度 を高めるこ とよ り,入力に追 い付 きなが ら推定 を こなす こ との方 が重要 であ る｡

ここで,精度 を落す方法 について考 える｡ このシス テムは

に よって処理 を進めている｡具体的 には 収束条件の判定 に使 われた り,最 良な推定初期状態 を 選 ぶ時 な どに も使 われ る｡ つま り, このシステムにお いての精度は

の値 に依存 してい る｡従 って,収 束条件 であ る

の値 を緩和 す るこ とに よって,精度 を落す こ とが出来,処理の高速化が 図れ る｡ ここで

とは,前

での

の値 であ る｡ その図

を示 す｡

図

収束条件 と実行時間

223

pre̲ASE‑ASE iteration finalASE time 0.00001 10 0 21.25 0.0001 10 0 21.00 0.001 10 0 21.00 0.01 10

0

前論文では,(

であ ったが, 今回

にまで緩和 して も

は

程度 に収 まる

こ とが分 かる｡推測すべ きデー タのオー ダーが

程 度であ るこ とを考 えて も十分小 さい といえる｡逆 に実 行時間は

程度 にまで短縮 され る｡

6.3

曲線推定の実額

次 に実時間処理 を実装 したシステムに関す る実験 を 行 な った. 今 回は一 度 の推定 に使 われ るデー タ数 は

とし,次の推定 でず らすデー タの個数 は

として い る｡ この ことは,一度の推定 中に新たに入力され る デー タの個数 が

個であ るような環境 を想定 してい る とい うことであ る｡ また,今回は推定回数 を

回に固 定 した｡従 って,全部 で使 われ るデー タ数 は

10×89‑990

とい うこ とにな る｡ また, この推定 では 精度は

に した｡

今回使用 した曲線の軌跡 は図

,

であ り,推定結 果は図

の ようになる｡入力軌跡

に対 しての推 定 結 果 は 図

の よ うに な る｡ この 時 の 各推 定 で の

Trackofthetargets 30000

25000

2㈱ 0

> 15000 10000 50000

1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 5 _X 0 0 0 ^{6 0 0 07 0 0 08 0 0 09 0 0 0}

図

入力軌跡 1

224

山本 孝一 ･下

俊彦 ･吉 田 紀彦

iteration

の数 は図

の ようにな る｡ また,入力軌跡

に対 しての推定結果は図

の ようになる｡ この時の 各推定での

の数は図1 1 の ようになる｡ これ らの結果を見 ると,入力軌跡 1の ような緩やかな曲線 に対 しては,かな りの精度で推定可能であることが分 かった｡ しか し,入力軌跡 2 の 3 次曲線の ように曲率 が きつ くなる と少 し誤差が出ている｡各

の

Trackofthetargets

1 0 0 0

0 0

4

05

X 図

入力軌跡

Tracksoftargets

100 20003000 4∝)05I000… 7㈱80009㈱

図

入力軌跡 1に対する推定軌跡

TrarlSitjorlOf托eration

10

8 .⊂:2 6 i. a

4

2

0

¥

芳 ■ 一 一 ‑一 ■ ■

^{‑. . . . ･ . . ･ . .}

PE芝‑‑

‑ * 一 一 一 一

PE3 ‑

‑ ‑ 1 . . ‑

0 20 40 60 8⁰ 100

estbTlatiorl

図

の推移

30(×)0

25000

20000

I. 15∝)0 1㈱0 5000

0

35知2Lb201

uO雪2)○よ

Tracksoftargets

1000 2000300040005X㈱ 6000 70008α)0抑

図

入力軌跡

に対する推定軌跡

Trans托ionofiteratbn

PE1 ‑ ‑‑ PE2 ‑‑‑‑★一一一一

PE3 .‑‑トー一一

ニ L...･.r. .

0 20 40 60 80 100

ostimation

図

の推移

推移 を見て も図1 1の方が

の数が多 くなって いる｡ また,曲率 が大 き くなっている時 に

の数が増 えている｡ これは収束 に手間を要 した ことを 示 している｡

7

.おわ りに

多体軌跡推定の問葛は従来の方法では 1つの問題解 決 PE で集中的に処理 されていた｡ また この間額の 解空間には無数の局所解が存在するため局所解 に陥 っ て しまうことが多 く,最適解が得に くい という欠点が あった｡それを改善するために確率的探索である焼鈍 法が導入 されたが,これは処理速度が大幅に遅 くなっ て しまった｡

一般 に分散処理 を行 ない協調 す るこ との利点 とし て,解の多様性が増 し局所解 に陥ることが減少す るこ

と,処理能力が向上することなどが挙げ られる｡

そ して,通信戦略 としてローカル法を採用 し,従来

の手法 を元 に複数の間層解決 PE を存在 させ,分散

協調処理 を行な う手法がシ ミiレーシ ョンされ 効果

を得た｡ この結果は多体軌跡推定の問題において分散

協調処理 が非常に有効であることを示す ものである｡

分散協調型多体軌跡推定 システムの高楼能化

そ こでその分散協調処理 を実際 に分散化 された環境 に実装 し,性能 と速度 をシ ミュレーシ ョン と実験比較 した｡ その結果 として性能 を落す ことな く実装 で き, その速度 はシ ミュレーシ ョンの

倍であ ることが分 かった｡ これに よって実際の分散環境で もこの手法 が 有効 であ ることを改めて証 明 した｡

また, より現実的なシステムを 目指 し,実時間処理 システムへの改良を行な った｡その中で, よ り高連 な 処理 を実現す るために,収束条件 を緩和す ることに よ って推定精度 を落 し,実行時間 とのバ ランスを とるこ とを試 みた｡ さ らに曲線 を細分化 し直線近似す るこ と によ り推定す ることに成功 した｡ これに誤差を加 えて も推定 で きることも分 かった｡

最後 に一度の推定 で使用す る入力数 を変化 させて実 験 を行なった｡ ここでは,緩 い曲線 に対 しては入力数 を減少 させ るこ とに よ り処理 を高速化で きた｡ また, 曲率の強い曲線 において も微妙 にバ ランスを整 えるこ

とに よって推定可能であ るこ とが分 かった｡

今後の課題 としては,実際 にセンサを使 って,シス テムにデー タを入力させ推定 を試 み ることが挙げ られ る｡

225

参 考 文 献

1)Pe主‑yihTingandRonaldA.Iltis,MultiTarget MotionAnalysisinaDSN,IEEETransactionson System,Man,andCybernetics,γol.21,no.5,pp.

1125‑1139,Sep/Oct.199

1 .

2)D.N.Jayasimaha,S.S.IyengarandR.L Kashyap,InformationIntegrationandSynchroni‑ zationinaDistributedSensorNetworks,IEEE TransactionsonSystem,Man,andCybernetics

,

1

1 .

D.Corki

l

Huhnsed,DistributedArtificialIntelligence (1985),MorganKaufmannPub,pp.29‑58 4

)三谷幸 男,分散協調 による多体軌跡推定 ,九州大

学修士論文