協調マルチロボットプロジェクト

この分野のキーワード

マルチエージェントシステム, 自律エージェント, 分散アルゴリズム, ロボット

自律ロボット

近年発売され話題になった掃除ロボットをご存知でしょうか． この掃除ロボットは，部屋の大きさを測り，障害物や階段などの段差を避け，部屋の中をくまなく掃除してくれます． しかもバッテリーが少なくなると自分で充電をするため，スタンドへ戻ります．

このような自律的で賢い（ように振る舞う）自律ロボット（自律エージェント）は，今後より一層様々な用途で必要とされて行くと考えられます．

自律ロボットの例としては，警備ロボットや芝刈りロボット，掃除ロボット，ロボカップサッカーのロボット群，災害救援ロボットなどをあげることができます．

領域被覆問題

自律ロボットに行なわせる基本的なタスクとして，領域被覆問題があります．領域被覆問題とは，与えられたフィールド内をくまなく巡回するタスクのことです．

フィールドは内部に障害物が存在したり，傾斜になっていたり，外形が多角形であったりと様々な状況が考えられますが，どのような状況にも対応できるような「自律的な」動作が求められます．

スパニングツリーによる領域被覆

領域被覆のために闇雲に動き回っていては効率がよくありません． 何より，知的であるとは言えないでしょう． 領域の完全被覆のための有効な手段として，スパニングツリーの作成があります．

スパニングツリーをフィールドに適用して作成されたスパニングツリー（図：黒太線）の周囲を辿ると一筆書きができます（図：青線）．
つまり，領域に対してスパニングツリーが作成できれば，すべての領域を被覆するルートが作成できます．

このスパニングツリーによる領域被覆アルゴリズムは，下で述べる３つの性質を満たしているため効果的なアルゴリズムなのですが，現実のタスクに適用する場合にいくつかの問題があります．
大沢研究室では，それらの問題点に対する改善アルゴリズムの提案や実証，実験を行なっています．

協調行動を行なうマルチロボット

１台のロボットによる領域被覆ならば，スパニングツリーを作成する方法で十分です．
しかし，複数のロボットでタスクを遂行するには担当する領域の分割問題が発生します．
また，現実のタスクを考慮すると，バッテリの電力低下による速度の変化，故障などによる稼働台数の変化，性能差による速度差などの課題も考慮する必要があります．

このような課題に対しても，次の３つの基準を満たすような自律ロボットを構成する必要が生じます．

完全性

フィールド内の移動可能領域をすべて被覆すること．

頑健性

ロボットが故障しても，他のロボットが1台以上動作可能ならば，タスクを遂行できること．

最小性

各々のロボットの動作に無駄な行動がないこと．

研究紹介

消費電力を考慮したマルチロボット領域被覆手法の考案

スパニングツリーによる領域被覆は前述の３つの基準を満たしていますが，ロボットの電力消費量を考慮していません．
一般にロボットは加減速やターン時に多くの電力を消費します．そこで，巡回パスの生成時にそれらを減少させることを考慮することは有効的です．
より長い時間ロボットを稼動させることを考えると電力消費量を削減することは効果的です．

スパニングツリーを用いた領域被覆では，１カ所で４回ターンを行なう必要のある場所が存在します．
そのような点は電力消費量の観点から非常に効率の悪い点であると言えます．

そこで，我々の考案したアルゴリズムは，前述の３つの基準のうち最小性を許容することで，電力消費量の観点から効率の良い被覆手法を提案することができます．
１カ所で４回のターンを必要とした点を直進（図：緑色）し，ターンするはずだった点を別の点から被覆するアルゴリズムを考案することで消費電力量を20％から40％程度低減可能であることが確認できました．

日根健晴, 大沢英一
消費電力を考慮したマルチロボット領域被覆手法の考察
合同エージェントワークショップ＆シンポジウム (JAWS2008)講演論文集, 2008