Anytime Decision Making Based on Unconstrained Influence Diagrams. Issue 4 (21st September 2015)

• Record Type: Journal Article
• Authors: Luque, Manuel; Nielsen, Thomas D.; Jensen, Finn V.
• Is Part Of: International journal of intelligent systems. Volume 31:Issue 4(2016)
• Page Start: 379
• Page End: 398
• Publication Date: 2015-09-21
• Subjects: Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; 006.3
• DOI: 10.1002/int.21780
• Languages: English
• ISSNs: 0884-8173

Abstract

Abstract : Unconstrained influence diagrams extend the language of influence diagrams to cope with decision problems in which the order of the decisions is unspecified. Thus, when solving an unconstrained influence diagram, we not only look for an optimal policy for each decision but also for a so‐called step policy specifying the next decision given the observations made so far. However, due to the complexity of the problem, temporal constraints can force the decision maker to act before the solution algorithm has finished and, in particular, before an optimal policy for the first decision has been computed. This paper addresses this problem by proposing an anytime algorithm that at any time provides a qualified recommendation for the first decisions of the problem. The algorithm performs a heuristic‐based search in a decision tree representation of the problem. We provide a framework for analyzing the performance of the algorithm, and experiments based on this framework indicate that the proposed algorithm performs significantly better under time constraints than dynamic programming.