- Award ID(s):
- 1718384
- PAR ID:
- 10387378
- Date Published:
- Journal Name:
- Journal of Artificial Intelligence Research
- Volume:
- 75
- ISSN:
- 1076-9757
- Page Range / eLocation ID:
- 1177 to 1221
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Influence diagrams are graphical models used to represent and solve decision-making problems under uncertainty. The solution of an influence diagram, a strategy, is traditionally represented by tables that map histories to actions; it can also be represented by an equivalent strategy tree. We show how to compress a strategy tree into an equivalent and more compact strategy graph, making strategies easier to interpret and understand. We also show how to compress a strategy graph further in exchange for bounded-error approximation.more » « less
-
Influence diagrams are graphical models used to represent and solve decision-making problems under uncertainty. The solution of an influence diagram, a strategy, is traditionally represented by tables that map histories to actions; it can also be represented by an equivalent strategy tree. We show how to compress a strategy tree into an equivalent and more compact strategy graph, making strategies easier to interpret and understand. We also show how to compress a strategy graph further in exchange for bounded-error approximation.more » « less
-
We consider a class of multi-agent optimization problems, where each agent has a local objective function that depends on its own decision variables and the aggregate of others, and is willing to cooperate with other agents to minimize the sum of the local objectives. After associating each agent with an auxiliary variable and the related local estimates, we conduct primal decomposition to the globally coupled problem and reformulate it so that it can be solved distributedly. Based on the Douglas-Rachford method, an algorithm is proposed which ensures the exact convergence to a solution of the original problem. The proposed method enjoys desirable scalability by only requiring each agent to keep local estimates whose number grows linearly with the number of its neighbors. We illustrate our proposed algorithm by numerical simulations on a commodity distribution problem over a transport network.more » « less
-
null (Ed.)We introduce an iterative framework for solving graph coloring problems using decision diagrams. The decision diagram compactly represents all possible color classes, some of which may contain edge conflicts. In each iteration, we use a constrained minimum network flow model to compute a lower bound and identify conflicts. Infeasible color classes associated with these conflicts are removed by refining the decision diagram. We prove that in the best case, our approach may use exponentially smaller diagrams than exact diagrams for proving optimality. We also develop a primal heuristic based on the decision diagram to find a feasible solution at each iteration. We provide an experimental evaluation on all 137 DIMACS graph coloring instances. Our procedure can solve 52 instances optimally, of which 44 are solved within 1 minute. We also compare our method to a state-of-the-art graph coloring solver based on branch-and-price, and show that we obtain competitive results. Lastly, we report an improved lower bound for the open instance C2000.9.more » « less
-
An influence diagram is a graphical representation of sequential decision-making under uncertainty, defining a structured decision problem by conditional probability functions and additive utility functions over discrete state and action variables. The task of finding the maximum expected utility of influence diagrams is closely related to the cost-optimal probabilistic planning, stochastic programmings, or model-based reinforcement learning. In this position paper, we address the heuristic search for solving influence diagram, where we generate admissible heuristic functions from graph decomposition schemes. Then, we demonstrate how such heuristics can guide an AND/OR branch and bound search. Finally, we briefly discuss the future directions for improving the quality of heuristic functions and search strategies.