📄 清华大学学报990203.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0076)http://www.i-power.com.cn/ipower/library/qhdxxb-e/qhdx99/qhdx9902/990203.htm -->
<HTML><HEAD><TITLE>清华大学学报990203</TITLE>
<META content="text/html; charset=gb2312" http-equiv=Content-Type>
<META content="MSHTML 5.00.2314.1000" name=GENERATOR></HEAD>
<BODY bgColor=#ffffff link=#000000>
<TABLE border=0 cellPadding=0 cellSpacing=0 width="90%">
<TBODY>
<TR>
<TD align=middle><A href="http://www.i-power.com.cn/ipower/"><IMG
alt="logo.gif (3178 bytes)" border=0 height=26
src="清华大学学报990203.files/logo.gif" width=174></A></TD>
<TD align=middle><A
href="http://www.i-power.com.cn/ipower/library/qhdxxb-e/index.htm"><STRONG><FONT
face=宋体 size=4>清华大学学报</FONT></STRONG></A><BR><STRONG><FONT face=System
size=4>TSINGHUA SCIENCE AND TECHNOLOGY</FONT></STRONG><BR><FONT face=宋体
size=2>1999年 第4卷 第2期 Vol.4 No.2 1999</FONT></TD>
<TD align=middle><A
href="http://www.i-power.com.cn/ipower/library/index.htm"><IMG
alt="qklogo.gif (1778 bytes)" border=0 height=26
src="清华大学学报990203.files/qklogo.gif" width=96></A></TD></TR>
<TR>
<TD align=middle colSpan=3>
<HR>
</TD></TR></TBODY></TABLE>
<TABLE border=0 cellPadding=0 cellSpacing=0 width="90%">
<TBODY>
<TR>
<TD><FONT size=3>
<P align=center></FONT><STRONG><FONT face="Times New Roman"
size=5>Consistent Algorithm for Multi-value Constraint with <BR>Continuous
Variables*</FONT></STRONG></P>
<P align=center><FONT face="Times New Roman" size=3>CHANG
Tianqing(</FONT><FONT size=3>常天庆</FONT><FONT face="Times New Roman"
size=3>), LI Jingyi(</FONT><FONT size=3>李敬逸</FONT><FONT
face="Times New Roman" size=3>), XU Wensheng(</FONT><FONT
size=3>徐文胜</FONT><FONT face="Times New Roman" size=3>), <BR>XIONG
Guangleng(</FONT><FONT size=3>熊光楞</FONT><FONT face="Times New Roman"
size=3>)</FONT><FONT size=3></P>
<P align=center><FONT face="Times New Roman">Department of Automation,
Tsinghua University, Beijing 100084</FONT></P>
<P align=left><FONT
face="Times New Roman"><STRONG>Abstract</STRONG></FONT> <FONT
face="Times New Roman">Mature algorithms for the Constraint Satisfaction
Problem (CSP) of binary constraint with discrete variables have already
been obtained for the application. For the instance of multi-value
constraint with continuous variables, the approach will be quite different
and the difficulty of settling will aggrandize a lot. This paper presents
the algorithm for realizing global consistency of continuous variable. And
this algorithm can be applied to multi-value constraint. <BR><STRONG>Key
words </STRONG></FONT> <FONT face="Times New Roman">artificial
intelligence; constraint satisfaction problem; consistency
problem</FONT></P>
<P align=left></FONT><STRONG><FONT face="Times New Roman"
size=4>Introduction<BR></FONT><FONT size=3> </FONT></STRONG><FONT
face="Times New Roman" size=3>The Constraint Satisfaction Problem (CSP)
was first developed for settling the constraint between discrete
variables. Many algorithms given out for improving the solving efficiency
of CSP were limited to binary constraint. In product development process
in Concurrent Engineering, we frequently meet with constraints with
multiple continuous variables. Under this situation, new nodus appears in
solving CSP. For example, while figuring out the CSP of binary constraint
with discrete variables, it is relatively simple to find out the value of
these two constrained variables from their limited value sets. And it is
comparatively easy to eliminate redundant values in the value set which
can not satisfy the constraint. So most attention is focused on finding
out the optimal sequence of the variables to be settled during the solving
process. However, under the instance of multi-value constraint with
continuous variables, it is rather difficult to find out the feasible
solution of the variables being constrained. And certain efficient
algorithm dealing with this problem has not been found yet. It is obvious
that how to find out the feasible solution of the variables being
constrained is the foundation of settling CSP and has significant
importance. </FONT><FONT size=3></P>
<P align=left></FONT><STRONG><FONT face="Times New Roman"
size=4>1</FONT><FONT size=4> </FONT><FONT face="Times New Roman"
size=4>Correlative Definition<BR></FONT></STRONG><FONT
size=3> </FONT><FONT face="Times New Roman" size=3><STRONG>Definition 1
(CSP)</STRONG></FONT><FONT size=3> </FONT><FONT face="Times New Roman"
size=3>CSP is a three-tuple problem specified by </FONT><FONT
size=3>（</FONT><FONT face="Times New Roman" size=3>X,D,C</FONT><FONT
size=3>）</FONT><FONT face="Times New Roman" size=3>. It involves a set of
n variables X<SUB>1</SUB>,X<SUB>2</SUB>,</FONT><FONT size=3>…</FONT><FONT
face="Times New Roman" size=3>,X<SUB>n</SUB>(each variable X<SUB>i</SUB>
has its domain D<SUB>i</SUB>) and a set of m constraints
C<SUB>1</SUB>,C<SUB>2</SUB>,</FONT><FONT size=3>…</FONT><FONT
face="Times New Roman" size=3>,C<SUB>m</SUB>. Each constraint can be
divided into two parts: variable set
V(C<SUB>i</SUB>)={X<SUB>i1</SUB>,</FONT><FONT size=3>…</FONT><FONT
face="Times New Roman" size=3>,X<SUB>ij</SUB>} and relationship set
R(C<SUB>i</SUB>)=R{X<SUB>i1</SUB>,</FONT><FONT size=3>…</FONT><FONT
face="Times New Roman" size=3>,X<SUB>ij</SUB>}</FONT><IMG
alt="wpe3A.jpg (744 bytes)" height=16 src="清华大学学报990203.files/9902031.jpg"
width=17><FONT face="Times New Roman" size=3>D<SUB>i1</SUB>×</FONT><FONT
size=3>…</FONT><FONT face="Times New Roman" size=3>×D<SUB>ij</SUB>. All
solutions of the constraint network can be represented as</FONT></P><FONT
size=3>
<P align=center><IMG alt="3t-1.gif (1115 bytes)" height=57
src="清华大学学报990203.files/3t-1.gif" width=293></P>
<P align=left><FONT face="Times New Roman">Here</FONT><IMG
alt="3t-2.gif (788 bytes)" height=33 src="清华大学学报990203.files/3t-2.gif"
width=281><FONT face="Times New Roman">, <IMG alt="wpe3B.jpg (796 bytes)"
height=20 src="清华大学学报990203.files/9902032.jpg" width=19> is the expansion
of <IMG alt="wpe3C.jpg (853 bytes)" height=25
src="清华大学学报990203.files/9902033.jpg" width=27>} represents the projection
of variable subset U={U<SUB>1</SUB>,</FONT>…<FONT
face="Times New Roman">,U<SUB>m</SUB>} on relationship k. The objective is
to determine whether this problem has solution, find out its single or
multiple solutions and solve correlative problems.<BR></FONT> <FONT
face="Times New Roman">Traditional CSP mainly discusses the problem of
discrete variable with finite value domain under binary constraint. The
corresponding content discussed in this paper is about continuous variable
with a series of intervals. Constraints are not limited to binary
constraint.<BR></FONT> <FONT face="Times New Roman">Backtracking is the
basic method of solving CSP. In order to reduce the time of backtracking,
preprocessing is always needed before backtracking. The basic principle of
preprocessing is to eliminate those elements that can not be the solution
in the value domain of the variables. Generally we use global consistency
and local consistency to represent the degree of simplicity of value
domain.<BR></FONT> <FONT face="Times New Roman"><STRONG>Definition 2
(Local Consistency)</STRONG></FONT> <FONT face="Times New Roman">Suppose
C<SUB>j</SUB>(j=1,</FONT>…<FONT face="Times New Roman">,m) is a constraint
which has direct link with variable X<SUB>i</SUB>. If for each value
x<SUB>i</SUB> in value domain of variable X<SUB>i</SUB>, we can always
find out a group of variable values (x<SUB>1</SUB></FONT>∈<FONT
face="Times New Roman">X<SUB>1</SUB>,</FONT>…<FONT
face="Times New Roman">,x<SUB>i</SUB></FONT>∈<FONT
face="Times New Roman">X<SUB>i</SUB>,</FONT>…<FONT
face="Times New Roman">,x<SUB>n</SUB></FONT>∈<FONT
face="Times New Roman">X<SUB>n</SUB>) which can satisfy constraints
C<SUB>j</SUB>(j=1,</FONT>…<FONT face="Times New Roman">,p,p</FONT>≤<FONT
face="Times New Roman">m), then variable X<SUB>i</SUB> is local
consistent. And if all variables are local consistent, then the
corresponding CSP is local consistent.<BR></FONT> <FONT
face="Times New Roman">Generally speaking, a CSP has not eliminated all
redundant portions when it reaches local consistency. Global consistency
has to be satisfied.<BR></FONT> <FONT
face="Times New Roman"><STRONG>Definition 3 (Global
Consistency)</STRONG></FONT> <FONT face="Times New Roman">If for each
value x<SUB>i</SUB> in value domain of variable X<SUB>i</SUB>, we can
always find out a group of variable values (x<SUB>1</SUB></FONT>∈<FONT
face="Times New Roman">X<SUB>1</SUB>,</FONT>…<FONT
face="Times New Roman">,x<SUB>i</SUB></FONT>∈<FONT
face="Times New Roman">X<SUB>i</SUB>,</FONT>…<FONT
face="Times New Roman">,x<SUB>n</SUB></FONT>∈<FONT
face="Times New Roman">X<SUB>n</SUB>) which can satisfy all constraints
C<SUB>j</SUB>(j=1,</FONT>…<FONT face="Times New Roman">,m) of CSP, then
variable X<SUB>i</SUB> is global consistent. If all variables are global
consistent, then the corresponding CSP is global
consistent.<BR></FONT> <FONT face="Times New Roman">The consistency of
CSP can be realized through the following algorithm.<BR></FONT> <FONT
face="Times New Roman"><STRONG>Algorithm 1 (Consistency algorithm of
CSP)</STRONG><BR></FONT> <FONT
face="Times New Roman">BEGIN<BR></FONT> <FONT
face="Times New Roman">WHILE changed=TRUE DO<BR></FONT> <FONT
face="Times New Roman">changed=FAIL<BR></FONT> <FONT
face="Times New Roman">FOR j=1 TO r by 1 DO<BR></FONT> <FONT
face="Times New Roman">FOR i=1 TO n by 1 DO<BR></FONT> <FONT
face="Times New Roman">Compute the consistent interval of variable
X<SUB>i</SUB> under the constraint group C<SUB>j</SUB>(j=p,</FONT>…<FONT
face="Times New Roman">,q,<BR></FONT> <FONT
face="Times New Roman">1</FONT>≤<FONT
face="Times New Roman">p</FONT>≤<FONT
face="Times New Roman">q</FONT>≤<FONT face="Times New Roman">m) while the
value domains are (X<SUB>1</SUB>,</FONT>…<FONT
face="Times New Roman">,X<SUB>i-1</SUB>,X<SUB>i+1</SUB>,</FONT>…<FONT
face="Times New Roman">,X<SUB>n</SUB>).IF the intervals
of<BR></FONT> <FONT face="Times New Roman">X<SUB>i</SUB> are
changed THEN changed=TRUE<BR></FONT> <FONT
face="Times New Roman">Use new interval to substitute the
former.<BR></FONT> <FONT face="Times New Roman">END/* of WHILE
*/<BR></FONT> <FONT face="Times New Roman">END<BR></FONT> <FONT
face="Times New Roman">This algorithm divides the constraints into r
groups. If r=m, each group has only one constraint, the algorithm can
reach local consistency. If r=1, then the algorithm can reach global
consistency. Computing the consistent interval is the core of the
algorithm. This paper separately deals with it as one problem.
<BR></FONT> <FONT face="Times New Roman"><STRONG>Problem
1</STRONG></FONT> <FONT face="Times New Roman">For n variables
X<SUB>i</SUB>(i=1,</FONT>…<FONT face="Times New Roman">,n)</FONT>，<FONT
face="Times New Roman">their respective value domains are
a<SUB>i</SUB></FONT>≤<FONT
face="Times New Roman">X<SUB>i</SUB></FONT>≤<FONT
face="Times New Roman">b<SUB>i</SUB>, their corresponding constraints are
c<SUB>j</SUB>(X<SUB>i</SUB>,</FONT>…<FONT
face="Times New Roman">,X<SUB>n</SUB>)(j=1,</FONT>…<FONT
face="Times New Roman">,p). How to seek the consistent interval
</FONT>［<IMG alt="wpe3D.jpg (826 bytes)" height=27
src="清华大学学报990203.files/9902034.jpg" width=32><FONT
face="Times New Roman">,</FONT><IMG alt="wpe3E.jpg (855 bytes)" height=27
src="清华大学学报990203.files/9902035.jpg" width=33>］<FONT
face="Times New Roman">(k</FONT>≥<FONT face="Times New Roman">1) of
X<SUB>n</SUB> corresponding to domains a<SUB>i</SUB></FONT>≤<FONT
face="Times New Roman">X<SUB>i</SUB></FONT>≤<FONT
face="Times New Roman">b<SUB>i</SUB>(i=1,</FONT>…<FONT
face="Times New Roman">,n) and constraints c<SUB>j</SUB>(j=1,</FONT>…<FONT
face="Times New Roman">,p)?<BR></FONT> <FONT face="Times New Roman">Owing
to the importance of this problem in CSP, many scholars have done thorough
research in this area. Davis</FONT><SUP>［<FONT
face="Times New Roman">1</FONT>］</SUP> <FONT face="Times New Roman">gave
out the interval algorithm of Waltz</FONT>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -