PRM

Probabilistic Roadmap — a sampling-based motion planning algorithm that pre-computes a graph of collision-free random configurations connected by local paths, then searches the graph for a path from start to goal. PRM is suited for multi-query planning where many different start-goal pairs are queried on the same map. It is complete in the probabilistic sense (finds a path if one exists, given enough samples).