一种Agent的偏好系统及其建立

受到Agent偏好模型的启发,提出了一个新的描述人们行为的偏好系统称为AF系统,它将Michael Freund的理性偏好推理与Adams提出的经典的归纳逻辑和概率逻辑相结合,即借助经典的逻辑系统,把人们的逻辑推理和以人们的偏好取向为基础的常识性推理以及以主观愿望为基础的意向推理结合在一起成为一个有机系统,并且在这个系统下提出Agent的理性偏好的建立方法以及推理步骤.最后给出一个实例,说明它能根据人们的部分愿望,全面估计人们的偏好走向,而且一旦人们的基本态度有所转向,偏好结构也可做相应调整,无需做根本改动,因此它具有鲁棒性和实用价值.     

Logical omniscience, semantics, and models of belief

Logical omniscience may be described (roughly) as the state of affairs in which an agent explicitly believes anything which is logically entailed by that agent's beliefs. It is widely agreed that humans are not logically omniscient, and that an adequate formal model of belief, coupled with a correct semantic theory, would not entail logical omniscience. Recently, two prominent models of belief have emerged which purport both to avoid logical omniscience and to provide an intuitively appealing semantics. The first of these models is due to Levesque (1984 b ); the second to Fagin and Halpem (1985). It is argued herein that each of these models faces serious difficulties. Detailed criticisms are presented for each model, and a computationally oriented theory of intensions is presented which provides the foundation for a new formal model of belief. This formal model is presented in a decidable subset of first-order logic and is shown to provide a solution to the general problem of logical omniscience. The model provides for the possibility of belief revision and places no a priori restrictions upon an agent's representation language.     

Constructive belief and rational representation

It is commonplace in artificial intelligence to divide an agent's explicit beliefs into two parts: the beliefs explicitly represented or manifest in memory, and the implicitly represented or constructive beliefs that are repeatedly reconstructed when needed rather than memorized. Many theories of knowledge view the relation between manifest and constructive beliefs as a logical relation, with the manifest beliefs representing the constructive beliefs through a logic of belief. This view, however, limits the ability of a theory to treat incomplete or inconsistent sets of beliefs in useful ways. We argue that a more illuminating view is that belief is the result of rational representation. In this theory, the agent obtains its constructive beliefs by using its manifest beliefs and preferences to rationally (in the sense of decision theory) choose the most useful conclusions indicated by the manifest beliefs.     

Sequent forms of Herbrand theorem and their applications

New sequent forms* of the famous Herbrand theorem are proved for first-order classical logic without equality. These forms use the original notion of an admissible substitution and a certain modification of the Herbrand universe, which is constructed from constants, special variables, and functional symbols occurring only in the signature of an initial theory. Other well-known forms of the Herbrand theorem are obtained as special cases of the sequent ones. Besides, the sequent forms give an approach to the construction and theoretical investigation of computer-oriented calculi for efficient logical inference search in the signature of an initial theory. In a comparably simple way, they provide us with some technique for proving the completeness and soundness of the calculi. *A part of this investigation was performed during a visit to the University of Liverpool supported by the grant NAL/00841/G given by the Nuffield foundation.     

Explanation-based learning: its role in problem solving

Abstract

‘Explanation-based’ learning is a semantically-driven. knowledge-intensive paradigm for machine learning which contrasts sharply with syntactic or ‘similarity-based’ approaches. This paper redevelops the foundations of EBL from the perspective of problem-solving. Viewed in this light, the technique is revealed as a simple modification to an inference engine which gives it the ability to generalize the conditions under which the solution to a particular problem holds. We show how to embed generalization invisibly within the problem solver, so that it is accomplished as inference proceeds rather than as a separate step. The approach is also extended to the more complex domain of planning to illustrate that it is applicable to a variety of logic-based problem-solvers and is by no means restricted to only simple ones. We argue against the current trend to isolate learning from other activity and study it separately, preferred instead to integrate it into the very heart of problem solving.     

A heuristic search approach to planning with temporally extended preferences

Planning with preferences involves not only finding a plan that achieves the goal, it requires finding a preferred plan that achieves the goal, where preferences over plans are specified as part of the planner's input. In this paper we provide a technique for accomplishing this objective. Our technique can deal with a rich class of preferences, including so-called temporally extended preferences (TEPs). Unlike simple preferences which express desired properties of the final state achieved by a plan, TEPs can express desired properties of the entire sequence of states traversed by a plan, allowing the user to express a much richer set of preferences. Our technique involves converting a planning problem with TEPs into an equivalent planning problem containing only simple preferences. This conversion is accomplished by augmenting the inputed planning domain with a new set of predicates and actions for updating these predicates. We then provide a collection of new heuristics and a specialized search algorithm that can guide the planner towards preferred plans. Under some fairly general conditions our method is able to find a most preferred plan—i.e., an optimal plan. It can accomplish this without having to resort to admissible heuristics, which often perform poorly in practice. Nor does our technique require an assumption of restricted plan length or make-span. We have implemented our approach in the HPlan-P planning system and used it to compete in the 5th International Planning Competition, where it achieved distinguished performance in the Qualitative Preferences track.     

三次有理Bézier曲线的形状调整方法

给出了两类调整三次有理Bézier曲线形状的方法。一类方法是使曲线通过给定的插值点,从而实现曲线的形状调整。另一类方法是将曲线上的点作为控制多边形两边连线段上的分点,通过调整分线段的比例,实现对曲线的形状调整。针对不同情况,分别给出了权因子的计算公式。计算方法简单,使用方便,并使三次有理Bézier曲线的形状调整更加具体和明确。同时,由计算结果得到了任意三次有理Bézier曲线不相交的充分必要条件。     

An algebraic theory of functional and multivalued dependencies in relational databases

Computation of the dependency basis is the fundamental step in solving the membership problem for functional dependencies (FDs) and multivalued dependencies (MVDs) in relational database theory. We examine this problem from an algebraic perspective. We introduce the notion of the inference basis of a set M of MVDs and show that it contains the maximum information about the logical consequences of M. We propose the notion of a dependency-lattice and develop an algebraic characterization of inference basis using simple notions from lattice theory. We also establish several interesting properties of dependency-lattices related to the implication problem. Founded on our characterization, we synthesize efficient algorithms for (a): computing the inference basis of a given set M of MVDs; (b): computing the dependency basis of a given attribute set w.r.t. M; and (c): solving the membership problem for MVDs. We also show that our results naturally extend to incorporate FDs also in a way that enables the solution of the membership problem for both FDs and MVDs put together. We finally show that our algorithms are more efficient than existing ones, when used to solve what we term the ‘generalized membership problem’.     

Logical Dialogues with Explicit Preference Profiles and Strategy Selection

The Barth–Krabbe–Hintikka–Hintikka Problem, independently raised by Barth and Krabbe (From axiom to dialogue: a philosophical study of logics and argumentation. Walter de Gruyter, Berlin, 1982) and Hintikka and Hintikka (The sign of three: Peirce, Dupin, Holmes. In: Eco U, Sebeok TA (eds) Sherlock Holmes confronts modern logic: Toward a theory of information-seeking through questioning. Indiana University Press, Bloomington, 1983), is the problem of characterizing the strategic reasoning of the players of dialogical logic and game-theoretic semantics games from rational preferences rather than rules. We solve the problem by providing a set of preferences for players with bounded rationality and specifying strategic inferences from those preferences, for a variant of logical dialogues. This solution is generalized to both game-theoretic semantics and orthodox dialogical logic (classical and intuitionistic).     

From machine learning to machine reasoning

A plausible definition of “reasoning” could be “algebraically manipulating previously acquired knowledge in order to answer a new question”. This definition covers first-order logical inference or probabilistic inference. It also includes much simpler manipulations commonly used to build large learning systems. For instance, we can build an optical character recognition system by first training a character segmenter, an isolated character recognizer, and a language model, using appropriate labelled training sets. Adequately concatenating these modules and fine tuning the resulting system can be viewed as an algebraic operation in a space of models. The resulting model answers a new question, that is, converting the image of a text page into a computer readable text. This observation suggests a conceptual continuity between algebraically rich inference systems, such as logical or probabilistic inference, and simple manipulations, such as the mere concatenation of trainable learning systems. Therefore, instead of trying to bridge the gap between machine learning systems and sophisticated “all-purpose” inference mechanisms, we can instead algebraically enrich the set of manipulations applicable to training systems, and build reasoning capabilities from the ground up.     

Argumentative Agent Deliberation, Roles and Context

This paper presents an argumentation based framework to support an agent's deliberation process for drawing conclusions under a given policy. The argumentative policy of the agent is able to take into account the roles agents can have within a context pertaining to an environment of interaction. The framework uses roles and context to define policy preferences at different levels of deliberation allowing a modular representation of the agent's knowledge that avoids the need for explicit qualification of the agent's decision rules. We also employ a simple form of abduction to deal with the incompleteness and evolving nature of the agent's knowledge of the external environment and illustrate how an agent's self deliberation can affect the mode of interaction between agents. The high degree of modularity of the framework gives it a simple computational model in which the agent's deliberation can be naturally implemented.     

Update by means of inference rules

Katsuno and Mendelzon have distinguished two abstract frameworks for reasoning about change: theory revision and theory update. Theory revision involves a change in knowledge or belief with respect to a static world. By contrast, theory update involves a change of knowledge or belief in a changing world. In this paper, we are concerned with theory update. Winslett has shown that theory update should be computed “one model at a time.” Accordingly, we focus exclusively on the update of interpretations. We begin with a study of revision programming, introduced by Marek and Truszcyński to formulize interpretation update in a language similar to logic programming. While revision programs provide a useful and natural definition of interpretation update, they are limited to a fairly restricted set of update rules. Accordingly, we introduce the more general notion of rule update—interpretation update by arbitrary sets of inference rules. We show that Winslett's approach to update by means of arbitrary sets of formulas corresponds to a simple subclass of rule update. We also specify a simple embedding of rule update in Reiter’s default logic, obtained by augmenting the original update rules with default rules encoding the commonsense law of inertia—the principle that things change only when they are made to.     

The Achievement of Knowledge Bases by Cycle Search

Forward chaining is an algorithm that is particularly simple and therefore used in many inference systems. It computes the facts that are implied by a set of facts and rules. Unfortunately, this algorithm is not complete with respect to negation. To solve this problem, it is possible, in the context of propositional calculus, to automatically add the rules needed to make forward chaining complete. This transformation is a logical compilation of knowledge bases. This article presents a new method, based on a cycle search in a graph associated to the set of rules to compile, which allows a precise identification of what is needed for completeness.     

Inductive inference of logic programs based on algebraic semantics

In this paper we present a new inductive inference algorithm for a class of logic programs, calledlinear monadic logic programs. It has several unique features not found in Shapiro’s Model Inference System. It has been proved that a set of trees isrational if and only if it is computed by a linear monadic logic program, and that the rational set of trees is recognized by a tree automaton. Based on these facts, we can reduce the problem of inductive inference of linear monadic logic programs to the problem of inductive inference of tree automata. Further several efficient inference algorithms for finite automata have been developed. We extend them to an inference algorithm for tree automata and use it to get an efficient inductive inference algorithm for linear monadic logic programs. The correctness, time complexity and several comparisons of our algorithm with Model Inference System are shown.     

Towards a Possibilistic Logic Handling of Preferences

The classical way of encoding preferences in decision theory is by means of utility or value functions. However agents are not always able to deliver such a function directly. In this paper, we relate three different ways of specifying preferences, namely by means of a set of particular types of constraints on the utility function, by means of an ordered set of prioritized goals expressed by logical propositions, and by means of an ordered set of subsets of possible choices reaching the same level of satisfaction. These different expression modes can be handled in a weighted logical setting, here the one of possibilistic logic. The aggregation of preferences pertaining to different criteria can then be handled by fusing sets of prioritized goals. Apart from a better expressivity, the benefits of a logical representation of preferences are to put them in a suitable format for reasoning purposes, or for modifying them.     

System reduction via truncated Hankel matrices

The problem of approximating Hankel operators of finite or infinite rank by lower-rank Hankel operators is considered. For efficiency, truncated Hankel matrices are used as the intermediate step before other existing algorithms such as theCF algorithms are applied to yield the desirable approximants. If the Hankel operator to be approximated is of finite rank, the order of approximation by truncated Hankel operators is obtained. It is also shown that when themths-number is simple, then rational symbols of the best rank-m Hankel approximants of thenth truncated Hankel matrices converge uniformly to the corresponding rational symbol of the best rank-m Hankel approximant of the original Hankel operator asn tends to infinity. Supported by SDIO/IST managed by the U.S. Army under Contract No. DAAL03-87-K-0025 and also supported by the National Science Foundation under Grant No. DMS 8602337. Supported by SDIO/IST managed by the U.S. Army under Contract No. DAAL03-87-K-0025. Supported by the National Science Foundation under Grant No. DMS 8602337.     

Rational Communication in Multi-Agent Environments

We address the issue of rational communicative behavior among autonomous self-interested agents that have to make decisions as to what to communicate, to whom, and how. Following decision theory, we postulate that a rational speaker should design a speech act so as to optimize the benefit it obtains as the result of the interaction. We quantify the gain in the quality of interaction in terms of the expected utility, and we present a framework that allows an agent to compute the expected utilities of various communicative actions. Our framework uses the Recursive Modeling Method as the specialized representation used for decision-making in a multi-agent environment. This representation includes information about the agent's state of knowledge, including the agent's preferences, abilities and beliefs about the world, as well as the beliefs the agent has about the other agents, the beliefs it has about the other agents' beliefs, and so on. Decision-theoretic pragmatics of a communicative act can be then defined as the transformation the act induces on the agent's state of knowledge about its decision-making situation. This transformation leads to a change in the quality of interaction, expressed in terms of the expected utilities of the agent's best actions before and after the communicative act. We analyze decision-theoretic pragmatics of a number of important kinds of communicative acts and investigate their expected utilities using examples. Finally, we report on the agreement between our method of message selection and messages that human subjects choose in various circumstances, and show an implementation and experimental validation of our framework in a simulated multi-agent environment.     

Controlling the learning process of real-time heuristic search

Real-time search provides an attractive framework for intelligent autonomous agents, as it allows us to model an agent's ability to improve its performance through experience. However, the behavior of real-time search agents is far from rational during the learning (convergence) process, in that they fail to balance the efforts to achieve a short-term goal (i.e., to safely arrive at a goal state in the present problem solving trial) and a long-term goal (to find better solutions through repeated trials). As a remedy, we introduce two techniques for controlling the amount of exploration, both overall and per trial. The weighted real-time search reduces the overall amount of exploration and accelerates convergence. It sacrifices admissibility but provides a nontrivial bound on the converged solution cost. The real-time search with upper bounds insures solution quality in each trial when the state space is undirected. These techniques result in a convergence process more stable compared with that of the Learning Real-Time algorithm.