A coherence maximisation process for solving normative inconsistencies

Norms can be used in multi-agent systems for defining patterns of behaviour in terms of permissions, prohibitions and obligations that are addressed to agents playing a specific role. Agents may play different roles during their execution and they may even play different roles simultaneously. As a consequence, agents may be affected by inconsistent norms; e.g., an agent may be simultaneously obliged and forbidden to reach a given state of affairs. Dealing with this type of inconsistency is one of the main challenges of normative reasoning. Existing approaches tackle this problem by using a static and predefined order that determines which norm should prevail in the case where two norms are inconsistent. One main drawback of these proposals is that they allow only pairwise comparison of norms; it is not clear how agents may use the predefined order to select a subset of norms to abide by from a set of norms containing multiple inconsistencies. Furthermore, in dynamic and non-deterministic environments it can be difficult or even impossible to specify an order that resolves inconsistencies satisfactorily in all potential situations. In response to these two problems, we propose a mechanism with which an agent can dynamically compute a preference order over subsets of its competing norms by considering the coherence of its cognitive and normative elements. Our approach allows flexible resolution of normative inconsistencies, tailored to the current circumstances of the agent. Moreover, our solution can be used to determine norm prevalence among a set of norms containing multiple inconsistencies.     

A multiagent network for peer norm enforcement

In a multiagent system where norms are used to regulate the actions agents ought to execute, some agents may decide not to abide by the norms if this can benefit them. Norm enforcement mechanisms are designed to counteract these benefits and thus the motives for not abiding by the norms. In this work we propose a distributed mechanism through which agents in the multiagent system that do not abide by the norms can be ostracised by their peers. An ostracised agent cannot interact anymore and looses all benefits from future interactions. We describe a model for multiagent systems structured as networks of agents, and a behavioural model for the agents in such systems. Furthermore, we provide analytical results which show that there exists an upper bound to the number of potential norm violations when all the agents exhibit certain behaviours. We also provide experimental results showing that both stricter enforcement behaviours and larger percentage of agents exhibiting these behaviours reduce the number of norm violations, and that the network topology influences the number of norm violations. These experiments have been executed under varying scenarios with different values for the number of agents, percentage of enforcers, percentage of violators, network topology, and agent behaviours. Finally, we give examples of applications where the enforcement techniques we provide could be used.     

On the connection between the phase transition of the covering test and the learning success rate in ILP

It is well-known that heuristic search in ILP is prone to plateau phenomena. An explanation can be given after the work of Giordana and Saitta: the ILP covering test is NP-complete and therefore exhibits a sharp phase transition in its coverage probability. As the heuristic value of a hypothesis depends on the number of covered examples, the regions “yes” and “no” represent plateaus that need to be crossed during search without an informative heuristic value. Several subsequent works have extensively studied this finding by running several learning algorithms on a large set of artificially generated problems and argued that the occurrence of this phase transition dooms every learning algorithm to fail to identify the target concept. We note however that only generate-and-test learning algorithms have been applied and that this conclusion has to be qualified in the case of data-driven learning algorithms. Mostly building on the pioneering work of Winston on near-miss examples, we show that, on the same set of problems, a top-down data-driven strategy can cross any plateau if near-misses are supplied in the training set, whereas they do not change the plateau profile and do not guide a generate-and-test strategy. We conclude that the location of the target concept with respect to the phase transition alone is not a reliable indication of the learning problem difficulty as previously thought. Editors: Stephen Muggleton, Ramon Otero, Simon Colton.     

Investigation of Commutative Properties of Discontinuous Galerkin Methods in PDE Constrained Optimal Control Problems

The aim of this paper is to investigate commutative properties of a large family of discontinuous Galerkin (DG) methods applied to optimal control problems governed by the advection-diffusion equations. To compute numerical solutions of PDE constrained optimal control problems there are two main approaches: optimize-then-discretize and discretize-then-optimize. These two approaches do not always coincide and may lead to substantially different numerical solutions. The methods for which these two approaches do coincide we call commutative. In the theory of single equations, there is a related notion of adjoint or dual consistency. In this paper we classify DG methods both in primary and mixed forms and derive necessary conditions that can be used to develop new commutative methods. We will also derive error estimates in the energy and L ² norms. Numerical examples reveal that in the context of PDE constrained optimal control problems a special care needs to be taken to compute the solutions. For example, choosing non-commutative methods and discretize-then-optimize approach may result in a badly behaved numerical solution.     

Belief representation in a deductivist type-free doxastic logic

Konolige's technical notion of belief based on deduction structures is briefly reviewed and its usefulness for the design of artificial agents with limited representational and deductive capacities is pointed out. The design of artificial agents with more sophisticated representational and deductive capacities is then taken into account. Extended representational capacities require in the first place a solution to the intensional context problems. As an alternative to Konolige's modal first-order language, an approach based on type-free property theory is proposed. It considers often neglected issues, such as the need for a more general account of thede dicto-de re distinction, and quasi-indicators. Extended deductive capacities require a subdivision of Konolige's notion of belief into two distinct technical notions,potential anddispositional belief. The former has to do with what an artificial agent could in principle come to actively believe, given enough time and its specific logical competence; the latter with what an agent can be assumed to believe with respect to a specific goal to be fulfilled.     

Learning goal hierarchies from structured observations and expert annotations

We describe a relational learning by observation framework that automatically creates cognitive agent programs that model expert task performance in complex dynamic domains. Our framework uses observed behavior and goal annotations of an expert as the primary input, interprets them in the context of background knowledge, and returns an agent program that behaves similar to the expert. We map the problem of creating an agent program on to multiple learning problems that can be represented in a “supervised concept learning’’ setting. The acquired procedural knowledge is partitioned into a hierarchy of goals and represented with first order rules. Using an inductive logic programming (ILP) learning component allows our framework to naturally combine structured behavior observations, parametric and hierarchical goal annotations, and complex background knowledge. To deal with the large domains we consider, we have developed an efficient mechanism for storing and retrieving structured behavior data. We have tested our approach using artificially created examples and behavior observation traces generated by AI agents. We evaluate the learned rules by comparing them to hand-coded rules. Editor: Rui Camacho     

Normative conflict resolution in multi-agent systems

Norms (permissions, obligations and prohibitions) offer a useful and powerful abstraction with which to capture social constraints in multi-agent systems. Norms should exclude disruptive or antisocial behaviour without prescribing the design of individual agents or restricting their autonomy. An important challenge, however, in the design and management of systems governed by norms is that norms may, at times, conflict with one another; e.g, an action may be simultaneously prohibited and obliged for a particular agent. In such circumstances, agents no longer have the option of complying with these norms; whatever they do or refrain from doing will lead to a social constraint being broken. In this paper, we present mechanisms for the detection and resolution of normative conflicts. These mechanisms, based on first-order unification and constraint solving techniques, are the building blocks of more sophisticated algorithms we present for the management of normative positions, that is, the adoption and removal of permissions, obligations and prohibitions in societies of agents. We capture both direct and indirect conflicts between norms, formalise a practical concept of authority, and model conflicts that may arise as a result of delegation. We are able to formally define classic ways for resolving conflicts such as lex superior and lex posterior.     

Partiality and Nondeterminacy in Program Proofs

Specifications and programs make much use of nondeterministic and/or partial expressions, i.e. expressions which may yield several or no outcomes for some values of their free variables. Traditional 2-valued logics do not comfortably accommodate reasoning about undefined expressions, and do not cater at all for nondeterministic expressions. We seek to rectify this with a 4-valued typed logic E4 which classifies formulae as either “true”, “false”, “neither true nor false”, or “possibly true, possibly false”. The logic is derived in part from the 2-valued logic E and the 3-valued LPF, and preserves most of the theorems of E. Indeed, the main result is that nondeterminacy can be added to a logic covering partiality at little cost. Received July 1996 / Accepted in revised form April 1998     

多Agent信任传递与信念聚合

对多Agent之间相互的信任和单Agent的信念采用定性与定量结合的方法,即某主体对另一主体信任程度或对某个知识可相信程度用取值范围从0至1的三元组(相信,不相信,不确定)表示,可以有效进行Agent之间知识的传递交流和单Agent知识的积累并加以计算,且解决了不同来源的知识冲突问题。     

MaNEA: A distributed architecture for enforcing norms in open MAS

Norms have been promoted as a coordination mechanism for controlling agent behaviours in open MAS. Thus, agent platforms must provide normative support, allowing both norm-aware and non-norm-aware agents to take part in MAS that are controlled by norms. In this paper, the most relevant proposals on the definition of norm enforcement mechanisms are analyzed. These proposals present several drawbacks that make them unsuitable for open MAS. In response to these problems, this paper describes a new Norm-Enforcing Architecture aimed at controlling norms in open MAS. Specifically, this architecture supports the creation and deletion of norms on-line as well as the dynamic activation and expiration of instances. Finally, it can dynamically adapt to different scale MAS. The efficiency of this architecture has been experimentally evaluated and the results are shown in this paper.     

Tableau-based automata construction for dynamic linear time temporal logic*

We present a tableau-based algorithm for obtaining a Büchi automaton from a formula in Dynamic Linear Time Temporal Logic (DLTL), a logic which extends LTL by indexing the until operator with regular programs. The construction of the states of the automaton is similar to the standard construction for LTL, but a different technique must be used to verify the fulfillment of until formulas. The resulting automaton is a Büchi automaton rather than a generalized one. The construction can be done on-the-fly, while checking for the emptiness of the automaton. We also extend the construction to the Product Version of DLTL.*This research has been partially supported by the project MIUR PRIN 2005 ‘Specification and verification of agent interaction protocols’.     

The complexity of agent design problems: Determinism and history dependence

The agent design problem is as follows: given a specification of an environment, together with a specification of a task, is it possible to construct an agent that can be guaranteed to successfully accomplish the task in the environment? In this article, we study the computational complexity of the agent design problem for tasks that are of the form “achieve this state of affairs” or “maintain this state of affairs.” We consider three general formulations of these problems (in both non-deterministic and deterministic environments) that differ in the nature of what is viewed as an “acceptable” solution: in the least restrictive formulation, no limit is placed on the number of actions an agent is allowed to perform in attempting to meet the requirements of its specified task. We show that the resulting decision problems are intractable, in the sense that these are non-recursive (but recursively enumerable) for achievement tasks, and non-recursively enumerable for maintenance tasks. In the second formulation, the decision problem addresses the existence of agents that have satisfied their specified task within some given number of actions. Even in this more restrictive setting the resulting decision problems are either pspace-complete or np-complete. Our final formulation requires the environment to be history independent and bounded. In these cases polynomial time algorithms exist: for deterministic environments the decision problems are nl-complete; in non-deterministic environments, p-complete.     

一种多Agent系统的社会规范

指出有关Agent社会规范研究中存在的问题,通过借鉴Coleman的社会学理论,提出一种基于权 利分配的Agent社会规范的概念.通过放宽平均权利分配的假设,给出了多Agent系统中社会规 范的形式定义,将规范的设计归结为约束满足问题.讨论了社会规范的合理性,并给出规范建 立和废除的条件.最后,针对对称利益局势讨论了社会规范的合理性,并给出了一个价值均衡 算法以改进规范的合理性,从而有助于推进基于市场的多Agent系统的研究.     

The Dynamics of Syntactic Knowledge

The syntactic approach to epistemic logic avoids the logicalomniscience problem by taking knowledge as primary rather thanas defined in terms of possible worlds. In this study, we combinethe syntactic approach with modal logic, using transition systemsto model reasoning. We use two syntactic epistemic modalities:‘knowing at least’ a set of formulae and ‘knowingat most’ a set of formulae. We are particularly interestedin models restricting the set of formulae known by an agentat a point in time to be finite. The resulting systems are investigatedfrom the point of view of axiomatization and complexity. Weshow how these logics can be used to formalise non-omniscientagents who know some inference rules, and study their relationshipto other systems of syntactic epistemic logics, such as Ågotnesand Walicki (2004, Proc. 2nd EUMAS, pp. 1–10), Alechinaet al. (2004, Proc. 3rd AAMAS, pp. 601–613), Duc (1997,J. Logic Comput., 7, 633–648).     

Knowledge Condition Games

Understanding the flow of knowledge in multi-agent protocols is essential when proving the correctness or security of such protocols. Current logical approaches, often based on model checking, are well suited for modeling knowledge in systems where agents do not act strategically. Things become more complicated in strategic settings. In this paper we show that such situations can be understood as a special type of game – a knowledge condition game – in which a coalition “wins” if it is able to bring about some epistemic condition. This paper summarizes some results relating to these games. Two proofs are presented for the computational complexity of deciding whether a coalition can win a knowledge condition game with and without opponents (Σ₂P-complete and NP-complete respectively). We also consider a variant of knowledge condition games in which agents do not know which strategies are played, and prove that under this assumption, the presence of opponents does not affect the complexity. The decision problem without opponents is still NP-complete, but requires a different proof.Sieuwert van Otterloo thanks the Institute for Logic, Language and Information in Amsterdam for its hospitality during the period that this paper was finalized.     

Phase Portrait Modeling of a Nonlinear System with a Dynamic Fuzzy Network

Fuzzy logic and neural networks are two important technologies for modeling and control of dynamical systems and have been constrained by the non-dynamical nature of their some popular architectures. There exist problems such as large rule bases (i.e., curse of dimensionality), long training times, the need to determine buffer lengths. This article proposes to overcome these major problems in phase portrait modeling of a nonlinear system with a dynamic fuzzy network (DFN) with unconstrained connectivity and with dynamic fuzzy processing units called “feurons”. Nonlinear physical system properties can be encapsulated by DFN. As an example, DFN has been used as the modeler for some nonlinear physical system such as chaotic, limit cycle, oscillator. The minimization of an integral quadratic performance index subject to dynamic equality constraints is considered for a phase portrait modeling application. For gradient computation adjoint sensitivity method has been used. Its computational complexity is significantly less than direct sensitivity method, but it requires a backward integration capability. We used first and approximate second order gradient-based methods including Broyden–Fletcher–Golfarb–Shanno algorithm to update the parameters of the dynamic fuzzy networks yielding faster rate of convergence     

Relaxation as a platform for cooperative answering

Responses to queries posed by a user of a database do not always contain the information desired. Database answers to a query, although they may be logically correct, can sometimes be misleading. Research in the area of cooperative answering for databases and deductive databases seeks to rectify these problems. We introduce a cooperative method calledrelaxation for expanding deductive database and logic programming queries. The relaxation method expands the scope of a query by relaxing the constraints implicit in the query. This allows the database to return answers related to the original query as well as the literal answers themselves. These additional answers may be of interest to the user. In section 1 we introduce the problem and method. In Section 2 we give some background on the research done in cooperative answering. Section 3 discusses the relaxation method, a potential control strategy, and uses. Section 4 looks at a semantic counterpart to this notion. In Section 5 we explore some of the control and efficiency issues. We enumerate open issues in Section 6, and conclude in Section 7.     

Formal models and algorithms for decentralized decision making under uncertainty

Over the last 5 years, the AI community has shown considerable interest in decentralized control of multiple decision makers or “agents” under uncertainty. This problem arises in many application domains, such as multi-robot coordination, manufacturing, information gathering, and load balancing. Such problems must be treated as decentralized decision problems because each agent may have different partial information about the other agents and about the state of the world. It has been shown that these problems are significantly harder than their centralized counterparts, requiring new formal models and algorithms to be developed. Rapid progress in recent years has produced a number of different frameworks, complexity results, and planning algorithms. The objectives of this paper are to provide a comprehensive overview of these results, to compare and contrast the existing frameworks, and to provide a deeper understanding of their relationships with one another, their strengths, and their weaknesses. While we focus on cooperative systems, we do point out important connections with game-theoretic approaches. We analyze five different formal frameworks, three different optimal algorithms, as well as a series of approximation techniques. The paper provides interesting insights into the structure of decentralized problems, the expressiveness of the various models, and the relative advantages and limitations of the different solution techniques. A better understanding of these issues will facilitate further progress in the field and help resolve several open problems that we identify. This work was done while S. Seuken was a graduate student in the Computer Science Department of the University of Massachusetts, Amherst.     

Deontic logics for prioritized imperatives

When a conflict of duties arises, a resolution is often sought by use of an ordering of priority or importance. This paper examines how such a conflict resolution works, compares mechanisms that have been proposed in the literature, and gives preference to one developed by Brewka and Nebel. I distinguish between two cases – that some conflicts may remain unresolved, and that a priority ordering can be determined that resolves all – and provide semantics and axiomatic systems for accordingly defined dyadic deontic operators. A preliminary version was presented to the working group “Law and logic’ of the XXII. World Congress of Philosophy of Law and Social Philosophy (IVR 2005), 24–29 May 2005, Granada, Spain.     

图像数据受限下的处理与分析

恶劣复杂及对抗环境下产生的图像数据通常受限,常具有非完整、不确定、小样本、小目标的全部或部分特性,与通常的图像大数据相比,对受限图像数据处理和分析的方法有明显区别：大数据的统计特性显著依赖于中心极限定理下的3σ原则,而受限下的图像数据统计一致性弱,难以体现可信且鲁棒的集中优势特点;遮挡、伪装等情况导致样本信息乃至维度都具有不完整性或非确定性,以模糊数学为基础的系列处理方法导致计算量剧增;以深度学习为代表的系列大数据处理方法得到巨大发展,但由于受限图像数据的处理和分析基本属于不可逆的逆问题,其解空间一般为高维子空间,如何可信鲁棒地确定空间中的解,目前尚无有效可行的通用理论和方法;采用隶属度为测度的系列方法需紧密依赖融入先验知识构造的代价函数。为促进受限图像数据的研究,梳理了对其处理和分析的机理、方法、手段以及遇到的困难,提出了可能的突破方法,以及催生的研究范式改变,以求抛砖引玉,吸引更多学者从事该研究。