A Universal Reactive Approach for Graph-Based Persistent Path Planning Problems With Temporal Logic Constraints

Abstract

This article introduces a reactive methodology tailored for a wide range of practical graph-based path planning applications. In these scenarios, a robot with limited sensor capabilities traverses an undirected graph to optimize metrics related to task duration. This article formalizes these challenges as graph-based persistent path planning problems with temporal logical constraints and proposes a comprehensive persistence planning framework. A novel universal algorithm with quadratic time complexity is designed, striking an optimal balance between accuracy and computational efficiency by establishing a new decision space. Theoretical analysis verifies the algorithm’s convergence and generality, especially for patrol, persistent surveillance, and watchman routing tasks. Moreover, the proposed algorithm is evaluated across various simulation scenarios, demonstrating its effectiveness in addressing complex path planning challenges.