skip to main content

Title: State Transition in Multi-agent Epistemic Domains Using Answer Set Programming
In this paper we develop a state transition function for partially observable multi-agent epistemic domains and implement it using Answer Set Programming (ASP). The transition function computes the next state upon an occurrence of a single action. Thus it can be used as a module in epistemic planners. Our transition function incorporates ontic, sensing and announcement actions and allows for arbitrary nested belief formulae and general common knowledge. A novel feature of our model is that upon an action occurrence, an observing agent corrects his (possibly wrong) initial beliefs about action precondition and his observability. By examples, we show that this step is necessary for robust state transition. We establish some properties of our state transition function regarding its soundness in updating beliefs of agents consistent with their observability.  more » « less
Award ID(s):
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
Lecture notes in computer science
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. The action language m∗ employs the notion of update models in defining transitions between states. Given an action occurrence and a state, the update model of the action occurrence is automatically constructed from the given state and the observability of agents. A main criticism of this approach is that it cannot deal with situations when agents’ have incorrect beliefs about the observability of other agents. The present paper addresses this shortcoming by defining a new semantics for m∗ . The new semantics addresses the aforementioned problem of m∗ while maintaining the simplicity of its semantics; the new definitions continue to employ simple update models, with at most three events for all types of actions, which can be constructed given the action specification and independently from the state in which the action occurs. 
    more » « less
  2. In multi-agent domains (MADs), an agent's action may not just change the world and the agent's knowledge and beliefs about the world, but also may change other agents' knowledge and beliefs about the world and their knowledge and beliefs about other agents' knowledge and beliefs about the world. The goals of an agent in a multi-agent world may involve manipulating the knowledge and beliefs of other agents' and again, not just their knowledge/belief about the world, but also their knowledge about other agents' knowledge about the world. Our goal is to present an action language (mA+) that has the necessary features to address the above aspects in representing and RAC in MADs. mA+ allows the representation of and reasoning about different types of actions that an agent can perform in a domain where many other agents might be present -- such as world-altering actions, sensing actions, and announcement/communication actions. It also allows the specification of agents' dynamic awareness of action occurrences which has future implications on what agents' know about the world and other agents' knowledge about the world. mA+ considers three different types of awareness: full-, partial- awareness, and complete oblivion of an action occurrence and its effects. This keeps the language simple, yet powerful enough to address a large variety of knowledge manipulation scenarios in MADs. The semantics of mA+ relies on the notion of state, which is described by a pointed Kripke model and is used to encode the agent's knowledge and the real state of the world. It is defined by a transition function that maps pairs of actions and states into sets of states. We illustrate properties of the action theories, including properties that guarantee finiteness of the set of initial states and their practical implementability. Finally, we relate mA+ to other related formalisms that contribute to RAC in MADs. 
    more » « less
  3. Earlier epistemic planning systems for multi-agent domains generate plans that contain various types of actions such as ontic, sensing, or announcement actions. However, none of these systems consider untruthful announcements, i.e., none can generate plans that contain a lying or a misleading announcement. In this paper, we present a novel epistemic planner, called EFP3.0, for multi-agent domains with untruthful announcements. The planner is similar to the systems EFP or EFP2.0 in that it is a forward-search planner and can deal with unlimited nested beliefs and common knowledge by employing a Kripke based state representation and implementing an update model based transition function. Different from EFP, EFP3.0 employs a specification language that uses edge-conditioned update models for reasoning about effects of actions in multi-agent domains. We describe the basics of EFP3.0 and conduct experimental evaluations of the system against state-of-the-art epistemic planners. We discuss potential improvements that could be useful for scalability and efficiency of the system. 
    more » « less
  4. We study how long‐lived, rational agents learn in a social network. In every period, after observing the past actions of his neighbors, each agent receives a private signal, and chooses an action whose payoff depends only on the state. Since equilibrium actions depend on higher‐order beliefs, it is difficult to characterize behavior. Nevertheless, we show that regardless of the size and shape of the network, the utility function, and the patience of the agents, the speed of learning in any equilibrium is bounded from above by a constant that only depends on the private signal distribution. 
    more » « less
  5. null (Ed.)
    Abstract Designing agents that reason and act upon the world has always been one of the main objectives of the Artificial Intelligence community. While for planning in “simple” domains the agents can solely rely on facts about the world, in several contexts, e.g. , economy, security, justice and politics, the mere knowledge of the world could be insufficient to reach a desired goal. In these scenarios, epistemic reasoning, i.e. , reasoning about agents’ beliefs about themselves and about other agents’ beliefs, is essential to design winning strategies. This paper addresses the problem of reasoning in multi-agent epistemic settings exploiting declarative programming techniques. In particular, the paper presents an actual implementation of a multi-shot Answer Set Programming -based planner that can reason in multi-agent epistemic settings, called PLATO (e P istemic mu L ti-agent A nswer se T programming s O lver). The ASP paradigm enables a concise and elegant design of the planner, w.r.t. other imperative implementations, facilitating the development of formal verification of correctness. The paper shows how the planner, exploiting an ad-hoc epistemic state representation and the efficiency of ASP solvers, has competitive performance results on benchmarks collected from the literature. 
    more » « less