芸術科学会論文誌 Vol. 22, No. 3, pp. 6:1 – 6:13 (2023)

バトルロイヤルゲームのアイテム探索に適した
マルチエージェント経路探索の定式化
柴山叶 1) (学生会員)

阿部雅樹 2) (正会員)

1) 東京工科大学大学院 バイオ・情報メディア研究科

渡辺大地 2) (正会員)
2) 東京工科大学 メディア学部

Multi-agent route search formulation
suitable for item search in battle royal games.
Kanau Shibayama1)

Masaki Abe2)

Taichi Watanabe2)

1) Graduate School of Bionics, Computer and Media Science, Tokyo University of Technology
2) School of Media Science, Tokyo University of Technology{g312100844, abemsk} ＠ edu.teu.ac.jp, earth@gamescience.jp

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

Abstract
In general, the delivery planning problem used to obtain eﬃcient routes for multi-agents requires all nodes to be visited,
so the cost per agent (travel distance, time, etc.) becomes very high when the number of agents is small and the numberof nodes is large. Therefore, there are cases where the route obtained is not practical, even if it is the optimal solution in
the delivery planning problem. For example, in a time-limited battle royale game, the optimal route cannot be obtainedby implementing an existing method for the delivery planning problem in the AI of a battle royale game because there
is not enough time to visit all the buildings. Therefore, we propose a formula for obtaining a travel route that can selectnodes under cost constraints in order to obtain a practical and eﬃcient route even under the above circumstances. We
then compare the eﬃciency of the existing solution methods with that of VRP, a general delivery planning problem, andDCVRP, which allows cost constraints to be set. The results show that the proposed method is more eﬃcient than theothers when not all nodes can be visited under cost constraints.

– 6:1 –

芸術科学会論文誌 Vol. 22, No. 3, pp. 6:1 – 6:13 (2023)

ヤーを最短距離で追いかけるゲームの敵キャラクターな

1 はじめに
1.1

どである．
これら経路探索においては地図上の地点群と地点間を研究背景

バトルロイヤルゲームでは，まずプレイヤーは 3，4

結ぶ道を，それぞれグラフ理論のノードとエッジとして人のチームを組んで何も持たずに空から降りていく．そ表現する．その中でもバトルロイヤルゲームのアイテム

して地上に着いたら市街地の中を探索し，武器や道具を探索に応用できる理論の礎としては，まず巡回セールス

集めて自身を強化して他のチームのプレイヤーを倒し，マン問題 [9](Traveling Salesman Problem, TSP) が挙

最後 1 チームの生き残りを懸ける．その間，時間経過でげられる．これは，セールスマンがある都市から出発し，

安全地帯が狭まっていく．以上がバトルロイヤルゲーム

全ての都市を訪問して出発地点に帰還する場合，どの順のルールであるが，近年大流行しており，代表的なタイ番で都市を回るのが最短かを求める最短経路問題 [10] で

トルでは PUBG:BATTLEGROUNDS(以下 PUBG)[1]ある．図 2 は TSP の経路取得の例である．

や荒野行動 [2] が挙げられる．バトルロイヤルゲームは1 試合に 100 人程の大人数を要するものが一般的であるが，プレイヤーのみだとマッチングに時間がかかるため
ゲーム AI[3] を採用しているタイトルも多い．また AIと戦うことで練習をしたいプレイヤーも多く，バトルロ
イヤルゲームの AI には相応の需要が見られる．しかし，

図 2 TSP とは．

新しいゲームジャンルかつルールが複雑ということもありゲーム AI は決して充実していない．特に AI の移動に関しては，アイテム探索や戦闘，長期の戦略的に有利な位置取りなど取るべき行動が多岐にわたるため，一つの定式による経路取得では成り立たない．そこで本研究ではアイテム探索の部分に着目し，アイテムをより多く発見できる経路探索の定式化を目指す．なお一連のゲー
ムの流れと研究の対象とする部分を図 1 に表す．

この TSP を複数人で分担して行うものが配送計画問
題 [11] (Vehicle Routing Problem, VRP) である．具体的には複数人で分担して街の全地点を 1 度ずつ訪れる経路の中で，移動距離が最小のものを求める問題で，名前の通り複数台のトラックで街の全顧客に効率的に荷物を配送出来る経路を求めるシステム [12] などに応用される．図 3 に VRP の模式図を示す．バトルロイヤルゲー
ムのアイテム探索においても，複数人でアイテムがある地点を効率的に巡回する必要があるため，この VRP が応用できると考えた．

図1

1.2

バトルロイヤルゲームとは．

先行研究

経路探索はグラフ理論 [4] を元に行われ，日常的な例
であるとカーナビゲーション [5] や電車の乗り換え案内[6] に応用されるが，本研究の対象であるゲームキャラク
ターの移動にも応用されている．Zeyad ら [7] はゲームにおける経路探索は深く研究，活用されていることを示した．具体的な一例としては，Zikky[8] が示したプレイ– 6:2 –

図 3 VRP の例．

芸術科学会論文誌 Vol. 22, No. 3, pp. 6:1 – 6:13 (2023)

また，VRP を拡張した問題として距離制約付き配送

上記の先行研究は全てノードの巡回に焦点を当てたも計画問題 [13](Distance-Constrained Vehicle Routingのであるが，エッジの巡回に焦点を当てた経路探索問題

Problems, DCVRP) が挙げられる．DCVRP は VRP

もある．代表的なものに全てのエッジを巡回する最短経にコスト制約を設けたものである．

路を求める中国人郵便配達問題 [21] や，VRPTW のよ代表的な複数人での経路探索問題は上記 2 つである

うにエッジに対して巡回すべき時間帯の制約をつけたが，これらは全地点を巡回することが前提であるため，

Time-Constrained Chinese Postman Problem[22] があエージェントの数が少なくノードが多い場合は 1 エー

る．Fortnite[23] のように通路からもアイテムを得られジェントあたりのコスト（移動距離や時間など）が非常るバトルロイヤルゲームもあるが極めて稀で，基本的にに大きくなる．バトルロイヤルゲームも一般的に 1 チー

アイテムは通路に落ちていないため，エッジに焦点を当

ム 4 人程度に対し建物の数は非常に多く，加えて時間制てたアプローチは汎用的で無いと考えた．

限もあるため既存解法での最適解は実用的であるとは言

1.3

い難い．

研究目標

本研究ではバトルロイヤルゲームのアイテム探索を次に，コスト制約下で経由ノードの利益の最大化をす

TOP の拡張問題として扱う．各建物の位置関係や探索る本手法に類似した配送計画問題として Team Orien-に要する時間，発見できるアイテムの数からコスト制約

teering Problem[14][15](TOP) が挙げられる．こちらの下で巡回する建物を取捨選択し，探索時間に対し発見で問題は最大化する対象は経由ノードの利益ではあるが，きるアイテム数を増大させる経路探索の定式について提コスト制約は移動距離であり経由したノードで行う作業

案する．

のコストは考慮していない．バトルロイヤルゲームのア

我々は，本研究の初期成果を NICOGRAPH2022 にイテム探索のコスト及び効率には，移動時間に加え建物て発表 [24] し，経路算出アルゴリズム記述の不足に関すの探索に要する時間も大きく影響するため TOP の解法る指摘を受けた．本論文では，設定した制約条件に基づで最適な経路は求めることが出来ないが，本研究の問題

き経路を算出するアルゴリズムを詳細に記すと共に，評も TOP を拡張したものであると言える．

価記述についてより体系化した記述に改めた．

また，VRP に一つのエージェントが運べる荷物数の制約を設けた問題として容量制約付き配送計画問題 [16]，TOP に同様の制約を設けた問題として Capacitated2 提案手法2.1

前提Team Orienteering Problem[17][18] が挙げられる．バ

本研究においてはグラフ理論を使用し，アイテムを得

トルロイヤルゲームでも 1 エージェントが持てるアイテ

られる建物をノード，エージェントの移動経路をエッジ

ムの数は決まっている．しかしバトルロイヤルゲームのとする．バトルロイヤルゲームの市街地とエージェント

アイテム探索では多くのアイテムを運ぶのではなく，必の移動経路を真上から見たイメージが図 4 であり，こ要なものだけを手に入れるために多くのアイテムを見つの建物の位置とエージェントの移動経路をグラフとしてけることが重要なため，上記の先行研究に設けられた制表す．

約は本研究において不要であると言える．
加えて，バトルロイヤルゲームの特徴である時間の制約に着目すると時間枠付き配送計画問題 [19][20](Vehicle

Routing Problem with Time Windows, VRPTW) が先行研究として挙げられる．こちらは各顧客に対して荷物を配送できる時間帯を制限した VRP である．バトル
ロイヤルゲームのアイテム探索にも制限時間があるが，相違点は時間内に安全地帯へ辿り着くことが出来れば他の地点にいつ訪れてもよい点である．
図4– 6:3 –

本研究におけるグラフの表し方．

芸術科学会論文誌 Vol. 22, No. 3, pp. 6:1 – 6:13 (2023)

また本研究で使用するのは重み付き無向グラフであで表すことができる．つまり，始点から終点の移動に要る．一般的な配送計画問題は移動距離をコストとする

した時間と訪れたノードの探索に要した時間の合計で[25] が，移動距離と移動時間は比例する点と建物を探索ある．

する時間もコストとして考慮しなければいけない点か

加えてエージェントの中で最も高い Cm （経路の総コ

ら，エージェントが移動にかかる”時間”を移動コストとスト）を Cmax とした時，コスト制約として以下の制約する．また各ノードには巡回する利益として発見できるを設ける．

Cmax ≤ L.

アイテムの数，建物の探索に要する時間として探索コス(4)

トを設定する．今回は建物が点在する屋外の地形を想定
また求めた経路全体の効率 R を以下のように定義

し，いずれのノード間でも移動出来ることとする．
その上でバトルロイヤルゲームではアイテム探索以外

する．

R=

で孤立することは危険であり，チームでまとまって移動

V
Cmax

.

(5)

することが望ましいため，エージェントには同じ始点かつまり利益を全員が集合するまでの時間で割ったもので

ら出発し同じ終点に集合する制約を設ける．

2.2

あり，R が高いほどアイテム探索の効率が高い経路であ

定式化

ノードの数 を p とする．前述した通りノードは建物であるため，市街地にある建物の数であると言える．次ると言える．

3 既存の配送計画問題の拡張と定式化にエージェントの数を a とおく．これはバトルロイヤル
ゲームの 1 チームの人数であり，a 人全体で最もアイテムを発見できる経路を探すこととなる．そしてノード k
で発見できるアイテムの数を Vk ，ノード k の探索に要する時間 (s) を Tk ，ノード k をエージェント m が訪れたかを xk,m ，エージェント m が始点から終点までの移動にかかった時間 (s) を Em と定義する．また全員が終点に集合するまでの制限時間を L とする．
まずエージェント m の経路において，ノード k に対して xk,m は以下のようになる．

{

xk,m =

0 (訪れていない)
1 (訪れた)Vk xk,mのコスト制約を設けることのできる DCVRP を比較対象とする．そのため 2.1 節と同様の前提条件でも成り立
つよう拡張した問題を定式化し以下に記す．

3.1

VRP

VRP はコスト制約が無いため式 (4) 以外の提案手法と同様の式が成り立つ．また，訪れた地点数の合計 N を
以下の式で表す．

N=

p
a ∑
∑

xk,m .

(6)

m=1 k=1計（発見出来たアイテムの合計）V は

V =て最も代表的な手法である VRP 及び，提案手法と同様(1)

この時，全エージェントが経路を通して得た利益の合pa ∑∑本研究ではマルチエージェントの移動経路算出におい加えて VRP は全地点を訪れることが前提であるため，以下の制約を設ける．

(2)

N = p.

(7)

m=1 k=1

で表すことができる．xk,m はノード k を訪れていない

VRP は全地点を分担して訪れる経路の組み合わせの中時は 0，訪れた時は 1 であるため，上記の式は訪れたノーで，全員が集合するまでの時間を最小化する問題である

ドのみの利益の合計であると言える．提案手法はこの式と考え Cmax を最小化する xk,m の順列を見つける．こ(2) を最大化する xk,m の順列を見つけることで経路を算れは最大値最小化問題であり，エージェント全体の集合

出する．

を g とすると，その名の通り目的関数がまたエージェント m の経路の総コスト Cm は

C m = Em +p∑

Minimize : max(Cm )Tk xk,m(3)

k=1– 6:4 –

subject to : m ⊂ g

芸術科学会論文誌 Vol. 22, No. 3, pp. 6:1 – 6:13 (2023)となるため非線形である．しかしこれは次と等価であ

次に全員が同じ L に集合するという制約は，
p∑る．

Minimize : ζxi,L,m −p∑(8)xL,i,m = 1

(11)

i=1

i=1

subject to : m ⊂ gsubject to : ζ ≥ Cm , m ⊂ gとなる．つまり「あるノードから L を訪れた回数」の方
なぜなら max(Cm ) は全ての Cm の値以上のうちで，が「L からあるノードを訪れた回数」より 1 度だけ多け最小の値 ζ を求めることに等しいからである．あとは式

れば L で経路が終わっていると言える．m に関しては(3) より線形計画問題として以下の式

式 (10) と同様である．
一方で F と L 以外のノードで経路が終わってはいけ

Minimize : ζ(9)subject to : ζ ≥ Em +

p
∑

ないため，
p
∑

Tk xk,m , m ⊂ gp∑xj,i,m = 0

(12)

i=1

i=1

k=1

subject to : i ̸= j, j ⊂ P , m ⊂ g

が，VRP の目的関数となる．

3.2

xi,j,m −となる．つまり F と L 以外のノードは，エージェント

DCVRP

が訪れた回数と出発した回数が同じである．これを全て

DCVRP はコスト制約付きの VRP であるため，式の F と L 以外のノードに制約として与える．

(4) のコスト制約下で全地点を訪れることができる場合

また同じ建物を探索しても非効率なため，誰かが一度は VRP と同様である．しかし式 (4) の制約下で全地点探索した建物は訪れないよう制約を与える．まず提案手を訪れられない場合は，なるべく多くの地点を訪れる
経路が優れていることは明白なため式 (6) を最大化する

法と DCVRP は全地点を巡回する必要がないため以下の式となる．

xk,m を見つけるよう拡張する．

p
a ∑
∑

4 その他の制約

xi,j,k ≤ 1(13)

k=1 i=1

subject to : i ̸= j, j ⊂ P

第 2 章および第 3 章で述べた制約の中で，まだ定式化していないものに関してこちらに記す．まず移動記録のあるノード j に対して，j 以外の全てのノードから，全データについて a を「どのノードから」，b を「どのノーてのエージェントが来たか否かを足して 1 以下あるいはドへ」，c を「対象となるエージェント」として xa,b,c と定1 であれば，ノード j に訪れたのは多くとも 1 エージェ

義し，加えて探索の始点のノード番号を F ，終点のノーントが 1 度だけということである．
一方 VRP は全地点を巡回する必要があるため次の式

ド番号を L，そのマップのノード全体の集合を P ，エー

で制約を与える．

ジェント全体の集合を g とする．
この時，全員が同じ F から出発するという制約は，

p
a ∑
∑

p
∑

k=1 i=1p∑i=1xi,F,m −xF,i,m = −1

xi,j,k = 1(14)

subject to : i ̸= j, j ⊂ P

(10)

i=1

式 (13) と同様に，あるノード j に対して，j 以外の全

subject to : m ⊂ gてのノードから，全てのエージェントが来たか否かを足となる．つまり「あるノードから F を訪れた回数」より

して 1 であれば，必ず j に訪れたのは 1 エージェントが「F からあるノードを訪れた回数」が 1 度だけ多ければ1 度だけということである．

F から出発していると言える．m はエージェントの番

式 (13) あるいは式 (14) 式の制約を全てのノードに対号であり，全てのエージェントに対して同様の制約を加して与えることで，同じ建物を 2 度訪れてしまう非効率

える．

的な経路を避けることができる．

– 6:5 –

芸術科学会論文誌 Vol. 22, No. 3, pp. 6:1 – 6:13 (2023)

5.2

5 実装
5.1

経路算出方法

第 2 章および第 3 章で述べた制約条件は，5.1 章のデー
タ構造を用いると線形計画問題 [27] として実装すること

データ構造

実装にあたり，ノードの数を p，エージェントの人数ができる．
本研究では，制約条件を PuLP[28] というライブラリを a とした時に以下の 3 つのデータを保持する.
図 5 は，各ノードのデータであり，見つかるアイテを用いて算出した．線形計画法の算出アルゴリズムをム数は式 (2) の Vk ，探索にかかる時間は式 (3) の Tk でコーディングする際，通常は目的関数や制約条件の係数ある．

から行列やベクトルの成分を抽出する工程が必要となるが，PuLP はそれらの成分を抽出せず，目的関数や制約条件をコードに直接記述するだけでよい．

PuLP によるコーディングは，大きく• 数理モデル設定 (LpProblem メソッド)
図5• 変数設定 (LpVariable メソッド)

各ノードのデータを保持する p × 4 行列．

• 目的関数設定• 制約条件設定

図 6 は，a 人の各エージェントの移動を記録した物で• ソルバー実行 (solve メソッド)ある．これは第 2 章および第 3 章の定式における xk,mに当たるが，実装上「どのノードから訪れたか」も図 6に分かれる．
数理モデルの設定は，目的関数を最大化するか最小化のように保持する．

するかを設定するものである．以下のソースコード 1 にその具体的な例を示す．
ソースコード 1

数理モデル設定

problem = LpProblem ( sense = LpMaximize )図6

各エージェントの移動を記録する p × p × a 行列．

変数の設定は LpVariable メソッドを用いる．以下の
図 7 は各ノード間の移動時間のデータである．本研究
ではどのノード間でも往来できるため，ワーシャル-フロ

ソースコード 2 は，図 6 の変数配列を生成する箇所のコード例である．

イド法 [26] による各ノード間の距離を更新する必要はな
く，各データは単純な直線距離である．図 6 の各ノード
データと図 7 の各要素を乗算し合計することで，式 (3)の Em を求める．なおノード 0 からノード 1 のデータと，ノード 1 からノード 0 のデータは明らかに等しいが，インデックスの入れ替え処理を削減するため両方保持することとする．

ソースコード 2

変数設定# ary_a : エ ー ジ ェ ン ト の 配 列# ary_p : 建 物 の 配 列
x = [[[ \LpVariable ( " x % s_ %s ,% s " %( i ,j , k ) , \cat = " Binary " ) if i != j \else None for k in range ( ary_a )] \for j in range ( ary_p )] \for i in range ( ary_p )]目的関数は，LpProblem で生成したインスタンスに対
図7

各ノード間の移動時間を保持する p × p 行列．

し「+=」演算子によって式を指定することにより設定できる．以下のソースコード 3 は，目的関数である式 (2)をコードとして記述した例である．lpSum メソッドは，– 6:6 –

芸術科学会論文誌 Vol. 22, No. 3, pp. 6:1 – 6:13 (2023)

LpVariable による変数インスタンスの配列を入力し，そ6.1の総和を求めるメソッドである．
ソースコード 3

実験 1

まずは一般的なバトルロイヤルゲームを想定し，• 建物の棟数: 15

目的関数設定# ary_a : エ ー ジ ェ ン ト の 配 列# ary_p : 建 物 の 配 列• 人数: 4problem += \lpSum ( df . exp_item [ i ] * x [ i ][ j ][ k ] \if i != j \else 0 for k in range ( ary_a ) \for j in range ( ary_p ) \for i in range ( ary_p ))の環境下で地形をランダムに生成し実験に用いた．生• 探索時間: 120(秒)成した地形図を図 8 に示す．

制約条件は，目的関数と同様に「+=」演算子で条件式を指定することにより設定できる．以下のソースコード

4 は，制約条件の一つである式 (12) をコードとして記述した例である．
ソースコード 4

制約条件設定# ary_p : 建 物 の 配 列# j : 建物ごとのカウンター# k : エージェントごとのカウンター

図8

problem += \lpSum ( x [ i ][ j ][ k ] for i in range ( ary_p )) - \lpSum ( x [ j ][ i ][ k ] for i in range ( ary_p )) == 0

実験に使用した地形．

図 8 の黒点はノードであり建物を表す．また右上の 2制約条件を列挙したら，最後に solve メソッドを呼び

つの数字はTk (Vk )出すことで解算出処理を実行する．以下のソースコード

5 は実行処理のコード例である．
ソースコード 5という表記になっている．例えばグラフ中央の 14(1) のノードは 14 秒かけてアイテムが 1 つしか見つからない

ソルバー実行

非効率的な建物であると言える．

problem . solve ()各手法の実験結果を表 1 及び図 9, 10, 11 に示す．色分けされた線が各エージェントの移動経路である．
な お ，PuLP で は 線 形 計 画 法 ア ル ゴ リ ズ ム と し て

図 12 は 3 次元での実験結果のイメージである．色分

COIN-OR Branch and Cut (CBC) ソルバー [29] がけされた球体がエージェント，水色の直方体が出発点，同梱されており，本手法でもこの CBC を採用した．

ピンク色の直方体が集合地点，その他の直方体がアイ
テムを見つけられる建物である．出発点から集合地点に

6 実験

移動するまでに，制限時間の中でアイテムが得られる建人数やマップの広さ，制限時間の条件を変えて，提案手物を探索している様子のシミュレーションである．エー

法と VRP，DCVRP で求められるそれぞれの経路と効ジェントがまだ探索していない建物は灰色で，探索した率を比較する実験を行った．検証に使用したコンピュー

建物はエージェントの色に変わっている．図 13 は図 12

タの OS は Windows10，CPU は Intel Core i7-7820X，を上空から見たもので，それを二次元のグラフにプロッ

メモリは 32GB，プログラム言語は Python，ライブラ

トしたものが図 9, 10, 11 である．

リは PULP である．

表 1 の「発見数」は発見出来たアイテム数，「到着時– 6:7 –

芸術科学会論文誌 Vol. 22, No. 3, pp. 6:1 – 6:13 (2023)

間」は始点から終点までにかかった時間，「効率」は発見
数を到着時間で割った値である．
また，VRP および DCVRP での経路算出も提案手法と同様に Revised Simplex Method を用いて算出した．
表1

実験 1 での各手法の比較．

発見数

到着時間 (秒)

効率

提案手法

100

119.8

0.83

VRP

118

207.6

0.57

DCVRP

76

118.9

0.64

図9

図 11

実験 1 の DCVRP の結果．

図 12

実験結果の 3 次元イメージ．

実験 1 の提案手法の結果．

図 13

実験結果の 3 次元イメージ（上空）．

な地点を避けることが出来ている．
次に式 (4) のコスト制約がなく，全地点を分担して訪れる経路のうち Cmax を最小化する VRP の解法で経路を探索した結果が図 10 である．VRP は制限時間が無い
解法かつ全地点を訪れるため最も発見出来たアイテム数
図 10

は多いが提案手法とさほど変わらず，制限時間を 87 秒

実験 1 の VRP の結果．

も超過しているため冒頭で述べた通り実用性は低い．
式 (2) を最大化する提案手法の方針で経路を探索した

次に DCVRP の解法で経路を探索した．式 (4) のコ

結果が図 9 である．グラフ中央の赤い円で囲んだ 14 秒

スト制約下では全地点を回れないことが分かっているた

かけて 1 つしかアイテムが見つからないような地点や，め式 (6) を最大化する解法で経路を探索した結果が図 11

遠くで孤立していて移動に時間がかかるような非効率的である．提案手法に比べ発見出来たアイテム数は少な– 6:8 –

芸術科学会論文誌 Vol. 22, No. 3, pp. 6:1 – 6:13 (2023)

表4

く，始点から終点までにかかった時間は変わらない．既発見数

到着時間 (秒)

効率

提案手法

84

119.9

0.70

VRP

122

286.1

0.43

DCVRP

65

119.9

0.54

存手法では避けられていた赤い円の非効率的な建物も探索してしまっている．
同様の条件で地形を 10 通りランダムに作成し，各手法を適用させ実験した結果の平均を表 2 に示す．
表2

実験 2 での各手法の比較．

実験 1 での各手法の平均．

発見数

到着時間 (秒)

効率

提案手法

95.7

119.7

0.79

VRP

107.2

207.6

0.52

DCVRP

72.2

119.3

0.61

エージェント数が 4 人での経路探索の場合，提案手法の定式を使い探索することが，汎用的に最も効率が良い
ことが分かった．
本手法および先行手法を用いて 10 回経路探索を実施
し，処理時間の平均を表 3 に示す．
表3

実験 1 における各手法の処理時間

図 14

実験 2 での提案手法の結果．

図 15

実験 2 での VRP の結果．

処理時間 (秒)提案手法

8786.3

VRP

13.1

DCVRP

11709.1

提案手法と DCVRP の処理時間は非常に長く，VRPは比較して非常に短い処理時間となった．

6.2

実験 2

同様に近年流行している APEX LEGENDS[30] 等のタイトルを想定した実験環境でも実験した．こちらは今までのバトルロイヤルゲームとは違い 3 人パーティかつ
マップが比較的狭く作られているため，環境を• 建物の棟数: 12• 人数: 3

悪いため避けている．

• 探索時間: 120(秒)次に VRP の解法で経路を探索した結果が図 15 であと設定した．各手法の実験結果を表 4 及び図 14, 15, 16

る．最短経路問題において経路が交差する場合は最適解に示す．

ではないが，黄色の円で経路が交差してしまっている．

提案手法の方針で経路を探索した結果が図 14 である．
赤い円の建物は一つだけ離れているが 19 秒かけて 18 個

これは他の手法にも同様に言えるが最適解ではなく近似解を求めるソルバー [28] を使用しているためである．

もアイテムを得られる効率の良い建物であるため訪れて

DCVRP の解法で経路を探索した結果が図 16 である．

いる．一方で青い円の建物は始点からも他の建物からもなるべく多くの地点を訪れるよう経路を選択するため効近いが，29 秒かけて 6 個しかアイテムを得られず効率が率が良い赤い円の建物を避けてしまっている．また効率– 6:9 –

芸術科学会論文誌 Vol. 22, No. 3, pp. 6:1 – 6:13 (2023)

状況を設定した．今回は提案手法と VRP の解法を適用させた．表 7 および図 17, 18 に提案手法と VRP の結果を示す．なお DCVRP は制限時間内にすべての建物を訪れることが出来る場合に VRP と同じ経路を導くため
割愛する．
表7

図 16

実験 3 での各手法の比較．

発見数

到着時間 (秒)

効率

提案手法

124

151.7

0.8

VRP

124

106.7

1.2

実験 2 での DCVRP の結果．

の悪い青い円の建物も訪れてしまっている．以上のこと
から得られたアイテム数及び効率が提案手法と比較し低くなった．
同様の条件で地形を 10 通りランダムに作成し，各手法を適用させた結果の平均を表 5 に示す．
表5

実験 2 での各手法の平均．

発見数

到着時間 (秒)

効率

提案手法

79.4

119.8

0.66

VRP

139.0

299.1

0.46

DCVRP

62.3

119.7

0.52

図 17

実験 3 での提案手法の結果．

図 18

実験 3 での VRP の結果．

この結果から，エージェント数や地点数の変化に対してもある程度の汎用性が窺える．
本手法および先行手法を用いて 10 回経路探索を実施
し，処理時間の平均を求めた結果を表 6 に示す．
表6

実験 2 における各手法の処理時間

処理時間 (秒)
提案手法

16.8

VRP

2.9

DCVRP

10.1

エージェント数を一人減らし，建物の数を 3 棟減らしただけで，実験 1 よりも大幅に時間を短縮する結果と
なった．

6.3

提案手法の方針で経路を探索した結果が図 17 である．

実験 3

経路を見ると，スタートから遠い建物を訪れた後にス

実験 1 の条件に対して到着時間を 120 秒 から 300 秒にし，制限時間内にすべての建物を訪れることが出来る

タート付近の建物を訪れている様子が見られ非効率的であることが分かる．

– 6:10 –芸術科学会論文誌 Vol. 22, No. 3, pp. 6:1 – 6:13 (2023)

VRP の解法で経路を探索した結果が図 18 である．始とが必要であると言える．

点から近い順に分担して建物を訪れている様子が見られまた処理時間に関しては，現状はどの手法もリアルタる．提案手法においても制限時間内で全ての建物を訪れイムに活用できるスコアでは無い．しかし基本的にバトることが出来るため，発見できるアイテムは両手法変わ

ルロイヤルゲームのマップとアイテムが見つかる地点はらない．加えて到着時間を最小化する解法のため全員集変わらないため，事前に経路を算出して活用する方法で合するまでの時間が提案手法より少なく，効率も高い結も，キャラクター AI のアイテム探索の効率化に寄与出果となった．

来ると考える．

同様の条件で地形を 10 通りランダムに作成し，各手法を適用させた結果の平均を表 8 に示す．
表8

本研究ではバトルロイヤルゲームのアイテム探索に

実験 3 での各手法の平均．

発見数

到着時間 (秒)

効率

提案手法

152.1

201.7

0.75

VRP

152.1

135.4

1.12

適した配送計画問題の定式を提案した．その上でアイ
テム探索に利用できる既存の理論として挙げた VRP,DCVRP の解法と経路の効率を比較をした．
その結果，コスト制約下で全地点を経由することが出

この結果から，制限時間が余る場合は既存手法である

VRP の方が適していることが分かる．
本手法および VRP を用いて 10 回経路探索を実施し，処理時間の平均を求めた結果を表 9 に示す．
表97 まとめと今後の展望

来ない状況下では本手法が最も効率の高い経路を導くことが分かった．エージェント数やノード数を変えても有効な結果を出したためある程度の汎用性が確認出来た．
しかし，コスト制約下で全地点を経由することができる状況下では，既存の VRP, DCVRP の方が有効である

実験 3 における各手法の処理時間ことが分かった．

処理時間 (秒)今回はあらかじめ実験に使用するグラフにエッジを設

提案手法

42.2

定しておらず，どのノード間でも直接移動できる環境下

VRP

14.3

で実験した．そのためバトルロイヤルゲームにおいては建物が点在する市街地など屋外でのアイテム探索などで

6.4

考察

有効だと考えられる．今後の展望として，エッジを設定

6.1 節と 6.2 節に示した実験結果より，制限時間内にし移動できるノードを制限したグラフを使い，入り組ん全ての建物を訪れることが出来ない状況下においてはだマップや迂回する必要のあるマップでも有用性を示す

提案手法が有効であると考えられる．これはバトルロイ

ことが出来れば，応用できるシチュエーションも増える

ヤルゲーム，ひいては制限時間などのコスト制約下でよと考えている．

り利益の高い経路を求める際には，取捨選択の出来ない
既存の配送計画問題の解法が適していないことを示して
いる．

参考文献
[1] KRAFTON INC., 2021. PUBG —KRAFTON.

一方 6.3 節より，制限時間が余る状況下では提案手法

https://asia.battlegrounds.pubg.com/ja/.

は適していないことが分かる．原因は処理時間を見て分

参照: 2023.02.02.

かる通り，提案手法はあくまで式 (2) の V を最大化する[2] NetEase, Inc., 2017. 荒野行動 —NetEase Games.

解法であるため，全建物を訪れることが出来た時点で経https://www.knivesout.jp/. 参照: 2023.02.03.

路のコストに関係なく最適解であると判断出来てしまう[3] 三宅陽一郎. ディジタルゲームにおける人工知能のからだと考察する．

応用の現在. 人工知能, Vol. 30, No. 1, pp. 45–64,以上のことからバトルロイヤルゲームのアイテム探索など，想定されるコスト制約に幅がある環境においては

2015.
[4] Alan M. Gibbons. Encyclopedia of Computer Sci-

特に，単一の移動経路算出手法ではなく複数を用いるこ– 6:11 –芸術科学会論文誌 Vol. 22, No. 3, pp. 6:1 – 6:13 (2023)

ence, pp. 755–759. John Wiley and Sons Ltd.,2003.

161–172, 1984.
[14] Marcus Poggi, Henrique Viana1, and Eduardo[5] Grantham KH Pang, K Takabashi, Takayoshi

Uchoa. The team orienteering problem: Formu-

Yokota, and Hiroshi Takenaga. Adaptive route

lations and branch-cut and price.

selection for dynamic route guidance system

Erlebach and Marco Lübbecke, editors, ATMOS,

based on fuzzy-neural approaches. IEEE Trans-Vol. 14, pp. 142–155, January 2010.

actions on Vehicular Technology, Vol. 48, No. 6,

In Thomas[15] C. Archetti, M.Grazia Speranza, and Daniele

pp. 2028–2041, 1999.

Vigo. Vehicle Routing: Problems, Methods, and[6] 林 良嗣; 槇谷 博光; 大島 邦彦; 中村英夫;. 大規模鉄Applications, Second Edition. Society for Indus-

道ネットワークにおける経路探索の簡略化手法に関trial and Applied Mathematics, November 2014.

する研究. 土木学会論文報告集, Vol. 338, , 1983.

[16] Zuzana Borcinova. Two models of the capaci-[7] Zeyad Abd Algfoor, Mohd Shahrizal Sunar, andtated vehicle routing problem. Croatian Opera-

Hoshang Kolivand. A comprehensive study ontional Research Review, Vol. 8, pp. 463–469, De-

pathﬁnding techniques for robotics and video

cember 2017.

games.

International Journal of Computer[17] C. Archetti, Dominique Feillet, Alain Hertz, andGames Technology, pp. 7–18, 2015.
[8] Moh Zikky.

M.Grazia Speranza. The capacitated team orienteering and proﬁtable tour problems. JORS,

Review of a*(a star) navigation

Vol. 60, pp. 831–842, June 2009.

mesh pathﬁnding as the alternative of artiﬁcial
intelligent for ghosts agent on the pacman game.

[18] Claudia

Archetti,

NicolaBianchessi,

and

EMITTER International journal of engineering

M. Grazia Speranza.

The capacitated teamtechnology, Vol. 4, No. 1, pp. 141–149, 2016.

orienteeringwithproblemincomplete

ser-vice. Optimization Letters, Vol. 7, No. 7, pp.

[9] Merrill M Flood. The traveling-salesman prob-

1405–1417, 2013.

lem. Operations Research, Vol. 4, No. 1, pp. 61–[19] 有熊 翼; 松冨 達夫; 木村有寿;. ファジィ性を考慮

75, December 1956.

した時間枠付き多目的配送計画問題の解法. Fuzzy[10] Ravindra K. Ahuja, Kurt Mehlhorn, James Orlin,
and Robert E. Tarjan. Faster algorithms for the

System Symposium, Vol. 27, , September 2011.

shortest path problem. J. ACM, Vol. 37, No. 2,[20] Brian; Kallehauge. On the vehicle routing prob-

pp. 213–223, apr 1990.

lem with time windows. Master’s thesis, Technical University of Denmark, 2006.

[11] Paolo Toth and Daniele Vigo. The Vehicle Routing Problem. Monographs on Discrete Mathemat-[21] Malandraki; Chryssi and Daskin; Mark;. The

ics and Applications. Society for Industrial andmaximum beneﬁt chinese postman problem andApplied Mathematics, 2002.

the maximum beneﬁt traveling salesman problem. European Journal of Operational Research,[12] Kris Braekers, Katrien Ramaekers, and InnekeVol. 65, pp. 218–234, 1993.

Van Nieuwenhuyse. The vehicle routing problem:
State of the art classiﬁcation and review. Com-[22] Wang Hsiao-Fan; Wen Yu-Pin;. Time-constrained

puters and Industrial Engineering, Vol. 99, pp.

chinese postman problems. Computers and Math-

300–313, 2016.

ematics with applications, Vol. 44, No. 3-4, pp.
375–387, 2002.

[13] G. Laporte, M. Desrochers, and Y. Nobert. Twoexact algorithms for the distance-constrained ve-[23] Epic Games Inc., 2023. Fortnite —Epic Games.

hicle routing problem. Networks, Vol. 14, pp.

https://www.fortnite.com/. 参照: 2023.02.02.

– 6:12 –芸術科学会論文誌 Vol. 22, No. 3, pp. 6:1 – 6:13 (2023)[24] 柴山叶, 阿部雅樹, 渡辺大地. バトルロイヤルゲーム

柴山 叶のアイテム探索におけるマルチエージェント移動経路最適化. NICOGRAPH2022, No. F-2, pp. 1–8,

2022.
[25] William Ho, George TS Ho, Ping Ji, andHenry CW Lau. A hybrid genetic algorithm forthe multi-depot vehicle routing problem.

En-

2021 年会津大学コンピュータ理工学部卒業．2023 年東gineering applications of artiﬁcial intelligence,

京工科大学大学院修士課程バイオ・情報メディア研究科

Vol. 21, No. 4, pp. 548–557, 2008.

メディアサイエンス専攻修了．芸術科学会会員．

[26] Stefan Hougardy. The ﬂoyd–warshall algorithm
on graphs with negative cycles. Information Pro-阿部雅樹

cessing Letters, Vol. 110, No. 8-9, pp. 279–281,
2010.
[27] Alexander Schrijver; John Wiley and Sons;. Theory of Linear and Integer Programming. 1998.
[28] pulp documentation team., 2009-2023.
Document.

PuLP

https://coin-or.github.io/

pulp/. 参照: 2023.02.02.

2008 年東京工科大学メディア学部卒業．2010 年同大[29] John Forrest and Robin Lougee-Heimer. CBC
User’s Guide.

https://www.coin-or.github.

io/Cbc/. 参照: 2023.05.06.

学大学院修士課程バイオ・情報メディア研究科メディア
サイエンス専攻修了．2016 年より同大学メディア学部
実験助手，現在に至る．コンピュータグラフィックスや[30] Electronic Arts Inc., 2023. APEX LEGENDS

ゲーム制作に関する研究に従事．芸術科学会会員．

—Electronic Arts. https://www.ea.com/ja-jp/
games/apex-legends. 参照: 2023.02.02.

渡辺大地

1994 年慶応義塾大学環境情報学部卒業．1996 年慶応義塾大学政策・メディア研究科修士課程修了．2016 年岩手大学工学研究科デザイン・メディア工学専攻博士後期課
程修了．博士 (工学)．1999 年より東京工科大学メディア学部講師．2017 年より同准教授，2020 年より同教授，
現在に至る．コンピュータグラフィックスやゲーム制作
に関する研究に従事．芸術科学会，情報処理学会，画像
電子学会，人工知能学会会員．

– 6:13 –