Fast Motion Planning in Dynamic Environments With Extended Predicate-Based Temporal Logic

Formal languages effectively outline robots' task specifications, yet current temporal logic struggles to balance semantic expression with solution speed. To address this challenge, we propose extended predicate-based temporal logic (E-pTL), augmenting conventional linear temporal logic with more expressive atomic predicates to reflect the time, space, and order attributes of task and represent complex tasks with dynamic propositions, time windows, and even relative time window. This approach, blending automata-based task abstraction and extended predicates, offers enhanced expressiveness and conciseness for intricate specifications. To cope with E-pTL, we introduce a novel planning framework, the Planning Decision Tree (PDT). PDT incrementally builds a tree through automata and system state searches, recording potential task plans. The proposed pruning method can reduce the exploration space. This method swiftly handles complex temporal tasks defined by E-pTL. Rigorous analysis confirms PDT-based planning's feasibility (ensuring satisfactory planning aligned with task specifications) and completeness (guaranteeing a feasible solution if available). Moreover, PDT-based planning proves efficient, with solution times approximately linearly proportional to automaton states squared. Extensive simulations and experiments validate its effectiveness and efficiency.