Italian Researchers Cut AI Planning's Exponential State Space Blowup in Half
Researchers carve out an 'eager' fragment of timeline-based planning that skips the exponential determinization step and directly synthesizes strategies.
- New paper defines an 'eager' fragment of qualitative timeline-based planning that avoids costly determinization.
- Plan-existence maps directly to DFA nonemptiness, enabling strategy synthesis of singly exponential size.
- Characterizes the maximal subset of Allen's 13 interval relations compatible with the deterministic fragment.
- Proves non-eager problems cannot be captured by any exponential-size DFA, showing the boundary is tight.
- Shows BPMN business process diagrams can be encoded into the eager fragment for controller synthesis.
- Theoretical work, no code or benchmarks released, but gives a clear recipe for practitioners.
An arXiv paper by researchers in Italy defines an eager fragment of qualitative timeline-based planning that compiles directly into a deterministic finite automaton, or DFA. The construction produces a singly exponential automaton and removes the general determinization step that can create a doubly exponential state space.
Engine developers gain a precise boundary for using deterministic monitors in plan and controller synthesis. Problems inside the fragment receive a direct DFA construction; problems outside it may require nondeterministic tracking, a larger deterministic representation, or a different solver.
Why nondeterminism gets expensive
Timeline-based planning models a domain as state variables that evolve concurrently. Each variable produces a sequence of tokens, where a token represents a value held over an interval. Local transition rules constrain successive values, while synchronization rules relate tokens across timelines through endpoint ordering and interval relations.
Qualitative planning uses temporal order instead of numeric duration bounds. A synchronization rule might require one token to begin after another ends, share an endpoint with it, overlap it, or remain contained within it. A plan is a collection of timelines that satisfies every local transition and synchronization constraint.
Plan existence for the general qualitative formalism is PSPACE-complete. Earlier membership proofs encode candidate plans as words and reduce existence to nonemptiness for a nondeterministic finite automaton, or NFA. The NFA can guess which token witnesses each existential requirement in a synchronization rule.
Strategy synthesis needs a definite monitor state for every observed plan prefix. An NFA may retain several possible runs, including guesses whose validity depends on later events. Standard subset construction records all those runs as one DFA state. When the NFA is already singly exponential in the planning instance, determinization can yield a doubly exponential DFA.
This story is for Pro members
You've reached the end of the free preview. Upgrade to AlphaSignal Pro to read the full article - and everything else behind the paywall.
Comments
