专利名称：自动划线的方法图1示出划线的一例；图2示出根据本发明的一目标网络的部分；图3A和3B示出有矩形衣片的矩形划线例子；图4示出本发明目标网络结构一例；图5A-5H示出由本发明的方法和系统获得的一系列划线；图6A-6K示出由本发明的方法和系统获得的另一系列划线。本发明的方法和系统包括解决划线问题的衣片群的概念。一种划线可理解为衣片的单一大群，它可以分成较小的群，例如图1所示的裤子的划线，在右下方是腰条的组，在线a的左右是两列大片。较小的群还可分成更小的群，直到单个衣片。衣片群的概念使得能鉴别局部和全部的目标。一方面，可以隔离地不影响其它群地处理衣片群；另方面，还可以在群与其它群的关系的整个范围来考虑衣片群。本发明的方法和系统通过实现目标网络，同时考虑局部和整体。图2示出目标网络结构。目标网络一般包括目标和交互件。目标是作决定的因子，它们不具有动作能力，仅代表对其他因子的动作的响应度。交互件是工作因子，它们不能代表响应度，而是专门进行划线本身的一些影响(如衣片/群的安排、变换和旋转)。在它们进行这个任务时，把信息反馈到目标，使目标开始进一步处理。最高目标与子目标连接，子目标或连接另外的子目标或连接交互件。交互件提供目标与划线间的联系。一目标网络涉及两个影响流诱发和满意。见图2，在通过目标网络从左到右的第一扫描中，最高目标MARKING(划线)诱发每个子目标BANDS(带)和PANELS(片)，它们又诱发多个进一步的子目标(如HOLE-FINDING(找孔)，PLACEMENT-SELECTION(布局选择)等)，或交互件(未示出)。当允许所有诱发影响从最高层目标向底层目标渗透时，某些下层目标被高度诱发，另外一些则不。仅充分诱发的下层目标实际影响确定划线中接下来的步骤，渗透和交互件的激发都是未确定地进行。在此方法中目标网络进行划线处理过程的目标驱动的符号导向，同时允许在处理过程中的随机波动。在下层目标被激发时，它经由一个或多个交互件以某种方式影响划线。这个作用产生其某种程度的满意，即这个工作成功的程度。在从右到左的目标网络的第二扫描中，这个满意从底层目标向最高目标反馈。这使底层目标能做两件事1.将划线现在状态中含的全局满意通告最高目标；2.在接下来的处理步骤对最高层目标的诱发施加从底层向上的影响。反馈到目标网络的满意在下一个从左到右的扫描中，利用在每个目标中的记忆能力影响诱发。
图2所示的目标网中每个目标潜在具有两个能力TENDENCY(趋势)和MEMORY(记忆)。TENDENCY是目标的或为高活性(1.0)或为非活性(0.0)或居其中的固有倾向。某些目标(如MARKING，BANDS和PANELS)，除非其它目标影响，是固有非活性的；另一些目标(如PRESUPPOSOTION(预测))，除非其它目标相反影响，是固有高活性的。TENDENCY是图2中每个目标中括号中的第一数字；括号中的第二数字是目标的MEMORY。MEMORY相似于惯性，并表示目标的不灵敏度，它表示目标抵抗其它目标影响的程度。带有零MEMORY(0.0)的目标完全在外压力影响之下，带有MEMORY(1.0)的目标拒绝任何方式的外影响，它总是“记着”它旧的触发状态。
上述说明使得能够理解图2中目标PRESUPPOSITION的含意。PRESUPPOSITION是固有高活性(1.0)的并有相当高的记忆(0.8)。它对目标PANELS有强的去活影响(-1.0)，并在通常过程中它确保目标PANELS是非活性的。然而由目标BANDS反馈的任何满意对PRESUPPOSITION具有强的去活影响(-1.0)。这意味着，在BANDS被高度满意时，目标PRESUPPOSITION被关闭，因此使PANELS能在下一个通过目标网络的诱发中高度诱发。因此可以说目标PANELS假设BANDS的满意。
整个目标网络是利用目标网络文件构成。下面是构成图2目标网络的需要的目标网络文件内容的一例。
1.MARKING用BANDS扩展0.4。
2.MARKING用PANELS扩展0.6。
3.PANELS假设BANDS。
上述行3自动建立执行上述假设关系的一隐含背景目标假设。尽管如此，明了这个关系的性质是重要的，它与“先确定带，后确定大片”时间顺序关系是很不相同的。这样的关系规定处理事物的严格次序，并极不适应于环境。与此相反，假设关系仅在给定瞬间提出在目标当中的注意分布“如果BANDS高度满意，仅注意PANELS”。这个关系允许在划线处理中稍后变化到BANDS，直到变化到BANDS完成前将其它目标暂搁置。另外，这种假设关系是非确定性的，它可如此严格以致在PANELS前总是完成BANDS，但它也可以足够迟以致在完全满意BANDS前开始PANELS。
群是说明任何给定瞬间上划线现时状态的中心象征方面。它们是由交互件处理的基本元素，并构成排列的衣片和/或衣片子群的以几何为基础的组，子群是划线中与其它群相对分离的。它们是以它们的几何边界(常与其它群的边界重叠)和允许包含的衣片的类别为特征。在图1中高度限制的群的一例是划线的右下部中的带组-该群是既在区域上也在它可包含的衣片类型上紧密限制。与它相对，图1中的极左部的列仅松散地限制在它右手侧(由a标出的区)并可以包含几乎所有类别的衣片。
作为一例，在图3中两个划线的小比例问题在下面讨论，这两个划线完全由矩形衣片构成，没有旋转或倾钭。
在图3A中的划线是所有衣片排在一起没分群，而图3b将带分群在划线的右下部，确保在衣片W和K间所示的鲜明限定的列。简单限定这些群降低这些划线的平均运行时间(如从146.12到106.3秒)，但如图3B所示，如果附加上系统应将较困难的衣片X或J之一排在最左列内的衣片类限制，那么时间进一步降低(如到37.15秒)。
在下面说明目标网络中交互件的概念。
当调入交互件时，它进行两个任务，以某方式影响划线，并评估它的作用的结果。然后这个评估被反馈到目标网络中的相关目标。交互件的这些动作进行在三个不同阶段，它们称为在下面说明的侦察、测试和任务建立。
在第一阶段，为避免前期浪费计算资源，一个交互件仅确定它是否应继续它的活动。为此交互件在运动中确立它的侦察任务。侦察任务确定是否实现了执行交互件的近似状态。
如果侦察任务发现交互件的状态未实现，那么交互件仃止。如果实现了，通过测试任务进行更广泛检查。测试任务假设由侦察进行的近似检查是正确的，并且交互件可以继续它的行动，但在此发生前测试任务检查追踪交互件活动的利益是什么。这个结果是从进行详细彻底计算期待的划线的可能改进的估计。测试任务通常也节省稍后建立划线要求的各种最初计算。
如果测试任务发现执行交互件的利益很低，那么交互件在此仃止。但如利益足够高，交互件执行它的建立任务。建立任务进行为实现交互件的目标所需的所有计算。这会涉及广泛分配计算资源。为此，先进行侦察和测试。在建立任务结束时，交互件的工作完成，在划线上进行了某些程序并将效果的准确评估反馈到目标网络。
关于交互件的重要一点是任何交互件，可完全独于所有考虑之外做它的工作，只受划线的现在状态的影响。交互件从不依靠以前己进行的任何具体活动，但在划线构成中数据的现在状态中仅从它们寻求的图案中取得线索。
下面说明如图3B所示的简单矩形衣片的典型划线处理过程。
本发明自动划线方法和系统是以下述信息为基础。
-划线限定文件-包含衣片和它们性质的说明。
-限制文件-包括与划线有关的限制。
-目标网络文件-根据具体排列方案构成目标网络的目标和交互件。
-分类文件-规定衣片类别分类，如大片、表袋等。
在选择了适当的文件后，存储在某存储装置中的，如硬盘或软盘的划线、它的衣片、限制和目标网络文件由处理装置装入，例如由计算机装入。然后，建立如图4所示的，根据在目标网络文件中的规范的目标网络。图4的目标网络与下述目标网络文件一致
<pre listing-type="program-listing"><![CDATA[//Central criteriaCriterion Top (Marker laid).// GoalsGoal BandStacking (Band stacking).Goal RestLaying (Laying remaining pieces)Goal TierLaying (Laying leftmost tier).Goal HPLaying (Laying remaining remaining Hodge-Podge of pieces).//SortkeysSortkey YSpanDesc(Y-Span，Descending).//InteractorsInteractor BandLayer (Band layer)Stacker (Bands，WaistBand，*，[1，-1]，0).Interactor Tierlnitr (Tier initiator)TierInitiator(Tier，1，*，YSpanDesc，left，[-1，4]，
，*，*，0.94，0.85).Interactor HPInitr (HodgePodge initiator)TierInitiator(Hp，*，*，YSpanDesc，left，[-1，4]，
，*，Bands 81.0]，0.88，0，85).Interactor TierJuggler (Tier juggler)Juggler(Tier，*，，YSpanDescend，*).Interactor HP Juggler (Hodge Podge juggler)Juggler (HP，*，YSpanDescend，*).//Goal dependenciesTop uses BandStacking to extend 0.2.Top uses RestLaying to extend 0.8.BandStacking uses BandLayer.RestLaying presupposes BandStacking.RestLaying uses TierLaying to extend 0.4.RestLaying uses HPLaying to extend 0.6.HPLaying presupposes TierLaying.TierLaying motivates Tierlnitr.TierLaying uses TierJuggler.TierJuggler presuposes Tierlnitr.HPLaying motivates HPInitr.HPLaying uses HPJuggler.HPJuggler presupposes HPInitr.]]></pre>
在图4中，圆表示目标，矩形表示交互件。在交互件规范中的各参数表示交互件-特定细节，如衣片的优先排列次序和建立群的标准。
在目标网络建立后，完全人为地诱发最高目标。这继续到最高目标回收到满意的足够水平。在这阶段所有交互件或完成了它们作用或自我满意地可不再继续进行下去。然后完成自动划线。
图5A-5H和6A-6K示出在根据本发明进行自动划线处理时一些划线的中间状态。在图5和6中，矩形衣片由相同字母表示。可见到，在根据本发明进行自动划线时中间划线彼此明显不同，但在每个划线下给定的参数在改善。在图5中，示出一处理过程，其端部上排列了所有衣片，而在图6的过程端部有一个衣片未排列，虽使用相同的结构文件。


本发明涉及制衣业中的划线问题,即遵守最小浪费等限制在一块衣料上排列给定数目衣片。本发明自动划线方法的特征是使用彼此连接的目标和交互件构成的目标网络,目标网络的第一和第二信息流方向分别定义为从一最高目标到底层一目标/一交互件和从底层一目标/一交互件到一最高目标。