Interactive Tree Decomposition Tool for Reducing System Analysis Complexity

Shahan Yang, Baobing Wang and John S. Baras

Submitted to 22nd Annual INCOSE International Symposium, 2012.

Abstract:

We present a graphical tool for the calculation of treewidth, a metric on the
parametric structure of a system that is intimately tied to the complexity of system analysis.
For many graphically describable systems, such as systems of parametric equations, as in a
SysML Parametric diagram, or Bayesian networks or even mind maps and writing term
papers, analysis of the system is exponential in treewidth and linear in system size. A tool
facilitating comprehensive analysis can serve to bring competitive advantage to a systems
engineering workflow by reducing costly unanticipated behaviors. Furthermore, a byproduct
of computing treewidth is a framework for enumerating computationally compatible
distributed algorithms.
Though there are classes for which treewidth computation is tractable (chordal graphs), it is
generally NP-complete. For this reason, we pose the problem from the perspective of finding
satisficing solutions, exposing choices that can influence the complexity of the resulting
system to the designer. A designer can contribute two important things to the structure of the
system: a visual intuition about the relationships between the underlying objects and the
ability to change the relationships themselves at design time to reduce analysis complexity.
Having a visual tool that provides instant feedback will help designers achieve an intuitive
grasp of the relationship between design decisions and system complexity. As complexity is
the root of almost every systems engineering problem, and also something not easily
understood, incorporating complexity analysis into a design process should improve resulting
system designs.

The tool uses a randomized, anytime algorithm for interactive optimization of treewidth. It
presents a sequence of choices to a designer and incrementally lowers an upper bound on
system treewidth over time. This algorithm is novel, as few algorithms are targeted at
interactivity with a human user.
We present a number of simple examples for using the tool. We show how our tool helps to
decompose some example systems, including a quadrotor optimization, a sensor network
optimization, a Bayesian network, and a mind map.