Compliant Conditions for Polynomial Time Approximation of Operator Counts
This work addresses computational bottlenecks in planning domains for researchers and practitioners, though it appears incremental as it builds on existing heuristics.
The paper tackles the computational complexity of the operator count heuristic by developing a polynomial-time approximation method using Lagrangian dual and compressed sensing techniques, achieving efficient computation for a specific class of domains.
In this paper, we develop a computationally simpler version of the operator count heuristic for a particular class of domains. The contribution of this abstract is threefold, we (1) propose an efficient closed form approximation to the operator count heuristic using the Lagrangian dual; (2) leverage compressed sensing techniques to obtain an integer approximation for operator counts in polynomial time; and (3) discuss the relationship of the proposed formulation to existing heuristics and investigate properties of domains where such approaches appear to be useful.