Unsolvable by Design: Turning AI Plans Into Security Guarantees

Failure should be boring

Approval workflows are supposed to be boring. A client submits documents, a system checks the required conditions, and an approval either happens or does not happen. Boring is good. Boring means the process does not accidentally approve a case while also escalating it as problematic.

The trouble begins when a workflow is written as a best-effort model of reality. Someone encodes the actions. Someone else adds an exception. A third person adds a shortcut because the quarterly dashboard prefers speed over philosophy. Eventually, a sequence exists that should not exist. It does not look like a bug when inspected locally. Each action seems defensible. The path as a whole is the problem.

That is the setting of Planning Task Shielding: Detecting and Repairing Flaws in Planning Tasks through Turning them Unsolvable, an arXiv paper by Alberto Pozanco, Marianela Morales, Pietro Totis, and Daniel Borrajo from J.P. Morgan AI Research.¹ The paper’s most useful idea is not that AI planning can find a path to a goal. That part is old news. The sharper idea is that planning can be turned inside out: define the dangerous state as the “goal,” find the paths that reach it, then minimally change the action model until that goal has no solution.

This is a small conceptual inversion with large practical consequences. Most safety discussions ask whether an AI system is likely to behave well. This paper asks a more surgical question: can the bad state be made unreachable under the formal model?

That is a colder, less inspirational question. Conveniently, it is also more useful.

The paper is not looking for a better plan

The first misconception to remove is simple: this is not a method for finding a safer plan. It is a method for making certain plans impossible.

Classical planning starts with a tuple usually written as $P = \langle F, A, I, G \rangle$:

In ordinary planning, $G$ is desirable. A robot reaches the warehouse shelf. A scheduler assigns the shifts. A logistics system finds the delivery sequence.

In planning task shielding, $G$ is deliberately undesirable. It is a property that should never hold. In the paper’s running example, the flawed condition is a workflow state where an application is both approved and escalated. The plan that reaches it is not an achievement. It is evidence that the system design permits a bad trace.

This shift changes the meaning of solvability. In normal planning, solvable means “good, we found a way.” In shielding, solvable means “bad, there is a vulnerability.” The desired result is unsolvability: no action sequence can reach the forbidden state.

The operational lesson is easy to miss. A planner can be used not only as a generator of actions, but as a detector of reachable failures. Once the failure is reachable, the repair task becomes: what is the smallest change to the action model that blocks every failure path?

Planning task shielding changes the system, not the alarm

The paper defines a shielding solution as a new set of actions $A’$ such that the modified planning task $P_S = \langle F, A’, I, G \rangle$ becomes unsolvable. It does not change the initial state. It does not redefine the forbidden goal. It changes the dynamics: what actions require, what they add, and what they delete.

That choice matters because it keeps the safety property fixed. A weak compliance system can always become “safe” by quietly redefining the violation. Very elegant. Also useless. Here, the bad state remains the bad state. The model must be altered so that the bad state can no longer be reached.

The allowed repairs are restricted to three types:

These are not arbitrary edits. The paper proves a monotonicity result: if actions are modified only in these ways, the number of solution plans cannot increase. In less formal terms, each allowed change can close doors but cannot open new ones.

That is the mechanism that makes the repair problem manageable. The algorithm does not need to consider every possible redesign of the domain. It can focus on edits that shrink the space of paths to the flawed state.

There is also a practical constraint hidden inside this neatness: if the forbidden goal already holds in the initial state, modifying actions cannot help. If the process starts in violation, no amount of future gatekeeping can make the empty plan disappear. Some messes are not workflow bugs. They are initial-condition bugs.

ALLMIN turns failure paths into a hitting problem

The paper’s algorithm, ALLMIN, works in two stages.

First, it computes the set of simple, loopless plans that reach the flawed goal. Second, it solves a Mixed-Integer Linear Program, or MILP, that selects the minimum set of action modifications needed to block every one of those plans.

The mechanism is easier to understand as a hitting problem. Imagine every failure path as a route through a building. You do not need to brick up every corridor. You need to close enough doors so that every route to the forbidden room is interrupted at least once. If one door lies on many bad routes, closing it is efficient. If bad routes are independent, you need more closures.

ALLMIN formalizes that intuition. It introduces decision variables representing possible edits: whether to add a fluent as a precondition to an action, whether to remove a fluent from an action’s add effects, and whether to add a fluent to an action’s delete effects. It also tracks whether fluents hold at each step of each failure plan and whether each action remains executable after the proposed edits.

The objective is simple:

The constraints enforce state propagation, precondition satisfaction, and the critical blocking condition: every known failure plan must contain at least one action that is no longer enabled.

This is why the paper is more interesting than a patching heuristic. A local fix might block the first plan a planner finds while leaving another path open. ALLMIN looks across all enumerated failure traces and searches for a minimal global repair.

“Minimal” should not be romanticized. The paper counts modifications, not operational pain. Adding a precondition to a rarely used internal action and removing an effect from a critical approval action both count as one edit. The authors explicitly identify richer preferences over modification types and affected actions as future work. In business terms, the current objective minimizes a technical count, not yet a change-management cost function.

The approval example shows the business intuition

The paper’s toy approval workflow is useful because it resembles the kind of brittle process many firms actually run. A submit action marks an application complete. A direct approval action grants approval when the application is complete. An escalation action handles cases with client concerns.

A flawed state arises when a case can be both approved and escalated. The example plan is:

1. submit application;
2. escalation;
3. direct approval.

A human process owner might inspect this path and propose a patch: remove the escalation effect, or add safe_client as a precondition for direct approval. Either fix may make sense depending on the domain. But the paper’s point is that one hand-crafted patch is not enough if there are several paths into the same bad state.

This is where the mechanism becomes relevant to enterprise automation. Many risks in workflow systems are not caused by a single evil action. They are caused by harmless actions composing badly. The individual steps pass review. The sequence fails.

That is also why monitoring alone feels unsatisfactory. A monitor can notice that a forbidden combination happened. A runtime guard can catch some cases before execution. But shielding asks a more structural question: can the formal model itself be repaired so that the forbidden combination has no path?

For compliance-heavy workflows, that distinction is not academic. Detecting a breach after the process has found a route to it is not the same as proving that the route does not exist. One produces alerts. The other changes the design.

The experiments are preliminary, but they reveal the bottleneck

The evaluation has two parts: synthetic graph-based planning tasks and small standard planning benchmarks from Blocksworld, Rovers, and Satellite. The synthetic benchmark is the main evidence for the exact algorithm because it allows the authors to control the number and structure of failure-reaching plans. The standard benchmarks are better read as a stress test and scaling probe, not as a claim that the method is ready for broad planning benchmarks.

The authors evaluate exact ALLMIN and two bounded variants, ALLMIN$^{10}$ and ALLMIN$^{100}$, which compute only 10 or 100 plans instead of all simple plans. They use SYMK to enumerate plans and HiGHS to solve the MILP, then validate the returned modifications by calling SYMK again to check whether the modified task has no remaining plan.

The table results are worth reading carefully rather than heroically.

Exact ALLMIN solves all synthetic tasks, including the 16-plan and 32-plan groups. It fails to solve the standard benchmarks within the 1,800-second time limit because computing all simple plans is not feasible there. The bounded variants solve more instances because they avoid exhaustive enumeration, but their success is no longer guaranteed.

This is the central trade-off. If you enumerate all failure-reaching plans, you can give a stronger guarantee, but the computation may fail to finish. If you enumerate only some plans, the method becomes faster, but the returned repair may leave unobserved bad paths intact.

The synthetic results also show why the method is not merely “one patch per bad plan.” In the 32-plan synthetic tasks, exact ALLMIN averages 21.4 modifications, fewer than the 32 failure paths. That means the optimizer is finding shared actions or shared facts that allow one modification to invalidate multiple paths. This is precisely the kind of compression a business process owner would want: do not patch thirty-two symptoms if twenty-one structural edits close the space.

Still, the runtime story is blunt. The authors report that execution time rises from fractions of a second on small synthetic instances to 66.4 seconds on the 32-plan synthetic cases for ALLMIN$^{100}$ and exact ALLMIN. In the broader analysis, the MILP becomes the dominant cost. The planner finds paths; the optimizer pays the bill.

As usual, the invoice arrives after the architecture meeting.

The business value is design-time assurance, not runtime supervision

The practical value of planning task shielding is clearest in domains where three conditions hold.

First, the process can be represented as deterministic actions over explicit state facts. That is plausible for approval workflows, access-control processes, API orchestration, compliance checks, and some agentic tool-use pipelines. It is less plausible for open-ended conversations, learned policies, or environments where state is ambiguous and continuously changing.

Second, the dangerous state can be specified clearly. “A restricted customer receives approval,” “a payment is released without dual authorization,” or “an agent deletes production data without a valid rollback condition” are candidates. “The system behaves in a reputationally awkward way” is not a crisp planning goal. Unfortunately, the legal department may still try.

Third, the number of meaningful paths to the bad state should be small enough, or structured enough, that enumeration and optimization remain useful. The paper explicitly motivates the synthetic benchmark by arguing that practical flawed states may have only a few reaching paths, unlike standard planning benchmarks that often contain hundreds of thousands of plans. That assumption is plausible for narrowly scoped enterprise processes, but it is an assumption, not a theorem.

If those conditions hold, the business interpretation is strong:

This points to a useful role for the method even before full automation. It can act as a diagnostic engine. Given a workflow model and a forbidden state, enumerate dangerous traces, propose minimal structural edits, and show process owners where the model is fragile.

The output would not replace human judgment. In fact, it would make judgment more focused. Instead of asking, “Does this policy look safe?” the organization can ask, “Which exact action effect or missing precondition allows the forbidden trace?” That is a better meeting. Still a meeting, regrettably, but better.

This is closer to formal verification than to AI safety theater

Much of AI governance still lives in the land of dashboards, audits, red-team anecdotes, and policy documents. Those tools have value, but they often describe behavior after the system already exists. Planning task shielding belongs to a different family: design-time assurance.

The distinction is important for agentic systems. When an AI agent can call tools, trigger workflows, and chain actions, safety cannot depend only on whether individual actions look acceptable. The sequence matters. A tool call that is harmless in one state may be dangerous after another tool call has changed the system.

Planning models are naturally sequence-aware. That makes them attractive for reasoning about agent workflows where the action space is explicit: retrieve record, update field, request approval, transfer funds, revoke access, deploy code. In such systems, the risk is often not one forbidden action but a forbidden path.

Planning task shielding says: model that path, then close it structurally.

This is not a substitute for model alignment, runtime monitoring, access control, or human approval. It is a complementary layer. Its job is narrower and more rigorous: for a specified bad state, under a specified transition model, no plan should reach it.

Narrow and rigorous is underrated. Broad and vague has had an excellent marketing department for years.

The hard boundary is model faithfulness

The paper’s guarantee is formal, but it is formal inside a model. That boundary should be stated once, clearly, without sprinkling generic caution across every paragraph like compliance confetti.

Planning task shielding assumes a classical planning setup: explicit fluents, deterministic action dynamics, defined initial state, and specified goal condition. If the real system behaves differently from the planning model, the guarantee weakens immediately. A missing action, a hidden side effect, an incorrect precondition, or an unmodeled external event can reopen paths that the shielded model has closed.

There is also a scalability boundary. Exact ALLMIN needs all simple plans that reach the flawed state. The standard benchmark results show that exhaustive enumeration can time out even on small selected planning problems when the number of plans is large. The bounded variants are promising as practical heuristics, especially ALLMIN$^{100}$ in the reported experiments, but once only a subset of plans is considered, success must be validated rather than assumed.

Finally, the current objective treats every modification as one unit. A production system would need preferences: avoid changing legally mandated actions, prefer adding preconditions over deleting effects, penalize edits to high-volume workflows, or require human approval for certain classes of change. The paper names this direction in future work. It is not a footnote; it is probably the bridge from elegant algorithm to usable enterprise tool.

The real contribution is a change in question

The strongest part of the paper is not the benchmark table. The table is preliminary, and the authors are appropriately clear that scalability remains open. The stronger contribution is the formulation.

Instead of asking a planner to reach a good goal, the paper asks the planner to expose a bad one. Instead of stopping at detection, it asks for the smallest action-model changes that make the bad goal unreachable. Instead of trusting local patches, it blocks all enumerated traces through a global optimization problem.

That is the article’s mechanism-first takeaway: planning becomes a way to manufacture unsolvability on purpose.

For businesses adopting agentic systems, this matters because the next wave of operational risk will not always look like a single bad output. It will look like a valid sequence of individually reasonable steps that reaches a state nobody wanted. Planning task shielding offers a disciplined way to ask whether such a sequence exists and how to remove it with minimal structural disruption.

The method is not ready to certify every messy enterprise process. It is too dependent on explicit models, too sensitive to path explosion, and not yet aligned with real-world modification costs. But as a design pattern, it is valuable: define the failure, search for reachable traces, then redesign the action space until the failure has no route.

Failure should be boring. Ideally, it should also be unreachable.

Cognaptus: Automate the Present, Incubate the Future.