Collision checking: test the motion between endpoints

Two clear endpoints can hide a collision halfway through a robot's motion. Checking the start and finish leaves the positions between them untested.

For one simple geometry, we can check the entire motion with a closest-point calculation. This lesson derives that test and compares it with sampled checks and bounding boxes.

Specify the shapes and contact rule

Use a disk robot of radius ρ = 0.25 m and a stationary circular obstacle of radius R = 0.5 m. The obstacle center is c = (0, 0). Both shapes live in the same plane, with world x right and y up.

At robot center p, define signed clearance:

Positive clearance means separation. Zero means contact, and negative clearance means overlap. We count contact as collision throughout this lesson.

A static check evaluates this expression at one center position. A motion check asks whether it ever becomes nonpositive along the chosen path. The OMPL documentation makes the same distinction between checking a state and validating a motion between states.

Account for the robot's radius

The disks touch when their center distance equals the sum of their radii. This lets us check the robot center against an inflated obstacle of radius R + ρ = 0.75 m.

Every center inside or on that larger disk puts the physical robot in collision. The obstacle itself still has radius 0.5 m. The extra 0.25 m accounts for the robot's size.

For a translating body, LaValle derives the forbidden translations using the obstacle and the reflected robot shape. A disk has the same shape after reflection, so its radius adds directly to the obstacle radius here. The configuration-space lesson develops this change from whole shapes to forbidden configuration points.

Find the closest point along the segment

Let a and b be the start and end centers. Write the straight path as p(u) = a + u(b − a) for 0 ≤ u ≤ 1. The parameter u describes progress along the segment; it carries no time unit.

Set d = b − a. Minimizing clearance is equivalent to minimizing the distance from c to this segment. For d ≠ 0, projection onto the infinite line gives:

The projection calculation removes the component perpendicular to the line. Clamping handles the segment ends: if the perpendicular foot lies beyond an endpoint, that endpoint supplies the minimum.

If a = b, the robot stays at one center. Use p_near = a and conventionally set τ = 0; division by d · d would be undefined.

The continuous result follows from one value:

This is an exact geometric test for a disk translating along this straight segment against this fixed circular obstacle. The implementation evaluates its formulas in floating point.

Catch a collision between clear endpoints

Take a = (−2, 0) m and b = (2, 0) m. Both endpoints have clearance 2 − 0.75 = 1.25 m.

Here d = (4, 0) m. The projection gives u₀ = 8/16 = 0.5, which already lies in the segment interval. Thus p_near = (0, 0) m and g_min = −0.75 m.

The robot crosses the obstacle despite its clear endpoints. Its first contact occurs when the center reaches x = −0.75 m, at u = 0.3125. The closest fraction τ = 0.5 identifies the minimum distance, not the first contact.

A collision checker can answer whether contact occurs without computing its first occurrence. A dynamics simulation that resolves impact would need additional contact and motion information.

Show what a sample set can miss

With N uniformly spaced sample points, including both endpoints, use uᵢ = i/(N − 1) for i = 0, …, N − 1. N points create N − 1 intervals between them.

For the worked path, N = 2 checks only the endpoints and misses the collision. N = 3 includes u = 0.5 and catches it. The sampled minimum clearance is always at least the true minimum because the sample set covers only selected path positions.

A different path can still slip between three samples. Let a = (−1.8, 0.74) m and b = (2.2, 0.74) m. The closest center is (0, 0.74) m at τ = 0.45, giving g_min = −0.01 m.

With N = 3, the middle center is (0.2, 0.74) m. Its clearance is approximately 0.016551 m, and the other samples are farther away. All three samples report separation even though the full segment collides.

Choosing N = 21 includes u = 0.45 and detects this example. A finite collection of clear samples alone does not establish that the untested intervals are clear. OMPL's motion-validation discussion explains how a coarse resolution can miss invalid states and why finer checking adds work.

Compare the samples with the whole motion

Continuous motion check

Do the samples miss a collision?

A disk of radius 0.25 m follows a straight center segment past an obstacle of radius 0.5 m. The dashed circle expands the obstacle to radius 0.75 m for checking the robot center.

Collision path presetThrough obstacleTangent contactClear passOverlapping boxes, clear pathStationary overlapBetween sample points

Sample points including endpoints

2 points

Current path progress u

0.00

Sample points use u = i/(N − 1), including both endpoints. Current progress moves only the displayed disk. Every clearance check still uses the whole selected segment or the stated sample set.

Distance check in world axes (m)

Broad-phase boxes in world axes (m)

• Gray solid circle: physical obstacle; blue dashed circle: inflated obstacle
• Amber disk: robot at current progress; solid blue line: center path
• Open circle: clear sample; cross: colliding sample; open diamond: closest center
• Dashed blue rectangle: swept robot bounds; solid black square: obstacle bounds

Path start (m)

(-2.000, 0.000)

Path end (m)

(2.000, 0.000)

Current center (m)

(-2.000, 0.000)

Current clearance (m)

1.250000

Endpoint minimum clearance (m)

1.250000

Sample points (count)

2

Sampled minimum clearance (m)

1.250000

Sample result

No sampled collision

Closest path fraction τ

0.500000

Closest center (m)

(0.000, 0.000)

Swept minimum clearance (m)

-0.750000

Swept result

Collision

Broad-phase result

Candidate pair

Swept result: collision. The sampled centers miss the collision between them. Current clearance: 1.250000 m.

Clearance is center distance minus 0.75 m. Negative values mean overlap; zero means contact. The numerical decision treats clearance at most 10⁻¹⁰ m as collision. This roundoff tolerance is separate from a physical safety margin or uncertainty model.

At a stationary preset, all N sample parameters describe the same center, so their markers overlap. The closest fraction is conventionally zero. A diamond can coincide with a sample or the current center.

Reset collision experiment

Start with two sample points. Add the midpoint by increasing the count to three. The sampled result changes while the swept minimum stays fixed.

Choose Between sample points with three samples, then increase to 21. Move current progress to inspect different robot positions. This control changes the displayed disk and its static clearance; it does not change the path or its continuous result.

Tangent contact has zero swept clearance and counts as collision. Clear pass has 0.25 m of minimum clearance. Stationary overlap checks the same colliding center for every progress value and sample parameter.

Separate bounding-box candidates from collisions

For many object pairs, a broad phase can eliminate clearly separated candidates before detailed geometry checks. An axis-aligned bounding box, or AABB, records a minimum and maximum coordinate along each axis.

Our swept robot box takes the coordinate bounds of the center segment and expands each side by ρ. It contains the entire moving disk at every progress value. The obstacle box extends R from its center along both axes.

If these boxes are disjoint, the enclosed shapes cannot intersect. Overlap keeps a candidate pair for the narrow phase, which performs the segment-distance calculation here. The Flexible Collision Library documents broad-phase managers alongside shape-level collision, distance and continuous-motion queries.

The Overlapping boxes, clear path preset runs from (0.7, 1.2) to (1.2, 0.7) m. Its swept robot box spans [0.45, 1.45] on each axis, overlapping the obstacle box [−0.5, 0.5]. Yet the closest center is (0.95, 0.95) m, with clearance approximately 0.593503 m.

The boxes include empty corner space, causing this false positive. Keeping the pair for a narrower check is the intended broad-phase behavior.

State what this result covers

The numerical contact rule classifies clearance at most 10⁻¹⁰ m as collision. It includes a tiny positive band to handle roundoff near tangency. The broad-phase comparisons use the same tolerance so they cannot reject that band before the narrow check.

A physical clearance margin has a different purpose. If a design requires margin m, check against R + ρ + m. Choosing m requires information about geometry, sensing and tracking errors; this lesson's roundoff constant supplies none of that information.

Real robots often use geometric primitives, convex parts or triangle meshes for collision models. Bounding-volume hierarchies group geometry so a query can discard separated regions. The right narrow-phase method depends on the shapes and the motion model; a library's supported query types do not make every combination interchangeable.

For an articulated arm, a straight line in joint coordinates generally moves its links along curved paths. Checking the straight chord between two tool positions cannot validate all link motion. A curved disk path or moving obstacle also requires a method that covers that actual motion.

A reachable workspace position can still require a blocked route. Rapidly exploring random trees use motion checks while growing candidate paths around obstacles. A learned policy's proposed waypoints need checks for the robot body and the connecting motion. With fixed obstacles, changing only the timing of the same geometric path leaves its collision status unchanged, although it changes speed and acceleration demands.

Reproduce the continuous check in Python

This standard-library example checks the worked crossing, tangency and box false positive. Its final two rows compare three samples with 21 on the offset crossing. Each row reports the minimum over the whole segment independently of sampling.

from math import hypot

RHO, R, TOL = 0.25, 0.5, 1e-10


def check(a, b, count):
    d = (b[0] - a[0], b[1] - a[1])
    length2 = d[0] ** 2 + d[1] ** 2
    tau = 0.0 if length2 == 0 else max(
        0.0, min(1.0, -(a[0] * d[0] + a[1] * d[1]) / length2))

    def point(u):
        return (a[0] + u * d[0], a[1] + u * d[1])

    def clearance(p):
        return hypot(*p) - (R + RHO)

    closest = point(tau)
    swept = clearance(closest)
    sampled = min(clearance(point(i / (count - 1))) for i in range(count))
    lower = [min(a[j], b[j]) - RHO for j in (0, 1)]
    upper = [max(a[j], b[j]) + RHO for j in (0, 1)]
    candidate = all(lower[j] <= R + TOL and -R <= upper[j] + TOL
                    for j in (0, 1))
    assert not (swept <= TOL and not candidate)
    return tau, swept, sampled, candidate


cases = [
    ("crossing", (-2, 0), (2, 0), 2),
    ("crossing", (-2, 0), (2, 0), 3),
    ("tangent", (-2, 0.75), (2, 0.75), 2),
    ("corner", (0.7, 1.2), (1.2, 0.7), 2),
    ("stationary", (0, 0), (0, 0), 2),
    ("between", (-1.8, 0.74), (2.2, 0.74), 3),
    ("between", (-1.8, 0.74), (2.2, 0.74), 21),
]
for name, a, b, count in cases:
    tau, swept, sampled, candidate = check(a, b, count)
    print(f"{name}: N={count}, tau={tau:.6f}, swept={swept:.6f}, "
          f"sampled={sampled:.6f}, candidate={candidate}")

Expected output:

crossing: N=2, tau=0.500000, swept=-0.750000, sampled=1.250000, candidate=True
crossing: N=3, tau=0.500000, swept=-0.750000, sampled=-0.750000, candidate=True
tangent: N=2, tau=0.500000, swept=0.000000, sampled=1.386001, candidate=True
corner: N=2, tau=0.500000, swept=0.593503, sampled=0.639244, candidate=True
stationary: N=2, tau=0.000000, swept=-0.750000, sampled=-0.750000, candidate=True
between: N=3, tau=0.450000, swept=-0.010000, sampled=0.016551, candidate=True
between: N=21, tau=0.450000, swept=-0.010000, sampled=-0.010000, candidate=True

Try it yourself

1. Change the robot size. Keep the obstacle radius at 0.5 m and move the robot center from (−2, 1) to (2, 1) m. What is the minimum clearance for robot radius 0.25 m? What happens if its radius increases to 0.5 m?

Show the radius and contact solution

The closest center is (0, 1) m at τ = 0.5. With robot radius 0.25 m, the combined radius is 0.75 m, so the minimum clearance is 1 − 0.75 = 0.25 m.

At robot radius 0.5 m, the combined radius becomes 1 m and the path is tangent. Zero clearance counts as collision. Positive clearance requires a robot radius strictly below 0.5 m in exact geometry; the numerical implementation also applies its small tolerance band.

2. Clamp the projection. Use the original radii and a segment from a = (1, 1) to b = (2, 1) m. Find the unconstrained closest fraction, the clamped fraction and minimum clearance. Explain why using the infinite line's distance would give the wrong segment clearance.

Show the endpoint projection solution

Here d = (1, 0) m and c − a = (−1, −1) m. The unconstrained fraction is u₀ = −1, so clamping gives τ = 0 and closest center (1, 1) m.

The minimum clearance is √2 − 0.75 ≈ 0.664214 m. The infinite horizontal line comes closest at (0, 1), outside the segment, and would report only 0.25 m. Both tests find separation in this case, but only the clamped calculation gives the segment's actual minimum.

Sources and further study

• Steven LaValle, Planning Algorithms: the translational C-space obstacle. The obstacle and reflected robot shape define forbidden translations through a Minkowski sum.
• OMPL: State Validity Checking. State checks, motion validation and the risk of missing invalid states between discrete samples.
• Flexible Collision Library: project documentation. Geometry types, collision and distance queries, continuous checks and broad-phase managers.