Non-monotonic Temporal Logics that Facilitate Elaboration Tolerant Revision of Goals

Chitta Baral, Jicheng Zhao

Introduction

In the field of autonomous agent design, Linear Temporal Logic (LTL) has long served as the standard for specifying complex tasks. However, a significant limitation of LTL is its monotonicity: once a goal is defined, any additional information can only further constrain the agent's behavior. It cannot easily retract or fundamentally revise a previous instruction without a complete rewrite of the specification. This paper introduces ER-LTL (Exceptions and Revisions Linear Temporal Logic), a non-monotonic framework designed to facilitate "elaboration tolerant" goal revision.

The Challenge: Monotonicity in Dynamic Environments

Consider a search-and-rescue robot. A supervisor might initially command: "Eventually pick up the medical kit and then proceed to the extraction point." In standard LTL, if the supervisor later realizes the extraction point is blocked and attempts to add a new rule, the logic treats this as an additional constraint rather than a replacement. To truly "fix" the goal, the operator must discard the original formula and construct a new, often more complex, logical expression from scratch.

This lack of elaboration tolerance—the ability to incorporate new information with minimal changes to the existing representation—is a major hurdle for real-time human-robot interaction. In high-stakes, fluid environments, goals are rarely static. ER-LTL addresses this by allowing users to update or retract goals incrementally.

ER-LTL: Syntax and Semantics

The core of the proposed framework is a rule-based structure that supports non-monotonic reasoning. ER-LTL programs consist of rules defined as:

$$h : [r](f_1 \rightsquigarrow f_2)$$

Where:

  • $h$ is a unique label for the rule.
  • $f_1$ is the precondition (the context in which the rule applies).
  • $f_2$ is the consequent (the temporal goal).
  • $r$ is a label pointing to potential exceptions.
  • $\rightsquigarrow$ is the "normality" operator.

This operator signifies that "Normally, if $f_1$ holds, then $f_2$ should be satisfied, unless an exception $r$ occurs." This structure allows for a hierarchy of rules where exceptions can themselves have exceptions, enabling sophisticated nested revisions.

Practical Implementation: Compilation to LTL

A primary advantage of ER-LTL is its compatibility with existing technology. The authors provide a method to compile ER-LTL programs back into standard LTL formulas using a "completion" technique inspired by the work of Ray Reiter. By wrapping the complexity of exceptions into a pre-processing step, the framework outputs a monotonic formula that can be handled by highly optimized, off-the-shelf LTL planners and model checkers. This ensures that the flexibility of non-monotonic reasoning does not come at the cost of losing access to established computational tools.

Key Insights and Comparisons

The paper highlights several conceptual breakthroughs:

  1. Flexible Exception Handling: ER-LTL distinguishes between weak exceptions (which simply render a goal inapplicable) and strong exceptions (which explicitly negate the original goal). Unlike previous attempts like N-LTL, which required these distinctions to be declared a-priori, ER-LTL allows these behaviors to emerge naturally from the rule structure.
  2. Incremental Knowledge: The framework acknowledges that human supervisors are rarely "perfect logicians" at the start of a mission. ER-LTL treats specifications as evolving documents, accommodating "afterthoughts" and shifting priorities without requiring a total system reset.
  3. Versatile Revision Types: The logic supports strengthening or weakening preconditions, replacing consequents entirely, and creating complex chains of revisions.

Limitations and Future Research

While ER-LTL represents a significant step forward, the authors identify several areas for future development:

  • Goal Progression: The current logic does not fully account for "stateful" revisions—how a goal should change if an agent has already partially completed the original task.
  • Natural Language Integration: There remains a gap between human speech and formal ER-LTL rules. Bridging this gap would allow for more intuitive, conversational goal revision.
  • Belief Revision: Currently, the framework focuses on revising goals. Integrating this with changing beliefs about the environment (e.g., discovering a door is locked) remains a complex challenge for future non-monotonic temporal logics.

Conclusion

ER-LTL provides a robust, elaboration-tolerant framework for agent goal specification. By allowing for incremental updates and exceptions while maintaining compatibility with standard LTL solvers, it offers a practical path toward more flexible and responsive autonomous systems in dynamic real-world environments.

Summary updated

Abstract

Temporal logics are widely used in specifying goals of agents. We noticed that when directing agents, humans often revise their requirements for the agent, especially as they gather more knowledge about the domain. However, all existing temporal logics, except one, do not focus on the revision of goals in an elaboration tolerant manner. Thus formal temporal logics that can allow elaboration tolerant revision of goals are needed. As non-monotonic languages are often used for elaboration tolerant specification, we propose to explore non-monotonic temporal logics for goal specification. Recently, a non-monotonic temporal logic, N-LTL, was proposed with similar aims. In N-LTL, goal specifications could be changed via strong and weak exceptions. However, in NLTL, one had to a-priori declare whether exceptions will be weak or strong exceptions. We propose a new nonmonotonic temporal logic, that not only overcomes this, but is also able to express exception to exceptions, strengthen and weaken preconditions, and revise and replace consequents; all in an elaboration tolerant manner.
BibTeX
@inproceedings{baral2008non,
  author = {Chitta Baral and Jicheng Zhao},
  title = {{Non-monotonic Temporal Logics that Facilitate Elaboration Tolerant Revision of Goals}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}

Loading related content...

Figure