A Rapid Path Planning Algorithm Based on the Bilateral Convex-Hull Expanding Model

There are the problems of low efficiency and losing the shortest path in path planning in the circumstance of obstacles. In addition, the boundary of convex-hull is characterized by its high efficiency in constructing the spatial network model. Enlightened by this, combining the relative position of paths and obstacles, a path planning method based on the bilateral convex-hull expanding model are proposed. Combining the high efficiency in the algorithm of the convex-hull boundary and the veracity in the route binary tree algorithm, a rapid path planning algorithm based on bilateral convex-hull expanding model is proposed. First, according to the relative position of path and obstacle, the obstacles that are relative to the path are grouped into the left obstacles and right obstacles. Then the path and its left and right obstacles are used to obtain its boundary of the convex-hull, which is regarded as the new path. Finally, the spatial network model are constructed by paths, and Dijkstra algorithm is used to solve the shortest path.Under the condition of ArcGIS Engine, three sets of comparative experiments are set up to analyze and compare the algorithm of convex-hull boundary, route binary tree and our proposed algorithm, respectively in terms of the accuracy of the spatial network model and the efficiency of the spatial network model construction. The result of simulation experiments show that our proposed algorithm is characterized by high efficiency in constructing the special network model and maintaining shortest paths.