Sampling on the $ {\cal C}_{free}$ boundary [22,26]

This scheme is based on the intuition that it is sometimes better to sample along the boundary, $ \partial{\cal C}_{free}$, rather than waste samples on large areas of $ {\cal C}_{free}$ that might be free of obstacles. Figure 5.29a shows one way in which this can be implemented. For each sample of $ {\alpha }(i)$ that falls into $ {\cal C}_{obs}$, a number of random directions are chosen in $ {\cal C}$; these directions can be sampled using the $ {\mathbb{S}}^n$ sampling method from Section 5.2.2. For each direction, a binary search is performed to get a sample in $ {\cal C}_{free}$ that is as close as possible to $ {\cal C}_{obs}$. The order of point evaluation in the binary search is shown in Figure 5.29a. Let $ \tau: [0,1]$ denote the path for which $ \tau(0) \in {\cal C}_{obs}$ and $ \tau(1) \in {\cal C}_{free}$. In the first step, test the midpoint, $ \tau(1/2)$. If $ \tau(1/2) \in {\cal C}_{free}$, this means that $ \partial{\cal C}_{free}$ lies between $ \tau(0)$ and $ \tau(1/2)$; otherwise, it lies between $ \tau(1/2)$ and $ \tau(1)$. The next iteration selects the midpoint of the path segment that contains $ \partial{\cal C}_{free}$. This will be either $ \tau(1/4)$ or $ \tau(3/4)$. The process continues recursively until the desired resolution is obtained.

Steven M LaValle 2012-04-20