推荐星级：

结合电路结构基于分块的诊断方法

更新时间：2019-12-24 17:52:21 大小：806K 上传用户：守着阳光1985 查看TA发布的资源 标签：电路结构 下载积分：1分评价赚积分（如何评价?）打赏收藏评论(0) 举报

资料介绍

基于模型的诊断问题在人工智能领域内一直备受关注,将诊断问题转换成SAT(Satisfiable)问题成为解决基于模型诊断问题的一个重要方法.基于目前高效诊断方法 LLBRS-Tree(Last-Level Based on Reverse Search-Tree)的研究,本文提出电路分块诊断方法 ACDIAG(Abstract Circuit Diagnosis)方法,对电路进行分块来缩减电路规模,利用LLBRS-Tree方法对分块后抽象电路求得极小块诊断解;提出诊断解拓展方法,结合分块后电路结构特征对每个极小块诊断解进行直接扩展得到极小诊断解,避免对抽象电路还原后才能得到所有解的问题.

部分文件列表

文件名	大小
结合电路结构基于分块的诊断方法.pdf	806K

立即下载

【关注视频号领20积分】【关注公众号立即送20积分】

部分页面预览

（完整内容请下载后查看）

Vol． 46 No． 7

Jul． 2018

第

期

电

子

学

报

2018

ACTA ELECTRONICA SINICA

年

月

结合电路结构基于分块的诊断方法

1，2

，，，，

欧阳丹彤刘伯文刘梦张立明张永刚

( 1．

，

吉林大学计算机科学与技术学院吉林长春

130012;

2．

，

吉林大学符号计算与知识工程教育部重点实验室吉林长春

130012)

，

基于模型的诊断问题在人工智能领域内一直备受关注将诊断问题转换成

SAT( Satisfiable)

摘

要

问题成为

．

解决基于模型诊断问题的一个重要方法基于目前高效诊断方法

LLBRS-Tree( Last-Level Based on Reverse Search-Tree)

，

的研究本文提出电路分块诊断方法

ACDIAG( Abstract Circuit Diagnosis)

，，

方法对电路进行分块来缩减电路规模利用

LLBRS-Tree

; ，

方法对分块后抽象电路求得极小块诊断解提出诊断解拓展方法结合分块后电路结构特征对每个极小

，

块诊断解进行直接扩展得到极小诊断解避免对抽象电路还原后才能得到所有解的问题

．

; SAT

; ;

问题枚举树抽象

关键词

中图分类号

URL: http: / /www． ejournal． org． cn

基于模型诊断

TP306

文章编号

0372-2112 ( 2018) 07-1571-07

文献标识码

DOI: 10． 3969 /j． issn． 0372-2112． 2018． 07． 005

电子学报

A Block-Based Diagnostic Method Combining with the Circuit Structure

1，2

OUYANG Dan-tong ，LIU Bo-wen ，LIU Meng ，ZHANG Li-ming ，ZHANG Yong-gang

( 1． College of Computer Science and Technology，Jilin University，Changchun，Jilin 130012，China;

2． Ministry Education Key Laboratory of Symbolic Computation and Knowledge Engineering，Jilin University，Changchun，Jilin 130012，China)

Abstract: Model-based diagnosis problem has been attracting much attention in the field of artificial intelligence． It is

an important technique for solving model-based diagnosis problem by converting diagnosis problem to SAT． Based on the re-

search of LLBRS-Tree，this paper proposes an ACDIAG method． Firstly，the circuit blocking method is used to block the cir-

cuit via circuit structure so as to downscale circuit． Then，minimal block diagnoses are acquired on the abstract circuit after

blocking via LLBRS-Tree． Secondly，diagnosis extending method is given to extend minimal block diagnoses to obtain other

diagnoses directly via circuit structure． It avoids the drawback that extending diagnoses need to restore the abstract circuit．

Key words: model-based diagnosis; SAT problem; enumeration tree; abstract

［6］

．

，

完备的极小碰集求解方法随问题规模上升

的方法

引言

．

复杂度会以指数级增长目前效率较高的方法主要包

［7］

( Model-Based Diagnosis，MBD)

基于模型的诊断

问

、

括姜云飞等学者提出的布尔代数方法

基于并行的

［8］

，

题是人工智能领域内的一个重要问题推动着人工智

、

碰集算法

结合特征学习的粒子群求解极小碰集方

［1］

［9］

［10］

．

MBD ，

直接求解难度较大著名学

能的发展

早期由于

de Kleer ，

提出的冲突集概念设计了一

、

．

等

法

基于连接关系的分布式求解方法

［2］

Reiter

者

结合

，

求解极小冲突集以及求解极小碰集都是

问题

［3］

，

个高效的诊断求解方法

首先求解电路的所有极小

MBD

，

随着对

问题更深入的研究与计算机硬件的发展

MBD

，，

冲突集然后对这些极小冲突集求解极小碰集并证明

，

许多学者为避免这两步求解过程对直接求解

方

［11］

．

了这些极小碰集是整个电路的所有极小诊断解国内

，

SAT

法进行了研究

其中将诊断问题转换为

问题是

问题是第

也是人工智能领域内的

SAT

［12］

外许多学者对求解极小冲突集与极小碰集的算法进行

MBD

． SAT

直接求解

一个被证明的

一个重要研究问题之一近年来在

，SAT

问题的重要方法之一

［4］

［13］

．

了研究早期学者提出使用定理证明器的方法与归

，

完全问题

［5］

，．

结方法求解极小冲突集但是效率较低随后国内学

．

，

竞赛的鼓励

SAT

者提出了结合枚举树与电路逻辑关系的利用

求解

，

SAT

下

求解技术的发展引人注目现在的

求解器

: 2016-12-29;

: 2017-09-07; :

责任编辑孙瑶

收稿日期

修回日期

基金项目国家自然科学基金

( No． 61672261，No． 61502199，No． 61402196，No． 61373052) ;

( No． LY16F020004)

浙江省自然科学基金

1572

2018

年

电

子

学

报

［14，15］

．

MBD

Tree) ，

中的每个结点结点中的元件假设为故障并将其

已经可以较快地处理更大规模的实例

将

问

SAT

，

问题进行求解能够克服诊断问题复杂

．

余元件都置为正常

题转换为

［16］

，

性不断增加的难题因而得到众多学者的广泛关注

．

( 2)

把步骤中的对应单元子句加入到电路的

，

近年来国内外学者开始研究结合结构信息对基

CNF

，

中调用

SAT CNF

求解器对电路

．

进行一致性检测

SAT ．，Smith

求解诊断的方法进行优化起初

，，．

若可满足则该结点是一个诊断解把此诊断解保存检

于

等学者

SAT

，

问题结合电路中自由输入变

SE-Tree

，

中所有结点后最后得到所有极小诊

将诊断问题转换成

测完

SAT

，．

的搜索空间提高诊断效率随

．

量的结构信息压缩

断解

［17］

，Siddiqi

后

等学者提出结合统治关系进行抽象的方

2. 3 LLBRS-Tree

方法

在基于反向搜索的有解无解剪枝

MBD，

，

对抽象后的电路进行诊断得到诊断解后

法求解

LLBRS-Tree

方法

．

对每一个抽象电路还原后分别求解赵相福等学者提

，，

中不仅剪掉是诊断解的结点而且还对不是诊断解的

［18］

SAT

CSSE-Tree

出了基于枚举树并利用

求解器的

方

．

冗余结点也进行剪枝在下面介绍有解剪枝与无解剪

［19］

． Amit Metodi

Section

法求解诊断问题

提出

概念并结

．

枝及反向搜索遍历的相关定义

［20］

Cone

，

的作用从电路结构的角度对基于

SAT

的诊断

，

反向搜索针对一棵枚举树当枚举树

合

定义

，

进行了优化缩减了诊断问题的求解时间

．

，

的层数已经给定的情况下称从枚举树的最后一层向

，

周建华等对问题结构特征进行了研究对

CSSE-

．

枚举树的根结点搜索的过程为反向搜索

Tree

，

方法进行改进提出了有解空间与无解空间剪枝方

SAT

在调用

求解器来判断当前元件集合是否为诊

［20］

( LLBRS-Tree

) ，

方法既结合了枚举树和诊断问题

，LLBRS-Tree

法

断解的时候

先对比较长的组件集合进行求解使得求解的

SAT

方法结合反向搜索遍历方法

，

的特征又利用了

SAT

，

求解器的特点是一种求解效率

，

CNF

问

． : ，

较高的方法该文提出了两个优化策略第一利用反向

，

．

求解时所耗费的时间

题的规模较小进而减少

，

搜索的思想对部分集合枚举树从底层结点到根结点

LLBRS-tree

算法步骤如算法所示

．

; ，

进行深度优先搜索第二结合非诊断解结点的祖先结

LLBRS-tree

算法

( ) ，

点真子集不是解的思想进行无解剪枝

．

LLBRS-Tree

，

方法充分研究基础上借鉴

本文在对

现有电路抽象方法结合电路结构提出一种新的分块

LLBRS-Tree

step 1.

step 2.

step 3.

step 4.

step 4a．

．

生成集合枚举树

，

，，

寻找当前未判断的最左结点若未找到跳转

step 6．

．

抽象策略将电路进行分块后利用

方法先

求解抽象电路的极小块诊断解并提出了一种由极小

块诊断解快速拓展得到原电路所有极小诊断解的方

SAT

．

求解器检查结点的一致性

调用

若可满足

该候选解判断其极小性若极小则删去原诊断解集合中该候

，

选解的所有超集然后该候选解加入诊断解集合

．

．，

法结合电路结构与电路信号的传递关系快速拓展得

step 4b．

step 5.

，，

使用有解剪枝策略找到其父结点跳转

step 3．

，

到极小诊断解避免了对抽象电路还原后才能得到所

，，，

若不可满足使用无解剪枝策略跳过祖先结点找到下一个

．

有极小诊断解的问题

，

要访问的结点跳转

step 3．

step 6.

．

返回诊断解集合

基于反向搜索的有解无解剪枝方法

2. 1 MBD

问题

电路分块诊断方法

［3］

DS = ( SD，

诊断系统被定义为三元组

定义

COMPS，OBS) ，

其中

: SD

，COMPS

LLBRS-Tree

表示系统描述

表示系

上一部分介绍了

方法求解极小诊断基

算法基础上提出了电路分

LLBRS-Tree

，

本思想本章在

LLBRS-Tree

，OBS

．

表示系统观测集

统元件集

［3］

ACDIAG，

此方法在

COMPS，

块诊断方法

方法基础

定义

设元件集的一个子集 Δ 

．

上加入了电路规模缩减方法和诊断解扩展方法下面

AB( c)

c ，

为真表示元件故障如果

OBS

∪

ACDIAG

，、

方法的基本思想相关定义定理及其证

{ － AB( c) | c COMPS －

的则 Δ 是关于

}

{

( SD，COMPS，OBS)

AB( c) | c

}

∈Δ 是可满足

的基于一致性诊断

给出

明和分析

3. 1

∈

Δ ∪

．

，

．

， '

称 Δ 是极小一致性诊断当任意 Δ Δ 不是基于

电路分块方法

．

一致性诊断

2. 2

电路分块方法结合电路结构特征对电路进行分

，．

块从而实现缩减求解电路的规模下面介绍该方法相

SAT

结合枚举树调用

的诊断方法

．

SAT

关概念和思想

使用

求解器和枚举树来求解极小诊断的基本

定义

基本元件如果元件输入端个数小于等

步骤

［21］

2，

称此元件为基本元件

．

( 1)

( Set-Enumeration-Tree，SE-

于

检测集合枚举树

全部评论(0)

暂无评论

评论赚积分>>

上传资源上传优质资源有赏金

结合电路结构基于分块的诊断方法

资料介绍

部分文件列表

部分页面预览

相关下载

全部评论(0)

热门标签

最新上传

热门下载

推荐下载

专栏首页