Efficient algorithms for graph-based decision making under uncertainty

• Grant number: 13/23197-4
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• Start date: March 01, 2014
• End date: March 16, 2015
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computer Systems
• Principal Investigator: Fabio Gagliardi Cozman
• Grantee: Denis Deratani Mauá
• Host Institution: Escola Politécnica (EP). Universidade de São Paulo (USP). São Paulo , SP, Brazil

Abstract

Influence diagrams are graph-based probabilistic models for representing decision-making problems under uncertainty. These diagrams allow for the clear communication of complex decision making situations, being one of the main tools in the probabilistic analysis of structured decision problems. Solving an influence diagram refers to finding an optimal set of rules that map observations into actions, which are generally used to specify the behavior of a rational agent. Finding such a set of rules is known to be an NP-hard task, even when thedecision problem bears a simple graphical structure. In light of the NP-hardness of the problem, it is not surprising that current algorithms for solving influence diagrams focus on either achieving short running times, at the expense of accuracy, or obtaining accurate solutions, at the expense of computational efficiency. Either approach alone is unsatisfactory, as it risks finding solutions of arbitrarily low quality or incurring excessively high computational costs. This can be critical in real applications. For instance, the controller of a mobile robot may have to find a good enough trajectory within a reasonable amount of time; failing to meet either criterion might lead to catastrophic behavior such as colliding with an object. Hence, it is necessary to design algoritms that can trade off accuracy and computational load, allowing the user to select the configuration most suitable for the task at hand. This project seeks the development of algorithms for solving limited memory influence diagrams that allow for accuracy and efficiency to be traded at the user's will.

Scientific publications

(9)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

NIE, SIQI; MAUA, DENIS D.; DE CAMPOS, CASSIO P.; JI, QIANG; GHAHRAMANI, Z; WELLING, M; CORTES, C; LAWRENCE, ND; WEINBERGER, KQ. Advances in Learning Bayesian Networks of Bounded Treewidth. ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 30 (NIPS 2017), v. 27, p. 9-pg., 2014-01-01. (13/23197-4)

COZMAN, FABIO GAGLIARDI; MAUA, DENIS DERATANI; AAAI. Bayesian Networks Specified Using Propositional and Relational Constructs: Combined, Data, and Domain Complexity. PROCEEDINGS OF THE TWENTY-NINTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, v. N/A, p. 7-pg., 2015-01-01. (13/23197-4)

COZMAN, FABIO GAGLIARDI; MAUA, DENIS DERATANI; AUGUSTIN, T; DORIA, S; MIRANDA, E; QUAEGHEBEUR, E. On the Complexity of Propositional and Relational Credal Networks. 2022 25TH INTERNATIONAL CONFERENCE ON INFORMATION FUSION (FUSION 2022), v. N/A, p. 9-pg., 2015-01-01. (13/23197-4)

MAUA, DENIS DERATANI; ANTONUCCI, ALESSANDRO; DE CAMPOS, CASSIO POLPO. Hidden Markov models with set-valued parameters. Neurocomputing, v. 180, n. SI, p. 94-107, MAR 5 2016. (13/23197-4)

MAUA, DENIS DERATANI. Equivalences between maximum a posteriori inference in Bayesian networks and maximum expected utility computation in influence diagrams. INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, v. 68, p. 211-229, JAN 2016. (13/23197-4)

MAUA, DENIS DERATANI; COZMAN, FABIO GAGLIARDI. Fast local search methods for solving limited memory influence diagrams. INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, v. 68, p. 230-245, JAN 2016. (13/23197-4)

MAUA, DENIS DERATANI; DE CAMPOS, CASSIO P.; BENAVOLI, ALESSIO; ANTONUCCI, ALESSANDRO. Probabilistic Inference in Credal Networks: New Complexity Results. JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, v. 50, p. 603-637, 2014. (13/23197-4)

MAUA, DENIS D.; DE CAMPOS, CASSIO P.; COZMAN, FABIO G.; YANG, Q; WOOLDRIDGE, M. The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages. PROCEEDINGS OF THE TWENTY-FOURTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI), v. N/A, p. 7-pg., 2015-01-01. (13/23197-4)

MAUA, DENIS DERATANI; ANTONUCCI, ALESSANDRO; DE CAMPOS, CASSIO POLPO. Hidden Markov models with set-valued parameters. Neurocomputing, v. 180, p. 14-pg., 2016-03-05. (13/23197-4)