Article(id=1327012519912256271, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327012311115608215, articleNumber=null, orderNo=null, doi=10.7544/issn1000-1239.202330546, pmid=null, cstr=null, oa=null, hot=null, price=null, onlineType=0, articleFormat=0, articleType=null, articleTypeStr=research-article, receivedDate=1687536000000, receivedDateStr=2023-06-24, revisedDate=1701878400000, revisedDateStr=2023-12-07, acceptedDate=null, acceptedDateStr=null, onlineDate=1794314039447, onlineDateStr=2026-11-10, pubDate=1738339200000, pubDateStr=2025-02-01, doiRegisterDate=null, doiRegisterDateStr=null, onlineIssueDate=1794314039447, onlineIssueDateStr=2026-11-10, onlineJustAcceptDate=null, onlineJustAcceptDateStr=null, onlineFirstDate=null, onlineFirstDateStr=null, sourceXml=null, magXml=null, createTime=1794314039447, creator=13701087609, updateTime=1794314039447, updator=13701087609, issue=Issue{id=1327012311115608215, tenantId=1146029695717560320, journalId=1324759914146529478, year='2025', volume='62', issue='2', pageStart='285', pageEnd='541', issueExtLink='null', onlineDate='null', pubDate='1738339200000', pubDateStr='2025-02-01', beforeIssueId=null, nextIssueId=null, price=null, status=1, issueComplete=1, articleOrder=1, issueType=-1, specialIssue=null, createTime=1794313989665, creator='13701087609', updateTime=1794376696965, updator='13701087609', preIssue=null, nextIssue=null, articleTotal=null, ext={EN=IssueExt(id=1327275325060395748, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327012311115608215, language=EN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=), CN=IssueExt(id=1327275325060395749, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327012311115608215, language=CN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=)}, issueFiles=null, downloadFileDto=null}, startPage=408, endPage=417, ext={EN=ArticleExt(id=1327012520096805648, articleId=1327012519912256271, tenantId=1146029695717560320, journalId=1324759914146529478, language=EN, title=A Model-Based Diagnosis Method for Integrating Cardinality Constraints and Enqueueing at Once, columnId=1325489891789910943, journalTitle=Journal of Computer Research and Development, columnName=Artificial Intelligence, runingTitle=null, highlight=null, articleAbstract=

Model-based diagnosis (MBD) finds a growing number of uses in different settings. It includes software fault localization, debugging of spread sheets, Web services, and hardware designs, and also the analysis of biological systems, among many others. Motivated by these different uses, there have been significant improvements made to MBD algorithms in recent years. Nevertheless, the analysis of larger and more complex systems motivates further improvements to existing approaches. Since computing diagnosis is computationally challenging, some MBD algorithms by compacting the model are presented successively, such as dominated-based compacted model with multiple observations (D-CMMO) approach. In this paper, we propose one new diagnosis model, namely, cardinality-constrained compacted (CCM) model, to solve the problem in which a considerable amount of time is needed when multiple observations are given and more than one fault is injected. CCM uses two methods to optimize the process of solving MBD. Firstly, we propose to utilize relationship of faulty system-outs and faulty components to limit the scope of target solution. Secondly, the performance of the MaxSAT (maximum satisfiability) solver is effectively improved by enqueueing all assumptions at once. Furthermore, experiment evaluations on ISCAS85 and ITC99 benchmarks show that compared with D-CMMO, the latest encoding algorithms for MBD, the above two optimization methods effectively reduce the scope of MBD problem, reduce the difficulty of searching for the target solution by the MaxSAT solver, and thus return diagnostic solution in a shorter time. On average, the solving efficiency of CCM method is improved by 64.5% and 92.8% compared with D-CMMO method respectively.

, authors=Yang Qing, Dantong Ouyang, Huisi Zhou, Liming Zhang*, authorsList=Yang Qing, Dantong Ouyang, Huisi Zhou, Liming Zhang, authorCompany=null, correspAuthors=Liming Zhang, authorNote=

born in 2000. Master candidate. His main research interest includes model-based diagnosis

born in 1968. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include the model-based diagnosis, SAT problem, and model checking

born in 1995. PhD. Her main research interests include MaxSAT, model-based diagnosis

born in 1980. PhD, senior engineer. Senior member of CCF. His main research interests include model-based diagnosis and SAT problem

, correspAuthorsNote=null, copyrightStatement=Copyright © 2025 Journal of Computer Research and Development. All rights reserved., copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=null, magXml=null, pdfUrl=null, pdf=null, pdfFileSize=null, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=null, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=null, mapNumber=null, fund=null), CN=ArticleExt(id=1327012524454687530, articleId=1327012519912256271, tenantId=1146029695717560320, journalId=1324759914146529478, language=CN, title=融合基数约束与单次入队的基于模型诊断方法, columnId=1325489892104483745, journalTitle=计算机研究与发展, columnName=人工智能, runingTitle=null, highlight=null, articleAbstract=

基于模型诊断(MBD)方法在不同的环境中有越来越多的用途,包括软件故障定位、电子表格的调试、Web服务和硬件设计,以及生物系统的分析等. 受这些不同用途的启发,近年来MBD算法改进成效显著. 然而,对体系庞大、结构复杂的系统,需要对现有方法进一步改进. 由于求解诊断解在计算上具有挑战性,因此相继提出了一些通过压缩模型的MBD算法来提高诊断效率,如基于统治的多观测压缩模型(dominated-based compacted model with multiple observations,D-CMMO)算法. 对于给定多个观测值且注入1个以上错误需要大量时间的诊断问题,提出了一个新的诊断模型CCM(cardinality-constrained compacted model)来解决. 基于基数约束的压缩模型算法使用2种方法对求解过程进行优化:首先,利用系统观测的故障输出和故障组件数量之间的约束关系来限制目标解的范围; 其次,通过对假设集采用单次入队方法, 进而有效提升MaxSAT(maximum satisfiability)求解器的性能. 此外,在ISCAS85和ITC99基准测试用例上的实验结果表明,与目前最新的MBD求解方法D-CMMO 相比,上述2种优化方法有效缩小了MBD问题的求解范围,降低 MaxSAT 求解器搜索目标解的难度,进而能在更短的时间内返回一个诊断解. 在平均状况下,CCM方法相比D-CMMO方法求解效率分别提升64.5%和92.8%.

, authors=青杨, 欧阳丹彤, 周慧思, 张立明*, authorsList=青杨, 欧阳丹彤, 周慧思, 张立明, authorCompany=null, correspAuthors=张立明, authorNote=

2000年生. 硕士研究生. 主要研究方向为基于模型的诊断

1968年生. 博士,教授,博士生导师,CCF高级会员. 主要研究方向为基于模型的诊断、可满足性问题、模型检测

1995年生. 博士. 主要研究方向为最大可满足性问题、基于模型的诊断

1980年生. 博士,高级工程师. CCF高级会员. 主要研究方向为基于模型诊断、可满足性问题

, correspAuthorsNote=
张立明()
, copyrightStatement=版权所有 © 2025 计算机研究与发展编辑部, copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=RHsI4Nc+t0KkVoXhcxYinw==, magXml=8UBhp8gmWUqQM0WmRcQpeQ==, pdfUrl=null, pdf=06GJJ3iQGXPZEQx0xnDePg==, pdfFileSize=1895665, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=CD5MFPtqGIdxB4IHgpn72w==, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=EbD1dBD8O36SKRHyOKXMDg==, mapNumber=null, fund=null)}, authors=[Author(id=1327012524958004018, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=qingyang3696@163.com, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012525037695795, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, authorId=1327012524958004018, language=EN, stringName=Yang Qing, firstName=Yang, middleName=null, lastName=Qing, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 2000. Master candidate. His main research interest includes model-based diagnosis

"}, bioImg=null, bioContent=

born in 2000. Master candidate. His main research interest includes model-based diagnosis

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012525108998964, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, authorId=1327012524958004018, language=CN, stringName=青杨, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"R7wqndAGE1ORRmfQHQOWsA==","content":"

2000年生. 硕士研究生. 主要研究方向为基于模型的诊断

"}, bioImg=R7wqndAGE1ORRmfQHQOWsA==, bioContent=

2000年生. 硕士研究生. 主要研究方向为基于模型的诊断

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1327012525188690742, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012525251605303, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, authorId=1327012525188690742, language=EN, stringName=Dantong Ouyang, firstName=Dantong, middleName=null, lastName=Ouyang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1968. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include the model-based diagnosis, SAT problem, and model checking

"}, bioImg=null, bioContent=

born in 1968. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include the model-based diagnosis, SAT problem, and model checking

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012525310325560, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, authorId=1327012525188690742, language=CN, stringName=欧阳丹彤, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"wl5zymf6zVpFBr8Aa2xUsg==","content":"

1968年生. 博士,教授,博士生导师,CCF高级会员. 主要研究方向为基于模型的诊断、可满足性问题、模型检测

"}, bioImg=wl5zymf6zVpFBr8Aa2xUsg==, bioContent=

1968年生. 博士,教授,博士生导师,CCF高级会员. 主要研究方向为基于模型的诊断、可满足性问题、模型检测

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1327012525419377466, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012525528429371, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, authorId=1327012525419377466, language=EN, stringName=Huisi Zhou, firstName=Huisi, middleName=null, lastName=Zhou, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1995. PhD. Her main research interests include MaxSAT, model-based diagnosis

"}, bioImg=null, bioContent=

born in 1995. PhD. Her main research interests include MaxSAT, model-based diagnosis

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012525608121148, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, authorId=1327012525419377466, language=CN, stringName=周慧思, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"K0Ly+HHaEhd+41tAPaM5qA==","content":"

1995年生. 博士. 主要研究方向为最大可满足性问题、基于模型的诊断

"}, bioImg=K0Ly+HHaEhd+41tAPaM5qA==, bioContent=

1995年生. 博士. 主要研究方向为最大可满足性问题、基于模型的诊断

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1327012525683618622, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=limingzhang@jlu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1327012527352951615, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, authorId=1327012525683618622, language=EN, stringName=Liming Zhang, firstName=Liming, middleName=null, lastName=Zhang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=null, bio={"content":"

born in 1980. PhD, senior engineer. Senior member of CCF. His main research interests include model-based diagnosis and SAT problem

"}, bioImg=null, bioContent=

born in 1980. PhD, senior engineer. Senior member of CCF. His main research interests include model-based diagnosis and SAT problem

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012527432643392, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, authorId=1327012525683618622, language=CN, stringName=张立明, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=null, bio={"img":"j4UnXzeHMirJnBmd2f4+Fw==","content":"

1980年生. 博士,高级工程师. CCF高级会员. 主要研究方向为基于模型诊断、可满足性问题

"}, bioImg=j4UnXzeHMirJnBmd2f4+Fw==, bioContent=

1980年生. 博士,高级工程师. CCF高级会员. 主要研究方向为基于模型诊断、可满足性问题

, aboutCorrespAuthor=null)}, companyList=null)], keywords=[Keyword(id=1327012527550083905, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=EN, orderNo=1, keyword=model-based diagnosis), Keyword(id=1327012527629775682, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=EN, orderNo=2, keyword=compacted model), Keyword(id=1327012527688495939, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=EN, orderNo=3, keyword=cardinality-constraints-based algorithm), Keyword(id=1327012527763993412, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=EN, orderNo=4, keyword=top-level diagnosis), Keyword(id=1327012527961125701, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=EN, orderNo=5, keyword=enqueueing all assumptions at once), Keyword(id=1327012528028234566, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=CN, orderNo=1, keyword=基于模型诊断), Keyword(id=1327012528099537735, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=CN, orderNo=2, keyword=压缩模型), Keyword(id=1327012528170840904, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=CN, orderNo=3, keyword=基于基数约束的算法), Keyword(id=1327012528292475721, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=CN, orderNo=4, keyword=顶层诊断解), Keyword(id=1327012528355390282, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=CN, orderNo=5, keyword=单次入队)], refs=[Reference(id=1327012532327396191, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=1, rfOrder=0, authorNames=null, journalName=null, refType=null, unstructuredReference=Reiter R. A theory of diagnosis from first principles[J]. Artificial Intelligence, 1987, 32(1): 57−95, articleTitle=null, refAbstract=null), Reference(id=1327012532386116448, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=2, rfOrder=1, authorNames=null, journalName=null, refType=null, unstructuredReference=Friedrich G, Gottlob G, Nejdl W. Hypothesis classification, abductive diagnosis and therapy[C]//Proc of the Expert Systems in Engineering Principles and Applications. Berlin: Springer, 1990: 69–78, articleTitle=null, refAbstract=null), Reference(id=1327012532449031009, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=3, rfOrder=2, authorNames=null, journalName=null, refType=null, unstructuredReference=Feldman A, Pill I, Wotawa F, et al. Efficient model-based diagnosis of sequential circuits[C]//Proc of the 34th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2020: 2814–2821, articleTitle=null, refAbstract=null), Reference(id=1327012532511945570, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=3, authorNames=null, journalName=null, refType=null, unstructuredReference=Struss P, Price C. Model-based systems in the automotive industry[J]. AI Magazine, 2004, 24(4): 17−34, articleTitle=null, refAbstract=null), Reference(id=1327012532566471523, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=4, authorNames=null, journalName=null, refType=null, unstructuredReference=Ardissono L, Console L, Goy A, et al. Cooperative model-based diagnosis of web services[C]//Proc of the 16th Int Workshop on Principles of Diagnosis. Paris: CEUR-WS, 2005: 125–130, articleTitle=null, refAbstract=null), Reference(id=1327012532633580388, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=6, rfOrder=5, authorNames=null, journalName=null, refType=null, unstructuredReference=Jannach D, Schmitz T. Model-based diagnosis of spreadsheet programs: A constraint-based debugging approach[J]. Automated Software Engineering, 2016, 23(1): 105−144, articleTitle=null, refAbstract=null), Reference(id=1327012532717466469, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=7, rfOrder=6, authorNames=null, journalName=null, refType=null, unstructuredReference=Jose M, Majumdar R. Cause clue clauses: Error localization using maximum satisfiability[J]. ACM SIGPLAN Notices, 2011, 46(6): 437−446, articleTitle=null, refAbstract=null), Reference(id=1327012532809741158, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=8, rfOrder=7, authorNames=null, journalName=null, refType=null, unstructuredReference=Feldman A, Provan G M, Van Gemund A J C. Computing minimal diagnoses by greedy stochastic search[C]//Proc of the 23rd AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2008: 911–918, articleTitle=null, refAbstract=null), Reference(id=1327012532889432935, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=9, rfOrder=8, authorNames=null, journalName=null, refType=null, unstructuredReference=Siddiqi S A, Huang Jinbo. Hierarchical diagnosis of multiple faults[C]//Proc of the 20th Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2007: 581–586, articleTitle=null, refAbstract=null), Reference(id=1327012532973319016, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=10, rfOrder=9, authorNames=null, journalName=null, refType=null, unstructuredReference=Jannach D, Schmitz T, Shchekotykhin K M. Parallelized hitting set computation for model-based diagnosis[C]//Proc of the 29th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2015: 1503–1510, articleTitle=null, refAbstract=null), Reference(id=1327012533048816489, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=11, rfOrder=10, authorNames=null, journalName=null, refType=null, unstructuredReference=Ansótegui C, Bonet M L, Levy J. SAT-based MaxSAT algorithms[J]. Artificial Intelligence, 2013, 196(1): 77−105, articleTitle=null, refAbstract=null), Reference(id=1327012533153674090, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=12, rfOrder=11, authorNames=null, journalName=null, refType=null, unstructuredReference=Feldman A, Provan G, de Kleer J. Solving model-based diagnosis problems with Max-SAT solvers and vice versa[C]//Proc of the 21st Int Workshop on Principles of Diagnosis. New York: PHM Society, 2010: 185–192, articleTitle=null, refAbstract=null), Reference(id=1327012533245948779, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=13, rfOrder=12, authorNames=null, journalName=null, refType=null, unstructuredReference=Stern R T, Kalech M, Feldman A. Exploring the duality in conflict-directed model-based diagnosis[C]//Proc of the 26th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2012: 828–834, articleTitle=null, refAbstract=null), Reference(id=1327012533308863340, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=14, rfOrder=13, authorNames=null, journalName=null, refType=null, unstructuredReference=Ignatiev A, Morgado A, Weissenbacher G, et al. Model-based diagnosis with multiple observations[C]//Proc of the 28th Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2019: 1108–1115, articleTitle=null, refAbstract=null), Reference(id=1327012533375972205, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=15, rfOrder=14, authorNames=null, journalName=null, refType=null, unstructuredReference=Lamraoui S, Nakajima S. A formula-based approach for automatic fault localization of imperative programs[C]//Proc of the 16th Int Conf on Formal Engineering Methods. Berlin: Springer, 2014: 251–266, articleTitle=null, refAbstract=null), Reference(id=1327012533493412718, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=16, rfOrder=15, authorNames=null, journalName=null, refType=null, unstructuredReference=Lamraoui S, Nakajima S. A formula-based approach for automatic fault localization of multi-fault programs[J]. Journal of Information Processing, 2016, 24(1): 88−98, articleTitle=null, refAbstract=null), Reference(id=1327012533577298799, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=17, rfOrder=16, authorNames=null, journalName=null, refType=null, unstructuredReference=Narodytska N, Bacchus F. Maximum satisfiability using core-guided MaxSAT resolution[C]//Proc of the 28th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2014: 2717–2723, articleTitle=null, refAbstract=null), Reference(id=1327012533661184880, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=18, rfOrder=17, authorNames=null, journalName=null, refType=null, unstructuredReference=Cai Shaowei, Lei Zhendong. Old techniques in new ways: Clause weighting, unit propagation and hybridization for maximum satisfiability[J]. Artificial Intelligence, 2020, 287: 103354−103354, articleTitle=null, refAbstract=null), Reference(id=1327012533732488049, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=19, rfOrder=18, authorNames=null, journalName=null, refType=null, unstructuredReference=Marques-Silva J, Heras F, Janota M, et al. On computing minimal correction subsets[C]//Proc of the 23rd Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2013: 615–622, articleTitle=null, refAbstract=null), Reference(id=1327012533795402610, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=20, rfOrder=19, authorNames=null, journalName=null, refType=null, unstructuredReference=Previti A, Mencía C, Järvisalo M, et al. Premise set caching for enumerating minimal correction subsets[C]//Proc of the 32nd AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2018: 6633–6640, articleTitle=null, refAbstract=null), Reference(id=1327012533883482995, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=21, rfOrder=20, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhou Huisi, Ouyang Dantong, Zhang Liming, et al. Model-based diagnosis with improved implicit hitting set dualization. Forthcoming[J]. Applied Intelligence, 2022, 52(2): 2111−2118, articleTitle=null, refAbstract=null), Reference(id=1327012533958980468, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=22, rfOrder=21, authorNames=null, journalName=null, refType=null, unstructuredReference=Kalech M, Stern R, Lazebnik E. Minimal cardinality diagnosis in problems with multiple observations[J]. Diagnostics, 2021, 11(5): 780−780, articleTitle=null, refAbstract=null), Reference(id=1327012534030283637, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=23, rfOrder=22, authorNames=null, journalName=null, refType=null, unstructuredReference=Gu Jun, Purdom P W, Franco J, et al. Algorithms for the Satisfiability Problem[M]//Handbook of Combinatorial Optimization. Berlin: Springer, 1999: 379–572, articleTitle=null, refAbstract=null), Reference(id=1327012534101586806, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=24, rfOrder=23, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhou Huisi, Ouyang Dantong, Zhao Xiangfu, et al. Two compacted models for efficient model-based diagnosis[C]//Proc of the 34th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2022: 3885−3893, articleTitle=null, refAbstract=null), Reference(id=1327012534177084279, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=25, rfOrder=24, authorNames=null, journalName=null, refType=null, unstructuredReference=Metodi A, Stern R, Kalech M, et al. A novel SAT-based approach to model based diagnosis[J]. Journal of Artificial Intelligence, 2014, 51(1): 377−411, articleTitle=null, refAbstract=null), Reference(id=1327012534248387448, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=26, rfOrder=25, authorNames=null, journalName=null, refType=null, unstructuredReference=Marques-Silva J , Mikoláš J, Ignatiev A , et al. Efficient model based diagnosis with maximum satisfiability[C]//Proc of the 24th Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2015: 1966−1972, articleTitle=null, refAbstract=null), Reference(id=1327012534323884921, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=27, rfOrder=26, authorNames=null, journalName=null, refType=null, unstructuredReference=Amit M, Roni S, Meir K, et al. Compiling model-based diagnosis to Boolean satisfaction[C]//Proc of the 26th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2012: 793−799, articleTitle=null, refAbstract=null), Reference(id=1327012534399382394, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=28, rfOrder=27, authorNames=null, journalName=null, refType=null, unstructuredReference=Thomas L, Robert E T. A fast algorithm for finding dominators in a flowgraph[J]. ACM Transactions Programming Languages and Systems, 1979, 1(1): 121−141, articleTitle=null, refAbstract=null), Reference(id=1327012534617486203, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=29, rfOrder=28, authorNames=null, journalName=null, refType=null, unstructuredReference=刘梦,欧阳丹彤,刘伯文,等. 结合问题特征的分组式诊断方法[J] 电子学报,2018,46(3):589−594, articleTitle=null, refAbstract=null), Reference(id=1327012536572031868, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=29, rfOrder=29, authorNames=null, journalName=null, refType=null, unstructuredReference=Liu Meng, Ouyang Dantong, Liu Bowen, et al. Grouped diagnosis approach using the feature of problem[J]. Acta Electronica Sinica, 2018, 46(3): 589−594 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327012536756581245, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=30, rfOrder=30, authorNames=null, journalName=null, refType=null, unstructuredReference=欧阳丹彤,刘伯文,刘梦,等. 结合电路结构基于分块的诊断方法[J] 电子学报,2018,46(7):1571−1577, articleTitle=null, refAbstract=null), Reference(id=1327012536869827454, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=30, rfOrder=31, authorNames=null, journalName=null, refType=null, unstructuredReference=Ouyang Dantong, Liu Bowen, Liu Meng, et al. A block-based diagnostic method combing with the circuit structure[J]. Acta Electronica Sinica, 2018, 46(7): 1571−1577 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327012537012433791, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=31, rfOrder=32, authorNames=null, journalName=null, refType=null, unstructuredReference=周慧思,欧阳丹彤,田鑫亮,等. 基于模型诊断的一种新编码方法[J] 计算机研究与发展,2023,60(1):95−102, articleTitle=null, refAbstract=null), Reference(id=1327012537222148992, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=31, rfOrder=33, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhou Huisi, Ouyang Dantong, Tian Xinliang, et al. A novel encoding for model based diagnosis[J]. Journal of Computer Research and Development, 2023, 60(1): 95−102 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327012537394115457, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=32, rfOrder=34, authorNames=null, journalName=null, refType=null, unstructuredReference=Siddiqi S A, Huang Jinbo. Sequential diagnosis by abstraction[J]. Journal of Artificial Intelligence Research, 2011, 41: 329−365, articleTitle=null, refAbstract=null), Reference(id=1327012537473807235, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=33, rfOrder=35, authorNames=null, journalName=null, refType=null, unstructuredReference=Eèn N, Sörensson N. Temporal induction by incremental SAT solving[J]. Electronic Notes in Theoretical Computer Science, 2003, 89(4): 543−560, articleTitle=null, refAbstract=null), Reference(id=1327012537553499012, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=34, rfOrder=36, authorNames=null, journalName=null, refType=null, unstructuredReference=Eèn N, Sörensson N. An extensible SAT-solver[C]//Proc of the 6th Theory and Applications of Satisfiability Testing. Berlin: Springer, 2004: 502−518, articleTitle=null, refAbstract=null), Reference(id=1327012537771602821, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=35, rfOrder=37, authorNames=null, journalName=null, refType=null, unstructuredReference=Audemard G, Lagniez J M, Simon L. Improving Glucose for incremental SAT solving with assumptions: Application to MUS extraction[C]//Proc of the 16th Theory and Applications of Satisfiability Testing. Berlin: Springer, 2013: 309–317, articleTitle=null, refAbstract=null), Reference(id=1327012537998095238, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=36, rfOrder=38, authorNames=null, journalName=null, refType=null, unstructuredReference=Ogawa T, Liu Yangyang, Hasegawa R, et al. Modulo based CNF encoding of cardinality constraints and its application to MaxSAT solvers[C]//Proc of the 25th IEEE Int Conf on Tools with Artificial Intelligence. Piscataway, NJ: IEEE, 2013: 9−17, articleTitle=null, refAbstract=null), Reference(id=1327012538065204103, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=37, rfOrder=39, authorNames=null, journalName=null, refType=null, unstructuredReference=Brglzz F, Fujtwara H. A neutral netlist of 10 combinational benchmark circuits and a target translator in FORTRAN[J/OL]. IEEE International Symposium on Circuits and Systems. 1985[2023-03-20].https://www.researchgate.net/publication/239562831_A_neutral_netlist_of_10_combinational_circuits_and_a_target_translator_in_fortran, articleTitle=null, refAbstract=null), Reference(id=1327012538132312968, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=38, rfOrder=40, authorNames=null, journalName=null, refType=null, unstructuredReference=Siddiqi S A. Computing minimum-cardinality diagnoses by model relaxation[C]//Proc of the 22nd Int Joint Conf on Artificial Intelligence. Palo Alto, CA : AAAI, 2011: 1087–1092, articleTitle=null, refAbstract=null)], funds=null, companyList=[AuthorCompany(id=1327012524748288811, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, xref=null, ext=[AuthorCompanyExt(id=1327012524756677420, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, companyId=1327012524748288811, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=College of Computer Science and Technology, Jilin University, Changchun 130012), AuthorCompanyExt(id=1327012524790231853, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, companyId=1327012524748288811, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=吉林大学计算机科学与技术学院 长春 130012)]), AuthorCompany(id=1327012524857340718, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, xref=null, ext=[AuthorCompanyExt(id=1327012524869923631, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, companyId=1327012524857340718, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=Key Laboratory of Symbol Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012), AuthorCompanyExt(id=1327012524882506544, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, companyId=1327012524857340718, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012)])], figs=[ArticleFig(id=1327012528464442187, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=EN, label=Figure 1, caption=c17 circuit diagram, figureFileSmall=2utuThSfg2DoV//NYTdVYg==, figureFileBig=CD5MFPtqGIdxB4IHgpn72w==, tableContent=null), ArticleFig(id=1327012528573494092, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=CN, label=图1, caption=c17电路图, figureFileSmall=2utuThSfg2DoV//NYTdVYg==, figureFileBig=CD5MFPtqGIdxB4IHgpn72w==, tableContent=null), ArticleFig(id=1327012528976147277, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=EN, label=Figure 2, caption=Example diagram for c17 circuit with multiple observations, figureFileSmall=LOKaQxvtQFV5e1/ghOy9HA==, figureFileBig=00MzEHQhiDq0DR+RHkef6w==, tableContent=null), ArticleFig(id=1327012529081004878, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=CN, label=图2, caption=多观测的c17电路示例图, figureFileSmall=LOKaQxvtQFV5e1/ghOy9HA==, figureFileBig=00MzEHQhiDq0DR+RHkef6w==, tableContent=null), ArticleFig(id=1327012529190056783, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=EN, label=Figure 3, caption=Comparison of run time of D-CMMO and CCM methods on ISCAS85 benchmark in the mode of Stack-At-0, figureFileSmall=2urEJqZ079yPKa43P1gfHQ==, figureFileBig=w++EXdPNIeKWuBKKYiDnkg==, tableContent=null), ArticleFig(id=1327012529278137168, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=CN, label=图3, caption=D-CMMO和CCM方法在Stack-At-0模式下ISCAS85基准上的运行时间比较, figureFileSmall=2urEJqZ079yPKa43P1gfHQ==, figureFileBig=w++EXdPNIeKWuBKKYiDnkg==, tableContent=null), ArticleFig(id=1327012529441715025, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=EN, label=Figure 4, caption=Comparison of run time of D-CMMO and CCM methods on ISCAS85 benchmark in the mode of Stack-At-1, figureFileSmall=QYGL4zfcQV3t1t52Ss/Aaw==, figureFileBig=ywoR7d7Kk8txVg1aR/b7Pw==, tableContent=null), ArticleFig(id=1327012529525601106, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=CN, label=图4, caption=D-CMMO和CCM方法在Stack-At-1模式下ISCAS85基准上的运行时间比较, figureFileSmall=QYGL4zfcQV3t1t52Ss/Aaw==, figureFileBig=ywoR7d7Kk8txVg1aR/b7Pw==, tableContent=null), ArticleFig(id=1327012529626264403, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=EN, label=Figure 5, caption=Comparison of run time of D-CMMO and CCM methods on ISCAS85 benchmark in the mode of FLIP, figureFileSmall=06WuIVy0ry3vJqB3r3HSbw==, figureFileBig=iydv7bJCIYhctybcDbDA4Q==, tableContent=null), ArticleFig(id=1327012529735316308, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=CN, label=图5, caption=D-CMMO和CCM方法在FLIP模式下ISCAS85基准上的运行时间比较, figureFileSmall=06WuIVy0ry3vJqB3r3HSbw==, figureFileBig=iydv7bJCIYhctybcDbDA4Q==, tableContent=null), ArticleFig(id=1327012529903088469, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=EN, label=Figure 6, caption=Comparison of run time of D-CMMO and CCM methods on ITC99 benchmark in the mode of Stack-At-0, figureFileSmall=MuIyCP4QyCgrEod+a53C/A==, figureFileBig=bUUVO9E+8UQkrw0cIz4rhg==, tableContent=null), ArticleFig(id=1327012529974391638, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=CN, label=图6, caption=D-CMMO和CCM方法在Stack-At-0模式下ITC99基准上的运行时间比较, figureFileSmall=MuIyCP4QyCgrEod+a53C/A==, figureFileBig=bUUVO9E+8UQkrw0cIz4rhg==, tableContent=null), ArticleFig(id=1327012530062472023, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=EN, label=Figure 7, caption=Comparison of run time of D-CMMO and CCM methods on ITC99 benchmark in the mode of Stack-At-1, figureFileSmall=W3LDPIY4302j2jqihDbMQg==, figureFileBig=rRSlAr0JaVCH2r5KD93t9A==, tableContent=null), ArticleFig(id=1327012531811496792, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=CN, label=图7, caption=D-CMMO和CCM方法在Stack-At-1模式下ITC99基准上的运行时间比较, figureFileSmall=W3LDPIY4302j2jqihDbMQg==, figureFileBig=rRSlAr0JaVCH2r5KD93t9A==, tableContent=null), ArticleFig(id=1327012531886994265, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=EN, label=Figure 8, caption=Comparison of run time of D-CMMO and CCM methods on ITC99 benchmark in the mode of FLIP, figureFileSmall=S86FDX/NdIHKH74E6mKN+g==, figureFileBig=t+jKq49ijnLQMufPLf8YPA==, tableContent=null), ArticleFig(id=1327012531962491738, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=CN, label=图8, caption=D-CMMO和CCM方法在FLIP模式下ITC99基准上的运行时间比较, figureFileSmall=S86FDX/NdIHKH74E6mKN+g==, figureFileBig=t+jKq49ijnLQMufPLf8YPA==, tableContent=null), ArticleFig(id=1327012532017017691, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=EN, label=Table 1, caption=Solved Results in the Example of ISCAS85, figureFileSmall=null, figureFileBig=null, tableContent=
电路系统输
入数量
系统输
出数量
组件数量CCM wins
Stack-At-0Stack-At-1FLIP
c17526192010
c432367160152319
c4994132202252228
c8806026383121411
c13554132546232019
c19083325880222518
c26702331401193271915
c354050221669212414
c53151781232307191718
c62883232241616133
c75522071083512131110
), ArticleFig(id=1327012532084126556, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=CN, label=表1, caption=

在ISCAS85实例上的求解结果

, figureFileSmall=null, figureFileBig=null, tableContent=
电路系统输
入数量
系统输
出数量
组件数量CCM wins
Stack-At-0Stack-At-1FLIP
c17526192010
c432367160152319
c4994132202252228
c8806026383121411
c13554132546232019
c19083325880222518
c26702331401193271915
c354050221669212414
c53151781232307191718
c62883232241616133
c75522071083512131110
), ArticleFig(id=1327012532151235421, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=EN, label=Table 2, caption=Solved Results in the Example of ITC99, figureFileSmall=null, figureFileBig=null, tableContent=
电路系统输
入数量
系统输
出数量
组件数量CCM wins
Stack-At-0Stack-At-1FLIP
b012239354431
b021124303530
b0344144413737
b04118632374043
b05136821383445
b062649302843
b0718380443938
b0894157453429
b0911146443344
b10116174404328
b1176662414442
b1256963354244
b131010310332734
b1432548567363921
b1536707922384229
b20322217158282134
b21322217482252425
b22322225460212524
), ArticleFig(id=1327012532218344286, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, language=CN, label=表2, caption=

在ITC99实例上的求解结果

, figureFileSmall=null, figureFileBig=null, tableContent=
电路系统输
入数量
系统输
出数量
组件数量CCM wins
Stack-At-0Stack-At-1FLIP
b012239354431
b021124303530
b0344144413737
b04118632374043
b05136821383445
b062649302843
b0718380443938
b0894157453429
b0911146443344
b10116174404328
b1176662414442
b1256963354244
b131010310332734
b1432548567363921
b1536707922384229
b20322217158282134
b21322217482252425
b22322225460212524
)], attaches=null, journal=Journal(id=1324759606947315908, delFlag=0, nameCn=计算机研究与发展, nameEn=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, issn=1000-1239, eissn=null, cn=11-1777/TP, coden=null, periodic=0, language=CN, oaType=null, ccby=null, superviseOffice=null, ownerOffice=null, pubOffice=null, editorOffice=null, officeType=null, aims=null, clcCode=null, officeProv=null, officeCity=null, officeAddr=null, officeZip=null, officeEmail=null, officePhone=null, editDirector=null, officeDirector=null, officeDirectorPhone=null, officeStaffNum=null, officeEmpNum=null, coverPicUrl=k2l8zgqwstuxxevFX2qxVA==, journalPrice=null, startedYear=null, abbrevIsoEn=Journal of Computer Research and Development, journalRemark=null, publicationField=null, createdTime=1793776903141, updatedTime=1793850698612, createdBy=18614031015, updatedBy=13701087609, firstLetterCn=J, firstLetterEn=J, subjectCode=Electronic Information, subjectName=null, subjectCodeEn=Electronic Information, subjectNameEn=null, picCn=k2l8zgqwstuxxevFX2qxVA==, picEn=r6k0Ry+RD+c/VXj5QarmDw==, jcr=null, cjcr=null, exts=[JournalExt(id=1325069127710286688, language=CN, name=计算机研究与发展, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698640, updatedTime=1793850698640, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""}), JournalExt(id=1325069127777395553, language=EN, name=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698656, updatedTime=1793850698656, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""})], databaseList=null, tenantJournalId=1324759914146529478, websiteList=[Website(id=1325070300139892771, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN, language=CN, createTime=1793850978169, createBy=18614031015, updateTime=1793851040259, updateBy=18614031015, name=计算机研究与发展-中文, tplId=1146099689490845704, title=计算机研究与发展, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070893751349360, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=articleTextType, value=kx, createTime=1793851119697, updateTime=1793851119697, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893730377837, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=banner, value=null, createTime=1793851119692, updateTime=1793851119692, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893772320883, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=grayFlag, value=0, createTime=1793851119702, updateTime=1793851119702, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893721989228, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851119690, updateTime=1793851119690, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893784903797, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=minRunFlag, value=0, createTime=1793851119705, updateTime=1793851119705, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893742960751, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic, createTime=1793851119695, updateTime=1793851119695, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893780709492, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=silenceFlag, value=0, createTime=1793851119704, updateTime=1793851119704, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893738766446, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_cn_619/, createTime=1793851119694, updateTime=1793851119694, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893755543665, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeColor, value=null, createTime=1793851119698, updateTime=1793851119698, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893763932274, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeStyle, value=null, createTime=1793851119700, updateTime=1793851119700, creator=18614031015, updator=18614031015)]), Website(id=1325070300580294698, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN, language=EN, createTime=1793850978274, createBy=18614031015, updateTime=1793851036638, updateBy=18614031015, name=计算机研究与发展-英文, tplId=1146101810881728533, title=Journal of Computer Research and Development, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070925288321148, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=articleTextType, value=kx, createTime=1793851127216, updateTime=1793851127216, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925263155321, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=banner, value=null, createTime=1793851127210, updateTime=1793851127210, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925309292671, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=grayFlag, value=0, createTime=1793851127221, updateTime=1793851127221, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925254766712, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851127208, updateTime=1793851127208, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925326069889, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=minRunFlag, value=0, createTime=1793851127225, updateTime=1793851127225, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925279932539, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic, createTime=1793851127214, updateTime=1793851127214, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925317681280, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=silenceFlag, value=0, createTime=1793851127223, updateTime=1793851127223, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925271543930, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_en_623/, createTime=1793851127212, updateTime=1793851127212, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925292515453, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeColor, value=null, createTime=1793851127217, updateTime=1793851127217, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925300904062, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeStyle, value=null, createTime=1793851127219, updateTime=1793851127219, creator=18614031015, updator=18614031015)])], journalTitle=计算机研究与发展, weixinUrl=null, journalUrl=https://crad.ict.ac.cn/, iacademicId=null, status=1, seqNo=null, journalTitleEn=Journal of Computer Research and Development, journalPhotoCn=k2l8zgqwstuxxevFX2qxVA==, journalPhotoEn=r6k0Ry+RD+c/VXj5QarmDw==, journalFirstLetter=J, journalRecommend=null, journalNew=null, journalCollection=null, jcrJf=null, cjcrJf=null, jcrJfStr=null, cjcrJfStr=null, submissionFirstDecision=null, sciSubjectClassification=null, casSubjectClassification=null, citeScore=null, totalCitationFrequency=null, icpCode=null, psCode=null, advertisingLicenseCode=null, copyrightInformation=null, country=null, option=, provinceCode=null, provinceName=null, collectFlag=false, interPubPlatform=, interPubPlatformUrl=null), detailUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202330546, detailUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202330546, pdfUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/PDF/10.7544/issn1000-1239.202330546, pdfUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/PDF/10.7544/issn1000-1239.202330546, aliStartDate=0, aliEndDate=0, collectionFlag=false, citedCount=null, citedUrl=null, previewStatus=0, delFlag=0, hasFullText=1, orderTime=1738339200000, fullTextJson=null, articleText=null, reference=null)
收藏切换
融合基数约束与单次入队的基于模型诊断方法
青杨 , 欧阳丹彤 , 周慧思 , 张立明 *
计算机研究与发展 | 人工智能 2025,62(2): 408-417
收起
收藏切换
计算机研究与发展 |人工智能 2025 , 62 (2) : 408 -417
融合基数约束与单次入队的基于模型诊断方法
全屏
[Author(id=1327012524958004018, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=qingyang3696@163.com, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012525037695795, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, authorId=1327012524958004018, language=EN, stringName=Yang Qing, firstName=Yang, middleName=null, lastName=Qing, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 2000. Master candidate. His main research interest includes model-based diagnosis

"}, bioImg=null, bioContent=

born in 2000. Master candidate. His main research interest includes model-based diagnosis

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012525108998964, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, authorId=1327012524958004018, language=CN, stringName=青杨, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"R7wqndAGE1ORRmfQHQOWsA==","content":"

2000年生. 硕士研究生. 主要研究方向为基于模型的诊断

"}, bioImg=R7wqndAGE1ORRmfQHQOWsA==, bioContent=

2000年生. 硕士研究生. 主要研究方向为基于模型的诊断

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1327012525188690742, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012525251605303, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, authorId=1327012525188690742, language=EN, stringName=Dantong Ouyang, firstName=Dantong, middleName=null, lastName=Ouyang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1968. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include the model-based diagnosis, SAT problem, and model checking

"}, bioImg=null, bioContent=

born in 1968. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include the model-based diagnosis, SAT problem, and model checking

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012525310325560, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, authorId=1327012525188690742, language=CN, stringName=欧阳丹彤, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"wl5zymf6zVpFBr8Aa2xUsg==","content":"

1968年生. 博士,教授,博士生导师,CCF高级会员. 主要研究方向为基于模型的诊断、可满足性问题、模型检测

"}, bioImg=wl5zymf6zVpFBr8Aa2xUsg==, bioContent=

1968年生. 博士,教授,博士生导师,CCF高级会员. 主要研究方向为基于模型的诊断、可满足性问题、模型检测

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1327012525419377466, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012525528429371, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, authorId=1327012525419377466, language=EN, stringName=Huisi Zhou, firstName=Huisi, middleName=null, lastName=Zhou, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1995. PhD. Her main research interests include MaxSAT, model-based diagnosis

"}, bioImg=null, bioContent=

born in 1995. PhD. Her main research interests include MaxSAT, model-based diagnosis

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012525608121148, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, authorId=1327012525419377466, language=CN, stringName=周慧思, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"K0Ly+HHaEhd+41tAPaM5qA==","content":"

1995年生. 博士. 主要研究方向为最大可满足性问题、基于模型的诊断

"}, bioImg=K0Ly+HHaEhd+41tAPaM5qA==, bioContent=

1995年生. 博士. 主要研究方向为最大可满足性问题、基于模型的诊断

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1327012525683618622, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=limingzhang@jlu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1327012527352951615, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, authorId=1327012525683618622, language=EN, stringName=Liming Zhang, firstName=Liming, middleName=null, lastName=Zhang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=null, bio={"content":"

born in 1980. PhD, senior engineer. Senior member of CCF. His main research interests include model-based diagnosis and SAT problem

"}, bioImg=null, bioContent=

born in 1980. PhD, senior engineer. Senior member of CCF. His main research interests include model-based diagnosis and SAT problem

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012527432643392, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327012519912256271, authorId=1327012525683618622, language=CN, stringName=张立明, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=null, bio={"img":"j4UnXzeHMirJnBmd2f4+Fw==","content":"

1980年生. 博士,高级工程师. CCF高级会员. 主要研究方向为基于模型诊断、可满足性问题

"}, bioImg=j4UnXzeHMirJnBmd2f4+Fw==, bioContent=

1980年生. 博士,高级工程师. CCF高级会员. 主要研究方向为基于模型诊断、可满足性问题

, aboutCorrespAuthor=null)}, companyList=null)]
青杨 , 欧阳丹彤, 周慧思, 张立明*
作者信息
  • 吉林大学计算机科学与技术学院 长春 130012
  • 符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012
通讯作者:
张立明()
作者简介:

2000年生. 硕士研究生. 主要研究方向为基于模型的诊断

1968年生. 博士,教授,博士生导师,CCF高级会员. 主要研究方向为基于模型的诊断、可满足性问题、模型检测

1995年生. 博士. 主要研究方向为最大可满足性问题、基于模型的诊断

1980年生. 博士,高级工程师. CCF高级会员. 主要研究方向为基于模型诊断、可满足性问题

A Model-Based Diagnosis Method for Integrating Cardinality Constraints and Enqueueing at Once
Yang Qing , Dantong Ouyang, Huisi Zhou, Liming Zhang*
Affiliations
  • College of Computer Science and Technology, Jilin University, Changchun 130012
  • Key Laboratory of Symbol Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012
  • born in 2000. Master candidate. His main research interest includes model-based diagnosis

    born in 1968. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include the model-based diagnosis, SAT problem, and model checking

    born in 1995. PhD. Her main research interests include MaxSAT, model-based diagnosis

    born in 1980. PhD, senior engineer. Senior member of CCF. His main research interests include model-based diagnosis and SAT problem

出版时间: 2025-02-01 doi: 10.7544/issn1000-1239.202330546
文章导航
收藏切换

基于模型诊断(MBD)方法在不同的环境中有越来越多的用途,包括软件故障定位、电子表格的调试、Web服务和硬件设计,以及生物系统的分析等. 受这些不同用途的启发,近年来MBD算法改进成效显著. 然而,对体系庞大、结构复杂的系统,需要对现有方法进一步改进. 由于求解诊断解在计算上具有挑战性,因此相继提出了一些通过压缩模型的MBD算法来提高诊断效率,如基于统治的多观测压缩模型(dominated-based compacted model with multiple observations,D-CMMO)算法. 对于给定多个观测值且注入1个以上错误需要大量时间的诊断问题,提出了一个新的诊断模型CCM(cardinality-constrained compacted model)来解决. 基于基数约束的压缩模型算法使用2种方法对求解过程进行优化:首先,利用系统观测的故障输出和故障组件数量之间的约束关系来限制目标解的范围; 其次,通过对假设集采用单次入队方法, 进而有效提升MaxSAT(maximum satisfiability)求解器的性能. 此外,在ISCAS85和ITC99基准测试用例上的实验结果表明,与目前最新的MBD求解方法D-CMMO 相比,上述2种优化方法有效缩小了MBD问题的求解范围,降低 MaxSAT 求解器搜索目标解的难度,进而能在更短的时间内返回一个诊断解. 在平均状况下,CCM方法相比D-CMMO方法求解效率分别提升64.5%和92.8%.

基于模型诊断  /  压缩模型  /  基于基数约束的算法  /  顶层诊断解  /  单次入队

Model-based diagnosis (MBD) finds a growing number of uses in different settings. It includes software fault localization, debugging of spread sheets, Web services, and hardware designs, and also the analysis of biological systems, among many others. Motivated by these different uses, there have been significant improvements made to MBD algorithms in recent years. Nevertheless, the analysis of larger and more complex systems motivates further improvements to existing approaches. Since computing diagnosis is computationally challenging, some MBD algorithms by compacting the model are presented successively, such as dominated-based compacted model with multiple observations (D-CMMO) approach. In this paper, we propose one new diagnosis model, namely, cardinality-constrained compacted (CCM) model, to solve the problem in which a considerable amount of time is needed when multiple observations are given and more than one fault is injected. CCM uses two methods to optimize the process of solving MBD. Firstly, we propose to utilize relationship of faulty system-outs and faulty components to limit the scope of target solution. Secondly, the performance of the MaxSAT (maximum satisfiability) solver is effectively improved by enqueueing all assumptions at once. Furthermore, experiment evaluations on ISCAS85 and ITC99 benchmarks show that compared with D-CMMO, the latest encoding algorithms for MBD, the above two optimization methods effectively reduce the scope of MBD problem, reduce the difficulty of searching for the target solution by the MaxSAT solver, and thus return diagnostic solution in a shorter time. On average, the solving efficiency of CCM method is improved by 64.5% and 92.8% compared with D-CMMO method respectively.

model-based diagnosis  /  compacted model  /  cardinality-constraints-based algorithm  /  top-level diagnosis  /  enqueueing all assumptions at once
青杨, 欧阳丹彤, 周慧思, 张立明. 融合基数约束与单次入队的基于模型诊断方法. 计算机研究与发展, 2025 , 62 (2) : 408 -417 . DOI: 10.7544/issn1000-1239.202330546
Yang Qing, Dantong Ouyang, Huisi Zhou, Liming Zhang. A Model-Based Diagnosis Method for Integrating Cardinality Constraints and Enqueueing at Once[J]. Journal of Computer Research and Development, 2025 , 62 (2) : 408 -417 . DOI: 10.7544/issn1000-1239.202330546
基于模型诊断(model-based diagnosis,MBD) [1]是分析复杂系统并解释系统故障原因的重要方法,这个方法已经在人工智能领域被研究了多年. 一般来说,MBD方法要么使用系统中每个组件都是已知和定义的溯因系统[2],要么使用系统中所有组件都未被定义的一致性模型[3]. 这些算法被广泛应用于各个领域,包括质量模型[4]、Web服务的调试[5]、电子表格调试[6]和软件故障定位[7]等领域.
本文的主要贡献包括2个方面:
1)提出通过传播系统输入得到诊断解的上界,将硬子句作为基数约束编码加入到MaxSAT编码中. 这种基数约束方法可以缩小诊断的搜索范围,进而降低求解诊断的难度.
2)提出利用单次入队方法将假设集中的所有文字入队到第1决策层,然后再进行单元传播,从而避免出现冲突后回溯到第0决策层导致的对假设集重复赋值的问题. 同时能够有效避免假设集中的否定文字被频繁替换到子句的看守列表中,排除对子句中的文字重复访问的代价.
MBD算法通过给定的系统模型和1个或多个观测值来计算诊断. 目前用于解决单个观测下的 MBD 问题的算法有:随机搜索算法[8]、基于编译的算法[9]、基于广度优先搜索的算法[10]、基于可满足性(satisfiability,SAT)问题的算法[11-12]、基于冲突导向的算法[13]等. 事实上,相比于单观测MBD问题,使用关于诊断系统的多个观测值有助于提高诊断过程的效率,因为它们在计算诊断时可以提供更多的诊断系统信息[14].
近年来,已经提出了许多考虑到多观测的基于模型诊断的方法. DC算法[15]旨在计算关于每个观测的每组诊断的所有覆盖集. DC*[16]通过减少冗余诊断的数量来降低DC算法的运行时间. 然而,DC和DC*都不能保证返回最小势的诊断. 蕴含碰集对偶(hitting set dualization,HSD)算法[14]专注于使用蕴含碰集和最大可满足性 [17-18]算法,在诊断和冲突之间计算最小校正集(minimal correction subsets,MCS)[19-20],其效果在注入单故障模型时优于DC和DC*算法. 尽管蕴含碰集对偶算法的性能在大多数情况下优于DC和DC*算法,但当注入更多故障时,它表现出较差的性能. 针对其进行改进的 IHSD算法[21],在推导具有多个观测的诊断时,首次使用了统治组件的概念. One SAT算法[22]将所有观测结果汇编成可满足性公式[23],并使用SAT求解器导出所有组件的健康指定. 基于统治的多观测压缩模型(dominated-based compacted model with multiple observations,D-CMMO)方法[24]通过新型变量映射方法来压缩子系统,并将统治组件编码为硬子句来计算顶层诊断解(top-level diagnosis,TLD)[25]. 作为一种压缩模型的方法,D-CMMO方法利用了系统的结构属性,有效地缩减了MBD问题编码后子句集的规模. 虽然D-CMMO保证返回基数最小的诊断,但它没有考虑故障输出与故障组件数量之间的关系.
本文提出一种基于基数约束的诊断方法CCM,并通过单次入队策略进一步提升MaxSAT求解器的性能,该方法在求解最小势诊断时,能有效减少求解时间. 此外,本文在ISCAS85和ITC99标准测试实例上,分别将CCM方法与D-CMMO方法进行了比较. 实验结果表明,CCM算法有效提高了MBD问题的求解效率.
在本节中,主要介绍基于模型诊断的相关定义及概念. 本文使用标准的基于模型诊断的定义[1]以及最新的参考文献[9,24-25],主要讨论多观测的基于模型诊断问题. 更具体而言,本文针对于计算一个弱故障模型的极小势诊断.
基于模型诊断问题由一个三元组( SD, Comps, Obs)组成,其中SD(system description)表示诊断问题的系统描述,Comps(components)代表组件的集合,Obs(observations) 表示系统输入和系统输出的观测值.
根据SD和Comps,每一个组件可以被定义为是健康的或是故障的. 对于每一个组件c ∈ Comps,如果c是故障的,则Ab(c) = 1;否则 Ab(c) = 0. 假设每一个组件c ∈ Comps都是健康的,记为 ∀c ∈ Comps,Ab(c) = 0,并且观测值是确定的,即没有传感器噪声造成的误差,诊断问题产生于SD和Comps不一致时:
$ SD\wedge Obs\wedge \left\{\neg Ab\left(c\right)|c\in Comps\right\}\models \perp .$
定义1. 诊断[1]. 给定一个诊断问题〈SD, Comps, Obs〉,诊断被定义为一组组件的集合M ⊆ Comps,
$ SD\wedge Obs\wedge \left\{Ab\left(c\right)|c\in M\right\}\wedge \left\{\neg Ab\left(c\right)|c\in Comps\backslash M\right\}\models / \perp . $
定义2. 极小诊断[25]. 一个诊断M是极小子集诊断,当且仅当任意M0 ⊂ M 都不是一个诊断. M是一个极小势诊断,当且仅当对于任意的诊断M0都有 |M0| ≥ |M|.
当对一个诊断问题给定了多于1个观测时,需要返回一组组件的赋值使之能解释全部的观测.
定义3. 多观测诊断[14]. 给当一个多观测的诊断问题 〈SD, Comps, Obs〉,假设每一个组件c∈Comps 都是健康的,记为 ¬Ab(c),一个多观测的诊断被定义为一组组件的子集M⊆ Comps,当
$ S D\wedge \underset{i=1}{\overset{m}{\bigwedge }}{Obs}_{i}\wedge \{Ab\left(c\right)|c\in M \}\wedge \left\{\neg Ab\left(c\right)|c\in Comps\backslash M\right\}\models /\perp . $
许多诊断方法通过将诊断问题编码为MaxSAT来求解诊断,本节将介绍MaxSAT的编码过程.
标准的基于模型诊断问题的编码方法[26]将每一个组件c∈Comps与一个命题范式$ \phi $联系起来,代表了它的正常行为,并且用一个布尔变量Hc来代表c是否为健康的. 将观测值看作一个命题式声明,MaxSAT编码的硬子句部分由具体化式(4)得到:
$ \phi =Obs\wedge \underset{c\in Comps}{\bigwedge }{H}_{c}\Rightarrow {\varphi }_{c}. $
而MaxSAT的软子句部分由所有代表组件健康状况的变量Hc组成. 由于MaxSAT可以求解满足最大权重和的软子句,因此将Hc设置为软子句可以保证得到最大数量健康组件的诊断解,即极小势诊断. 在一组满足$ \varphi $的赋值中,被指派为false的健康变量Hc的集合决定了一个诊断M. 图1给出c17的电路结构.
例如,考虑图1中的基于模型诊断问题,使nand(A, B, C)描述与非门正常行为的命题范式,其中, A和B是与非门的输入,C为与非门的输出. 因此
$ \varphi = \left( {\begin{aligned}&{{i_1} \wedge - {i_2} \wedge {i_3} \wedge {i_4} \wedge - {i_5}} \wedge {{H_{{N_1}}} \Rightarrow nand({i_1},{i_3},{z_1})} \wedge \\ &{{H_{{N_2}}} \Rightarrow nand({i_3},{i_4},{z_2})} \wedge {{H_{{N_3}}} \Rightarrow nand({i_2},{z_2},{z_3})} \wedge \\ &{{H_{{N_4}}} \Rightarrow nand({i_5},{z_2},{z_4})} \wedge {{H_{{N_5}}} \Rightarrow nand({z_1},{z_3},{o_1})} \wedge \\ &{{H_{{N_6}}} \Rightarrow nand({z_3},{z_4},{o_2})}\end{aligned}} \right) . $
软子句由以下部分组成:
$ \varphi ' = \left( {{H_{{N_1}}} \wedge {H_{{N_2}}} \wedge {H_{{N_3}}} \wedge {H_{{N_4}}} \wedge {H_{{N_5}}} \wedge {H_{{N_6}}}} \right) . $
WCNF中的子句cl的权重用ω(cl)表示,我们分别设置硬子句和软子句的权重为:
1)对于$\varphi $中的子句被设置为硬子句,ω(cl) := num(Hc),
2)所有的Hc变量被设置为软子句,ω(cl) := 1,
其中num(Hc)代表健康变量的数量,也就是组件的数量.
电路系统的直接统治者是一个用来约束CNF编码被广泛使用的技术[9,27]. 令o代表一个连接所有系统输出的虚拟节点. 节点v是节点u的统治者如果从u到o的所有路径都通过v[28]. 节点v是u的直接统治者如果u的所有其他统治者也是v的统治者. 一个电路门是被统治节点如果它的直接统治者不是o,否则它不是被统治节点.
如果一个被统治的电路门出现在某个极小势诊断中,那么它可以被它的直接统治者取代[9]. 因此,求解极小势诊断时可以只分析不包括被统治节点的诊断. 这种诊断被称作顶层诊断. 利用系统的结构属性计算顶层诊断是一种可行的方法,这种方法在许多基于SAT的诊断算法中得到了应用[29-31].
定义4. 顶层诊断[25]. 一个极小势诊断是一个顶层诊断如果它不包括被统治的电路门.
以图1为例,由于N1到达系统输出的路径是唯一的,且通过N5,所以N5是N1的统治者. 对于观测{i1,−i2,i3,i4,−i5,o1,o2},N3是一个顶层诊断,因为它不包括任何被统治节点. 通过将被统治组件的健康变量添加到硬子句中(即声明这些组件是健康的),可以计算顶层诊断.
为了简化MBD到MaxSAT的编码过程,缩减被编码的电路门生成的子句的规模,D-CMMO方法[24]对每一个观测构造一个子系统,并利用子系统之间的结构关系压缩电路模型. 压缩后的模型是一个布尔范式,我们通过单次调用MaxSAT求解器即可得到多观测的诊断. 一些曾在D-CMMO中提出的概念如传播边及传播节点,将在以下定义中给出解释.
定义5. 差别输入(DI)[24]. DI(SysInsx, SysInsy),记作Dix,y,是系统输入的一个子集,由SysInsx和SysInsy中不同的变量组成.
例如,给定2组系统输入SysIns1={−i1,i2,i3,−i4,i5}, SysIns2={−i1,i2,−i3,i4,−i5}, DI1,2={i3,i4,i5}.
定义6. 传播边(P-Edges)[24]. 给定一个系统输入i,P-Edges(i)是系统变量的一个子集,代表从i到所有可达的系统输出所经过的边. 给定一个系统输入的子集,记作SubSysIns,P-Edges(SubSysIns)是系统变量的一个子集,代表从i到所有可达的系统输出所经过的边,且 i ∈ SubSysIns.
定义7. 传播节点(P-Nodes)[24]. 给定一个系统输出i,P-Nodes(i)是Comps的一个子集,代表从i到所有可达的系统输出所经过的节点. 给定一个系统输入的子集,记作SubSysIns,P-Nodes(SubSysIns)是系统变量的一个子集,代表从i到所有可达的系统输出所经过的节点,且i ∈ SubSysIns.
例如,考虑图1中的系统变量i1,P-Edges(i1)={i1,z1,o1},P-Nodes(i1)={N1,N5}. 考虑图1中的系统输入的一个子集{i1,i2},P-Edges({i1, i2})={i1,z1,o2,i2,z3,o2},P-Nodes({i1, i2})={N1,N3,N5,N6}.
在将MBD问题编码为MaxSAT时,D-CMMO方法利用定义4~6来简化电路模型. 图2展示了第1组观测和第N组观测之间的差别,图2(a)展示了与第1组观测匹配的系统变量的整型数;图2(b)展示了与第N组观测所匹配的系统变量的整型数,不同的变量代表了不同的整型数.
式(7)列出了利用简化电路模型得到的系统描述的命题逻辑范式. 如式(7)中所示,变量的匹配过程记为VarMapping,工作如下:对于图2(a),我们将组件或线路相应地匹配为一个新的整型数并构建第1个子系统. 对于图2(b),我们计算DI(SySIns1,SysInsn),记作DI1,n,并且重新为P-Edges(D1,n)中的系统变量赋值一个新的整型数,除了差别变量之外,保留其他变量的匹配. 迭代地,通过编码P-Nodes(DI1,i)中的组件来构建所有子系统. 在图2中,假设SysIns1和SysInsn的差别变量是{cn},在VarMapping的过程中,P-Nodes(cn)中的系统变量被重新赋值了整型数,这些系统变量用虚线代表. 当编码第N个子系统时,只有P-Nodes(cn)中的系统变量和连接它的线路需要被重新编码,也就是说,{N1}和连接它的线路不需要被重新编码.
$ M = \left( {\begin{array}{*{20}{c}}{{H_{{{{N}}_1}}} \Rightarrow nand({a_1},{b_1},{f_1})}& \wedge &{…}& \wedge &{{H_{{N_1}}} \Rightarrow nand({a_1},{b_1},{f_1})}& \wedge &{…} \\ {{H_{{N_2}}} \Rightarrow nand({b_1},{c_1},{g_1})}& \wedge &{…}& \wedge &{{H_{{N_2}}} \Rightarrow nand({b_1},{c_n},{g_n})}& \wedge &{…} \\ {{H_{{N_3}}} \Rightarrow nand({g_1},{d_1},{h_1})}& \wedge &{…}& \wedge &{{H_{{N_3}}} \Rightarrow nand({g_n},{d_1},{h_n})}& \wedge &{…} \\ {{H_{{N_4}}} \Rightarrow nand({g_1},{e_1},{i_1})}& \wedge &{…}& \wedge &{{H_{{N_4}}} \Rightarrow nand({g_n},{e_1},{i_n})}& \wedge &{…} \\ {{H_{{N_5}}} \Rightarrow nand({f_1},{h_1},{j_1})}& \wedge &{…}& \wedge &{{H_{{N_5}}} \Rightarrow nand({f_1},{h_n},{j_n})}& \wedge &{…} \\ {{H_{{N_6}}} \Rightarrow nand({h_i},{i_1},{k_1})}& \wedge &{…}& \wedge &{{H_{{N_6}}} \Rightarrow nand({h_n},{i_n},{k_n})}& \wedge &{…} \end{array}} \right) . $
在编码完系统描述之后,D-CMMO方法将所有的观测编码为硬子句,将所有的健康变量编码为软子句.
算法1总结了利用D-CMMO计算极小势的多观测诊断的方法. 令M代表最终的命题逻辑范式. 在行①中,我们通过将电路系统中的每一个组件和线路匹配为一个整型数得到第1个子系统模型M1,同时将Obs1编码为相应的常量. 行②~⑧中,每一次迭代,算法计算SysIns1和SysInsi的差别变量,然后传播D1i的值得到P-Nodes(D1i)和P-Edges(D1i),将P-Nodes(D1i)中的系统变量编码为新的整型数. 在行⑨⑩中,算法将每一个子系统编码为硬子句. 行⑪~⑮中,根据顶层诊断的概念,算法1将被统治组件编码为硬子句(设定其为健康的),将其他组件编码为软子句. 行⑯⑰中,算法通过调用MaxSAT求解器得到多观测的诊断.
算法1. D-CMMO算法.
输入:系统描述SD,系统组件Comps,观测值Obsi;
输出:诊断Δ.
① M1 ← 将SD,Comps,Obs1编码为硬子句;
② for i ∈ { 2,3,…,m } do
③  找到DI1i的P-Nodes;
④  找到DI1i的P-Edges;
⑤  for c ∈ P-Noeds(DI1i) do
⑥    Mc ← WCNF(c.Fan-in,c.Fan-out, c.GateType); /*将扇入值、扇出值、门 类型编码为WCNF 赋值给Mc*/
⑦   Mi = Mi ∧ Mc;
⑧  end for
⑨  M = M ∧ Mi ∧ HardCls(DI1i);/*将DI1i编码 为硬子句加入到M中*/
⑩ end for
⑪ if c ∈ DominatedComps then
⑫  M = M ∧ HardCls(c);/*如果是统治组件则 编码为硬子句*/
⑬ else
⑭  M = M ∧ SoftCls(c);/*否则编码为软子句*/
⑮ end if
⑯ Δ ← MaxSAT(M);
⑰ return Δ.
文献[25]中的实验表明了基数约束方法在求解基于SAT的诊断时能够提升算法的效率. 本节将介绍CCM方法及该方法为了改进基于MaxSAT的多观测诊断用到的基数约束和假设集的概念.
定义8. 故障输出[32]. 假设电路系统中所有组件都是健康的,对系统输入进行传播得到传播输出,故障输出变量等同于传播输出与系统输出之间变量之差.
例如,给定图1中的一组观测{i1,−i2,i3,i4,−i5,−o1,o2},其中系统输入为{ i1,−i2,i3,i4,−i5},系统输出为{−o1,o2},在全部组件都健康的假设下,传播输出为{o1,o2},故障输出为{o1}.
大量实验表明,在随机注入多故障的复杂电路中,单观测的故障输出数量常常小于多观测诊断的基数. 我们利用故障输出的数量作为多观测诊断的下界,通过引入下界对多观测诊断的基数进行约束,从而缩小诊断的搜索空间,提高复杂诊断问题的搜索效率.
定义9. 假设集[33]. 假设集A是由文字组成的一个集合. 给定一个CNF范式F,基于假设的SAT求解器或返回一个赋值使得F∧A可满足,或返回不可满足.
在求解MaxSAT问题时,基于假设的SAT求解器经常被用来计算最小不可满足子集和最小校正子集. 在基于假设集的SAT求解器中,最广泛使用的处理假设集的技术是将假设集纳入SAT求解器的自身决策中,这些SAT求解器包括MiniSAT[34]和Glucose[35]. 然而,这项技术会带来不必要的代价,这些代价包括在加入被蕴含子句时会回溯到假设集决策之前从而导致重新对假设集进行决策,以及基于CDCL的SAT求解器在单元传播时会重复访问同一子句中的文字O(n2)次. 而通过单次入队的方法可以避免这些代价. 下面将介绍标准的处理假设集的方法和改进的单次入队方法.
令输入范式为F,假设集为A={a1,a2,…,ak}. 在大多数先进的SAT求解器中,支持假设集的技术需要SAT求解器选择ai作为决策文字,当它开始第i个决策层时,其中1≤ i ≤ k. 如果ai已经被赋真值,SAT求解器增加决策层并继续进行第 i+1个决策,即一个空的决策层被加入到路径中. 如果ai已经被赋假值,那么可以说明前n-1个假设决策拥有充分的条件去蕴含¬ai,因此C=(¬a1 ,¬a2,… ,¬ai)是A的冲突子句;否则ai还未被赋值,它会被入队到一个新的决策层中. 当假设集中所有的文字被入队后,SAT求解器能够根据它自身的启发式算法选择决策层文字.
单次入队方法为:当所有的文字在第0决策层中被单元传播后,SAT求解器增加决策层并将假设集中所有的文字入队到第1决策层,之后进行单元传播. 如果在处理假设集时,SAT求解器发现ai已经被赋真值,那么ai在第0决策层已经被弄真,这说明ai已经在路径中的第0层而我们可以跳过对ai的入队操作. 相似的,如果ai已经被赋假值,那么¬ai已经在第0决策层被弄真,所以C=(¬ai)是F的冲突子句并且被SAT求解器返回. 当假设集中的一个新的蕴含单子句被发现后,单次入队方法会回溯到第1决策层,并将蕴含子句加入到第1决策层的末尾,从而避免重新赋值假设集的代价. 因为假设集文字在单元传播之前被赋值,所以假设集中的否定文字不会被频繁替换到子句的看守列表中,从而避免了相同子句中的文字被重复访问的情况. 实验结果表明,单次入队方法比标准方法更能提升MaxSAT求解器的效率,并且能够在相同的时间限制内求解出更多的用例.
算法2. CCM算法.
输入:系统描述SD,系统组件Comps,观测值Obsi;
输出:诊断Δ.
① M1 ← 将SD,Comps,Obs1编码为硬子句;
② for i ∈ { 2,3,…,m } do
③  找到DI1i的P-Nodes;
④  找到DI1i的P-Edges;
⑤  传播Obsi的系统输入得到故障输出;
⑥  for c ∈ P-Noeds(DI1i) do
⑦   Mc ← WCNF(c.Fan-in,c.Fan-out, c.GateType);/*将扇入值、扇出值、门类 型编码为WCNF赋值给Mc*/
⑧   Mi = Mi ∧ Mc;
⑨  end for
⑩  M = M ∧ Mi ∧ HardCls(DI1i) ∧ Constraint(max(Faultouts));/*将DIi1编码 为硬子句加入到M中,另外加入基数约 束对M进行限制*/
⑪ end for
⑫ if c ∈ DominatedComps then
⑬  M = M ∧ HardCLs(c);/*如果是统治组件则 编码为硬子句*/
⑭ else
⑮  M = M ∧ SoftCls(c);/*否则编码为软子句*/
⑯ end if
⑰ Δ ← reinforced_MaxSAT(M);/*使用改进的 MaxSAT求解器搜索诊断解*/
⑱ if |Δ| = max(Faultouts)/*当诊断解的基数和故 障输出数量相同时,进行验证*/
⑲  for i ∈ { |Δ|-1,|Δ|-2, …,0 }
⑳    Ωi ← SAT( Mhard ∧ Comps ∧ Constraint(i) );    /*调用SAT求解器继续向下搜索*/
㉑   if unsatifiable ∈ Ωi
㉒    return Ωi+1;
㉓   end if
㉔  end for
㉕ end if
㉖ return Δ.
具体的CCM方法如算法2所示,其中被改进的地方为行⑤⑩,⑰~㉔. 在行①中,通过将电路系统中的组件和线路匹配为整型数得到子系统模型M1. 行②~⑨中,迭代计算SysIns1和SysInsi的差别变量,得到P-Nodes(D1i)和P-Edges(D1i),编码为新的整型数,并对每组观测计算其故障输出. 在行⑩⑪中,将子系统编码为硬子句,同时将最高故障输出作为基数约束加入到硬子句中,其中,基数约束采用Totalizer[36]的编码方法. 在行⑫~⑯中,将被统治组件编码为硬子句(设定其为健康的),将其他组件编码为软子句. 行⑰中,采用单次入队方法对MaxSAT求解器进行改进后,通过调用MaxSAT求解器得到多观测的诊断. 在行⑱之后,加入验证:如果得到的多观测诊断基数等于故障输出最大值,则调用SAT求解器继续向下搜索,直至SAT求解器返回unsatisfiable,则极小势诊断为SAT最后一次的返回结果Ωi+1.
在本节中,我们将CCM方法与目前最好的处理多观测MBD问题的方法D-CMMO[24]进行了对比. 在编码为MaxSAT后求解诊断问题时,选择与D-CMMO相同的MaxSAT求解器RC2[14],并且使用单次入队方法对RC2进行了改进,其中,RC2是2018年的MaxSAT评估中加权表现最好的MaxSAT求解器. 实验建立在ISCAS85基准用例[37]和ITC99基准用例[26]上,这2组诊断用例也在文献[14, 24, 38]中使用. 本文使用文献[24]中提及的方法生成测试用例,即对于每一个电路,通过建立3种故障模型来评估实验,分别为:固定为0(Stack-At-0)、固定为1(Stack-At-1)和翻转(FLIP)等故障. 对于ISCAS85基准用例,在每种故障模型上分别生成330个故障电路结构,对于ITC99基准用例,在每种故障模型上分别生成810 个故障电路结构. 在注入故障时,随机选择K个组件注入故障,且K的范围为10~50. 实验在Ubuntu 20.04.5 LTS和11th Gen Intel® CoreTM i7-11700KF@3.60 GHz × 2,12 GB RAM上进行. 图3~5分别给出D-CMMO方法和CCM方法在3种故障模型下,求解ISCAS85基准用例时,得到一个极小势诊断解的运行时间.
如图3~5所示,在实验中,设置MaxSAT求解时间的上限为200 s. 对于大多数测试用例,D-CMMO和CCM可以在200 s内通过MaxSAT求解器返回诊断结果. 并且对于大多数测试实例,CCM的运行时间要小于D-CMMO,3种故障模型中,CCM运行时间较少,所占的比例分别为82.5%,80.9%,60.9%. 在平均情况下,CCM求解效率相比D-CMMO提升64.5%. 图6~8分别显示了在3种故障模型下,D-CMMO和CCM求解ITC99用例时,得到一个极小势诊断所用的时间.
如图6~8所示,在坐标轴上的点表示一方在给定时间内无法求解的一些测试用例. 使用CCM和D-CMMO不能得到一个解的用例个数分别为117和144. 在求解实例的个数上,CCM优于D-CMMO. 除此之外,在求解效率上,CCM的运行速度相比D-CMMO平均提升92.8%.
在ISCAS85和ITC99实例上的详细实验结果分别如表1和表2所示.
在2组表中第5~7列显示在不同的故障模型下, CCM求解诊断时所用时间比D-MMO短的实例个数(CCM wins),当2种方法的运行时间都超过时间限制时,用例结果不计入任何一方数据. 从表1和表2可以看出,对每一个电路进行诊断搜索时,CCM都是可行的,且求解结果显示,相比于D-CMMO,CCM具有明显优势. 特别是在c499电路上,CCM在3种故障模型下的测试结果都远超D-CMMO,94.9%的实例的实验结果优于D-CMMO.
目前,很多基于SAT的多观测MBD问题把MaxSAT编码作为分析多观测MBD问题的一个基本步骤. 本文在面向统治组件的研究基础上,提出一种基于基数约束的求解方法CCM,显著缩小了MBD问题的搜索范围,进而降低了MaxSAT问题的求解难度和求解诊断的时间. 本文提出了2种方法用于提高CCM的效率. 首先,根据电路系统的结构特性,通过传播系统输入得到诊断解的上界,作为硬子句加入到MaxSAT编码中. 其次,利用单次入队的方法避免对假设集重复赋值以及对子句中的文字重复访问的代价,从而优化MaxSAT求解器,提高求解的效率. 实验结果表明,通过加入基数约束以及单次入队策略,能有效减少MaxSAT求解器搜索诊断的难度,进而提高求解诊断的效率. CCM在ISCAS85和ITC99基准用例上求解高效,相对于D-CMMO在求解效率上分别提升64.5%和92.8%. 在未来研究中,将探索强故障模型下的CCM的扩展算法.
作者贡献声明:青杨提出了算法思路和实验方案、负责论文的撰写与修订;欧阳丹彤确定综述选题、指导和督促论文的撰写与修改;周慧思负责文献资料的整理与分析以及部分图表的绘制;张立明提出论文指导意见与修改方案.

参考文献 引证文献
排序方式:
1
Reiter R. A theory of diagnosis from first principles[J]. Artificial Intelligence, 1987, 32(1): 57−95
2
Friedrich G, Gottlob G, Nejdl W. Hypothesis classification, abductive diagnosis and therapy[C]//Proc of the Expert Systems in Engineering Principles and Applications. Berlin: Springer, 1990: 69–78
3
Feldman A, Pill I, Wotawa F, et al. Efficient model-based diagnosis of sequential circuits[C]//Proc of the 34th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2020: 2814–2821
4
Struss P, Price C. Model-based systems in the automotive industry[J]. AI Magazine, 2004, 24(4): 17−34
5
Ardissono L, Console L, Goy A, et al. Cooperative model-based diagnosis of web services[C]//Proc of the 16th Int Workshop on Principles of Diagnosis. Paris: CEUR-WS, 2005: 125–130
6
Jannach D, Schmitz T. Model-based diagnosis of spreadsheet programs: A constraint-based debugging approach[J]. Automated Software Engineering, 2016, 23(1): 105−144
7
Jose M, Majumdar R. Cause clue clauses: Error localization using maximum satisfiability[J]. ACM SIGPLAN Notices, 2011, 46(6): 437−446
8
Feldman A, Provan G M, Van Gemund A J C. Computing minimal diagnoses by greedy stochastic search[C]//Proc of the 23rd AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2008: 911–918
9
Siddiqi S A, Huang Jinbo. Hierarchical diagnosis of multiple faults[C]//Proc of the 20th Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2007: 581–586
10
Jannach D, Schmitz T, Shchekotykhin K M. Parallelized hitting set computation for model-based diagnosis[C]//Proc of the 29th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2015: 1503–1510
11
Ansótegui C, Bonet M L, Levy J. SAT-based MaxSAT algorithms[J]. Artificial Intelligence, 2013, 196(1): 77−105
12
Feldman A, Provan G, de Kleer J. Solving model-based diagnosis problems with Max-SAT solvers and vice versa[C]//Proc of the 21st Int Workshop on Principles of Diagnosis. New York: PHM Society, 2010: 185–192
13
Stern R T, Kalech M, Feldman A. Exploring the duality in conflict-directed model-based diagnosis[C]//Proc of the 26th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2012: 828–834
14
Ignatiev A, Morgado A, Weissenbacher G, et al. Model-based diagnosis with multiple observations[C]//Proc of the 28th Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2019: 1108–1115
15
Lamraoui S, Nakajima S. A formula-based approach for automatic fault localization of imperative programs[C]//Proc of the 16th Int Conf on Formal Engineering Methods. Berlin: Springer, 2014: 251–266
16
Lamraoui S, Nakajima S. A formula-based approach for automatic fault localization of multi-fault programs[J]. Journal of Information Processing, 2016, 24(1): 88−98
17
Narodytska N, Bacchus F. Maximum satisfiability using core-guided MaxSAT resolution[C]//Proc of the 28th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2014: 2717–2723
18
Cai Shaowei, Lei Zhendong. Old techniques in new ways: Clause weighting, unit propagation and hybridization for maximum satisfiability[J]. Artificial Intelligence, 2020, 287: 103354−103354
19
Marques-Silva J, Heras F, Janota M, et al. On computing minimal correction subsets[C]//Proc of the 23rd Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2013: 615–622
20
Previti A, Mencía C, Järvisalo M, et al. Premise set caching for enumerating minimal correction subsets[C]//Proc of the 32nd AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2018: 6633–6640
21
Zhou Huisi, Ouyang Dantong, Zhang Liming, et al. Model-based diagnosis with improved implicit hitting set dualization. Forthcoming[J]. Applied Intelligence, 2022, 52(2): 2111−2118
22
Kalech M, Stern R, Lazebnik E. Minimal cardinality diagnosis in problems with multiple observations[J]. Diagnostics, 2021, 11(5): 780−780
23
Gu Jun, Purdom P W, Franco J, et al. Algorithms for the Satisfiability Problem[M]//Handbook of Combinatorial Optimization. Berlin: Springer, 1999: 379–572
24
Zhou Huisi, Ouyang Dantong, Zhao Xiangfu, et al. Two compacted models for efficient model-based diagnosis[C]//Proc of the 34th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2022: 3885−3893
25
Metodi A, Stern R, Kalech M, et al. A novel SAT-based approach to model based diagnosis[J]. Journal of Artificial Intelligence, 2014, 51(1): 377−411
26
Marques-Silva J , Mikoláš J, Ignatiev A , et al. Efficient model based diagnosis with maximum satisfiability[C]//Proc of the 24th Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2015: 1966−1972
27
Amit M, Roni S, Meir K, et al. Compiling model-based diagnosis to Boolean satisfaction[C]//Proc of the 26th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2012: 793−799
28
Thomas L, Robert E T. A fast algorithm for finding dominators in a flowgraph[J]. ACM Transactions Programming Languages and Systems, 1979, 1(1): 121−141
29
刘梦,欧阳丹彤,刘伯文,等. 结合问题特征的分组式诊断方法[J] 电子学报,2018,46(3):589−594
Liu Meng, Ouyang Dantong, Liu Bowen, et al. Grouped diagnosis approach using the feature of problem[J]. Acta Electronica Sinica, 2018, 46(3): 589−594 (in Chinese)
30
欧阳丹彤,刘伯文,刘梦,等. 结合电路结构基于分块的诊断方法[J] 电子学报,2018,46(7):1571−1577
Ouyang Dantong, Liu Bowen, Liu Meng, et al. A block-based diagnostic method combing with the circuit structure[J]. Acta Electronica Sinica, 2018, 46(7): 1571−1577 (in Chinese)
31
周慧思,欧阳丹彤,田鑫亮,等. 基于模型诊断的一种新编码方法[J] 计算机研究与发展,2023,60(1):95−102
Zhou Huisi, Ouyang Dantong, Tian Xinliang, et al. A novel encoding for model based diagnosis[J]. Journal of Computer Research and Development, 2023, 60(1): 95−102 (in Chinese)
32
Siddiqi S A, Huang Jinbo. Sequential diagnosis by abstraction[J]. Journal of Artificial Intelligence Research, 2011, 41: 329−365
33
Eèn N, Sörensson N. Temporal induction by incremental SAT solving[J]. Electronic Notes in Theoretical Computer Science, 2003, 89(4): 543−560
34
Eèn N, Sörensson N. An extensible SAT-solver[C]//Proc of the 6th Theory and Applications of Satisfiability Testing. Berlin: Springer, 2004: 502−518
35
Audemard G, Lagniez J M, Simon L. Improving Glucose for incremental SAT solving with assumptions: Application to MUS extraction[C]//Proc of the 16th Theory and Applications of Satisfiability Testing. Berlin: Springer, 2013: 309–317
36
Ogawa T, Liu Yangyang, Hasegawa R, et al. Modulo based CNF encoding of cardinality constraints and its application to MaxSAT solvers[C]//Proc of the 25th IEEE Int Conf on Tools with Artificial Intelligence. Piscataway, NJ: IEEE, 2013: 9−17
37
Brglzz F, Fujtwara H. A neutral netlist of 10 combinational benchmark circuits and a target translator in FORTRAN[J/OL]. IEEE International Symposium on Circuits and Systems. 1985[2023-03-20].https://www.researchgate.net/publication/239562831_A_neutral_netlist_of_10_combinational_circuits_and_a_target_translator_in_fortran
38
Siddiqi S A. Computing minimum-cardinality diagnoses by model relaxation[C]//Proc of the 22nd Int Joint Conf on Artificial Intelligence. Palo Alto, CA : AAAI, 2011: 1087–1092
2025年第62卷第2期
127
48
0
引用本文
BibTeX
文章信息
doi: 10.7544/issn1000-1239.202330546
  • 接收时间:2023-06-24
  • 首发时间:2026-11-10
  • 出版时间:2025-02-01
补充材料
相关文章
文章信息
作者
出版历史
  • 收稿日期:2023-06-24
  • 修回日期:2023-12-07
基金
作者信息
    吉林大学计算机科学与技术学院 长春 130012
    符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012

通讯作者:

张立明()
参考文献
分享链接
https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202330546
分享至
全文二维码

扫描看全文

引用本文
BibTeX
本文的引用情况
2种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏