09:00 〜 10:40
[3Pin1-13] GPUを用いたBatch Random Walkによる古典的プランニング
キーワード：プランニング、GPGPU、探索アルゴリズム
Graphical Processing Units(GPU)は，効率的に大規模な並列計算を行うことができるので，様々な分野へ応用されている．本研究では，Monte-Carlo Random Walk(MRW)に基づいて，GPUでの前方探索を用いた古典的プランニングの手法を検討した．まず，MRWの一般化としてBatch MRW(BMRW)を提案する．既存のMRWは単一のノードを始点としてランダムウォークを行うが，BMRWは複数のノードを始点とする．CPU1コアを用いた実験によって，BMRWを用いた充足プランナが，MRWを用いた既存のプランナであるArvand13と同程度の性能であることを示した．続いて，BMRWのランダムウォーク部分をGPU上で行うプランナであるBMRWGを提案し，BMRWGがBMRW に比べて高速であることを示した．さらに，既存の高性能なプランナと比較した場合，BMRWGは複数のIPCベンチマークドメインで同程度かそれ以上の性能を持つことを示した．本稿はICAPS2018の論文[Kuroiwa 18]の extended abstract である．