Survey of Robot 3D Path Planning Algorithms <s> D-Star ( <s> The task of planning trajectories for a mobile robot has received considerable attention in the research literature. Most of the work assumes the robot has a complete and accurate model of its environment before it begins to move; less attention has been paid to the problem of partially known environments. This situation occurs for an exploratory robot or one that must move to a goal location without the benefit of a floorplan or terrain map. Existing approaches plan an initial path based on known information and then modify the plan locally or replan the entire path as the robot discovers obstacles with its sensors, sacrificing optimality or computational efficiency respectively. This paper introduces a new algorithm, D*, capable of planning paths in unknown, partially known, and changing environments in an efficient, optimal, and complete manner. > <s> BIB001 </s> Survey of Robot 3D Path Planning Algorithms <s> D-Star ( <s> Abstract : By now Artificial Intelligence (AI), Theoretical Computer Science (CS theory) and Operations Research (OR) have investigated a variety of search and optimization problems. However, methods from these scientific areas use different problem descriptions, models, and tools. They also address problems with particular efficiency requirements. For example, approaches from CS theory are mainly concerned with the worst-case scenarios and are not focused on empirical performance. A few efforts have tried to apply methods across areas. Usually a significant amount of work is required to make different approaches "talk the same language," be successfully implemented, and, finally, solve the actual same problem with an overall acceptable efficiency. This thesis presents a systematic approach that attempts to advance the state of the art in the transfer of knowledge across the above mentioned areas. In this work we investigate a number of problems that belong to or are close to the intersection of areas of interest of AI, OR and CS theory. We illustrate the advantages of considering knowledge available in different scientific areas and of applying algorithms across distinct disciplines through successful applications of novel hybrid algorithms that utilize benefitial features of known efficient approaches. Testbeds for such applications in this thesis work include both open theoretical problems and ones of significant practical importance. We introduce a representation change that enables us to question the relation between the Pigeonhole Principle and Linear Programming Relaxation. We show that both methods have exactly the same bounding power. Furthermore, even stronger relation appears to be between the two methods: The Pigeonhole Principle is the Dual of Linear Programming Relaxation. Such a relation explains the "hidden magic" of the Pigeonhole Principle, namely its power in establishing upper bounds and its effectiveness in constructing optimal solutions. <s> BIB002 </s> Survey of Robot 3D Path Planning Algorithms <s> D-Star ( <s> D* is a planning method that always routes a robot in initially unknown terrain from its current location to a given goal location along a shortest presumed unblocked path. The robot moves along the path until it discovers new obstacles and then repeats the procedure. D* has been used on a large number of robots. It is therefore important to analyze the resulting travel distance. Previously, there has been only one analysis of D*, and it has two shortcomings. First, to prove the lower bound, it uses a physically unrealistic example graph which has distances that do not correspond to distances on a real map. We show that the lower bound is not smaller for grids, the kind of map-based graph on which D* is usually used. Second, there is a large gap between the upper and lower bounds on the travel distance. We considerably reduce this gap by decreasing the upper bound on arbitrary graphs, including grids. To summarize, we provide new, substantially tighter bounds on the travel distance of D* on grids, thus providing a realistic analysis for the way D* is actually used. <s> BIB003 </s> Survey of Robot 3D Path Planning Algorithms <s> D-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/sup */ (D/sup */) 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 faster than planning from scratch since it modifies its previous search results locally. Consequently, it has been extensively used in mobile robotics. In this article, we introduce an alternative to D/sup */ that determines the same paths and thus moves the robot in the same way but is algorithmically different. D/sup */ Lite is simple, can be rigorously analyzed, extendible in multiple ways, and is at least as efficient as D/sup */. We believe that our results will make D/sup */-like replanning methods even more popular and enable robotics researchers to adapt them to additional applications. <s> BIB004
* ). D-star (D * ) BIB001  , short for dynamic A * , is famous for its wide use in the DARPA unmanned ground vehicle programs. D * is a sensor based algorithm that deals with dynamic obstacles by real time changing its edge's weights to form a temporal map and then moves the robot from its current location to the goal location in the shortest unblocked path. D * , As well as A * , evaluates the cost by considering the postcalculation and forward estimation. D * maintains a list of states which is used to propagate information about changes of the arcs cost function. The evaluation function is represented as  However, differing from A * , ℎ ( ) is not necessarily the shortest path length to the goal compared to A * ; also computation of ℎ ( ) assumes that the robot can pass through obstacles. At each time it updates a minimum heuristic function when it encounters new obstacles and the whole graph, thus enabling efficient searching in dynamic environments. Smirnov BIB002 considered the worst travel distance case of D * and restrained its lower bound as Ω((log | |/ log log | |)| |) steps and upper bound as (| | 2 ). The bound is used to solve the problem that D * uses unrealistic distance in its graph, and there is a large gap between the lower bounds and upper bounds. Based on BIB002 , Tovey et al. BIB003 put it forward by adding more tighter bounds for D * . Koenig and Likhachev BIB004 extended LPA * to the case where the goal changes between replanning episodes; it is like a simplified version of D * , called D * Lite, but it is proposed based on LPA * . Table 3 provides a straightforward summarization of node based optimal algorithms. As the name implies, node based optimal algorithms deal with node and arc information. However, as the nodes and arcs provide an incomplete structure of the configuration space, this kind of method can only achieve the best result limited by the representation of environment. This kind of algorithms is single search methods. It cannot generate multipath for fleet. For real time implementation, Dijkstra's algorithm's time complexity is ( 2 ) ( is the number of the nodes); A * and D * reduce the complexity to a lower degree, which enables on-line implementation.