Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Fast local search methods for solving limited memory influence diagrams

Texto completo
Autor(es):
Maua, Denis Deratani [1] ; Cozman, Fabio Gagliardi [2]
Número total de Autores: 2
Afiliação do(s) autor(es):
[1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil
[2] Univ Sao Paulo, Escola Politecn, BR-05508030 Sao Paulo - Brazil
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: INTERNATIONAL JOURNAL OF APPROXIMATE REASONING; v. 68, p. 230-245, JAN 2016.
Citações Web of Science: 1
Resumo

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. (C) 2015 Elsevier Inc. All rights reserved. (AU)

Processo FAPESP: 13/23197-4 - Algoritmos eficientes para tomada de decisão sob incerteza baseada em grafos
Beneficiário:Denis Deratani Mauá
Linha de fomento: Bolsas no Brasil - Pós-Doutorado