# Petri Net Relaxation for Infeasibility Explanation and Sequential Task Planning

arXiv: https://arxiv.org/abs/2602.22094 · HTML: https://mlsanity.com/paper/2602.22094/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 84 references that are in the map.
- First posted on arXiv 25 Feb 2026.

## Builds on (most cited first, 5 of 5)

- [Parallelizing the dual revised simplex method](https://mlsanity.com/paper/1503.01889/) (2015)
- [Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient](https://mlsanity.com/paper/2106.04756/) (2021)
- [RADAR-X: An Interactive Mixed Initiative Planning Interface Pairing Contrastive Explanations and Revised Plan Suggestions](https://mlsanity.com/paper/2011.09644/) (2020)
- [A Comparative Study of SMT and MILP for the Nurse Rostering Problem](https://mlsanity.com/paper/2505.10328/) (2025)
- [Planning with Dynamically Changing Domains](https://mlsanity.com/paper/2508.02697/) (2025)

## Abstract (arXiv)

Plans often change due to changes in the situation or our understanding of the situation. Sometimes, a feasible plan may not even exist, and identifying such infeasibilities is useful to determine when requirements need adjustment. Common planning approaches focus on efficient one-shot planning in feasible cases rather than updating domains or detecting infeasibility. We propose a Petri net reachability relaxation to enable robust invariant synthesis, efficient goal-unreachability detection, and helpful infeasibility explanations. We further leverage incremental constraint solvers to support goal and constraint updates. Empirically, compared to baselines, our system produces a comparable number of invariants, detects up to 2 times more infeasibilities, performs competitively in one-shot planning, and outperforms in sequential plan updates in the tested domains.