CoChat

Graphical Model Inference in Optimal Control of Stochastic Multi-Agent Systems

Open access
Van den Broek, B., Wiegerinck, W., Kappen, B. · 2008 · Journal of Artificial Intelligence Research
Cited by 83

The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.

Abstract

In this article we consider the issue of optimal control in collaborative multi-agent systems with stochastic dynamics. The agents have a joint task in which they have to reach a number of target states. The dynamics of the agents contains additive control and additive noise, and the autonomous part factorizes over the agents. Full observation of the global state is assumed. The goal is to minimize the accumulated joint cost, which consists of integrated instantaneous costs and a joint end cost. The joint end cost expresses the joint task of the agents. The instantaneous costs are quadratic in the control and factorize over the agents. The optimal control is given as a weighted linear combination of single-agent to single-target controls. The single-agent to single-target controls are expressed in terms of diffusion processes. These controls, when not closed form expressions, are formulated in terms of path integrals, which are calculated approximately by Metropolis-Hastings sampling. The weights in the control are interpreted as marginals of a joint distribution over agent to target assignments. The structure of the latter is represented by a graphical model, and the marginals are obtained by graphical model inference. Exact inference of the graphical model will break down in large systems, and so approximate inference methods are needed. We use naive mean field approximation and belief propagation to approximate the optimal control in systems with linear dynamics. We compare the approximate inference methods with the exact solution, and we show that they can accurately compute the optimal control. Finally, we demonstrate the control method in multi-agent systems with nonlinear dynamics consisting of up to 80 agents that have to reach an equal number of target states.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1613/jair.2473

Cites

3 of 3 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

  • Factor graphs and the sum-product algorithm

    Kschischang, F. R., Frey, B. J., & Loeliger, H.-A. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910572 · Cited by 6,486 · cited 4×

    “Belief propagation is an algorithm that computes the beliefs (Kschischang et al., 2001).”
    Influential
  • An Introduction to Variational Methods for Graphical Models

    Jordan, M. I., Ghahramani, Z., Jaakkola, T. S., & Saul, L. K. (1999) · Machine Learning · doi:10.1023/a:1007665907178 · Cited by 3,791 · cited 1×

    “A discussion on this line of thought can be found in (Kappen, 2007). There are many more possible model extensions worthwhile exploring in future research. Obvious examples are bounded controls, or a limited observation of the global state of the system; these issues are already of interest to study in the single agen…”
  • Path integrals and symmetry breaking for optimal control theory

    Kappen, H. J. (2005) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2005/11/p11011 · Cited by 309 · cited 6×

    “Van den Broek, Wiegerinck, and Kappen (2007) considered a multi-agent system with second-order dynamics, linear autonomous dynamics and zero instantaneous costs, and showed that graphical model inference by naive mean field approximation significantly outperformed a greedy inference.”
    BackgroundMethodInfluential

Show all 3 references

Cited by

Metadata

Authors
Van den Broek, B., Wiegerinck, W., & Kappen, B.
Venue
Journal of Artificial Intelligence Research
Published
2008-05-16
Volume
32
Pages
95-122
ISSN
1076-9757 (ISSN-L)
OpenAlex
W2137808289
Cited by
83
References
3
FWCI
10.97
Type
journal article
Language
en
Open access
diamond

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.