1. Goal
Avoid harm
General step:
- Create 3D model for robot (from URDF)
- Define workspace and trajectory (to detect the potential collision)
- Detection
- Avoidance
- Test
2. Detection
Separating Axis Theorem (SAT): Simple but computationally expensive
- Pros:
- Suitable for detecting collisions between convex polyhedra.
- Can handle objects of arbitrary shapes and sizes.
- Relatively easy to implement.
- Cons:
- May produce false negatives if the objects are not convex or have concavities.
- Can be computationally expensive for complex shapes with many faces or vertices.
Gilbert-Johnson-Keerthi (GJK) algorithm:
- Pros:
- Can detect the intersection between any two convex objects.
- Efficient and robust algorithm.
- Can handle objects of arbitrary shapes and sizes.
- Cons:
- Can be more difficult to implement than some other methods.
- May produce false negatives if the objects are not convex or have concavities.
- Requires an initial guess for the closest points between the two shapes.
Minkowski Portal Refinement (MPR) algorithm: Non-convex, computation expensive
- Pros:
- Can detect collisions between non-convex objects.
- Efficient and robust algorithm.
- Can handle objects of arbitrary shapes and sizes.
- Cons:
- More computationally expensive than some other methods.
- Can be more difficult to implement than some other methods.
- May produce false negatives if the objects have narrow tunnels or thin gaps.
Bounding Volume Hierarchy (BVH): Simple, can handle complex objects, but less accurate
- Pros:
- Can accelerate collision detection for complex objects.
- Efficient and easy to implement.
- Can handle objects of arbitrary shapes and sizes.
- Cons:
- Can be less accurate than some other methods.
- May produce false positives if the bounding volumes are too large or not well-optimized.
2.1. False Negative
Fails to detect a collision that actually exists.
Cause
- Insufficient solution
- Inaccurate collision model
- Numerical errors
- Algorithm limitation
You can never eliminate it
2.2. Robot Arm
- For convex shape, SAT and GJK are good choices
- SAT more simple
- GJK more robust
- For non-convex shapes or has narrow tunnels, MPR is good choice
- If has complex shapes with many faces or vertices, BVH is a good choice