2. 南京师范大学 虚拟地理环境教育部重点实验室,江苏 南京 210097
2. Key Laboratory of Virtual Geographic Environments,Nanjing Normal University,Nanjing 210046,China
1 引 言
随着社会进步和科学发展,人类面临一系列重大而紧迫的全球性问题,需要将地球各圈层视作密切联系的整体,理解它们相互作用的过程和机理[1]。分布式协同地理建模(distributed collaborative geographic modeling,DCGM)正是在现代计算机、分布式网络和通信技术的支持下,协调跨学科边界有效而持续的合作,避免空间数据和地理模型的重复性建设,实现复杂地球系统科学问题的协同求解。空间信息及地理模型资源的共享、集成和表达是空间思维扩展的关键[2],国内外许多学者概括了开放式空间基础信息平台的发展特征和技术内涵[3, 4, 5, 6],围绕异构空间信息共享[7]、地理模型标准化和形式化[8]、共享集成[9, 10]、服务链构建[11, 12]等方面进行深入探索。上述研究对推进分布式协同地理建模产生了积极的作用,但其大多是从全局角度预先定义固定而静态的模型集成模式,难以在实际建模过程中进行动态调整和更改,不利于地理协同建模理论方法的进一步发展。
分布式协同地理建模通过分支领域专家完成各自承担的建模任务来实现智慧(规划或执行能力)集成,大量的随机因素使得任务分解具有动态不确定性,更侧重于鼓励参与其中的建模成员进行任务分解的探讨和设置,是典型的与领域相关的智能规划问题。针对不同的应用领域,许多学者对任务分解方法进行了研究,设计了过程网、时序逻辑公式、结构矩阵和工作流模型等有关方法[13, 14, 15]。然而,这些研究大多是基于任务自身特征而进行,较少考虑任务执行主体(领域专家或建模成员)的智慧,主要应用于领域无关的规划问题,难以适用于分布式协同地理建模过程。
与上述经典规划相比,层次任务网络(hierarchical task network,HTN)规划的主要优点在于其需要领域专家给出规划动作和方法集合,能够充分而有效地表达经验知识,实现任务的规划、推理和分解。基于此,本文通过对分布式协同地理建模任务分解过程和依据进行分析,构建了基于HTN规划的地理建模任务形式化表达模型,设计了基于顺序任务分解(ordered task decomposition,OTD)的建模任务递归分解算法,实现了地理建模任务HTN规划器并通过应用实例进行了方法验证。
2 分布式协同地理建模任务分解分布式协同地理建模采用团队式的工作模式,各领域专家反复研讨后明确所需求解的地理问题及目标,将建模任务分解成多个子任务并分派给具有执行能力的建模成员,通过协调和组织多个成员主体间的合作,构建模型求解更复杂的地球系统科学问题。
2.1 建模任务分解过程分析复杂的地理模型往往结构庞大且功能繁多,其所对应的建模任务信息量大且内容多,因此应将其逐步细化分解。任务分解是为后续的任务规划和分派管理控制提供依据的关键一步,其按照一定的原则将抽象的建模总任务细化为多个简单而具体的子任务的替换集合,得到可执行的“建模子任务金字塔”,子任务间存在松散的关联耦合度,且具有各自的独立性,以便多个建模成员协同执行建模任务。
结合分布式协同地理建模流程,其任务分解主要步骤如下:① 依据待求解的地理问题抽取建模需求,确定地理建模总任务和目标;② 将总任务细化、分解并扩展为子任务网络;③ 分析子任务的可行性,判断建模成员对子任务现有或潜在的规划和建模能力;④ 对于甄选失败的子任务将粒度继续分解,直至所有子任务分解粒度为可用一种可行的方法予以地理建模求解为止;⑤ 对于甄选成功粒度合适的子任务则将其分派给潜在的建模成员,如图 1所示。
2.2 地理建模任务分解依据任务分解的关键在于分解依据与粒度的把握,分解是否合理将影响地理协同建模的顺利进行,若分解粒度太粗,则子任务复杂度大且难执行;而若分解粒度太细,则又会增加任务管理与控制的难度。分解后子任务的粒度是否合适,取决于建模成员按照何种分解依据对地理建模任务进行细化分解,即取决于成员的规划和建模能力。地理建模任务分解具有其特殊性,需要充分考虑地理建模特点,通常分布式协同地理建模中任务分解可按以下方式进行。
(1) 功能结构:按照拟构建模型的功能结构进行任务分解,将总任务分解成多个子领域、子模型、子操作甚至是子运算。例如,将地理建模总任务分解为输入、处理、输出等功能子模块。
(2) 组织多方性:分布式协同地理建模涉及的组织数量日益递增,需要众多政府部门和科研机构的积极参与,根据各部门的数据资源和建模能力,将建模任务分与不同的组织机构。
(3) 时空尺度:时空尺度是考察地理事物特征与变化的时间和空间范围,包括客体、主体和时空维。不同时空尺度的地理模型的机理不同,例如将“流域”尺度建模任务划分成多个“子流域”尺度的子任务。
(4) 计算复杂性:地理模型是为了求解复杂地理问题所构建的计算资源,涉及空间数据、存储资源和计算能力等资源组织方式,可分为空间复杂性和时间复杂性等方面。
3 基于HTN规划的地理建模任务形式化表达一般而言,给定的地理建模任务大多是模糊的、非量化的、非形式化的,但这种描述方式存在许多问题:跨学科领域的建模成员间沟通困难、同一建模任务的抽象描述不一致、空间信息及地理模型重复采集和构建等,且不利于地理建模任务在计算机上的表达。因此,需要在地理协同建模之初就对所需分解的任务进行完整而正确的描述,即利用形式化手段对地理建模任务进行表达。
3.1 层次任务网络规划HTN规划是在设计加工、项目管理、生产调度、装配规划等实际应用领域中使用最为广泛的一种规划技术,原因在于其面向工程实际且能够较好地利用领域知识进行推理分解,适用于大规模层次任务环境中的工作规划和流程的计算机辅助制定[16]。国际上现已对HTN规划的理论模型进行了研究,提出了完备的模型,并给出可被证明正确的HTN规划程序:UMCP、SHOP2、JSHOP2等[17, 18, 19, 20]。
HTN规划形式化表示成一阶谓词逻辑语言L〈V,C,P,F,T,N〉6元组。其中:V为变量符号集合;C是常量符号集合;P为谓词符号集合;F为基本任务(动作)符号集合;T为复合任务符号集合;N是任务标记(labeling)符号集合;P、F、T两两相交为空集。
基本任务的语法形式为:do[f(x1,x2,…,xk)],其中,f∈F,(x1,x2,…,xk)为项。
目标任务的语法形式为:achieve[l],其中,l是文字。
复合任务的语法形式为:perform[t(x1,x2,…,xk)],其中,t∈T,(x1,x2,…,xk)为项。
目标任务和复合任务统称为非基本任务。
任务网络的语法形式为:[(n1∶α1)…(nm∶αm),φ],其中,αi是任务,其可能是基本任务也可能是非基本任务;ni∈N是αi的标记,以便与其他出现在网络中的任务相区别;表示任务之间的关系,包含逻辑算子┐和逻辑析取∧。
操作(算子)是一个基本的操作行为模式,语法形式为:(f(v1,v2,…,vk),l1,l2,…,lm),其中,f∈F,是基本任务符号;(v1,v2,…,vk)∈V是出现的变量;而(l1,l2,…,lk)是文字,表示基本动作即最底层任务的作用结果。
分解方法的语法形式为:(α,d),其中,α为非基本任务;d为任务网络,表示完成任务网络d是实现任务α的一种分解方法,分解方法将上层的抽象任务分解为下层的具体任务。
规划领域表示为:D=〈Op,Me〉,其中Op为操作(算子)集合;Me为分解方法集合,Me的构建需要借助领域知识和经验,是智能策略的主要表现形式。
规划问题定义为四元组P:P=〈S0,d,D〉=〈S0,d,Op,Me〉,是描述规划系统要解决的具体问题的实例。其中,S0为系统初始状态;d为要规划的目标任务;D为规划领域,分解为操作集合Op和方法集合Me。
3.2 形式化表达建模任务具有层次性,需要在科研机构、实验室以及建模成员之间自上而下完成任务主体的匹配和甄选。HTN规划正是基于分层抽象和领域知识的分布式智能规划技术和求解方法,与协同求解地理问题时进行建模任务规划的思考方式非常相似。基于HTN的语义和模型结构进行地理模型任务的形式化定义如下。
3.2.1 定义1:地理建模任务的HTN形式化框架语言L的项集为Term,子项分为4类:Hol(建模成员)、Act(行为)、Htn(分层任务网络)、Obj(其他对象)。相应的: U=UHol∪UAct∪UHtn∪Obj,式中UHol表示成员集合;UAct表示行为集合,且有UAct=UPAct∪UCAct,主要分为基本行为集合UPAct和非基本行为集合UCAct两部分;UHtn表示基于行为的分层任务网络;而UObj表示其他对象集合。
Inc⊆UHol×UHol,表示建模成员之间直接包含的偏序关系。
Can:UPAct→powerset(UHol),给出能执行某个基本行为的建模成员集合,其中,powerset是幂集符号。通过该定义可以间接体现出建模成员的执行能力,表征了成员的建模能力。
∏:UHol→powerset(UHtn),定义每个建模成员所拥有的分层任务网络集合,表征了成员的规划能力。
Meth:UHtn→UCAct,定义了每个分层任务网络的目的,即该分层任务网络所用于求解的非基本任务行为。对应于HTN规划方法的语法形式(α,d),即表明了任务网络d是实现该非基本任务α的方法。
进一步给出某个建模成员接受建模任务的定义。
3.2.2定义2:地理建模(geom)geom(i,α,φ)表示:建模成员i接受建模子任务α,φ是与α有关的约束。为简化建模任务递归分解算法的说明,在形式化同时给出相应的符号约定:① i、j,k表示建模成员符号;② φ、φ′、φ″表示约束公式符号;③ a、b表示基本行为符号;④ α、β表示非基本行为符号;⑤ ω表示分层任务网络符号,其中是空网络符号。
4 基于OTD的地理建模任务分解与分派算法OTD算法一种高效HTN规划算法,按照任务网络d中子任务的先后顺序,采用前向搜索依次进行任务分解,每次分解都基于对当前系统状态的判断而生成一个可行计划,并记录动作序列的代价信息,最终通过一次性回溯机制判定并返回一个优化的计划,从而减少了求解过程中的不确定性,使求解效率得到极大提高[20, 21]。分布式人工智能领域已通过大量的参数和方法对比,充分验证了OTD算法的适用性和高效性[22]。
地理建模任务的HTN规划形式化表达,采用OTD算法实现地理建模任务分解流程(见图 2),递归地将任务网络中的复合任务分解成越来越小的子任务,并在分解过程中顺序依次进行协调和优化判定,从而展现出地理建模任务层层剥离的梯阶分解过程。
5 试验案例为验证HTN规划方法的可行性,采用分布式流域水文模型SWAT(soil and water assessment tool)[23]作为试验案例。基于VC++.NET开发并实现了地理建模任务HTN规划器程序,自上而下实现建模任务的形式化表达和分解流程,如图 3所示。
SWAT模型具有过程模块化、连接命令化的特征,不同的子功能模块分别模拟流域内多种不同的水循环物理过程[24]。对于SWAT建模总任务“陆面地理过程”而言,依据功能结构将其分解为“陆相水文循环”(产流和坡面汇流部分)和“水文过程循环”(河道汇流部分)子任务。前者控制着每个子流域内主河道的水、泥沙、养分和杀虫剂等物质的输入量;后者模拟水、沙等物质从河网向流域出口的输移运动。依据空间尺度分层细化“陆相水文循环”为多个“子流域”,每个“子流域”又可按功能结构分解为“陆面演算”和“河道演算”子任务,分别在不同的时间尺度上进行日、月、季、年的数值计算。基于SWAT建模原理、模型结构和数据组织特征,具体以子任务“河道演算”为例,解读SWAT 2012模型程序[25]的FORTRAN源代码,设置该任务HTN规划形式化表达的变量、常量和谓词符号集合〈V,C,P,F,T,N〉,如下:① 变量符号集合V包括alpha_bnke(:)、bankst(:)、ch_l2(:)、ch_revap(:)、da_ha、hru_sub(:)、ievent、inum1、inum2等变量;② 常量符号集合C包括max_ievent、min_ievent、equal_icanal、min_rttlc等常量;③ 谓词符号集合P为rchinit、rtover、rtday、rtmusk、rthourly、rthmusk等谓词;④ 目标任务为achieve[模拟水、泥沙、养分和杀虫剂在主河道中的输移过程];⑤ 基本任务F为do[河道水流演算];⑥ 复合任务T为perform[t(河道泥沙演算,河道养分演算,河道杀虫剂演算)]。
子任务“河道演算”的HTN规划形式化表达,采用OTD算法递归分解该任务的实施过程如下:
(1) 建模成员i“王伯贤”在接受建模子任务α“河道演算”,初始化规划标识为false。
(2) 成员i“王伯贤”检查自身的建模能力和规划能力,发现其自身虽然不具备直接执行“河道演算”的建模能力,但具备“河道演算”的规划能力。
(3) 依据功能结构的分解原则,建模成员i“王伯贤”具有一个能够规划该建模子任务的HTN规划,依据组织多方性原则将该任务α“河道演算”分解为4个子任务,分别是:“河道水流演算”、“河道泥沙演算”、“河道养分演算”和“河道杀虫剂演算”,并设置HTN规划个数m=1,建模子成员个数n=0。
(4) 依据上述的HTN规划方案,分别依次递归调用4个子任务的任务分解算法,将基本任务“河道水流演算”分派给建模成员i“王伯贤”。
(5) 其他3个复合子任务进一步调用递归的任务分解算法,寻求并识别其他可承担复合任务的潜在建模成员,从而实现“河道演算”下的各复合子任务的分解与分派。
如此反复循环递归,逐步分层地实现建模任务的分解,直至任务网络中没有复合任务为止,最终生成可被各建模成员直接执行的基本任务网络。依据分解后的地理建模子任务网络,将SWAT模型源程序进行解读和拆分,获得多个可独立运行的子模块,并进行分布式协同调用。
以江西省兴国县境内水河流域为试验研究区,潋水河位于115°30′E—115°52′E和26°19′N—26°37′N之间,流域面积约579km2,其作为一个闭合的流域,是中国南方丘陵的典型区,内部水系发达,地形、土壤、植被、人类经济活动等较为复杂多样,适合进行SWAT流域模拟研究[26]。利用地理建模任务HTN规划器拆分SWAT建模任务,选择性地调用变动存储系数法(Rtday)和马斯京根法(Rtmusk)两种河道水流模型,采用文献[27]中潋水流域1991—2005年共15年的水文过程进行分布式协同计算的径流模拟值,分别进行年平均产水值的精度对比分析。
如图 4所示,对于潋水河流域无论采用Rtday还是Rtmusk水流演算方法,均能取得较好的拟合结果,且与直接调用SWAT源程序模拟计算得到的流域每年出口径流的模拟值结果完全一致。通过建模任务HTN规划器程序,可在建模成员交互协同间实现建模任务的分解、甄选和分派,根据求解需求动态选择并控制Rtday和Rtmusk等河道水流演算模块的调用顺序及方式,而无需像传统SWAT模型运行过程中去手动配置basins.bsn文件中的irte变量。使得地理专家在不了解SWAT各具体模块所有内部算法的情况下,仍然可以通过建模任务HTN规划程序来控制各模块的分布式协同调用,满足建模成员主体分别进行地理建模和研究的需要,具有较高的动态性、灵活性、适应性和有效性。
6 结 论针对分布式协同地理建模中的任务分解问题,分析地理建模任务分解过程和分解依据,在地理建模任务的形式化表达和递归分解算法的研究基础之上,实现了基于HTN规划的地理建模任务规划器,具有以下显著特点:① 基于HTN的地理建模任务形式化表达能充分利用领域知识,可以支持地理建模任务共识的理解和辨识;② 基于OTD的地理建模任务分解算法具有递归和回溯能力,能够满足快速求解大规模地理建模任务的动态规划需求;③ 协调各建模成员间的建模和规划能力,避免空间数据和地理模型的重复采集和构建。分布式协同地理建模过程中的任务分解是一个复杂而迭代的过程,涉及的影响因素较多,需要处理的信息量较大。一方面既需要深入分析所分解的建模任务之间的时间、空间和资源等方面的依赖关系;另一方面还需要利用成员间的实时通信和协商能力,使任务分派更符合实际建模需求。因此,分析建模任务间的依赖关系并设计成员间的信息流和控制流反馈,实现地理建模任务的合理分解和分派将是下一步研究的重点。
[1] | YAO Yupeng, MA Fuchen. A Discussion on the Conceptual Model for the Strategy of the Earth System Research in China [J]. Advances in Earth Science,2005,20(2):144-148. (姚玉鹏, 马福臣. 关于我国开展地球系统研究战略概念模型的讨论[J]. 地球科学进展, 2005,20(2):144-148.) |
[2] | GOODCHILD M F, JANELLE D G. Toward Critical Spatial Thinking in the Social Sciences and Humanities[J]. Geo Journal, 2010,75(1):3-13. |
[3] | DAVID J M, PAUL A, L. The Emergence of Geoportals and Their Role in Spatial Data Infrastructures [J]. Computers, Environment and Urban Systems, 2005,29(1):3-14. |
[4] | GONG Jianya, CHEN Jing, XIANG Longgang, et al. GeoGlobe: Geo-spatial Information Sharing Platform as Open Virtual Earth[J]. Acta Geodaetica et Cartographica Sinica,2010,39(6):551-553.(龚健雅, 陈静, 向隆刚,等. 开放式虚拟地球集成共享平台GeoGlobe[J].测绘学报, 2010,39(6):551-553.) |
[5] | LV Guonian. Geographic Analysis-oriented Virtual Geographic Environment: Framework, Structure and Functions[J]. China Earth Science D, 2011,54:733-743. (闾国年. 地理分析导向的虚拟地理环境:框架\结构与功能[J]. 中国科学:D辑, 2011, 54:733-743.) |
[6] | GUO Renzhong, LIU Jiangtao, PENG Zifeng, et al. Technologies Connotation and Developing Characteristices of Open Geospatial Information Platform[J]. Acta Geodaetica et Cartographica Sinica, 2012,41(3):323-326.(郭仁忠, 刘江涛, 彭予凤,等.开放式空间基础信息平台的发展特征与技术内涵[J]. 测绘学报, 2012,41(3):323-326.) |
[7] | OMRAN E E, ETTEN J V. Spatial-Data Sharing: Applying Social-Network Analysis to Study Individual and Collective Behavior[J]. International Journal of Geographical Information Science, 2007, 21(6):699-714. |
[8] | YANG Hui, SHENG Yehua, WEN Yongning, et al. Research on Standardization and Formalization of Heterogeneous Geo-analysis Models in Web Space[J]. Geo-information Science, 2008,10(3):382-389. (杨慧, 盛业华, 温永宁, 等. Web环境下异构地理分析模型的标准化和形式化研究[J]. 地球信息科学, 2008,10(3):382-389.) |
[9] | WEN Yongning, LV Guonian, YANG Hui,et al. A Service-oriented Framework of Distributed Geographic Model Integration[J]. Journal of Remote Sensing, 2006,10 (2):160-168.(温永宁, 闾国年, 杨慧, 等. 面向服务的分布式地学模型集成框架研究[J]. 遥感学报, 2006,10(2):160-168.) |
[10] | YANG Hui, SHENG Yehua, WEN Yongning, et al. Distributed Geographic Models Sharing Method Based on Web Services[J]. Geomatics and Information Science of Wuhan University, 2009,34 (2):142-145.(杨慧, 盛业华, 温永宁, 等. 基于Web Services的地理模型分布式共享方法[J]. 武汉大学学报:信息科学版, 2009,34(2):142-145.) |
[11] | JIA Wenjue, LI Bin, GONG Jianya. Research on Dynamic GIS Chain Based on Workflow Technology[J]. Geomatics and Information Science of Wuhan University, 2005,30(11):982-985. (贾文钰, 李斌, 龚健雅. 基于工作流技术的动态GIS服务链研究[J]. 武汉大学学报:信息科学版,2005,30(11):982-985.) |
[12] | YU Hailong,WU Lun, LIU Yu, et al. A Study of Integration between GIS and GIS-based Model Based on Web Services[J]. Acta Geodaetica et Cartographica Sinica,2006,35 (2):153-165.(于海龙, 邬伦, 刘瑜, 等. 基于Web Services的GIS与应用模型集成研究[J]. 测绘学报, 2006,35(2):153-165.) |
[13] | UGER K, DANA N, MARCO P, et al. Task Decomposition on Abstract States, for Planning under Nondeterminism[J]. Artificial Intelligence, 2009,173(5-6):669-695. |
[14] | GAO Fei, QIU Xuesong, GAO Zhipeng, et al. Task Decomposition Algorithm for IT Complex Application Management Based on Multi-agent Collaboration[J]. Journal of Software, 2011,22(9):2049-2058. (高斐,邱雪松,高志鹏,等. 基于多代理协作的IT复杂应用管理任务分解算法[J]. 软件学报, 2011,22(9):2049-2058.) |
[15] | ZHANG Wanpeng, WANG Nan, CHEN Jing. An HTN Planning Domain Modeling Method Using a Workflow Model[J].CAAI Transactions on Intelligent Systems, 2011,6(3):239-247. (张万鹏, 王楠, 陈璟.一种利用工作流模型的分层任务网络规划领域建模方法[J].智能系统学报,2011,6(3):239-247.) |
[16] | EROL K, HENDLER J, NAU D S. Complexity Results for HTN Planning[J]. Annals of Mathematics and Artificial Intelligence, 1996,18:69-93. |
[17] | YANG Q. Formalizing Planning Knowledge for Hierarchical Planning[J]. Computational Intelligence Journal, 1990,6:12-24. |
[18] | KAMBHAMPATI S, HENDLER J A. A Validation-Structure-Based Theory of Plan Modification and Reuse[J]. Artificial Intelligence, 1992,55:193-258. |
[19] | HENDLER K E J, NAU D S. A Sound and Complete Procedure for Hierarchical Task Network Planning[C]// Proceedings of AI Planning Systems.[S.l.]: UMCP,1994:249-254. |
[20] | SMITH S, NAU D, THROOP T. Computer Bridge: A Big Win for AI Planning [J]. AI Magazine, 1998, 19 (2): 93 -105. |
[21] | DIX J, KUTER U, NAU D. Planning in Answer Set Programming Using Ordered Task Decomposition[C]//KI 2003: Advances in Artificial Intelligence. [S.l.]:Springer LNCS, 2003:490-504. |
[22] | SONG Jinge, ZHA Jianzhong, LU Yiping. Multiple Plans Oriented OTD Algorithm for HTN Planning[J]. Journal of Beijing Jiaotong Unviversity, 2009,33(4):46-49. (宋泾舸, 查建中, 陆一平. HTN规划中面向多计划生成的顺序任务分解算法[J]. 北京交通大学学报, 2009,33(4):46-49.) |
[23] | NEITSCH S L, ARNOLD J G, KINIRY J R, et al. Soil and Water Assessment Tool Theoretical Documentation [R]. [S.l.]:SWAT, 2005. |
[24] | WANG Zhonggen, LIU Changming, HUANG Youbo. The Theory of SWAT Model and Its Application in Heibe Basin[J]. Progress in Geography, 2003,22(1):79-86.(王中根, 刘昌明, 黄友波. SWAT模型的原理、结构及应用研究[J]. 地理科学进展, 2003,22(1):79-86.) |
[25] | SWAT 2012. Soil and Water Assessment Tool[EB/OL]. [2013-3-13]. http://swat.tamu.edu/. |
[26] | LI Shuo, SUN Bo, ZENG Zhiyuan, et al. Distributed Modeling of Nutrient Transport in Basin with Support of Remote Sensing and Geography Information System[J]. Chinese Journal of Applied Ecology, 2004,15(2):278-282.(李硕, 孙波, 曾志远,等. 遥感和GIS辅助下流域养分迁移过程的计算机模拟[J]. 应用生态学报, 2004,15(2):278-282.) |
[27] | LI Shuo, SUN Bo, ZENG Zhiyuan, et al. Study on Spatial Discretization in Basin Simulation Aided by RS and GIS[J]. Acta Pedologica Sinica, 2004,41(2):183-189.(李硕, 孙波, 曾志远, 等. 遥感、GIS辅助下流域空间离散化方法研究[J]. 土壤学报,2004,41(2):183-189.) |