複数ロボットの経路衝突・待機
バグ・不具合を報告
複数のロボットが同一格子上を移動する際の時刻別占有と待機を考慮し、衝突しない経路を探索する。
項目を入力・選択してから「計算する」を押してください。
選択内容に応じて、残りの入力項目を案内します。
計算結果
—tick
- 最遅到着
- —tick
- 最終頂点衝突
- —件
- 最終禁止swap
- —件
- 個別経路の頂点衝突
- —件
- 個別経路のswap
- —件
- CBS展開ノード数
- —件
値を入力して計算してください。
この計算機は使いやすかったですか?
回答はサイト改善のために保存します。入力値・計算結果は送りません。
ありがとうございます。よかったら、上の共有ボタンからこの計算機を紹介しませんか?
計算方法・適用範囲・出典
計算方法
各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。