[3Pin1] インタラクティブ(1)

[3Pin1-13] Batch Random Walk for GPU-Based Classical Planning(Extended Abstract)

〇Ryo Kuroiwa¹, Alex Fukunaga¹ (1. the University of Tokyo)

Keywords:planning, GPGPU, search algorithm

Graphical processing units (GPUs) have become ubiquitous because they offer the ability to perform cost and energy efficient massively parallel computation. We investigate forward search classical planning on GPUs based on Monte-Carlo Random Walk(MRW). We first propose Batch MRW (BMRW), a generalization of MRW which performs random walks starting with many seed states, in contrast to traditional MRW which used a single seed state. We evaluate a sequential implementation of BMRW on a single CPU core and show that a sequential, satisficing planner based BMRW performs comparably with Arvand, the previous MRW-based planner. Then, we propose BMRW_G, which uses a GPU to perform random walks. We show that BMRW_G achieves significant speedup compared to BMRW and achieves competitive performance on a number of IPC benchmark domains. This is an extended abstract of an ICAPS2018 paper [Kuroiwa 18].