Survey of Robot 3D Path Planning Algorithms <s> Mathematic Model Based Algorithms: Elements and <s> This paper presents a novel algorithm for path planning of mobile robots in known 3D environments using Binary Integer Programming (BIP). In this approach the problem of path planning is formulated as a BIP with variables taken from 3D Delaunay Triangulation of the Free Configuration Space and solved to obtain an optimal channel made of connected tetrahedrons. The 3D channel is then partitioned into convex fragments which are used to build safe and short paths within from Start to Goal. The algorithm is simple, complete, does not suffer from local minima, and is applicable to different workspaces with convex and concave polyhedral obstacles. The noticeable feature of this algorithm is that it is simply extendable to n-D Configuration spaces. Keywords—3D C-space, Binary Integer Programming (BIP), Delaunay Tessellation, Robot Motion Planning. <s> BIB001 </s> Survey of Robot 3D Path Planning Algorithms <s> Mathematic Model Based Algorithms: Elements and <s> This is the second part of a series papers on modeling and path planning of the City-Climber robot. This paper presents a path planning method for the City-Climber robot using mixed integer linear programming (MILP) in 3D building environments that consist of objects with primitive geometrical shapes. In order to use MILP to solve obstacle avoidance problems, we first simplify and decouple the robot dynamic model by introducing a restricting admissible control. The decoupled model and obstacle can be rewritten as a linear program with mixed integer linear constraints that account for the collision avoidance. A key benefit of this approach is that the path optimization can be readily solved using the AMPL and CPLEX optimization software with a Matlab interface. Simulation results show that the framework of MILP is well suited for path planning and obstacle avoidance problems for the wall-climbing robot in 3D environments. <s> BIB002 </s> Survey of Robot 3D Path Planning Algorithms <s> Mathematic Model Based Algorithms: Elements and <s> A flatness-based flight trajectory planning/replanning strategy is proposed for a quadrotor unmanned aerial vehicle (UAV). In the nominal situation (fault-free case), the objective is to drive the system from an initial position to a final one without hitting the actuator constraints while minimizing the total time of the mission or minimizing the total energy spent. When actuator faults occur, fault-tolerant control (FTC) is combined with trajectory replanning to change the reference trajectory in function of the remaining resources in the system. The approach employs differential flatness to express the control inputs to be applied in the function of the desired trajectories and formulates the trajectory planning/replanning problem as a constrained optimization problem. <s> BIB003
Analysis. Mathematic model based algorithms include linear algorithms and optimal control. These methods model the environment (kinematic constraints) as well as the system (dynamic) and then bound the cost function with all the kinematic and dynamic constraints bounds which are inequalities or equations to achieve an optimal solution. The elements of mathematic model based algorithms are presented in Figure 5 . Where flatness based method was first proposed by Chamseddine et al. BIB003 , this method employs differential flatness to ensure control flatness along the reference path; it linearizes the nonlinear kinodynamic constraints to form a rather simple form. MILP is Mixed-Integer Linear Programming BIB002 which has a strong modeling capability to describe almost all the information. BIP is Binary Linear Programming BIB001 ; it is a special case of linear programming where the variables have only 0-1 integer value. 