追跡と逃避

追跡回避問題（その派生形は警官と強盗問題やグラフ探索問題とも呼ばれる）は、あるグループが環境内で別のグループのメンバーを追跡するという、数学とコンピュータサイエンスにおける一連の問題である。この種の問題に関する初期の研究では、環境が幾何学的にモデル化されていた。 ^[1] 1976年、トーレンス・パーソンズは、動きがグラフによって制約される定式化を導入した。^[2]幾何学的定式化は連続追跡回避問題、グラフ定式化は離散追跡回避問題（グラフ探索問題とも呼ばれる）と呼ばれることがある。現在の研究は、通常、これら2つの定式化のいずれかに限定されている。

追跡-回避問題の離散的定式化では、環境はグラフとしてモデル化されます。

追跡と回避には無数のバリエーションが考えられますが、多くの要素が共通する傾向があります。典型的で基本的な例は次のとおりです (警官と強盗のゲーム)。追跡者と回避者はグラフのノードを占めます。両者は交互にターンを取り、各メンバーは、その場に留まるか、エッジに沿って隣接するノードに移動することになります。追跡者が回避者と同じノードを占めている場合、回避者は捕らえられ、グラフから削除されます。通常提起される質問は、すべての回避者を最終的に捕らえるために何人の追跡者が必要かということです。追跡者が 1 人だけで十分な場合、グラフは警官勝利グラフと呼ばれます。この場合、1 人の回避者は常に、グラフのノードの数nに線形の時間で捕らえることができます。k人の追跡者でr 人の回避者を捕らえるのにもr nのオーダーで時間がかかりますが、追跡者が 2 人以上の場合の正確な境界はまだ不明です。

多くの場合、移動ルールは、回避者の速度を変更することによって変更されます。この速度は、回避者が 1 ターンで移動できるエッジの最大数です。上記の例では、回避者の速度は 1 です。もう一方の極端な概念は、無限速度です。これは、追跡者が占有しているノードを含まないパスが元の位置と最終位置の間にある限り、回避者がグラフ内の任意のノードに移動できるようにします。同様に、いくつかのバリエーションでは、追跡者に「ヘリコプター」を装備させ、追跡者がターン中に任意の頂点に移動できるようにします。

他のバリエーションでは、追跡者と回避者が常にノードを占有しなければならないという制限を無視し、エッジ沿いのどこかに配置される可能性を考慮します。これらのバリエーションは、スイープ問題と呼ばれることが多く、以前のバリエーションは検索問題のカテゴリに分類されます。

いくつかの変種は、重要なグラフパラメータと同等です。具体的には、グラフGで無限の速度を持つ単一の回避者を捕獲するために必要な追跡者の数を見つけること（追跡者と回避者が順番に移動する制約がなく、同時に移動する場合）は、 Gのツリー幅を見つけることと同等であり、回避者の勝利戦略は、Gの避難所の観点から説明できます。この回避者が追跡者から見えない場合、問題はパス幅または頂点の間隔を見つけることと同等です。^[3] グラフGで単一の見えない回避者を 1 ターン（つまり、追跡者が最初の配置から 1 回移動する）で捕獲するために必要な追跡者の数を見つけることは、追跡者が最初に好きな場所に配置できると仮定して、 Gの最小支配集合のサイズを見つけることと同等です（この後の仮定は、追跡者と回避者が順番に移動すると見なされる場合に当てはまります）。

ボードゲーム「スコットランドヤード」は追跡・逃亡問題のバリエーションです。

いくつかの追跡-回避変種の複雑さ、すなわち、与えられたグラフをクリアするのに何人の追跡者が必要か、また、与えられた数の追跡者がグラフ上でどのように移動すれば、移動距離の合計が最小になるか、またはタスク完了時間が最小になるかは、Nimrod Megiddo、SL Hakimi、Michael R. Garey、David S. Johnson、およびChristos H. Papadimitriou（J. ACM 1988）、およびR. Borie、C. Tovey、S. Koenigによって研究されています。^[4]

マルチプレイヤー追跡・回避ゲームの解決も注目を集めています。R Vidal ら、Chung と Furukawa [1]、Hespanha ら、およびその中の参考文献を参照してください。Marcos AM Vieira と Ramesh Govindan と Gaurav S. Sukhatme は、すべてのプレイヤーが完全な知識に基づいて最適な決定を下す場合に、追跡者がすべての回避者を捕獲するための最小完了時間戦略を計算するアルゴリズムを提供しました。このアルゴリズムは、回避者が追跡者よりも大幅に高速である場合にも適用できます。残念ながら、これらのアルゴリズムは少数のロボットを超えて拡張できません。この問題を克服するために、Marcos AM Vieira と Ramesh Govindan と Gaurav S. Sukhatme は、ゲームを複数のマルチ追跡者シングル回避者ゲームに分解することにより、追跡者が回避者を捕獲する分割アルゴリズムを設計および実装しました。

追跡-回避ゲームの連続的な定式化では、環境は幾何学的にモデル化され、通常はユークリッド平面または別の多様体の形をとります。ゲームのバリエーションでは、速度や加速の範囲を制限するなど、プレイヤーに操作上の制約を課す場合があります。障害物を使用することもできます。

ライオンが人間を同じ速さで追いかけている場合、人間がライオンから常に直線上を移動することで、平面または球面上で逃げることができることは明らかです。両者が円盤内に閉じ込められている場合、ライオンが人間を捕まえる可能性が高いと思われます。ベシコビッチは1952年に、人間にはどんな戦略に対しても捕獲を無期限に回避する戦略があることを証明しました。^[5]

追跡回避問題の最初の応用例の一つは、ランド研究所のルーファス・アイザックスが考案したミサイル誘導システムであった。^[1]

• 天使の問題
• 追跡と逃走
• 殺人運転手問題
• プリンセスとモンスターのゲーム
• ゲームを検索
• 追跡曲線

• アイザックス、R. (1965)。『微分ゲーム：戦争と追跡、制御と最適化への応用に関する数学理論』ニューヨーク：ジョン・ワイリー・アンド・サンズ。OCLC 489835778  。
• Parsons, TD (1976)。「グラフにおける追跡と回避」。グラフの理論と応用。Springer-Verlag。pp. 426–441。
• Borie, R.; Tovey, C.; Koenig, S. (2009) 「追跡-回避問題のためのアルゴリズムと複雑性の結果」。国際人工知能合同会議 (IJCAI) の議事録。2010 年 3 月 11 日閲覧。
• Ellis, J.; Sudborough, I.; Turner, J. (1994). 「グラフの頂点間隔と探索数」.情報と計算. 113 (1): 50–79. doi : 10.1006/inco.1994.1064 .
• Fomin, FV; Thilikos, D. (2008). 「保証されたグラフ検索に関する注釈付き参考文献」.理論計算機科学. 399 (3): 236–245. doi : 10.1016/j.tcs.2008.02.040 .
• Kirousis, M.; Papadimitriou, C. (1986). 「検索とペブリング」理論計算機科学42 ( 2): 205–218. doi : 10.1016/0304-3975(86)90146-5 .
• Nowakowski, R.; Winkler, P. (1983). 「グラフにおける頂点間の追跡」.離散数学. 43 (2–3): 235–239​​. doi : 10.1016/0012-365X(83)90160-7 .
• Petrosjan, Leon (1993). 「微分追跡ゲーム (最適化シリーズ、第 2 巻)」. World Scientific Pub Co Inc. 2 .
• Seymour, P. ; Thomas, R. (1993). 「グラフ検索とツリー幅の最小最大定理」. Journal of Combinatorial Theory, Series B. 58 ( 1): 22–33. doi : 10.1006/jctb.1993.1027 .
• Vidal; et al. (2002). 「確率的追跡-回避ゲーム: 理論、実装、および実験的評価」(PDF) . IEEE Transactions on Robotics and Automation . 18 (5): 662–669. doi :10.1109/TRA.2002.804040.
• Marcos AM Vieira、Ramesh Govindan、Gaurav S. Sukhatme。「ネットワークロボットによるスケーラブルで実用的な追跡回避」。Journal of Intelligent Service Robotics：[2]。
• Chung and Furukawa (2008). 「自律追跡者の時間最適制御のための到達可能性ベースの戦略」.エンジニアリング最適化. 40 (1): 67–93. Bibcode :2008EnOp...40...67C. doi :10.1080/03052150701593133. S2CID  120015118.
• Hespanha 他 (1999)。「マルチエージェント確率的追跡-回避ゲーム」。第 38 回 IEEE 意思決定および制御会議の議事録。pp. 2432–2437。