 Minkowski addition for collision detection

Suppose a robot occupies a closed set $R\subseteq {\mathbb{R}}^n$ relative to its chosen reference point, and a closed obstacle occupies $O$. Keep the robot's orientation fixed and allow only translations. At reference position $q$, its occupied set is $q+R$. If touching counts as collision, the forbidden positions in this configuration space are exactlyThe minus sign reflects the robot through its reference origin: solving $q+r=o$ gives $q=o-r$. Thus collision checking for a moving shape becomes checking whether one point lies in a fixed Minkowski sum. Steven M. LaValle derives this translational configuration space construction in Planning Algorithms, section 4.3.2, equation 4.37 and Example 4.13.

For a concrete toy example, take the robot rectangle $R=[0,2]\times [0,1]$ with its reference point at the lower-left corner, and obstacle rectangle $O=[4,6]\times [2,4]$. Their collision region is the rectangleFor example, $q=(3,3/2)$ is forbidden: $q+R=[3,5]\times [3/2,5/2]$ meets $O$ in $[4,5]\times [2,5/2]$, of area $1/2$. At $q=(2,1)$ there is just corner contact, which our convention also forbids. Using $O+R=[4,8]\times [2,5]$ instead would wrongly miss both reference positions. Only when $R=-R$, as for an origin-centred disk, does the reflection leave the robot set unchanged.

The same calculation handles bounded additive uncertainty. If the actual reference position is $q+e$ for any $e\in E$, the union of possible occupied sets is $q+(E+R)$. There exists an allowed error causing contact exactly whenConsequently avoiding this set guarantees avoidance for every $e\in E$ in this model. For $E=[-\epsilon ,\epsilon {]}^2$, the example's forbidden region becomes $[2-\epsilon ,6+\epsilon ]\times [1-\epsilon ,4+\epsilon ]$, with area $(4+2\epsilon )(3+2\epsilon )$. Here $-E=E$ because the error bounds are symmetric; a one-sided error set must still be negated. This is a worst-case geometric bound, not a probability of collision. Rotating the robot requires an orientation-dependent Minkowski sum for each orientation.