Utility Functions for Ceteris Paribus Preferences

Ceteris paribus (all-else equal) preference statements concisely represent preferences over outcomes or goals in a way natural to human thinking. Although deduction in a logic of such statements can compare the desirability of specific conditions or goals, many decision-making methods require numerical measures of degrees of desirability. To permit ceteris paribus specifications of preferences while providing quantitative comparisons, we present an algorithm that compiles a set of qualitative ceteris paribus preferences into an ordinal utility function. Our algorithm is complete for a finite universe of binary features. Constructing the utility function can, in the worst case, take time exponential in the number of features, but common independence conditions reduce the computational burden. We present heuristics using utility independence and constraint-based search to obtain efficient utility functions.     

Optimal Selection of Uncertain Actions by Maximizing Expected Utility

A new means of action selection via utility fusion is introduced as an alternative to both sensor fusion and command fusion. Distributed asynchronous behaviors indicate the utility of various possible states and their associated uncertainty. A centralized arbiter then combines these utilities and probabilities to determine the optimal action based on the maximization of expected utility. The construction of a utility map allows the system being controlled to be modeled and compensated for; experimental results verify that this approach improves performance.     

Representation of Preferences by Quasi-Linear Means

Starting by quasilinear means, we propose and analyze functionals that allow to represent the preferences of the decision maker in a more general setting; the preference order in the set of the alternatives depends on the way the functional has been generated. The functionals of this kind enjoy classical properties as independence and dominance principle. Anyway we stress that to make use of a single functional is not sufficient to describe paradoxical situations that arise for istance in the Kahneman and Tversky experiment.     

Empirical Game Theoretic Models: Computational Issues

This paper discusses computational issues raised by ageneric solution and estimation methodology applicableto a broad range of empirical game theoretic modelswith incomplete information. By combining the use ofMonte Carlo simulation techniques with that of smoothkernel estimation of empirical distribution functions,the authors develop a numerical algorithm ofunparalleled performance and flexibility applicable,in particular, to models for which no operationalsolutions currently exist. An illustration to a set ofprocurement data from the French aerospace industry isused to illustrate the operation of this algorithm.     

控制系统的满意优化效用理论研究及应用

提出了满意优化不同于传统优化的基本特点,并依此建立了控制系统参数设计的满意优化模型.由所建立的效用函数及其期望,设计了效用函数下的满意优化算法,并进一步探讨了文中所设计的效用函数具有有界闭凸性及其在可测非负实值函数下的基本运算性质,为该算法的应用推广提供了理论基础.单回路控制系统下的仿真算例数据表明,效用函数下的满意优化算法具有良好的收敛性.     

Active acquisition of user models: Implications for decision-theoretic dialog planning and plan recognition

This article investigates the implications ofactive user model acquisition upon plan recognition, domain planning, and dialog planning in dialog architectures. A dialog system performs active user model acquisition by querying the user during the course of the dialog. Existing systems employ passive strategies that rely on inferences drawn from passive observation of the dialog. Though passive acquisition generally reduces unnecessary dialog, in some cases the system can effectively shorten the overall dialog length by selectively initiating subdialogs for acquiring information about the user.We propose a theory identifying conditions under which the dialog system should adoptactive acquisition goals. Active acquisition imposes a set ofrationality requirements not met by current dialog architectures. To ensure rational dialog decisions, we propose significant extensions to plan recognition, domain planning, and dialog planning models, incorporating decision-theoretic heuristics for expected utility. The most appropriate framework for active acquisition is a multi-attribute utility model wherein plans are compared along multiple dimensions of utility. We suggest a general architectural scheme, and present an example from a preliminary implementation.The author will be at the Department of Computer Science, University of Toronto, untilThe author will be at the Department of Computer Science, University of Toronto, untilThe author will be at the Department of Computer Science, University of Toronto, untilThe author will be at the Department of Computer Science, University of Toronto, untilThe author will be at the Department of Computer Science, University of Toronto, untilThe author will be at the Department of Computer Science, University of Toronto, until     

基于效用曲线改进的前景理论价值函数

针对选取前景理论函数参数时仅考虑决策的不理性而并未区分决策者的风险态度这一特点,基于效用曲线改进了前景理论价值函数的形式并扩展了其参数范围.该函数借鉴效用曲线依据曲线形状区分决策者风险态度的方法,同时对比已有的实验数据,得出价值函数曲线形状与决策者风险态度相关,为价值函数参数选取提供了一定的理论依据.计算实例表明,该方法便于参数选取,决策结果稳定、有效,此外,风险决策时决策结果受参考点变化的影响远大于决策者不同的风险态度,在实际决策时对于参考点的选取需要非常谨慎.     

U-Clustering:基于效用聚类的激励学习算法

提出了一个新的效用聚类激励学习算法U-Clustering。该算法完全不用像U-Tree算法那样进行边缘节点的生成和测试,它首先根据实例链的观测动作值对实例进行聚类,然后对每个聚类进行特征选择,最后再进行特征压缩,经过压缩后的新特征就成为新的状态空间树节点。通过对NewYorkDriving[2,13]的仿真和算法的实验分析,表明U-Clustering算法对解决大型部分可观测环境问题是比较有效的算法。     

面向英汉词典编纂的粘贴工具的设计、实现及应用

分析和介绍一款用Delphi语言开发的面向英汉词典编纂的粘贴工具的设计、实现和应用。该工具软件依托微软视窗操作系统的进程间通讯机制,实现小巧、方便和实用的设计目标。在英汉词典的编写过程中使用该粘贴工具粘贴或插入频繁用到的特殊符号或专用文字块可以提高工作效率和减少录入错误。     

A Comparison of Probabilistic, Possibilistic and Evidence Theoretic Fusion Schemes for Active Object Recognition

One major goal of active object recognition systems is to extract useful information from multiple measurements. We compare three frameworks for information fusion and view-planning using different uncertainty calculi: probability theory, possibility theory and Dempster-Shafer theory of evidence. The system dynamically repositions the camera to capture additional views in order to improve the classification result obtained from a single view. The active recognition problem can be tackled successfully by all the considered approaches with sometimes only slight differences in performance. Extensive experiments confirm that recognition rates can be improved considerably by performing active steps. Random selection of the next action is much less efficient than planning, both in recognition rate and in the average number of steps required for recognition. As long as the rate of wrong object-pose classifications stays low the probabilistic implementation always outperforms the other approaches. If the outlier rate increases averaging fusion schemes outperform conjunctive approaches for information integration. We use an appearance based object representation, namely the parametric eigenspace, but the planning algorithm is actually independent of the details of the specific object recognition environment. Received: June 18, 1998; revised November 17, 1998     

A Rule-Based Approach to Developing Software Development Prediction Models

Managers of software development projects increasingly recognize the importance of planning and estimation and now have many sophisticated tools at their disposal. Despite this many systems are still delivered way behind schedule, cost far more to produce than original budget estimates and fail to meet user requirements.It is the contention of the authors that many existing tools are inadequate because they fail to embrace the significant body of knowledge accumulated by past and present project managers.This paper presents a new approach to planning which enables project managers to learn from the experience of others. The authors have adopted a bottom-up approach to planning which goes from the specific (planning the requirements capture and analysis process—RCA) to the general (planning the whole development process). A model, called MARCS, was constructed to give predictions of the resources (time, effort, cost, people) needed for the completion of and outcomes of the RCA process. Based on the predictions about the RCA process, the model then attempts to predict the resources and outcomes of the whole development process. MARCS is a combination of rule-based models and its main advantage is that it incorporates both qualitative and quantitative factors that can be easily identified and measured in the beginning of the development process.Empirical data concerning 107 projects developed by more than 70 organizations within UK, gathered through a two-stage mail survey was used for the construction and validation of the MARCS planning model.     

A Comparative Study of Game Theoretic and Evolutionary Models of Bargaining for Software Agents

Most of the existing work in the study of bargaining behavior uses techniques from game theory. Game theoretic models for bargaining assume that players are perfectly rational and that this rationality is common knowledge. However, the perfect rationality assumption does not hold for real-life bargaining scenarios with humans as players, since results from experimental economics show that humans find their way to the best strategy through trial and error, and not typically by means of rational deliberation. Such players are said to be boundedly rational. In playing a game against an opponent with bounded rationality, the most effective strategy of a player is not the equilibrium strategy but the one that is the best reply to the opponents strategy. The evolutionary model provides a means for studying the bargaining behaviour of boundedly rational players. This paper provides a comprehensive comparison of the game theoretic and evolutionary approaches to bargaining by examining their assumptions, goals, and limitations. We then study the implications of these differences from the perspective of the software agent developer.     

Facilitating the use of multi-attribute utility theory in expert systems:an aid for identifying the right relative importance weights of attributes

In general, expert system applications to real cases involve making decisions, i.e. selecting a suitable action among a set of possible alternative actions. A well-known standard method for modelling decision problems is the so-called multi-attribute utility theory (MAUT), a method in which the alternatives are viewed in terms of their attributes. A set of attributes are identified and a specific value and a suitable relative importance weight are assigned to each attribute. However, it is not easy for the expert to quantify the relative importance weight of an attribute: this assignment entails a certain abstraction activity from the expert and, as is well known, experts have difficulty in providing their knowledge in abstract and general terms. In order to overcome this difficulty we propose a method for automatically inferring relative importance weights from a set of specific action sequences. An action sequence is a list in chronological order of the actions executed by the expert when facing specific cases of decision problems. Providing action sequences requires no other effort but remembering specific episodes, and this task is much easier for experts than having to directly provide precise numbers expressing relative importance weights. Moreover in many cases action sequences are already stored in suitable records. Consider, for example, the list of medical tests executed on a given patient, a list included in the patient clinical record stored in the clinical database of a hospital. On the basis of these considerations the proposed method should be useful for designers of expert systems which face problems of choosing the right action among a set of alternative actions.     

一种基于效用和证据理论的可信软件评估方法

由于可信软件评估需求的动态多变以及专家主观决策的有限理性,多维多尺度可信软件评估问题是一个重要而困难的研究课题.在分析现有可信软件评估需求的基础上,提出一种基于效用和证据理论的可信软件评估方法.首先设计了一个需求驱动的可信指标树动态构造模型:开放式可信指标数据库和指标树生成算法;接着讨论分析了基于效用的可信软件定性和定量指标的信息预处理技术,并重点介绍基于分布式评估框架和Dempster合成规则的可信软件评估证据推理算法;最后通过案例证明了该方法的有效性和合理性.相信该模型的提出能对复杂环境下软件可信性评估理论的进一步研究起推动作用.     

传感器网络中基于帕累托最优效用的包转发研究

本文运用博弈论的观点和方法来解决传感器网络中的包转发问题。为传感器网络建立了包转发模型,分析了节点参与包转发会话所获得的帕累托最优效用,提出了基于帕累托最优效用的包转发算法POUPF,并证明了该算法能够建立纳什均衡以保证每个节点都获得帕累托最优效用。仿真结果表明：POUPF能够有效促进节点自发合作,确保了每个节点获得帕累托最优效用;任何偏离POUPF节点的包转发行为都会导致所有节点效用的下降。     

过度规划、部分可满足规划及简单偏好综述*

智能规划是人工智能的重要分支,它从某个特定问题的初始状态出发,寻找达到解决该问题的目标状态的动作序列,但是在许多真实问题中,往往没有足够的资源来实现所有目标。因此,智能规划中对软目标的研究包括过度规划、部分可满足规划和简单偏好,已成为近年来的热点。将对过度规划、部分可满足规划和简单偏好的主要研究成果进行综述,包括这几类问题的差异比较、主要解决方案以及对将来的展望。     

A General Framework for Expressing Preferences in Causal Reasoning and Planning

We consider the problem of representing arbitrary preferencesin causal reasoning and planning systems. In planning, a preferencemay be seen as a goal or constraint that is desirable, but notnecessary, to satisfy. To begin, we define a very general querylanguage for histories, or interleaved sequences of world statesand actions. Based on this, we specify a second language inwhich preferences are defined. A single preference defines abinary relation on histories, indicating that one history ispreferred to the other. From this, one can define global preferenceorderings on the set of histories, the maximal elements of whichare the preferred histories. The approach is very general andflexible; thus it constitutes a ‘base’ languagein terms of which higher-level preferences may be defined. Tothis end, we investigate two fundamental types of preferencesthat we call choice and temporal preferences. We consider concretestrategies for these types of preferences and encode them interms of our framework. We suggest how to express aggregatesin the approach, allowing, e.g. the expression of a preferencefor histories with lowest total action costs. Last, our approachcan be used to express other approaches and so serves as a commonframework in which such approaches can be expressed and compared.We illustrate this by indicating how an approach due to Sonand Pontelli can be encoded in our approach, as well as thelanguage PDDL3.     

A heuristic search algorithm with lexicographic goals

This paper describes a new general algorithm for graph search problems with additive lexicographic goals. The use of lexicographic goals in the formulation of search problems provides greater control and expressive power over the properties of solution paths. The algorithm, called METAL-A^N* can be used to find the set of all solutions to a goal problem. The fundamental concepts of the algorithm are explained and a simple example is used to trace its behaviour. Sufficient conditions that guarantee the completeness and admissibility of METAL-A^N* are also presented.     

按任意字段对数据排序的实用程序

在数据库应用系统中查看数据时,不同的用户希望按照自己的使用角度来排列数据,但是,在初始打开数据页面的时候,数据总是只能按照一种方式排序。如果能够实现用户点击自己希望的排序字段,数据就按照顺序与逆序方式交替显示,既可以满足各种用户对数据的排序需求了。因此,设计了一个通用的方法适用于任意字段按照顺序与逆序交替排列。