Adding Time and Intervals to Procedural and Hierarchical Control Specifications

Tran Cao Son, Chitta Baral, Le-Chi Tuan

Introduction

High-level agent control often relies on languages like GOLOG to manage sequences, loops, and conditional behaviors. However, traditional GOLOG frameworks have historically struggled with durative actions—actions that occupy a span of time—and complex temporal constraints. Often, these systems default to an "as soon as possible" execution model, which lacks the flexibility required for real-world scenarios where actions must occur within specific relative time windows. For instance, specifying that "Action A should start between 1 and 3 minutes after Action B starts" was difficult to represent without over-constraining the resulting plan.

To address these limitations, this paper introduces $Golog+HTN^{TI}$, a hybrid control language. By combining the procedural logic of GOLOG with the task-decomposition capabilities of Hierarchical Task Networks (HTN) and an interval-based temporal reasoning system, the authors provide a framework for more realistic and flexible agent behavior in time-sensitive environments.

The Action Description Language $\mathcal{AD}$

The foundation of $Golog+HTN^{TI}$ is an extension of the standard action description language $\mathcal{A}$, termed $\mathcal{AD}$. This extension incorporates the concept of time directly into the action theory.

Syntax of the extended action description language $\mathcal{AD}$, including duration and executability constraints.

As shown in the table above, $\mathcal{AD}$ introduces the duration(a, v) property, allowing the system to reason about the time required for an action $a$ to complete. It also handles causal effects (causes(a, f)) and executability conditions, providing a robust base for temporal planning.

Temporal Connectives and Hierarchical Constraints

The core innovation of $Golog+HTN^{TI}$ lies in its sophisticated temporal connectives. Rather than simple sequential execution, the language allows for:

  • Start-to-Start ($;^s_{[t1,t2]}$): Program $p_2$ must start between $t_1$ and $t_2$ units after $p_1$ begins.
  • End-to-Start ($;^e_{[t1,t2]}$): Program $p_2$ must start between $t_1$ and $t_2$ units after $p_1$ finishes.
  • HTN Constraints: These allow for partial ordering, such as requiring one task to finish before another starts while leaving other tasks unordered.

These constraints define a "window of opportunity" rather than a fixed schedule. This flexibility is illustrated by the fact that a single program specification can result in multiple valid execution traces.

Example of different execution traces (a) and (b) for the same set of actions, demonstrating how temporal constraints allow for varied scheduling.

Implementation via Answer Set Programming

To translate these high-level specifications into executable plans, the authors employ Answer Set Programming (ASP), specifically using the AnsProlog language. The planning process is treated as a search for an "answer set"—a logical model where all procedural, hierarchical, and temporal constraints are satisfied.

By leveraging powerful ASP solvers like smodels or dlv, the system can efficiently search the space of possible schedules to find a valid execution trace. This approach avoids the need for a custom planning algorithm and benefits from the performance optimizations inherent in modern logic programming solvers.

Key Results and Formal Foundations

The authors provide a rigorous mathematical foundation for $Golog+HTN^{TI}$ by defining the "trace" of a program. They established two primary theorems:

  1. Soundness: Every answer set of the translated logic program corresponds to a valid execution trace of the original control specification.
  2. Completeness: Every valid execution trace of the specification is represented by at least one answer set in the logic program.

A prototype interpreter was developed to demonstrate the practical utility of this approach, successfully generating plans for agents in domains with complex overlapping actions and strict temporal deadlines.

Limitations and Future Directions

While $Golog+HTN^{TI}$ significantly advances temporal control, some limitations remain. The current model uses discrete time (non-negative integers), which may not capture continuous processes or "Zeno" behaviors. Additionally, the computational complexity of ASP can lead to large search spaces as the number of time steps increases.

Future work aims to incorporate continuous fluents (e.g., monitoring battery levels) and extend the framework to handle more complex processes using the $\mathcal{ADC}$ language. The authors also plan to conduct more extensive performance evaluations in larger, more complex domains.

Summary updated

Abstract

In this paper we introduce the language Golog+HTNTI for specifying control using procedural and HTN-based constructs together with deadlines and time restrictions. Our language starts with features from GOLOG and HTN and extends them so that we can deal with actions with duration by being able to specify time intervals between the start (or end) of an action (or a program) and the start (or end) of another action (or program). We then discuss an off-line interpreter based on the answer set planning paradigm such that the answer sets of the logic program have a one to one correspondence with the traces of the Golog+HTNTI specification.
BibTeX
@inproceedings{son2004adding,
  author = {Tran Cao Son and Chitta Baral and Le-Chi Tuan},
  title = {{Adding Time and Intervals to Procedural and Hierarchical Control Specifications}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2004},
}
Figure