Path Planning Using Generalized Voronoi Graph (GVG) for Car-like Mobile Robot

Abstract

Often autonomous mobile robots operate in unknown environment is a hard problem, especially for car-like mobile robot. They require two necessary steps: one is the safe execution for a collision free motion, and the other one is a path to a goal position. This thesis addresses a navigation method for a car-like mobile robot that moves in unknown environment. Thus a novel method bases on conventional Generalized Voronoi Graph(GVG) is proposed, that enables a car-like robot to generate a path from a start configuration to a target position without collision in an bounded environment containing only convex obstacles. We are only considering 2-D space, and in 2-D space GVG is a roadmap of the environment. The advantage of our approach is it enables the robot generate the GVG structure of in unknown environment, and in the process of generation we can arrive any point in the environment. Conventional GVG was defined for holonomic system and it cannot be followed exactly by a nonholonomic robot. The proposed algorithm enables the car-like robot generate the GVG structure, access the GVG and trace the GVG with the nonholonomic constraint until it reaches the point to depart. After it reaches this point, it follows nonholonomic path to the goal. The advantage of this algorithm is that the car-like robot can generate a collision free path between any two points in unknown environment, and the sensor only need to detect the closest point on obstacles.