Dynamic programming in in uence diagrams with decision circuits
Ross Shachter, Debarun Bhattacharjya
Decision circuits perform efficient evaluation of influence diagrams, building on the ad- vances in arithmetic circuits for belief net- work inference [Darwiche, 2003; Bhattachar- jya and Shachter, 2007]. We show how even more compact decision circuits can be con- structed for dynamic programming in influ- ence diagrams with separable value functions and conditionally independent subproblems. Once a decision circuit has been constructed based on the diagram's "global" graphical structure, it can be compiled to exploit "lo- cal" structure for efficient evaluation and sen- sitivity analysis.
PDF Link: /papers/10/p509-shachter.pdf
AUTHOR = "Ross Shachter
and Debarun Bhattacharjya",
TITLE = "Dynamic programming in in uence diagrams with decision circuits",
BOOKTITLE = "Proceedings of the Twenty-Sixth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-10)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2010",
PAGES = "509--516"