Multi-robot Path Planning Based on Two-stage Genetic Algorithm Using Direction Ordering Chromosome

Efficient collision-free path planning is crucial in multi-robot systems. This paper presents a path planning strategy for multiple robotsnavigating environments with grid-patterned obstacles, using a genetic algorithm. A novel chromosome structure, termed the direction ordering chromosome, is introduced to represent each robot’s movement directions and idle time. This representation reduces potential path solutions and aids the genetic population in converging on a viable and conflict-free path. The adoption of a two-stage genetic algorithm also enables the discovery of solutions with fewer inter-robot conflicts and reduced unnecessary stoppages. Simulation results showed that the two-stage genetic algorithm finds solutions more efficiently than the single stage genetic algorithm. The proposed algorithm plans paths faster than conflict-based search when numerous robots are involved.