Dynamic Safety Search (DSS) is a multi-agent sampling-based dynamic path planning method. In contrast to positional planners (eg. ERRT) it considers each agent kinematic parameters, and current velocities in planning.

DSS is proposed by Bruce in 2006, and is an improvement over the well-known Dynamic Window method. The main improvements are:

  • Replacing grid-base sampling with random sampling
  • Being multi-agent, meaning it can generate a safe path for any number of agents

The set of possible accelerations used in DSS calculation is also recalculated, using our actual robot model which is based on BLDC motor equation. The author proposed that acceleration space plot of the set is likely to be a partial ellipse, but based on our computations, it actually is a diamond:

In our AI software, the output of the ERRT planner is fed into the motion planner, and an acceleration vector a is generated for the robot. Then this vector is passed to the DSS as the input, and a safe acceleration vector f is generated.

On the implementation side, the DSS algorithm generates the result for all robots simultaneously, so it cannot be parallelized. But because of its anytime basis, it can be terminated whenever required, and it will give the best found result. In our experiments, it almost always gives good enough results in the given 0.2 mS time.

Leave a Reply

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

WordPress.com Logo

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

Facebook photo

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

Connecting to %s