The Two-Edged Nature of Diverse Action Costs

Diverse action costs are an essential feature of many real-world planning applications. Some recent studies have shown that diversity of action costs makes planning more difficult, and that searching using unit action costs can outperform searching the same domain with diverse action costs. In this paper, we provide experimental evidence and theoretical analysis showing that search can also benefit from action cost diversity. We show that on several IPC problems cost diversity has a positive effect (reduces search effort). We then present a theoretical analysis establishing that these positive cases are not accidental. Our main result is a "No Free Lunch" theorem showing that any negative effects of cost diversity are always perfectly counterbalanced by positive effects. Our theoretical analysis also shows that it is advantageous to have a strongly concentrated distribution of solution costs. In many domains, unit costs will give rise to a more concentrated distribution than diverse costs, but we give an example typifying domains in which the opposite is the case.