Planning and scheduling

Planning and scheduling are classic problems in artificial intelligence. Some but workers take planning and scheduling to be synonymous; others do not.

Standards

PDDL is a series of standard for specifying symbolic planning problems.

  • McDermott et al, 1998: PDDL—Planning Domain Definition Language (pdf)
  • Helmert, slides: An introduction to PDDL (pdf)
  • Veloso, 2002, slides: PDDL by example (pdf)

PDDL is best regarded as a syntactical language as its formal semantics seems to be ad hoc and incomplete:

  • Fox & Long, 2003: PDDL2.1: An extension to PDDL for expressing temporal planning domains (doi)
    • First formal semantics for a PDDL language
  • McDermott, 2003: The formal semantics of processes in PDDL (pdf)

Literature

Books and surveys

  • Russell & Norvig, 2021, AI: A Modern Approach, 4th ed. (website ), Ch. 11: Automated planning
  • Ghallab, Nau, Traverso, 2004: Automated planning: Theory and practice (webpage )
    • The standard textbook for symbolic planning
  • Ghallab, Nau, Traverso, 2016: Automated planning and acting (webpage )

Hierarchical planning

Hierarchical planning, or more accurately hierarchical task network (HTN) planning, is one the most popular planning methods.

  • Ghallab, Nau, Traverso, 2004, Ch. 11: Hierarchical task network planning
  • Georgievski & Aiello, 2014: An overview of hierarchical task network planning (arxiv)
  • Nau et al, 2003: SHOP2: An HTN planning system (doi, arxiv)
    • Now considered the prototypical HTN planner, state-of-the-art at its time
    • New version: Goldman & Kuter, 2019: Hierarchical task network planning in Common Lisp: the case of SHOP3 (doi, pdf, GitHub )

HTNs in robotics:

  • Hayes & Scassellati, 2016: Autonomously constructing hierarchical task networks for planning and human-robot collaboration (doi, pdf)

Planning using graphs

How to create a plan or schedule from a dependency graph, typically a DAG:

  • Cordasco & Rosenberg, 2014: On scheduling series-parallel DAGs to maximize AREA (doi)
    • Cordasco, De Chiara, Rosenberg, 2014: An AREA-oriented heuristic for scheduling DAGs on volatile computing platforms (doi)
    • Rosenberg, 2016: Scheduling DAGs opportunistically: The dream and the reality circa 2016 (doi)
    • …and many other papers, seemingly indistinguishable from each other

An important concept here, with connections to graph drawing, is the series-parallel graph :

  • Bang-Jensen & Gutin, 2009: Digraphs, Ch. 2: Classes of digraphs (doi), Sec. 2.6: Series-parallel digraphs
  • Di Battista et al, 1999: Graph drawing, Sec. 3.2: Series-parallel digraphs
  • Mitchell, 2004: Creating minimal vertex series parallel graphs from directed acyclic graphs (acm , pdf)
  • Valdes, Tarjan, Lawler, 1982: The recognition of series parallel digraphs (doi)
    • Conference version: Valdes, Tarjan, Lawler, 1979: The recognition of series parallel digraphs (doi)
  • Duffin, 1965: Topology of series-parallel networks (doi)
    • Introduces series-parallel graphs as a model of electrical networks

Category theory for planning

Categorical logic and databases, monoidal categories, and other concepts of applied category theory have been used in planning.

  • Master, Patterson, Yousfi, Canedo, 2019: String diagrams for assembly planning (doi, arxiv)
  • Breiner, Denno, Subrahmanian, 2020, in AMS Notices: Categories for planning and scheduling (doi)