Efficient interactive configuration of unbounded modular systems

ABSTRACT

Interactive configuration guides a user searching through a large combinatorial space of solutions to a system of constraints. We investigate a class of very expressive underlying constraint satisfaction problems: modular recursive constraint systems of unbounded size. A precomputation step is used to obtain a configuration algorithm for such systems that supports the user efficiently with bounded response time. This precomputation step determines all solutions for each module, which are computed and stored in compact data structures such as Binary Decision Diagrams (BDDs), in order to eliminate run-time search. The precomputation step also detects ill-behaved module collections that have no finite solutions. The runtime interaction algorithm scales well as its response time only depends on the amount of the information passed locally between the modules, and not on the size of the entire configured structure. Our algorithm was implemented and tested on an industrial example, and gives good response times. We believe this is the first known sound and complete algorithm for solving unbounded interactive configuration problems, with bounded response time per interaction.

REFERENCES

• 1: E. R. van der Meer and H. R. Andersen. BDD-based recursive and conditional modular interactive product configuration. In Proceedings of the International Workshop on CSP techniques with Immediate Application, pages 112--126, Toronto, Canada, September 2004.
• 2: Erik R. van der Meer. Modular Configuration. PhD thesis, ITU University of Copenhagen, 2005. Submitted.
• 3: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 4: H. Fargier and M.-C. Vilarem. Compiling CSPs into tree-driven automata for interactive solving. In Proceedings of the 3rd International Workshop on User-Interaction in Constraint Satisfaction, pages 44--55, 2003.
• 5: T. Hadzic, S. Subbarayan, R. M. Jensen, H. R. Andersen, J. Møller, and H. Hulgaard. Fast backtrack-free product configuration using a precompiled solution space representation. In Proceedings of the International Conference on Economic, Technical and Organisational Aspects of Product Configuration Systems, pages 131--138, Copenhagen, Denmark, June 2004.
• 6: J. Nejsum Madsen. Methods for interactive constraint satisfaction. Master's thesis, University of Copenhagen, 2003.
• 7: D. Magro. Interactive configuration capability in a sale support system: lazyness and focusing mechanisms. In Proceedings of the Configuration Workshop held at IJCAI-2001, pages 57--63, Seattle, Washington, August 2001.
• 8: D. Sabin and E. C. Freuder. Configuration as composite constraint satisfaction. In Proceedings of the 1st Artificial Intelligence and Manufacturing Research Planning Workshop, pages 153--161, 1996.
• 9: S. Subbarayan and H. R. Andersen. Linear functions for interactive configuration using join matching and CSP tree decomposition. In Proceedings of the Configuration Workshop held at IJCAI-2005, pages 7--12, Edinburgh, Scotland, July 2005.
• 10: S. Subbarayan, R. M. Jensen, T. Hadzic, H. R. Andersen, H. Hulgaard, and J. Møller. Comparing two implemenations of a complete and backtrack-free interactive configurator. In Proceedings of the International Workshop on CSP techniques with Immediate Application, pages 97--111, Toronto, Canada, September 2004.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems

General Terms:
Algorithms, Languages, Performance

Keywords:
constraint satisfaction, interactive configuration