AND/OR Branch-and-Bound search for combinatorial optimization in graphical models

This is the first of two papers presenting and evaluating the power of a new framework for combinatorial optimization in graphical models, based on AND/OR search spaces. We introduce a new generation of depth-first Branch-and-Bound algorithms that explore the AND/OR search tree using static and dynamic variable orderings. The virtue of the AND/OR representation of the search space is that its size may be far smaller than that of a traditional OR representation, which can translate into significant time savings for search algorithms. The focus of this paper is on linear space search which explores the AND/OR search tree. In the second paper we explore memory intensive AND/OR search algorithms. In conjunction with the AND/OR search space we investigate the power of the mini-bucket heuristics in both static and dynamic setups. We focus on two most common optimization problems in graphical models: finding the Most Probable Explanation in Bayesian networks and solving Weighted CSPs. In extensive empirical evaluations we demonstrate that the new AND/OR Branch-and-Bound approach improves considerably over the traditional OR search strategy and show how various variable ordering schemes impact the performance of the AND/OR search scheme.     

几乎最快与渐近最优的并行分枝界限算法

分枝界限算法是求解组合优化问题的技术之一,它被广泛地应用在埃运筹学与组合数学中.对共享存储的最优优先一般并行分枝界限算法给出了运行时间复杂度下界Ω(m/p+hlogp),其中p为可用处理器数,h为扩展的结点数,m为状态空间中的活结点数.通过将共享存器设计成p个立体堆,提出了PRAM-EREW上一个新的一般并行分枝界限算法,理论上证明了对于h<p^2p,该算法为最快且渐近最优的并行分枝界限算法.最后对0-r背包问题给出了模拟实验结果.     

A minimax algorithm better than alpha-beta?

An algorithm based on state space search is introduced for computing the minimax value of game trees. The new algorithm SSS1 is shown to be more efficient than α-ß in the sense that SSS1 never evaluates a node that α-ß can ignore. Moreover, for practical distributions of tip node values, SSS1 can expect to do strictly better than α-ß in terms of average number of nodes explored. In order to be more informed than α-ß, SSS1 sinks paths in parallel across the full breadth of the game tree. The penalty for maintaining these alternate search paths is a large increase in storage requirement relative to α-ß. Some execution time data is given which indicates that in some cases the tradeoff of storage for execution time may be favorable to SSS1.     

AND/OR search spaces for graphical models

The paper introduces an AND/OR search space perspective for graphical models that include probabilistic networks (directed or undirected) and constraint networks. In contrast to the traditional (OR) search space view, the AND/OR search tree displays some of the independencies present in the graphical model explicitly and may sometimes reduce the search space exponentially. Indeed, most algorithmic advances in search-based constraint processing and probabilistic inference can be viewed as searching an AND/OR search tree or graph. Familiar parameters such as the depth of a spanning tree, treewidth and pathwidth are shown to play a key role in characterizing the effect of AND/OR search graphs vs. the traditional OR search graphs. We compare memory intensive AND/OR graph search with inference methods, and place various existing algorithms within the AND/OR search space.     

A join algorithm for combining AND parallel solutions in AND/OR parallel systems

When two or more literals in the body of a Prolog clause are solved in (AND) parallel, their solutions need to bejoined to compute solutions for the clause. This is often a difficult problem in parallel Prolog systems that exploit OR and independent AND parallelism in Prolog programs. In several AND/OR parallel systems proposed recently, this problem is side-stepped at the cost of unexploited OR parallelism in the program, in part due to the complexity of the backtracking algorithm beneath AND parallel branches. In some cases, the data dependency graphs used by these systems cannot represent all the exploitable indenpendent AND parallelism known at compile time.In this paper, we describe the compile time analysis for an optimizedjoin algorithm for supporting independent AND parallelism in logic programs efficiently without leaving any OR parallelism unexploited. We then discuss how this analysis can be used to yield very efficient runtime behavior. We also discuss problems associated with a tree representation of the search space when arbitrarily complex data dependency graphs are permitted. We describe how these problems can be resolved by mapping the search space onto the data dependency graphs themselves. The algorithm has been implemented in a compiler for parallel Prolog based on the Reduce-OR process model. The algorithm is suitable for the implementation of AND/OR systems on both shared and nonshared memory machines. Performance on benchmark programs exhibiting AND and OR parallelism on one shared memory machine and one message passing machine is presented.This work was supported in part by NSF Grants CCR-87-00988 and CCR-89-02496.A shorter version of this paper appears in theProceedings of NACLP 1990.     

Problem reduction representation for the linguistic analysis of waveforms

This paper shows how the nondirectional structural analysis of pattern data can be performed by matching a problem reduction representation (PRR) of pattern structure with sample data, using a best-first state space search algorithm called SSS*. The end result of the matching algorithm is a tree whose nodes represent recognized structures in the data. Tip nodes of the tree structure correspond to primitives which are recognized in the raw data by curve fitting routines. The operators of the algorithm allow the tree to be constructed with a combination of top-down or bottom-up steps. The matching of the structure tree to waveform segments need not be done in a left-right sequence. Moreover ambiguous matches are pursued in a best first order by using state space search with partial parse trees as states. A software system called WAPSYS (for waveform parsing system) is described, which implements this structural analysis paradigm. Experience using WAPSYS to analyze carotid pulse waves is also discussed.     

Evaluating the impact of AND/OR search on 0-1 integer linear programming

AND/OR search spaces accommodate advanced algorithmic schemes for graphical models which can exploit the structure of the model. We extend and evaluate the depth-first and best-first AND/OR search algorithms to solving 0-1 Integer Linear Programs (0-1 ILP) within this framework. We also include a class of dynamic variable ordering heuristics while exploring an AND/OR search tree for 0-1 ILPs. We demonstrate the effectiveness of these search algorithms on a variety of benchmarks, including real-world combinatorial auctions, random uncapacitated warehouse location problems and MAX-SAT instances.     

Problem-solving models and search strategies for pattern recognition

Noting the major limitations of multivariate statistical classification and syntactic pattern recognition models, this paper presents an overview of some recent work using alternate representations for multistage and nearest neighbor multiclass classification, and for structural analysis and feature extraction. These alternate representations are based on generalizations of state-space and AND/OR graph models and search strategies developed in artificial intelligence (AI). The paper also briefly touches on other current interactions and differences between artificial intelligence and pattern recognition.     

面向多智能体博弈的并行蒙特卡洛树搜索算法研究

蒙特卡洛树搜索算法是一种常用的强化学习算法,博弈过程中动态空间的指数级增长是制约该算法学习效率的因素。基于并行方法对蒙特卡洛树搜索算法进行优化,提出基于胜率估值传递的并行蒙特卡洛树搜索算法。改进后的并行博弈搜索策略框架包含一个主进程和多个子进程,其中子进程用于探索,主进程根据子进程传递的胜率估值数据进行决策。结合多智能体博弈平台Pommerman进行实验验证,与传统的蒙特卡罗树搜索算法相比,并行蒙特卡罗树搜索算法有效提高了资源利用率、博弈胜率及决策效率。     

Memory intensive AND/OR search for combinatorial optimization in graphical models

In this paper we explore the impact of caching during search in the context of the recent framework of AND/OR search in graphical models. Specifically, we extend the depth-first AND/OR Branch-and-Bound tree search algorithm to explore an AND/OR search graph by equipping it with an adaptive caching scheme similar to good and no-good recording. Furthermore, we present best-first search algorithms for traversing the same underlying AND/OR search graph and compare both algorithms empirically. We focus on two common optimization problems in graphical models: finding the Most Probable Explanation (MPE) in belief networks and solving Weighted CSPs (WCSP). In an extensive empirical evaluation we demonstrate conclusively the superiority of the memory intensive AND/OR search algorithms on a variety of benchmarks.     

ACS算法在矩形件优化排料中的应用

矩形件优化排料是一类具有NP完全难度的组合优化问题。有关的优化问题可用与或树来描述,这样就把矩形件优化排料问题变换为寻找一棵面积比率最大的二叉树。用ACS算法实现这种树搜索,是把一定数量的人工蚂蚁分布在与或树的根节点,人工蚂蚁间通过使用信息素相互交流,完成从与或树到二叉树的选择,从而得到矩形件优化排料问题的优化解。     

Solving constraint optimization problems from CLP-stylespecifications using heuristic search techniques

Presents a framework for efficiently solving logic formulations of combinatorial optimization problems using heuristic search techniques. In order to integrate cost, lower-bound and upper-bound specifications with conventional logic programming languages, we augment a constraint logic programming (CLP) language with embedded constructs for specifying the cost function and with a few higher-order predicates for specifying the lower and upper bound functions. We illustrate how this simple extension vastly enhances the ease with which optimization problems involving combinations of Min and Max can be specified in the extended language CLP* and we show that CSLDNF (Constraint SLD resolution with Negation as Failure) resolution schemes are not efficient for solving optimization problems specified in this language. Therefore, we describe how any problem specified using CLP* can be converted into an implicit AND/OR graph, and present an algorithm called GenSolve which can branch-and-bound using upper and lower bound estimates, thus exploiting the full pruning power of heuristic search techniques. A technical analysis of GenSolve is provided. We also provide experimental results comparing various control strategies for solving CLP* programs     

Parallel multi-dimensional range query processing with R-trees on GPU

The general purpose computing on graphics processing unit (GP-GPU) has emerged as a new cost effective parallel computing paradigm in high performance computing research that enables large amount of data to be processed in parallel. Large scale scientific data intensive applications have been playing an important role in modern high performance computing research. A common access pattern into such scientific data analysis applications is multi-dimensional range query, but not much research has been conducted on multi-dimensional range query on the GPU. Inherently multi-dimensional indexing trees such as R-Trees are not well suited for GPU environment because of its irregular tree traversal. Traversing irregular tree search path makes it hard to maximize the utilization of massively parallel architectures. In this paper, we propose a novel MPTS (Massively Parallel Three-phase Scanning) R-tree traversal algorithm for multi-dimensional range query, that converts recursive access to tree nodes into sequential access. Our extensive experimental study shows that MPTS R-tree traversal algorithm on NVIDIA Tesla M2090 GPU consistently outperforms traditional recursive R-trees search algorithm on Intel Xeon E5506 processors.     

基于故障相关矩阵的最优测试序列生成方法

针对最优测试序列生成问题,采用与或图搜索生成测试序列,将系统故障与测试之间的关系作为节点生成的依据,在综合了信息论与启发式搜索理论的基础上,由霍夫曼编码和信息熵构成的启发式搜索函数来引导与或图的搜索生成诊断树,安排最优的测试顺序,实现用最少的代价隔离系统故障;在解决与或图搜索问题中应用了改进后的AO*算法,避免出现"NP-完全"的复杂计算问题,整个过程大大减少了生成节点的数量,提高了故障隔离效率。     

Precedence tree guided search for the efficient identification of multiple situations of interest – AND/OR graph matching

Intelligence analysis is a domain characterized by a torrent of streaming data within which a very small portion contains useful knowledge or actionable intelligence. Intelligence analysts have to sift through the compiled data and weave through a complex web of convoluted connections in an attempt to illuminate information requirements (IR) and maintain situational awareness. Automated methodologies have eased the manual burden of this process to some extent. Data are naturally modeled in a graphical form representing the known people, places, events and the relationships between them. Graph matching algorithms in which an information requirement is formulated as a template graph or situation of interest to be found in the observed data graph have been successfully employed in intelligence analysis processes. Absent from these past contributions is the recognition that partial information requirements, such as indicators and warnings, are not mutually exclusive to a specific IR, and an understanding of the characteristics of the underlying data can lead to significant performance benefits. The knowledge of overlapping template sections forms the motivation for precedence tree guided search and AND/OR templates. Through the recognition of the overlapping sections, a single AND/OR template can be created to answer many information requirements. This paper presents a novel algorithm for the intelligent traversal of an AND/OR template, providing increased algorithmic efficiency over the execution of multiple sequential graph matching instances. This paper focuses on development of an algorithm for intelligent AND/OR template traversal with computational results illustrating the effectiveness of the developed methods. The results indicate a significant improvement in runtime (with a speedup over 5 in some cases) while maintaining a good solution quality (within 2% of multiple AND path graph matching executions) in AND/OR and precedence tree guided graph matching.     

Generalization of alpha-beta and SSS1 search procedures

Search procedures, such as alpha-beta and SSS1, are used to solve minimax game trees. With a notable exception of B1, most of these procedures assume the static model, i.e., the computation is done solely on the basis of static values given to terminal nodes. The first goal of this paper is to generalize these to the informed model, which permits the usage of heuristic information pertaining to nonterminal nodes, such as upper and lower bounds, and estimates, of the exact values realizable from the corresponding game positions. We provide a general framework, within which various conventional procedures including alpha-beta and SSS1 can be naturally generalized to the informed model.For the static model, it is known that SSS1 surpasses alpha-beta in the sense that it explores only a subset of the nodes which are explored by alpha-beta. The second goal of this paper is, assuming the informed model, to develop a precise characterization of the class of search procedures that surpass alpha-beta. It turns out that the class contains many search procedures other than SSS1 (even for the static model). Finally some computational comparison among these search procedures is made by solving the 4 × 4 Othello game.     

A parallel alpha/beta tree searching algorithm

This paper gives a theoretical foundation for using parallel processing to search an alpha/beta minimax game tree. A mathematical discussion predicts the behavior of a particular parallel algorithm, Principle Variation Splitting (PVS), along with an enhancement that improves performance for most test cares. After the theoretical discussion, some practical results obtained by running two implementations of the PVS algorithm on a 30-processor tightly coupled shared memory machine are given to show the speedup obtained by parallel processing.     

一种求解与/或树的Petri网方法

研究了用Petri网求解人工智能中与/或树的问题,提出了一种把与/或树转换成相应的Petri网,并通过其逆网求得原与/或树的解树的方法,可进而利用模糊Petri网的推理得到与/或树的最优解树。该方法直观高效,拓宽了Petri网的应用领域。     

Nagging: A scalable fault-tolerant paradigm for distributed search

This paper describes nagging, a technique for parallelizing search in a heterogeneous distributed computing environment. Nagging exploits the speedup anomaly often observed when parallelizing problems by playing multiple reformulations of the problem or portions of the problem against each other. Nagging is both fault tolerant and robust to long message latencies. In this paper, we show how nagging can be used to parallelize several different algorithms drawn from the artificial intelligence literature, and describe how nagging can be combined with partitioning, the more traditional search parallelization strategy. We present a theoretical analysis of the advantage of nagging with respect to partitioning, and give empirical results obtained on a cluster of 64 processors that demonstrate nagging's effectiveness and scalability as applied to A^* search, β minimax game tree search, and the Davis–Putnam algorithm.     

广义AND／OR图的自底向上的启发式搜索算法BHAO

本文首先根据三角模概念，定义了一类新的更具普遍意义的广义ＡＮＤ／ＯＲ图．根据新定义的启发式函数ｈ（ｎ，ｘ）以及广义ＡＮＤ／ＯＲ图的最佳解树之所有子树亦是最佳子解树的原理，提出了广义ＡＮＤ／ＯＲ图的自底向上的启发式搜索算法ＢＨＡＯ．文中证明了算法ＢＨＡＯ的可采纳性．本文还提出了两类新的启发式函数的单调限制概念，并据此研究了算法ＢＨＡＯ的单调限制性质，研究了两个ＢＨＡＯ算法间的比较性质．