Survey of Robot 3D Path Planning Algorithms <s> A-Star ( * ). <s> Although the problem of determining the minimum cost path through a graph arises naturally in a number of interesting applications, there has been no underlying theory to guide the development of efficient search procedures. Moreover, there is no adequate conceptual framework within which the various ad hoc search strategies proposed to date can be compared. This paper describes how heuristic information from the problem domain can be incorporated into a formal mathematical theory of graph searching and demonstrates an optimality property of a class of search strategies. <s> BIB001 </s> Survey of Robot 3D Path Planning Algorithms <s> A-Star ( * ). <s> A method for planning smooth robot paths is presented. The method relies on the use of Laplace's equation to constrain the generation of a potential function over regions of the configuration space of an effector. Once the function is computed, paths may be found very quickly. These functions do not exhibit the local minima which plague the potential field method. Unlike decompositional and algebraic techniques. Laplace's equation is very well suited to computation on massively parallel architectures. > <s> BIB002 </s> Survey of Robot 3D Path Planning Algorithms <s> A-Star ( * ). <s> A methodology for exact robot motion planning and control that unifies the purely kinematic path planning problem with the lower level feedback controller design is presented. Complete information about a freespace and goal is encoded in the form of a special artificial potential function, called a navigation function, that connects the kinematic planning problem with the dynamic execution problem in a provably correct fashion. The navigation function automatically gives rise to a bounded-torque feedback controller for the robot's actuators that guarantees collision-free motion and convergence to the destination from almost all initial free configurations. A formula for navigation functions that guide a point-mass robot in a generalized sphere world is developed. The simplest member of this family is a space obtained by puncturing a disk by an arbitrary number of smaller disjoint disks representing obstacles. The other spaces are obtained from this model by a suitable coordinate transformation. Simulation results for planar scenarios are provided. > <s> BIB003 </s> Survey of Robot 3D Path Planning Algorithms <s> A-Star ( * ). <s> This paper presents a method for generating shortest paths in cluttered environments, based on the Hamilton-Jacobi-Bellman (HJB) equation. Formulating the shortest obstacle avoidance problem as a time optimal control problem, the shortest paths are generated by following the negative gradient of the return function, which satisfies the HJB equation. A method to generate near-optimal paths is also presented, based on a psuedo return function. Paths generated by this method are guaranteed to reach the goal, at which the psuedo return function is shown to have a unique minimum. The computation required to generate the near-optimal paths is substantially lower than those of traditional potential field methods, making it applicable to on-line obstacle avoidance. Examples with circular obstacles demonstrate close correlation between the near-optimal and optimal paths, and the advantages of the proposed approach over traditional potential field methods.<<ETX>> <s> BIB004 </s> Survey of Robot 3D Path Planning Algorithms <s> A-Star ( * ). <s> The paper first describes the problem of goals unreachable with obstacles nearby when using potential field methods for mobile robot path planning. Then, new repulsive potential functions are presented by taking the relative distance between the robot and the goal into consideration, which ensures that the goal position is the global minimum of the total potential. <s> BIB005 </s> Survey of Robot 3D Path Planning Algorithms <s> A-Star ( * ). <s> Mobile robots often operate in domains that are only incompletely known, for example, when they have to move from given start coordinates to given goal coordinates in unknown terrain. In this case, they need to be able to replan quickly as their knowledge of the terrain changes. Stentz' Focussed Dynamic A* is a heuristic search method that repeatedly determines a shortest path from the current robot coordinates to the goal coordinates while the robot moves along the path. It is able to replan one to two orders of magnitudes faster than planning from scratch since it modifies previous search results locally. Consequently, it has been extensively used in mobile robotics. In this paper, we introduce an alternative to Focussed Dynamic A* that implements the same navigation strategy but is algorithmically different. Focussed Dynamic A* Lite is simpler, easier to understand, easier to analyze and easier to extend than Focussed Dynamic A*, yet is more efficient. We believe that our results will make D*-like replanning algorithms even more popular and enable robotics researchers to adapt them to additional applications. <s> BIB006 </s> Survey of Robot 3D Path Planning Algorithms <s> A-Star ( * ). <s> Artificial Intelligence has traditionally used constraint satisfaction and logic to frame a wide range of problems, including planning, diagnosis, cognitive robotics and embedded systems control. However, many decision making problems are now being re-framed as optimization problems, involving a search over a discrete space for the best solution that satisfies a set of constraints. The best methods for finding optimal solutions, such as A^*, explore the space of solutions one state at a time. This paper introduces conflict-directed A^*, a method for solving optimal constraint satisfaction problems. Conflict-directed A^* searches the state space in best first order, but accelerates the search process by eliminating subspaces around each state that are inconsistent. This elimination process builds upon the concepts of conflict and kernel diagnosis used in model-based diagnosis [J. de Kleer, B.C. Williams, Diagnosing multiple faults, Artif. Intell. 32(1) (1987) 97-130; J. de Kleer, A. Mackworth, R. Reiter, Characterizing diagnoses and systems, Artif. Intell. 56 (1992) 197-222] and in dependency-directed search [R. Stallman, G.J. Sussman, Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis, Artif. Intell. 9 (1977) 135-196; J. Gaschnig, Performance measurement and analysis of certain search algorithms, Technical Report CMU-CS-79-124, Carnegie-Mellon University, Pittsburgh, PA, 1979; J. de Kleer, B.C. Williams, Back to backtracking: controlling the ATMS, in: Proceedings of AAAI-86, 1986, pp. 910-917; M. Ginsberg, Dynamic backtracking, J. Artif. Intell. Res. 1 (1993) 25-46]. Conflict-directed A^* is a fundamental tool for building model-based embedded systems, and has been used to solve a range of problems, including fault isolation [J. de Kleer, B.C. Williams, Diagnosing multiple faults, Artif. Intell. 32(1) (1987) 97-130], diagnosis [J. de Kleer, B.C. Williams, Diagnosis with behavioral modes, in: Proceedings of IJCAI-89, 1989, pp. 1324-1330], mode estimation and repair [B.C. Williams, P. Nayak, A model-based approach to reactive self-configuring systems, in: Proceedings of AAAI-96, 1996, pp. 971-978], model-compilation [B.C. Williams, P. Nayak, A reactive planner for a model-based executive, in: Proceedings of IJCAI-97, 1997] and model-based programming [M. Ingham, R. Ragno, B.C. Williams, A reactive model-based programming language for robotic space explorers, in: Proceedings of ISAIRAS-01, 2001]. <s> BIB007 </s> Survey of Robot 3D Path Planning Algorithms <s> A-Star ( * ). <s> Grids with blocked and unblocked cells are often used to represent continuous 2D and 3D environments in robotics and video games. The shortest paths formed by the edges of 8-neighbor 2D grids can be up to ≈ 8% longer than the shortest paths in the continuous environment. Theta* typically finds much shorter paths than that by propagating information along graph edges (to achieve short runtimes) without constraining paths to be formed by graph edges (to find short "any-angle" paths). We show in this paper that the shortest paths formed by the edges of 26-neighbor 3D grids can be ≈ 13% longer than the shortest paths in the continuous environment, which highlights the need for smart path planning algorithms in 3D. Theta* can be applied to 3D grids in a straight-forward manner, but it performs a line-of-sight check for each unexpanded visible neighbor of each expanded vertex and thus it performs many more line-of-sight checks per expanded vertex on a 26-neighbor 3D grid than on an 8-neighbor 2D grid. We therefore introduce Lazy Theta*, a variant of Theta* which uses lazy evaluation to perform only one line-of-sight check per expanded vertex (but with slightly more expanded vertices). We show experimentally that Lazy Theta* finds paths faster than Theta* on 26-neighbor 3D grids, with one order of magnitude fewer line-of-sight checks and without an increase in path length. <s> BIB008 </s> Survey of Robot 3D Path Planning Algorithms <s> A-Star ( * ). <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> BIB009 </s> Survey of Robot 3D Path Planning Algorithms <s> A-Star ( * ). <s> The graph-search algorithms developed between 60s and 80s were widely used in many fields, from robotics to video games. The A* algorithm shall be mentioned between some of the most important solutions explicitly oriented to motion-robotics, improving the logic of graph search with heuristic principles inside the loop. Nevertheless, one of the most important drawbacks of the A* algorithm resides in the heading constraints connected with the grid characteristics. Different solutions were developed in the last years to cope with this problem, based on post-processing algorithms or on improvements of the graph-search algorithm itself. A very important one is Theta* that refines the graph search allowing to obtain paths with “any” heading. In the last two years, the Flight Mechanics Research Group of Politecnico di Torino studied and implemented different path planning algorithms. A Matlab based planning tool was developed, collecting four separate approaches: geometric predefined trajectories, manual waypoint definition, automatic waypoint distribution (i.e. optimizing camera payload capabilities) and a comprehensive A*-based algorithm used to generate paths, minimizing risk of collision with orographic obstacles. The tool named PCube exploits Digital Elevation Maps (DEMs) to assess the risk maps and it can be used to generate waypoint sequences for UAVs autopilots. In order to improve the A*-based algorithm, the solution is extended to tri-dimensional environments implementing a more effective graph search (based on Theta*). In this paper the application of basic Theta* to tri-dimensional path planning will be presented. Particularly, the algorithm is applied to orographic obstacles and in urban environments, to evaluate the solution for different kinds of obstacles. Finally, a comparison with the A* algorithm will be introduced as a metric of the algorithm performances. <s> BIB010 </s> Survey of Robot 3D Path Planning Algorithms <s> A-Star ( * ). <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> BIB011
A-star (A * ) BIB001 is an extension of Dijkstra's algorithm, which reduces the total number of states by introducing a heuristic estimation of the cost from the Artificial potential Local minima BIB002 BIB003 BIB004 BIB009  BIB005 Fast convergence is the priority queue; is the goal; ( , ) return the cost to apply action from ; is the best cost-to-come known so far; is the finite action space; = ( , ) ∈ is a state transition function; .Insert( ) (11) END; END (12) END; END; Algorithm 5: Dijkstra's algorithm. current state to the goal state. The heuristic function can be designed to obtain the constraints, while the estimation must never overestimate the actual cost to get the nearest goal node. By applying this guiding like heuristic, A * can converge very fast and ensures optimality as well. A * is proposed by introducing an evaluation function (13), which consists of postcalculation toward the initial state and heuristic estimation toward the goal, where ( ) is the cost from initial state init to current state , which is the same as ( ) in Algorithm 5. ℎ( ) is the heuristic estimation of the cost of an optimal path from current state to goal state. The estimation ℎ( ) of each state tends to be close to the real cost; thus A * has a faster speed to converge based on comparison of the cost of neighbors. Compared with Dijkstra's algorithm, A * obtains a faster speed to converge. For 3D environment, A * has been widely implemented. Amato et al.  constructed the feasible road map by applying PRM and then adopted A * to execute best route exploration. Authors in BIB011 implemented A * with UAV platform with an octree based PRM. Niu and Zhuo  introduced "cell" and "region" conception to enhance the environment understanding of A * , thus enabling flexible representation of 3D environments. Koenig and Likhachev proposed an environment-representation varying adaptive A * , that is, Lifelong Planning A * (LPA) BIB006 . LPA * can adapt to environment changes by using previous information as well as iterative replanning. Williams and Ragno BIB007 propounded a conflict-direct A * ; it accelerates the exploring process by eliminating subspaces around each state that are inconsistent. It is proposed in  that A * can choose any state to be parent state, thus resulting in a more flat turning angle, named Theta * . The algorithm has the ability to be able to obtain system constraints; thus it can find shorter and more realistic path. De Filippis et al. BIB010 implemented both Theta * and A * in 3D environment, and an experimental comparison is given to prove that Theta * reduces the searching compared to A * . Although Theta * acts well compared to A * , but when applied to 3D environment, it consumes much time to check unexpected neighbors. Line-of-sight check method, called lazy Theta * BIB008 , is proposed to avoid unnecessary check of unexpected neighbors. Authors in  introduced a method to reuse information from previous explorations and update information through the affected and relevant portions of the exploring space. This may cause extra computational consumption, but it can tackle dynamical threat and converge fast.