Methods and apparatus to provide techniques for planners that records constraints over a set of numeric state variables for each fact and characterizes the set of states in which that fact is true to provide more information to reason about mutual exclusions among sets of states offering a tighter bound on the metric cost of a plan than existing planners currently attain. This more accurate estimate can avoid irrelevant states and decrease search times.