Survey of Robot 3D Path Planning Algorithms <s> Node Based Optimal Algorithms: Elements and Analysis. <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> BIB001 </s> Survey of Robot 3D Path Planning Algorithms <s> Node Based Optimal Algorithms: Elements and Analysis. <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> BIB002 </s> Survey of Robot 3D Path Planning Algorithms <s> Node Based Optimal Algorithms: Elements and Analysis. <s> The majority of existing approaches to mobile robot mapping assumes that the world is static, which is generally not justified in real-world applications. However, in many navigation tasks including trajectory planning, surveillance, and coverage, accurate maps are essential for the effective behavior of the robot. In this paper we present a probabilistic grid-based approach for modeling changing environments. Our method represents both, the occupancy and its changes in the corresponding area where the dynamics are characterized by the state transition probabilities of a Hidden Markov Model. We apply an offline and an online technique to learn the parameters from observed data. The advantage of the online approach is that it can dynamically adapt the parameters and at the same time does not require storing the complete observation sequences. Experimental results obtained with data acquired by real robots demonstrate that our model is well-suited for representing changing environments. Further results show that our technique can be used to substantially improve the effectiveness of path planning procedures. <s> BIB003
Node based optimal algorithms explore through the decomposed graph BIB003 . Analyzing from the point of the search mechanism, node based optimal algorithms share the same property that they explore among a set of nodes (cell) in the map, where information sensing and processing procedures are already executed. This kind of methods can always find an optimal path according to the certain decomposition. Figure 4 illustrates the typical elements of node based optimal algorithms. Where LPA * BIB001 represents Lifelong Planning A * algorithm which is a repeating version of A * (i.e., having the ability to handle dynamic threats), D * -Lite BIB002 was proposed based on LPA * , which deals with dynamic threat situations. Dijkstra's algorithms, A * and D * , are traditionally classified as discrete optimal planning  , or road map algorithms  , or search algorithms  , and so on. However, they do not collide with each other and just express the same thing where algorithms like this kind deal with discrete optimization based on grid decomposition.