A Formal Approach to Agent Design: An Overview of Constraint-Based Agents

Formal models for agent design are important for both practical and theoretical reasons. The Constraint-Based Agent (CBA) design approach includes two formal models: Constraint Nets and Timed -automata. A constraint net models the agents and the environment symmetrically as, possibly hybrid, dynamical systems; a timed -automaton specifies the desired real-time dynamic behaviors of the situated agents. Given a constraint-based specification of the desired behavior, a constraint-based agent can be synthesized as a constraint solver. Using formal modeling and specification, it is also possible to verify complex agents as obeying real-time temporal constraint specifications. This overview paper presents a summary of the development and application of the CBA framework.     

A Constraint-Based Robotic Soccer Team

It is a challenging task for a team of multiple fast-moving robots to cooperate with each other and to compete with another team in a dynamic, real-time environment. For a robot team to play soccer successfully, various technologies have to be incorporated including robotic architecture, multi-agent collaboration and real-time reasoning. A robot is an integrated system, with a controller embedded in its plant. A robotic system is the coupling of a robot to its environment. Robotic systems are, in general, hybrid dynamic systems, consisting of continuous, discrete and event-driven components. Constraint Nets (CN) provide a semantic model for modeling hybrid dynamic systems. Controllers are embedded constraint solvers that solve constraints in real-time. A controller for our robot soccer team, UBC Dynamo98, has been modeled in CN, and implemented in Java, using the Java Beans architecture. A coach program using an evolutionary algorithm has also been designed and implemented to adjust the weights of the constraints and other parameters in the controller. The results demonstrate that the formal CN approach is a practical tool for designing and implementing controllers for robots in multi-agent real-time environments. They also demonstrate the effectiveness of applying the evolutionary algorithm to the CN-modeled controllers.     

基于约束的调度研究和实现

运用约束程序设计(CP)思想和技术来调度正成为一个新兴的研究领域。文章首先对CP和调度的相关领域知识进行了简要介绍;然后按照CP所倡导的问题建模和问题求解相分离的思想,建立起一般理论调度问题的约束模型,并设计实现了一个基于约束的调度求解算法CBS-1;并对一些典型问题进行了实验,实验结果表明算法提高了约束调度求解的效率和通用性。     

A formal mathematical framework for modeling probabilistic hybrid systems

The development of autonomous agents, such as mobile robots and software agents, has generated considerable research in recent years. Robotic systems, which are usually built from a mixture of continuous (analog) and discrete (digital) components, are often referred to as hybrid dynamical systems. Traditional approaches to real-time hybrid systems usually define behaviors purely in terms of determinism or sometimes non-determinism. However, this is insufficient as real-time dynamical systems very often exhibit uncertain behavior. To address this issue, we develop a semantic model, Probabilistic Constraint Nets (PCN), for probabilistic hybrid systems. PCN captures the most general structure of dynamic systems, allowing systems with discrete and continuous time/variables, synchronous as well as asynchronous event structures and uncertain dynamics to be modeled in a unitary framework. Based on a formal mathematical paradigm exploiting abstract algebra, topology and measure theory, PCN provides a rigorous formal programming semantics for the design of hybrid real-time embedded systems exhibiting uncertainty.      

Testing robot controllers using constraint programming and continuous integration

ContextTesting complex industrial robots (CIRs) requires testing several interacting control systems. This is challenging, especially for robots performing process-intensive tasks such as painting or gluing, since their dedicated process control systems can be loosely coupled with the robot’s motion control.ObjectiveCurrent practices for validating CIRs involve manual test case design and execution. To reduce testing costs and improve quality assurance, a trend is to automate the generation of test cases. Our work aims to define a cost-effective automated testing technique to validate CIR control systems in an industrial context.MethodThis paper reports on a methodology, developed at ABB Robotics in collaboration with SIMULA, for the fully automated testing of CIRs control systems. Our approach draws on continuous integration principles and well-established constraint-based testing techniques. It is based on a novel constraint-based model for automatically generating test sequences where test sequences are both generated and executed as part of a continuous integration process.ResultsBy performing a detailed analysis of experimental results over a simplified version of our constraint model, we determine the most appropriate parameterization of the operational version of the constraint model. This version is now being deployed at ABB Robotics’s CIR testing facilities and used on a permanent basis. This paper presents the empirical results obtained when automatically generating test sequences for CIRs at ABB Robotics. In a real industrial setting, the results show that our methodology is not only able to detect reintroduced known faults, but also to spot completely new faults.ConclusionOur empirical evaluation shows that constraint-based testing is appropriate for automatically generating test sequences for CIRs and can be faithfully deployed in an industrial context.     

Constraint Databases: Promising Technology or Just Intellectual Exercise?

This paper describes the state of Constraint Databases (CDBs), a young discipline at the intersection of Database Management, Constraint Programming, Computational Geometry and Operations Research. As in Constraint Logic Programming, constraints in CDBs are a first class data type, and can play many modeling roles including spatial and temporal behavior, complex design requirements, and partial and incomplete information, for which existing databases have proven inadequate. We motivate the importance of CDBs, outline the work in the area that has been done, the current trends, and future directions and challenges. We briefly discuss (1) constraint modeling, canonical forms and algebras, (2) data models and query languages, (3) indexing and approximation-based filtering, (4) constraint algebra algorithms and global optimization, and (5) systems and case studies. We argue that CDBs are a promising technology that will impact many important application realms, and furthermore have the potential to be integrated into future database systems, and operations research and constraint programming tools.     

智能机器人系统建模的新理论─—环递阶模型理论

本文走从语言文字描述到符号化再到形式化的崭新道路来探索智能机器人系统的建模问题。首先，为智能机器人系统建立了更全面、确切的语言文字描述，然后，通过直现地符号化，为智能机器人系统提出并建造成了一种新型的结构模型，命名为环递阶模型，最后，利用形式语言理论，将环递阶模型形式化，从而，首次将智能机器人系统整体形式化地建模成了一种上下文无关文法，为智能机器人系统的建模问题开发成了一种解析的框架。形成了一种新的理论，命名为环递阶模型理论。     

The CCUBE Constraint Object-Oriented Database System

Constraints provide a flexible and uniform way to represent diverse data capturing spatio-temporal behavior, complex modeling requirements, partial and incomplete information etc, and have been used in a wide variety of application domains. Constraint databases have recently emerged to deeply integrate data captured by constraints in databases. This paper reports on the development of the first constraint object-oriented database system, CCUBE, and describes its specification, design and implementation. The CCUBE system is designed to be used for the implementation and optimization of high-level constraint object-oriented query languages as well as for directly building software systems requiring extensible use of constraint database features. The CCUBE data manipulation language, Constraint Comprehension Calculus, is an integration of a constraint calculus for extensible constraint domains within monoid comprehensions, which serve as an optimization-level language for object-oriented queries. The data model for the constraint calculus is based on constraint spatio-temporal (CST) objects that may hold spatial, temporal or constraint data, conceptually represented by constraints. New CST objects are constructed, manipulated and queried by means of the constraint calculus. The model for the monoid comprehensions, in turn, is based on the notion of monoids, which is a generalization of collection and aggregation types. The focal point of our work is achieving the right balance between the expressiveness, complexity and representation usefulness, without which the practical use of the system would not be possible. To that end, CCUBE constraint calculus guarantees polynomial time data complexity, and, furthermore, is tightly integrated with the monoid comprehensions to allow deeply interleaved global optimization.     

实体造型中的几何约束

实体造型是一个基于约束的过程，完成从功能约束到几何约束、再到代数约束的转化而得到实体模型。本文讨论了几何约束的层次性及其表示，并且对几何约束同设计意图的关系进行了研究，提出了基于ＣＳＧ／ＧＣＧ／Ｂ－ｒｅｐ的模型表示。     

A modular design of Bayesian networks using expert knowledge: Context-aware home service robot

Recently, demand for service robots increases, and, particularly, one for personal service robots, which requires robot intelligence, will be expected to increase more. Accordingly, studies on intelligent robots are spreading all over the world. In this situation, we attempt to realize context-awareness for home robot while previous robot research focused on image processing, control and low-level context recognition. This paper uses probabilistic modeling for service robots to provide users with high-level context-aware services required in home environment, and proposes a systematic modeling approach for modeling a number of Bayesian networks. The proposed approach supplements uncertain sensor input using Bayesian network modeling and enhances the efficiency in modeling and reasoning processes using modular design based on domain knowledge. We verify the proposed method is useful as measuring the performance of context-aware module and conducting subjective test.     

吸尘机器人的现状及其智能系统的若干关键技术

吸尘机器人能实现室内环境全自动清洁,替代了传统的人工清洁,具有十分广阔的市场前景。介绍了国内外吸尘机器人产品现状;综合评述了其智能系统中的全区域覆盖、路径规划、环境建模及传感器等的研究现状,对关键技术的难点进行了说明,并对其发展前景做了展望。     

Integration of Heterogeneity for Human-Friendly Robotic Operations

The objective of this paper is to develop an analytical scheme to integrate the heterogeneity of human and robot functions to achieve a human-friendly robotic operations. The heterogeneity of human and robot functions can be characterized by the fact that humans are intelligent while robots are fast, powerful and accurate. Humans can use their knowledge and experience to quickly respond to unexpected events, which makes it easy for humans to deal with unstructured environments. In contrast, robots can easily enhance the mechanical power of humans and the ability of humans to work remotely. Therefore, robots are capable of performing precise and repetitive tasks at high speed or in a hazardous environment. The important issue, in light of human/robot heterogeneity, is how to plan and control a robotic operation such that the human and the robot can cooperate in a complementary manner. Thus, a task which cannot be done by either human or robot alone can be performed efficiently and robustly by both. This paper introduces a new paradigm for human/robot interactive systems, heterogeneous function-based human/robot cooperation. A new perceptive action reference frame has been developed in the paper. It matches human perception and robot sensory measurement, and provides a platform for modeling the human/robot cooperative operations. The theoretical results presented in the paper have laid down a foundation for stability analysis as well as a planning and control system design of human/robot integrated systems. The implementations and experimental results have clearly demonstrated the advantages of proposed methods.     

位－力驱动的线驱连续型机器人的动力学建模及实验验证

提出了一种位－力混合驱动的线驱连续型机器人的动力学模型。首先,基于集中质量矩阵法进行机器人动力学建模,将机器人动能的连续积分等效离散为三点求和形式,可简化建模过程并提升仿真的计算效率。其次,分析了驱动力与驱动线几何约束的力学关系,将线驱动作用等效建模为电机的驱动参数与牵引线张力的线性方程组,不仅可以精确地满足牵引线对系统的约束条件,还可以在不使用拉力传感器的条件下得到线的驱动力,降低了机器人成本及控制难度,这种方法适用于任意数量牵引线的连续型机器人。最后,将线驱连续型机器人的仿真和实验结果进行对比,机器人末端点的轨迹最大误差为3.85%,验证了所提模型的有效性。     

机床产品分布式协同约束模型研究

研究了机床产品协同开发中约束的种类和特点以及约束模型的建立方法,描述了约束网络的一致性、有效性、完备性和全面性等特性,并列举了一个具体的约束网络实例。建立了协同产品开发中的动态约束模型,将约束分为耦合约束和独立约束两种类型,通过设定耦合约束的变量的取值范围,将耦合约束转换为独立约束,并综合利用约束传播算法和区间求解算法对该约束模型进行求解。最后给出了协同产品开发中约束模型的网络实现流程并开发了相应的原型系统,为冲突的检测方法提供了量化手段,可以提前发现潜在的冲突。     

USING META-PROGRAMMING,CONSTRAINT LOGIC PROGRAMMING AND APPROXIMATE REASONING FOR EXPERT SYSTEMS DESIGN

Abstract

This paper presents an enhancement of the CARESS system—A Constraint Approximative Reasoning System Support—introduced in (Popescu and Roventa, 1994). CARESS is an experimental system with primarily two objectives:

(1)knowledge representation and manipulation techniques and to implement them in PROLOG III, and

(2) to develop a knowledge programming environment for building expert systems. We discuss here the use of meta-programming, constraint logic programming and approximate reasoning for the design of expert systems

It has already been proven that meta-programming and logic programming are powerful techniques for expert system design. Fuzzy logic can be used to model one kind of uncertainty. Constraint logic programming is useful for dealing with the constraints given by operations using fuzzy sets.     

Architecting centralized coordination of soccer robots based on principle solution

Coordination strategy is a relevant topic in multi-robot systems, and robot soccer offers a suitable domain to conduct research in multi-robot coordination. Team strategy collects and uses environmental information to derive optimal team reactions, through cooperation among individual soccer robots. This paper presents a diagrammatic approach to architecting the coordination strategy of robot soccer teams by means of a principle solution. The proposed model focuses on robot soccer leagues that possess a central decision-making system, involving the dynamic selection of the roles and behaviors of the robot soccer players. The work sets out from the conceptual design phase, facilitating cross-domain development efforts, where different layers must be interconnected and coordinated to perform multiple tasks. The principle solution allows for intuitive design and the modeling of team strategies in a highly complex robot soccer environment with changing game conditions. Furthermore, such an approach enables systematic realization of collaborative behaviors among the teammates.     

Mixed Global Constraints and Inference in Hybrid CLP–IP Solvers

The complementing strengths of Constraint (Logic) Programming (CLP) and Mixed Integer Programming (IP) have recently received significant attention. Although various optimization and constraint programming packages at a first glance seem to support mixed models, the modeling and solution techniques encapsulated are still rudimentary. Apart from exchanging bounds for variables and objective, little is known of what constitutes a good hybrid model and how a hybrid solver can utilize the complementary strengths of inference and relaxations. This paper adds to the field by identifying constraints as the essential link between CLP and IP and introduces an algorithm for bidirectional inference through these constraints. Together with new search strategies for hybrid solvers and cut-generating mixed global constraints, solution speed is improved over both traditional IP codes and newer mixed solvers.     

Spontaneous behavior for cooperation through interaction: An emotionally intelligent robot system

This paper deals withspontaneous behavior for cooperation through interaction in a distributed autonomous robot system. Though a human gives the robots evaluation functions for the relation of cooperation among robots, each robot decides its behavior depending on its environment, its experience, and the behavior of other robots. The robot acquires a model of the behavior of the other robots through learning. Inspired by biological systems, the robot's behaviors are interpreted as emotional by an observer of the system. In psychology, the emotions have been considered to play important roles for generation of motivation and behavior selection. In this paper, the robot's behaviors are interpreted as follows: each robot feels frustration when its behavior decision does not fit its environment. Then, it changes its behavior to change its situation actively and spontaneously. The results show potential of intelligent behavior by emotions. This work was presented, in part, at the International Symposium on Artificial Life and Robotics, Oita, Japan, February 18–20, 1996