ベンチマーク

手法を比べるには、同じ問題で測る必要があります。MAPF の研究では Moving AI Lab が配布するマップとシナリオが事実上の標準になっています。

大規模ベンチマークは同梱していません

配布条件とリポジトリのサイズを考え、Moving AI のマップ・シナリオはここに含めていません。配布元から取得して、シミュレータへ読み込んでください。

読み込める形式

形式	内容	状態
`.map`	Moving AI のマップ。`.` `G` `S` が通行可	パーサ実装済み
`.scen`	Moving AI のシナリオ。開始・目標の対と最適経路長	パーサ実装済み
独自 JSON	本サイトのシナリオ形式。マップ・エージェント・タスク・ルール・seed を含む	シミュレータで import / export 可

.map / .scen のパーサは実装済みですが、シミュレータ UI からのファイル読み込みは JSON のみ対応です。 Moving AI ファイルの UI 読み込みは今後の課題です。

独自 JSON の形式

{
  "formatVersion": 1,
  "id": "example",
  "name": "例",
  "kind": "one-shot-mapf",
  "width": 4, "height": 1,
  "map": ["...."],
  "agents": [
    { "id": "a1", "start": [0, 0], "goal": [3, 0] },
    { "id": "a2", "start": [3, 0], "goal": [0, 0] }
  ],
  "rules": {
    "goalBehavior": "stay",
    "forbidEdgeSwap": true,
    "forbidFollowing": false,
    "allowDiagonal": false
  },
  "seed": 1
}

map は 1 行 1 文字列で、. が通行可、それ以外が壁です。ルールを既定から変えた場合はrules に保存されるため、後から見ても前提が分かります。

組み込みのテストケース

シミュレータには小さなプリセットを用意しています。挙動の確認と、説明用の最小例です。

名前	ねらい
Open Grid	壁のない 12×12。基本動作の確認用。
Narrow Corridor	幅 1 の通路。正面衝突が必ず起きる。回廊対称性の説明に使う。
Rooms	4 部屋を狭い出入口でつないだ配置。ボトルネックが分散する。
Cross	十字路。中央で 4 方向が競合する。
Warehouse	棚を並べた倉庫風。MAPD の説明に使う想定の骨格。
Random Obstacles	seed で決まるランダム障害物。同じ seed なら同じ配置になる。
Swap Conflict	1 本道で 2 体が入れ替わる最小例。退避用のくぼみが 1 つだけある。個別に計画すると edge-swap conflict が起きるが、待避すれば解ける。
Bottleneck	1 マスの隘路を多数のエージェントが通る。優先順位の影響が見える。
TAPF: 匿名（1 チーム）	4 体が 1 チーム。どの target へ誰が行ってもよい。チームが 1 つなので匿名 MAPF と同じ。
TAPF: 割当が効く例	1 チーム 2 体。並び順どおりに割り当てると経路が交差するが、入れ替えれば真っすぐ行ける。解いた結果の割当が並び順と違うことを確かめる用。
TAPF: 2 チーム	2 チーム × 2 体。チーム内では交換可能、チームをまたいだ交換は不可。両チームとも並び順とは違う割当が最適になる。
MAPD: well-formed	通路の上下に pickup / delivery、左右の袋小路に parking。Definition 1 の 3 条件を満たす。
MAPD: well-formed でない例	退避できる場所がエージェント数より少ない。条件 (b) を満たさないので TP の保証の対象外。
MAPD: タスクの奪い合いが効く例	遠い agent が取ったタスクを、あとで空いた近い agent が奪えると得をする。TP と TPTS の差が出る。
MAPD: 退避しないと詰まる例	配達地点が通路の途中にある。手が空いた agent をそこへ置いたままにすると後続を塞ぐ。endpoint 規律の有無で差が出る。
MAPD: capacity 2	1 体の agent が同時に 2 件まで運べる。capacity を 1 に戻したコピーと経路・TTD を比較できる。
MG-MAPD: multi-goal	1 件の task が pickup 後に 2 つの delivery goal を順に訪れる。

シミュレータで試す →