多agent规划综述*

多Agent规划是智能规划和多Agent系统的交叉领域,随着智能规划领域研究范围的不断扩展和多Agent系统领域研究内容的不断深入,多Agent规划受到了越来越多的关注。有鉴于此,本文对多Agent规划的概念和主要方法进行全面综述。具体内容包括智能规划和多Agent系统的背景介绍、多Agent规划的各种形式化描述方式以及基于规划修复、合并或者马尔可夫决策过程的的分布式规划方法。最后,还给出了多Agent规划的发展趋势。     

自动获取派生谓词规划领域的通用规划

通用规划(解)是针对某个领域的像算法一样的规划解,通过对其的解释可以直接得出具体问题的规划解,而不需要调用任何规划系统.但是目前通用规划的提取只能在一些简单或者特殊的领域中进行,没有推广到复杂或者一般的规划领域.该文提出在包含派生谓词的规划领域自动获取通用规划的方法.与已有获取方法不同的是:首先,基于派生谓词规则,文中方法明确指出派生谓词目标与动作效果之间的依赖关系,用以完善通用规划中动作应用的目的;其次,在提取过程中借助角色来帮助识别规划解中的循环结构.实验结果表明,文中方法不仅容易在派生谓词规划领域中获取通用规划,而且还能够以较好的性能求解一类以派生谓词为主要目标的规划"难"题.该文是在派生谓词规划领域中提取通用规划的首创性工作.     

过度规划、部分可满足规划及简单偏好综述*

智能规划是人工智能的重要分支,它从某个特定问题的初始状态出发,寻找达到解决该问题的目标状态的动作序列,但是在许多真实问题中,往往没有足够的资源来实现所有目标。因此,智能规划中对软目标的研究包括过度规划、部分可满足规划和简单偏好,已成为近年来的热点。将对过度规划、部分可满足规划和简单偏好的主要研究成果进行综述,包括这几类问题的差异比较、主要解决方案以及对将来的展望。     

并行概率规划综述*

自动规划是人工智能的重要分支。它针对特定领域的特定问题,生成一个由可应用动作构成的规划。经典规划中的动作效果是确定的,且在每个时间步内只能执行一个动作。但在实际问题中,动作的效果往往是不确定性的,且动作的执行具有并发性。因此,并行概率规划(Parallel and Probabilistic Planning, PPP) 被提出,并在近两次国际规划比赛中有了专门的PPP比赛。PPP的应用前景正在引起规划研究学术圈的关注。有鉴于此,本文对其进行综述。具体内容包括定义PPP领域、问题和规划解,介绍其描述语言、基准领域及规划器,并对其中两个有代表性的规划器进行实际测试。实验表明在求解效率方面测试结果与比赛结果基本一致,但部分规划器的求解规模与竞赛不完全一致。这可能是比赛中的某些未开源代码或手工干预得到的。     

通用准则评估综述

在介绍CC国内外发展现状的基础上,系统地分析了通用准则CC的基本概念、主要思想以及CC评估角色和类型等主要问题,并对CC评估配套方法——CEM及其评估流程进行了深入探讨,最后在总结CC评估现状的基础上,指出了CC评估所存在的问题及其未来的发展趋势。     

机器人路径规划方法综述

路径规划技术是机器人控制技术研究中的一个重要问题,目前为止,其研究方法主要有两大类传统方法和智能方法.综述了有关机器人路径规划技术的研究方法,介绍了自由空间法等传统方法,同时讨论了基于遗传算法、模糊控制和神经网络等智能方法的路径规划技术,并展望了机器人路径规划技术的未来与发展趋势.     

智能规划的通用问题描述进展

规划领域定义语言是第一届国际规划竞赛提出的问题定义语言,随着两年一次的国际规划竞赛的举办,其语言的描述方式和能力也在不断扩展。本文将现有规划问题的通用描述予以综述,通过形式化地描述智能规划在不同发展阶段的通用描述方法,对其语法和语义以实例进行剖析,为后续的研究者提供精准的规划描述,并提出了未来的发展趋势。     

通用智能门禁管理机制

根据各种门禁的共同特点，以模式识别门禁为例，提出通用智能门禁管理机制。该管理机制使得系统的监控硬件趋近最小配置，对缩小系统体积、降低成本极为有利。该管理机制的主程序设计为单向闭环链结构，尽管监控硬件趋近最小配置，但不影响众多参数的设置与各项管理功能的实施，增加智能参数和操作功能而不增加系统软件的整体复杂度。该机制在以89C51为核心的系统上实现，其原理也适用其它计算机系统，同样也适用其它非模式识别智能门禁系统。     

基于模型估计的关节式月球车参数化轨迹规划*

为了在轨迹规划阶段提高月球车在三维地形中的轨迹规划精度,以被动关节式地形自适应月球车为研究对象,融合关节机器人D-H坐标建模方法构建月球车悬架运动学模型,结合数值求解方法,推导了任意崎岖三维地形中月球车姿态估计模型.在模型估计基础上利用参数化控制原理,建立了满足约束条件下被动关节式月球车在任意地形中的基于模型估计的一般性参数化轨迹生成模型.针对轮式月球车的非完整性特点,结合数值求解方法,推导了非线性模型的求解方法.最后利用仿真方法,以八轮摇杆摇臂关节式月球车为例,验证了崎岖地形中基于模型估计的轨迹生成方法的正确性,且可提高关节式月球车在崎岖地形中的规划精度.     

不确定层次任务网络规划研究综述

层次任务网络(Hierarchical task network, HTN)规划作为一项重要的智能规划技术被广泛应用于实际规划问题中, 传统的HTN规划无法处理不确定规划问题.然而, 现实世界不可避免地存在无法确定或无法预测的信息, 这使许多学者开始关注不确定规划问题, 不确定HTN规划研究也成为HTN规划研究的前沿.本文从HTN规划过程出发分析了不确定HTN规划问题中涉及的三类不确定, 即状态不确定、动作效果不确定和任务分解不确定; 总结了系统状态、动作效果和任务分解等不确定需要扩展确定性HTN规划模型的工作, 以此对现有不确定HTN规划的研究工作加以梳理和归类; 最后,对不确定HTN规划研究中仍需要解决的问题和未来的研究方向作了进一步展望.     

面向并行负载平衡的数据剖分技术*

对传统的数据剖分技术和负载平衡对大规模并行计算性能的影响进行了综述,介绍了目前典型的几何剖分方法和图剖分方法的特点,并分析比较各种剖分算法及常用剖分软件包(ParMETIS、Zoltan、JOSTLE等)在实际应用中的优缺点,深入探讨了数据剖分技术是如何对超大规模数值模拟计算任务进行高效划分以解决负载平衡问题的,以期为开展并行计算研究和并行性能优化的研究人员提供参考。     

Evaluating the impact of alternative plans on manufacturing performance

In recent years, process planners have become interested in the development of dynamic process planning systems that can interface to scheduling systems providing alternative process plans to increase flexibility in scheduling. However, deciding how many alternatives are needed has not been addressed in any previous studies. This paper presents the results of a simulation-based study aimed at characterizing the benefit provided from having alternative plans available for use in scheduling. This benefit is quantified in terms of the overall performance of a job-shop manufacturing environment. The results of this study indicate that the advantage gained by increasing the number of alternative process plans diminishes rapidly. In fact, under some conditions for the particular system studied, increasing the number of alternatives actually resulted in degraded system performance. Based on these results developers of process planning systems and methodologies need to evaluate carefully the benefit of expending time and resources on the generation of alternative plans or optimal plans.     

基于执行频率的循环展开优化方法

本文提出一种面向嵌入式低功耗的基于执行频率的循环展开优化方法,根据循环的执行频率,积极展开一些频繁被执行的循环,不展开那些很少被执行的循环。所有这些都在GCC4.0.0上进行了实现,并在sim-panalyzer功耗模拟器上对12个Benchmarks进行了测试,结果表明,相对于传统的循环展开优化,新的优化方法可以有效的降低功耗,并且减少了代码量的增加。     

Optimized Unrolling of Nested Loops

Loop unrolling is a well known loop transformation that has been used in optimizing compilers for over three decades. In this paper, we address the problems of automatically selecting unroll factors for perfectly nested loops, and generating compact code for the selected unroll factors. Compared to past work, the contributions of our work include (i) a more detailed cost model that includes register locality, instruction-level parallelism and instruction-cache considerations; (ii) a new code generation algorithm that generates more compact code than the unroll-and-jam transformation; and (iii) a new algorithm for efficiently enumerating feasible unroll vectors. Our experimental results confirm the wide applicability of our approach by showing a 2.2× speedup on matrix multiply, and an average 1.08× speedup on seven of the SPEC95fp benchmarks (with a 1.2× speedup for two benchmarks). Larger performance improvements can be expected on processors that have larger numbers of registers and larger degrees of instruction-level parallelism than the processor used for our measurements (PowerPC 604).     

分簇结构谓词以及编译优化框架研究

谓词执行是在控制流存在的条件下可以有效挖掘指令级并行性的硬件机制。而在分簇结构上实现谓词机制,可以提高分簇结构上条件的执行效率。本文针对分簇结构展开谓词体系体系结构的研究,提出了分簇结构部分谓词的高效实现方法,以及基于循环展开的分簇结构部分谓词支持框架。实验表明,本文提出的分簇结构部分谓词及编译框架可以很好地提高条件执行程序的执行效率。     

基于指令Cache和寄存器压力的循环展开优化

循环展开是一种常用的编译优化技术,能够有效减少循环开销,提升指令级并行程度和数据局部性,提升循环的执行效能。然而,过度的循环展开会造成指令Cache溢出,增大寄存器压力,循环展开次数太少又会浪费潜在的性能提升机会,因此寻找恰当的展开因子是研究循环展开问题的核心。基于GCC开源编译器,面向循环展开问题开展深入的分析与研究,针对指令Cache和寄存器资源对循环展开的影响,提出了一种基于指令Cache和寄存器压力的循环展开因子计算方法,并在GCC编译器中实现了该计算方法。申威和海光平台上的实验结果显示,相较于目前GCC中存在的其它展开因子计算方法,所提出的方法可以获得更为有效的循环展开因子,提升了程序性能。在SPEC CPU 2006测试集上的平均性能分别提升了2.7%和3.1%,在NPB-3.3.1测试集上的分别为5.4%和6.1%。     

利用循环分割和循环展开避免Cache代价

存储系统与处理器之间的速度差距逐渐变大,为此,cache使用了分级机制,但这也带来了额外的存储延迟(cache代价).提出一种利用循环分割和循环展开相结合避免cache代价的PCPLPU(prevent cache penalty by loop partition-unrolling)算法.实验结果表明,PCPLPU算法能够有效避免循环代价,提高程序性能.     

Experiments with proof plans for induction

The technique of proof plans is explained. This technique is used to guide automatic inference in order to avoid a combinatorial explosion. Empirical research is described to test this technique in the domain of theorem proving by mathematical induction. Heuristics, adapted from the work of Boyer and Moore, have been implemented as Prolog programs, called tactics, and used to guide an inductive proof checker, Oyster. These tactics have been partially specified in a meta-logic, and the plan formation program, CLAM, has been used to reason with these specifications and form plans. These plans are then executed by running their associated tactics and, hence, performing an Oyster proof. Results are presented of the use of this technique on a number of standard theorems from the literature. Searching in the planning space is shown to be considerably cheaper than searching directly in Oyster's search space. The success rate on the standard theorems is high.     

广义区间上的泛逻辑自相关系数求解

广义自相关系数的求解是泛逻辑在不确定性推理中需要解决的关键问题之一。称任意[a,b]区间为广义区间,在广义区间上给出了广义N范数、广义N性生成元、广义自相关系数的定义。提出了由复杂系统参数的分布函数求解广义自相关系数的一般方法,给出并证明了重要的直通NLK公式。最后举例说明了求解k值的具体,为从数学模型和逻辑推理两个角度来分析复杂系统参数间的相关性提供了一种新的思路。     

基于申威众核处理器的MD5解密算法优化

当前的MD5解密算法无法适应申威架构,不能充分发挥申威26010众核处理器的性能优势。针对上述问题,采用散列初始化、循环展开、链接变量优化、61步优化和申请内存优化等优化方法在单核上进行优化,提高解密算法速度,并且将优化后的解密算法改写成主从模式,将计算任务分配到64个从核中并行执行,对主从核的访存方式进行优化,以减少访存对程序带来的时间开销。通过5组不同任务量的测试,实验结果显示在单核上优化后的平均加速比为12.28,在从核上优化后的平均加速比为44.84。实验结果表明在申威26010众核处理器上的MD5解密算法优化方法具有可行性和有效性。