Distributed AEC databases for collaborative design

The Architecture, Engineering and Construction (AEC) design process for a facility involves participation of many design specialists. These participants are architects, engineers (structural, mechanical and electrical) and contractors, who may be independent design professionals or design teams within an organization. From the viewpoint of information processing, two characteristic features distinguish the AEC design process from many other design domains. Firstly, there is a massive volume of design data involved in the design of each of its component specialties. Secondly, the specialization of the disciplines themselves warrant substantial autonomy. For design automation, this autonomy should be realized without sacrificing the collaborative nature of the multidisciplinary AEC design process. We propose autonomous AEC databases to deal with the first issue, and a global constraint maintenance mechanism for the second. Autonomous design databases can support the existing local applications in architectural, structural and mechanical engineering, and construction domains. However, a set of inter-disciplinary constraints needs to be enforced to ensure spatial and functional consistency of the design. A global constraint checking mechanism frees designers from the burden of keeping track of various design changes that may result in cross-functional conflicts. In this paper, we discuss the relevant issues for constraint management on distributed AEC databases. Although specific AEC examples will be used, the presentation is general enough to be applicable to other design domains, such as VLSI and manufacturing.     

Incremental integrity checking of UML/OCL conceptual schemas

Integrity constraints play a key role in the specification and development of software systems since they state conditions that must always be satisfied by the system at runtime. Therefore, software systems must include some kind of integrity checking component that ensures that all constraints still hold after the execution of any operation that modifies the system state. Integrity checking must be as efficient as possible not to seriously slow down the system performance at runtime. In this sense, this paper proposes a set of techniques to facilitate the efficient integrity checking of UML-based software specifications, usually complemented with a set of integrity constraints defined in Object Constraint Language (OCL) to express all rules that cannot be graphically defined. In particular, our techniques are able to determine, at design-time, when and how each constraint must be checked at runtime to avoid irrelevant verifications. We refer to these techniques as incremental because they minimize the subset of the system state that needs to be checked after each change by assuming that the system was initially in a consistent state and just reevaluating the elements that may have been affected by that change. We also show how the techniques can be integrated in a model-driven development framework to automatically generate a final implementation that automatically checks all constraints in an incremental way.     

Constraint-based test generation for automotive operating systems

This work suggests a method for systematically constructing a software-level environment model for safety checking automotive operating systems by introducing a constraint specification language, OSEK_CSL. OSEK_CSL is designed to specify the usage constraints of automotive operating systems using a pre-defined set of constraint types identified from the international standard OSEK/VDX. Each constraint specified in OSEK_CSL is interpreted as either a regular language or a context-free language that can be checked by a finite automaton or a pushdown automaton. The set of usage constraints is used to systematically classify the universal usage model of OSEK-/VDX-based operating systems and to generate test sequences with varying degrees of constraint satisfaction using LTL model checking. With pre-defined constraint patterns and the full support of automation, test engineers can choose the degree of constraint satisfaction and generate test cases using combinatorial intersections of selected constraints that cover all corner cases classified by constraints. A series of experiments on an open-source automotive operating system show that our approach finds safety issues more effectively than conventional specification-based testing, scenario-based testing, and conformance testing.     

Model checking dynamic pushdown networks

A dynamic pushdown network (DPN) is a set of pushdown systems (PDSs) where each process can dynamically create new instances of PDSs. DPNs are a natural model of multi-threaded programs with (possibly recursive) procedure calls and thread creation. Thus, it is important to have model checking algorithms for DPNs. We consider in this work model checking DPNs against single-indexed LTL and CTL properties of the form \({\bigwedge f_i}\) such that f _i is a LTL/CTL formula over the PDS i. We consider the model checking problems w.r.t. simple valuations (i.e., whether a configuration satisfies an atomic proposition depends only on its control location) and w.r.t. regular valuations (i.e., the set of the configurations satisfying an atomic proposition is a regular set of configurations). We show that these model checking problems are decidable. We propose automata-based approaches for computing the set of configurations of a DPN that satisfy the corresponding single-indexed LTL/CTL formula.     

Completion of Rewrite Systems with Membership Constraints Part II: Constraint Solving

We consider a constraint system involving equations and membership constraints. Membership constraints are interpreted as the membership to some recognizable tree languages. The terms may contain a restricted kind ofcontext variables. We give a set of constraint solving rules which is proved to be complete and terminating. This gives a unification algorithm for an order-sorted logic (without any restriction on the signature) which contains some restricted kind of second-order variables.     

Practical minimization of pairwise-covering test configurations using constraint programming

Context: Testing highly-configurable software systems is challenging due to a large number of test configurations that have to be carefully selected in order to reduce the testing effort as much as possible, while maintaining high software quality. Finding the smallest set of valid test configurations that ensure sufficient coverage of the system’s feature interactions is thus the objective of validation engineers, especially when the execution of test configurations is costly or time-consuming. However, this problem is NP-hard in general and approximation algorithms have often been used to address it in practice.Objective: In this paper, we explore an alternative exact approach based on constraint programming that will allow engineers to increase the effectiveness of configuration testing while keeping the number of configurations as low as possible.Method: Our approach consists in using a (time-aware) minimization algorithm based on constraint programming. Given the amount of time, our solution generates a minimized set of valid test configurations that ensure coverage of all pairs of feature values (a.k.a. pairwise coverage). The approach has been implemented in a tool called PACOGEN.Results: PACOGEN was evaluated on 224 feature models in comparison with the two existing tools that are based on a greedy algorithm. For 79% of 224 feature models, PACOGEN generated up to 60% fewer test configurations than the competitor tools. We further evaluated PACOGEN in the case study of an industrial video conferencing product line with a feature model of 169 features, and found 60% fewer configurations compared with the manual approach followed by test engineers. The set of test configurations generated by PACOGEN decreased the time required by test engineers in manual test configuration by 85%, increasing the feature-pairs coverage at the same time.Conclusion: Our experimental evaluation concluded that optimal time-aware minimization of pairwise-covering test configurations is efficiently addressed using constraint programming techniques.     

Propagation algorithms for lexicographic ordering constraints

Finite-domain constraint programming has been used with great success to tackle a wide variety of combinatorial problems in industry and academia. To apply finite-domain constraint programming to a problem, it is modelled by a set of constraints on a set of decision variables. A common modelling pattern is the use of matrices of decision variables. The rows and/or columns of these matrices are often symmetric, leading to redundancy in a systematic search for solutions. An effective method of breaking this symmetry is to constrain the assignments of the affected rows and columns to be ordered lexicographically. This paper develops an incremental propagation algorithm, GACLexLeq, that establishes generalised arc consistency on this constraint in O(n) operations, where n is the length of the vectors. Furthermore, this paper shows that decomposing GACLexLeq into primitive constraints available in current finite-domain constraint toolkits reduces the strength or increases the cost of constraint propagation. Also presented are extensions and modifications to the algorithm to handle strict lexicographic ordering, detection of entailment, and vectors of unequal length. Experimental results on a number of domains demonstrate the value of GACLexLeq.     

Incremental semantic analysis for OCL compilers

In software engineering, modeling with unified modeling language and object constraint language became industry standards and are supported by many computer-aided software engineering tools. The increasing number of the modeled functionalities results in complex models that need more and more textual constraints to express the hidden restrictions applied to the systems. During the metamodel development, rebuilding all the constraints is unnecessary when only a few changes have been applied due to the iterative, incremental manner of modifications. In this paper, we present a family of algorithms that handles the changes in constraints incrementally on the expression level; thus, the required rebuilds are kept to a minimum. Incremental variable reference resolving and type checking are performed as a part of the incremental semantic analysis. Balancing between the incremental and standard compilation is also considered, heuristics are given to select the faster method of compilation at each iteration. With the achieved results the duration of metamodel development can be decreased; thus, the efficiency of the environment is improved.     

Constraint graph-based frequent pattern updating from temporal databases

There have been many kinds of association rule mining (ARM) algorithms, e.g., Apriori and FP-tree, to discover meaningful frequent patterns from a large dataset. Particularly, it is more difficult for such ARM algorithms to be applied for temporal databases which are continuously changing over time. Such algorithms are generally based on repeating time-consuming tasks, e.g., scanning databases. To deal with this problem, in this paper, we propose a constraint graph-based method for maintaining frequent patterns (FP) discovered from the temporal databases. Particularly, the constraint graph, which is represented as a set of constraint between two items, can be established by temporal persistency of the patterns. It means that some patterns can be used to build the constraint graph, when the patterns have been shown in a set of the FP. Two types of constraints can be generated by users and adaptation. Based on our scheme, we find that a large number of dataset has been efficiently reduced during mining process and the gathering information while updating.     

Building renovation adopts mass customization

This work is motivated by an industrial need of manufacturing façades insulating envelopes in order to reduce energy consumption in residential buildings. An insulating envelope is a configuration of a set of rectangular panels that respects a set of limitations. Due to the number of façades to be renovated and the number of possible configurations for a single façade, the envelope configuration is both a mass customization problem as well as a combinatorial one. The paper then introduces a decision support system based on the framework of constraint satisfaction, as it fits neatly the constrained nature of the problem. Two configuration tasks have been identified as prerequisite to envelopes configurations: (1) the configuration of a questionnaire for information inputs and (2) the configuration of a constraint satisfaction problem for each one of the façades to be renovated. The system architecture promotes maintenance, modularity and efficiency as different configuration tasks are divided into web-services. Conception and implementation of the massive building thermal renovation are then supported.     

Using SCL to specify and check design intent in source code

Software developers often fail to respect the intentions of designers due to missing or ignored documentation of design intent. SCL (Structural Constraint Language) addresses this problem by enabling designers to formalize and confirm compliance with design intent. The designer expresses his intent as constraints on the program model using the SCL language. The SCL conformance checking tool examines developer code to confirm that the code honors these constraints. This paper presents the design of the SCL language and its checker, a set of practical examples of applying SCL, and our experience with using it both in an industrial setting and on open-source software.     

面向约束的鲁棒设计方法

提出了一种面向约束的鲁棒设计方法,该方法能够利用约束网络对并行设计中的一类不确定性参数进行有效的描述和处理。该文提出了反映协同设计需求的数学模型,设计了一个通用的一致性求解算法框架,并利用基于区间代数的一致性算法,在设计的初期就监控设计过程,使设计者在确定参数前能够通过约束网络定量地考虑下游的约束条件,并能够提早发现冲突以避免设计后期出现大的返工。文中的研究是实现并行设计中“一次成功”的技术基础。     

A program for generating configuration state lists in many-electron atoms

This program written in FORTRAN is aimed at generating configuration state list of the set of complex atomic configurations. The program generates a list of configuration states obtained by taking into account many additional constraints of different types for minimizing the orders of matrices, as proposed in [Bogdanovich et al., Comput. Phys. Comm. 143 (2002) 174]. The generated list file complies with the requirements of codes [Hibbert et al., Comput. Phys. Comm. 64 (1991) 455; Fischer et al., Comput. Phys. Comm. 64 (1991) 486] and other related programs.

Program summary

Title of program: ATOTERMCatalogue identifier: ADTMProgram summary URL:http://cpc.cs.qub.ac.uk/summaries/ADTMProgram obtainable from: CPC Program Library, Queen's University of Belfast, N. IrelandLicensing provisions: NoneComputers: Any computer with a FORTRAN 77 compilerOperating systems under which the program has been tested: LinuxProgramming language used: FORTRAN 77Memory required to execute with typical data: 2 MBNo. of lines in distributed program, including text data, etc.: 2368No. of bytes in distributed program, including test data, etc.: 15 446Distribution format: tar gzip fileKeywords: Complex atom, configuration interaction, configuration state, LS-couplingNature of physical problem: Generating the list of configuration states with taking into account multiple additional constraints of different types.Method of solution: Building the configuration state list for the set of the given configurations with further selection of necessary configuration states by applying a set of restrictions on each configuration.Restrictions onto the complexity of the problem: For atomic configurations containing any electron shells with l?3; momenta of the electron shells with l>3 and N?2 is restricted by L_max=6. The number of the active shells can not exceed seven.Unusual features of the program: Possibility to select configuration states.Typical running time: Seconds to minutes. Depends on the size of the problem: of the order of a few seconds for simple configurations to minutes for a large set of very complex admixed configurations with f-electron shells.     

A logic-based mechanism for integrity maintenance of engineering databases

The semantics of engineering data can be represented in terms of constraints and can be maintained via constraint checking and enforcement. Conventional databases (e.g. Relational Databases) are inadequate for maintaining engineering data semantics because they have no effective means for representing and checking/enforcing constrains. As an extension of relational databases, deductive databases overcome this inadequacy by enabling constraint representation and checking. However, they too lack the constraint enforcement ability. a logic-based mechanism for enforcing constrainst in deductive databases is presented in this paper. The mechanism is composed of two operators: a truth enforcement operator and a falsity enforcement operator. The mechanics of these operators and their use for integrity enfocement are described herein.     

An interval-based SAT modulo ODE solver for model checking nonlinear hybrid systems

This paper presents a bounded model checking tool called Hydlogic{\texttt{Hydlogic}} for hybrid systems. It translates a reachability problem of a nonlinear hybrid system into a predicate logic formula involving arithmetic constraints and checks the satisfiability of the formula based on a satisfiability modulo theories method. We tightly integrate (i) an incremental SAT solver to enumerate the possible sets of constraints and (ii) an interval-based solver for hybrid constraint systems (HCSs) to solve the constraints described in the formulas. The HCS solver verifies the occurrence of a discrete change by using a set of boxes to enclose continuous states that may cause the discrete change. We utilize the existence property of a unique solution in the boxes computed by the HCS solver as (i) a proof of the reachability of a model and (ii) a guide in the over-approximation refinement procedure. Our Hydlogic{\texttt{Hydlogic}} implementation successfully handled several examples including those with nonlinear constraints.     

Review of: “Management by Motivation”By Saul W. Gellerman. (American Management Association,’1968.) [Pp. 286.] $0.

This paper examines the effects of different types of complexity facing novice designers in constraint satisfaction tasks. The nature of the complexity in a design task was varied by manipulating different aspects of the extrinsic constraints, which refer to restrictions concerning how design components can be assembled. We investigated the effect of the number of constraints (Study 1) and the number of different types of constraint (Study 2) in a simulated office design task. Results indicated that tackling a design task with a greater number of constraints, or more types of constraint, resulted in decrements in performance. Study 3 examined the effect of reasoning about constraints that involved a fixed location in the office layout and those that did not. It was found that having a higher proportion of constraints that referenced a fixed location led to better design performance. The theoretical and practical aspects of these results are discussed.

Practitioner summary: This paper identifies sources of constraint complexity facing the novice designer in an office design task. Three features of constraints proved problematic: the number of constraints, the number of types of constraint and whether the constraint involved a specific location. Training and decision support solutions are discussed.     

Model-based verification of quantitative non-functional properties for software product lines

Evaluating quality attributes of a design model in the early stages of development can significantly reduce the cost and risks of developing a low quality product. To make this possible, software designers should be able to predict quality attributes by reasoning on a model of the system under development. Although there exists a variety of quality-driven analysis techniques for software systems, only a few work address software product lines. This paper describes how probabilistic model checking techniques and tools can be used to verify non-functional properties of different configurations of a software product line. We propose a model-based approach that enables software engineers to assess their design solutions for software product lines in the early stages of development. Furthermore, we discuss how the analysis time can be surprisingly reduced by applying parametric model checking instead of classic model checking. The results show that the parametric approach is able to substantially alleviate the verification time and effort required to analyze non-functional properties of software product lines.     

Specification and automated validation of staged reconfiguration processes for dynamic software product lines

Dynamic software product lines (DSPLs) propose elaborated design and implementation principles for engineering highly configurable runtime-adaptive systems in a sustainable and feature-oriented way. For this, DSPLs add to classical software product lines (SPL) the notions of (1) staged (pre-)configurations with dedicated binding times for each individual feature, and (2) continuous runtime reconfigurations of dynamic features throughout the entire product life cycle. Especially in the context of safety- and mission-critical systems, the design of reliable DSPLs requires capabilities for accurately specifying and validating arbitrary complex constraints among configuration parameters and/or respective reconfiguration options. Compared to classical SPL domain analysis which is usually based on Boolean constraint solving, DSPL validation, therefore, further requires capabilities for checking temporal properties of reconfiguration processes. In this article, we present a comprehensive approach for modeling and automatically verifying essential validity properties of staged reconfiguration processes with complex binding time constraints during DSPL domain engineering. The novel modeling concepts introduced are motivated by (re-)configuration constraints apparent in a real-world industrial case study from the automation engineering domain, which are not properly expressible and analyzable using state-of-the-art SPL domain modeling approaches. We present a prototypical tool implementation based on the model checker SPIN and present evaluation results obtained from our industrial case study, demonstrating the applicability of the approach.     

MELOADES: Methodology for long-term online adaptation of embedded software for heterogeneous devices

In this work MELOADES [mel-uh-dees] is presented: a methodology for long-term online adaptation of embedded software that addresses the challenge of redeploying software and executing it within resource constraints. Instead of using fixed analytical models of resource consumption developed offline or tuning model parameters, MELOADES automatically reconfigures hardware online without any analytical model. MELOADES leverages long-term deployment by first selecting a set of hardware configurations that can potentially execute software tasks while satisfying a range of resource constraints and then storing these in a memoization table. The table is initialized using a Design of Experiments (DoE) survey to generate these speculative configurations. During deployment, for each new task assigned to the software, either a memoized configuration is found or a limited search for a new configuration that satisfies the task constraints is performed. Search results are added to the memoization table to reduce the time and energy required for future searches and eventually MELOADES converges to a simple table look-up. The effectiveness of this technique was demonstrated with an image capture and wireless transmission representative long-term application deployed on a Nokia N80 smartphone. Using a genetic search algorithm for energy efficiency/constrained image tasks, MELOADES satisfied 94% of all task constraints, evaluated only 1.6% of the configuration space, and used 98.5% less energy than an exhaustive search.