Automated Planning and Scheduling

Classical planning assumes an environment that is fully observable, deterministic, static (the world doesn't change except through the agent's own actions), and made of discrete states and finite actions — a restrictive but tractable setting in which a planner's job is to find a sequence of actions transforming a known initial state into a state satisfying a specified goal. The foundational representation for this setting is STRIPS, introduced by Richard Fikes and Nils Nilsson at SRI in their 1970 technical note and 1971 journal paper, which represented each action by a precondition (the set of facts that must hold for the action to be applicable), an add list (facts the action makes true), and a delete list (facts the action makes false). This precondition/add/delete structure let a planner reason about an action's effects purely symbolically, without re-deriving them from first principles through full theorem proving each time, which was the key efficiency innovation over prior approaches.

Trace a small blocks-world plan by hand: blocks A, B, and C sit on a table, with C currently stacked on A, and the goal is to have A stacked on B, with B still on the table. The first applicable action is Unstack(C, A) — its precondition (C is on A, C is clear, the gripper is empty) is satisfied by the initial state, so its effects fire: the add list contributes 'C is on the table' and 'gripper is holding C,' while the delete list removes 'C is on A' and 'gripper is empty' from the world description. Once C is clear of A, the action Stack(A, B) becomes applicable — its precondition (A is clear, B is clear, gripper is holding A) is now satisfied — and its effects add 'A is on B' and 'gripper is empty' while deleting 'A is on the table' and 'gripper is holding A.' Two actions in sequence, Unstack(C, A) then Stack(A, B), transform the initial state into one satisfying the goal, and at every step the planner needed only to check the small, explicit precondition list against the current facts rather than re-deriving from scratch whether the action was legal.

This add-list/delete-list bookkeeping generalizes cleanly to much larger domains with dozens of object types and hundreds of possible actions, and it is why STRIPS-style representations remain the conceptual basis of virtually all classical planning systems used today, including automated logistics and supply-chain routing, robot task planning, spacecraft operations scheduling, and even planning-based approaches to automatically configuring software systems, despite the original paper predating modern computing hardware by half a century. The lasting influence of Fikes and Nilsson's representation is a reminder that a well-chosen data structure — here, three simple lists per action — can outlast the specific algorithms originally built around it by decades, since later planners kept the precondition/add/delete structure even as the search procedures operating over it were repeatedly reinvented. What STRIPS deliberately left out is just as important as what it included: by assuming a closed world (anything not explicitly stated true is false) and by ignoring concurrent or continuous effects, it traded away expressiveness for tractability, a trade-off later languages like PDDL and ADL would selectively relax.

As planning research matured beyond individual research groups' ad hoc representations, the field needed a standardized, machine-readable syntax so that different planners could be compared fairly on the same benchmark problems rather than each research group hand-encoding problems in an incompatible, homegrown format. The Planning Domain Definition Language (PDDL), specified by McDermott and colleagues for the 1998 International Planning Competition (AIPS-98), filled this role by separating a planning task into a domain file (declaring the predicates and actions available in that world, each action given as a STRIPS-like precondition and effect written in a Lisp-like syntax) and a problem file (declaring the specific objects, initial state, and goal for one instance of that domain). Because the domain file captures everything general about a world — the warehouse-robot domain's Load, Unload, and Move actions, for instance — the same domain definition can be paired with any number of different problem files, each specifying a different starting arrangement of crates and a different target arrangement. This domain/problem separation is precisely why PDDL has become the lingua franca for planning competitions and research comparisons across decades of subsequent planners, each of which can be benchmarked on identical, publicly shared problem sets.

Beyond simple state-space search over STRIPS actions (searching forward from the initial state or backward from the goal), the planning graph offers a compact structure for extracting strong heuristics or, in algorithms like GraphPlan, for directly searching for a plan. A planning graph is built in alternating levels: a proposition level listing facts that could possibly hold after a given number of time steps, followed by an action level listing actions whose preconditions could be satisfied at that point, followed by the next proposition level generated by those actions' effects, and so on, growing outward level by level from the initial state. Crucially, the graph also tracks mutual exclusion (mutex) relations — pairs of actions or propositions that can never coexist at the same level, such as two actions with directly conflicting effects, two actions where one's precondition is deleted by the other's effect, or a proposition and its own negation — which let the planner recognize early, cheaply, and without any search at all, that certain goal conjunctions simply cannot yet be achieved at a given level.

This level-by-level structure gives a natural, admissible-in-spirit distance estimate: the first level at which a goal proposition appears (without being mutex with the other goal propositions also required at that level) provides a lower bound on how many plan steps are needed to reach the goal, since no shorter plan could possibly have produced that proposition any earlier. Planning-graph-derived heuristics exploit this lower bound to guide state-space search far more effectively than an uninformed search would manage on its own, by letting the search algorithm estimate, for any partial plan, roughly how much further work remains before the goal can plausibly be reached, and preferring to expand the states whose estimated remaining distance is smallest. The GraphPlan algorithm pushes this idea further still, alternating between extending the planning graph forward by one more level and then searching backward from the goal level for a valid, mutex-free set of actions achieving it, stopping as soon as such a set is found — an approach that was, for a period, dramatically faster than the state-space planners that preceded it precisely because so much of the reasoning about which actions could conflict was pushed into the graph's cheap, level-by-level construction rather than into expensive backtracking search.

Flat STRIPS-style planning, reasoning directly in terms of primitive actions, becomes unwieldy for realistic problems with hundreds of steps, because the search space of primitive-action sequences grows enormously as problem size increases. Hierarchical planning addresses this by introducing high-level actions (HLAs) that stand for entire sub-plans, refined recursively into either further HLAs or eventually primitive actions — an approach formalized in hierarchical task network (HTN) planning, where a planner reasons first at an abstract level ('deliver package,' refined later into 'navigate to pickup,' 'load package,' 'navigate to destination,' 'unload package') and only expands detail where it's needed, letting the same abstract plan be validated for correctness before any of its refinements are computed in full. This mirrors how a human project manager plans a large undertaking: first at the level of milestones, only later filling in the specific tasks and dependencies beneath each milestone, so that a flawed high-level strategy can be caught and revised long before time is spent working out its low-level details.

Once a valid sequence (or partial order) of actions exists, a second, distinct problem remains: scheduling that plan against limited, shared resources such as machines, personnel, or — in the warehouse-robot scenario — a single forklift that cannot serve two crates at once. The common 'plan first, schedule later' approach treats plan generation (deciding what to do and in what order, respecting logical dependencies such as one crate needing to be moved before the bay beneath it can be accessed) and scheduling (deciding exactly when to do each step, respecting resource and time constraints such as forklift availability) as separable phases, since the planning problem determines a partial order of necessary steps while scheduling then allocates those steps to specific time windows and resources without needing to revisit whether the underlying plan itself is logically sound. This separation is a pragmatic simplification rather than a logical necessity — in principle, resource constraints could be folded directly into the planning representation itself — but keeping the two concerns apart makes each one individually far more tractable to solve well.

For the scheduling phase specifically, the critical path method (CPM) is a standard technique: given a set of tasks with known durations and precedence constraints (some tasks must finish before others can start), CPM computes the longest chain of dependent tasks from start to finish — the critical path — which lower-bounds the total project duration, since any delay along that specific chain delays the whole project by exactly the same amount. Tasks that lie off the critical path, by contrast, have slack: extra time within which they can be delayed or rescheduled without pushing back the overall completion date, which is why a scheduler facing limited resources like a single forklift should protect the critical-path tasks' timing first and use whatever slack exists elsewhere to absorb resource conflicts. In the warehouse example, if unloading crate A onto the truck depends on crate B first being moved out of the way, that dependency chain is a candidate for the critical path, while a third, independent crate C with generous slack could be rescheduled around the forklift's availability without affecting how soon the overall job finishes.