Petri Net Relaxation for Infeasibility Explanation and Sequential Task Planning
This addresses the need for robust planning systems that can handle infeasibilities and updates, particularly for sequential task planning, though it appears incremental in nature.
The paper tackles the problem of detecting infeasible plans and explaining why they cannot be achieved, proposing a Petri net reachability relaxation method that detects up to 2 times more infeasibilities compared to baselines while performing competitively in one-shot planning.
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.