Planning for Temporally Extended Goals

AAAI 1996

TL;DR

This paper introduces a novel temporal logic, MITL, for specifying complex goals that go beyond simple final states, including deadlines, safety, and maintenance requirements. They also present a sound and complete planning algorithm that leverages "formula progression" to efficiently generate plans satisfying these rich temporal goals.

What Problem Does This Paper Address?

Traditional AI planning systems often define goals as conditions on a final state. While this works for simple tasks, it's insufficient for agents that need to perform complex sequences of actions with specific timing or safety constraints. For instance, an agent might need to ensure a certain condition never becomes false during its operation (a safety goal) or that a task is completed by a specific time (a deadline). Communicating these nuanced requirements to a planner is challenging. Existing approaches often struggle to express these temporally extended goals precisely, leading to plans that might achieve the desired end state but violate crucial intermediate conditions. This paper aims to bridge this gap by providing a formal language and a planning mechanism for these more sophisticated goals.

Methods

The core of this work lies in two main contributions:

  1. Metric Interval Temporal Logic (MITL): The authors propose MITL, an extension of existing temporal logics that allows for first-order quantification and specifies goals as desirable sequences of states, not just final states. This logic can express:
  2. Classical goals: Achieving a specific final state.
  3. Temporal deadlines: Goals that must be met within a certain time frame.
  4. Safety goals: Conditions that must always hold true.
  5. Maintenance goals: Conditions that must be maintained over time.
  6. Quantified goals: Goals involving universal or existential quantification over domain elements.
  7. Formula Progression Planning Algorithm: They develop a planning algorithm that uses a technique called "formula progression." Instead of checking goal satisfaction only at the end, this algorithm incrementally updates the goal formula as the plan is built.
  8. The initial state is labeled with the goal formula.
  9. For each action taken, the goal formula is "progressed" to reflect the new state and the time elapsed. This means the formula is transformed to represent what needs to be true from that new state onwards to satisfy the original goal.
  10. This progression allows for early detection of impossible plans (if a formula becomes FALSE) and efficient pruning of the search space.
  11. Termination is checked by seeing if an "idling" state (where no further actions are taken) satisfies its current label.

Datasets

Not discussed in the paper. The authors use a simulated "Robot Room domain" for empirical evaluation.

Key Insights and Ideas

  • Goals as State Sequences, Not Just End States: The fundamental shift in perspective is viewing goals as specifying acceptable paths through states, rather than just destinations. This is crucial for temporal reasoning.
  • Formula Progression as Incremental Goal Checking: This technique is a powerful way to integrate goal checking directly into the planning process, enabling efficient search and pruning. It transforms temporal logic into a dynamic constraint that guides the planner.
  • MITL's Expressiveness: The ability to combine temporal modalities with first-order logic and intervals allows for a remarkably rich specification of agent behavior, encompassing safety, deadlines, and complex temporal relationships.
  • Search Control via Goals: Safety and temporal goals naturally act as search control mechanisms, pruning branches of the search space that would violate these conditions, leading to more efficient planning.

Key Results

The paper demonstrates the effectiveness of their approach through empirical results on a simulated Robot Room domain. They show that their planner can generate plans for various types of goals, including:

  • Classical goals: Achieved efficiently.
  • Quantified goals: Demonstrated with an example requiring all objects to be in a specific room and the robot to be empty-handed.
  • Goals with timing deadlines: Illustrated by a scenario where objects must be moved within strict time limits, requiring careful sequencing of actions.
  • Safety and "don't disturb" goals: Shown to significantly speed up planning by pruning irrelevant search paths. For instance, a goal to prevent doors from being closed unnecessarily led to substantial speedups.

Specific examples include:

  • A classical goal took 22 seconds and expanded 636 worlds.
  • A quantified goal took 3 seconds and expanded 126 worlds.
  • A goal with a tight deadline and a safety constraint took 8 seconds and expanded 284 worlds.
  • When a more complex timing deadline was introduced, the same problem took 120 seconds and expanded 1907 worlds, highlighting the impact of goal complexity.

Limitations and Future Work

  • Efficiency for Complex Goals: While their approach is sound and complete, the planner's efficiency can still be a challenge for very complex temporal goals, as seen in the G5 example. The authors acknowledge that the planner is not efficient enough for all practical problems and relies on blind search for simple goals.
  • Search Control: They suggest that domain-dependent search control information, expressed as MITL formulas, is key to improving efficiency. They plan to explore this further, aiming for polynomial-time planners.
  • Incomplete State Descriptions: The current system assumes complete state descriptions. The authors note that this could be relaxed, but it would likely impact efficiency, potentially requiring theorem proving instead of simple lookups.
  • Future Work: The authors intend to further investigate search control mechanisms and explore the performance of their planner on more realistic planning problems. They also mention the possibility of extending their framework to handle more complex notions of incompleteness.

Summary updated

BibTeX
@inproceedings{1996planning,
  title = {{Planning for Temporally Extended Goals}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure