# Diversity Maintenance for Efficient Robot Path Planning  
[PERSON]  
Path planning can generally be classified based on the nature of the environment as static or dynamic. In the case of the static environment, the layout, once perceived by the robot remains unchanged. Dynamic environments include movable objects i.e., other robots. According to the algorithm used for planning, the planner can either be local--meaning sensor-based and reactive, or global--meaning map-based and planning the trajectory from the initial to the final position at once. Based on the completeness, planning can be classified either as complete or heuristic. In the case of complete planning, the algorithm will always find a path in finite time if the path exists, or report that no feasible path exists in finite time. These algorithms are preferred for the systems with a low number of degrees of freedom over the heuristics algorithms [2; 3; 4; 5; 6]. In the case of a 3D problem considered in this paper, both the trajectory and the robot's body have to avoid obstacles present in the environment and thus checked for collisions. This makes planning significantly more complex when compared to simple point-wise planning. It is known that for similar problems, population-based heuristic planning methods, i.e., swarm and evolutionary approaches are successfully utilized to find high-quality solutions in acceptable time [7; 8; 9; 10]. It is also proven that the path planning problem is NP-complete, with the complexity of tasks increasing exponentially with the DOF number [11]. This is an additional motivation of exploring alternative methods to path planning, seeking for high quality (instead of optimal) solutions in limited time. The majority of papers utilizing instances of population-based heuristic optimization for path planning deal with the case of a mobile robot, presented as a point in the space, aiming to find a set of going-through nodes in 2D space [12; 13; 14]. A more realistic scenario is using a 3D model of the robot, with movement in an environment containing obstacles of different shapes and positions. In this case, a simple solution of going-through nodes does not suffice, because the body of the robot plays a critical role in checking for collision-free motion [15; 16]. In this paper, an evolutionary algorithm-based path planner is proposed to solve the problem of path planning both for a simplified model of a mobile robot and a realistic 3 DOF stationary robot. The former will be presented as a point in space, while the later will be actual RRR model including links and presence of obstacles. It is shown that evolutionary algorithms (EA) are susceptible to getting trapped in suboptimal regions of the search space [17]. That means that the best individuals in the population are evolved fitter during the optimization process, but there is still space for improvement, that has to be utilized through the additional exploration of the search space. This usually happens when a local optimum has a large basin of attraction, thus forming a misleading region in the search space that can influence the whole population by trapping it in this suboptimal region. To alleviate this, diversity maintenance methods have been proposed to ensure that potential solutions (that make up the population) remain diverse. This way, EA's are forcing some of the individuals to explore different regions of the search space with the motivation of eventually finding better optima, or in the best case, the global optimum. Diversity maintenance (DM) generally can be either implicit or explicit [18], with the latter being of interest in this paper. Explicit DM schemes are based on the idea of forcing the population to maintain different niches when doing selection or replacement. Two of the most common forms are fitness sharing--in which genotypically similar individuals share fitness values with other individuals that are considered similar to them using appropriate metrics.