Loading article…
ゲーム理論では、殺人運転手問題は数学的な追跡問題であり、歩行者はゆっくりしか動けないが非常に機動性に優れているという架空のランナーと、ランナーよりはるかに速いが機動性がはるかに劣る自動車の運転手がランナーを轢こうとしているという問題である。ランナーと運転手はどちらも疲れないものとする。解決すべき問題は、どのような状況で、どのような戦略で、自動車の運転手が歩行者を常に捕まえられるか、または歩行者が自動車からいつまでも逃れられるかである。
この問題は、ミサイル防衛やその他の軍事目標の非機密代理としてよく使用され、科学者が安全保障上の影響を受けることなくこの問題に関する論文を発表することを可能にしている。[1]
この問題は、1951年にRANDコーポレーションの報告書[2]と著書「微分ゲーム」の中でルーファス・アイザックスによって提案されました。[3]
殺人運転手問題は、連続時間で連続状態空間でプレイされる微分ゲームの典型的な例です。変分法とレベルセット法は、問題の解決法を調査するための数学的枠組みとして使用できます。この問題は娯楽問題として表現されていますが、実際の多くのアプリケーションで使用される数学の重要なモデル問題です。
この問題の離散バージョンは、マーティン・ガードナー（著書『数学カーニバル』第 16 章）によって説明されており、速度 2 のパトカーが速度 1 の犯罪者を長方形のグリッド上で追跡します。この場合、パトカーは左折や U ターンをすることはできませんが、犯罪者は左折や U ターンをすることはできません。
参照
- 変分法
- レベルセット法
- アポロニウスの追跡問題
- コンウェイの天使問題。強力で機動力のある敵と、非常に機動力があるがそれほど強力ではない敵を対決させる数学的なゲームである。
- プリンセスとモンスターのゲーム
参考文献
- ^ Becker, AT, & Garcia, J. (2018 年 1 月 22 日). Wolfram Demonstrations Project . 殺人運転手問題. https://demonstrations.wolfram.com/TheHomicidalChauffeurProblem/
- ^ R. アイザックス、ゲーム・オブ・パースート、ランド社 (1951)
- ^ R. アイザックス、「微分ゲーム：戦争と追跡、制御と最適化への応用に関する数学理論」、ジョン・ワイリー・アンド・サンズ、ニューヨーク (1965)、349-350 ページ。
外部リンク
- 殺人運転手問題の歴史、ピエール・ベルンハルト教授の60周年記念講演会での発表。
- 殺人運転手ゲーム問題の事例分析研究
- 殺人運転手ゲーム。価値関数のレベルセットの計算
- 殺人運転手問題