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.
Figures & tables
Figure 1: Petri net structure for PDDL preconditions and effects. (a) variable in precondition (not in effect). (b) variable in effect (not in precondition). (c) variable in precondition and effect.
Figure 2: Two-literal invariants from our PN relaxation and baselines. All methods produce similar numbers of invariants.
Figure 3: Average infeasibility detection times over 10 iterations and counts. Absent data points exceeded a 10 -minute timeout or 8GiB memory limit. Dashes in the table indicates unsupported numeric domains for Mp and FD.
Figure 4: Average one-shot planning times over 10 iterations. The figures show the numbers of instances solved over time in numeric domains. Excluded data points exceeded the 10 -minute timeout or 8GiB memory limit.
Figure 5: Average cumulative planning times over 10 iterations for sequential planning. TMKit Gurobi outperforms the baselines in most sequences. Excluded data points exceeded the 30 -minute timeout or 8GiB memory limit.