Minimal belief and negation as failure in multi-agent systems (Q1861897): Difference between revisions

The paper presents a modal logic for multi-agent systems. The logic has modalities \(A\) and \(B\) for one non-monotonic agent and modalities \(K1,\ldots, Kn\) for another \(n\) monotonic agents. The non-monotonic operators \(A\) and \(B\) are not allowed inside the scope of the monotonic operators \(K1, \ldots, Kn\). Hence, the logic can only represent the thoughts the non-montonic agent has about the monotonic agents and not (!) vice versa. It is shown that the limited form of interaction between the modalities still allows for basic applications in the area of Robocup, the robotic football competition. But more involved interaction cannot be handled by this logic. The modalities \(A\) and \(B\) are taken from \textit{V. Lifschitz} [ Artif. Intell. 70, 53-72 (1994; Zbl 0820.03016)]. The author has given an algorithm and complexity results for the satisfiablity problem for these modalities in \textit{R. Rosati} [J. Artif. Intell. Res. 11, 277-300 (1999; Zbl 0932.03024)]. In the current paper it is shown that the constraints on the interaction of A and B with the modalities \(K1,\ldots, Kn\) allow for an elegant extension of these methods and results: it is shown that for the full logic the satisfiability problem is PSPACE complete. (Several fragments are considered which are \(\Sigma^p_2\) or \(\Sigma_3^p\) complete.) In this way a suspected lack of applications for the logic is balanced by success on the theoretical side. The presentation is concise but clear.