| Avoidance obstacle path planning problem is able to be stated as follows: in obstacle environment, based on a certain evaluation criterion(such as the shortest length of path, the shortest time of moving, the minimal consuming of energy, and so on), from start point to destination point, plans a optimal ( or sub-optimal ) collision free path. It has universal applications in many fields, such as robotics, VLSI's design, GIS, etc. The main contents relate to many subjects, for example environment representing, planning method, path searching and artificial intelligence. Researchers are always caring for and thinking much of the study of high-powered algorithm for avoidance obstacle path planning. Through exploration and research in many aspects, some fruits are obtained, but there are plenty of problems needed to lucubrate.Bases on the model of visibility graph, uses the methods of "intelligent calculation", "two level dynamic planning", and "the minimal arbitrary quadrangle encasing box", etc., studies the algorithm for planning path of avoidance obstacle at two levels of theory and application. The obtained results can not only been applied to the design and implementation of algorithm for avoidance obstacle path planning, but also been used to solve the problems of computational geometry. So, this study has the important theory significance and the practical application value.The visibility graph is used to represent environment and construct the model of environment in this paper, the optimal path problem of avoidance obstacle is transformed into the problem of shortest path through visibility line from start point to destination point, this is the base of the research.The difference of GT's algorithm for TSP is carefully analyzed, compares TSP with avoidance obstacle path planning problem, introduces "gene base" into the problem, mends the GT's algorithm, and successfully uses it to solve the avoidance obstacle path planning problem. Additionally, mathematics formula about the relation of problem size and initial population size is presented; during selecting the initial chromosome, invalid and sightless selection is avoided by using convex point method. All these measures improve the evolving efficiency.An analysis of the shortest path problem between two arbitrary points in the obstacle environment is also submitted. This paper presents an algorithm entitled as "A Two-level Dynamic Shortest Path Planning Algorithm to Obstacle Avoidance", which does not destroy the integrity information of obstacle, and is different from the traditional Floyed Algorithm. The algorithm essentially reflects unification of global optimization and local optimization in this very complex environment. In addition, a new algorithm is constructed to solve cost matrix of graph, the course of that algorithm is more intuitive and easier to understand. Correctness of the algorithm's result is proved through theoretic testifying and experimental computing. Time complexity of algorithm presented in this paper is O(n3) (n is the number of obstacles' vertices, including starting point and destination point), same as Floyed Algorithm's time complexity, but ideas of the algorithm in this paper is innovative.In order to reduce algorithm's time complexity of avoidance obstacle path planning, one way is to study new more effective algorithm, and the other effective way is to decrease vertices on boundary of obstacles on the premise of guaranteeing the precision of path planning. Obstacle is usually represented as close contour line (i.e. convex polygon), constructing minimal area encasing box besieging the close contour is one effective method to solve the problem. Encasing box problem is a basal problem of computational geometry. Besides being applied in path planning, encasing box problem has broad application in collision detecting, real time roaming, visual region clipping, etc.Currently, method presented by H.Freeman and P.Shapira[1975,in New York Univesity] is used to obtain minimal area rectangle encasing b...
|
PDF Full Text Request