Concentration of Measure Phenomenon and its Implications for Sample-based Planning Algorithms in Very-High Dimensional Configuration Spaces

摘要

In very high-dimensional <tex>$(\gg 10)$</tex> 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). First we show that the graph vertices concentrate in a thin-shelled hyper-sphere, with almost none near the origin nor at the edges of the workspace. Next we examine how varying one of the algorithms' parameters - the maximum edge length- can dramatically alter the algorithms' complexity and the connectivity of the resulting graph. Finally, we explore how the position of the initial node, often placed arbitrarily, can impact the shape of the graph. While the contributions of this paper are largely theoretical, many robotic applications of practical interest have extremely high-dimensional configuration spaces including humanoids, swarms and soft (a.k.a. continuum) robotics.