研究背景と既存研究
近年，マイクロプロセッサ，姿勢センサやGPSモジュールの性能向上，低価格化が進み，UAV（Unmanned Aerial Vehicle）やUGV（Unmanned Ground Vehicle)などの自律的な制御が可能なエージェントを安価に構成することが可能となってきている．このような技術的進歩を背景に，複数のエージェントを用いたフォーメーション制御や協調制御などが，理論的研究と現実問題への応用研究の両面から盛んに研究されている[1,2]．
この協調制御で扱われている問題のひとつに被覆制御問題[3]に関する研究がある．被覆制御とは，ある領域に対し複数のエージェントを配置する際に効率のよい配置を実現することを目的とした制御である．この被覆制御の応用例としては，カメラなどのセンサーを搭載したUAVを複数用意し，指定された領域の情報を集めるというような情報収集タスクなどが考えられる．被覆制御問題に対する最も基本的なアプローチの手法は，被覆制御問題を評価関数の最適化問題として定式化し，評価関数最適化問題に対する解法の一種である勾配法を用いてエージェントへの入力を導出し，最適被覆を実現するというものである[3,4]．この基本的なアプローチをベースに，適応制御の手法を応用した研究[5]や，各エージェントが用いることのできる情報に制限を加えた研究[6-8]など多くの問題設定が考えられている．
一方で，可動性を持った複数のエージェントを無線中継器として利用することで，無線通信ネットワークを構築する手法の研究も行われており，この手法をマルチエージェントネットワークの制御と呼ぶこととする．このようなマルチエージェントネットワークは，そのネットワークを構成するエージェントにUAVなどの可動性を持ったエージェントを用いることで，ネットワークインフラの設置にかかるコストを抑えることや，災害地や戦場など任意の場所に素早く無線通信ネットワークを構築することを可能とすると期待されている．文献[9-11]では，無線通信ネットワークの通信速度とUAVの位置の関係に着目し，通信速度を最大化するために，UAVの位置をextremum seeking[12]という制御手法を用いて最適化する手法を提案している．現実問題への応用のための研究として[13]では，ロボットを用いた遠隔手術における通信にUAVを用いた無線通信ネットワークを利用する実証実験が行われている．さらに，理論的側面からのアプローチとして，エージェントをより抽象化し，エージェントによって構成されるネットワークをグラフとして表し，そのグラフの連結性などの性質に着目した研究[14-16]も行われている．
研究目的
本研究では，これらの既存研究を踏まえ，センサネットワーク[17,18]などの空間に分布する情報源に対し，その情報源の分布に応じて情報伝達を中継するエージェントを適切に配置することで情報収集の効率を高めるという研究[19-22]に注目する．このとき，情報源から得られた情報は，エージェントによって構成される無線通信ネットワークを通じて中継されることになるが，エージェント間の通信を無線通信によるものとし，その無線通信が可能な距離に制限を導入すると既存研究におけるマルチエージェントの制御手法をそのまま適用するだけではマルチエージェントネットワークの連結性が失われてしまうという問題が生じてしまう．本研究では，この問題に対し，既存の被覆制御の手法にマルチエージェントネットワークの制御の考え方を導入することでマルチエージェントネットワークの連結性を維持しながら最適なエージェントの配置を導出する手法を提案することを目的とする．
主結果
本節では，本研究で提案するマルチエージェントの制御手法について概説する．
ネットワーク拘束付きDeterministic Annealing
本研究では，解決すべき問題をマルチエージェントネットワークの連結性を維持することを拘束条件とした被覆制御問題として定式化する．そこで，まずネットワーク拘束なしの被覆制御問題に対しては，[23]で提案されているDeterministic Annealingを用いた被覆制御という手法を用いることとする．このDeterministic Annealingを用いた被覆制御を用いることで，[3,4]等で用いられている基本的な被覆制御手法よりも初期配置依存性を抑えた大域的なエージェントの配置を得ることができる．続いてネットワーク拘束に関しては，被覆制御を行う評価関数にバリア関数と呼ばれる関数を導入することで実現する．このバリア関数は，任意のグラフを用いて定義され，グラフに含まれるエッジの両端に属するエージェント間の距離が指定したエージェントの通信可能限界距離に近づくと無限大に発散する性質をもち，エージェント間の距離を通信可能限界距離以下に抑える働きをする．
最適なグラフの選択
ネットワーク拘束を実現するバリア関数は，任意のグラフを用いて定義するが，このグラフをどのように選択するかという問題が生じる．本研究では，このグラフの選択という問題に対して，マルチエージェントネットワークのネットワーク構造を表すR-diskグラフ(エージェントの位置をノード，エージェント間の通信路が存在するノードの組をエッジとして持つグラフ)の全域部分グラフを選択することでマルチエージェントネットワークの連結性を維持できることを示した．また，この全域部分グラフを選ぶ際に，幾何的最小全域木と呼ばれるグラフを選ぶことが，ネットワーク拘束による被覆制御への影響の程度を最小化する意味で最適であることを示した．
数値シミュレーション結果
提案手法を用いて数値シミュレーションを行った結果を示す．図1に，ある情報源の分布と15機のエージェントに対し，提案手法を適用することで得られた配置を示す．背景の濃淡は情報源の分布を表し，ノードはエージェントの配置を，青・緑のエッジはエージェント間の通信路の有無を，青のエッジはネットワーク拘束をかけたエッジを表す．このとき，青のエッジによって構成されるグラフはエージェントの配置から導出される幾何的最小全域木となっている．図1からマルチエージェントネットワークの連結性を維持しながら，情報源を覆っている様子が見て取れる．図2にネットワーク拘束をかけていない被覆制御を用いて得られる結果と提案手法を用いて得られる結果との比較を示す．縦軸は被覆の性能の指標であるひずみ関数値を表し，この値が小さいほど良い被覆をしていることを示す．横軸は本研究で用いたDeterministic Annealingを用いた被覆制御の進展を表す．図2から，最終的に得られる被覆性能は2つの手法間でほとんど差がなく，提案手法がネットワーク拘束をかけることでネットワークの連結性を維持しながら，良い被覆性能を達成している事がわかる．
|
|
| 図1 提案手法で得られる配置 | 図2 ネットワーク拘束の有無による被覆性能の比較 |
今後の課題
今後の課題としては，本研究で用いたDeterministic Annealingという手法が集中制御的手法であるという問題に対して，これをマルチエージェントの制御において望ましいとされる分散制御的手法に変換することが挙げられる．加えて，提案手法の評価において，エージェントの配置の収束速度に関する議論がなされていないという問題がある．この収束速度は，すなわちマルチエージェントが空間に対して展開する際の迅速さを表すため，非常に重要な性能であると考えられる．そのため，この収束速度に関する考察なども今後の課題となる．
References
[1] A. Ryan, M. Zennaro, A. Howell, R. Sengupta, and J. K. Hedrick, ``An overview of emerging results in cooperative UAV control,'' in Proc. IEEE Conf. Dec. Contr., (Paradise Island, Bahamas), pp. 602-607, December 2004.
[2] T. Samad, J. S. Bay, and D. Godbole, ``Network-centric systems for military operations in urban terrain: the role of UAVs,'' Proc. IEEE, vol. 95, no. 1, pp. 92-107, 2007.
[3] J. Cortes, S. Martinez, T. Karatas, and F. Bullo, ``Coverage control for mobile sensing networks,'' IEEE Trans. Rob. Autom., vol. 20, no. 2, pp. 243-255, 2004.
[4] S. Martinez, J. Cortes, and F. Bullo, ``Motion coordination with distributed information,'' IEEE Contr. Sys. Mag., vol. 27, no. 4, pp. 75-88, 2007.
[5] M. Schwager, J.-J. Slotine, and D. Rus, ``Decentralized, adaptive control for coverage with networked robots,'' in Proc. IEEE Int. Conf. Robo. Autom., (Rome, Italy), pp. 3289-3294, April 2007.
[6] A. Howard, M. J. Mataric, and G. S. Sukhatme, ``Mobile sensor network deployment using potential fields: a distributed, scalable solution to the area coverage problem,'' in Proc. Dist. Auton. Rob. Syst., (Fukuoka, Japan), pp. 299-308, June 2002.
[7] J. Cortes, S. Martinez, and F. Bullo, ``Spatially-distributed coverage optimization and control with limited-range interactions,'' ESAIM Contr. Optim. Calc. Variat., vol. 11, no. 4, pp. 691-719, 2005.
[8] K. Laventall and J. Cortes, ``Coverage control by multi-robot networks with limited-range anisotropic sensory,'' Int. J. Contr., vol. 82, no. 6, pp. 1113-1121, 2009.
[9] C. Dixon and E. W. Frew, ``Controlling the mobility of network nodes using decentralized extremum seeking,'' in Proc. IEEE Conf. Dec. Contr., (San Diego, CA), pp. 1291-1296, December 2006.
[10] C. Dixon and E. W. Frew, ``Maintaining optimal communication chains in robotic sensor networks using mobility control,'' in Proc. Int. Conf. Rob. Com. Coor., (Athens, Greece), October 2007.
[11] E. W. Frew, ``Cooperative standoff tracking of uncertain moving targets using active robot networks,'' in Proc. IEEE Int. Conf. Robo. Autom., (Rome, Italy), pp. 3277-3282, April 2007.
[12] M. Kristic and H. H. Wang, ``Stability of extremum seeking feedback for general nonlinear dynamic systems,'' Automatica , vol. 36, no. 4, pp. 595-601, 2000.
[13] M. J. H. Lum, J. Rosen, H. King, D. C. W. Friedman, G. Donlin, G. Sankaranarayanan, B. Harnett, L. Huffman, C. Doarn, T. Broderick, and B. Hannaford, ``Telesurgery via unmanned aerial vehicle with a field deployable surgical robot,'' Stud. Health Technol. Inform., vol. 125, pp. 313-315, 2007.
[14] M. Mesbahi, ``On state-dependent dynamic graphs and their controllability properties,'' IEEE Trans. Autom. Contr., vol. 50, no. 3, pp. 387-392, 2005.
[15] Y. Kim and M. Mesbahi, ``On maximizing the second smallest eigenvalue of a state-dependent graph laplacian,'' IEEE Trans. Autom. Contr., vol. 51, no. 1, pp. 116-120, 2006.
[16] K. Srivastava and M. W. Spong, ``Multi-agent coordination under connectivity constraints,'' in Proc. Amer. Contr. Conf., (Seattle, WA), pp. 2648-2653, June 2008.
[17] I. F. Akyildiz, S. Weilian, Y. Sankarasubramaniam, and E. Cayirci, ``A survey on sensor networks,'' IEEE Comm. Mag., vol. 40, no. 8, pp. 102-114, 2002.
[18] J. Carle and D. Simplot-Ryl, ``Energy-efficient area monitoring for sensor networks,'' IEEE Computer, vol. 37, no. 2, pp. 40-46, 2004.
[19] J. Llorca, M. Kalantari, S. D. Milner, and C. C. Davis, ``A quadratic optimization method for connectivity and coverage control in backbone-based wireless networks,'' Ad Hoc Netorks, vol. 7, no. 3, pp. 614-621, 2009.
[20] K. Xu, X. Hong, and M. Gerla, ``An ad hoc network with mobile backbones,'' in Proc. IEEE Int. Conf. Comm., (New York, NY), April 2002.
[21] S. Perumal, J. S. Baras, C. J. Graff and D. G. Yee, ``Aerial platform placement algorithms to satisfy connectivity, capacity and survivability constraints in wireless ad-hoc networks,'' in Proc. IEEE Mil. Comm. Conf., (San Diego, CA), November 2008.
[22] S. Bandyopadhyay and E. J. Coyle, ``An energy efficient hierachical clustering algorithm for wireless sensor networks,'' in Proc. IEEE Conf. Comp. Comm., (San Francisco, CA), March 2003.
[23] A. Kwok and S. Martinez, ``A distributed deterministic annealing algorithm for limited-range sensor coverage,'' in Proc. Amer. Contr. Conf., (St. Louis, MO), pp. 1448-1453, June 2009.