Crowd Simulations

Demo of motion planning using dynamic A-star, path smoothing, and TTC (time-to-collision obstacle avoidance) on cylindrical agents:


  • Dynamic A-star
    • Path recalculated on over 60 agents every 2 seconds (agent paths highlighted in green)
    • Minkowski sum used to plot around obstacles and generate PRM (probabilistic roadmap)
    • Agents can be easily added and removed from the planning during run-time
  • Path smoothing
    • Agents move towards furthest possible point in path
    • Leads to less robotic movements
  • TTC (time to collision)
    • Agents avoid each other based on inverse power law (1/ttc ^ 2). Force-based agent interaction
    • Agents “sense” when they will collide with each other and move to avoid


Things to fix

  • Add barriers (walls borders) to TTC model so agents can avoid bumping into them
  • Agents “pop” away from each other
    • Tune time to collision equation to avoid over-increasing the magnitude of the force pushing agents away from each other
      • Set maximum force magnitude
      • Adjust power law curve to be less steep


  • Improve nearest neighbor search using BVH (bounding volume hierarchy) instead of brute force distance check

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s