Mobile Robot Path Planning With a Moving Goal

Path planners, in which a hunter is required to chase after a moving target, are an important problem for robotic systems such as unmanned aerial vehicles and unmanned underwater vehicles. This paper describes an incremental moving target path planning algorithm which leverages previous planning data to update the path in the case where the target moves. The algorithm in this paper addresses the need for a quick path-planner that can be used in an environment where the target is moving. The algorithm does this by sacrificing optimality in order to reduce the computational complexity of the problem. Examples show that the algorithm reduces the complexity of re-planning by approximately 12 times while only increasing path length taken by 1.5%. Analytical estimates of the best and worst case complexity of the algorithm were developed, and these estimates are validated with experimental data.