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.
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.
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:
- Soundness: Every answer set of the translated logic program corresponds to a valid execution trace of the original control specification.
- 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