Configuration Spaces, Minkowski Sums, and Translational Motion Planning

Configuration Spaces, Minkowski Sums, and Translational Motion Planning

A robot moving through a room seems to pose a question about two shapes: does the robot overlap an obstacle? Configuration space turns it into a question about one point: does the robot's chosen reference point enter a forbidden region? That change of viewpoint is the foundation of motion planning.

Part 20 used binary space partitions to organize visible surfaces and spatial order. Here we organize possible poses. The result is a bridge from geometric modeling to planning: after obstacles have been transformed into forbidden configurations, Part 22 can connect the remaining free configurations with a visibility graph and search for a shortest route.

From Workspace to Configuration Space

The workspace is the physical plane containing the robot and obstacles. A configuration is the smallest tuple that completely specifies the robot's pose. For a point robot translating in the plane, it is simply $q=(x,y)$. For a rigid polygon allowed to translate but not rotate, it is still $(x,y)$ once we choose a reference point fixed in the polygon. If rotation is allowed, it becomes $(x,y,\theta)$.

The set of all configurations is the configuration space, or C-space. It divides into:

• $C_{\mathrm{obs}}$, configurations at which the robot intersects an obstacle;
• $C_{\mathrm{free}}$, configurations allowed by the collision policy.

A continuous collision-free motion is therefore a curve $\gamma:[0,1]\to C_{\mathrm{free}}$ with $\gamma(0)=q_s$ and $\gamma(1)=q_g$. Planning asks whether such a curve exists; optimization may additionally ask for the shortest, safest, or smoothest one.

For a point robot, workspace and C-space almost coincide: each physical obstacle is already a forbidden set for $(x,y)$. A polygonal robot changes the geometry because collision depends on the whole translated footprint.

Why the Robot Is Reflected

Let $R$ be the robot footprint expressed relative to reference point $r_0=(0,0)$, and let $R+q=\{r+q:r\in R\}$ be the robot translated to configuration $q$. A workspace obstacle $O$ blocks exactly those translations satisfying

$$ (R+q)\cap O\ne\varnothing. $$

At collision, some $r\in R$ and $o\in O$ obey $r+q=o$, so $q=o-r$. The forbidden set is thus

$$ C_O = \{o-r:o\in O,\ r\in R\}=O\oplus(-R), $$

where $A\oplus B=\{a+b:a\in A,b\in B\}$ is the Minkowski sum, and $-R=\{-r:r\in R\}$ is the robot reflected through its reference point. The minus sign is not decorative: it follows directly from solving $r+q=o$ for $q$.

Changing the reference point translates the coordinates of every configuration and every C-obstacle, but it does not change which physical placements collide. A vertex, centroid, or convenient local origin all work if used consistently. Start and goal must name the position of that same reference point.

Computing a Convex Minkowski Sum

For convex polygons $A$ and $B$ with counterclockwise vertices, $A\oplus B$ is convex. One simple method forms every pairwise vertex sum and takes their convex hull, but that creates $mn$ candidates. A linear-time method instead merges boundary edge directions.

Rotate each cyclic vertex list so it begins at its lowest, then leftmost, vertex. Convert both boundaries to edge vectors in counterclockwise angular order. Begin at $a_0+b_0$ and repeatedly append the edge with smaller polar angle; when angles tie, append their vector sum. This is analogous to merging sorted lists and takes $O(m+n)$ time once the polygons are normalized.

def convex_minkowski_sum(A, B):
    """CCW convex polygons, rotated to lowest-then-leftmost vertex."""
    A = normalize_cycle(A)
    B = normalize_cycle(B)
    ea = edge_vectors(A)
    eb = edge_vectors(B)
    i = j = 0
    out = [add(A[0], B[0])]

    while i < len(ea) or j < len(eb):
        if j == len(eb) or (i < len(ea) and angle_before(ea[i], eb[j])):
            step = ea[i]
            i += 1
        elif i == len(ea) or angle_before(eb[j], ea[i]):
            step = eb[j]
            j += 1
        else:  # parallel edges with the same direction
            step = add(ea[i], eb[j])
            i += 1
            j += 1
        out.append(add(out[-1], step))

    return remove_collinear_and_repeated_endpoint(out)

In production, angle_before should compare half-planes and cross-product signs rather than call atan2. This avoids transcendental rounding and handles equal directions explicitly.

Nonconvex Shapes and Obstacle Unions

If either input is nonconvex, merely merging its edge directions is wrong: the boundary is not globally ordered like a convex support function. A common exact pipeline decomposes a nonconvex obstacle and robot into convex pieces, computes all pairwise convex sums, and unions the results. If $O=\bigcup_i O_i$ and $R=\bigcup_j R_j$, then

$$O\oplus(-R)=\bigcup_{i,j}\left(O_i\oplus(-R_j)\right).$$

Triangulation is easy but may produce many pieces; a coarser convex decomposition usually reduces pairwise sums. The union step matters. Keeping overlapping pieces without constructing an overlay can still support conservative collision tests, but visibility and shortest-path algorithms need a clean boundary with internal edges removed.

Collision Tests Become Point Queries

After preprocessing, configuration $q$ is in collision exactly when the reference point lies in the union of C-obstacles. Point-in-polygon or point-location structures can answer repeated pose queries. A segment from $q_s$ to $q_g$ is a valid straight translation if it remains in $C_{\mathrm{free}}$; equivalently, it must not cross a forbidden boundary or enter a forbidden interior.

That equivalence exposes a useful separation of concerns. Minkowski sums handle robot shape once. A spatial index handles broad-phase candidate obstacles. Robust segment intersection and containment predicates handle the narrow phase. A planner can then reason about points and segments without carrying the full robot through every test.

Contact semantics must be chosen before coding:

• Under a closed-obstacle policy, boundary contact counts as collision, so $C_{\mathrm{free}}$ excludes C-obstacle boundaries.
• Under an open-obstacle policy, tangential contact is permitted, but a path that runs along a boundary needs consistent treatment.
• With required clearance $\delta$, inflate obstacles again by a radius-$\delta$ disk—or by a polygonal approximation if the representation must remain polygonal.

Do not hide this choice inside a floating-point epsilon. Use filtered or exact orientation predicates for topology, define how zero signs are classified, remove zero-length edges, and canonicalize coincident vertices. Conservative numerical inflation can be sensible for safety, but its physical units and tolerance should be explicit.

Translational Planning

For a fixed-orientation polygonal robot, the complete workflow is now concrete:

1. Express the robot relative to a declared reference point and reflect it.
2. Construct $O_i\oplus(-R)$ for every obstacle, decomposing and unioning when needed.
3. Reject start or goal configurations that violate the contact policy.
4. Search for a curve through the complement of the C-obstacle union.
5. Translate the reference-point curve back into robot placements and independently collision-check the result.

A direct start-to-goal segment should be tested first. If it is blocked, one can decompose free space into cells and search their adjacency graph, build a roadmap, or—when seeking Euclidean shortest paths among polygonal obstacles—use the visibility graph developed in Part 22.

The transformation preserves translational path length: the physical robot and its reference point undergo the same displacement. It does not by itself optimize clearance, turning count, or execution dynamics. Those objectives require edge weights or a richer state model.

What Changes When Rotation Is Allowed?

Adding orientation lifts configuration space from a plane to $(x,y,\theta)$. For each fixed $\theta$, a horizontal slice has C-obstacles

$$C_O(\theta)=O\oplus\bigl(-R_\theta\bigr),$$

but these slices change continuously with angle and together form three-dimensional forbidden volumes. A path may escape a blocked translational slice by rotating, yet rotation can also cause a corner to sweep into an obstacle. Planning over a few sampled angles is an approximation unless resolution and interpolation safety are justified.

Exact rotational planning is substantially harder: feature contacts generate algebraic surfaces, free-space topology can change between critical angles, and shortest paths live in a metric mixing distance with rotation. Practical systems often discretize orientation, use sampling-based planning, or build conservative swept volumes. The 2D translational model remains valuable both as an exact special case and as a lower-level primitive.

The Modeling Lesson

Configuration space is a change of coordinates with algorithmic leverage. It converts shape collision into membership, motion into a curve, and a polygonal robot into a point navigating expanded obstacles. Minkowski sums supply the exact expansion; convex decomposition and overlay machinery make nonconvex cases usable; robust boundary semantics keep the mathematical equivalence intact.

The obstacles are now ready for Part 22. Their vertices—including those created by Minkowski sums and unions—will become candidate turning points. Visibility edges will encode collision-free straight translations, and graph search will turn the geometry of $C_{\mathrm{free}}$ into an executable route.