Blocking optimized SIMD tree search on modern processors

Tree search is a widely used fundamental algorithm. Modern processors provide tremendous computing power by integrating multiple cores, each with a vector processing unit. This paper reviews some studies on exploiting single instruction multiple date （SIMD） capacity of processors to improve the performance of tree search, and proposes several improvement methods on reported SIMD tree search algorithms. Based on blocking tree structure, blocking for memory alignment and dynamic blocking prefetch are proposed to optimize the overhead of memory access. Furthermore, as a way of non-linear loop unrolling, the search branch unwinding shows that the number of branches can exceed the data width of SIMD instructions in the SIMD search algorithm. The experiments suggest that blocking optimized SIMD tree search algorithm can achieve 1.6 times response speed faster than the un-optimized algorithm.

Performance Characterization of Parallel Game-tree Search Application Crafty

Game-tree search plays an important role in the field of Artificial Intelligence （AI）. In this paper, we characterize one parallel game-tree search workload in chess： the latest version of Crafty, a state of art program, on two Intel Xeon shared-memory multiprocessor systems. Our analysis shows that Crafty is latency-sensitive and the hash-table and dynamic tree splitting used in Crafty cause large scalability penalties. They consume 35%-50% of the running time on the 4-way system. Furthermore, Crafty is not bandwidth-limited.

Prediction Distortion in Monte Carlo Tree Search and an Improved Algorithm

Teaching computer programs to play games through machine learning has been an important way to achieve better artificial intelligence (AI) in a variety of real-world applications. Monte Carlo Tree Search (MCTS) is one of the key AI techniques developed recently that enabled AlphaGo to defeat a legendary professional Go player. What makes MCTS particularly attractive is that it only understands the basic rules of the game and does not rely on expert-level knowledge. Researchers thus expect that MCTS can be applied to other complex AI problems where domain-specific expert-level knowledge is not yet available. So far there are very few analytic studies in the literature. In this paper, our goal is to develop analytic studies of MCTS to build a more fundamental understanding of the algorithms and their applicability in complex AI problems. We start with a simple version of MCTS, called random playout search (RPS), to play Tic-Tac-Toe, and find that RPS may fail to discover the correct moves even in a very simple game position of Tic-Tac-Toe. Both the probability analysis and simulation have confirmed our discovery. We continue our studies with the full version of MCTS to play Gomoku and find that while MCTS has shown great success in playing more sophisticated games like Go, it is not effective to address the problem of sudden death/win. The main reason that MCTS often fails to detect sudden death/win lies in the random playout search nature of MCTS, which leads to prediction distortion. Therefore, although MCTS in theory converges to the optimal minimax search, with real world computational resource constraints, MCTS has to rely on RPS as an important step in its search process, therefore suffering from the same fundamental prediction distortion problem as RPS does. By examining the detailed statistics of the scores in MCTS, we investigate a variety of scenarios where MCTS fails to detect sudden death/win. Finally, we propose an improved MCTS algorithm by incorporating minimax search to overcome prediction distortion. Our simulation has confirmed the effectiveness of the proposed algorithm. We provide an estimate of the additional computational costs of this new algorithm to detect sudden death/win and discuss heuristic strategies to further reduce the search complexity.

基于自动终止准则改进的kd-tree粒子近邻搜索研究

对于大规模运动模拟问题而言,近邻点的搜索效率将对整体的运算效率产生显著影响。本文基于关联性分析建立kd-tree的最大深度dmax与粒子总数N的自适应关系式,提出了kd-tree自动终止准则,即ATC-kd-tree,同时还考虑了叶子节点大小阈值n_(0)对近邻搜索效率的影响。试验表明,ATC-kd-tree具有更高的近邻搜索效率,相较于不使用自动终止准则的kd-tree搜索效率最高提升46%,且适用性更强,可求解不同N值的近邻搜索问题,解决了粒子总数N发生改变时需要再次率定最大深度dmax的问题。同时,本文还提出了网格搜索法组合坐标下降法的两步参数优化算法GSCD法。通过2维阿米巴虫形状的参数优化试验发现,GSCD法可更为快速地率定ATC-kd-tree的可变参数,其优化效率比网格搜索法最高提升了205%,相较于改进网格搜索法最高提升了90%。研究结果表明,ATC-kd-tree和GSCD法不仅提高了近邻搜索的效率,也为复杂运动中近邻粒子搜索问题提供了一种更为高效的解决方案,能够显著降低计算资源的消耗,进一步提升模拟的精度和效率。

ADAPTIVE CGF COMMANDER BEHAVIOR MODELING THROUGH HTN GUIDED MONTE CARLO TREE SEARCH

Improving the intelligence of virtual entities is an important issue in Computer Generated Forces （CGFs） construction. Some traditional approaches try to achieve this by specifying how entities should react to predefined conditions, which is not suitable for complex and dynamic environments. This paper aims to apply Monte Carlo Tree Search （MCTS） for the behavior modeling of CGF commander. By look-ahead reasoning, the model generates adaptive decisions to direct the whole troops to fight. Our main work is to formulate the tree model through the state and action abstraction, and extend its expansion process to handle simultaneous and durative moves. We also employ Hierarchical Task Network （HTN） planning to guide the search, thus enhancing the search efficiency. The final implementation is tested in an infantry combat simulation where a company commander needs to control three platoons to assault and clear enemies within defined areas. Comparative results from a series of experiments demonstrate that the HTN guided MCTS commander can outperform other commanders following fixed strategies.

VLSI implementation of MIMO detection for 802.11n using a novel adaptive tree search algorithm

A 4×4 64-QAM multiple-input multiple-output （MIMO） detector is presented for the application of an IEEE 802.1 In wireless local area network. The detector is the implementation of a novel adaptive tree search （ATS） algorithm, and multiple ATS cores need to be instantiated to achieve the wideband requirement in the 802.11 n standard. Both the ATS algorithm and the architectural considerations are explained. The latency of the detector is 0.75 μs, and the detector has a gate count of 848 k with a total of 19 parallel ATS cores. Each ATS core runs at 67 MHz. Measurement results show that compared with the floating-point ATS algorithm, the fixed-point imple- mentation achieves a loss of 0.9 dB at a BER of 10^-3.

Research on the adaptive hybrid search tree anti-collision algorithm in RFID system

Due to more tag-collisions result in failed transmissions,tag anti-collision is a very vital issue in the radio frequency identification(RFID) system.However,so far decreases in communication time and increases in throughput are very limited.In order to solve these problems,this paper presents a novel tag anti-collision scheme,namely adaptive hybrid search tree(AHST),by combining two algorithms of the adaptive binary-tree disassembly(ABD) and the combination query tree(CQT),in which ABD has superior tag identification velocity and CQT has optimum performance in system throughput and search timeslots.From the theoretical analysis and numerical simulations,the proposed algorithm can colligate the advantages of above algorithms,improve the system throughput and reduce the searching timeslots dramatically.

Fast Tree Search for A Triangular Lattice Model of Protein Folding

Using a triangular lattice model to study the designability of proteinfolding, we overcame the parity problem of previous cubic lattice model and enumerated all thesequences and compact structures on a simple two-dimensional triangular lattice model of size4+5+6+5+4. We used two types of amino acids, hydrophobic and polar, to make up the sequences, andachieved 2^(23)+2^(12) different sequences excluding the reverse symmetry sequences. The totalstring number of distinct compact structures was 219,093, excluding reflection symmetry in theself-avoiding path of length 24 triangular lattice model. Based on this model, we applied a fastsearch algorithm by constructing a cluster tree. The algorithm decreased the computation bycomputing the objective energy of non-leaf nodes. The parallel experiments proved that the fast treesearch algorithm yielded an exponential speed-up in the model of size 4+5+6+5+4. Designabilityanalysis was performed to understand the search result.

Parametrically Optimal, Robust and Tree-Search Detection of Sparse Signals

We consider sparse signals embedded in additive white noise. We study parametrically optimal as well as tree-search sub-optimal signal detection policies. As a special case, we consider a constant signal and Gaussian noise, with and without data outliers present. In the presence of outliers, we study outlier resistant robust detection techniques. We compare the studied policies in terms of error performance, complexity and resistance to outliers.

Nearest neighbor search algorithm for GBD tree spatial data structure

This paper describes the nearest neighbor (NN) search algorithm on the GBD(generalized BD) tree. The GBD tree is a spatial data structure suitable for two-or three-dimensional data and has good performance characteristics with respect to the dynamic data environment. On GIS and CAD systems, the R-tree and its successors have been used. In addition, the NN search algorithm is also proposed in an attempt to obtain good performance from the R-tree. On the other hand, the GBD tree is superior to the R-tree with respect to exact match retrieval, because the GBD tree has auxiliary data that uniquely determines the position of the object in the structure. The proposed NN search algorithm depends on the property of the GBD tree described above. The NN search algorithm on the GBD tree was studied and the performance thereof was evaluated through experiments.

Heru Search Method—Unique in the World that Uses Unprecedented Mathematical Formulas and Replaces the Binary Tree Breaking Various Paradigms Like 0(log<i>n</i>)

This paper deals with the efficiency of the search, with a method of organization and storage of the information that allows better results than the research trees or binary trees. No one ever dared to present better results than 0(log n) complexity, and when they wish to improve, they use balanced trees, but they continue to use principles that do not impact the pre-semantic information treatment. The Heru search method has as main characteristic the total or partial substitution of the use of the binary trees, enabling the elimination of the approximate results and informing the user the desired information instead of occurrences by sampling outside the desired information. The breakdown of the 0(log n) paradigm and the refinement of the searches are achieved with the use of a set of unpublished mathematical formulas and concepts called Infinite Series with Multiple Ratios.

考虑综合性能最优的非短视快速天基雷达多目标跟踪资源调度算法

合理有效的资源调度是天基雷达效能得以充分发挥的关键。针对天基雷达多目标跟踪资源调度问题,建立了综合考虑目标威胁度、跟踪精度与低截获概率(LPI)的代价函数;考虑目标的不确定、天基平台约束以及长远期期望代价,建立了多约束下的基于部分可观测的马尔可夫决策过程(POMDP)的资源调度模型;采用拉格朗日松弛法将多约束下的多目标跟踪资源调度问题转换分解为多个无约束的子问题;针对连续状态空间、连续动作空间及连续观测空间引起的维数灾难问题,采用基于蒙特卡罗树搜索(MCTS)的在线POMDP算法—POMCPOW算法进行求解,最终提出了一种综合多指标性能的非短视快速天基雷达多目标跟踪资源调度算法。仿真表明,与已有调度算法相比,所提算法资源分配更合理,系统性能更优。

Planning,monitoring and replanning techniques for handling abnormity in HTN-based planning and execution

A framework that integrates planning,monitoring and replanning techniques is proposed.It can devise the best solution based on the current state according to specific objectives and properly deal with the influence of abnormity on the plan execution.The framework consists of three parts:the hierarchical task network(HTN)planner based on Monte Carlo tree search(MCTS),hybrid plan monitoring based on forward and backward and norm-based replanning method selection.The HTN planner based on MCTS selects the optimal method for HTN compound task through pre-exploration.Based on specific objectives,it can identify the best solution to the current problem.The hybrid plan monitoring has the capability to detect the influence of abnormity on the effect of an executed action and the premise of an unexecuted action,thus trigger the replanning.The norm-based replanning selection method can measure the difference between the expected state and the actual state,and then select the best replanning algorithm.The experimental results reveal that our method can effectively deal with the influence of abnormity on the implementation of the plan and achieve the target task in an optimal way.

LLRB算法的函数式建模及其机械化验证

基于机器定理证明的形式化验证技术不受状态空间限制,是保证软件正确性、避免因潜在软件缺陷带来严重损失的重要方法.LLRB(left-leaning red-black trees)是一种二叉搜索树变体,其结构比传统的红黑树添加了额外的左倾约束条件,在验证时无法使用常规的证明策略,需要更多的人工干预和努力,其正确性验证是一个公认的难题.为此,基于二叉搜索树类算法Isabelle验证框架,对其附加性质部分进行细化,并给出具体化的验证方案.在Isabelle中对LLRB插入和删除操作进行函数式建模,对其不变量进行模块化处理,并验证函数的正确性.这是首次在Isabelle中对函数式LLRB插入和删除算法进行机械化验证,相较于目前LLRB算法的Dafny验证,定理数由158减少至84,且无需构造中间断言,减轻了验证的负担;同时,为复杂树结构算法的函数式建模及验证提供了一定的参考价值.

面向人员岸滩行进的三维路径规划算法研究

针对当前无法为人员岸滩行进提供科学合理的路径规划这一问题,论文基于蚁群算法提出了面向岸滩行进的最优路径规划算法。首先对基本的蚁群算法进行了改良,包括路径搜索方式、信息素更新策略和启发函数的合理设计等,改善了算法的收敛效率;然后定量结合多类岸滩场路径规划影响因子,构建了满足岸滩行进的代价函数;最终实现了面向岸滩行进的算法构建。该算法可为实现复杂地形条件下岸滩行进的最优路径解算和基于蚁群算法的相关三维路径规划分析研究提供参考借鉴。

树状结构在数据流求均值中的应用

数据采集过程中,随着数据的增加,数据的平均值持续发生变化。为了研究平均值的变化过程,分析平均值序列的计算方法是有必要的。传统的方法是使用线性顺序存储方式计算均值序列,总的时间复杂度高达O(n2)。提出利用树状结构存储方法求取均值序列,并介绍其实现方法,该方法时间复杂度大大降低,仅为O(n*lnn)。

基于聚类和GBDT的镀锌钢卷力学性能预测

热镀锌钢卷力学性能影响因素之间关系复杂,限制了模型精度的提升。采用k-means算法利用化学成分属性对镀锌钢卷数据集进行聚类,将数据聚成三种模式簇实现样本的优选。利用梯度提升树算法,开展各模式数据集与不划分模式的全数据集下的力学性能建模研究,最后结合网格搜索与交叉验证方法进行模型参数优化。研究结果表明,分模式下模型MAE误差相比于全数据集建模平均减小0.85 MPa。参数优化后,各模式下MAE误差平均减少5.19 MPa,RMSE误差平均减少3.63 MPa,提高了预测模型精度。

基于KNN-RRT 的机械臂运动路径规划算法

针对机械臂路径规划过程中节点生成容易陷入局部最小值、算法收敛速度慢等问题,以目标引力函数渐进最优快速扩展随机树(P-RRT)为基础,提出一种基于KNN快速查找的自适应步长的改进RRT算法(KNN-RRT)。首先,在目标引力的基础上引入AdaGrad方法来调整自适应步长系数,降低随机点采样陷入局部最小值的问题;其次,利用KDTree来存储节点并利k邻近快速搜索查找相邻节点,提高算法的效率,并结合三次B样条曲线优化搜索路径的质量;最后,基于KNN-RRT算法在不同障碍物环境下进行实验,实验结果表明该算法在路径搜索时间、路径质量等方面有显著提升,提高算法的稳定性。

基于深度蒙特卡洛树搜索的拱坝仓面排序研究

合理的仓面排序方案对于加快工程进度和优化资源配置有着重要影响。然而,现有仓面排序方法将这一序贯决策问题简化,多数采用多属性决策方法,存在仅对大坝实时施工状态进行分析以及未考虑未来仓面浇筑方案对当前排序策略影响的问题;部分采用多目标优化方法进行仓面排序多目标优化问题分析,但主要是采用静态权重,存在忽略了仓面排序策略随环境动态变化的不足。针对以上问题,本文提出基于深度蒙特卡洛树搜索的拱坝仓面排序方法。首先,分析仓面排序问题的约束条件和目标函数,建立仓面排序强化学习模型;其次,针对仓面排序强化学习模型具有复杂且庞大的离散状态空间,为提高搜索效率,提出融合深度学习的蒙特卡洛树搜索方法,分别利用深度神经网络进行先验动作概率分布预测和策略函数评估;最后,以乌东德拱坝工程为例进行研究,结果表明本文方法可以有效地分析拱坝仓面排序问题,且相比于粒子群方法、证据理论方法,本文方法分析的施工工期可分别提前6天、14天,平均机械利用率分别提高1.19%、1.35%。本研究为拱坝仓面排序分析与优化提供了新思路。

Navi:基于自然语言交互的数据分析系统

随着大数据时代的到来,数据分析的作用日益显著.它能够从海量数据中发现有价值的信息,从而更有效地指导用户决策.然而,数据分析流程中存在三大挑战:分析流程高耦合、交互接口种类多和探索分析高耗时.为了应对上述挑战,提出了基于自然语言交互的数据分析系统Navi.该系统采用模块化的设计原则,抽象出主流数据分析流程的3个核心功能模块:数据查询、可视化生成和可视化探索模块,从而降低系统设计的耦合度.同时,Navi以自然语言作为统一的交互接口,并通过一个任务调度器实现了各功能模块的有效协同.此外,为了解决可视化探索中搜索空间指数级和用户意图不明确的问题,提出了一种基于蒙特卡洛树搜索的可视化自动探索方法,并设计了基于可视化领域知识的剪枝算法和复合奖励函数,提高了搜索效率和结果质量.最后,通过量化实验和用户实验验证了Navi的有效性.