Genetic Kinodynamic Velocity Planning for Prioritized Multi-Robot Coordination

Planning collision-free trajectories is a key challenge when operating multiple robots in a shared workspace. Prioritized planning is a well-known technique in which individual paths around static obstacles are planned first and velocity profiles avoiding mutual collisions are calculated in a second step according to a prioritization scheme. With the knowledge, at which distance along the path and at what time conflicts would occur, other robots can be represented as dynamic obstacles in a distance-time-space that can be searched for conflict-free motion plans. We present a novel, genetic algorithm-based approach that overcomes major limitations of known search algorithms for finding suitable velocity profiles. The algorithm uses jerk samples as gene encoding method and converges to optimal results avoiding dynamic obstacles by mutation and natural selection. By providing feasible initial populations, the algorithm is anytime-capable and delivers high-quality results which can be used in frameworks for trajectory coordination and disturbance handling for complex, articulated vehicles.