Concentration of Measure Phenomenon and its Implications for Sample-based Planning Algorithms in Very-High Dimensional Configuration Spaces
Joel M. Esposito,Joel M. Esposito
In very high-dimensional $(\gg 10)$ spaces, a collection of points generated uniformly at random will concentrate very tightly about its expected value - defying intuition developed in low-dimensional spaces. This paper explores the implications of this for two major classes of sample-based robot motion planning algorithms: Rapidly Exploring Random Trees (RRTs) and Probabilistic Road Maps (PRMs). ...
