Multi-agent route search formulation suitable for item search in battle royal games.
Kanau Shibayama, Masaki Abe, Taichi Watanabe · The Journal of the Society for Art and Science · 2023
一般的にマルチエージェントでの効率的な移動経路取得に応用される配送計画問題は，全てのノードを必ず巡回するため，エージェントの数が少なくノードが多い場合は1エージェントあたりのコスト(移動距離や時間など) が非常に大きくなる．そのため求めた経路が配送計画問題においては最適解でも実用性を伴わないケースが見られる．例えば時間制限のあるバトルロイヤルゲームにおいて，全ての建物を巡回すると時間が足りないため，配送計画問題の既存手法をバトルロイヤルゲームのAIに実装しても最適な移動経路を求めることは出来ない．そこで本研究では上記のような状況下でも実用的かつ効率的な経路を求めるべく，コスト制約下でノードを取捨選択出来る移動経路取得の定式について提案する．そのうえで一般的な配送計画問題であるVRP，コスト制約を設けることのできるDCVRP の二つの問題の既存解法による探索結果と効率を比較した．その結果，コスト制約下で全てのノードを訪れることが出来ない状況下では，提案手法が他手法より効率の良い経路を求められることが示された．