Reduction of Visibility Graph on Global Path Planning for Mobile Robot

Abstract

Visibility graph is a kind of conventional method in path planning for mobile robot. Complexity degree of visibility graph increases rapidly with more obstacles appearing. If the number of vertexes of obstacles is N, the computing time will be O(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> ). In this paper, the concept of completely visible obstacles and related theorems are presented, the resulting reduced visibility graph are applied to the global path planning of mobile robot combing with dynamic visibility graph and improves quality of real time.