Stochastic Modeling of Branch-and-Bound Algorithms with Best-First Search

Branch-and-bound algorithms are organized and intelligently structured searches of solutions in a combinatorially large problem space. In this paper, we propose an approximate stochastic model of branch-and-bound algorithms with a best-first search. We have estimated the average memory space required and have predicted the average number of subproblems expanded before the process terminates. Both measures are exponentials of sublinear exponent. In addition, we have also compared the number of subproblems expanded in a best-first search to that expanded in a depth-first search. Depth-first search has been found to have computational complexity comparable to best-first search when the lower-bound function is very accurate or very inaccurate; otherwise, best-fit search is usually better. The results obtained are useful in studying the efficient evaluation of branch-and-bound algorithms in a virtual memory environment. They also confirm that approximations are very effective in reducing the total number of iterations.     

Searching graphs with A*: applications to job sequencing

The best-first search algorithm A* allows search graphs that are trees, directed acyclic graphs or directed graphs with cycles. In real life applications of A* the search graph is generally implemented as a tree. It is shown here that for certain well known one-machine job sequencing problems that arise in job shops, graph search is much faster than best-first tree search when problem instances are of small and medium size. Moreover, graph search uses less memory and so is able to solve larger problems. Depth-first search needs little memory, and is therefore capable in principle of solving problems of arbitrary size, but is slower than graph search by orders of magnitude for the examples that were studied     

基于BDD的增量启发式搜索

增量搜索是一种利用先前的搜索信息提高本次搜索效率的方法,通常可以用来解决动态环境下的重规划问题.在人工智能领域,一些实时系统常常需要根据外界环境的变化不断修正自身,这样就会产生一系列变化较小的相似问题,此时应用增量搜索将会非常有效.另外,基于BDD(binary decision diagram)的启发式搜索,结合了基于BDD的搜索和启发式搜索这两种方法的优点.它既用BDD这一紧凑的数据结构来表示系统的状态空间,又通过使用启发信息来进一步压缩搜索树的大小.在介绍基于BDD的启发式搜索和增量搜索之后,结合这两种方法给出了基于BDD的增量启发式搜索算法--BDDRPA*.大量的实验结果表明,BDDRPA*算法是非常有效的,它可以被广泛地应用到智能规划、移动机器人问题等领域中.     

Scheduling task graphs optimally with A*

Scheduling tasks onto the processors of a parallel system is a crucial part of program parallelisation. Due to the NP-hard nature of the task scheduling problem, scheduling algorithms are based on heuristics that try to produce good rather than optimal schedules. Nevertheless, in certain situations it is desirable to have optimal schedules, for example for time-critical systems or to evaluate scheduling heuristics. This paper investigates the task scheduling problem using the A* search algorithm which is a best-first state space search. The adaptation of the A* search algorithm for the task scheduling problem is referred to as the A* scheduling algorithm. The A* scheduling algorithm can produce optimal schedules in reasonable time for small to medium sized task graphs with several tens of nodes. In comparison to a previous approach, the here presented A* scheduling algorithm has a significantly reduced search space due to a much improved consistent and admissible cost function f(s) and additional pruning techniques. Experimental results show that the cost function and the various pruning techniques are very effective for the workload. Last but not least, the results show that the proposed A* scheduling algorithm significantly outperforms the previous approach.     

Breadth-first heuristic search

Recent work shows that the memory requirements of A* and related graph-search algorithms can be reduced substantially by only storing nodes that are on or near the search frontier, using special techniques to prevent node regeneration, and recovering the solution path by a divide-and-conquer technique. When this approach is used to solve graph-search problems with unit edge costs, we show that a breadth-first search strategy can be more memory-efficient than a best-first strategy. We also show that a breadth-first strategy allows a technique for preventing node regeneration that is easier to implement and can be applied more widely. The breadth-first heuristic search algorithms introduced in this paper include a memory-efficient implementation of breadth-first branch-and-bound search and a breadth-first iterative-deepening A* algorithm that is based on it. Computational results show that they outperform other systematic search algorithms in solving a range of challenging graph-search problems.     

Weighted heuristic anytime search: new schemes for optimization over graphical models

Weighted heuristic search (best-first or depth-first) refers to search with a heuristic function multiplied by a constant w [31]. The paper shows, for the first time, that for optimization queries in graphical models the weighted heuristic best-first and weighted heuristic depth-first branch and bound search schemes are competitive energy-minimization anytime optimization algorithms. Weighted heuristic best-first schemes were investigated for path-finding tasks. However, their potential for graphical models was ignored, possibly because of their memory costs and because the alternative depth-first branch and bound seemed very appropriate for bounded depth. The weighted heuristic depth-first search has not been studied for graphical models. We report on a significant empirical evaluation, demonstrating the potential of both weighted heuristic best-first search and weighted heuristic depth-first branch and bound algorithms as approximation anytime schemes (that have sub-optimality bounds) and compare against one of the best depth-first branch and bound solvers to date.     

GEORG: VLSI circuit partitioner with a new genetic algorithm framework

This paper suggests a new framework of multidimensional genetic algorithm and applies it to the real-world problem of very large scale integration (VLSI) partitioning. The framework consists of a new multidimensional genetic operator, called geographic crossover, and a new genetic encoding scheme. Geographic crossover enables more powerful creation of new solutions by allowing a diverse mixture of parent solutions. Its theoretical validity is proved based on a new view of crossover. The new genetic encoding scheme helps space search by effectively utilizing geographical linkages of genes. The new framework can be incorporated into most existing genetic algorithm (GA) implementations just by replacing the crossover module and leaving the other modules intact. For a test suite of 11 ACM/SIGDA VLSI circuitpartitioning benchmark circuits, the GA under this framework significantly outperformed recently published state-of-the-art methods as well as a previous GA on linear string.     

A comparison of multiobjective depth-first algorithms

Many real world problems involve several, usually conflicting, objectives. Multiobjective analysis deals with these problems locating trade-offs between different optimal solutions. Regarding graph search problems, several algorithms based on best-first and depth-first approaches have been proposed to return the set of all Pareto optimal solutions. This article presents a detailed comparison between two representatives of multiobjective depth-first algorithms, PIDMOA* and MO-DF-BnB. Both of them extend previous single-objective search algorithms with linear-space requirements to the multiobjective case. Experimental analyses on their time performance over tree-shaped search spaces are presented. The results clarify the fitness of both algorithms to parameters like the number or depth of goal nodes.     

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.     

Iterative-deepening search with on-line tree size prediction

The memory requirements of best-first graph search algorithms such as A* often prevent them from solving large problems. The best-known approach for coping with this issue is iterative deepening, which performs a series of bounded depth-first searches. Unfortunately, iterative deepening only performs well when successive cost bounds visit a geometrically increasing number of nodes. While it happens to work acceptably for the classic sliding tile puzzle, IDA* fails for many other domains. In this paper, we present an algorithm that adaptively chooses appropriate cost bounds on-line during search. During each iteration, it learns a model of the search tree that helps it to predict the bound to use next. Our search tree model has three main benefits over previous approaches: (1) it will work in domains with real-valued heuristic estimates, (2) it can be trained on-line, and (3) it is able to make more accurate predictions with only a small number of training examples. We demonstrate the power of our improved model by using it to control an iterative-deepening A* search on-line. While our technique has more overhead than previous methods for controlling iterative-deepening A*, it can give more robust performance by using its experience to accurately double the amount of search effort between iterations.     

Efficient branch-and-bound algorithms on a two-level memory system

Branch-and-bound algorithms in a system with a two-level memory hierarchy were evaluated. An efficient implementation depends on the disparities in the numbers of subproblems expanded between the depth-first and best-first searches as well as the relative speeds of the main and secondary memories. A best-first search should be used when it expands a much smaller number of subproblems than that of a depth-first search, and the secondary memory is relatively slow. In contrast, a depth-first search should be used when the number of expanded subproblems is close to that of a best-first search. The choice is not as clear for cases in between these cases are studied. Two strategies are proposed and analyzed: a specialized virtual-memory system that matches the architectural design with the characteristics of the existing algorithm, and a modified branch-and-bound algorithm that can be tuned to the characteristic of the problem and the architecture. The latter strategy illustrates that designing a better algorithm is sometimes more effective that tuning the architecture alone     

Evaluation of a parallel branch-and-bound algorithm on a class ofmultiprocessors

We propose and evaluate a parallel “decomposite best-first” search branch-and-bound algorithm (dbs) for MIN-based multiprocessor systems. We start with a new probabilistic model to estimate the number of evaluated nodes for a serial best-first search branch-and-bound algorithm. This analysis is used in predicting the parallel algorithm speed-up. The proposed algorithm initially decomposes a problem into N subproblems, where N is the number of processors available in a multiprocessor. Afterwards, each processor executes the serial best-first search to find a local feasible solution. Local solutions are broadcasted through the network to compute the final solution. A conflict-free mapping scheme, known as the step-by-step spread, is used for subproblem distribution on the MIN. A speedup expression for the parallel algorithm is then derived using the serial best-first search node evaluation model. Our analysis considers both computation and communication overheads for providing realistic speed-up. Communication modeling is also extended for the parallel global best-first search technique. All the analytical results are validated via simulation. For large systems, when communication overhead is taken into consideration, it is observed that the parallel decomposite best-first search algorithm provides better speed-up compared to other reported schemes     

Planning an endgame move set for the game RISK: a comparison of search algorithms

Seven algorithms used to search for solutions in dynamic planning and execution problems are compared. The specific problem is endgame moves for the board game RISK. This paper concentrates on comparison of search methods for the best plan using a fixed evaluation function, fixed time to plan, and randomly generated situations that correspond to endgames in RISK with eight remaining players. The search strategies compared are depth-first, breadth-first, best-first, random walk, gradient ascent, simulated annealing, and evolutionary computation. The approaches are compared for each example based on the number of opponents eliminated, plan completion probability, and value of ending position (if the moves do not complete the game). Simulation results indicate that the evolutionary approach is superior to the other methods in 85% of the cases considered. Among the other algorithms, simulated annealing is the most suitable for this problem.     

Partial-order reduction and trail improvement in directed model checking

In this paper we present work on trail improvement and partial-order reduction in the context of directed explicit-state model checking. Directed explicit-state model checking employs directed heuristic search algorithms such as A* or best-first search to improve the error-detection capabilities of explicit-state model checking. We first present the use of directed explicit-state model checking to improve the length of already established error trails. Second, we show that partial-order reduction, which aims at reducing the size of the state space by exploiting the commutativity of concurrent transitions in asynchronous systems, can coexist well with directed explicit-state model checking. Finally, we illustrate how to mitigate the excessive length of error trails produced by partial-order reduction in explicit-state model checking. In this context we also propose a combination of heuristic search and partial-order reduction to improve the length to already provided counterexamples.     

基于A*的双向预处理改进搜索算法

本文针对传统A*算法存在冗余路径点较多与单向搜索耗时较长的缺点,提出了一种改进A*算法.该算法采用双向预处理结构减少冗余节点数,并通过归一化处理和增加节点标记信息进一步优化估价函数提高遍历速度.利用仿真软件对改进A*算法进行实验,并与其它经典路径规划算法进行比较.仿真结果表明,改进后的A*算法较于传统A*算法能以较低的搜索节点数和搜索时长较好的完成全局路径规划.     

A*算法的改进及并行化

针对串行A^*算法时间性能较差的问题,提出了一种基于并行搜索和快速插入(PSFI)的算法。首先,研究了共享存储平台上的常见并行启发式搜索算法;然后,通过使用一种延迟的单表搜索(DSTS)方法和新的数据结构,改进了串行算法;其次,在此基础上,设计出一种基于共享存储平台的并行算法;最后,采用OpenMP加以实现。对24数码问题的测试结果表明,改进的串行和并行算法将运行时间分别减少到原算法的1/140和1/450;与并行的NBlock优先(PBNF)算法相比,并行算法将加速比提高到3.2,同时,改进算法是严格的最佳优先搜索算法,保证了解的质量,且易于实现。     

An efficient technique for nearest-neighbor query processing on the SPY-TEC

The SPY-TEC (spherical pyramid-technique) was proposed as a new indexing method for high-dimensional data spaces using a special partitioning strategy that divides a d-dimensional data space into 2d spherical pyramids. In the SPY-TEC, an efficient algorithm for processing hyperspherical range queries was introduced with a special partitioning strategy. However, the technique for processing k-nearest-neighbor queries, which are frequently used in similarity search, was not proposed. In this paper, we propose an efficient algorithm for processing nearest-neighbor queries on the SPY-TEC by extending the incremental nearest-neighbor algorithm. We also introduce a metric that can be used to guide an ordered best-first traversal when finding nearest neighbors on the SPY-TEC. Finally, we show that our technique significantly outperforms the related techniques in processing k-nearest-neighbor queries by comparing it to the R*-tree, the X-tree, and the sequential scan through extensive experiments.     

Path recovery in frontier search for multiobjective shortest path problems

Frontier search is a best-first graph search technique that allows significant memory savings over previous best-first algorithms. The fundamental idea is to remove from memory already explored nodes, keeping only open nodes in the search frontier. However, once the goal node is reached, additional techniques are needed to recover the solution path. This paper describes and analyzes a path recovery procedure for frontier search applied to multiobjective shortest path problems. Differences with the scalar case are outlined, and performance is evaluated over a random problem set.     

Depth-First Branch-and-Bound versus Depth-Bounded IDA: New Results

In a real-time task an action must be executed given limited computation. One approach to limited computation is to search a tree of possible action sequences to a fixed depth and then execute an action with the lowest associated backed-up cost. The standard algorithm for such a search is Depth-First Branch-and-Bound (DFBB), also known in the Artificial Intelligence literature as Minimin with Alpha Pruning . This article shows that a depth-bounded extension of a popular iterative algorithm called IDA has a surprisingly large range of search trees on which it outperforms DFBB—something previous analytical results do not predict. We prove that the extended algorithm, which we call DIDA , is correct, is guaranteed to terminate, and is asymptotically (i.e., on its last iteration) as efficient as DFBB—assuming a consistent heuristic is used. We also prove that both algorithms are guaranteed not to decrease their accuracy with a deeper search, assuming a consistent heuristic. Because accuracy is generally correlated with decision quality, the time saved by visiting fewer states translates to deeper searches which translates to better decisions. Results from random search trees show that DIDA is most efficient when the path cost + leaf node heuristic value is distributed with low variance; as branching factor increases, the range for which DIDA is more efficient also increases. Results with Eight, Fifteen, Twenty-four, and Ninety-nine Puzzle implementations of both algorithms—all domains with low variance of path cost + leaf node heuristic value—show that DIDA significantly outperforms DFBB.     

Semantic representation and correspondence for state-based motion transition

Consistent transition algorithms preserve salient source motion features by establishing feature-based correspondence between motions and accordingly warping them before interpolation. These processes are commonly dubbed as preprocessing in motion transition literature. Current transition methods suffer from a lack of economical and generic preprocessing algorithms. Classical computer vision methods for human motion classification and correspondence are too computationally intensive for computer animation. The paper proposes an analytical framework that combines low-level kinematics analysis and high-level knowledge-based analysis to create states that provide coherent snapshots of body-parts active during the motion. These states are then corresponded via a globally optimal search tree algorithm. The framework proposed here is intuitive, controllable, and delivers results in near realtime. The validity and performance of the proposed system are tangibly proven with extensive experiments.