When Plans Break: Relaxing Petri Nets for Smarter Sequential Planning

Plans fail in painfully ordinary ways.

A warehouse robot cannot both reserve the last pallet slot and keep the aisle clear. A field-service schedule cannot satisfy every customer window after one technician calls in sick. A compliance workflow cannot approve a transaction before the missing document exists, no matter how passionately the dashboard insists on “urgent priority.”

The usual planning question is: What is the next valid plan? Useful, certainly. But in many operational settings, the more expensive question arrives first: Is the requested plan even possible? And if not, which requirements are fighting each other?

That is the practical center of “Petri Net Relaxation for Infeasibility Explanation and Sequential Task Planning” by Nhat Le, John G. Rogers, Claire N. Bonial, and Neil T. Dantam.¹ The paper is not simply another entry in the long contest of “planner A is faster than planner B on benchmark C.” There is some of that, because academia is still academia. But the more interesting contribution is diagnostic: the authors use a Petri net representation and a linear programming relaxation to identify unreachable goals, synthesize mutex invariants, and explain infeasibility through conflicting goal conditions. Then they connect that preprocessing to incremental SMT/MILP solving so related planning problems can be updated without throwing away all prior work.

The key misconception to kill early is this: a relaxed LP planner is not a magic shortcut that directly returns valid plans. The relaxation is deliberately optimistic. If the LP says a goal might be reachable, the real planning problem may still fail because ordering constraints can break the apparent solution. But if the LP says a goal is impossible, that impossibility is meaningful. In this paper, feasibility is weak evidence; infeasibility is the sharp instrument.

That distinction is where the business relevance begins.

The paper changes the planning question from “find a plan” to “diagnose the plan space”

Classical task planning often starts with a fixed model: states, actions, an initial condition, and a goal. The system searches for an action sequence that moves the world from the initial state to a goal state. Constraint-based planning encodes this as a satisfiability or optimization problem over a bounded horizon: at step 0, the initial state holds; at step $h$, the goal holds; between each pair of steps, some valid transition must explain the change.

This framing works well when the problem is feasible and the specification is stable. That is a pleasant world. Nobody lives there for long.

The paper studies sequential task planning: a sequence of related planning problems where users or environments revise the original request. Goals can change. Additional constraints can be added. A plan that was acceptable five minutes ago may now be invalid. A new user requirement may expose that the previous goal set was inconsistent all along.

The authors focus on two update types:

They do not claim to handle arbitrary changes to the entire domain model. Changes to state variables, preconditions, or action effects are acknowledged as more general but outside the efficient update path studied here. That boundary matters. The paper is about planning under structured revisions, not universal real-time model surgery.

Step one: translate grounded PDDL into a Petri net

The mechanism starts by converting a grounded PDDL planning problem into a Petri net.

In PDDL, the domain describes variables, actions, preconditions, effects, an initial state, and goals. In the Petri net view:

For Boolean variables, the paper distinguishes whether a variable appears only in an action precondition, only in an effect, or in both. For numeric variables, it constructs similar arc structures and also infers bounds when possible. For example, if a numeric variable is only increased and never decreased, its starting value gives a natural lower bound. If every action that decreases it requires the variable to exceed some threshold, that threshold can help infer a lower bound.

This conversion is not a cosmetic change of notation. It gives the authors a flow structure. Once actions become transitions and state variables become places, planning begins to look like the movement of tokens through a network. That opens the door to the relaxation.

A fully faithful Petri net reachability problem remains hard. No surprise there; planning did not become easy just because we drew circles and arrows. But the Petri net form allows a useful approximation: ignore some temporal ordering details and ask whether the aggregate flow from initial marking to final marking is even possible.

The relaxation is optimistic by design, which is exactly why infeasibility is useful

The core technical move is a linear relaxation of Petri net reachability.

Instead of asking whether there exists a valid ordered sequence of transitions, the relaxation asks whether the overall token/value balance can work out if we count how many times each transition fires. In simplified terms, it checks whether the final marking can be explained by the initial marking plus accumulated transition effects.

The paper’s key reachability relationship can be understood as:

Here, $m$ represents markings, $C$ is the incidence matrix describing how transitions affect places, and $x$ counts transition firings. The slack terms handle subtleties around Boolean rebinding under the authors’ generalized Petri net treatment.

This relaxation drops the exact ordering requirement. That is a serious loss. A set of transitions may balance in aggregate but still be impossible to order without making an intermediate resource negative, violating a precondition, or crossing a bound. So LP feasibility does not prove the real plan exists.

But the other direction is powerful. If even the relaxed flow cannot satisfy the target, then the original planning problem cannot either. The relaxed problem is easier than the real one. Failing the easier test means failing the harder task.

This is the paper’s most important interpretive hinge:

That asymmetry is useful in business systems because operations teams often need early rejection more than philosophical completeness. If a plan request cannot pass a cheap necessary condition, there is little point sending it into a heavier planner just to watch compute cycles quietly burn.

This is also why the word “relaxation” should not scare non-technical readers. A relaxation is not a sloppy approximation pretending to be truth. Used carefully, it is a filter. It asks: “Even if we give this plan extra freedom, can it work?” If the answer is no, the original request is dead. Very dead. Respectfully, but dead.

Mutex invariants turn impossible combinations into search constraints

The first application of the relaxation is invariant generation.

In planning, an invariant is a fact that holds across all reachable states. One common form is a mutual exclusion invariant, or mutex: two Boolean facts cannot be true at the same time. For example, a robot cannot be in two distinct rooms at once, unless the model is doing physics by committee.

The authors use the LP relaxation to test whether two places can both be true in any reachable marking. If the relaxed system cannot make them both true, then the original system cannot either. That gives a sound mutex invariant.

These invariants matter because constraint-based planners can use them to reduce the search space. Instead of allowing the solver to consider impossible combinations and rediscover their impossibility repeatedly, the planner can encode compact constraints such as “at most one of this group may hold.”

The experiments compare the paper’s invariant generation against Madagascar and Fast Downward on three classical combinatorial domains. The result is not that the Petri net relaxation dominates every baseline. The paper reports that all methods produce similar numbers of two-literal invariants. Madagascar produces slightly more; Fast Downward produces the same number as the authors’ approach.

That makes this section a main evidence test for validity and competitiveness, not the paper’s strongest claim of superiority. The point is that the relaxation-based method can generate comparable invariants while fitting into a broader framework that also handles numeric domains and infeasibility explanations.

The business reading should be modest: this is not “a new invariant engine crushes old planners.” It is closer to: “the same relaxation used for diagnosis can also produce useful planner constraints.” That is less dramatic, and therefore more likely to be true.

Infeasibility explanations are the operationally valuable part

The paper’s second application is more distinctive: infeasibility detection and explanation.

The authors define an infeasibility explanation as a minimal set of goal conditions that causes the relaxed constraints to become infeasible. If the full goal is impossible, the system searches for smaller subsets of goal clauses that are already mutually unreachable. With few goal conditions, combinations can be enumerated. With many, the paper describes an integer programming formulation that disables goal conditions and minimizes the number disabled, then searches for alternative inconsistent sets.

This matters because planners often fail in ways that are useless to users. “No plan found” is technically honest and operationally irritating. A manager does not only need to know that the schedule failed; she needs to know whether the failure came from the delivery window, the staffing rule, the route restriction, the inventory constraint, or the brilliant late-stage executive requirement added in the meeting.

The paper’s explanations stay close to the original planning domain by focusing on conflicting goal conditions rather than exposing every transformed internal constraint. That is a sensible product decision disguised as a technical choice. Users usually do not want to debug the solver’s private algebra. They want to know which requested outcomes cannot coexist.

In the infeasibility experiments, the authors evaluate classical problems from Unsolvability IPC 2016 and auto-generated unsolvable numeric Delivery and Counter problems. Each tested domain has 10 problems of increasing size, under a 10-minute timeout and 8 GiB memory limit.

The detection count table is one of the clearest empirical results:

The authors’ Gurobi-backed approach detects 48 infeasibilities out of 50, with Z3 detecting 46. ENHSP SAT detects 34. FF BFS+H detects 32. Fast Downward detects 20, but only across the classical domains in this setup. Madagascar detects none in the table.

This is main evidence for the infeasibility-detection claim. It also hints at why numeric planning is an important test case: some classical planners do not support the numeric domains used here, while the Petri net relaxation is designed to cover Boolean, integer, and real-valued places.

The boundary is equally important. The result says the LP relaxation is empirically strong on these tested unsolvable domains. It does not say every infeasible planning problem will be caught. Because the relaxation is optimistic, some impossible real planning problems may still look feasible to the LP. Those cases then require heavier planning search or other proof methods. The paper’s contribution is a robust early detector, not an oracle wearing a lab coat.

Incremental solving makes updates cheaper only after there is something to reuse

The third mechanism is incremental planning with SMT and MILP solvers.

Constraint-based planners often solve a bounded-horizon problem, then increase the horizon until a plan is found. The paper supports both SMT and MILP formulations. For SMT, the authors emphasize per-check assumptions rather than relying only on assertion-stack push/pop behavior, because solvers may retain learned information differently depending on how constraints are added and removed. For MILP, they translate logical expressions into linear constraints using CNF-style transformations and indicator constraints or Big-M formulations where needed.

The sequential planning story then follows naturally:

1. Translate the planning domain into a Petri net.
2. Use relaxation-based preprocessing for invariants, infeasibility checks, and reachable sets.
3. Solve the planning problem through SMT or MILP constraints.
4. When goals change or constraints are added, reuse what remains valid.
5. Recompute only the parts that the update invalidates.

For changing goals, the Petri net itself remains unchanged. The relaxation and invariants remain valid; backward reachability and goal checks may need recomputation. The updated goal conditions become per-check assumptions.

For added constraints, more must be recomputed: invariants, goal reachability, and reachable sets under the new restrictions. Still, the constraint solver can reuse prior structure and, in the Gurobi case, warm-start from a previous solution.

This is the mechanism behind the sequential planning result. It is not that the solver suddenly becomes brilliant. It stops pretending each revision is a brand-new universe.

The sequential experiments compare one-shot planning and cumulative time over update sequences. For one-shot numeric planning, performance is domain-dependent. The authors’ approach outperforms FF in Block Grouping, Counters, Sailing, and Sugar, and outperforms ENHSP SAT in Sugar. But one-shot planning is not the main thesis, and the paper does not pretend otherwise.

The stronger result is sequential. The authors benchmark randomly generated update sequences in Block Grouping and Counters, with 30 updates per sequence. TMKit Gurobi has higher initial cost in some cases, but cumulative planning time is lower than the baselines in most tested sequences. Some baselines also cannot handle constraint-addition updates because they lack support for PDDL global constraints.

This is main evidence for the sequential planning claim, with an implementation-related interpretation: incremental solving and warm starts reduce repeated work across related planning problems.

The business translation is straightforward. If a workflow planner is used once, overhead matters. If the same planning problem is revised repeatedly—as in dispatching, warehouse operations, robotic execution, field service, maintenance scheduling, or compliance workflows—reuse becomes valuable. A slower first plan may still be worthwhile if every subsequent revision is cheaper.

Naturally, the first plan must still finish. Warm starts do not help before the system has warmed anything. Apparently, time remains linear and vendors have not yet patched causality.

What the evidence supports, and what it does not

The paper’s empirical section is easiest to understand if we separate the tests by purpose.

This separation matters because a normal paper summary would flatten all results into “the method performs better.” That would be lazy. The evidence is more specific:

• The invariant result shows the method is competitive as preprocessing.
• The infeasibility result is the strongest differentiator.
• The one-shot result is mixed but useful.
• The sequential result supports the paper’s operational thesis: repeated planning updates benefit from reuse.
• The limitations restrict where the method should be positioned.

For business readers, that means the technology is most interesting not as a generic replacement planner but as a planning-diagnosis and replanning layer.

Business value: cheaper diagnosis, not just faster planning

The most useful business interpretation is not “LP makes planning faster.” That is too broad and partly wrong.

A better interpretation is:

Petri net relaxation can act as an early diagnostic layer for planning systems, especially when requirements change and infeasible goal combinations need to be explained before expensive replanning begins.

That has several practical consequences.

First, systems can reject impossible requests earlier. In operations software, an infeasible request often travels too far down the pipeline: from UI to planner, from planner to exception handler, from exception handler to human escalation. Early infeasibility detection compresses that loop.

Second, explanations can shift user behavior. If the system says “no plan found,” users may keep tweaking random inputs. If it says “these three goal conditions cannot coexist,” users can revise the right part of the request. The paper’s minimal conflicting goal sets are not full causal narratives, but they are far more actionable than silence.

Third, sequential updates are the normal case in many businesses. The same plan is revised as new orders arrive, resources disappear, constraints tighten, or humans remember requirements they definitely should have mentioned earlier. Incremental solving fits this reality better than treating every revision as a one-shot planning contest.

Fourth, the approach is relevant beyond robotics. The paper’s examples and implementation context connect to planning research, but the abstraction applies to business processes wherever actions, preconditions, resources, and goals can be modeled explicitly: warehouse workflows, approval routing, staff scheduling, fleet dispatch, automated procurement, emergency response coordination, and constrained service delivery.

Still, the inference from paper to business use must be kept disciplined.

The ROI case is therefore clearest in systems where three conditions hold: infeasibility is common, revisions are frequent, and explanations reduce human rework. If a system mostly solves easy one-shot feasible plans, this approach may add overhead without much payoff. There is no shame in using a hammer for nails and not for soup.

Deployment boundaries: where the method can bite back

The paper is careful about limitations, and the practical reader should be too.

The first boundary is numerical reliability. The PN relaxation depends on LP infeasibility checks. Floating-point error can lead to spurious infeasibilities. Rational arithmetic, as in SMT solvers, can avoid floating-point error but may cost more computation. Domains involving irrational coefficients or nonlinear functions remain outside the comfortable zone.

The second boundary is grounding scale. The method works on grounded or propositionalized planning domains. Large numbers of grounded state variables can make constraint-based planning difficult. Long horizons also remain challenging. The paper does not solve the old explosion problem; it uses structure and relaxation to make important parts cheaper.

The third boundary is update type. The sequential planning method focuses on changing goals and adding constraints. Those are common and useful, but they are not the full universe of operational change. If the action model itself changes—new action schemas, changed preconditions, altered effects—the reuse story becomes more complicated.

The fourth boundary is first-solve overhead. Incremental solving helps after prior work exists. In the experiments, FF can outperform the authors’ system on the smallest Counters case. That is not an embarrassing exception; it is a reminder that heavy machinery is not free. For small, easy problems, a heuristic planner may win because it simply starts lighter.

The fifth boundary is explanation scope. Minimal conflicting goal sets are helpful, but they are not the same as a polished business explanation. A production system would still need to translate goal clauses into user-facing language, rank repair options, and perhaps suggest alternative feasible goal sets. The paper gives the diagnostic core, not the whole product layer.

The more interesting planner is the one that says “no” well

This paper is valuable because it treats planning failure as information.

Many AI planning discussions still revolve around plan generation: how to find the sequence, how fast to find it, how optimal it is. Those questions remain important. But in deployed systems, failed and revised plans are not edge cases. They are the daily texture of work. The model is incomplete. The user forgot a constraint. The resource disappeared. The goal bundle was inconsistent from the start. Reality, as usual, declined to respect the specification.

By converting grounded PDDL domains into Petri nets, relaxing reachability into an LP, using infeasibility as a sound signal, extracting conflicting goal sets, and then reusing solver work across structured updates, the paper offers a mechanism for planning systems that diagnose as well as search.

That mechanism-first view is essential. Without it, the contribution looks like a planner benchmark. With it, the paper becomes a design pattern for business automation: put a cheap, sound impossibility filter before expensive planning; explain conflicts in the language of goals; and reuse reasoning when users revise the problem instead of starting from zero every time.

The future of planning systems will not belong only to the fastest system that can produce a plan when everything is clean. It will also belong to systems that can say, precisely and early, “these requirements cannot coexist.” Not glamorous. Very useful. A surprisingly large share of enterprise software could use the habit.

Cognaptus: Automate the Present, Incubate the Future.