Safe Linear Temporal Logic Motion Planning in Dynamic Environments

Abstract

This paper proposes an online control framework for mobile robots to satisfy a complex mission given in the form of linear temporal logic (LTL) without colliding with moving obstacles in the environment. The proposed framework consists of three modules named the static planner, the local collision avoidance, and the patcher. The static planner is synthesized by solving a parity game for a finite abstraction of the robot model based on a world map with static obstacles to fulfill the LTL task. The local collision avoidance module computes a set of safe controls that guarantees a safe distance between the moving objects. Both of the modules can be rigorously computed offline only once via formal methods. The patcher is activated whenever a moving obstacle is detected and modifies the static plan online for a short horizon by using only provably safe controls. The resulting modified strategy can guarantee collision-free motion without losing the ability to satisfy the LTL task. As opposed to using assume-guarantee type of LTL tasks, the proposed framework can handle the situations where obstacle movement is unpredictable.