Survey of Robot 3D Path Planning Algorithms <s> Linear Algorithms. <s> OPTRAGEN is a MATLAB toolbox for numerically solving optimal control problems. OPTRAGEN translates optimal control problems to nonlinear programming problems. The transcription of optimal control problem (OCP) to nonlinear programming (NLP) problem is done by parameterizing trajectories as splines. The output of the transcription is a cost function and a constraint function that can be interfaced with any commercially available nonlinear programming solver. OPTRAGEN can be considered to be a parser that translates optimal control problems to nonlinear programming problems, and is not dependent on any nonlinear programming solver <s> BIB001 </s> Survey of Robot 3D Path Planning Algorithms <s> Linear Algorithms. <s> This paper presents an improved path planner formulation using mixed-integer linear programming (MILP) to solve a receding horizon optimization problem in real-time for unmanned aerial vehicles (UAVs). This paper uses variable sized time-steps with linear interpolation points and horizon minimization techniques to enhance the capability of the online path planner. Flight tests on an unique indoor quadrotor testbed demonstrate that MILP can be reliably used in real-time. A multi-vehicle test is also presented to demonstrate non-communicating de-confliction trajectory planning using MILP. <s> BIB002 </s> Survey of Robot 3D Path Planning Algorithms <s> Linear Algorithms. <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> BIB003 </s> Survey of Robot 3D Path Planning Algorithms <s> Linear Algorithms. <s> The goal of adaptive sampling in the ocean is to predict the types and locations of additional ocean measurements that would be most useful to collect. Quantitatively, what is most useful is defined by an objective function and the goal is then to optimize this objective under the constraints of the available observing network. Examples of objectives are better oceanic understanding, to improve forecast quality, or to sample regions of high interest. This work provides a new path-planning scheme for the adaptive sampling problem. We define the path-planning problem in terms of an optimization framework and propose a method based on mixed integer linear programming (MILP). The mathematical goal is to find the vehicle path that maximizes the line integral of the uncertainty of field estimates along this path. Sampling this path can improve the accuracy of the field estimates the most. While achieving this objective, several constraints must be satisfied and are implemented. They relate to vehicle motion, intervehicle coordination, communication, collision avoidance, etc. The MILP formulation is quite powerful to handle different problem constraints and flexible enough to allow easy extensions of the problem. The formulation covers single- and multiple-vehicle cases as well as single- and multiple-day formulations. The need for a multiple-day formulation arises when the ocean sampling mission is optimized for several days ahead. We first introduce the details of the formulation, then elaborate on the objective function and constraints, and finally, present a varied set of examples to illustrate the applicability of the proposed method. <s> BIB004 </s> Survey of Robot 3D Path Planning Algorithms <s> Linear Algorithms. <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> BIB005
For linear algorithm form based path planning problem, this kind of algorithm tends to have the following form: subject to lower ≤ ( , , , ) ≤ upper , where cost-goal is a cost function that takes into kinodynamic constraints as as well as the expected properties, such as minimum distance, energy, and threat. the control factor, ( , , ) is the kinodynamic constraint which acts as penalty function, and ( , , ) is the exploring step reachable region function to ensure a strong convergence ability to the goal. Equation (16) is the initial condition, (17) is the final condition, (18) is algebraic path constraints, and (19) is the control constraints. Linear algorithms have the ability to describe the environment completely; meanwhile they can model the kinematics and dynamics constraints. Furthermore, linear algorithms can handle control disturbance or model uncertainty. MixedInteger Linear Programming (MILP) methods combine binary and integer logical constraints and are most commonly used because they closely represent the environment and system. Reference BIB004 BIB005 BIB002 implemented MILP, respectively, in aerial, underwater, and ground robots. Bhattacharya BIB001 directly supported a free MATLAB toolbox, which is called OPTRAGEN, to solve the MILP problem. Masehian and Habibi BIB003 used 0-1 binary integer to represent the path length operator and then solved the path planning problem using binary integer programming.