Survey of Robot 3D Path Planning Algorithms <s> Mathematic Model Based Algorithms <s> A unified approach suitable for path planning with moving polyhedral obstacles is presented. The planner views the space-time configuration of free space as disjoint polytopes that represent a time-dependent environment consisting of moving and stationary objects. Each point in the space-time domain is mapped into a unique polytope set. The planner then constructs a family of feasible collision-free trajectories by searching connected polytopes between the start polytope and the goal polytope that satisfy the speed and time constraints. Finally, a near-optimal trajectory is determined by constrained optimization. This approach does not require that obstacles be nonoverlapping or noncolliding. In addition, the obstacle is allowed to move faster than the planned robot. However, the speed of the obstacle must be piecewise-constant. The proposed approach can be easily extended to motion planning in higher dimensional spaces. > <s> BIB001 </s> Survey of Robot 3D Path Planning Algorithms <s> Mathematic Model Based Algorithms <s> We address optimal path planning in three dimensional space for an unmanned aerial vehicle (UAV) in the stationary risk environment. We separate the task into two stage, in the first one we determine the risk optimal 2D path for fixed time problem. Then we solve the series of BVPs (Boundary Value Problems) with different UAV speeds and determine the admissible 2D path, which satisfies the time and risk constraints. In the last step one takes into account the relief along the chosen path and determine the approximated 3D path, which minimizes 2D threat along the path and satisfies other constraints. <s> BIB002
Node based optimal algorithms use grids to represent configuration space; meanwhile this kind of methods assumes the robot as a point and only considers the acceleration and velocity constraints. Thus it is not complete to represent the environments as well as consider system dynamics. Mathematic model based algorithms optimize by describing kinodynamic constraints in combination of polynomial forms. They can model the environment as a time variant system (sometimes even a model and time variant system), which is synchronization to the current location of the robot. Due to the fact that this kind of algorithms can handle dynamics constraints to achieve cost optimum, some researchers regard mathematic optimization methods as trajectory planning method. However, mathematic model based algorithms are proposed to solve the problem of finding a path or trajectory locally or globally BIB002 BIB001 . In order to distinguish from trajectory planning methods, we provide a stronger definition compared to Definition 4.