TL;DR
This paper introduces a new language, PQCLTLf, for specifying temporal goals with prioritized preferences in probabilistic environments. They develop a method to translate these preferences into a computational model (weighted automata) and use it to find optimal policies that minimize dissatisfaction, offering a more nuanced approach to planning than traditional methods.
What Problem Does This Paper Address?
Planning in complex environments often involves achieving multiple objectives, but not all objectives can always be met. When faced with such trade-offs, decision-makers need a way to express which objectives are more important. Traditional temporal logic planning focuses on satisfying hard constraints. However, in real-world scenarios, especially in robotics and AI, it's crucial to handle situations where some goals might be partially or fully unmet, and the system needs to achieve the "least bad" outcome based on prioritized preferences. Existing work on probabilistic planning with preferences often uses simple prioritized lists of goals, which can be less expressive. This paper aims to bridge this gap by providing a formal language and a corresponding planning framework that allows for richer, hierarchical specification of preferences over temporal logic objectives in probabilistic settings.
Methods
The core contribution is the development of Prioritized Qualitative Choice Linear Temporal Logic on Finite Traces (PQCLTLf). This language extends standard linear temporal logic (LTL) on finite traces by incorporating prioritized conjunction and ordered disjunction from qualitative choice logic. This allows users to express preferences like "satisfy goal A, but if that's not possible, then satisfy goal B."
To enable planning with these preferences, the authors propose a two-step approach:
- Automata-Theoretic Modeling: They devise a method to translate PQCLTLf formulas into weighted deterministic finite automata (WDFAs). This is a key step, as WDFAs provide a computational model that captures the satisfaction degree of temporal sequences with respect to the prioritized preferences. The construction involves building WDFAs for basic LTLf formulas and then recursively combining them for ordered disjunction and prioritized conjunction.
- Product MDP and Reward Maximization: The WDFAs are then integrated with the probabilistic environment (modeled as a labeled Markov Decision Process or MDP) using a product operation. This creates a larger MDP where states encode both the robot's current situation and the automaton's state. A reward function is defined on this product MDP such that maximizing the expected total reward corresponds to minimizing the expected dissatisfaction score of the original PQCLTLf preference formula. This allows leveraging existing MDP solvers to find the optimal policy.
Datasets
Not discussed in the paper. The experiments use a simulated 8x8 stochastic gridworld, which is a standard benchmark for reinforcement learning and planning tasks.
Key Insights and Ideas
- Expressive Preference Specification: PQCLTLf offers a more nuanced way to express preferences than simple prioritized lists, allowing for hierarchical and conditional goals. The ordered disjunction (×) and prioritized conjunction (&) are crucial for this expressiveness.
- Bridging Logic and Planning: The translation to WDFAs is a critical bridge, converting abstract logical preferences into a concrete computational model that can be integrated with probabilistic planning algorithms.
- Dissatisfaction Score as a Metric: Defining a dissatisfaction score (ranging from 0 to 1) for temporal traces provides a quantifiable measure of how well a given outcome satisfies the prioritized preferences, enabling optimization.
- Optimal Policy Minimizes Dissatisfaction: The core result is that finding an optimal policy in the product MDP (maximizing reward) directly translates to finding a policy that minimizes the expected dissatisfaction score in the original problem.
Key Results
The paper demonstrates the efficacy of their approach through case studies on probabilistic robotic motion planning. They show that their preference-based planning method can generate policies that achieve more preferred outcomes compared to traditional planning methods, especially when dealing with trade-offs. For example, in a gridworld scenario, their policy was shown to achieve higher satisfaction probabilities for prioritized goals. The computational complexity of constructing the WDFA is double-exponential in the worst case for LTLf formulas, but the construction for ordered disjunction and prioritized conjunction is polynomial in the size of the sub-formulas. The planning problem on the product MDP is solved using standard techniques, with experimental results showing fast computation times (under 0.1 seconds for 8x8 gridworlds).
Limitations and Future Work
- Complexity of WDFA Construction: While polynomial for the combination operators, the initial translation of LTLf to DFAs can be double-exponential in the size of the formula, which might be a bottleneck for very complex LTLf specifications.
- Incomparable Options: The PQCLTLf language, as defined, does not handle incomparable options, meaning all preferences must be rankable.
- Future Work: The authors suggest incorporating preference elicitation and learning from data to automatically infer user preferences. They also envision adaptive planning, where preferences can change dynamically. Extending the framework to handle more complex temporal logic fragments or different types of probabilistic environments are also potential future directions.
Summary updated