Samplingbased

Samplingbased refers to methods that solve problems by generating samples from a search space and using them to construct approximate solutions. These approaches rely on random or quasi-random sampling rather than exhaustive enumeration or fixed discretization, making them suitable for high-dimensional or complex spaces. They are used in robotics, optimization, computer graphics, and probabilistic inference.

In motion planning, sampling-based algorithms build graphs or trees by sampling configurations and connecting feasible samples. Notable examples include probabilistic roadmaps and rapidly exploring random trees. In optimization, these methods draw candidate solutions from a distribution and update that distribution based on performance, as in random search, the cross-entropy method, and certain evolutionary strategies.

In statistics and machine learning, sampling underpins methods such as Markov chain Monte Carlo, which approximate posterior distributions by drawing samples. Theoretical properties often discussed for sampling-based methods include probabilistic completeness and asymptotic optimality in specific problem families, meaning that with increasing samples, a feasible or optimal solution becomes more likely and the solution quality tends to improve.

Benefits of sampling-based methods include scalability to high dimensions and reduced reliance on precise discretization. Limitations include the computational costs of sampling and evaluation, dependence on the sampling strategy, and potential inefficiency if samples poorly cover the space. Post-processing and heuristics are often used to refine results.

History: sampling-based ideas gained prominence in robotics in the 1990s with the development of probabilistic roadmaps and related planners. Since then, they have become a core tool for problems where exact methods are impractical.