Mauá, Denis Deratani and De Campos, Cassio Polpo and Zaffalon, Marco (2013) On the complexity of solving polytreeshaped limited memory influence diagrams with binary variables. Artificial Intelligence, 205. pp. 3038. ISSN 00043702

Text
maua2012b.pdf  Published Version Download (372kB)  Preview 
Abstract
Influence diagrams are intuitive and concise representations of structured decision problems. When the problem is nonMarkovian, an optimal strategy can be exponentially large in the size of the diagram. We can avoid the inherent intractability by constraining the size of admissible strategies, giving rise to limited memory influence diagrams. A valuable question is then how small do strategies need to be to enable efficient optimal planning. Arguably, the smallest strategies one can conceive simply prescribe an action for each time step, without considering past decisions or observations. Previous work has shown that finding such optimal strategies even for polytreeshaped diagrams with ternary variables and a single value node is NPhard, but the case of binary variables was left open. In this paper we address such a case, by first noting that optimal strategies can be obtained in polynomial time for polytreeshaped diagrams with binary variables and a single value node. We then show that the same problem is NPhard if the diagram has multiple value nodes. These two results close the fixedparameter complexity analysis of optimal strategy selection in influence diagrams parametrized by the shape of the diagram, the number of value nodes and the maximum variable cardinality.
Item Type:  Scientific journal article, Newspaper article or Magazine article 

Uncontrolled Keywords:  decision theory, in uence diagrams, decision networks, probabilistic planning, computational complexity 
Subjects:  Computer sciences 
Depositing User:  Cassio Polpo De Campos 
Date Deposited:  13 Mar 2014 14:16 
Last Modified:  23 May 2016 12:51 
URI:  http://repository.supsi.ch/id/eprint/3907 
Actions (login required)
View Item 