0%

Collision Avoidance

1. Goal

Avoid harm

General step:

  1. Create 3D model for robot (from URDF)
  2. Define workspace and trajectory (to detect the potential collision)
  3. Detection
  4. Avoidance
  5. 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

3. Avoidance