Non-monotonic Temporal Logics for Goal Specification

Chitta Baral, Jicheng Zhao

Introduction

In the field of artificial intelligence, specifying goals for autonomous agents often relies on temporal logics like Linear Temporal Logic (LTL). While LTL is highly effective for defining rigid properties—such as "always keep the door locked" or "eventually reach the destination"—it struggles with the inherent messiness of real-world environments. Specifically, classical temporal logics are monotonic: once a constraint is added, the set of valid plans can only shrink. This paper, originally presented at IJCAI 2007, introduces N-LTL, a non-monotonic extension of LTL designed to handle exceptions gracefully through a property known as "elaboration tolerance."

The Problem: The Lack of Elaboration Tolerance

In classical AI planning, if a developer specifies a goal in LTL and later realizes there are exceptions to that goal, they must perform "logical surgery" on the original formula. For example, consider a robot instructed to "always keep the floor dry." If the robot later needs to clean the floor, the developer cannot simply add a new rule. Instead, they must rewrite the original formula to something like "Always (if not cleaning, then floor is dry)."

This lack of elaboration tolerance makes building complex, evolving systems incredibly difficult. Human instructions are rarely complete; we typically provide a general rule and refine it with exceptions as they arise. N-LTL aims to mirror this human-centric approach by allowing developers to specify general goals and later add exceptions by simply appending new rules rather than rewriting the existing logic.

Methodology: The N-LTL Framework

The authors propose N-LTL as a rule-based language that borrows structural elements from logic programming. The framework is built on several core innovations:

1. Rule-Based Syntax

Instead of a single, monolithic formula, an N-LTL specification consists of a set of rules. A special symbol $g$ represents the final goal, while labels ($r_1, r_2, \dots$) identify specific segments of the goal that may be subject to future exceptions.

2. Exception Operators

N-LTL introduces two distinct types of exceptions to provide fine-grained control over agent behavior:

  • Weak Exceptions ($[r]\phi$): This indicates that $\phi$ normally holds, but the rules labeled under $r$ list situations where the agent is no longer required to ensure $\phi$ is true.
  • Strong Exceptions ($[[r]]\phi$): This indicates that $\phi$ normally holds, but $r$ lists situations where $\phi$ is explicitly allowed to be false.

3. Compilation and Translation

To ensure the logic remains grounded and usable, the authors provide an algorithm to "compile" N-LTL rules back into standard LTL formulas. While the resulting LTL formulas are larger, this mapping allows N-LTL to leverage existing LTL verification tools. Furthermore, the paper provides a translation into Answer Set Programming (ASP), enabling the use of logic programming solvers to find plans that satisfy these non-monotonic goals.

Key Insights and Results

The primary contribution of N-LTL is the shift toward additive goal specification. By requiring the specifier to explicitly mark which parts of a goal are subject to exceptions (using the $[r]$ notation), the language provides a balance between the flexibility of non-monotonic logic and the strict control required for safety-critical AI.

Theoretical Findings

  • Non-monotonicity: The authors formally prove that N-LTL is non-monotonic. Adding a rule for a strong exception can actually increase the number of valid plans, effectively making the goal "easier" to satisfy in specific contexts.
  • Computational Efficiency: The process of converting N-LTL to LTL is shown to be a polynomial-time operation. This suggests that the added flexibility of the language does not impose a prohibitive computational cost compared to standard LTL.
  • Planning Integration: The translation to logic programming bridges the gap between high-level theoretical specification and practical automated planning, allowing for the generation of agents that can navigate complex rule sets with exceptions.

Limitations and Future Work

While N-LTL offers a significant step forward in elaboration tolerance, it has specific constraints. Currently, a user must decide a priori which goal fragments might have exceptions; an exception cannot be added to a statement that was not originally wrapped in an exception operator.

Future research directions include comparing this "explicit exception" approach with traditional default logics, where statements do not need to be pre-marked. Additionally, while the compilation is polynomial, the practical scalability of the resulting complex LTL formulas in large-scale industrial planning remains an area for further empirical study.

Summary updated

Abstract

One of the main ways to specify goals of agents is to use temporal logics. Most existing temporal logics are monotonic. However, in representing goals of agents, we often require that goals be changed non-monotonically. For example, the initial goal of the agent may be to be always in states where p is true. The agent may later realize that under certain conditions (exceptions) it is ok to be in states where p is not true. In this paper, we propose a simple extension of LTL, which we call N-LTL, that allows non-monotonic specification of goals. We study properties of N-LTL. We also consider a translation from N-LTL to logic programs and study the relationship between N-LTL and logic programs.
BibTeX
@inproceedings{baral2007non,
  author = {Chitta Baral and Jicheng Zhao},
  title = {{Non-monotonic Temporal Logics for Goal Specification}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
}
Figure