AAAI Publications, Ninth Annual Symposium on Combinatorial Search

Font Size: 
Compliant Conditions for Polynomial Time Approximation of Operator Counts
Tathagata Chakraborti, Sarath Sreedharan, Sailik Sengupta, T. K. Satish Kumar, Subbarao Kambhampati

Last modified: 2016-06-20


In this brief abstract, we develop a computationally simpler version of the operator count heuristic for a particular class of domains. The contribution of this abstract is thus threefold, we (1) propose an efficient closed form approximation to the operator count heuristic; (2) leverage compressed sensing techniques to obtain an integer approximation in polynomial time; and (3) discuss the relationship of the proposed formulation to existing heuristics and investigate properties of domains where such approaches are useful.


operator count, Lagrangian, sparse coding

Full Text: PDF