Goal Specification, Non-Determinism and Quantifying over Policies

Chitta Baral, Jicheng Zhao

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.

A 5-state transition system used to demonstrate policy partitioning.

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.

Table showing how different P-CTL* goals partition the set of satisfiable policies for the 5-state example.

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

Abstract

One important aspect in directing cognitive robots or agents is to formally specify what is expected of them. This is often referred to as goal specification. Temporal logics such as LTL, and CTL* have been used to specify goals of cognitive robots and agents when their actions have deterministic consequences. It has been suggested that in domains where actions have non-deterministic effects, temporal logics may not be able to express many intuitive and useful goals. In this paper we first show that this is indeed true with respect to existing temporal logics such as LTL, CTL*, and π-CTL*. We then propose the language, P-CTL*, which includes the quantifiers, exist a policy and for all policies. We show that this language allows for the specification of richer goals, including many intuitive and useful goals mentioned in the literature which cannot be expressed in existing temporal languages. We generalize our approach of showing the limitations of π-CTL* to develop a framework to compare expressiveness of goal languages.
BibTeX
@inproceedings{baral2006goal,
  author = {Chitta Baral and Jicheng Zhao},
  title = {{Goal Specification, Non-Determinism and Quantifying over Policies}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure