Optimal Path Planning Satisfying Complex Task Requirement in Uncertain Environment

Summary Robots often need to accomplish some complex tasks such as surveillance, response and obstacle avoidance. In this paper, a dynamic search method is proposed to generate optimal robot trajectories satisfying complex task requirement in uncertain environment. The LTL-A* algorithm is presented to generate a global optimal path and the A* algorithm is provided to modify the global optimal path. The task is specified by a linear temporal logic (LTL) formula, and a weighted transition system according to the known information in uncertain environment is modeled to describe the robot motion. Subsequently, a product automaton is constructed by combining the transition system with the task requirement. Based on the product automaton, the LTL-A* algorithm is proposed to generate a global optimal path. The local path planning based on the A* algorithm is employed to deal with the environment change during the process of tracking the global optimal path for the robot. The results of the simulation and experiments show that the proposed method can not only meet the complex task requirement in uncertain environment but also improve the search efficiency.