EXPLORING INFEASIBILITY FOR ABSTRACTION-BASED HEURISTICS

Fan Yang

Infeasible heuristics are heuristic values that cannot be the optimal solution cost. Detecting infeasibility is a useful technique (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 infeasibility 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 heuristics? These questions guide us to explore infeasibility further. Comparative experimental results show the potential benefits of this technique.

Subjects: 15.7 Search; 1.8 Game Playing

Submitted: May 4, 2008


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.