Hierarchical decision making in multi-agent systems using answer set programming. (English) Zbl 1177.68229
Inoue, Katsumi (ed.) et al., Computational logic in multi-agent systems. 7th international workshop, CLIMA VII, Hakodate, Japan, May 8–9, 2006. Revised selected and invited papers. Berlin: Springer (ISBN 978-3-540-69618-6/pbk). Lecture Notes in Computer Science 4371. Lecture Notes in Artificial Intelligence, 20-40 (2007).
Summary: We present a multi-agent formalism based on extended answer set programming. The system consists of independent agents connected via a communication channel, where knowledge and beliefs of each agent are represented by a logic program. When presented with an input set of literals from its predecessor, an agent computes its output as an extended answer set of its program enriched with the input, carefully eliminating contradictions that might occur.
It turns out that while individual agents are rather simple, the interaction strategy makes the system quite expressive: essentially a hierarchy of a fixed number of agents \(n\) captures the complexity class \({\Sigma^{\text{P}}_{n}}\), i.e. the \(n\)-th level of the polynomial hierarchy. Furthermore, unbounded hierarchies capture the polynomial hierarchy \({\mathcal{PH}}\). This makes the formalism suitable for modelling complex applications of MAS, for example cooperative diagnosis. Furthermore, such systems can be realized by implementing an appropriate control strategy on top of existing solvers such as dlv and smodels.
For the entire collection see [Zbl 1152.68003].
It turns out that while individual agents are rather simple, the interaction strategy makes the system quite expressive: essentially a hierarchy of a fixed number of agents \(n\) captures the complexity class \({\Sigma^{\text{P}}_{n}}\), i.e. the \(n\)-th level of the polynomial hierarchy. Furthermore, unbounded hierarchies capture the polynomial hierarchy \({\mathcal{PH}}\). This makes the formalism suitable for modelling complex applications of MAS, for example cooperative diagnosis. Furthermore, such systems can be realized by implementing an appropriate control strategy on top of existing solvers such as dlv and smodels.
For the entire collection see [Zbl 1152.68003].
MSC:
| 68T42 | Agent technology and artificial intelligence |
| 68N17 | Logic programming |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
