Obstacle region for multiple bodies

If the robot consists of multiple bodies, the situation is more complicated. The definition in (4.34) only implies that the robot does not collide with the obstacles; however, if the robot consists of multiple bodies, then it might also be appropriate to avoid collisions between different links of the robot. Let the robot be modeled as a collection, $ \{{\cal A}_1,{\cal A}_2,\ldots,{\cal A}_m\}$, of $ m$ links, which may or may not be attached together by joints. A single configuration vector $ q$ is given for the entire collection of links. We will write $ {\cal A}_i(q)$ for each link, $ i$, even though some of the parameters of $ q$ may be irrelevant for moving link $ {\cal A}_i$. For example, in a kinematic chain, the configuration of the second body does not depend on the angle between the ninth and tenth bodies.

Let $ {P}$ denote the set of collision pairs, in which each collision pair, $ (i,j) \in P$, represents a pair of link indices $ i,j
\in \{ 1,2,\ldots,m\}$, such that $ i \not = j$. If $ (i,j)$ appears in $ {P}$, it means that $ A_i$ and $ A_j$ are not allowed to be in a configuration, $ q$, for which $ {\cal A}_i(q) \cap {\cal A}_j(q) \not = \emptyset$. Usually, $ {P}$ does not represent all pairs because consecutive links are in contact all of the time due to the joint that connects them. One common definition for $ P$ is that each link must avoid collisions with any links to which it is not attached by a joint. For $ m$ bodies, $ {P}$ is generally of size $ O(m^2)$; however, in practice it is often possible to eliminate many pairs by some geometric analysis of the linkage. Collisions between some pairs of links may be impossible over all of $ {\cal C}$, in which case they do not need to appear in $ {P}$.

Using $ {P}$, the consideration of robot self-collisions is added to the definition of $ {\cal C}_{obs}$ to obtain

$\displaystyle {\cal C}_{obs}= \Bigg( \bigcup_{i=1}^{m} \{ q \in {\cal C}\;\vert...
... {\cal C}\;\vert\; {\cal A}_i(q) \cap {\cal A}_j(q) \not = \emptyset \} \Bigg).$ (4.36)

Thus, a configuration $ q \in {\cal C}$ is in $ {\cal C}_{obs}$ if at least one link collides with $ {\cal O}$ or a pair of links indicated by $ {P}$ collide with each other.

Steven M LaValle 2012-04-20