SHF: Small: An Integrated Parallel Constraint Programming Platform for Combinatorial Search Problems

SHF：Small：用于组合搜索问题的集成并行约束编程平台

• 批准号: 1018006
• 负责人: Neng-Fa Zhou
• 金额: $ 27.71万
• 依托单位: CUNY Brooklyn College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-08-01 至 2015-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1018006&HistoricalAwards=false
• 关键词: SHF; Small; Integrated; Parallel; Constraint

Many real-world problems, ranging from scheduling in industrial production lines, planning for intelligent robots, protein structure predication, resource allocation, to various network optimization problems are combinatorial search problems. Constraint Programming (CP) and Answer Set Programming (ASP) are emerging techniques for solving these problems. CP over Finite Domains (FD) has had great successes in many application areas, such as scheduling, where use of global constraints is very effective. ASP has been found amenable to knowledge-intensive search problems such as planning and configuration problems. Recently, there has been great interest in parallelizing CP and ASP solvers to take advantage of the power provided by multi-core processors. This research aims to develop an integrated parallel constraint programming platform for combinatorial search problems. It entails three tasks. Firstly, this research will enhance the power of CLP(FD) (Constraint Logic Programming over FD) by enabling constraints over Composite Finite Domains (CFD). The resulting language, CLP(CFD), allows for natural and efficient modeling of problems with multi-attributed objects. Action Rules (AR), a successful language developed by the PI, will be enhanced and used to implement CLP(CFD). Secondly, this research will develop a compiler to translate ASP programs into AR. For an ASP program, the generated program maintains a partial answer set as a pair of disjoint tuple sets and uses labeling and propagation to compute answer sets. Unlike most ASP solvers, the AR-based solver requires no prior grounding of programs. Thirdly, this research will parallelize AR. Since AR is used as a common intermediate language for both CLP(CFD) and ASP, a parallel implementation of AR will directly result in parallel solvers for CLP(CFD) and ASP. This research will advance the implementation techniques for constraint languages and the resulting system will benefit a wide range of real-world applications.

从工业生产线调度、智能机器人规划、蛋白质结构预测、资源分配到各种网络优化问题，许多现实问题都是组合搜索问题。约束编程（CP）和答案集编程（ASP）是解决这些问题的新兴技术。有限域上的CP（FD）在许多应用领域取得了巨大的成功，例如调度，其中使用全局约束是非常有效的。ASP已被发现适合知识密集型搜索问题，如规划和配置问题。最近，人们对并行CP和ASP求解器产生了极大的兴趣，以利用多核处理器提供的功能。本研究旨在发展一个整合式平行约束规划平台，以解决组合搜寻问题。它涉及三项任务。首先，本研究将通过在复合有限域（CFD）上启用约束来增强CLP（FD）（FD上的约束逻辑编程）的能力。由此产生的语言，CLP（CFD），允许自然和有效的建模问题的多属性对象。行动规则（AR）是PI开发的一种成功语言，将得到加强并用于实施CLP（CFD）。其次，本研究将开发一个编译器来将ASP程序翻译成AR。对于ASP程序，生成的程序将部分答案集维护为一对不相交的元组集，并使用标记和传播来计算答案集。与大多数ASP求解器不同，基于AR的求解器不需要事先对程序进行基础。第三，本研究将AR并行化。由于AR被用作CLP（CFD）和ASP的通用中间语言，因此AR的并行实现将直接导致CLP（CFD）和ASP的并行求解器。该研究将促进约束语言的实现技术，所产生的系统将有利于广泛的现实世界的应用。