Timeline-based Planning:
Theory and Practice

Abstract

Planning systems are usually built around the concepts of state and action, inherited from STRIPS, at the core of modeling languages such as PDDL. Timeline-based planning approaches the problem from a different perspective: there is no explicit separation between states, actions, and goals, but rather, the planned domain is represented as a system made of independent, but interacting, components, whose behavior over time, represented as timelines, is governed by a given set of temporal constraints. This paradigm, born in the context of planning and scheduling of space operations, has been employed in the last two decades in a number of complex scenarios, from short- to long-term planning of space exploration missions, to onboard autonomy of spacecrafts. Recently, research in the field explored the application of the paradigm to different scenarios such as assistive robotics, and settled long-standing questions about theoretical and computational properties of timeline-based problems and languages.

This tutorial introduces the timeline-based approach to planning. After briefly recalling the history of the development of this approach, the paradigm is compared with common action-based planning formalisms á la PDDL. Then, recent developments, both theoretical and applied, and research challenges in the field are described in detail. The recently introduced PLATINUm framework is described as a representative of the class of timeline-based planning systems, and recent theoretical results about the expressiveness of timeline-based languages and the computational complexity of timeline-based problems are described in detail.

Slides are online!

Thanks to all the people that attended the tutorial. The slides are available at the following links:

Main slides deck

Slides about PLATINUm

Speakers

• Nicola Gigante
  University of Udine, Italy
  e-mail
• Angelo Montanari
  University of Udine, Italy
  e-mail
• Andrea Orlandini
  ISTC-CNR, Rome, Italy
  e-mail
• Alessandro Umbrico
  ISTC-CNR, Rome, Italy
  e-mail

Detailed timeline of the tutorial

Part 1 • Timeline-based planning systems

• Introduction
  • History of the approach, application scenarios, survery of state-of-the-art systems
  • Basic concepts: state variables, timelines, plans, synchronization rules
  • Definition of timeline-based planning problems, examples
• Integrating planning and execution
  • Timeline-based planning problems with uncertainty
  • Flexible timelines, flexible plans
  • Controllability issues of flexible plans: weak, strong, and dynamic controllability
• Timelines in practice: the PLATINUm system
  • Introduction to the framework
  • Application scenarios: assistive robotics, human-robot interaction
  • Handling of resources
• Open issues and future developments

Part 2 • Timeline-based planning: expressiveness and complexity

• Expressiveness of timeline-based languages:
  • Expressiveness comparison with action-based languages á la PDDL
  • Timelines are expressive enough to capture action-based temporal planning
• Complexity of timeline-based problems:
  • Deciding whether timeline-based problems admit solution plans is EXPSPACE-complete
  • Other complexity results: problems with bounded horizon, problems over infinite timelines, problems over dense time
  • Automata-theoretic perspective
• Timeline-based planning problems with uncertainty:
  • Issues of flexible plans
  • Timeline-based games, a game-theoretic approach: game arena, moves, strategies
  • Finding winning strategies is 2EXPTIME-complete
• Timelines and temporal logic:
  • A logical characterization of timeline-based planning problems
  • The Bounded TPTL with Past logic captures timeline-based problems
• Open issues and future developments