Abstract
This paper introduces P-CTL, a novel temporal logic extension designed for specifying complex goals in non-deterministic environments. By incorporating quantifiers that reason directly over policies (strategies), P-CTL enables autonomous agents to adopt "best-effort" behaviors, adapting their objectives based on the environmental constraints and the strength of available strategies. We demonstrate that P-CTL is strictly more expressive than existing logics like CTL and $\pi$-CTL*, particularly in its ability to partition policies into preference-based hierarchies.
Introduction
In autonomous systems, goals are traditionally defined as destination states. However, real-world actions are often non-deterministic, where a single action can lead to multiple outcomes. In such environments, a plan is better represented as a policy—a mapping from states to actions.
While logics like LTL and CTL* are effective for path-based properties, they fail to express goals contingent on the availability of specific types of strategies. For instance, an agent might prefer a guaranteed (strong) strategy but settle for a possible (weak) one if no guarantee exists. Existing formalisms cannot distinguish these nuances, creating a gap in specifying robust robotic behavior when perfect outcomes are not guaranteed.
Methods
The authors propose P-CTL, which extends $\pi$-CTL with two policy-level quantifiers:
- $EP$ (Exists a Policy): There exists a policy starting from the current state such that a specific formula holds.
- $AP$ (For All Policies): For every possible policy starting from the current state, a specific formula holds.
By nesting these with standard path quantifiers (like "Always" $\Box$ or "Eventually" $\diamond$), P-CTL can express conditional and adaptive goals. For example, an agent can check for a strong policy ($EP A_\pi \diamond p$) and fall back to a weak one ($EP E_\pi \diamond p$) if necessary. The paper also introduces a formal framework to compare the expressiveness of goal languages mathematically, proving that P-CTL can describe sets of desirable policies that other languages cannot.
Key Insights and Results
The primary contribution is the formalization of the "Try Your Best" requirement, where agents are mandated to choose the strongest available policy class (Strong > Strong Cyclic > Weak). P-CTL is the first logic to natively capture this hierarchy. Unlike previous logics, P-CTL is "adaptive"—the satisfaction of a goal depends on the domain's structure and what it permits the agent to achieve.
The authors demonstrate the superior expressiveness of P-CTL* through a 5-state transition system example.
Using this model, they show that P-CTL can create arbitrary partitions of available policies based on preference. As shown in the table below, different P-CTL goals can isolate specific sets of policies (labeled $\pi_1$ through $\pi_5$), a feat impossible in CTL or $\pi$-CTL.
Conclusion and Future Work
While P-CTL offers significant gains in expressiveness, it introduces higher computational complexity for model checking and synthesis due to policy quantification. Future work includes exploring $P_t$-CTL**, which considers history-dependent (trajectory-based) policies, and extending the framework to multi-agent environments where agents must cooperate or compete within non-deterministic settings.
Summary updated