权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Constraint Satisfaction for Configuration: Logical Fundamentals,Algorithms, and Complexity

配置的约束满足：逻辑基础、算法和复杂性

基本信息

批准号：
EP/G055114/1
负责人：
Georg Gottlob
金额：
$ 61.65万
依托单位：
University of Oxford
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2009
资助国家：
英国
起止时间：
2009 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FG055114%2F1
关键词：
Constraint Satisfaction Configuration Logical Fundamentals

项目摘要

The project deals with configuration problems. Flexibility and efficiency in the customization of products and services --rather than series production-- has become a key factor of competitiveness in the post-industrial economy. Configuration development is an excellent application area for artificial intelligence methods and for constraint satisfaction, in particular.Developing a product configuration system is a challenging task in many ways. Product configuration tools should be designed to encode the complex knowledge from domain experts, such as the characteristics of the different components involved in thecustomization and the restriction on how these components can be combined with each other. However, this might be very difficult in general, because customization is a generative process, where both the number of the involved components and the types of components themselves may be unknown at the beginning.The second challenge in building automatic configurators concerns the efficiency of the algorithms supporting the customization. In fact, product configuration in real scenarios is likely to involve several components and hundreds of associated variables, whosevalues have to be dynamically determined based on the customer's needs. For instance, telephone switching systems often consisting of several hundreds of racks, thousands of frames, and dozens of thousands modules. Given the huge size of the problems to betreated, a major requirement is to integrate efficient algorithms to both building the configuration that best matches with the customer's desires and checking whether a given configuration satisfies the technological requirements from the industry.In order to achieve significant progress, we will first study existing approaches and compare them formally and request feedback from the industrial advisory board. We propose to investigate a formalism suited to the cope with the above mentioned challenges, called the extensible constraint satisfaction problem (ECSP). Wewill study the expressive power and the complexity of decision and computational problems related to this formalism. We also propose to investigate the complexity issues in the presence of value-generating constraints, which is a well-known type ofconstraints used in database theory, but has not been investigated in the context of CSPs so far. Once the framework for extensible CSPs has been layed out, our plan is to investigate decomposition techniques, to find tractable subclasses of ECSPs. Finally, we will implement and test a configurator system, based on our framework,and using our decomposition algorithms. The project is organised into four main work packages. WP1 systematically studies the relevant problems to configuration, both by formally comparing existing approaches in the literature and by receiving feedback from the industrial advisory board. WP2 focuseson the extensible constraint satisfaction problems (ECSPs). Particular focus will be given to complexity analysis of the relevant decision and computational problems. WP3 consists of a comprehensive study of decomposition methods suitable to ECSPs toidentify tractable subclasses. In WP4, we will implement and test a proof-of-concept prototype of configuration system, based on ECSP and on the decomposition methods developed in WP3.The scientific project staff will consist of one post-doc, and one doctoral student. The student is expected to intensively co-operate with the post-doc.We plan to publish the results in top artificial intelligence journals and at leading international conferences.

该项目处理配置问题。产品和服务定制的灵活性和效率——而不是批量生产——已成为后工业经济中竞争力的关键因素。配置开发是人工智能方法和约束满足的一个极好的应用领域。开发产品配置系统在许多方面都是一项具有挑战性的任务。产品配置工具应该被设计为对来自领域专家的复杂知识进行编码，例如定制中涉及的不同组件的特征以及这些组件如何相互组合的限制。然而，这通常是非常困难的，因为定制是一个生成过程，其中所涉及的组件的数量和组件本身的类型在开始时可能都是未知的。构建自动配置器的第二个挑战涉及支持自定义的算法的效率。事实上，实际场景中的产品配置可能涉及几个组件和数百个相关变量，这些变量的值必须根据客户的需求动态确定。例如，电话交换系统通常由数百个机架、数千个帧和数十个模块组成。考虑到要处理的问题规模巨大，一个主要的需求是集成有效的算法来构建最符合客户需求的配置，并检查给定的配置是否满足行业的技术要求。为了取得重大进展，我们将首先研究现有的方法，并对它们进行正式比较，并要求工业咨询委员会提供反馈。我们建议研究一种适合于应对上述挑战的形式，称为可扩展约束满足问题（ECSP）。我们将研究与这种形式主义相关的决策和计算问题的表达能力和复杂性。我们还建议研究存在价值生成约束的复杂性问题，这是数据库理论中使用的一种众所周知的约束类型，但到目前为止还没有在csp的背景下进行研究。一旦可扩展csp的框架被制定出来，我们的计划是研究分解技术，找到可处理的ecsp子类。最后，我们将实现和测试一个配置器系统，基于我们的框架，并使用我们的分解算法。该项目分为四个主要工作包。WP1系统地研究了配置的相关问题，既通过比较文献中现有的方法，也通过接收工业咨询委员会的反馈。WP2关注可扩展约束满足问题（ecsp）。特别的重点将给予相关决策和计算问题的复杂性分析。WP3包括对适合于ecsp的分解方法的全面研究，以识别可处理的子类。在WP4中，我们将基于ECSP和WP3中开发的分解方法，实现和测试配置系统的概念验证原型。科研项目人员由博士后1人、博士生1人组成。该学生应与博士后密切合作。我们计划在顶级人工智能期刊和领先的国际会议上发表研究结果。