Three-Dimensional Obstacle Space Based On Convex Hull Model Path Planning Research

With the deepening of the research on unmanned aerial vehicle and intelligent robot,the path planning problem of robot and aircraft in three-dimensional space has gradually appeared in the perspective of researchers at home and abroad.The focus of this kind of problem is to extend the path planning from two-dimensional space to three-dimensional space and even three-dimensional obstacle space.Obstacle collision detection is the basis of path planning in 3d obstacle space.Most of the existing collision detection studies are based on spatial models with high spatial redundancy such as AABB model and OBB model,which are difficult to model the holes formed by multiple obstacles and only applicable to single obstacles.Heuristic algorithms are widely used in 3d path planning.The traditional heuristic algorithm gives priority to solving the shortest path and lacks consideration for the situation that the shortest path will become congested if large-scale robots or u AVs choose the shortest path at the same time.In view of the above problems,this paper has done the following work.Firstly,the spatial data models commonly used in spatial database are analyzed,and the advantages and disadvantages of each model are discussed in detail.The basic principles and current research directions of collision detection are described,and the advantages and disadvantages of collision detection methods commonly used in 2d and 3D space in 3D obstacle space are analyzed.The concept of path planning in three-dimensional space is defined,and the different research directions of path planning in three-dimensional space are studied and discussed.Through the above research,lay the theoretical foundation of this paper.Secondly,the convex shell model of three-dimensional space is selected as the spatial model of obstacles in the three-dimensional obstacle space in this paper.It is necessary to pay attention to the safety of the object when moving,so this paper adopts the sphere model to represent the object.The traditional collision detection can only detect the collision relationship between two objects.The GJK-R algorithm proposed in this paper can introduce the radius of the target object into the collision detection process,so that the collision detection of two objects can be transformed into the collision detection and passability detection of three objects.The Divide Objects algorithm proposed in this paper can deal with non-convex polyhedron holes formed by collision of multiple obstacles.Based on the above two algorithms,this paper proposes an obstacle classification algorithm,which divides obstacles into independent obstacles,joint obstacles and passable obstacles based on the passability of the target object between obstacles.Based on obstacle classification and passability distance algorithm,this paper proposes a k-nearest neighbor query algorithm for 3d obstacle space passability based on collision detection,which can solve the problem that the existing obstacle space nearest neighbor query does not consider object passability to a certain extent.Thirdly,aiming at the problem of path finding in 3d obstacle space path planning,this paper proposes a space generation algorithm for solving 3d obstacle space,which generates path nodes of 3D obstacle space according to the midpoint of the shortest distance between adjacent independent obstacles and connects the nodes to form an undirected graph.In this solution space,the path of three-dimensional space is represented by undirected graph,which simplifies the three-dimensional obstacle space.Aiming AT the problem of shortest path congestion caused by a large number of targets moving AT the same time,the AT algorithm is proposed by combining historical trajectory data with heuristic algorithm.The algorithm is superior to the traditional heuristic algorithm in the optimal path passing time.Finally,experiments are constructed according to the research content.Based on the experimental variables such as data size and data distribution,the obstacle classification algorithm based on GJK-R algorithm is compared with the traditional collision detection algorithm.It is proved that GJK-R algorithm can significantly reduce the density of obstacles in 3d obstacle space.Compared with visual K-nearest neighbor query,the practicability of k-nearest neighbor query in 3d obstacle space is proved.Through the comparison between AT and A* algorithm in the same solution space,it is proved that AT algorithm has A significant advantage in the passage time of path generation.