A Case of Pathology in Multiobjective Heuristic Search
Abstract
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 defined 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.
Cite
Text
Pérez-de-la-Cruz et al. "A Case of Pathology in Multiobjective Heuristic Search." Journal of Artificial Intelligence Research, 2013. doi:10.1613/JAIR.4100Markdown
[Pérez-de-la-Cruz et al. "A Case of Pathology in Multiobjective Heuristic Search." Journal of Artificial Intelligence Research, 2013.](https://mlanthology.org/jair/2013/perezdelacruz2013jair-case/) doi:10.1613/JAIR.4100BibTeX
@article{perezdelacruz2013jair-case,
title = {{A Case of Pathology in Multiobjective Heuristic Search}},
author = {Pérez-de-la-Cruz, José-Luis and Mandow, Lorenzo and Machuca, Enrique},
journal = {Journal of Artificial Intelligence Research},
year = {2013},
pages = {717-732},
doi = {10.1613/JAIR.4100},
volume = {48},
url = {https://mlanthology.org/jair/2013/perezdelacruz2013jair-case/}
}