Path planning for mobile robots using genetic algorithm and probabilistic roadmap

摘要

Mobile robots have been employed extensively in various environments which involve automation and remote monitoring. In order to perform their tasks successfully, navigation from one point to another must be done while avoiding obstacles present in the area. The aim of this study is to demonstrate the efficacy of two approaches in path planning, specifically, probabilistic roadmap (PRM) and genetic algorithm (GA). Two maps, one simple and one complex, were used to compare their performances. In PRM, a map was initially loaded and followed by identifying the number of nodes. Then, initial and final positions were defined. The algorithm, then, generated a network of possible connections of nodes between the initial and final positions. Finally, the algorithm searched this network of connected nodes to return a collision-free path. In GA, a map was also initially loaded followed by selecting the GA parameters. These GA parameters were subjected to explorations as to which set of values will fit the problem. Then, initial and final positions were also defined. Associated cost included the distance or the sum of segments for each of the generated path. Penalties were introduced whenever the generated path involved an obstacle. Results show that both approaches navigated in a collision-free path from the set initial position to the final position within the given environment or map. However, there were observed advantages and disadvantages of each method. GA produces smoother paths which contributes to the ease of navigation of the mobile robots but consumes more processing time which makes it difficult to implement in realtime navigation. On the other hand, PRM produces the possible path in a much lesser amount of time which makes it applicable for more reactive situations but sacrifices smoothness of navigation. The presented advantages and disadvantages of the two approaches show that it is important to select the proper algorithm for path planning suitable for a particular application.