Applying Constraint Programming to Incorporate Engineering Methodologies into the Design Process of Complex Systems

AAAI 2012

TL;DR

This paper presents a novel approach to automatically enforce complex engineering methodologies during the design of intricate systems. By modeling design artifacts and their relationships as a graph and using constraint programming, the system can detect violations and contradictions in real-time, even with incomplete design data. This promises to improve design quality and reduce errors by providing immediate feedback to engineers.

What Problem Does This Paper Address?

Designing complex systems, like those found in automotive or aerospace industries, involves numerous engineers from different disciplines using various tools. Ensuring these diverse components and their interdependencies adhere to established engineering methodologies (which provide guidelines for design quality and traceability) is a significant challenge. Current methods for checking compliance are often manual, error-prone, or only capable of verifying simple, local rules. This leaves a gap in effectively managing and enforcing global, complex methodology guidelines across the entire design lifecycle, especially when design data is distributed across multiple tools and not yet complete.

Methods

The core of the proposed solution lies in two key innovations:

  1. Graph Representation: The system's design data, including artifacts (requirements, functions, tests) and their relationships, is represented as a double-layered graph. The lower layer captures artifact-to-artifact relations, while the upper layer represents the system's hierarchical decomposition into subsystems. This structured representation allows for a unified view of distributed design information.
  2. Constraint Programming (CP): Engineering methodology rules are translated into constraints that operate on this graph structure. A constraint programming solver is then used to check if the current design data (represented by the graph) satisfies all these rules. CP is particularly well-suited because it can handle complex, global relationships and can identify contradictions even when the design is only partially complete. The paper also introduces specific CP variables and constraint types to model these rules effectively, including connectivity, cardinality, and cyclic rules.

Datasets

The paper evaluates its approach using a tutorial example of a modern vehicle and a real-world systems engineering tutorial project called Search And Rescue Air Vehicle (SARAH) designed by Israel Aerospace Industries Ltd. The SARAH project involved design artifacts of 7 types residing in up to 31 subsystems, with a context tree depth of 4. The methodology rules enforced were 76 in total.

Key Insights and Ideas

  • Real-time Methodology Enforcement: The ability to check methodology compliance during the design process, rather than as a post-hoc validation, is a significant shift. This allows for immediate correction of errors.
  • Handling Incomplete Data: A crucial insight is that the CP approach can detect violations and contradictions even when the design is not fully complete. This is highly practical, as designs evolve iteratively.
  • Unified Rule Checking: Constraint programming allows for the simultaneous checking of complex, global methodology rules, which is a significant improvement over traditional methods that check rules individually.
  • Declarative Rule Definition: Using CP provides a declarative language for defining methodology rules, making them easier to express, understand, and modify compared to writing custom scripts.
  • Performance Trade-offs: The paper highlights that analyzing contradictions (Algorithm 3) is computationally more expensive than simply producing information about implied or forbidden links (Algorithm 2).

Key Results

The CP application was successfully used to check the methodology conformance of the SARAH project. The performance results, summarized in Figure 4, show that the runtime for contradiction analysis (rectangles) is generally higher than for information production (circles). For instances requiring contradiction analysis, runtimes ranged from approximately 0.1 seconds to over 1000 seconds, depending on the number of design artifacts. For information production, runtimes were significantly lower, often in the sub-second range. The authors estimate that for companies using similar methodologies, this application could save engineers significant workload per subsystem and, more importantly, increase the number of detected errors during the design phase.

Limitations and Future Work

The authors acknowledge several limitations:

  • Scalability for Contradictions: The performance for analyzing contradictions can be a bottleneck for large, non-compliant design nets. Future work could focus on improving algorithms for extracting unsatisfiable cores, such as using smarter ordering of variables and constraints or implementing timeouts for partial results.
  • Explanation Granularity: The algorithm for explaining contradictions might not always provide the most concise explanation, sometimes pointing to multiple constraints rather than a single missing artifact.
  • Assumption of Artifact Existence: The CP formulation assumes the existence of all relevant design artifacts, which can lead to less precise explanations if artifacts are missing.

Future work could also explore incorporating preferences or optimization functions (soft constraints) into the CP model to guide engineers towards better design choices, rather than just identifying violations. The authors also suggest that the LDRM framework, combined with this CP approach, could be extended to support more comprehensive impact analysis and traceability.

Summary updated

BibTeX
@inproceedings{2012applying,
  title = {{Applying Constraint Programming to Incorporate Engineering Methodologies into the Design Process of Complex Systems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2012},
}
Figure