Radar maps

Figure 6.22b illustrates which values of $ \theta $ produce collision. We will refer to this representation as a radar map. The four contact orientations are indicated by the contact feature. The notation $ [e_3,v_1]$ and $ [e_2,e_3]$ identifies the two intervals for which $ (x,y,\theta) \in {\cal C}_{free}$. Now imagine changing $ (x,y)$ by a small amount, to obtain $ (x^\prime,y^\prime)$. How would the radar map change? The precise angles at which the contacts occur would change, but the notation $ [e_3,v_1]$ and $ [e_2,e_3]$, for configurations that lie in $ {\cal C}_{free}$, remains unchanged. Even though the angles change, there is no interesting change in terms of the contacts; therefore, it makes sense to declare $ (x,y,\theta)$ and $ (x,y,\theta^\prime)$ to lie in the same cell in $ {\cal C}_{free}$ because $ \theta $ and $ \theta^\prime$ both place the segment between the same contacts. Imagine a column of two $ 3$-cells above a small area around $ (x,y)$. One $ 3$-cell is for orientations in $ [e_3,v_1]$, and the other is for orientations in $ [e_2,e_3]$. These appear to be 3D regions in $ {\cal C}_{free}$ because each of $ x$, $ y$, and $ \theta $ can be perturbed a small amount without leaving the cell.

Figure 6.23: If $ x$ is increased enough, a critical change occurs in the radar map because $ v_1$ can no longer be reached by the robot.
...dder2b.eps,width=1.7in} \\
(a) & (b) \\

Of course, if $ (x,y)$ is changed enough, then eventually we expect a dramatic change to occur in the radar map. For example, imagine $ e_3$ is infinitely long, and the $ x$ value is gradually increased in Figure 6.22a. The black band between $ v_1$ and $ e_2$ in Figure 6.22b shrinks in length. Eventually, when the distance from $ (x^\prime,y^\prime)$ to $ v_1$ is greater than the length of $ {\cal A}$, the black band disappears. This situation is shown in Figure 6.23. The change is very important to notice because after that region vanishes, any orientation $ \theta^\prime$ between $ e_3$ and $ e_3$, traveling the long way around the circle, produces a configuration $ (x^\prime,y^\prime,\theta^\prime) \in {\cal C}_{free}$. This seems very important because it tells us that we can travel between the original two cells by moving the robot further way from $ v_1$, rotating the robot, and then moving back. Now move from the position shown in Figure 6.23 into the positive $ y$ direction. The remaining black band begins to shrink and finally disappears when the distance to $ e_3$ is further than the robot length. This represents another critical change.

The radar map can be characterized by specifying a circular ordering

$\displaystyle ([f_1,f_2],[f_3,f_4],[f_5,f_6],\ldots,[f_{2k-1},f_{2k}]) ,$ (6.6)

when there are $ k$ orientation intervals over which the configurations lie in $ {\cal C}_{free}$. For the radar map in Figure 6.22b, this representation yields $ ([e_3,v_1],[e_2,e_3])$. Each $ f_i$ is a feature, which may be an edge or a vertex. Some of the $ f_i$ may be identical; the representation for Figure 6.23b is $ ([e_3,e_3])$. The intervals are specified in counterclockwise order around the radar map. Since the ordering is circular, it does not matter which interval is specified first. There are two degenerate cases. If $ (x,y,\theta) \in {\cal C}_{free}$ for all $ \theta \in [0,2 \pi)$, then we write $ ()$ for the ordering. On the other hand, if $ (x,y,\theta) \in {\cal C}_{obs}$ for all $ \theta \in [0,2 \pi)$, then we write $ \emptyset$.

Steven M LaValle 2012-04-20