Goal Change in the Situation Calculus

Although there has been much discussion of belief change (e.g.[4, 21]), goal change has not received much attention. In thispaper, we propose a method for goal change in the frameworkof Reiter's; [12] theory of action in the situation calculus[8, 10], and investigate its properties. We extend the frameworkdeveloped by Shapiro et al. [17] and Shapiro and Lespérance[16], where goals and goal expansion were modelled, but goalcontraction was not.     

具有极点约束的输出反馈完整性控制器设计

基于LMI理论,给出了线性连续时不变系统具有极点约束的输出反馈完整性控制器存在的充分条件,并在此基础上提出一种输出反馈完整性控制器的设计方法。使得当传感器或执行器发生故障时。闭环系统渐近稳定,且闭环极点位于左半复平面的指定区域。数值示例说明了该方法的有效性。     

Solving Systems of Difference Constraints Incrementally

Difference constraints systems consisting of inequalities of the form x _i - x _j b _i,j occur in many applications, most notably those involving temporal reasoning. Often, it is necessary to maintain a solution to such a system as constraints are added, modified, and deleted. Existing algorithms handle modifications by solving the resulting system anew each time, which is inefficient. The best known algorithm to determine if a system of difference constraints is feasible (i.e., if it has a solution) and to compute a solution runs in Θ (mn) time, where n is the number of variables and m is the number of constraints. This paper presents a new efficient incremental algorithm for maintaining a solution to a system of difference constraints. As constraints are added, modified, or deleted, the algorithm determines if the new system is feasible and updates its solution. When the system becomes infeasible, the algorithm continues to process changes until it becomes feasible again, at which point a feasible solution will be produced. The algorithm processes the addition of a constraint in time O(m + n log n) and the removal of a constraint in constant time when the original system is feasible. More precisely, additions are processed in time O( || Δ || + |Δ| log|Δ| ) , where |Δ| is the number of variables whose values are changed to compute the new feasible solution, and || Δ || is the number of constraints involving the variables whose values are changed. When the original system is infeasible, the algorithm processes any change in O(m + n log n) amortized time. The new algorithm can also be used to check for the existence of negative cycles in dynamic graphs. Received September 25, 1997; revised November 16, 1997.     

Integrating Discrete and Continuous Change in a Logical Framework

The goal of our work is to develop theoretical foundations for the representation of knowledge in domains in which properties may vary continuously. One achievement of our research is that it extends the applicability of current research on theories of action. Furthermore, we are able to apply known approaches to the frame and ramification problems, developed for discretely changing worlds, to domains in which the world changes continuously.
Our approach is based on the discrete situation calculus and on a monotonic solution to the frame problem. In order to address the combined frame and ramification problems, we extend Lin and Reiter's work. We use Pinto and Reiter's extension to the situation calculus to represent occurrences . We extend this work further to allow for reasoning by default. For example, if we know that a ball is falling and we do not have any reason to believe that an action would interfere with the ball's motion, then we assume that the ball will hit the ground. Finally, we extend the language of the situation calculus to allow for properties that change within situations. We also show that our proposed situation calculus inherits the solutions to the frame and ramification problems.     

Cost-Based Arc Consistency for Global Cardinality Constraints

A global cardinality constraint (gcc) is specified in terms of a set of variables X={x ₁,...,x _p} which take their values in a subset of V={v ₁,...,v _d}. It constrains the number of times each value v _iV is assigned to a variable in X to be in an interval [l _i,u _i]. A gcc with costs (costgcc) is a generalization of a gcc in which a cost is associated with each value of each variable. Then, each solution of the underlying gcc is associated with a global cost equal to the sum of the costs associated with the assigned values of the solution. A costgcc constrains the global cost to be less than a given value. Cardinality constraints with costs have proved very useful in many real-life problems, such as traveling salesman problems, scheduling, rostering, or resource allocation. For instance, they are useful for expressing preferences or for defining constraints such as a constraint on the sum of all different variables. In this paper, we present an efficient way of implementing arc consistency for a costgcc. We also study the incremental behavior of the proposed algorithm.     

基于装配约束动态管理的虚拟拆卸

装配约束是虚拟拆卸环境下必须考虑的装配体的重要信息,提出虚拟拆卸过程中装配约束的动态管理机制,并实现了基于装配约束导航的虚拟拆卸。装配约束的动态管理包括虚拟环境下装配约束的获取、表达以及拆卸过程中装配约束的动态维护,即装配约束的动态解除和产生,文中用装配约束图表达零件间的装配约束,提出装配约束的间接解除方法,并实现了基于装配约束推理的零件可拆卸方向的推导。最后,通过一个简单装配体的拆卸实例,对文中方法进行了验证。     

一种基于案例和约束的排课系统

排课问题其本质就是时间表问题,属于典型的组合优化和不确定性调度问题,已经被证明为NP—Complete类问题。针对已有排课案例中大量知识和排课过程大量存在的教师和学生的特殊需求,提出了面向规则的形式化描述：TPQE描述体系,对排课问题中的强规则和弱规则进行了描述和形式化表示,同时提出了规则约束力的表示方法,设计了用于求解最大化WTPQE权值的算法——weighted SAT,开发相应的原型系统。     

面向微处理器验证的约束描述语言及其编译器

该文提出了一种用于微处理器体系结构级测试程序自动生成的约束描述语言,并设计实现了该语言的编译器,详细介绍了语言特性以及为了生成合法体系结构级测试程序,编译器所做的特殊处理。最后给出了利用该语言对DLX微处理器进行验证的实验和结果。     

独立于设计者的行动推理

高水平的智能机器人要求能够独立地对环境进行感知并进行正确的行动推理.在情境演算行动理论中表示带有感知行动及知识的行动推理需要外部设计者为agent写出背景公理、感知结果及相应的知识变化,这是一种依赖于设计者的行动推理.情境演算行动理论被适当扩充,感知器的表示被添加到行动理论的形式语言中,并把agent新知识的产生建立在感知器的应用结果之上.扩充后的系统能够形式化地表示机器人对环境的感知并把感知结果转换为知识,还能进行独立于设计者的行动推理,同时让感知行动的“黑箱”过程清晰化.     

一种意向驱动式面向agent程序设计语言

提出了一种意向驱动式面向agent程序设计语言--AOPLID(agent-oriented programming language with intention driver).该语言基于开放式情景演算OSC(open situation calculus),吸收了GOLOG的合理成分,加入对信念、意向、能力、策略等agent心智成分的处理,使用信念修正原语处理通信交互以及事件响应等外因行动,并采用了一种新颖的离线规划和在线执行相结合的运行方式,从而解决了GOLOG语言在应用于面向agent程序设计时不能有效地描述处理agent心智状态,无法处理外因行动等问题.给出了AOPLID语言语法结构,基于OSC的AOPLID程序语义以及AOPLID程序实例.     

行动推理中循环因果关系的研究

近年来行动推理的研究成为人工智能领域的热门问题,而结果问题是目前行动推理研究的核心问题之一．该文针对许多行动推理系统不能处理循环因果关系的问题,提出了解决方法．基于适当修改后的McCain和Turner的因果理论,该文提出了一种能处理循环依赖的理论转化方法．转化后的因果理论消除了循环依赖,而且可以采用单调推理方法．基于因果闭包语义,证明了转化前后的因果理论具有相同的模型．当因果关系不存在循环依赖时,该文方法得到与McCain,Turner方法(1997)相同的结果．     

Modeling Agent Negotiation Via Fuzzy Constraints in E-Business

In e-business, disputes between two or more parties arise for various reasons and involve different issues. Thus, resolution of these disputes frequently relies on some form of negotiation. This article presents a general problem-solving framework for modeling multi-issue multilateral agent negotiation using fuzzy constraints in e-business. Fuzzy constraints are thus used not only to define each agent's demands involving human concepts, but also to represent the relationships among agents. A concession strategy, based on fuzzy constraint-based problem-solving, is proposed to relax demands, and a trade-off strategy is presented to evaluate existing alternatives. This approach provides a systematic method for reaching an agreement that benefits all agents with a high satisfaction degree of constraints. Meanwhile, by applying the method, agents can move toward an agreement more quickly, because their search focuses only on the feasible solution space. An example application to negotiate an insurance policy among agents is provided to demonstrate the usefulness and effectiveness of the proposed framework.     

Unification Modulo <Emphasis Type="Italic">ACUI</Emphasis> Plus Distributivity Axioms

E-unification problems are central in automated deduction. In this work, we consider unification modulo theories that extend the well-known ACI or ACUI by adding a binary symbol * that distributes over the AC(U)I-symbol +. If this distributivity is one-sided (say, to the left), we get the theory denoted AC(U)ID_l; we show that AC(U)ID_l-unification is DEXPTIME-complete. If * is assumed two-sided distributive over +, we get the theory denoted AC(U)ID; we show unification modulo AC(U)ID to be NEXPTIME-decidable and DEXPTIME-hard. Both AC(U)ID_l and AC(U)ID seem to be of practical interest, for example, in the analysis of programs modeled in terms of process algebras. Our results, for the two theories considered, are obtained through two entirely different lines of reasoning. A consequence of our methods of proof is that, modulo the theory that adds to AC(U)ID the assumption that * is associative-commutative, or just associative, unification is undecidable.     

BSCRP网:机器人规划的赋时有色网实现方法

为了解决情景演算无法解决框架问题和生成动作序列效率底的问题,提出了一种基于情景演算推理规则的表示机器人规划的赋时有色网实现方法——BSCRP网(representation based on situation calculus for robot plan),并提出了一种基于双向搜索策略的BSCRP网系统的构造方法。实验结果表明了机器人规划的BSCRP网系统不仅能形式化地描述动作、状态以及动作和状态之间的关系,而且能动态地规划出实现目标的动作序列并计算执行动作序列所需时间。