大阪大学 大学院工学研究科 電子制御機械工学専攻

1D1-09

効率的かつ反応性のよいロボットシステム実現のための プランニングと行動の並列スケジューリング

Realizing Ecientand Reactive Rob otic System inDynamic Environments

by ParallelScheduling of Planningand Action

三浦 純

JunMiura

白井 良明

YoshiakiShirai

大阪大学 大学院工学研究科 電子制御機械工学専攻

DepartmentofComputer-ControlledMechanicalSystems,GraduateSchoolofEngineering,OsakaUniversity

Thispap erdescrib esametho dofparallelschedulingofplanning andactiontorealizeanecientandreactive

rob oticsystemindynamicenvironments.Themetho dusesapartialplanningresult,whichcomesfromaniterative

renementplanning,todeterminefeasibleactionstob eexecutedinparallelwiththeplanningpro cess. Themetho d

isappliedtoamultiple-cameramultiple-persontrackingproblem.

1.

はじめに

知能システムは通常，複数の機能要素の集合として設計され る．例えば，従来のロボットではセンサ部，計画部，行動部に分 割され，通常この順に逐次的に実行され，一つの部分は前の部分 の結果を利用する．資源や時間の制約が厳しいときにはこのよう な逐次的実行で十分であるが，そうでないときには効率と反応性 を高めるための戦略が必要である．ロボットのような物理的エー ジェントでは，並列実行可能な複数のプロセッサによってシステ ムが構成されている場合が多い．例えば，視覚移動ロボットでは 視覚認識，行動計画，動作制御の三つのプロセッサを用いること がある．そのような場合に，必要な機能要素を複数のプロセッサ に分配し，それらを並列実行することを考える．

われわれは移動ロボットのプランニングと行動を並列化する ことにより，その効率を高める手法を提案した^[三浦^00]．この ような並列化の典型的な例は以下のようである．いま，ある町の 中心部から町の東部に行こうとしており，助手席の友人が地図を 見て道を探しているとする．この場合，目的地が東部にあると分 かった段階ですぐに東へ車を走らせてよい．具体的にどの道を通 るにせよ，この行動はおそらく大きな損失にはならないからであ る．これを一般的に述べると，現在からある程度未来までの間の 適切な行動を決定するために十分な情報が得られれば，さらなる 情報収集や計画生成の終了前にその行動が並列実行可能である，

ということである．このような並列化の実現のために，現在のプ ランニング過程と並列に実行可能な行動集合を選択するための基 準⁽一貫性基準⁾を問題ごとに定義し，それを用いて並列実行可 能な行動集合を選択した後，最適な行動を決定する手法を提案し た．静的環境での移動ロボットのナビゲーション問題に適用し，

並列化により効率が向上することを示した．

本論文では，まずこのような並列化をより一般化した形で説 明する．さらに，動的環境下でのプランニング問題に適用する．

動的環境では効率と反応性のトレードオフの問題が重要である．

すなわち，プランニングを簡単化して反応性を高めると，局所的 なプランニングの結果として，非効率的な行動が選択される可能 性がある．一方，プランニングに時間をかけると一般に反応性が 低下する．そこで，並列化によって環境変化に対する反応性をあ まり落とすことなく効率を上げることを目指す．具体的な例題と 連絡先^:三浦 純，大阪大学 大学院工学研究科 電子制御機械工学 専攻，〒^565-0871吹田市山田丘^2-1，[email protected]

して複数のカメラで複数の人間を追跡する問題を取り上げる．

自律エージェントを制御するための階層的アーキテクチャが 多く提案されている⁽例えば，^[Bonasso97])．これらの研究は 主に熟考と即応の統合を扱っており，そこで考えられている並列 化は，すでに選択された現在の動作ステップを実行しながら，次 の動作ステップを計画するというものである．このような並列化 は例えば実時間探索^[Korf90]の考え方を適用して実現できる．

それに対し，本論文で扱う並列化は最終的な動作ステップが決定 される前に行動を開始するものでプランニングしながらの行動と 呼んでいる^[三浦^00]．

2.

機能要素間の依存関係の分類

2.1 生産者/消費者という見方

情報の依存関係がある²つの機能要素を，生産者と消費者と いう観点から見ると，生産者は製品を生成し消費者はそれを利用 する．このような関係はロボットにおいて例えば，地図生成部と 軌道生成部との関係，軌道生成部と動作制御部との関係に見られ る．本論文では，プランニング部とプランに基づく動作選択部を 生産者，消費者の関係の例として考える．

2.2 強依存関係と弱依存関係

生産者が一定時間計算した後に最終結果を出力するような，

いわゆる一撃型の場合には，消費者は結果が出るまで何の情報 も得られない．このような関係をここでは強依存関係^(hardde-

p endency)と呼ぶ．²つの機能要素が強依存関係にある場合，

それらは並列化できない³¹．この関係はスケジューリングにおけ る順序制約^[Zweben94]に相当する．

生産者が処理の途中で何らかの中間結果，例えば生成物の候 補集合に関する情報を提供でき，かつ消費者がその結果を行動 決定に利用できれば，消費者は生産者の処理の終了を待たずに行 動を開始することができる．このような関係を弱依存関係^(soft

dep endency)と呼ぶ．弱依存関係はプランニングしながらの行

動を実現するための重要な考え方である．図1は2つの依存関係 の比較である．

31 もちろん，先の実時間探索の場合のように，ⁱ番目の動作とⁱ⁺¹番 目のプランニングの並列化は可能である．

consumer producer

time final product

consumer producer

time intermediate results

hard dependency soft dependency

図^2: 複数カメラ複数人物追跡問題

3.

弱依存関係のための並列スケジューリング

3.1 扱う問題と並列スケジューリングの典型例

本論文では，図²に示すような，複数のカメラで複数の人物 を追跡する問題(multiple-camera multiple-person tracking problem,MCMP問題と呼ぶ⁾を扱う．

MCMP問題^{: M}人の人が部屋の中を自由に動く．各人はと きどきドアの一つから出てまた戻ってくる．^N個のカメラが天 井に取りつけられており，各カメラはある範囲内で観測方向を変 えることができる．単一のプランナが現在どれかのカメラで追跡 中の人物，すなわち位置と速度が推定されている人物を各カメラ に割り当て，各カメラは割り当てられた人物を独立に追跡する．

このシステムの目標はある決められた時間の範囲で，できるだけ 多くの人物を追跡することである．なお，カメラは人物を視野に 入れればその認識は自動的にできるものとする．

図³は弱依存関係を利用して，人物のカメラへの割り当てが終 了する前にカメラが動き出すことのできる状況の例である．図 中，^camera1は⁷人追跡可能で，そのうちの³人は^camera2 も追跡可能である．残りの⁴人は^camera1だけが追跡できる．

この場合プランナは共有されている3人の割り当てを決める．

camera 1は現時点では割り当てが分からなくても，最終的に⁴

人から⁷人の人物が割り当てられることが分かる．⁴人だけな ら^Aの方向へ視野を移動することが望ましく，⁷人なら^Bの方 向が望ましい．したがって，良い移動方向はおよそ^Cの方向で あろう．ここで，^\良い^"という言葉は，最終的にどのような割

person tracked only by camera 1 person tracked only by camera 2 person shared by both cameras

A B

C current center position FOV (field of view)

of camera 1 FOV of camera 2

図^{3: camera1}の視野の可能な移動方向

り当てになってもそれほど損をすることはない，という意味であ る．したがって，そのような良い移動方向が選択でき，プランニ ングと並列に動作できれば，効率を落とすことなく十分な反応性 を保つことができると思われる．

3.2 繰り返し改善

弱依存関係の実現のためには，生産者は中間結果を繰り返し 生成する必要がある．そのために，最終結果の候補を徐々に絞っ ていく，繰り返し改善処理^{[Bo ddy89]}を利用する^[三浦^00]． 繰り返し処理は最終結果が出た時点で終了する．また，動的環境 では計算資源の有限性を考慮し，次の終了条件も設定する．

最低限の反応性を確保するために，決められた時間が経過 したら繰り返しを終了する．

繰り返しによる改善がある程度以下になったら，繰り返し を終了する．

3.3 一貫性基準

消費者は生産者の中間結果を利用して次の行動を決定する．

そのために，生産者の現在の処理と消費者の行動との間の一貫性 という考え方を導入する．消費者の行動が，現在の生産者の処理 によってもたらされるいかなる最終結果に対しても効果的である とき，その行動は一貫性があると言う^[三浦^00]．消費者は一貫 性のある行動集合から適切なものを選択して実行する．一貫性の 基準は一般に問題固有であり問題ごとに設計する必要がある．

どのような一貫性基準を用いるかは全体のシステムの効率に 影響を与える．緩い基準を用いれば，消費者の多くの行動が一貫 性のあるものとなるため，早い動き出しが可能となるが，最適な 行動から大きくはずれた行動が選択された場合，全体の効率は落 ちるかも知れない．一方，厳しい基準を用いれば実行される行動 はよいものになるが，動き出しが遅くなるため，やはり結果とし て全体の効率が落ちるかも知れない．このようなトレードオフに ついて後で実験結果を示す．

4.

実装と実験的評価

4.1 詳細な問題設定

MCMP問題⁽複数カメラ複数人物追跡問題⁾のためのシミュ レータを製作した⁽図⁴参照⁾．先に述べた一般的な問題設定に加 えて，以下の設定を用いた．部屋は^40m×^40mの正方形で，

16台のカメラが⁴×⁴の配列で^10mの高さの天井に取りつけ られている．各カメラの視野は半径^5mの円であり，その中心は

camera position on the ceiling

walking person current field of view

door

図^{4: MCMP}問題シミュレータ

. . . planner

controller

iterative refinement of assignment

one cycle of camera control . . .

. . . . . .

initial assignment generation

set of latest assignment candidates

図^5: プランナとコントローラの実行のタイムチャート

カメラの取りつけ位置を中心とする半径^5mの円内を移動でき る．カメラ視野の移動速度の最大値は毎秒^0.5mである．

毎回のシミュレーションでは，⁵⁰人の人物を生成した．各人 物は⁴つのドアのどれかから部屋に入ってくるものとした．初 期，最高，最低の移動速度はそれぞれ毎秒^1.0m，^3.0m，^0.1m とした．各時間ステップごとに，あらかじめ与えられた加速度と 方向変化の分散にしたがって，各人の速度をランダムに変更し た．ドアから一定の距離に近づくとある確率で部屋から出て，し ばらく後に同じドアから入ってくるものとした．

4.2 プランナとコントローラ

このプランニング問題において，生産者は人物のカメラへの 割り当てを生成する⁽プランナと呼ぶ⁾．消費者は与えられた割 り当てを基にカメラの制御を行う⁽コントローラと呼ぶ⁾．プラ ンナは繰り返し的に割り当てを生成し，コントローラの要求が あればその時点での割り当てを返す．すべてのコントローラは¹ 秒のサイクルタイムで動作するとする．タイムチャートは図⁵の ようになる．

4.3 割り当て問題の繰り返し改善としての定式化 人物 ^{pi(i=1;:::;P)} とカメラ^{cj(j =1;:::;C)}に対し，

割り当て^Aを次のように定義する^:

A:pi ! cj (j=0;:::;C)

ここで^c0 は人物が現在どのカメラからも追跡されておらず，割 り当ての対象でないことを示す．プランナの目的は最適な割り当 てを行うことである．

4.3.1 初期割り当て プランナは毎回のプランニングを開始

する前に，現在追跡中の人物の近未来での⁽現在は¹秒後⁾の位 置を予測し，それを基に初期割り当てを計算する．初期割り当て では，各カメラについて追跡可能な人物をすべて割り当てる．こ の時点では，一人の人物が複数のカメラに割り当てられているこ ともある．この初期割り当てから始めて，徐々によい割り当てを 求める．

4.3.2 割り当ての評価 割り当ては次の二つの点から評価す

る．一つは追跡される人物の数である．もう一つはカメラ群の注 視点がどの程度散らばっているかであり，一般にカメラ群の注視 点が狭い範囲に集中していると良くないであろう，という知識に 基づく．注視点の分散の程度^dod は次式の，各カメラの注視点 から最も近い他のカメラの注視点までの距離の分散で計算する．

dod = E

2

(mindist

i

0mindist) 2

3

;

mindisti = min

j6=i dist(p

i

;p

j )

ここで，^E[1] は期待値，^pi はこの割り当てに対して計算され る ⁱ番目のカメラの注視点を^{32, dist(1;1)} は²点間の距離を，

mindistは最小距離の平均を，それぞれ表す．^dodは小さいほ

32 注視点の計算は後で述べる．

camera A camera B

camera C

1 2

3 4

5 6

7

図^6: 状況の例

1 2 3 4 5 6 7

A B C 1 2 3 4 5 6 7 A B C

1 2 3 4 5 6 7

A B C 1 2 3 4 5 6 7

A B C 1 2 3 4 5 6 7

A B C

図^7:改善処理の例

どよい．初期位置ではカメラの注視点は取りつけ位置の真下にあ り，^dodは⁰である．^{ni,dodi,nj,dodj}をそれぞれ，割り当 て^Aiと^Ajにおける追跡人物数と注視点分散度とすると，

1. ni>nj, or

2. n

i

=n

j

anddod

i

>dod

j .

であれば，割り当て^Ai は割り当て^Ajより良いとみなす．

4.3.3 割り当てからの注視点の決定 ある割り当てに対し，

各カメラの注視点を以下のように決定する．決められた注視点は

dodの計算およびプランナの最終結果の生成に用いられる．

割り当てられた人物のないカメラは，最大速度で初期位置に 戻るように注視点を制御する．また，他のカメラと共有している 人物がないカメラについては，できるだけ多くの人数が視野には いるような注視点の領域の重心を選ぶ．

他のカメラと人物を共有するカメラについては，少なくとも

1人の人物をグループ内の他のカメラと共有するように，全体を グループ分けし，以下のような一時的な割り当てを行う．まずグ ループ内のカメラを追跡可能人数の降順で並べ，最初のものから 順番に割り当てを決定していく．あるカメラに割り当てられた人 物は，後ろのカメラの候補からはずす．この処理をグループ内の すべてのカメラについて繰り返す．例えば，図6の例では，人物

1〜⁴をカメラ^Aに，⁵，⁶を^B に，⁷を^Cに割り当てる．

その後，共有していないカメラと同様に，注視点を決定する．

4.3.4 繰り返し改善処理 割り当て候補は評価の降順に並べ

ておく．各繰り返しステップでは，現在一番よい候補を選んで改 善する．一回の改善処理では，複数のカメラに割り当てられてい る人物を一人ずつ選び，その人物を各カメラにそれぞれ割り当て ることにより，候補を生成する．例えば，図⁶に示す状況では，

現在の割り当ては左側のものであり，共有されている人物は 4 と 6 であるので，それらをどこに割り当てるかで，右側に示す

4つの新たな割り当て候補が生成される．図中の点線は削除され た割り当てを示す．新たな候補は生成の際に上述の注視点の計算 を同時に行い，その評価に基づきリストの適当な場所に挿入され る．リストの大きさを一定以下に保つために，ある候補の追跡可 能人数が現在最善の候補より小さいとき，その候補を削除する．

4.3.5 繰り返しの終了条件と最終割り当ての生成 次の²つ

の終了条件を用いる．⁽¹⁾十分よい割り当てが得られた場合^: 現 在最善の候補^A3と次善の候補^A33 について， 中心点の分散度

person tracked exclusively by the camera person shared with other cameras

current focus of attention

gex gall

FOV of the camera

gex

gall g

c

c

図^8: 一貫性基準と動作選択

について，^dodA3=dodA33 がしきい値⁽現在は^0:99)より大き きければ，繰り返しを終了する．⁽²⁾繰り返し改善の処理が一定 量を越えた場合^: 生成された候補数が一定数⁽現在は⁶⁰⁾を越え た場合，終了する．繰り返しが終了したら，そのときの最善候補 の割り当てを，最終割り当て結果としてコントローラに送る．

4.4 一貫性基準と動作の選択

コントローラの一貫性のある動作⁽ここでは注視点の移動⁾と は，プランナがどのような最終割り当てを生成しても，大きな損 失がないものである⁽図³参照⁾．ある割り当て候補について，一 つのカメラに対する割り当てられる人物の集合は，その候補の改 善によって単調減少する．したがって，現在残っている割り当て 候補すべてを調べて，各カメラごとに最終的に割り当てられる可 能性のある人物を数え上げ，それらすべてに対して一貫性のある 行動を選択すればよい．

他のカメラと共有している人物がないカメラでは，その行動 を独立に決めることができる．そこで，それらの人物がすべて追 跡できる注視点の集合への移動が一貫性のある行動集合となり，

その重心位置を最適なものとして選ぶ．

他のカメラと共有する人物があるカメラの場合，一貫性のあ る行動は次のように計算する⁽図⁸参照^).まず，次の²つの位置 を計算する．^gex はこのカメラに排他的に割り当てられた人物 の予測位置で作られる凸包の中心である．^gall はすべての割り 当てられた人物の予測位置で作られる凸包の中心である．ここ で，一貫性のある行動は現在の注視点位置 ^c とこれら²つの点 のなす三角形の内部にあるというヒューリスティックを用いる．

一貫性のある行動から最適なものを選ぶ際に，次の2つのパ ラメータを用いる． は排他的に割り当てられた人物群と他の 人物群とをそれぞれどの程度重要視するか，という重みである．

この重みを用いて，まず分割点^{g = g}ex

+(10)g

all を計 算し，次の注視点⁽行動⁾は現在位置 ^c と ^g を結ぶ線上にある とする．パラメータ は注視点移動の速度を制御する．すなわ ち，最大速度に を掛けたものを可能な最大速度とする．を 大きくすると注視点移動速度が大きくなるので， は一貫性基 準の，ある意味の^\緩さ^"を表すものになる．シミュレーション ではは^0:8に固定した^. またはその値を変えることにより 一貫性基準の^\緩さ^"と全体の追跡性能との関係を調べる．

4.5 シミュレーション結果

5組のデータセットについてシミュレーションを行った．一つ のデータセットは50人の1000ステップ分の移動データから成 る．追跡性能の評価基準として，全ステップでの追跡成功割合を 用いる．

まず提案する手法を次の³種の手法と比較した．^(1)idealは 計算コストが無視できるとしたもの，すなわち最大可能数の割り

0.94

0.90

0.80

0.72 1 2 3 4 5

tracking ratio

problem ID ideal

parallel

sequential

reactive

図^9: 比較結果

1 2 3 4 5

0.88

0.84

0.80

tracking ratio

problem ID β=0.9

β=0.7 β=0.5

β=0.3 β=0.1

図^10: の効果

当て候補が各回のプランナのサイクルで必ず調べることができる としたものである．これをシステムの性能の上界として用いる．

(2)reactiveは各カメラが自分の持っている情報だけを基に独立

に制御するものである．この場合カメラ間の調整は一切ないの で，同じ人物を複数のカメラが追跡することがあり得る．これを 下界として用いる．(3)sequentialはプランナが中間結果を生成 せず，最終結果が出てからコントローラに渡すもの，すなわちプ ランナとコントローラが逐次実行されるものである．ここでは一 つの割り当て候補を生成するのに¹⁼²⁰秒かかるとしたので，最 大数⁽⁶⁰⁾の候補を生成したときの最大の遅延は³秒である．図

9に示す比較結果から提案手法が有効であることが分かる．

次に，一貫性基準の^\緩さ^"パラメータと性能の関係を調べ た． を ^{0:1 (}一番厳しい⁾，^0:3，^0:5，^0:7，^{0:9 (}一番緩い⁾ の各値に設定し，性能の変化を調べた結果が図¹⁰である．図よ り厳しすぎる基準も緩すぎる基準もよくないことがわかる．この 問題の場合には ^=0:5 が一番良さそうだが，パラメータ選択 の一般論の検討は今後の課題である．

5.

おわりに

動的環境で動作するロボットシステムにおいてプランニング と行動を並列化することにより，高い実行効率と環境変化に対す る反応性をともに実現する手法について述べた．複数カメラ複数 人物追跡問題に適用し，その効果を確認した．また，プランニン グと一貫性のある行動を選択する基準の厳しさと効率との関係を 実験的に調べた．

今後は提案する手法を実際の複数カメラ追跡システムへ適用 することを考えている．また，複数の並列実行可能な機能要素か らなるシステムを制御するための並列スケジューリングの一般理 論の構築も今後の課題である．

参考文献

[Bo ddy89] Bo ddy,M.andDean, T.: SolvingTime-Dep endent

PlanningProblems, inProceedingsof IJCAI-89,pp.979{

984(1989).

[Bonasso97] Bonasso,R.,Firby,R.,Gat,E.,Kortenkamp,D.,

Miller, D.,and Slack,M.: Exp eriences withan Architec-

tureforIntelligent,ReactiveAgents,J.ofExperimentaland

TheoreticalArticialIntelligence,Vol.9,No.2(1997).

[Korf90] Korf,R.: Real-TimeHeuristicSearch,ArticialIntel-

ligence,Vol.42,pp.189{211(1990).

[三浦^00] 三浦^, 白井：プラニングと行動の一貫性に基づく移動ロボッ トのプラニングと行動の並列スケジューリング^, 人工知能学会誌^,

Vol.15,No.6,pp.1089{1096(2000).

[Zweben94] Zweben,M.andFox,M.eds.: IntelligentSchedul-

ing,MorganKaufmann(1994).