Anytime decision making based on unconstrained influence diagrams

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

1 Citation (Scopus)
245 Downloads (Pure)

Resumé

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.
OriginalsprogEngelsk
TidsskriftInternational Journal of Intelligent Systems
Vol/bind31
Udgave nummer4
Sider (fra-til)379-398
Antal sider20
ISSN0884-8173
DOI
StatusUdgivet - 2016

Fingerprint

Influence Diagrams
Decision making
Decision Making
Optimal Policy
Temporal Constraints
Decision trees
Dynamic programming
Decision problem
Decision tree
Dynamic Programming
Recommendations
Heuristics
Experiments
Experiment

Citer dette

@article{c44b167eec0d4a599a1b16b0a4a3d18c,
title = "Anytime decision making based on unconstrained influence diagrams",
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.",
author = "Manuel Luque and Nielsen, {Thomas Dyhre} and Jensen, {Finn Verner}",
year = "2016",
doi = "10.1002/int.21780",
language = "English",
volume = "31",
pages = "379--398",
journal = "International Journal of Intelligent Systems",
issn = "0884-8173",
publisher = "Wiley",
number = "4",

}

Anytime decision making based on unconstrained influence diagrams. / Luque, Manuel; Nielsen, Thomas Dyhre; Jensen, Finn Verner.

I: International Journal of Intelligent Systems, Bind 31, Nr. 4, 2016, s. 379-398.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

T1 - Anytime decision making based on unconstrained influence diagrams

AU - Luque, Manuel

AU - Nielsen, Thomas Dyhre

AU - Jensen, Finn Verner

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

U2 - 10.1002/int.21780

DO - 10.1002/int.21780

M3 - Journal article

VL - 31

SP - 379

EP - 398

JO - International Journal of Intelligent Systems

JF - International Journal of Intelligent Systems

SN - 0884-8173

IS - 4

ER -