基于规划的空间布局

本文基于正规集首先建立了一个空间布局问题的形式化定义,然后分析了这一问题的计算复杂度,并证明了基于网格上空间布局问题的可计算性.重点介绍了基于分布式规划的住宅平面布局问题的求解模型,同时给出了一个实例,最后分析了规划方法和分布式规划的一些优点.     

空间布局的约束图方法

空间布局的自动化是智能CAD领域的研究方向之一,旨在为设计师提供智能辅助工具，用于求解在建筑、厂房设备、大规模集成电路以及产品包装等等若干领域出现的布局问题.图论方法是空间布局研究的主要途径之一.以往的布局模型由于难以充分表达知识与约束,使得设计过程与结果难以控制.本文提出一种可应用于2D及3D布局的规范约束图及层次约束图模型,给出了约束图解的存在条件.该模型可以表示精细的布局知识与约束,在一定程度上克服了以往图模型不能充分表达布局知识与约束的不足.本文还给出了基于约束图的布局生成算法.     

基于空间布局约束的拓扑关联规则挖掘

在空间拓扑关联挖掘中,为提取包含指定空间布局关系的拓扑关联规则,提出一种基于空间布局约束的拓扑关联规则挖掘算法,该算法能够在多空间关系模式下,挖掘包含空间布局约束的拓扑关联规则,将空间关系事务转换成整数,通过空间布局约束重构非目标空间对象类的权值向量,用重构权位值递减构建候选频繁项,并用布尔运算计算其支持数。实验结果表明,与传统挖掘算法相比,该算法的挖掘速度更快、更有效。     

A CSP technique-based interactive control panel layout

An interactive and iterative control panel layout method based on the constraint satisfaction problem (CSP) technique was developed to generate an ergonomically sound panel design. This control panel layout method attempts to incorporate a variety of relevant ergonomic principles and design constraints, and generate an optimal or, at least, a ‘satisfactory’ solution through an efficient search algorithm. The problem of seeking an ergonomically sound panel design should be viewed as a multi-criteria problem, and most of the design objectives should be understood as constraints. Hence, a CSP technique was employed in this study for dealing with the multi-constraints layout problem. The efficient search algorithm using ‘preprocess’ and ‘look_ahead’ procedures was developed to handle the vast amount of computational effort. In order to apply the CSP technique to the panel layout procedure, the ergonomic principles such as spatial compatibility, frequency-of-use, importance, functional grouping, and sequence-of-use were formalized as CSP terms. The effectiveness of the proposed panel layout method was evaluated by example problems, and the results clearly showed that the generated layouts properly considered various ergonomic design principles.     

基于树搜索的一种动态空间调度方法

针对大型离散企业产品组装空间调度问题,本文提出了一种基于树搜索的动态调度方法。该方法同时考虑了空间布置和时间调度两方面因素,在整个调度规划周期内,算法分成两部分：一是调度准备阶段,把调度时间分割成连续的时间段,并通过时间约束条件得到在每个分场地内需要组装的模块候选集,同时得到分场地的初始布局状态;二是局部调度阶段,通过深度优先树搜索的方法,在每个时间片内使用局部调度算法进行空间布置搜索,得出最优调度。该方法简单实用,最后,仿真实验说明了所提方法的有效性。     

Smashing peacocks further: drawing quasi-trees from biconnected components

We extend the popular force-directed approach to network (or graph) layout to allow separation constraints, which enforce a minimum horizontal or vertical separation between selected pairs of nodes. This simple class of linear constraints is expressive enough to satisfy a wide variety of application-specific layout requirements, including: layout of directed graphs to better show flow; layout with non-overlapping node labels; and layout of graphs with grouped nodes (called clusters). In the stress majorization force-directed layout process, separation constraints can be treated as a quadratic programming problem. We give an incremental algorithm based on gradient projection for efficiently solving this problem. The algorithm is considerably faster than using generic constraint optimization techniques and is comparable in speed to unconstrained stress majorization. We demonstrate the utility of our technique with sample data from a number of practical applications including gene-activation networks, terrorist networks and visualization of high-dimensional data     

Incremental planning using conceptual graphs

Abstract

When performing a planning or design task in many domains it is often difficult to specify in advance what the precise goals are. It is therefore useful to have a system in which the planning process is performed interactively, with the solution approaching the users' intent incrementally through iterations of the planning process. A planning system intended to function in this way must be able to take goal specifications interactively rather than all at once at the beginning of the planning process. The planning process then becomes one of satisfying new goals as they are given by the user, modifying as little as possible the results of previous planning work. Incremental planning is an approach to interactive planning problems that allows a system to create a plan incrementally, modifying a previous plan to satisfy new or more precise goal specifications. In this paper we present an incremental planning system called the general constraint system (GCS) that is based on the conceptual programming environment (CP) developed at New Mexico State University and we show an example of the use of the system for a simple civil engineering design problem     

方位关系约束满足问题的推理求解

约束满足问题（Constraint Satisfaction Problems CSP）是人工智能的一个研究领域,诸如空间查找、规划等问题都可转化为约束满足问题。方位关系是空间关系的重要组成部分,用以确定空间对象间的一种顺序。本文研究了空间方位关系模型,给出了方位关系约束的一般表示形式。在此基础上,利用组合表推理给出了方位关系约束满足问题的一个推理求解算法,该算法的时间复杂度为O（n^2）。     

机器人辅助腹腔介入治疗的空间运动约束及控制策略

描述了机器人辅助腹腔介入治疗中的手术规划模型和虚拟夹具（VF）方法,研究了引导型和障碍型两 类虚拟夹具的空间运动约束生成方法以及基于导纳控制的综合控制策略．通过建立引力势场和参考方向实现了对控 制对象的引导,通过建立斥力势场实现了空间避障（如腹腔内血管及肋骨）,从而为手术器械的运动及定位提供了 有效的辅助作用．VF 的刚度系数可以调节空间运动约束的苛刻程度．单个VF 和腹腔3 维空间中多个VF 的仿真实 验验证了空间运动约束和控制算法的有效性．本文的方法适用于类似的遥操作和人机协作系统．     

Modelling Musical Structures

Modelling musical structures is a research field prominent among mathematicians and computer scientists as well as musicologists, psychomusicologists and musicians. Constraint programming has been proved to be a highly appropriate technique in this field. For the task of automated music composition, in particular, constraints have been shown to describe composition principles in a declarative, natural, and, above all, efficient way since music composition knowledge is in fact a collection of conditions rather than a sort of cookery-book.Unfortunately, many approaches stress the technical aspects of applying constraints and do not think about the concrete role of constraints, i.e. about what music really should be. In general, the composer as an artist is more concerned about what he wants to say through his music than with theoretically (or socially or psychologically) established rules. This means that automated music composition needs practical goals in order to make sense. The role of those goals as well as musical constraints and constraint technologies that help to realize the goals are to be shown in this article. As a modelling example the system COPPELIA is introduced. It generates music on the basis of the structures, goals, and contents of given multimedia presentations. In this relatively young field of constraint application that does not supply such ideal, well-defined and closed sets of conditions as technical applications do, we find it very important to also present general thoughts about the sense of our application, about the development of composition constraints and the conditions under which these constraints work effectively.     

Musical constraint satisfaction problems solved with adaptive search

Constraint Programming (CP) allows to model and solve combinatory problems by specifying some partial information on variables, unknowns of the problem. We have studied musical constraint problems, either stated by contemporary composers, or of musical analysis, or instrumentation, in collaboration with IRCAM (french Institute for Research and Coordination Acoustics / Music). Fourteen such problems have been modeled and solved, which allowed to give a detailed typology. This has been used to conceive and implement OMClouds, a library in the Computer Assisted Composition environment OpenMusic. It is based on a local search algorithm called adaptive search. Its architecture allows in particular to define a constraint problem visually, to solve it, and eventually to edit partial or approached results during the resolution process.     

Intelligent multimedia layout: A reference architecture for the constraint-based spatial layout of multimedia presentations

With increases in the complexity and dynamics of multimedia information communicated by current applications, there arises a corresponding need towards a standard technology for intelligent multimedia interfaces. In this article, we address those components of an intelligent multimedia presentation system (IMMPS) which deal with the design and the realization of spatial layout. We treat multimedia layout as a multidimensional constraint problem and propose a reference architecture for a general-purpose intelligent multimedia layout manager (IMMLM) that is based on a dedicated constraint solver kernel.     

An observation concerning constraint-based compaction

This paper presents a refinement of the most commonly used technique for VLSI layout compaction. The usual approach to the compaction problem involves solving a constraint system that encodes the design rules of the layout. When arbitrary design rules are allowed, the fastest known algorithm for solving the constraint system requires Θ(nm) time in the worst case, where n is the number of layout components and m is the number of constraints. Here we show that if the input layout is legal, the constraint system can be solved in Θ(m+n log n) time. The key idea is to write the constraints in terms of displacements of layout features, rather than absolute coordinates.     

Logic of design actions

The way in which knowledge about design can be incorporated into knowledge-based design systems is discussed and demonstrated within the framework of an overall logical/linguistic model of the design process. The technique of hierarchical planning is discussed. within this framework. The domain under consideration is that of spatial layout in buildings.     

求解布局模型的并行矩阵算法研究

布局设计通常要建立抽象状态空间模型。求解布局模型，实现从模型状态到坐标图的转化，是计算机辅助布局设计的重要研究内容之一。本文在简要介绍一种层次布局模型ＨＬＭ１的基础上，引入了模型的解的概念；研究了ＨＬＭ１的子模型－层次约束图解的存在条件；提出了求解层次约束图，实现从模型到坐标图转化以及检测约束矛盾的一种并行矩阵算法，并给出了一个计算实例。     

Layout design in dynamic environments: analytical issues

The paper discusses the layout problem for a productive environment affected by variability of demand (dynamic environment). A conceptual framework of the layout flexibility is discussed, according to the concept of layout robustness. An analytical approach extends the technique adopted for the optimal layout determination from the static to the dynamic context. For an assigned layout problem, an example shows how the analytical approach may be applied to the calculation of the probability distribution of the cost function. From this basis, a measure of the layout robustness is proposed and commented on, in order to give useful advice to those in charge of layout planning and control and to highlight the potential use of the theoretical issues discussed.     

Constraint Solving for Proof Planning

Proof planning is an application of AI planning to theorem proving that employs plan operators that encapsulate mathematical proof techniques. Many proofs require the instantiation of variables; that is, mathematical objects with certain properties have to be constructed. This is particularly difficult for automated theorem provers if the instantiations have to satisfy requirements specific for a mathematical theory, for example, for finite sets or for real numbers, because in this case unification is insufficient for finding a proper instantiation. Often, constraint solving can be employed for this task. We describe a framework for the integration of constraint solving into proof planning that combines proof planners and stand-alone constraint solvers. Proof planning has some peculiar requirements that are not met by any off-the-shelf constraint-solving system. Therefore, we extended an existing propagation-based constraint solver in a generic way. This approach generalizes previous work on tackling the problem. It provides a more principled way and employs existing AI technology.     

Interactive Case-Based Planning for Forest Fire Management

This paper describes an AI system for planning the first attack on a forest fire. This planning system is based on two major techniques, case-based reasoning, and constraint reasoning, and is part of a decision support system called CHARADE. CHARADE is aimed at supporting the user in the whole process of forest fire management. The novelty of the proposed approach is mainly due to the use of a local similarity metric for case-based reasoning and the integration with a constraint solver in charge of temporal reasoning.     

Robust design based on constraint networks

This paper describes a robust design method using constraint networks. As opposed to the traditional statistical robust methodology, the proposed method gives a valid model to analyze parameter uncertainties so as to predict conflicts in concurrent design. The mathematical model, which reflects the requirements of robust design, is given in the paper. A general consistency algorithm is designed using interval arithmetic to refine the intervals. This paper also proves that the consistency algorithm is arc consistent if the constraint network is integrated. The constraint network uses the consistency algorithm to verify the design process early in the process and to assist the designers in determining design variables to reduce the multidisciplinary iterations in concurrent design. The quantitative effect of downstream constraints can be analyzed before determining design parameters and potential conflicts can be predicted. A layout design example shows the validity of the method.     

Constraint network approach to the design and manufacture of labels in a high-variety label-printing environment

This paper presents a constraint network approach to the design and manufacture of high-variety labels. The existing approach to label printing in the industry is essentially a sequential approach. In this approach, layout sheet utilization is optimized based on label attributes only. Production then attempts to meet delivery date of the labels by first processing high-priority labels from the layout sheet, and others later. This results in huge work-in-process inventory and high production cost. In this paper, we propose a constraint network approach to the design and manufacture of labels on layout sheets. Mathematical models of the various manufacturing stages are considered in the design process. Thus the emerging optimal layout design minimizes the work-in-process inventory and production cost, and maximizes production efficiency. The algorithm is an application of artificial intelligence techniques in a system domain. An example application of the algorithm results in an efficient production schedule and greater product delivery performance.