Predicting the Performance of Randomized Parallel Search: An Application to Robot Motion Planning

Abstract. In this paper we discuss methods for predicting the performance of any formulation of randomized parallel search, and propose a new performance prediction method that is based on obtaining an accurate estimate of the k-processor run-time distribution. We show that the k-processor prediction method delivers accurate performance predictions and demonstrate the validity of our analysis on several robot motion planning problems. Key words: randomized path planning, randomized parallel search, performance evaluation, parallel computers