Smart Expansion Techniques for ASP-based Interactive Configuration

LUCIA BALÁŽOVÁ, RICHARD COMPLOI-TAUPE, SUSANA HAHN, NICOLAS RÜHLING, GOTTFRIED SCHENNER · 2025

Read Smart Expansion Techniques for ASP-based Interactive Configuration by LUCIA BALÁŽOVÁ, RICHARD COMPLOI-TAUPE, SUSANA HAHN, NICOLAS RÜHLING, GOTTFRIED SCHENNER (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-21027.txt.

Introduction

Lucia Balážová, Richard Comploi-Taupe, Susana Hahn, Nicolas Rühling, and Gottfried Schenner published this paper in 2025. It speeds up interactive product configuration, the software that lets a buyer build a custom product step by step. Their solver rests on answer set programming, a logic method that lists all valid options.

The slow part is finishing a half-built configuration on its own. The authors add four smart expansion tricks to the standard step-by-step search. Each trick reads off facts that must hold, or may hold, and adds the objects those facts demand. That trims the search space and cuts the number of costly dead-end checks. The paper also shows a user interface built on the solver's interface. The gains matter for large industrial catalogs, where shoppers expect instant answers.

Catalog record

CREATORLUCIA BALÁŽOVÁ, RICHARD COMPLOI-TAUPE, SUSANA HAHN, NICOLAS RÜHLING, GOTTFRIED SCHENNER
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-21027

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Smart Expansion Techniques for ASP-based Interactive Configuration Thanks: This research was partially supported by the Austrian Research Promotion Agency (FFG) under the “AI for Green” programme, and by the German Federal Ministry for Economic Affairs and Energy (BMWE) through the ZIM project grant KK5291307GR4. LUCIA BALÁŽOVÁ, RICHARD COMPLOI-TAUPE, SUSANA HAHN, NICOLAS RÜHLING, GOTTFRIED SCHENNER Abstract Product configuration is a successful application of Answer Set Programming (ASP). However, challenges are still open for interactive systems to effectively guide users through the configuration process. The aim of our work is to provide an ASP-based solver for interactive configuration that can deal with large-scale industrial configuration problems and that supports intuitive user interfaces via an API. In this paper, we focus on improving the performance of automatically completing a partial configuration. Our main contribution enhances the classical incremental approach for multi-shot solving by four different smart expansion functions. The core idea is to determine and add specific objects or associations to the partial configuration by exploiting cautious and brave consequences before checking for the existence of a complete configuration with the current objects in each iteration. This approach limits the number of costly unsatisfiability checks and reduces the search space, thereby improving solving performance. In addition, we present a user interface that uses our API and is implemented in ASP. Under consideration for acceptance in TPLP. keywords Answer Set Programming, Product Configuration, Interactivity 1 Introduction Configuration ( Felfernig et al. 2014 ) has been one of the first successful applications ( Gebser et al. 2011b ; Felfernig et al. 2017 ; Gençay et al. 2019 ) of Answer Set Programming (ASP; Lifschitz 2019 ; Gelfond and Kahl 2014 ). Nonetheless, there are open challenges for ASP-based configurators, one of them being interactive configuration. Industrial configuration problems in large infrastructure projects may contain thousands of components and hundreds of component types and are typically solved in a step-wise manner by combining interactive actions with automatic solving of sub-problems ( Falkner et al. 2020 ) . When using a grounding-based formalism like ASP, a grounding bottleneck ( Eiter et al. 2007 ) arises due to the large number of components. Furthermore, the necessary domain size is not known beforehand and can vary significantly. Therefore, we require a way to dynamically introduce new components during the configuration process. In our previous work we developed an API to satisfy basic requirements for interactive configuration ( Falkner et al. 2020 ) based on OOASP ( Falkner et al. 2015 ) and using various features of clingo 1 1 1 https://potassco.org/clingo/ ( Gebser et al. 2019 ) . In this paper, we report on our recent advancements in developing an ASP-based domain-independent interactive configuration platform. The new achievements, compared to previously published reports ( Comploi-Taupe et al. 2022 ; Comploi-Taupe et al. 2023 ) , consist of dramatically improved solving performance by using novel so-called smart expansion techniques and the creation of a UI prototype based on clinguin ( Beiser et al. 2024 ) . The general idea of the smart expansion techniques is to infer as much knowledge as possible from the current configuration state and to use this knowledge to reduce the search space of the ASP solver and to limit costly unsatisfiability checks. This results from the insight that in our earlier implementation objects were added incrementally to the configuration without any class restrictions or associations which in turn led to a combinatorial explosion of the search space. For this purpose, we introduced four new functions: ObjectNeeded , GlobalUpperBoundGap , GlobalLowerBoundGap , and AssociationPossible . While the first three ones use intersections of possible solutions to determine objects that are definitely needed in the configuration, the latter function provides possible associations between two objects with the intention of quickly estimating the minimal size of a complete configuration. We demonstrate the working of the functions using our racks example as known from earlier work. The remainder of the paper is organized as follows: Section 2 presents background on ASP, product configuration and the OOASP framework, as well as our running example and previous results regarding the interactive configurator. We then proceed to present our novel contributions. Section 3 contains detailed explanations about the four smart expansion functions and their implementation in our interactive configurator, and Section 4 introduces our novel clinguin user interface. Finally, Section 5 demonstrates the experimental results of our new implementation comparing its performance to the previous version and Section 6 concludes this paper. 2 Background 2.1 Answer Set Programming A logic program consists of rules of the form ⬇ a 1 ;...; a m :- a m+1 ,..., a n , not a n+1 ,..., not a o . where for 1\leq i\leq o , each a i is an atom of form p ( t 1 ,..., t k ) and all t j are terms (variables, constant terms, or function terms). For 0\leq m\leq n\leq o , atoms a 1 to a m are often called head atoms, while a m+1 to a n and not a n+1 to not a o are also referred to as positive and negative body literals, respectively. An expression is said to be ground if it contains no variables. As usual, not denotes (default) negation. A rule is called a fact if m=n=o=1 , normal if m=1 , and an integrity constraint if m=0 . In what follows, we deal with normal logic programs only, for which m is either 0 or 1. Semantically, a logic program induces a set of stable models, being distinguished models of the program determined by the stable models semantics ( Gelfond and Lifschitz 1990 ) . To ease the use of ASP in practice, several extensions have been developed. Multi-shot solving, which is one such extension, allows for solving continuously changing logic programs in an operative way. In clingo , this can be controlled via an API for implementing reactive procedures that loop on grounding and solving while reacting, for instance, to outside changes or previous solving results. We want to highlight here the use of so-called assumptions and externals ( Kaminski et al. 2023 ) . The former are added to the solving process and can be interpreted as integrity constraints that force the answer sets to contain certain atoms without providing evidence for them. The latter are specified by the # external directive and allow for declaring atoms whose truth value can be set via the API. This provides the tools to continuously assemble ground rules evolving at different stages of a reasoning process and to change program behavior by manipulating the truth values of atoms. 2.2 Product Configuration and OOASP Product configuration as an activity produces the specification of an artifact that is assembled from instances of given component types and that conforms to a given set of constraints between those components. Component types can have attributes, thus components can be parametrized. Furthermore, components are related via part-of, is-a, or other relationships ( Felfernig et al. 2014 ) . Many configuration problems are dynamic, meaning the number of necessary components for a solution is unknown in advance ( Falkner et al. 2016 ) . OOASP ( Falkner et al. 2015 ; Falkner et al. 2018 )

Read the complete text