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
Modelling Multi-Agent Epistemic Planning in ASP
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
- Award ID(s):
- 1914635
- NSF-PAR ID:
- 10209018
- Date Published:
- Journal Name:
- Theory and Practice of Logic Programming
- Volume:
- 20
- Issue:
- 5
- ISSN:
- 1471-0684
- Page Range / eLocation ID:
- 593 to 608
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
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
-
more » « less
Abstract This paper outlines the potential gains for Constructionist research and praxis in modelling that might be obtained by recognising the power of the Patch—a humble computational being in the NetLogo modelling environment that has been overshadowed by its more popular fellow agent, the Turtle. To contextualise this opportunity, I describe how Constructionist modelling has thrived by promoting forms of learning that rely on learners’ identifying with agents. I argue that patches are a neglected agent type in this multi‐agent modelling tradition, and that the possibilities for learners to adopt the patch perspective in support of exploratory forms of modelling and aesthetic expression have been under‐researched. Nevertheless, I show there are a variety of powerful ways for learners––both individually and in groups––to identify with patches. I describe ongoing research showing how taking an aesthetic approach to patches has the potential to support individuals and groups in powerful forms of learning with and about multi‐agent modelling.
Practitioner notes What is already known about this topic
Turtles (movable agents in Logo and Constructionist environments descended from Logo) can be ‘transitional objects’ that provide learners a way to make powerful ideas their own.
These agents can be powerful ‘objects‐to‐think‐with’ in large part because they encourage learners to identify with them in a form of learning known as ‘syntonic learning’.
Expressive activities that draw on learners’
aesthetic interests can support their learning with and about computational representations.Multi‐agent modelling is a powerful extension of Logo‐based learning environments that provides access to powerful ideas about complex systems and their emergent properties.
In the multi‐agent setting, individual learners and/or groups of learners can identify syntonically with agents to provide entry points for reasoning about complexity.
What this paper adds
Patches (non‐movable agents in the NetLogo modelling environment) are under‐represented in the research on multi‐agent modelling, and the potential for learners to adopt the patches’ perspective has been neglected.
An aesthetically driven approach to patches can ground students’ understanding of their expressive value.
Participatory activities in which learners play the role of patches (called ‘Stadium Card’ activities) can ground the patch perspective, so that learners can achieve a form of syntonicity and/or collectively adopt the perspective of patches in the aggregate.
Participatory activities that blend intrinsic and extrinsic perspectives on the patch grid can further enhance learners’ facility with programming for patches and their understanding of patches’ collective expressive power.
Implications for practice and/or policy
Balancing the focus between turtles and patches can enrich the modelling toolbox of learners new to agent‐based modelling.
Patches
do capture important aspects of individual and collective experience, and so can be good objects‐to‐think‐with, especially when conceptualising phenomena at a larger scale.The expressive potential of the patch grid is an important topic for computer science as well (eg, through 2D cellular automata). This is a rich context for learning in itself, which can be made accessible to groups of learners through physical or virtual participatory role‐play.
Moreover, physical or virtual grids of people‐patches may exhibit novel aggregate computational properties that could in turn become interesting areas for research in computer science.
-
null (Ed.)The paper introduces the notion of an epistemic argumentation framework (EAF) as a means to integrate the beliefs of a reasoner with argumentation. Intuitively, an EAF encodes the beliefs of an agent who reasons about arguments. Formally, an EAF is a pair of an argumentation framework and an epistemic constraint. The semantics of the EAF is defined by the notion of an ω-epistemic labelling set, where ω is complete, stable, grounded, or preferred, which is a set of ω-labellings that collectively satisfies the epistemic constraint of the EAF. The paper shows how EAF can represent different views of reasoners on the same argumentation framework. It also includes representing preferences in EAF and multi-agent argumentation. Finally, the paper discusses complexity issues and computation using epistemic logic programming.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/S1471068420000289
