複数ロボットの経路衝突・待機

複数のロボットが同一格子上を移動する際の時刻別占有と待機を考慮し、衝突しない経路を探索する。

項目を入力・選択してから「計算する」を押してください。

選択内容に応じて、残りの入力項目を案内します。

計算する内容
障害物セル(必要な分のみ)任意
行x(列)y(行)操作
1

2列を左端の欄へタブ区切りで貼り付けられます。200行まで。

xは右方向、yは下方向。左上を(0,0)とし、空行は無視します。

ロボットの開始・目標必須
行ロボットID開始x開始y目標x目標y操作
1
2

5列を左端の欄へタブ区切りで貼り付けられます。6行まで。

IDは英字から始める半角英数字・_・-、20文字以内。開始・目標座標は0始まりで入力。

0〜40。時刻0を含む。滞在もこの時刻以内に完了させます。


計算結果

値を入力して計算してください。

お気に入り一覧

計算方法・適用範囲・出典

計算方法

各agent iの時間展開状態(x,y,t)で4近傍移動・待機を1tickとしてA*最短路を探索。CBSで最初の頂点衝突(v,t)に各agentの禁止頂点制約を、逆方向swap(u→v,t)に禁止辺制約をそれぞれ分岐追加し、当該agentのみ再探索。CTノードはΣ arrival_iを優先、同値ならmakespanと生成順。到着後stayは無期限占有、disappearは到着tickのみ、dwellは到着から追加dwellTicksだけ占有。cost=Σ最終到着tick、makespan=max最終到着tick。

各ロボットの時刻付き経路、衝突前後の頂点・swap件数、makespan、sum of costs、探索ノード数。

計算例(架空の数値)

3×2格子、A:(0,0)→(1,0)、B:(1,0)→(0,0)の同時逆方向移動はswap衝突です。交換禁止なら空き行への迂回が必要です。

適用対象と限界

障害物が固定で、移動と待機が同じ長さの一斉離散tickで表せる仮想格子上のロボット。連続時間・実機走行・速度・旋回・積荷・物理的安全距離・途中ウェイポイント/時間窓・動的障害物は対象外です。。

採用した方式

  • 離散4近傍CBS(総到着時間最小)(E1852 v1.0):対象範囲 最大20×20、6ロボット、40tick、期限と探索予算付き/適用地域 global

方法と出典

方法:E1852 bounded discrete MAPF CBS SOC v1.0 (2026-11-15)。データ記録日:2026-11-15。