基于知识库的机场机位自动分配系统

基于知识库的机场机位自动分配系统

1基于过程性知识的数据库设计在机场的运营和管理过程中，基本信息包括机场的时间、飞机的输入和功能、机场的类型和动态机票的规划和动力学。要直接生成基于这些信息的一般概率表，则很难使用。这是因为以下原因。(1)信息量大,每天需要分配的航班非常多,因此需要有较好的时间和空间性能。(2)针对一个航班有多个可行的分配方案,且航班信息变化大,信息不全,只能给出理论最佳方案。(3)安全性要求高。(4)实时性强,要求能够快速进行资源分配,以确保其它的保障进程能够按时进行。(5)对资源利用率的高要求。因此,基于机场机位分配的多规则和不确定性,本系统必须具有一定的智能性。智能系统需要知识才能工作,知识的质量和数量关系到系统的智能程度,知识的描述方法决定知识的质量,而知识的存储结构则决定系统的效率和知识库的容量,甚至决定系统的成败。传统的数据处理将知识寓于程序中,即程序就代表着系统解决问题所使用的知识。这种知识的表示类型称为过程型知识。过程型知识针对特定的问题,根据具体的处理步骤用一系列过程来表达,执行效率非常高,但它有以下缺点:(1)不易表示大量知识,且知识难于理解和修改。(2)只适合表达完全正确的知识,稍有含糊的知识就难以用程序表达。(3)只适合于处理完整、准确的数据。综上所述,过程性知识表示要求待处理的问题具有成熟的解法和完整、准确的数据,这大大地限制了它的适用范围,所以适用性比使用知识库要差。而利用关系数据库技术建立知识库则具有以下优点:(1)利用关系数据库成熟的管理技术能够对知识库中的各种知识进行集中管理,方便地对这些知识进行增加、删除、修改、浏览等操作,增强了知识对技术人员的透明度,并极大地简化了系统设计和维护人员对已有知识的访问过程和管理、维护难度。(2)利用ODBC(opendatabaseconnectivity)技术可以在多种编程环境(例如VC、VB、Delphi、Powerbuild)中方便地实现对各种数据库系统的访问,使不同编程语言在数据库的基础上实现了统一,从而在专家系统开发过程中可以根据需要灵活地选择开发语言以降低开发难度、提高开发效率。(3)目前针对常用关系数据库系统(如Oracle、Sybase)已推出许多专用开发工具(如Delphi、Powerbuild),利用它们可以方便快捷地开发出很友好的图形用户界面(GUI),便于用户使用,从而降低了对用户计算机操作能力的要求。因此,要适应机场机位自动分配的实时性、高效性、灵活性和安全性,同时保证系统具有更好的可移植性和可扩充性,必须在系统中引入知识库。2系统的维护界面整个系统采用客户机/服务器模式,其中数据库及其操作存放在服务器端,用户操作界面处于客户端。数据库主要存放航班动态信息、机位分配的辅助信息和中间结果表,并通过标准的SQL语言或存储过程来访问和更新全局数据库。知识库作为全局数据库的一部分,单独提供维护界面,使得用户可以浏览,并且自行修改。系统的主要目的是在已知当日航班动态、各种机型、机位尺寸等信息后,能够自动、实时地为即将到来的进港航班分配合适的机位,并且保证资源的高利用率。同时由于个体机场的特殊性,也要兼顾一些特殊要求。考虑到这些因素,本系统采用将知识存在知识库中与将知识寓于程序中相结合的方式,就是把不可能发生变化的信息(定量知识)直接表示成过程性知识,比如对飞机和机位尺寸的判断方法等,然后将经常可能发生变化的知识或者原则(定量知识和特殊原则)表示成形式化的知识,存于知识库中。这样做就能够兼顾过程性知识处理执行效率高和知识库技术的灵活性和可移植性。处理流程如图1。首先找到需要分配机位的航班,然后通过两层多步推理得到机位分配的结果。3知识设计3.1知识的表达本系统利用规则-事实体系作为描述知识的主要手段,知识的基本组成部分有:事实和规则。(1)添加中间节点转换成二元关系例如:张三和李四是同一个导师W的学生,表示成teach(A,张三,李四),添加中间节点转换成二元关系如下:teach(A,张三,李四)=teach(A,张三)^teach(A,李四)因此,所有的事实都可以表示成元事实。(2)结论的二元关系由此可见,规则可以最终表示为前提和结论的二元关系(如果考虑置信度的话将是三元关系);前提和结论均是由一系列元事实的合取和析取组合构成。(3)采用双重关系法表示知识范畴3.2基于关系数据库的知识存储考虑如下推理思路:将前提拆分成多个元事实,它们之间直接通过没有括号的合取与析取运算合成。针对每个元事实,找到所适用的规则进行推理,符合条件的推理结果为真,否则为假。各个元事实的推理结果进行整体逻辑运算得到整个前提的结果,如果为真,则与本前提对应的结论表示的事实成立,否则不成立。由于这个原因,可以很自然地设想用关系数据库的形式来存储知识,这就能够很好地满足上述要求。在本系统中,每一条机位分配的原则都作为一条知识来记录。按照第2部分的介绍,其表现形式为:IF<前提>THEN<结论>|<动作>,优先级P用文法G定义如下:规则->IF前提THEN结论优先级前提->元事实|前提∧元事实|前提∨元事实结论->元事实|结论∧元事实|结论∨元事实元事实->对象名对象属性名对象属性关系符对象属性值优先级->自然数即:当前提满足时,得出结论或执行其动作,优先级为P。其中前提是单个事实(命题)或者若干事实(命题)的与/或,结论一般为单个(事实)命题。优先级是在本系统的特殊环境下,为了保证各条分配原则知识在进行推理时出现冲突的一种冲突消解辅助信息。前提是由机场机位分配是需要考虑的常见对象的各种属性在特定环境下的取值。结论则通常是在满足前提的情况下使用的机位号。在系统中,知识库的构建以关系数据库为基础,将表示每一条分配原则的知识拆分存储。主要存储在4张表中。(1)规则前提:对象名、对象属性名其字段分别为:<规则号,规则前提号,对象名,对象属性名,二元关系符,属性值>规则号是用来表示这个前提是属于哪一个规则的;规则前提号唯一标识本条规则前提;对象名是本事实描述的对象的名字;对象属性名是本事实描述的对象的属性的名字;二元关系符在这里通常是=,〉,<属性值就是事实描述的对象的某个属性在特定环境下的取值。按照第2部分的描述,规则的前提可能是一个或者多个元事实的合取或者析取构成。所以,在关系数据库中记录时,前提的每一个元事实都将作为规则前提表中的一条记录。元事实之间的合取、析取运算符将另存。(2)规则结论/属性值规则结论表同规则前提表,其字段分别为:<规则号,规则结论号,对象名,对象属性名,二元关系符,属性值>其含义同规则前提表,不过规则结论一般为单个事实。(3)规则运算表的编码由于在规则前提表或者规则结论表中存储元事实间的关系运算符会引起数据库操作的不一致性,并且也不方便后面推理机的推理,因此单独存在规则运算表中。其字段如下:<规则号,规则操作符号,操作符,操作符位置>规则号表示这个操作符所属的规则;规则操作符号唯一标识这个操作符;操作符就是连接元事实的关系运算符,通常是^,v;操作符位置描述这个操作符出现的位置是在前提还是在结论。(4)分配原则的判定整体描述一条规则,其字段分别为:<规则号,优先级>规则号唯一标识这条规则;优先级表示这条规则在整个机位分配知识库各条分配知识中的优先地位。在利用机位分配知识库进行机位分配时,如果出现了某两条分配原则(知识)的推理结果出现了冲突,将以分配原则的优先级为评判准则,优先级低的分配原则产生的分配结论自动失效。例如:对于分配原则(知识):南方航空公司的国内单进737系列航班可以停在1~3号,7~12号机位,优先级为3。可以这样进行处理,首先翻译为:对于前提“南方航空公司的国内进港航班”,拆分成如下多个元事实的合取和析取的混合运算,航班的航空公司=南方航空公司and航班的航班属性=国内单进and飞机的主机型=737。再以第1个事实为例,说明其构成。“航班的航空公司=南方航空公司”,对象名是“航班”,对象属性是“航空公司”,二元关系符是“=”,属性值是“南方航空公司”。对于结论“停留在1~3号,7~12号机位”,拆分成:机位的机位号>0and机位的机位号<4or机位的机位号>6and机位的机位号<13。3.3基于知识的推理知识表示是一个系统,它不仅仅是存储实行还包括该系统提供到知识的通路和对知识的访问手段,以及对知识的利用方式,要求能够方便快速地访问到所需的数据,并且能够安全高效地推理出合理的结论。所以还需要再加上一组控制这些知识的通用接口。假设现在有一趟航班申请机位,那么怎样应用知识库推理得到合适的机位呢?由于机场机位自动分配知识库系统的特殊性,即其推理结果都是可以分配的机位集合,因此假定规则推理的结果(即可以分配的机位)为集合S,初始时为全集{}(所有的有效机位)。各项规则在存入知识库的时候已经将其分解成一系列由元事实mfacti的合取和析取所构成的元事实集(这个过程被称之为事实的元事实化),目的是为了方便后面的元事实匹配。在此就不用重复此项操作。首先将知识库中的规则按照优先级从低到高排序,针对各条规则,从数据库中的信息找出规则前提的元事实mfacti的匹配项,如果每个元事实都匹配为真的话,那么表示这条规则的前提为真,否则为假。如果整个规则的前提匹配成功,记录其结论a。并且与集合S作集合交运算。如果交运算的结果为空,表明当前规则与前面某些优先级高的规则发生了冲突,需要作冲突调解,具体方法就是直接令当前规则无效,其产生的结果集合a不与S作交运算。依次按照上述方法处理知识库中的每一条规则,就可以得到通过知识库推理得到的可分配机位集合。我们形式化地描述了整个推理过程,其推理流程如图2所示。假设一次数据库查询的平均时间为p,一条规则平均由n个元事实构成,一个元事实的推理次数为m,那么一条规则的平均推理时间为:T=nmp+O(0),如果专家系统的某个知识库有k条规则,那么在这个知识库范围内的一次推理过程的平均时间是:T=knmp+O(0)。对于一般的大型专家系统的推理过程,如果取n<=5,m<=3,k<=20,可知该方法基本上能够满足大多数应用的要求。由于本系统的特殊性,利用知识库并不是很复杂。在通用情况下,一般需要考虑事实匹配、推理控制、推理结果集的复合处理、复杂数据结构设计等工作。4存储结构的设计经实际检验,本系统具有以下一些优点:(1)速度不仅能够满足武汉天河机场机位自动分配系统的实时性要求,而且还能够满足大多数应用要求。(2)知识库的修改很方便,适用于各种与机场机位自动分配知识库系统类似的大型规则与事实集合。(3)设计的专家系统可以采用通用程序设计语言,并且此类知识库具有平台无关性。(4)采用推理机与知识库分离的方式使系统具有更大的可移植性和扩充性。总之,在机场机位自动分配系统中引入知识库,增加了系统的灵活性和通用性,确保了在紧张的机场调度工作中,能够高速、安全地为指挥人员提供最佳的机位分配方案,保障后续指挥工作的顺利进行。事实可以分为元事实(Metafact)和复杂事实。在本系统中,可以表示为二元关系的事实被称为元事实,用谓词公式来表示:OP(Attr,val)。其中,OP是一种二元关系,Attr是某个对象的某种属性,val则是属性具有的属性值。OP随着不同的描述对象具有不同的含义,针对本系统的特殊性,一般来说可以归纳为如下两类:集合运算符和算术运算符。不能够直接表示为二元关系的事实称为复杂事实,但是一般都能够表示为多元关系,对于多元关系,总可以用添加节点的方式表示为二元关系:R(A1,A2,A3,A4,…,An)=R1(A11,A12)∧R2(A21,A22)∧…∧Rn(Xn1,Xn2)。规则由前提、结论和优先级描述组成。前提是一系列元事实通过合取和析取运算所构成的假设,结论与前提构成方式类似。为了方便推理机进行推理,同时也避免规则解释的二义性,规则的前提和结论可以是析取和合取的组合运算,但是不能通