Introduction

Model-based programming [9] is an approach to simplify and automate software development for embedded systems: it exploits constraint-based component models to automatically reason about possible component interactions, thus reducing the programming task to assembling engineering models of device components and writing high-level code in terms of current and desired device states.  The challenge in model-based programming is to develop efficient algorithms that can reason through a large space of component interactions to quickly identify most likely current states (monitoring and diagnosis) and generate least-cost desired states (planning and reconfiguration).  In this research effort, we adapt methods from constraint optimization and operations research in order to push the border on the complexity of models that can be handled, thus making model-based programming applicable to devices with very large state spaces, such as mixed hardware/software systems.  This is an exciting new research area that lies at the intersection of artificial intelligence, operations research, and software engineering.

Approach

Our approach is to frame reasoning about models - which lies at the base of  model-based monitoring, diagnosis, reconfiguration, and planning tasks - as a constraint optimization problem [10].  This formulation allows us to leverage advanced techniques for constraint solving and optimization, in particular methods that can exploit domain-specific structure of the problem to avoid state explosion.  Our research combines a range of different methods from different areas and investigates possible trade-offs between them in the context of model-based programming:

• using soft constraints, such as valued CSPs and semiring-CSPs [2], as a uniform representational framework for both constraints and uncertainty;
• decomposing constraint networks into trees [3, 4] as a basis for exploiting independence of subproblems through local consistency and dynamic programming (see Fig. 1);
• enumerating solutions in best-first order [10], allowing for anytime behavior and efficient focusing on leading solutions;
• encoding constraints symbolically [1] to exploit regularities and compactly represent very large state spaces;
• learning during search by extracting small conflict sets [10].

Figure 1: Constraint network of a circuit diagnosis example (left) and one of its possible tree decompositions (right).

Progress

Building upon our previous work in constraint-based optimization [10], we have framed different notions of model-based diagnosis as a constraint optimization problem using soft constraints [7].  Based on this theoretical work, we developed a prototype for a constraint optimization engine that integrates structural decomposition, symbolic encoding, and search [6]. It consists of an off-line compilation phase that compiles the constraint graph into a tree structure, and a fast on-line phase that computes solutions to the tree-structured problem using a distributed version of dynamic programming (see Fig. 1). Also, we recently developed an approach that allows to efficiently map richer classes of devices, such as mixed hardware/software systems, into the soft constraint formalism [5].

Future

In the future, we aim at leveraging the performance improvements of the underlying constraint processing to introduce more accurate planning and diagnosis algorithms for model-based programming, and tackle application domains that were previously infeasible. A step in this direction is our recently introduced n-step algorithm [5], which uses a sliding window of n time steps in order to construct optimal trajectories of state evolution.  We will demonstrate and validate our next-generation model-based programming system on testbeds from automotive applications.

Research Support

This research is funded in part by the project "Model-based Programming, Self-Diagnosis and Repair", Toyota research agreement 5/1/04.

References

[1] R.I. Bahar, E.A. Frohm, C.M. Gaona, G.D. Hachtel, E. Macii, A. Pardo, and F. Somenzi. Algebraic Decision Diagrams and Their Applications. In IEEE /ACM International Conference on CAD, pages 188–191, Santa Clara, California, 1993.

[2] Stefano Bistarelli, Ugo Montanari, and Francesca Rossi. Semiring-based constraint satisfaction and optimization. Journal of the ACM, 44(2):201–236, 1997.

[3] Georg Gottlob, Nicola Leone, and Francesco Scarcello. A comparison of structural CSP decomposition methods. Artificial Intelligence, 124(2):243–282, 2000.

[4] Kalev Kask, Rina Dechter, Javier Larrosa, and Fabio Cozman. Unifying tree-decomposition schemes for automated reasoning. Technical report, University of California, Irvine, 2001.

[5] Tsoline Mikaelian, Brian C. Williams, and Martin Sachenbacher: Diagnosing Complex Systems with Software-Extended Behavior using Constraint Optimization. Proceedings of the International Workshop on Principles of Diagnosis (DX-05), Pacific Grove, California, 2005.

[6] Martin Sachenbacher and Brian C. Williams. Bounded Search and Symbolic Inference for Constraint Optimization. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-05), Edinburgh, Scotland, 2005.

[7] Martin Sachenbacher and Brian C. Williams. Diagnosis as Semiring-based Constraint Optimization. Proceeedings of the 16th European Conference on Artificial Intelligence (ECAI'04), Valencia, Spain, 2004.

[8] Thomas Schiex, Helene Fargier, and Gerard Verfaillie. Valued Constraint Satisfaction Problems: hard and easy problems. Proceedings of the International Joint Conference in Artificial Intelligence (IJCAI-95), Montreal, Canada, August 1995.

[9] Brian C. Williams. and Michel D. Ingham. Model-Based Programming: Controlling Embedded Systems by Reasoning About Hidden State, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP-02) , Ithaca, New York, September 2002.

[10] Brian C. Williams, and Robert Ragno. Conflict-directed A* and its Role in Model-based Embedded Systems.  To appear in the Special Issue on Theory and Applications of Satisfiability Testing, Journal of Discrete Applied Mathematics, < January 2003.