Multi-Agent Planning with Spatio-Temporal and Topological Constraints using STL-GO

ドローンの一群がただランダムに飛び回るのではなく、単一の超スマートな脳として機能する世界を想像してみてください。これは、マルチエージェント・システム（Multi-Agent Systems）と呼ばれる、コンピュータサイエンスの一分野です。そこでは、多くのロボットが協力して、森林火災の消火や遭難者の捜索といった大きな問題を解決します。ロボット同士が衝突したり、任務を忘れたりしないように、エンジニアは「形式手法（formal methods）」を使用します。これは、ロボットに従わせるための厳格な数学的なルールブックを書くという、少し凝った言い方です。通常、これらのルールブックは、「赤信号では止まれ」や「時速20マイルを超えて走行してはならない」といった単純な交通法規のようなものです。しかし、現実の世界はもっと複雑です。時には、ロボットは「近くに仲間はいるか？ 彼らと通信できるか？ 彼らは火災を見たか？」を知る必要があります。これには、時間や空間だけでなく、ロボット間の接続の形、すなわち「トポロジー（topology）」を理解するルールブックが必要です。これは、一台の車のためのルールリストと、毎秒パートナーを変えるダンス・グループのためのルールブックとの違いのようなものです。

本論文では、彼らの「友情マップ（つながりの図）」が絶えず変化する場合に、ドローンの群れにどのように動きを計画させるかという難しい問題に取り組んでいます。著者らは、STL-GO（Spatio-Temporal Logic with Graph Operators：グラフ演算子を用いた時空間論理）という、新しい非常に強力なルールブック言語を導入しました。従来の言語は時間や空間を扱うことはできましたが、誰が誰と話しているかという複雑で変化するネットワークを扱うことは困難でした。研究者たちは、これらの複雑で変化するルールを取り込み、ロボットの具体的な飛行計画へと変換できる2種類の異なる「翻訳機」（混合整数計画法に基づくものと、充足可能性モジュロ理論に基づくもの）を構築しました。彼らは、ロケーター・ドローンとレスキュアー・ドローンを含む救助ミッションのシミュレーションを用いて、これらの翻訳機の性能をテストしました。その結果、新しい手法は複雑なチームワークを扱うのに十分強力である一方で、計算負荷が高くなることがあり、特定のタスクに応じて一方の手法が他方よりも速く問題を解決できることが示されました。

変わりゆく群れの物語

あなたは、2種類のドローンからなる救助チームの指揮官だと想像してください。それは、ロケーター（偵察機）とレスキュアー（ヒーロー）です。ロケーターは森の中を飛び回り、火災を探します。ロケーターが火災を発見すると、以下の手順でいくつかのことを行う必要があります。

1. 感知（Sense）: 火災が本物であることを確認する。
2. 接続（Connect）: 他のロケーターやレスキュアーに対して、「ここに火災あり！」と叫ぶ（通信する）。
3. 割り当て（Assign）: 助けに行くための特定のレスキュアーを選ぶ。
4. 行動（Act）: レスキュアーは火災の場所へ飛び、生存者を救助し、安全なテントまで運びます。

問題は、「叫ぶ（通信する）」部分が、風やバッテリー残量、そしてドローンがどこを飛んでいるかに依存することです。ロケーターがレスキュアーと通信できることもあれば、できないこともあります。レスキュアーが遠すぎて声が聞こえないこともあります。誰が誰と話せるかというマップは、動的グラフ（dynamic graph）、つまり毎秒変化する接続のウェブなのです。

著者らが解決した問題は、**「接続関係が常に変化している状況でも、ルールに従うための完璧な飛行経路を計算するコンピュータ・プログラムを、どのように書けばよいか？」**ということです。

魔法のルールブック：STL-GO

著者らは、STL-GOと呼ばれる特別な言語を使用しました。この言語は、次のような指示を書くための方法だと考えてください。

• 「すべての火災は、5分以内にロケーターによって発見されなければならない」
• 「発見された後、ロケーターは2分以内に、通信可能な少なくとも1機のレスキュアーを見つけなければならない」
• 「その後、レスキュアーは火災の場所へ飛び、生存者をテントまで運ばなければならない」

STL-GOにおける「グラフ演算子（Graph Operators）」こそが、秘伝のソースです。これによって、ルールブックは「現在の接続マップを確認せよ。ロケーターからレスキュアーへの経路は存在するか？」といった指示を出すことができます。これは、単に「座標X, Yへ行け」と言うよりもはるかに困難です。コンピュータに、チームのネットワークの形状を常に再評価させる必要があるからです。

2つの翻訳機：MIPとSMT

ルールを書くことと、実際にロボットを飛ばすことは別物です。コンピュータは、これらの高度なルールを、ステップバイステップの移動リスト（例：「前方に5メートル進み、左に曲がる」）へと翻訳する必要があります。本論文では、この仕事を行うための2つの異なる「翻訳機」を提示しています。

1. MIP翻訳機（混合整数計画法）: これは、非常に厳格で細部までこだわる会計士のようなものです。単に「何らかのプラン」を見つけるのではなく、「最善の」可能なプランを見つけ出そうとします。「最もバッテリー消費が少ない経路を見つけろ」と命じることもできます。これはエネルギーを節約したい場合には最適ですが、ジャグリングをしながら巨大な数独を解こうとする時のように、動作が重く、時間がかかることがあります。
2. SMT翻訳機（充足可能性モジュロ理論）: これは、電光石火の探偵のようなものです。彼は「最善の」プランを見つけることには興味がなく、ただ「機能する」プランを見つけたいだけです。彼は「これらすべてのルールを満たすことは可能か？」と問いかけます。もし可能であれば、解決策を提示します。通常、会計士よりもはるかに高速ですが、燃料効率などの最適化を行うことはできません。

救助シミュレーション

アイデアをテストするために、著者らは森林火災のシミュレーションを作成しました。彼らはロケーターとレスキュアーがいるシナリオを設定し、以下の条件でのミッション計画をコンピュータに求めました。

• 火災は異なる場所で発生する可能性がある。
• ドローンは、誰が通信可能かに基づいて、通信し、タスクを割り当てなければならない。
• これらすべては、特定の制限時間内に完了しなければならない。

彼らは、異なるチーム規模（5機のロケーターから9機のロケーターまで）と、異なる複雑さのレベル（感知のみ、通信の追加、タスク割り当ての追加）でシミュレーションを実行しました。

判明したこと：

• SMT翻訳機はスピードスターでした。 ほとんどすべてのテストにおいて、SMT翻訳機はMIP翻訳機よりもはるかに速く、有効な飛行計画を見つけ出しました。例えば、9機のロケーターと3機のレスキュアーがすべての種類の接続を扱うシナリオでは、SMT翻訳機は約16.5秒で問題を解決しましたが、MIP翻訳機は1,480秒以上かかり、（絶対的な最善策ではなく、単に「良い」プランを見つけただけで）まだ計算を続けていました。
• MIP翻訳機はオプティマイザー（最適化担当）でした。 著者らがMIP翻訳機に対し、最も直接的で燃料効率の良い経路を見つけるよう求めたとき、それはドローンの動きを形成する上で優れた仕事を見せましたが、SMT翻訳機は単に「機能する任意の経路」を与えるだけでした。
• 複雑さが重要になります。 ルール（特定の通信リンクやタスク割り当ての要求など）を追加するにつれて、問題は両者にとって難しくなりました。しかし、MIP翻訳機の方がより苦戦し、チームが大きくなるにつれて変数と制約の数が爆発的に増加しました。

なぜこれが重要なのか

この論文は、ロボットの群れに関するあらゆる問題を解決したと主張しているわけではありません。著者らは、自分たちの結果が、環境が完全に予測可能である（突然の突風や無線故障がない）シミュレーションに基づいていることを慎重に注記しています。現実の世界は混沌としており、これらの計画は即座に調整される必要があるかもしれません。

しかし、彼らは、ロボットのチームに対して複雑で変化するルールを書き、コンピュータにそれらをどのように飛行させるかを計算させることが可能であることを証明しました。彼らは、「会計士（MIP）」が微調整には適している一方で、「探偵（SMT）」の方が、ミッションがそもそも実行可能かどうかを素早く判断するためのより良い選択肢になることが多いことを示しました。これは、現実の災害において、人間による連携された救助隊のように、状況に応じてチームワークを即座に適応させることができる、協調的なロボットの群れを実現するための重要な一歩です。