iADA*: Improved Anytime Path Planning and Replanning Algorithm for Autonomous Vehicle

Path planning of autonomous mobile robots in a real-world environment presents several challenges which are usually not raised in other areas. The real world is inherently complex, uncertain and dynamic. Therefore, accurate models of path planning are difficult to obtain and quickly become outdated. Anytime planners are ideal for this type of problem as they can find an initial solution very quickly and then improve it as time allows. This paper proposes a new anytime incremental search algorithm named improved Anytime Dynamic A*(iADA*). The algorithm is based on the currently popular anytime heuristic search algorithm, which is Anytime Dynamic A*(ADA*). The iADA* algorithm improves the calculation of the path lengths and decreases the calculating frequency of the path throughout the search, making it significantly faster. The algorithm is designed to provide an efficient solution to a complex, dynamic search environment when the locally changes affected. Our study shows that the two-dimensional path-planning iADA* experiments were between 2.0 to 3.7 times faster than ADA*, both in partially known and fully unknown dynamic environments. Additionally, in this paper shows the experiment results of the comparison with other four existing algorithms based on computing time and path lengths. iADA* was an average 2.57 times reduced on the computational time for the environment which locally changes effected. For the path length is little increase, but it is not the worst case. According to the experiments, the more the environmental problems and complexity increases, the more iADA* provides a rapid in-search time and total time to obtain the final solution.