大地震や津波などの災害が発生した場合，人命救助や被害状況の情報入手を最優先に行わなければならない． 阪神・淡路大震災のような大規模な災害が起きた場合には，広範囲における被害地域の情報収集と人命救助，その他のレスキュー活動のために大勢の人員を配置する必要がある． しかし負傷者が続出する災害現場において，大勢の人員を確保することは難しい．そこで，災害時の情報収集や人命救助等の活動において複数のオートモービルを用いることを考える．
　災害時のレスキューは，人命救助を目的としたレスキューや，消火に関連したレスキューなど様々な分野に分けることができる． 阪神大震災のような過去の災害を見ると，災害に伴う建築物倒壊や高速道路の高架橋落下，または地割れによる道路の寸断がいたるところで見られる． このような悪条件の中，救急隊や消防隊といったレスキュー隊は重傷者がいる地点や病院，または火災現場などの目的の地点まで迅速に移動しなければならない． 従って道路の寸断情報はレスキュー活動において非常に重要な情報である． そこで本研究では，複数のオートビークルを用いて道路の寸断状況を素早く把握することを目的とした問題について考える．

　あるエリアで道路の寸断情報を得るためには，全ての道を通りエリア内の道が寸断されているか判断する必要がある． 複数のビークルを用いて，ある区切られたエリアを網羅しビークルが通れないような障害物を探知する問題では，様々な研究が行われている．
　文献[1]では，複数の同じビークルを用いて，あるエリア内を全て探索するときのアルゴリズムが提案されている． なおこのエリアには多数の壁状の障害物が置かれていると仮定されている． この文献では，ビークルはお互いに一定の距離を保ちながら小さくセル化したマップを全て通ることを目的とし，またランダムミーティングポイントという点を設定することによって，通常時より早く探索できるアルゴリズムが提案されている．
　文献[2]では，複数の犬型ロボット"アイボ"と小型飛行船をオペレータが直接操作し障害物を探索するレスキューロボットチームについて報告されている． ここでは全てのオペレーターが見ることができる仮想地図（Virtual Map）を用いて，各ロボットに取り付けられた小型カメラで発見された道や障害物を， 発見と同時に仮想地図にその情報を与えることによって， 全てのオペレーターが探索エリアの実際と同様のマップを見ることができるようなシステムが提案されている．
　一方，最適化の分野ではエリア内の全ての道を通ることを目的とした，中国人郵便問題（Chinese Postman Problem: CPP）と呼ばれる組み合わせ最適化問題に関する研究が盛んに行われている[3]． CPPとは，道（エッジ）と道の分岐点（ノード）から成り立つグラフが与えられたときに，全てのエッジを1回以上通るような最適な経路を考える問題である． 一般に，CPPではあるコストを考え，これを最小（最大）にするような最適経路を導くことを目的とする．代表的なコストの例としては，経路の総距離などが挙げられる． CPPは問題設定やコストによって様々な応用問題が存在する． 一般に，CPPの最適解を得るには膨大な計算量が伴い，近年ではCPPを短い時間で解くアルゴリズムの研究が盛んに行われている． 文献[4]では，一方向しか進めないエッジを含むCPPの最適解を近似的に求めるアルゴリズムが提案されており，また[5]では， CPPにおいてエッジ毎に仕事が設定されており，この仕事を完遂するまでの時間の上限と下限のみ指定されているような場合の解法を導いている． その他のCPPの応用問題として，複数のエージェントを用いて，全てのエージェントの中で一番長い経路の距離を最小にするmin-max k-person CPPという問題も存在する． 文献[6]ではこのmin-max k-person CPPの最適解を得るためのアルゴリズムを提案している． このように，CPPの分野では，最適解や近似解を効率よく導くための様々な手法やアルゴリズムが提案されているが， 現在提案されている手法はどれも，グラフが大きくなるにつれてその計算量が膨大になり，最適解を得るのが難しい．

　多くのフォーメーション制御の研究では，同じ特性を持つビークル間のフォーメーション制御を対象としている. 一方，[7]では異なる特性をもつエージェントの適応協調制御設計の一つの手法が提案されている． この手法はロボットがチームでサッカーの試合をする“ロボカップサッカー”に実際に利用されている． 例えば，シュートやボールをキックする能力に長けたロボットやディフェンスの能力に長けたロボットなど， 多種のロボットが存在する場合にそれらが協調しつつ，かつ個々の能力を最大限に引き出せるような制御則を提案している．
　ロボットを用いた災害時のレスキューに関する研究は，一方ではヘビ型ロボットなどの災害ロボットの研究が現在盛んに行われている． それに対して，レスキューを目的とした複数のビークル間の協調制御に関する研究は現在ではまだ数少ない．

　本研究では，複数のオートビークルを用いて災害時の道路の寸断状況を把握することを目指す. 研究を行う最初の段階として，地上を走るn台のビークルを用いて， グラフ（道路網）の全てのエッジ（道）を通り道路の被害状況を素早く把握する という問題を考える．このときの各ビークルの動作のアルゴリズムを提案・設計する．
　さらに，本研究ではヘリコプター等のオートビークルを取り入れ，異なる特性間の協調制御を行うことによって， より迅速な道路状況把握を目指す.

・全てのビークルの位置情報，経路情報は共有可能とする．
・被害のない，元のグラフは始めに与えられているとする．
・全てのビークルは，マップの中心付近に位置するノードから出発する．
・ビークルの速度は一定であるとする．
　このような問題設定下において，グラフの全ての道を１回以上通り， さらにこの作業を達成するまでの時間を出来るだけ短くすることを目的とする．
　上記の問題は, [6]のCPPとして解くことは考えられない. スタート時には被害箇所がわからず，最適な経路を算出することは出来ないからである． そこで本研究ではモデル予測制御の概念を取り入れ， ビークルがノード（交差点）に到達した時に，有限個のノードを通る経路を暫定的に決定し， 新たにノードに到達する毎にこの経路を更新していく手法を提案する． ビークルの周りの限られた範囲で経路の最適化を随時行うことで，被害箇所が発見された時の対処を可能にし，更に計算時間の短縮も図る． またこの問題では，各ビークルは近くにある電波塔やヘリコプターと通信を行い，そこから各ビークルに経路の指示を出すという集中制御を想定する．

　全てのエッジを通り，被害状況を素早く把握するために2つの評価関数を考え，それぞれ重みをかけた和を利用して経路を決定する． 第一に，どのビークルも通っていないエッジを優先的に通るような評価をする． 第二に，各ビークルに目標点を与え，その目標点との直線距離を評価する． 目標点をマップの端点などに適切に置くことによって，各ビークルが目標点付近を担当するような経路を選ぶようにする． この2つの評価関数を与えることにより，この問題の精度のよい解を短い計算時間で得ることを実現する．

　上記の評価関数の2つ目の要素において，最適な目標点を設置することによって最適な担当エリアを規定することを考える．
　CPPのような最適経路問題においては，マップが大きい場合にエリアを区域化し，各ビークルに規定するといった 区域化問題(Districting Problem)の研究も盛んに行われている[8,9,10]． 　
　本研究では，ネットワークボロノイ図[11,12]を用いた最適な区域化を行い，目標点を設置することを試みる． 　

　本論文で提案したモデル予測制御的手法による解法を用いて数値実験を行った． 用いたグラフは東京都目黒区にある実際の道路網を引用したものであり、マップは横幅1.5km，縦幅2.75kmの長方形である． また，仮想的に３ヶ所の寸断道路を導入した． ビークルの速度は30km/hとした．
このグラフを用いて，ビークル数を変更したときの総探索時間の比較を行った． 数値実験の結果を図1に示す． 横軸はビークル数nを表し，縦軸は総探索時間T_fを表す. また，ビークル数が3台の時と，4台の時の道路探索の様子を図2と図3にそれぞれ示す.
この結果より，ビークル数が増えるにつれて探索時間は減少することがわかる． また，ビークル数が2と3のときを比べると，探索時間は28% 近く減少しているが， ビークル数が4と5のときを比べると探索時間は13% 程度しか減少していない． これより，ビークル数が増大するにつれて探索時間の減少の割合は小さくなることがわかる．

　本研究では，都市震災時の道路の寸断状況把握問題をモデル予測制御的に解く解法を導いた． マルチビークルの集中制御を想定し，総探索時間をなるべく小さくする評価関数を提案した． また，ネットワークボロノイ図を用いたエリア分割により，適切な担当エリアの規定を提案した． さらに，数値実験を通してこれらの手法の有効性を示した．
　本研究では地上を走るビークルのみを扱ったが， 今後はヘリコプターなどの異なる性質のビークルを同時に扱ったレスキューフォーメーションへの発展を目指す．

[1] M. N. Rooker and A. Birk, "Multi-robot exploration under the constraints of wireless networking,'' Control Engineering Practice, vol. 15, pp. 435-445, 2007.
[2] S. Tajada, A. Cristina, P. Goowyne, E. Normand, R. O'Hara, and S. tarapore, "Virtual synergy: A human-robot interface for urban search and rescue,'' AAAI Mobile Robot Competition, pp. 13-19, 2003.
[3] G. N. Frederickson, M. S. Hecht, and C. E. Kim, "Approximation algorithms for some routing problems,'' SIAM J. Comp., vol. 7, pp. 178-193, 1978.
[4] W. L. Pearn and J. B. Chou, "Improved solutions for the Chinese postman problem on mixed networks,'' Comp. Oper. Res., vol. 26, pp. 819-827, 1999.
[5] U. F. Aminua and R. W. Egleseb, "A constraint programming approach to the Chinese postman problem with time windows,'' Comp. Oper. Res., vol. 33, pp. 3423-3431, 2006.
[6] D. Ahr and G. Reinelt, "A tabu search algorithm for the min-max k-Chinese postman problem,'' Comp. Oper. Res., vol. 33, pp. 3403-3422, 2006.
[7] A. Bonarini and M. Restelli, "An architecture for adaptive coordination of heterogeneous agents,'' Workshop su agenti robotic, 2002.
[8] L. Muyldermans, D. Cattrysse, D. V. Oudheusden, and T. Lotan, "Districting for salt spreading operations,'' Eur. J. Oper. Res., vol. 139, pp. 521-532, 2002.
[9] Y. Ouyang, "Design of vehicle routing zones for large-scale distribution systems,'' Trans. Res. Part B, vol. 41, pp. 1079-1093, 2007.
[10] L. C. Galvao, A. G. Novaes, J. E. Souza de Cursi, and J. C. Souza, "A multiplicatively-weighted Voronoi diagram approach to logistics districting,'' Comp. Oper. Res., vol. 33, pp. 93-114, 2006.
[11] M. Erwig, "The graph Voronoi diagram with applications,'' Networks, vol. 36, pp. 156-163, 2000.
[12] S. L. Hakimi, M. Labbe, and E. Schsc.eche, "The Voronoi partition of a network and its implications in location theory,'' INFORMS J. Comp., vol. 4, pp. 412-417, 1992.

Tokyo Institute of Technology
Dynamical Systems Lab
Email: pak[at]cyb.sc.e.titech.ac.jp
2008 / 5 / 10 更新