ペトリネットの全単模性を利用したタスク割当と経路探索の構造的整合性

- Task Assignment and Path Finding (TAPF) を対象に、複数ロボットの衝突回避運動とゴール選択を同時に解く最適化問題を扱う研究。 - 時間展開を明示せず、Petri net (PN) ベースの最適化フレームワークを構築。 - 安全性は連続する中間 marking 間の unit-capacity traversal として課し、時間解釈に依存しない協調戦略を導く。 - Boolean specifications over regions of interest へ拡張し、two-stage LP/MILP scheme を提案。

- 既存の optimization-based approaches は time-expanded network-flow models に依存し、大規模 mixed-integer programs となり scalability が限られる。 - 本研究は明示的な時間展開なしに motion model の構造的性質を利用し、計算効率を改善。 - 固定した congestion level（synchronization depth）で constraint matrix の total unimodularity を示し、LP relaxation の integral optimal solutions を保証。 - 大規模ベンチマークで time-expanded optimization baselines に対し大幅な scalability 改善を報告。

- ロボット運動を strongly connected state-machine PNs でモデル化。 - congestion level（synchronization depth）を整数に固定すると motion-planning constraint matrix が totally unimodular となり、motion variables の LP relaxation が integral optimal solutions を持つ。 - congestion が 1 を超える場合、intermediate markings に基づく synchronization-on-demand mechanism を導入。 - 同期段数を固定すれば対応する constraint matrices の total unimodularity が保たれ、motion variables の integrality を維持。 - Boolean specifications には two-stage LP/MILP scheme を用い、integrality を task-s…

- 大規模ベンチマーク上の simulations を実施。 - time-expanded optimization baselines と比較し、scalability の大幅な改善を示した。 - 具体的なベンチマーク名・指標・数値は要旨からは不明。

- congestion level や synchronization stages を固定した条件下での total unimodularity と integrality が議論の中心。 - 同期段数固定が解の質や計算負荷に与える影響の詳細は要旨からは不明。 - Boolean specifications における two-stage scheme の一般性や限界は要旨からは不明。 - 実機実験の有無や動的環境への適用性は要旨からは不明。

- time-expanded network-flow models を用いた既存の TAPF 最適化研究（baselines）。 - Petri net を用いた motion planning / multi-robot coordination の関連研究。 - total unimodularity を利用した整数計画の LP relaxation に関する理論研究。 - synchronization-on-demand や intermediate markings に関連する PN ベースの手法。