Advanced search
Start date
Betweenand
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Fast local search methods for solving limited memory influence diagrams

Full text
Author(s):
Maua, Denis Deratani [1] ; Cozman, Fabio Gagliardi [2]
Total Authors: 2
Affiliation:
[1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil
[2] Univ Sao Paulo, Escola Politecn, BR-05508030 Sao Paulo - Brazil
Total Affiliations: 2
Document type: Journal article
Source: INTERNATIONAL JOURNAL OF APPROXIMATE REASONING; v. 68, p. 230-245, JAN 2016.
Web of Science Citations: 0
Abstract

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)

FAPESP's process: 13/23197-4 - Efficient algorithms for graph-based decision making under uncertainty
Grantee:Denis Deratani Mauá
Support Opportunities: Scholarships in Brazil - Post-Doctorate