This summary is written to provide some analysis of the running time of PRM. The main objective is to show how probabilistic completeness can be proved for a given choice of planning problem, local planner and configuration generator. A PRM planner is probabilistically complete if for any query, the probability of answering the query incorrectly after building a roadmap goes to zero as the number of milestones goes to infinity. In the following treatment, we analyze a simplified version of PRM which tries all pairs of connections in the roadmap.
expansiveness