|Current Workshop | Overview||Back | Home | Search ||
MAO - Multi-Agent Organisation
Wil van der Aalst
Process Mining Manifesto
The growing interest in log-based process analysis motivated the establishment of the IEEE Task Force on Process Mining. The goal of this task force is to promote the research, development, education, and understanding of process mining. Members of the task force include representatives of more than a dozen commercial software vendors (e.g., Pallas Athena, Software AG, Futura Process Intelligence, HP, IBM, Fujitsu, Infosys, and Fluxicon), ten consultancy firms (e.g., Gartner and Deloitte) and over twenty universities. The task force recently released a manifesto describing guiding principles and challenges. Process mining aims to discover, monitor and improve real processes by extracting knowledge from event logs readily available in today's information systems. The manifesto aims to increase the visibility of process mining as a new tool to improve the (re)design, control, and support of operational business processes. It is intended to guide software developers, scientists, consultants, and end-users. In his talk prof. Wil van der Aalst will introduce process mining as an enabling technology for analyzing the behavior of agents.
An Interaction-oriented Framework for Social Computing
We propose an interaction-oriented framework and the related support infrastructure, that reifies commitment-based interaction protocols into programmable environments and artifacts. The use of commitments gives a normative characterization to coordination artifacts, while the use of artifacts enables the application of software engineering methodologies to protocols.
Verifying Normative Behaviour via Normative Mechanism Design
(joint work with Mehdi Dastani)
The environment is an essential component of multi-agent systems and is often used to coordinate the behaviour of individual agents. Recently many languages have been proposed to specify and implement multi-agent environments in terms of social and normative concepts. In this talk, we first introduce a formal setting of multi-agent environment which abstracts from concrete specification languages. We extend this formal setting with norms and sanctions and show how concepts from mechanism design can be used to formally analyse and verify whether specific normative behaviours can be enforced (or implemented) if agents follow their subjective preferences.
We also consider complexity issues of associated problems.
A note on procedural rules in argument games
In my talk I will look at abstract argument games as a source of interesting intuitions concerning the notion of procedural rule.
I will be concerned, in particular, with the problem of the rationale or justification of procedural rules as appropriate means to achieve a given end---in the case of argument games, the end being the adequacy with respect to a given Dung semantics. I will report on some of my recent work on the topic, and point at a number of research directions.
A minimal requirement on allocative
efficiency in the social sciences is Pareto optimality. In this paper, we
identify a far-reaching structural connection between Pareto optimality and
perfection that has various algorithmic consequences for coalition formation.
Based on this insight, we formulate the Preference Refinement Algorithm (PRA)
which computes an individually rational and Pareto optimal outcome in hedonic
coalition formation games or any other discrete allocation setting. Our
approach also leads to various results for specific classes of hedonic games.
In particular, we show that computing and verifying Pareto optimal partitions
in general hedonic games, anonymous games, three-cyclic games, room-roommate
games and B-hedonic games is intractable while both problems are tractable for
roommate games, W-hedonic games, and house allocation with existing tenants.
(joint work with Emiliano Lorini, Frédéric Moisan, Nicolas Troquard)
We propose a logical framework to represent and reason about agent interactions in normative systems. Our starting point is a dynamic logic of propositional assignments. We first show that it embeds Coalition Logic of Propositional Control CL-PC and that various notions of ability and capability can be captured in it. We then extend the logic in order to represent and reason about some important aspects of a theory of institutional action: (1) the distinctions between physical facts and actions and institutional facts and actions; (2) the distinction between causality and ‘counts-as’; (3) the notion of institutional power.
Technically, our contribution consists in extending the dynamic logic of propositional assignments with constructions allowing to express that an agent plays a given role; that a physical action causes another physical action; that a physical action performed by an agent playing a given role counts as an institutional action.
Doubtful Deviations and Farsighted Play
(joint work with Matthijs Melissen)
Nash equilibrium is based on the idea that a strategy profile is stable if no player can benefit from a unilateral deviation. We observe that some locally rational deviations in a strategic game may not be profitable anymore if one takes into account the possibility of further deviations by the other players. As a solution, we propose the concept of farsighted pre-equilibrium, which takes into account only deviations that do not lead to a decrease of the player's outcome even if some other deviations follow. While Nash equilibria are assumed to include plays that are certainly rational, our pre-equilibrium is supposed to rule out plays that are _certainly irrational_. We prove that positional strategies are sufficient to define the concept, we study its computational complexity, and show that pre-equilibria correspond to subgame-perfect Nash equilibria in a meta-game obtained by using the original payoff matrix as arena and the deviations as moves.
Organisation aware agents: challenges and some first results
Organizational notions such as roles, norms (e.g., obligations and permissions), and services are increasingly viewed as natural concepts to manage the complexity of software development. In particular in the context of multi-agent systems, agents are expected to be organization-aware, i.e., to understand and reason about the structure, work processes, and norms of the agent organization in which they operate. We analyze which kinds of reasoning an agent should be able to do to function in an organization. We categorize these kinds of reasoning with respect to several dimensions and give some examples of the reasoning required.
Programming Norm-Aware Agents
(joint work with Natasha Alechina and Mehdi Dastani)
We can define a "norm-aware" agent as one that deliberates on its goals, norms and sanctions before deciding which plan to select and execute. Norm-aware agents are able to violate norms (accepting the resulting sanctions) if it is in their overall interests to do so, e.g., if meeting an obligation would result in an important goal of the agent becoming unachievable. Programming norm-aware agents in conventional BDI-based agent programming languages is difficult, as they lack support for deliberating about goals, norms, sanctions and deadlines. In this talk, I will sketch the norm-aware agent programming language N-2APL. N-2APL is based on 2APL and provides support for beliefs, goals, plans, norms, sanctions and deadlines. I will describe how the syntax and semantics of 2APL were modified to support norm-awareness, and show that N-2APL agents are rational in the sense of committing to a set of plans that will achieve the agent's most important goals and obligations by their deadlines while respecting its most important prohibitions.
A simple logic for reasoning about institutional actions
propose a logical framework to represent and reason about some important
aspects of a theory of institutional action:
Ubiquity, or at least being active in more than one place at a time, is not unusual in conventional social interactions. Contracting within a supply network, trading in investment banking or managing an archaeological expedition are typical situations where several individuals are involved in simultaneous activities that involve different participants and may have causal and temporal interdependencies. In spite of their natural abundance and their inherent technical interest, such situations have not been thoroughly studied in the context of MAO. In this talk I will explore a notion of "co-incidence" in open multiagent systems. I will first propose a characterization of the notion of activity and then discuss how activities may be interrelated as well as how an agent may be active in more than one activity. Based on those elements I will present a conceptual model to specify and implement MAS with co-incident activities.
Goal-Directed Conflict Resolution and Policy Refinement
A norm (or policy) can be defined as a guideline stating what is allowed, what is forbidden and what is obligated for an entity in some situation so that an acceptable outcome is achieved. Policies occur in many contexts, whether they are loose social networks of individuals or highly structured institutions. For example, the NHS (UK National Health Service) state in their Care Record Guarantee that the "NHS is prohibited from sharing any information that identifies the patient for any reason other than providing care". Such a policy provides a high-level guarantee of information privacy to patients, but it is not necessarily clear how this maps to specific clinical care or clinical research protocols. Furthermore, it is a significant challenge for policy authors to specify consistent and coherent policies for systems to support information management and auditing. A thorough understanding of the meanings and implications of policies is important for their effective implementation. Significant effort has been invested in exploring algorithms for evaluating sets of norms or policies for logical consistency. This is, however, only a partial solution. Consistency and coherence evaluation of policies must be context (or more specifically goal) dependent. The authoring and analysis of policies for an institution must focus on both logical and functional conflicts with respect to the goals of the institution. We are exploring reasoning mechanisms to support the authoring an refinement of OWL-POLAR policies within the context of the dot.rural Digital Economy research project, and investigating their application to clinical care information management for the support of patients in rural areas.
Arguing about Legal Concepts and Norm Applicability using Theory Revision and Inferences to the Best Theory
This paper moves from the assumption that legal concepts can be fruitfully represented as logical theories of constitutive rules. The interpretation of legal concepts can thus be viewed as a process where we (a) aggregate theories corresponding to the legal and ordinary understandings of concepts, and (b) revise these theories in order to align concepts with the goals of regulative legal rules. The combination of the above two procedures raises the crucial question of how to choose among many possible revision outcomes. This problem can take the form of a dialectical process where the players exchange arguments and counter-arguments to establish which is the best theory. Some criteria are briefly discussed in this regard, such as theory inclusiveness, teleological coherence, simplicity, minimal change, and theory connectedness.
Compliance with normative systems
I will argue that the cognitive attitudes and operations involved in compliance
with normative systems are usually different from those involved in complying
with isolated social norms. While isolated norms must be stored in the memory of
the agents endorsing them, this does not happen with regard to large normative systems.
In the latter case, the agent adopts a general policy-based intention to comply
with the normative system as a whole, an intention that provides an abstract motivation
for specific acts of compliance, once the agent has established that these
acts are obligatory according the system. I will show how the endorsement of such
a policy can be based on different individual attitudes, ranging from self-interest to
altruistic, social or moral motivations. Finally, I will analyse how a normative system
may both constrain powers and extend them, relying on this abstract motivation
of its addressees.
Norms, action and agency
This will be an overview of a `logic of unwitting collective agency', a language combining a transition based account of action with a logic of 'brings it about' or 'sees to it that' expressions. I call it 'unwitting agency' because it makes no attempt to capture deliberative or purposeful action. I want to make no assumptions at all about the reasoning or perceptual capabilities of the agents---they can be human, or computer agents, or simple reactive devices. Actions might be deliberative but could also be unwitting: 'unwitting' can mean both inadvertent and unaware. Somewhat surprisingly perhaps, the logic does bear a strong resemblance to Ingmar P\"orn's (1977) logic of `brings it about' and to `stit' logics, though there are also some important conceptual and technical differences. The account generalises naturally to talking about the collective actions of groups of agents: several different forms of (unwitting) collective agency can be identified. The talk will concentrate on presenting some examples rather than technical details of the language. I will discuss how some illustrative examples can be represented and analysed. On a related but different point, I would also like to make some general remarks about the idea of using norms or `social laws' as a means of coordinating agent interactions in multi-agent systems.
On group norms
We consider the representation and processing of group norms – these norms address groups of individuals, affecting their joint behaviours. Groups norms arise in many situations;, e.g., an obligation on the sales team to meet once a week, a prohibition on gatherings of more than N people, or a permission for a group visit to a building. We provide a taxonomy of group norms, propose means to represent these, and provide semantics for norm fulfilment and violation. Additionally, we explore mechanisms for agents processing group norms, namely, how agents become aware of group norms, and how their individual behaviours can factor these in (e.g., for joint action/coordination). Finally, we sketch how our representation of group norms formally connects with an organisation algebra, showing how creation and changes affect and are affected by group norms.