本研究は、自動倉庫の搬送層におけるコンベアネットワークを用いた小包ルーティング問題を、新たに「注文連続性制約（order-contiguity constraint）」を導入した $online\ MAPF\text{-}OC$ として定式化している。この制約は、各ワークステーションにおいて同一注文の小包が他の注文に挟まれることなく連続して到着することを要求するものであり、到着順序の入れ替わりによるオペレーターの再仕分け作業や処理遅延を防ぐことを目的としている。エージェント（小包）は、注文ラベル $o_i$、投入頂点 $s_i$、目的地 $d_i$ のタプル $a_i = (o_i, s_i, d_i)$ として定義され、時間経過とともに出現し、目的地到着後にサービス時間 $T_{service}$ を経てネットワークを離脱する動的な設定である。
本研究の主な貢献は、注文の連続性を考慮した新しい問題設定 $MAPF\text{-}OC$ の定式化と、それに対する完全な多項式時間アルゴリズムである $Dual\text{-}Ordering\ Prioritized\ Planning\ (DOPP)$ の提案である。DOPPは、(i) 注文レベルの到着シーケンスの探索、(ii) エージェントレベルの優先順位の精緻化、(iii) 優先順位付き計画法（PP）による経路合成、という3層構造を持つ。この手法は、実行可能な解を迅速に発見した上で、計算予算に応じてメイクスパンを反復的に改善できるanytime特性を備えている。また、実際の倉庫レイアウトを含む様々なコンベアネットワークを用いた実験により、高いスケーラビリティと高品質な計画生成能力を実証した。
提案手法 $DOPP$ は、以下の3つの階層からなる探索ベースのanytimeアルゴリズムである。
1. **Level 1 (Prioritized Planning):** 優先順位に基づき、衝突を回避しつつ経路を合成する。注文の連続性を担保するため、目的地が特定の注文の到着時刻以降にのみ占有可能となる目的地ブロッキング制約 $t \ge t_{arrival}(o)$ を適用する。
2. **Level 2 (Agent-level Refinement):** 同一注文内のエージェント間の優先順位を、近傍探索（Neighborhood Search）を用いて精緻化する。
3. **Level 3 (Order-level Refinement):** ワークステーションへの注文到着順序そのものを、近傍探索によって最適化し、メイクスパンを改善する。
オンライン設定では、時刻 $t$ においてルックアヘッド窓 $[t, t + \Delta T)$ 内に現れるエージェントを対象としたバッチベースの再計画を採用している。
実験では、Small/Medium/Complex/Largeの4種類のコンベアネットワークマップを用い、Admission Controlを用いたPIBT（PIBT-AC）をベースラインとして比較評価を行った。評価指標には、最短移動時間を下限とする正規化メイクスパン $\mathcal{M} = \frac{C_{max}}{L_{min}}$ および目的地利用率 $\text{util} = \frac{1}{|D|} \sum_{d \in D} \frac{C_d}{C_{max}}$ を用いている。結果として、DOPPは全てのマップにおいてPIBT-ACを凌駕する性能を示した。特に、Vanilla DOPPでもLargeマップにおいて実行時間が $10^2$ 秒未満に収まる実用的なスケーラビリティを確認しており、Level 3の洗練（refinement）が性能向上に大きく寄与することが示された。また、Lifelong設定においても、一貫して低いメイクスパンを達成している。
DOPPは、既存のMAPF手法（CBSやPIBT）と比較して、狭い通路での性能低下や効率の減少を抑えつつ、実用的な計算量で実行可能なLifelong実行を実現している。本研究の定式化におけるスナップショットの最適解算出は、既存のMAPFのNP困難性に起因してNP困難であることが示されているが、DOPPは多項式時間で動作する。今後の展望として、より高度な物流自動化に向けて、小包の投入位置や目的地割り当て自体を最適化の変数に組み込んだ、より広範なオンライン $MAPF\text{-}OC$ への拡張が挙げられている。
本研究では、自動倉庫のコンベアネットワークにおいて、同一注文に属する小包が配送先で連続して到着するように制御する「Order-Contiguous Arrivals」の制約を伴う問題を、オンライン多エージェント経路探索（online MAPF-OC）として定式化している。この問題は、エージェント（小包）が時間経過とともに出現し、配送完了時にネットワークから退出するという動的な設定である。提案手法である Dual-Ordering Prioritized Planning (DOPP) は、(i) オーダーレベルの到着シーケンスの探索、(ii) エージェントレベルの優先順位の精緻化、(iii) 優先順位付き計画法（prioritized planning）による実行可能な解の合成、という3層構造を持つ完全な多項式時間アルゴリズムである。実際の倉庫から派生した様々なコンベアネットワークのレイアウトを用いた実験により、DOPP は厳しい時間制約下においても高いスケーラビリティと高品質な計画生成能力を持つことが示されている。
本研究は、自動倉庫の搬送層におけるコンベアネットワークを用いた小包のルーティング問題を、オンラインのマルチエージェント経路探索（online MAPF）として定式化し、新たに「注文連続性制約（order-contiguity constraint）」を導入した $online\ MAPF\text{-}OC$ を提案している。この制約は、各ワークステーションにおいて同一注文の小包が他の注文に挟まれることなく連続して到着することを要求するものであり、到着順序の入れ替わりによるオペレーターの再仕分け作業や処理遅延を防ぐことを目的としている。提案手法である $Dual\text{-}Ordering\ Prioritized\ Planning\ (DOPP)$ は、(i) ワークステーションへの注文到着順序を決定する注文レベルの優先順位探索、(ii) エージェントレベルでの注文内優先順位の精緻化、(iii) 優先順位付き計画法（PP）を用いた衝突回避かつ注文連続性を満たす経路合成、という3段階の最適化プロセスからなる探索ベースの anytime アルゴリズムである。DOPP は完全性を持ち、多項式時間で動作し、実行時間に応じて makespan を反復的に改善できる特性を持つ。実際の倉庫レイアウトを含む様々なコンベアネットワークマップを用いた評価実験により、DOPP は限定的な時間予算内での実用的なスケーラビリティと、アドホックな反応型ポリシーに対する優れた makespan 低減性能が示されている。
従来の小包輸送におけるルーティング研究は、オンラインの経路選択やフロー調整、あるいは MILP やネットワークフローを用いた最適化手法が提案されてきたが、変数の増大により大規模なオンライン計画への適用が困難であった。本研究では、これに対し、共有グラフ上で衝突を回避しながら複数のエージェントを調整する Multi-agent Path Finding (MAPF) を抽象化として用い、一般的な有向グラフ上での衝突のない小包軌道のオンライン合成を目指す。既存の Lifelong MAPF や Online MAPF は、エージェントが時間経過とともに次々と現れる性質を扱うが、本研究が提案する MAPF-OC (Order-Contiguous) は、各目的地において「同一の注文に属する小包が連続したブロックとして到着しなければならない」という順序連続性の制約を導入している。これは、各エージェントに目標の順序が与えられている MAPF-PC とは異なり、注文ブロック自体の到着順序を Makespan を最小化するように最適化する決定変数として扱う点が特徴である。本手法は、倉庫ロボティクスや鉄道ネットワーク、自律交差点の調整といった MAPF の応用範囲を、コンベアシステムへと拡張するものである。
本セクションでは、注文の連続性を考慮したマルチエージェント経路計画（MAPF-OC）の定式化を行っている。コンベアネットワークは有向グラフ $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ としてモデル化され、各頂点は容量1のコンベアセグメントを表し、エージェント $a_i = (o_i, s_i, d_i)$ は注文ラベル $o_i$、投入頂点 $s_i$、目的地 $d_i$ のタプルで定義される。エージェントの経路 $p_i$ は、投入時刻 $t_{start, i} \ge e_i$ において有効であり、目的地到着時刻 $t_{arr, i}$ に到達後、一定のサービス時間 $T_{service}$ を経過してネットワークを離脱する制約を持つ。衝突回避条件に加え、本研究の核心である「注文の連続性（Order-contiguity）」は、目的地 $d$ に到着するエージェントを到着時刻順に並べた際、同じ注文 $o$ に属するエージェントが連続したブロックを形成することを要求する。オフライン設定では、与えられた全エージェント集合 $\mathcal{A}$ に対して、有効、衝突フリー、かつ注文連続性を満たし、最大完了時間（makespan） $M = \max_{a_i \in \mathcal{A}} t_{arr, i}$ を最小化する解を求める。オンライン設定では、バッチベースの再計画を採用し、時刻 $t$ においてルックアヘッド窓 $[t, t + \Delta T)$ 内に現れるエージェントを対象に、スナップショットのmakespanを最小化する。なお、スナップショットにおける最適解の算出は、既存のMAPFのNP困難性から、本問題においてもNP困難であることが示されている。
DOPP (Dual-Ordering Prioritized Planning)は、注文の連続到着（order-contiguity）を維持しつつ、多エージェント経路計画（MAPF）におけるメイクスパンを最適化するanytimeアルゴリズムである。本手法は、注文レベルの優先順位を探索するLevel 3、エージェントレベルの優先順位を探索するLevel 2、および優先順位に基づき優先度付き計画（PP）を実行するLevel 1からなる3層構造を採用している。初期化フェーズでは、アクティブな注文を優先し、エージェントの優先順位を注文の優先順位と整合させることで、PPが多項式時間で実行可能な「well-formed」な設定を保証する。具体的には、Level 1において、エージェントが目的地を占有する時間を制限する目的地ブロッキング制約 $t \ge t_{arrival}(o)$ を適用することで、注文の連続性を担保している。また、計算時間が許す限り、Level 3では保留中の注文の順序を、Level 2では保留中の注文内のエージェント順序を近傍探索（Neighborhood Search）によって改善し、メイクスパンの向上を図る。実験では、CBSやPIBTといった既存手法と比較して、狭い通路での性能低下や効率の減少を抑えつつ、実用的な計算量で実行可能なLifelong実行を実現している。
本研究では、注文の連続到着（Order-Contiguous Arrivals）を考慮したコンベア・パーセル・ルーティングに対し、階層的な近傍探索を用いるDOPP（Decoupled Order-based Planning and Pathfinding）の有効性を評価している。実験は、Small/Medium/Complex/Largeの4種のマップを用い、PIBT-AC（Admission Controlを用いたPIBT）をベースラインとして、スナップショット品質、実行時間、スケーラビリティ、Anytime特性、およびLifelong性能を評価した。評価指標には、最短移動時間を下限とする正規化メイクスパン $\mathcal{M} = \frac{C_{max}}{L_{min}}$ と、目的地利用率 $\text{util} = \frac{1}{|D|} \sum_{d \in D} \frac{C_d}{C_{max}}$ が用いられている。結果として、DOPPは全てのマップにおいてPIBT-ACを凌駕し、特に注文の優先順位を扱うLevel 3の洗練（refinement）が性能向上に大きく寄与することが示された。実行時間に関しては、Vanilla DOPPでもLargeマップで $10^2$ 秒未満に収まる実用的なスケーラビリティを示し、Level3-NS等の洗練手法は計算予算に応じて品質を向上させるAnytime特性を持つ。Lifelong設定においても、スナップショットでの改善が継続的な再計画に反映され、PIBT-ACに対して一貫して低いメイクスパンを達成している。
本研究では、コンベアネットワークにおける注文連続到着（Order-Contiguous Arrivals）を考慮したオンラインMAPF-OC（Multi-Agent Path Finding with Order-Contiguous arrivals）を定式化し、実行可能な解を迅速に発見した上で、許容される限りメイクスパンを改善するanytimeアルゴリズムであるDOPPを提案した。実験の結果、DOPPは実用的なスケーラビリティと高い解の品質を実証しており、従来の倉庫仕分け以外のMAPFアルゴリズムの応用例を拡充した。今後の展望として、より高度な物流自動化に向けて、小包の投入位置や目的地割り当てを組み込んだオンラインMAPF-OCへの拡張が挙げられている。
online MAPF-OCはMAPF, Lifelong MAPF, MAPDとどう異なりますか？
ご質問いただいた、提案問題である online MAPF-OC と、既存の関連概念（MAPF, Lifelong MAPF, MAPD）との違いについて、本文の記述および一般的な研究知識に基づき整理します。
| 用語 | 主な特徴・焦点 | online MAPF-OC との主な違い |
| :--- | :--- | :--- |
| MAPF | 衝突回避経路の合成 | offline設定が主であり、到着順序の制約を持たない。 |
| Lifelong MAPF | 継続的な目標更新 | エージェントの目標更新に焦点を当て、荷物の新規流入や到着順序制約を扱わない。 |
| MAPD | 荷物の回収と配送の最適化 | 荷物の割り当て（Pickup/Deliveryのペアリング）が主眼であり、到着順序の制約は含まない。 |
| online MAPF-OC | 荷物の連続的な流入と、目的地での到着順序制御 | **