MAPDとは
Multi-Agent Pickup and Delivery（MAPD）は、運搬タスクが次々に発生し続ける環境で、割当と経路計画を同時に解き続ける問題です。 倉庫のロボットがこの形にあたります。
問題設定と代表的な解法は [mapd-tp-tpts-central-2017] にあります。
MAPF との違い
| MAPF（one-shot） | MAPD | |
|---|---|---|
| 目標 | 各エージェントに固定の目標が 1 つ | 固定の目標は無い。タスクが与えられる |
| タスク | なし | (pickup, delivery) の対。時間とともに到着し続ける |
| 割当 | 不要 | 誰がどのタスクをやるかも決める |
| 終わり | 全員が目標に着いたら終了 | 終わらない。運用し続ける |
| 指標 | sum of costs / makespan | service time / throughput / 未処理タスク数 |
主な指標
- service time — タスクが発生してから配達が完了するまでの時間
- throughput — 単位時間あたりに完了したタスク数
- 未処理タスク数 — まだ誰にも割り当てられていない、または配達が終わっていないタスク
シミュレータでの対応状況
シミュレータでは pickup / delivery の配置とタスク生成（タスク数・到着率・seed）ができ、 シナリオ JSON にも保存されます。 ただし現時点で MAPD に対応した Solver は未実装のため、実行はできません。 実装が入り次第、シミュレータの選択肢に現れます。
MAPD 系の手法一覧 ・Lifelong MAPF の手法一覧
このページは原論文の定義に基づいて書いていますが、節番号・ページ番号までの照合は未了です。