用CLP技术解决动画自动生成中的布局规划问题*

以本实验室研制的一个多重论域的约束逻辑程序设计系统BPUCLP为基础,提出用约束逻辑程序(Constraint Logic Programming,CLP)解决布局规划问题。该方法用几何模型表示对象,用算术约束描述对象间的位置关系,并通过BPUCLP的约束求解机制为各个位置变量取值。该方法实现了二维人物初始布局规划和三维卧室家具布局规划。实验证明该方法是有效的。     

Nicolog: A simple yet powerful cc(FD) language

In this paper, we describe Nicolog, a language with capabilities similar to recently developed constraint logic programming (CLP) languages such as CLP(BNR), clp(FD), and cc(FD). Central to Nicolog are projection constraints (PCs), a sublanguage for compiling and optimizing constraint propagation in numeric and Boolean domains. PCs are an interesting generalization of the indexical constraints introduced in cc(FD) and also found in clp(FD). Nicolog compiles a very general class of built-in constraints into equivalent sets of PCs, allowing an arbitrary mixture of integer (easily extensible to real) and Boolean operations. Nicolog also lets the user program PCs directly, making it possible to implement new sophisticated propagation procedures. We show that PCs are a simple, efficient, and flexible way to implement most of the propagation procedures possible in other FD CLP systems. These include procedures for cardinality, constructive disjunction, implication, and mixed Boolean/numeric constraints. Empirical results with a simple prototype Nicolog implementation based on the WAM architecture show it can solve hard problems with speed comparable to the fastest existing CLP systems.     

MIQP‐based Layout Design for Building Interiors

We propose a hierarchical framework for the generation of building interiors. Our solution is based on a mixed integer quadratic programming (MIQP) formulation. We parametrize a layout by polygons that are further decomposed into small rectangles. We identify important high‐level constraints, such as room size, room position, room adjacency, and the outline of the building, and formulate them in a way that is compatible with MIQP and the problem parametrization. We also propose a hierarchical framework to improve the scalability of the approach. We demonstrate that our algorithm can be used for residential building layouts and can be scaled up to large layouts such as office buildings, shopping malls, and supermarkets. We show that our method is faster by multiple orders of magnitude than previous methods.     

Temporal Reasoning for a Collaborative Planning Agent in a Dynamic Environment

We present a temporal reasoning mechanism for an individual agent situated in a dynamic environment such as the web and collaborating with other agents while interleaving planning and acting. Building a collaborative agent that can flexibly achieve its goals in changing environments requires a blending of real-time computing and AI technologies. Therefore, our mechanism consists of an Artificial Intelligence (AI) planning subsystem and a Real-Time (RT) scheduling subsystem. The AI planning subsystem is based on a model for collaborative planning. The AI planning subsystem generates a partial order plan dynamically. During the planning it sends the RT scheduling subsystem basic actions and time constraints. The RT scheduling subsystem receives the dynamic basic actions set with associated temporal constraints and inserts these actions into the agent's schedule of activities in such a way that the resulting schedule is feasible and satisfies the temporal constraints. Our mechanism allows the agent to construct its individual schedule independently. The mechanism handles various types of temporal constraints arising from individual activities and its collaborators. In contrast to other works on scheduling in planning systems which are either not appropriate for uncertain and dynamic environments or cannot be expanded for use in multi-agent systems, our mechanism enables the individual agent to determine the time of its activities in uncertain situations and to easily integrate its activities with the activities of other agents. We have proved that under certain conditions temporal reasoning mechanism of the AI planning subsystem is sound and complete. We show the results of several experiments on the system. The results demonstrate that interleave planning and acting in our environment is crucial.     

Reasoning on constraints in CLP(FD)

Constraint Logic Programming solvers on finite domains (CLP(FD) solvers) use constraints to prune those combinations of assignments which cannot appear in any consistent solution. There are applications, such as temporal reasoning or scheduling, requiring some form of qualitative reasoning where constraints can be changed (restricted) during the computation or even chosen when disjunction occurs. We embed in a (CLP(FD) solver the concept of constraints as first class objects. In the extended language, variables range over finite domains of objects (e.g., integers) and relation variables range over finite domains of relation symbols. We define operations and constraints on the two sorts of variables and one constraint linking the two. We first present the extension as a general framework, then we propose two specializations on finite domains of integers and of sets. Programming examples are given, showing the advantages of the extension proposed from both a knowledge representation and an operational viewpoint.     

Improving assembly precedence constraint generation by utilizing motion planning and part interaction clusters

In this paper, we present a technique that combines motion planning and part interaction clusters to improve generation of assembly precedence constraints. In particular, this technique automatically finds, and clusters, parts that can mutually affect each other’s accessibility, and hence may impose assembly constraints. This enables the generation of accurate precedence constraints without needing to examine all possible assembly sequences. Given an assembly model, our technique generates potential disassembly layers: spatial clustering is used to generate part sets. Next, motion planning based on rapidly-exploring random trees (RRT) with multiple trees is used to evaluate the interaction between these part sets. Specifically, motion planning is used to determine which part sets can be removed from the assembly. These sets are added to the first disassembly layer and removed from the assembly. Part sets that can be removed from the simplified assembly are then added to the second layer. If the process gets stuck, parts in the parent set are regrouped, and the process continues until all disassembly layers are found. The resulting structure reveals precedence relationships among part sets, which can be used to generate feasible assembly sequences for each part set and the whole assembly. We present theoretical results related to the algorithms developed in the paper. Computational results from tests on a variety of assemblies are presented to illustrate our approach.     

HIERARCHICAL ARC CONSISTENCY FOR DISJOINT REAL INTERVALS IN CONSTRAINT LOGIC PROGRAMMING

There have been many proposals for adding sound implementations of numeric processing to Prolog. This paper describes an approach to numeric constraint processing which has been implemented in Echidna, a new constraint logic programming (CLP) language. Echidna uses consistency algorithms which can actively process a wider variety of numeric constraints than most other CLP systems, including constraints containing some common nonlinear functions. A unique feature of Echidna is that it implements domains for real-valued variables with hierarchical data structures and exploits this structure using a hierarchical arc consistency algorithm specialized for numeric constraints. This gives Echidna two advantages over other systems. First, the union of disjoint intervals can be represented directly. Other approaches require trying each disjoint interval in turn during backtrack search. Second, the hierarchical structure facilitates varying the precision of constraint processing. Consequently, it is possible to implement more effective constraint processing control algorithms which avoid unnecessary detailed domain analysis. These advantages distinguish Echidna from other CLP systems for numeric constraint processing.     

A simple and efficient boolean solver for Constraint Logic Programming

We study in this paper the use of consistency techniques and local propagation methods, originally developed for constraints over finite domains, for solving boolean constraints in Constraint Logic Programming (CLP). To this aim, we first present a boolean CLP language clp(B/FD) built upon a CLP language over finite domains clp(FD) which uses a propagation-based constraint solver. It is based on a single primitive constraint which allows the boolean solver to be encoded at a low level. The boolean solver obtained in this way is both very simple and very efficient: on average it is eight times faster than the CHIP propagation-based boolean solver, i.e. nearly an order of magnitude faster, and infinitely better than the CHIP boolean unification solver. It also performs on average several times faster than special-purpose stand-alone boolean solvers. We then present in a second time several simplifications of the above approach, leading to the design of a very simple and compact dedicated boolean solver. This solver can be implemented in a WAM-based logical engine with a minimal extension limited to four new abstract instructions. This clp(B) system provides a further factor two speedup w.r.t. clp(B/FD).     

CAL: A theoretical background of constraint logic programming and its applications

Constraint logic programming (CLP) is an extension of logic programming by introducing the facility of writing and solving constraints in a certain domain. CAL (Contrainte avec Logique) is a CLP language in which (possibly non-linear) polynomial equations can be written as constraints, while almost all the other CLP languages proposed so far have concentrated only on linear equations and inequations. This paper describes a general semantics of CLP including CAL, and shows the validity of CAL in this framework.     

基于Multi-Agent系统的多飞行器协同路径规划方法的研究

无人多飞行器(UAV)协同技术是当前分布式人工智能的一个热点领域,其中一个关键技术在于如何实现多UAV集群根据复杂环境中目标、威胁、地形变化以及各UAV之间的性能约束动态进行实时性航路规划。提出一种基于Multi-agent系统的多UAV对实时动态多目标进行路径规划的方法。其核心是基于Multi-agent系统的decen-tralized控制方案。在Multi-agent平台上,实现了agent对于环境、目标、任务等路劲规划约束条件的建模,同时提出了多agent动态路径规划方法的实现方案。方案使用DisCSP模型框架,将基于真实复杂战场环境的实时路径规划问题所涉及的多复杂限制条件,抽象成Multi-agent系统中的各个约束条件,通过多agent间Dynamic Programming过程求解多UAV实时动态多目标的路径规划和协同任务分配的ABT算法,并实现在动态威胁和地形以及动态目标下具备集群协同能力的多UAV实时仿真系统。     

An integrated model for solving cell formation and cell layout problem simultaneously considering new situations

Cellular manufacturing system (CMS) is one of the group technology (GT) usages. Among the necessary decisions for a successful CMS implementation, cell formation problem (CFP) and cell layout problem (CLP) are two most popular ones. The majority of past studies in CMS discussed on CFPs and some of those focused on CLP ones. A few researchers solve the CPF and CLP simultaneously. In this paper, we present a new integrated mathematical model considering cell formation and cell layout simultaneously. The goal of our model is to group similar parts and corresponding different machines in same cells. Machines sequence in each cell and cell positions is also specified in the system. Moreover, our proposed model considers forward and backtracking movements as well as new assumptions for distances between cells using sequence data and production volume. One appropriate adjusted measure from the literature and two new measures of performance for evaluating solutions are defined. To validate the model, two well-known critical benchmark examples are employed. Computational experiments demonstrate that our proposal is a proficient model and show the effectiveness of our implementation.     

A distributed constraint-based scheduler

This paper presents the design and implementation of a distributed advisory system which helps different human experts in the management and control of traffic within railway stations and along railway branches. Our approach allows the management of a whole railway line in a modular, expandable and scalable way. The scheduling of trains along a railway line is performed by several modules each one controlling a certain number of resources. These modules solve the scheduling of trains by interacting and communicating with each other. Each module has to deal with temporal constraints, priority between trains and constraints due to the structure of the station and railway branches. Our approach is based on the constraint logic programming (CLP) paradigm for solving the constraints involved in the problem. Therefore, this paper shows the versatility and adequacy of the CLP approach for the problems of this type.     

Interactive microcomputer graphic methods for smoothing craft layouts

Computer-aided layout planning has been under development since the early 1960s, and many layout programs are based on the powerful and well known program, CRAFT (Computerized Relative Allocation of Facilities Technique by Armour and Buffa 1963).

Unfortunately, the major drawback of these facilities layout programs is that they often create unrealistic and impractical designs since the resulting block layouts can have odd shapes. Most architectural building designs require that the rooms and departments be in the form of squares, rectangles or L-shapes. The traditional approach to rectifying this problem is to manually modify the block plans at the corresponding expense of time and effort.

This paper identifies the problems and proposes interactive graphic methods for smoothing CRAFT layouts. In addition, a new method for the assessment of layout efficiency is introduced to measure the quality of a layout before and after smoothing.     

Online Replanning of Time-Efficient Flight Paths for Unmanned Rotorcraft

Onboard and online flight path planning for small-scale unmanned rotorcraft requires efficient algorithms in order to meet real-time constraints. In a priori unknown environment, rapid replanning is necessary in order to maintain a safe clearance when new obstacles are detected. The complexity of the planning problem varies vastly with the required flight path qualities and the complexity of the environment. In most scenarios flight paths should be smooth and time-efficient and always feasible to fly. Therefore, the rotorcraft’s flight dynamics must be accounted for. Decoupled planning approaches have been proven to solve this problem very efficiently by dividing the problem into sequentially solvable subproblems. However, this computational efficiency comes at the cost of having to compromise on the flight path quality. In this work, we present a decoupled planning approach that has been integrated with our midiARTIS helicopter in order to perform onboard path planning when flying through a priori unknown environment. The approach involves roadmap-based global path planning and local path refinement with cubic splines. It allows to plan safe, dynamically feasible and time-efficient flight paths with limited onboard processing power. We present simulation results from a set of benchmark scenarios in complex urban terrain as well as results from flight testing of a closed-loop obstacle avoidance maneuver with virtual obstacle mapping. Our results demonstrate that close-to-optimal flight paths can be planned with a decoupled planning approach, if heuristics and simplifications for each planning step are carefully chosen.     

Mathematical formulation and a new metaheuristic for the constrained double-floor corridor allocation problem

A layout plan for a manufacturing system that is designed without any facility constraints will most likely be infeasible when confronted with reality. Additionally, considering that land available for building industrial plants is limited and its cost is high, it is necessary to investigate the layout planning of two and multi-floor facilities. To address these shortages in the scientific literature, we focus on the double-floor corridor allocation problem (DFCAP) which covers a wide range of complex facility constraints, such as fixed floor constraints, fixed row constraints, fixed positioning constraints, mutual floor constraints, mutual row constraints, sequencing constraints and adjacency constraints. For the model mentioned above, we term it as a constrained DFCAP (cDFCAP). A mixed-integer linear programming model is formulated for the cDFCAP. In order to solve larger realistic problems, a constrained metaheuristic with the memetic algorithm framework customised for solving the cDFCAP is introduced in this work. In our algorithm, four problem-specific heuristic rules to construct a set of initial solutions are developed. In addition, an ideal parameter combination for our constrained memetic algorithm is determined through a Taguchi experimental design. Finally, the results of a set of cDFCAP instances with different sizes (n = 10∼80) report that our provided approach is effective for the considered problem.     

Meta-Level interpretation of constraint languages a case study: Logical primitives

This paper provides a detailed presentation of a Prolog-written meta-level interpreter for a constraint logic programming (CLP) language for expressing equalities and disequalities of finite trees, as well as non-negative integers (arities). The logical interpretation of the Prolog primitive functor (whose arguments are trees and arity) is used to illustrate the interactions among constraints pertaining to multiple domains. The paper’s objective is to provide insights about CLP language design and to present a modularized, incrementally-expandable meta-processor for this class of languages.     

Extending constraint logic programming for temporal reasoning

In recent years, several constraint‐based temporal reasoning frameworks have been proposed. They consider temporal points or intervals as domain elements linked by temporal constraints. Temporal reasoning in these systems is based on constraint propagation. In this paper, we argue that a language based on constraint propagation can be a suitable tool for expressing and reasoning about temporal problems. We concentrate on Constraint Logic Programming (CLP) which is a powerful programming paradigm combining the advantages of Logic Programming and the efficiency of constraint solving. However, CLP presents some limitations in dealing with temporal reasoning. First, it uses an “arc consistency” propagation algorithm which is embedded in the inference engine, cannot be changed by the user, and is too weak in many temporal frameworks. Second, CLP is not able to deal with qualitative temporal constraints. We present a general meta CLP architecture which maintains the advantages of CLP, but overcomes these two main limitations. Each architectural level is a finite domain constraint solver(CLP(FD)) that reasons about constraints of the underlying level. Based on this conceptual architecture, we extend the CLP(FD)language and we specialize the extension proposed on Vilain and Kautz’sPoint Algebra, on Allen’s Interval Algebra and on the STP framework by Dechter, Meiri and Pearl. In particular, we show that we can cope effectively with disjunctive constraints even in an interval‐based framework. This revised version was published online in June 2006 with corrections to the Cover Date.     

SetCoLa: High‐Level Constraints for Graph Layout

Constraints enable flexible graph layout by combining the ease of automatic layout with customizations for a particular domain. However, constraint‐based layout often requires many individual constraints defined over specific nodes and node pairs. In addition to the effort of writing and maintaining a large number of similar constraints, such constraints are specific to the particular graph and thus cannot generalize to other graphs in the same domain. To facilitate the specification of customized and generalizable constraint layouts, we contribute SetCoLa: a domain‐specific language for specifying high‐level constraints relative to properties of the backing data. Users identify node sets based on data or graph properties and apply high‐level constraints within each set. Applying constraints to node sets rather than individual nodes reduces specification effort and facilitates reapplication of customized layouts across distinct graphs. We demonstrate the conciseness, generalizability, and expressiveness of SetCoLa on a series of real‐world examples from ecological networks, biological systems, and social networks.     

Intelligent backtracking in CLP(ℜ)

CLP() is a constraint logic programming language in which constraints can be expressed in the domain of real numbers. Computation in this specialized domain gives access to information useful in intelligent backtracking. In this paper, we present an efficient constraint satisfaction algorithm for linear constraints in the real number domain and show that our algorithm directly generates minimal sets of conflicting constraints when failures occur. We demonstrate how information gleaned during constraint satisfaction can be integrated with unification failure analysis. The resulting intelligent backtracking method works in the context of a two-sorted domain, where variables can be bound to either structured terms or real number expressions. We discuss the implementation of backtracking and show examples where the benefit of pruning the search tree outweights the overhead of failure analysis.     

AutoBrief: a multimedia presentation system for assisting data analysis

We present an approach to generating multimedia presentations that integrates hierarchical planning to achieve communicative goals, and task-based graphic design. A planning process decomposes domain-specific goals to domain-independent goals, which in turn are realized by media-specific techniques such as task-based graphic design. We apply our approach to developing AutoBrief, a system that summarizes large data sets using natural language and information graphics. Finally, we analyze AutoBrief in terms of the standard reference model (SRM).