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.