Exploring Infeasibility for Abstraction-Based Heuristics

Infeasible heuristics are heuristic values that cannot be the optimal solution cost. Detecting infeasibility is a useful tech-nique (Yang et al. 2008) to improve the quality of heuristics because it allows the heuristic value to be increased without risking it becoming inadmissible. However, extra memory is required when applying this technique. Is checking for in-feasibility the best way to use this extra memory? Can this technique be extended to problems with non-uniform edge costs? Can infeasibility only be detected for additive heuris-tics? These questions guide us to explore infeasibility further. Comparative experimental results show the potential benefits of this technique