Survey of Robot 3D Path Planning Algorithms <s> PRM Series. <s> A new motion planning method for robots in static workspaces is presented. This method proceeds in two phases: a learning phase and a query phase. In the learning phase, a probabilistic roadmap is constructed and stored as a graph whose nodes correspond to collision-free configurations and whose edges correspond to feasible paths between these configurations. These paths are computed using a simple and fast local planner. In the query phase, any given start and goal configurations of the robot are connected to two nodes of the roadmap; the roadmap is then searched for a path joining these two nodes. The method is general and easy to implement. It can be applied to virtually any type of holonomic robot. It requires selecting certain parameters (e.g., the duration of the learning phase) whose values depend on the scene, that is the robot and its workspace. But these values turn out to be relatively easy to choose, Increased efficiency can also be achieved by tailoring some components of the method (e.g., the local planner) to the considered robots. In this paper the method is applied to planar articulated robots with many degrees of freedom. Experimental results show that path planning can be done in a fraction of a second on a contemporary workstation (/spl ap/150 MIPS), after learning for relatively short periods of time (a few dozen seconds). <s> BIB001 </s> Survey of Robot 3D Path Planning Algorithms <s> PRM Series. <s> This paper presents a novel randomized motion planner for robots that must achieve a specified goal under kinematic and/or dynamic motion constraints while avoiding collision with moving obstacles with known trajectories. The planner encodes the motion constraints on the robot with a control system and samples the robot's state × time space by picking control inputs at random and integrating its equations of motion. The result is a probabilistic roadmap of sampled state ×time points, called milestones, connected by short admissible trajectories. The planner does not precompute the roadmap; instead, for each planning query, it generates a new roadmap to connect an initial and a goal state×time point. The paper presents a detailed analysis of the planner's convergence rate. It shows that, if the state×time space satisfies a geometric property called expansiveness, then a slightly idealized version of our implemented planner is guaranteed to find a trajectory when one exists, with probability quickly converg... <s> BIB002 </s> Survey of Robot 3D Path Planning Algorithms <s> PRM Series. <s> This paper presents a 3D path planning algorithm for an unmanned aerial vehicle (UAV) in complex environments. In this algorithm, the environments are divided into voxels by octree algorithm. In order to satisfy the safety requirement of the UAV, free space is represented by free voxels, which have enough space margin for the UAV to pass through. A bounding box array is created in the whole 3D space to evaluate the free voxel connectivity. The probabilistic roadmap method (PRM) is improved by random sampling in the bounding box array to ensure a more efficient distribution of roadmap nodes in 3D space. According to the connectivity evaluation, the roadmap is used to plan a feasible path by using A* algorithm. Experimental results indicate that the proposed algorithm is valid in complex 3D environments. <s> BIB003
Unlike RRT, Probabilistic Road Map (PRM) considers different choices for the set of states to which connections are attempted. PRM BIB001 is the first popular multiple-query method for building a road map by using sampling approach. When applied to 3D space, it first defines the configuration space and an obstacle free space free . The method samples a random state in free . Then it tries to connect to nearest neighbors ( -PRM) or connect to states within a -ball region or connect to states under 8 Journal of Control Science and Engineering is the set of edges rand ← th randomly chosen state (5) ( , ) = Explore RRG ( , rand ) (6) End Algorithm 1: Body of RRG. computational burden which is a combination of the above two, that is, -PRM ∩ -ball. It should be declared that each connection is collision-free. After the road map is absolutely formed, a node based search algorithm (Dijkstra, A * , D * , etc.) is used to find the least cost path from initial state to the goal state. The pseudocode of PRM is illustrated in Algorithm 4. In Algorithm 4, PRM adds all the connections which are without collision (from line 4 to line 9). Authors in  first implemented PRM into 3D environment and showed fast exploration performance. However, with the expanding of the exploring graph, the expense on collision checking increases. Amato et al.  put it forward by proposing an obstaclebased nodes generation strategy; at each step the road map candidate points are selected on the obstacle surface. This trick reduces the total processing time by ignoring the useless points in obstacle region. Hsu et al. BIB002 solved the "dynamic threat weak" problem of PRM by introducing a concept of "milestone," that is, state × time which creates a real time graph connecting the initial point and the goal point. It was implemented in ground robots and proved of having quick convergence ability. Yan et al. BIB003 proposed an octree to build 3D grid-structure which weakens the effect of randomness, thus guaranteeing fast searching ability. The Table 1 : Elements of PRM.