[3P5-OS-17a] ひと中心の未来社会とAI

[3P5-OS-17a-01] 期限を考慮したマルチエージェント搬送問題

〇牧野 寛也¹、伊藤 誠悟¹ (1. （株）豊田中央研究所)

キーワード：マルチエージェント経路計画問題、マルチエージェント搬送問題、最短経路問題、数理最適化

本論文では，はじめに期限を考慮したマルチエージェント搬送問題 (Deadline-Aware Multi-Agent Pickup and Delivery, DA-MAPD) を定義する．マルチエージェント搬送問題 (Multi-Agent Pickup and Delivery, MAPD) は，複数の荷物を集荷地点から配達地点まで運ぶための経路を計画する問題であり，MAPD における期限の考慮は自動倉庫や工場などで重要になる．また，DA-MAPD に対する解法として，期限を考慮した Token Passing アルゴリズム (Deadline-Aware Token Passing, DA-TP) を提案する．DA-TP は，共有メモリ (token) を用いたタスク割り当ておよび経路計画を行う従来の Token Passing アルゴリズム (TP) の拡張である．DA-TP では，実行コストと期限に対する緊急度の両者を考慮してタスク割り当てを行う．自動倉庫を模したシミュレーション環境における数値実験により，DA-TP が遅延時間を減少させることを確認した．