Genetic Algorithms for Path Planning in a Room with Obstacles

摘要

When an individual enters a room, he/she knows how to plan his/her path to a desired point in the room, avoiding any obstacles on the way. The individual generates a mental map of the room, based on his or her sensing of the environment, and uses this map to find the optimal path. This task is not trivial for a robot. Even if the map of the environment is somehow made available for the robot, the robot is still required to plan its path. The general problem of path planning for autonomous robots is defined as the search for a path which a robot (with specified geometry) has to follow in a described environment, in order to reach a particular position and orientation B, given an initial position and orientation A. Our approach is to use genetic algorithms to search for a viable and preferably the optimal solution to the problem. We use chromosomes that encode the entire path using a set of discrete steps taken in directions encoded by 3-bit genes. This unique approach requires us to make some modifications to the general genetic algorithms technique, such as varying mutation probability and variable chromosome length. Our approach allows us to plan a path for any amount of obstacles and works particularly well in cases where the number of obstacles is small.