J.L. Pérez de la Cruz, L. Mandow and E. Machuca (2013) "A Case of Pathology in Multiobjective Heuristic Search", Volume 48, pages 717-732

PDF | PostScript | doi:10.1613/jair.4100

This article considers the performance of the MOA* multiobjective search algorithm with heuristic information. It is shown that in certain cases blind search can be more efficient than perfectly informed search, in terms of both node and label expansions.

A class of simple graph search problems is defi ned for which the number of nodes grows linearly with problem size and the number of nondominated labels grows quadratically. It is proved that for these problems the number of node expansions performed by blind MOA* grows linearly with problem size, while the number of such expansions performed with a perfectly informed heuristic grows quadratically. It is also proved that the number of label expansions grows quadratically in the blind case and cubically in the informed case.

Click here to return to Volume 48 contents list