Fast local search methods for solving limited memory influence diagrams

Denis Deratani Mauá, Fabio Gagliardi Cozman

Resultado de la investigación: Contribución a una revistaArtículo

1 Cita (Scopus)

Resumen

© 2015 Elsevier Inc. All rights reserved. Limited memory influence diagrams are graph-based models that describe decision problems with limited information such as planning with teams and/or agents with imperfect recall. Solving a (limited memory) influence diagram is an NP-hard problem, often approached through local search. In this work we give a closer look at k-neighborhood local search approaches. We show that finding a k-neighboring strategy that improves on the current solution is W[1]-hard and hence unlikely to be polynomial-time tractable. We also show that finding a strategy that resembles an optimal strategy (but may have low expected utility) is NP-hard. We then develop fast schema to perform approximate k-local search; experiments show that our methods improve on current local search algorithms both with respect to time and to accuracy.
Idioma originalInglés estadounidense
Páginas (desde-hasta)230-245
Número de páginas16
PublicaciónInternational Journal of Approximate Reasoning
DOI
EstadoPublicada - 1 ene 2016
Publicado de forma externa

Huella Profundice en los temas de investigación de 'Fast local search methods for solving limited memory influence diagrams'. En conjunto forman una huella única.

  • Citar esto