精简有序二元决策图的泛化研究

Reduced ordered binary decision diagram (ROBDD) is the most influential knowledge compilation language so far. A well-known problem of ROBDD is its low space-efficiency, which reflects the exponential explosion in size when compiling many types of knowledge bases into ROBDD. With the increasing sizes of knowledge bases in recent years, this problem already becomes a bottleneck for further application of ROBDD. In order to reduce the possibility of exponential explosion, this proposal will study how to generalize ROBDD to obtain new languages with higher space-efficiency in the premise of not losing the main advantages of ROBDD (including completeness, canonicity, high time-efficiency and the existence of efficient compiling method). Therefore, this proposal plans to carry out the following research: generalizing ROBDD by introducing three types of decomposition to obtain new knowledge compilation languages; proposing a new evaluation criterion of time-efficiency of knowledge compilation languages to improve the current evaluating system, and then evaluating all new languages under the improved evaluating system; designing bottom-up and top-down compiling methods for the new languages; proposing a high-quality heuristic strategy to guide the compiling process to reduce compiling time and improve compilation quality; and developing packages of the new language to facilitate the use of new languages in practice. The research results of this proposal have the potential to replace the role of ROBDD in many applications; and they also have important reference effect to other research fields, including model counting and probabilistic reasoning.

精简有序二元决策图是到目前为止应用最广的知识编译语言，其问题在于空间效率较低，很多知识库被编译到该语言下时对应结果会发生指数爆炸。近年来随着知识库的增大，该问题已成为阻碍精简有序二元决策图进一步应用的瓶颈。为了降低指数爆炸发生的可能性，在保持精简有序二元决策图已有优势（具有完备性、规范性和较高时间效率以及存在高效编译方法）的前提下，拟研究如何对该语言进行泛化得到具有更高空间效率的语言。为此，通过向精简有序二元决策图引入三类分解提出新的知识编译语言；提出新的时间效率评估标准完善目前的评估体系，并在新体系下全面评估新语言的理论性质；为新语言设计自底向上和自顶向下两种编译方法；研究基于格局检测的启发式策略引导编译过程提高编译效率和编译质量；开发新语言的程序包方便应用领域对语言的使用。本项目的研究成果有望在多个应用领域中取代精简有序二元决策图的作用，并对模型计数和概率推理等领域具有重要借鉴作用。

精简有序二元决策图是一种具有完备性、规范性和较高时间效率以及存在高效编译语言，到目前为止应用最为广泛。精简有序二元决策图的问题在于空间效率较低，很多知识库被编译到该语言下时对应编译结果会发生指数爆炸。近年来随着知识库的增大，该问题已成为阻碍其进一步应用的瓶颈。.为了降低指数爆炸发生的可能性，在保持精简有序二元决策图已有优势的前提下，研究了如何对该语言引入分解进行泛化得到具有更高空间效率的语言。通过引入有界分解和树结构分解，提出两类规范的知识编译语言；提出了一种新的称为操作快速性的时间效率评估标准，该标准完善目前的目标语言评估体系；在新体系下全面评估新语言的理论性质；为新语言设计自底向上和自顶向下两种编译方法，前者基于合取操作，后者基于DPLL；研究基于格局检测的启发式策略引导编译过程提高编译效率和编译质量；开发了新语言的程序包方便应用领域对语言的使用。.项目期间发表论文10篇，其中，SCI期刊和一级学报论文7篇，CCF推荐为A、B类期刊和会议论文3篇。申请国家发明专利2项，授权软件著作权1项。作为第10完成人获得中国商业联合会科学技术奖一等奖1项。本项目的研究成果有望在多个应用领域中取代精简有序二元决策图的作用，并对模型计数和概率推理等领域具有重要借鉴作用。