平行结构类问题求解方法的研究

本文将分布式问题求解应用背景分为层次结构与平行结构两大类;给出了二维平行结构类问题的形式化描述,讨论了二维平行结构类问题的集中式与分布式求解方法以及计算复杂性。结果表明:基于知识的解法是可行的;分布式求解在提高问题求解速度与减少内存空间方面具有优越性。     

基于路径索引与编码模式的路径连接

在各种XML查询语言中普遍采用路径表达式来表示对象间的嵌套和引用关系，路径表达式的求解是查询处理中的一个关键问题．本文提出一种基于路径索引与编码模式的路径连接方法，利用路径索引能够以与路径长度成比例的时间求出对象的后代或祖先的目标集，利用编码模式则可以用常数时间确定对象之间的祖先一后代关系．实验结果表明，本文提出的方法具有较高的效率，当对大量对象进行连接以及当路径的长度、路径上结点的出度或入度较大时，本文提出的方法明显优干自顶向下或自底向上遍历的方法。     

方向相似性聚类方法DSCM

针对方向性数据提出了一种鲁棒的基于方向相似性度量的聚类方法DSCM．DSCM首先基于方向性度量构造目标函数，然后通过不动点迭代法对目标函数优化，获得各个样本的最终稳定状态，最后基于样本的最终状态集利用层次聚类技术实现聚类．DSCM的优势在于对方向性数据聚类时不依赖于具体的初始化参数，且能自组织地求解最优聚类划分因而有很好的鲁棒性．通过实验证实了DSCM的有效性以及对已有的两个传统方向性聚类算法的优越性．     

分布式求解平行结构类问题中重选区域的研究

本文以平行结构类问题的形式化描述为基础,详细讨论了分布式求解平行结构类问题系统中相邻结点间重迭区域的作用,定义了最小重迭区域的概念,并提出一种新的设立重迭区域方法——“可变法”,最后在分布式运输调度系统上进行了试验研究,结果表明:〈1〉设置重迭区域是必要的;〈2〉最小重迭区域的定义是有意义的;〈3〉与美国麻省大学采用的“固定法”相比,“可变法”保证了求解质量,减少了冗余的计算与通信开销。     

DATALOG程序的组及其应用

为了提高DATALOG程序自底向上计值的效率，本文提出了把DATALOG规则分成若干个组，对这些组可以给出一个拓扑序列，而对同一个组内的各个规则可以给出一个激发序列，以此来有效地控制DATALOG程序自底向上计值时对规则的调度，从而提高计算效率．这一技术可以应用于传统的各种自底向上计算方法，本文绘出了半朴质（Semi-Naove）算法和良基模型（Well-Founded）的交替不动点算法（AlternatingFixPoint）的改进．改进后的算法比原算法在时间和空间效率上都有较大的提高．     

基于演化算法实现多目标优化的岛屿迁徙模型

多目标演化算法(MOEA)利用种群策略，尽可能地找出多目标问题的Pareto最优集供决策者选择，为决策者提供了更大的选择余地，与其它传统的方法相比有了很大的改进．但提供大量选择的同时，存在着不能为决策者提供一定的指导性信息，不能反映决策者的偏好，可扩展性差等问题．本文提出了一个新的多目标演化算法(MOEA)计算模型…岛屿迁徙模型，该模型体现了一种全新的多目标演化优化的求解思想，对多目标优化问题的最优解集作了新的定义．数值试验结果表明，岛屿迁徙模型在求解MOP时有效地解决了以上问题，并且存在进一步改进的潜力．     

利用算符分析的问题求解

将状态空间的问题求解过程变换为逐步缩小与目标状态的差异过程是一种问题的分解方式．求解差异的顺序可通过分析算符对状态的影响而作出规划，规划的原则是最大限度地在不改变最近已实现子目标的条件下实现下一子目标．为此，在问题分解时各层子目标选择的依据是让各算符有最大的可利用率，即以状态对算符最小约束传播的原则选择各层子目标；最后生成一个子目标规划层次集．问题求解过程就表现为从初始状态开始实现层次集中的某一子目标序列，其间可能涉及子目标回溯．     

度量空间一种自底向上索引树构造算法

在多媒体或复杂对象数据库中，相似性搜索是一种非常重要的操作，这些操作一般可以归结为度量空间的相似性查询．提出一种新的度量空间索引数据结构（bu-tree），它是基于自底向上的分层聚类来构造索引结构，而传统的度量空间数据结构大部分是基于自顶向下构造的方法．相对于传统的构造方法，bu-tree可以在更小的索引半径内包含更多的对象，这样有利于查询的筛选．给出了bu-tree的构造算法以及相应的范围查询算法．实验表明，bu-tree的性能好于sa-tree，特别是在度量空间不是均匀分布或者查询具有较低的选择度情况下．     

广义与或树的启发式搜索算法BTAO

本文根据乐观决策准则提出了广义与或树这一新概念,证明了广义与或树的耗散值与其最佳解树的耗散值是等价的。根据新定义的启发式函数h~(Tr)(n,x),提出了广义与或树的自底向上的启发式算法BTAO~*。算法BTAO~*是可采纳的,即定能找到最佳解树,进而求解出广义与或树的耗散值。     

基于聚类的快速多目标遗传算法

多目标遗传算法非常适合于求解多目标优化问题．讨论了进化个体之间的支配关系及有关性质，论证了可以用快速排序的方法对进化群体中的个体进行分类，同时探讨了用聚类方法来保持群体的多样性，具体讨论了基于层次凝聚距离的聚类，在此基础上提出了用分类和聚类的方法构造新的进化群体．理论分析与实验结果表明，所讨论的方法比较国际上已有的方法具有更快的收敛速度．     

How to reach O.R. Wisdom

This paper identifies the Operations Research (O.R.) problems from a systems view of information, knowledge and understanding. This systems view is examined as a basis for a developmental approach to problem solving and decision making processes. O.R. wisdom lies in achieving a balance between short-and long-term goals through a process of participation and learning.     

Distributed Algorithms for Multi-Robot Observation of Multiple Moving Targets

An important issue that arises in the automation of many security, surveillance, and reconnaissance tasks is that of observing the movements of targets navigating in a bounded area of interest. A key research issue in these problems is that of sensor placement—determining where sensors should be located to maintain the targets in view. In complex applications involving limited-range sensors, the use of multiple sensors dynamically moving over time is required. In this paper, we investigate the use of a cooperative team of autonomous sensor-based robots for the observation of multiple moving targets. In other research, analytical techniques have been developed for solving this problem in complex geometrical environments. However, these previous approaches are very computationally expensive—at least exponential in the number of robots—and cannot be implemented on robots operating in real-time. Thus, this paper reports on our studies of a simpler problem involving uncluttered environments—those with either no obstacles or with randomly distributed simple convex obstacles. We focus primarily on developing the on-line distributed control strategies that allow the robot team to attempt to minimize the total time in which targets escape observation by some robot team member in the area of interest. This paper first formalizes the problem (which we term CMOMMT for Cooperative Multi-Robot Observation of Multiple Moving Targets) and discusses related work. We then present a distributed heuristic approach (which we call A-CMOMMT) for solving the CMOMMT problem that uses weighted local force vector control. We analyze the effectiveness of the resulting weighted force vector approach by comparing it to three other approaches. We present the results of our experiments in both simulation and on physical robots that demonstrate the superiority of the A-CMOMMT approach for situations in which the ratio of targets to robots is greater than 1/2. Finally, we conclude by proposing that the CMOMMT problem makes an excellent domain for studying multi-robot learning in inherently cooperative tasks. This approach is the first of its kind for solving the on-line cooperative observation problem and implementing it on a physical robot team.     

Synthesizing User Centered and Designer Centered IS Development Approaches Using General Systems Theory

This paper uses general systems theory to provide an expanded view of information systems in organizations. Three general viewpoints and corresponding approaches to information systems development are identified. The designer centered or American approach to information systems development is based on a functionalist perspective of information systems and a problem solving orientation. The user centered or European approach to information systems development takes an expanded view of information systems that specifically considers humans and recognizes their aspirations and goals and uses a democratic, participative approach to develop systems in an effort to produce an improved workplace and a better quality of worklife for users. A third viewpoint on information systems development, business process centering, is identified that further expands the components of the system to include the set of integrated tasks that provide value to the customer. We define a new development approach that combines the strengths of these approaches based on general systems theory, business process centering, and a measurement and control system.     

Reinforcement based mobile robot navigation in dynamic environment

In this paper, a new approach is developed for solving the problem of mobile robot path planning in an unknown dynamic environment based on Q-learning. Q-learning algorithms have been used widely for solving real world problems, especially in robotics since it has been proved to give reliable and efficient solutions due to its simple and well developed theory. However, most of the researchers who tried to use Q-learning for solving the mobile robot navigation problem dealt with static environments; they avoided using it for dynamic environments because it is a more complex problem that has infinite number of states. This great number of states makes the training for the intelligent agent very difficult. In this paper, the Q-learning algorithm was applied for solving the mobile robot navigation in dynamic environment problem by limiting the number of states based on a new definition for the states space. This has the effect of reducing the size of the Q-table and hence, increasing the speed of the navigation algorithm. The conducted experimental simulation scenarios indicate the strength of the new proposed approach for mobile robot navigation in dynamic environment. The results show that the new approach has a high Hit rate and that the robot succeeded to reach its target in a collision free path in most cases which is the most desirable feature in any navigation algorithm.     

Organizing Multiagent Systems

Despite all the research done in the last years on the development of methodologies for designing MAS, there is no methodology suitable for the specification and design of MAS in complex domains where both the agent view and the organizational view can be modeled. Current multiagent approaches either take a centralist, static approach to organizational design or take an emergent view in which agent interactions are not pre-determined, thus making it impossible to make any predictions on the behavior of the whole systems. Most of them also lack a model of the norms in the environment that should rule the (emergent) behavior of the agent society as a whole and/or the actions of individuals. In this paper, we propose a framework for modeling agent organizations, Organizational Model for Normative Institutions (OMNI), that allows the balance of global organizational requirements with the autonomy of individual agents. It specifies global goals of the system independently from those of the specific agents that populate the system. Both the norms that regulate interaction between agents, as well as the contextual meaning of those interactions are important aspects when specifying the organizational structure.     

Emergence of intelligence in next-generation manufacturing systems

In the paper we propose a fundamental shift from the present manufacturing concepts and problem solving approaches towards new manufacturing paradigms involving phenomena such as emergence, intelligence, non-determinism, complexity, self-organization, bottom-up organization, and coexistence with the ecosystem. In the first part of the paper we study the characteristics of the past and the present manufacturing concepts and the problems they caused. According to the analogy with the terms in cognitive psychology four types of problems occurring in complex manufacturing systems are identified. Then, appropriateness of various intelligent systems for solving of these four types of problems is analyzed. In the second part of the paper, we study two completely different problems. These two problems are (1) identification of system in metal forming industry and (2) autonomous robot system in manufacturing environment. A genetic-based approach that imitates integration of living cells into tissues, organs, and organisms is used. The paper clearly shows how the state of the stable global order (i.e., the intelligence) of the overall system gradually emerges as a result of low-level interactions between entities of which the system consists and the environment.     

一种自顶而下的Web-服务全局行为设计方法

“Web-服务”组合的分布式本质,使得设计者们在需求说明和逻辑确认方面都遇到了新的挑战。我们先分析自底而上方法的不足,提出了一种自顶而下的设计和验证方法。该方法是用“会话协议”来描述想得到的全局行为,然后在全局会话协议上验证预设的系统目标。最后按会话协议合成各实体。     

Solving time-dependent multimodal transport problems using a transfer graph model

In this paper we present an hybrid approach for solving the time-dependent multimodal transport problem. This approach has been tested on realistic instances of the problem providing an adequate balance between computation time and memory space. This solution can be applied to real transport networks in order to reduce the impact of traffic congestion on pollution, economy, and citizen’s welfare. A comparison with two previous approaches are given from theoretical point of view as well as experimental performance.     

Hierarchical representation of problem-solving knowledge in a frame-based process planning system

In most frame-based reasoning systems, the information being manipulated is represetned using frames, but the problem-solving knowledge that manipulates the frames is represented as production rules. One problem with this approach is that rules are not always a natrual way to represent knowledge; another is that systems containing lots of rules may suffer from problems with “exponetial blowup” in the amount of computation required. This paper describes a way to address these problems by organizing the problem-solving knowledge not as rules, but in a particular kind of frame hierarchy. the approach described in this paper has been implemented in a problem-solving system called SIPP (Semi-Intelligent Process Planner), which produces plans of action for the manufacture of metal parts. the paper gives an overview of SIPP, compares its knowledge representation and problem solving methods to approaches used in other knowledge-based systems, and describes goals for further research.     

Planning and meta-planning (MOLGEN: Part 2)

The selection of what to do next is often the hardest part of resource-limited problem solving. In planning problems, there are typically many goals to be achieved in some order. The goals interact with each other in ways which depend both on the order in which they are achieved and on the particular operators which are used to achieve them. A planning program needs to keep its options open because decisions about one part of a plan are likely to have consequences for another part.This paper describes an approach to planning which integrates and extends two strategies termed the least-commitment and the heuristic strategies. By integrating these, the approach makes sense of the need for guessing; it resorts to plausible reasoning to compensate for the limitations of its knowledge base. The decision-making knowledge is organized in a layered control structure which separates decisions about the planning problem from decisions about the planning process. The approach, termed meta-planning, exposes and organizes a variety of decisions, which are usually made implicitly and sub-optimally in planning programs with rigid control structures. This is part of a course of research which seeks to enhance the power of a problem solvers by enabling them to reason about their own reasoning processes.Meta-planning has been implemented and exercised in a knowledge-based program (named MOLGEN) that plans gene cloning experiments in molecular genetics.