Non-smooth environment modeling and global path planning for mobile robots

Abstract

An Approximate Voronoi Boundary Network is constructed as the environmental model by way of enlarging the obstacle raster. The connectivity of the path network under complex environment is ensured through building the second order Approximate Voronoi Boundary Network after adding virtual obstacles at joint-close grids. This method embodies the network structure of the free area of environment with less nodes, so the complexity of path planning problem is reduced largely. An optimized path for mobile robot under complex environment is obtained through the Genetic Algorithm based on the elitist rule and re-optimized by using the path-tightening method. Since the elitist one has the only authority of crossover, the management of one group becomes simple, which makes for obtaining the optimized path quickly. The Approximate Voronoi Boundary Network has a good tolerance to the imprecise a priori information and the noises of sensors under complex environment. Especially it is robust in dealing with the local or partial changes, so a small quantity of dynamic obstacles is difficult to alter the overall character of its connectivity, which means that it can also be adopted in dynamic environment by fusing the local path planning.

Keywords

non-smooth modeling / Voronoi diagram / path planning / genetic algorithm

References

[1] WuLi-juan, XuXin-he. Design of an obstacle-avoidance strategy based on genetic algorithms in robot soccer competition[J]. Robot, 2001, 23(2): 142-145(in Chinese)

[2] Janet JasonA, LuoR C, KayM G. Autonomous mobile robot global motion planning and geometric beacon collection using traversability vectors[J]. IEEE Transactions on Robotics and Automation, 1997, 13(1): 132-140

[3] JiangKai-chun, SeneviratneL D, EarlesP W E. A shortest path based path planning algorithm for non-holonomic mobile robots[J]. Journal of Intelligent and Robotics Systems, 1999, 24: 347-366

[4] ZhouMing, SunShu-dong, PengYan-wu. A centralized coordinated path planning method based on genetic algorithm for multiple mobile robots[J]. Acta Aeronautica et Astronautica Sinica, 2000, 21(2): 146-149(in Chinese)

[5] CannyJ F, DonaldB R. Simplified Voronoi diagrams [J]. Discrete and Computational Geometry, 1988, 24(3): 219-236

[6] OsamuTakahashi, SchillingR J. Motion planning in a plane using generalized Voronoi diagrams[J]. IEEE Transactions on Robotics and Automation, 1989, 5(2): 143-150

[7] ChosetHowie, BurdickJoel. Sensor-based exploration: the hierarchical generalized Voronoi graph [J]. International Journal of Robotics Research, 2000, 19(2): 96-125

[8] FordL R, FulkersonD RFlows in Networks[M], 1962, Princeton, Princeton University Press

[9] PreparataF, ShamosMComputational Geometry: An Introduction [M], 1985, New York, Springer Verlag