A Knowledge Based GA for Path Planning of Multiple Mobile Robots in Dynamic Environments

In this paper, a knowledge based genetic algorithm (GA) for on-line path planning of multiple mobile robots in dynamic environments is proposed. The proposed GA uses a unique problem representation method to represent 2D robot environments with complex obstacle layouts and obstacles are allowed to be of arbitrary shapes. Correspondingly, an effective evaluation method is developed specially for the proposed GA. The proposed evaluation method is capable of accurately detecting collisions among robot paths and arbitrarily shaped obstacles, and assigns costs that are effective for the proposed GA. Problem-specific GA instead of the standard GAs are used for robot path planning. The proposed knowledge based GA incorporates the domain knowledge into its specialized operators, some of which also combine a local search technique. The effectiveness and efficiency of the proposed genetic algorithm is demonstrated by simulation studies