TY - JOUR
T1 - Fast local search methods for solving limited memory influence diagrams
AU - Mauá, Denis Deratani
AU - Cozman, Fabio Gagliardi
PY - 2016/1/1
Y1 - 2016/1/1
N2 - © 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.
AB - © 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.
UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84949624961&origin=inward
UR - https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=84949624961&origin=inward
U2 - 10.1016/j.ijar.2015.05.003
DO - 10.1016/j.ijar.2015.05.003
M3 - Article
SP - 230
EP - 245
JO - International Journal of Approximate Reasoning
JF - International Journal of Approximate Reasoning
SN - 0888-613X
ER -