Heuristic search for equivalence checking

Equivalence checking plays a crucial role in formal verification since it is a natural relation for expressing the matching of a system implementation against its specification. In this paper, we present an efficient procedure, based on heuristic search, for checking well-known bisimulation equivalences for concurrent systems specified through process algebras. The method tries to improve, with respect to other solutions, both the memory occupation and the time required for proving the equivalence of systems. A prototype has been developed to evaluate the approach on several examples of concurrent system specifications.     

Heuristic search for the stacking problem

This paper presents the Stacking Problem, a hard combinatorial optimization problem concerning handling and storage of items in a warehouse, where they are handled by a crane and organized into stacks. We define the problem, study its complexity class, and present a mathematical programming model to solve it. In order to tackle medium‐ or large‐scale instances, we propose a simulation‐based algorithm using semi‐greedy construction heuristics. This simple approach allows for multiple constructions, finding solutions within reasonable time even for large instances. Three semi‐greedy heuristics are proposed and compared in an extensive computational experiment, where we study the relation between the number of constructions and the best solution obtained using each heuristic.     

Heuristic improvement through triangulation

Abstract

This paper presents a method for improving heuristics using a triangulation technique. Instead of using a heuristic to directly estimate distance (X₁, X₂) between nodes X₁ and X₂, the proposed technique selects a reference node R_i applies the heuristic to (X₁,R_i) and (X₂,R_i), and uses the Euclidean distance formula to calculate a new heuristic value. If two nodes are close to each other, then they should also be approximately equidistant to a third reference node. Utilizing a set of many such reference nodes, node expansions can be reduced for a large class of heuristics. Very early results for this method, referred to as multi-dimensional heuristics, showed that fewer node expansions were needed when using the triangulation technique. New results in this paper include the development of a new learning procedure for selecting reference nodes, experimentation on reusing reference node sets for multiple goal instances, a comparison of multi-dimensional heuristics with weighting and how they dynamically weight states near the goal, and some observations which help explain how and why this technique improves heuristics.     

Heuristic search for one-to-many shortest path queries

Annals of Mathematics and Artificial Intelligence - In this paper we study the One-to-Many Shortest Path Problem (OMSPP), which is the problem of solving k shortest path problems that share the...     

Heuristic evaluation functions in artificial intelligence search algorithms

We consider a special case of heuristics, namely numeric heuristic evaluation functions, and their use in artificial intelligence search algorithms. The problems they are applied to fall into three general classes: single-agent path-finding problems, two-player games, and constraint-satisfaction problems. In a single-agent path-finding problem, such as the Fifteen Puzzle or the travelling salesman problem, a single agent searches for a shortest path from an initial state to a goal state. Two-player games, such as chess and checkers, involve an adversarial relationship between two players, each trying to win the game. In a constraint-satisfaction, problem, such as the 8-Queens problem, the task is to find a state that satisfies a set of constraints. All of these problems are computationally intensive, and heuristic evaluation functions are used to reduce the amount of computation required to solve them. In each case we explain the nature of the evaluation functions used, how they are used in search algorithms, and how they can be automatically learned or acquired.     

Heuristic search and pruning in polynomial constraints satisfaction

In this paper, we report how certain AI techniques can be used to speed up an algebraic algorithm for deciding the satisfiability of a system of polynomial equations, dis-equations, and inequalities. We begin by viewing the algebraic algorithm (Cylindrical Algebraic Decomposition) as a search procedure which searches for a solution of the given system. When viewed in this way, the algebraic algorithm is non-deterministic, in the sense that it can often achieve the same goal, but following different search paths requiring different amounts of computing times. Obviously one wishes to follow the least time-consuming path. However, in practice it is not possible to determine such an optimal path. Thus it naturally renders itself to the heuristic search techniques of AI. In particular we experimented with Best-First strategy. We also study a way to prune the search space, which proves to be useful especially when the given polynomial system is not satisfiable. The experimental results indicate that such AI techniques can often help in speeding up the algebraic method, sometimes dramatically. This revised version was published online in June 2006 with corrections to the Cover Date.     

基于用户行为的启发式本体搜索机制

为了能够以较高的准确率搜索到用户所需要的领域本体,在分析本体搜索需求和研究用户搜索行为的基础上,提出了一种基于用户行为的启发式本体搜索机制,利用不同用户由于领域认知不同,输入的具有领域共性的搜索关键词不同,实现用户搜索关键词的启发式扩展和搜索匹配度的提高。实验表明,使用该方法执行本体搜索具有较高的准确率和召回率。     

Heuristic manipulation,tabu search and frequency assignment

Heuristic manipulation attempts to modify the search space of an optimization problem, using information provided by an underlying heuristic method. In this paper it is applied in combination with tabu search to the fixed spectrum frequency assignment problem.The frequency assignment problem involves the assignment of discrete channels (or frequencies) to the transmitters of a radio network, such as a mobile telephone network. Frequency separation is necessary to avoid interference by other transmitters to the signal received from the wanted transmitter at the reception points. Unnecessary separation causes an excess requirement for spectrum. Good assignments minimize interference and the spectrum required. In fixed spectrum frequency assignment the frequency spectrum available is given and the target is to minimize the interference in the network.Computational experiments confirm that the manipulation technique is able to drive the underlying tabu search algorithm towards improved solutions.     

Heuristic search + local model checking in selective mu-calculus

Many tools for the automatic analysis or verification of finite-state distributed systems are based on construction of the global state graph of the system under consideration. Thus, they often fail because of the state explosion problem: the state space of a distributed system potentially increases exponentially in the number of its parallel components. To overcome this problem, we present a model checking procedure, based on the combination of heuristic searches with ideas taken from local model checking. We use heuristic mechanisms for exploration of the search space in order to avoid construction of the complete state graph.     

Heuristic search in PARLOG using replicated worker style parallelism

Most concurrent logic programming languages hide the distribution of processes among physical processors from the programmer. For parallel applications based on heuristic search, however, it is important for the programmer to accurately control this distribution. With such applications, an inferior distribution strategy easily leads to enormous search overheads, thus decreasing speedup on parallel hardware.

To solve this problem, various language extensions for concurrent logic languages have been proposed, such as mapping notations and priorities. We present an alternative approach that does not require any new language features. Our solution is to use the replicated workers paradigm in a concurrent logic language (PARLOG). This paradigm has thus far mainly been used in parallel procedural languages, such as Linda and Orca. We show that it is just as useful for logic languages. We have implemented two parallel applications, the Traveling Salesman Problem and alpha-beta search, using this approach. Also, we have done some performance measurements of these programs on a multiprocessor. These experiments show that significant speedups can be obtained in this way.     

基于禁忌搜索的启发式算法求解球体Packing问题*

为求解具有NP难度的球体Packing问题,通过将禁忌搜索方法与基于自适应步长的梯度下降法和二分法相结合,提出了一个启发式算法。对50个等球算例进行了实例测试,算法改进了其中44个算例的目前最优结果。大量的实例计算结果表明,该启发式算法是求解球体Packing问题的一个有效算法。     

Improving peer-to-peer search performance through intelligent social search

As a large amount of information is added onto the Internet on a daily basis, the efficiency of peer-to-peer (P2P) search has become increasingly important. However, how to quickly discover the right resource in a large-scale P2P network without generating too much network traffic remains highly challenging. In this paper, we propose a novel P2P search method, by applying the concept of social grouping and intelligent social search; we derive peers into social groups in a P2P network to improve search performance. Through a super-peer-based architecture, we establish and maintain virtual social groups on top of a P2P network. The interactions between the peers in the P2P network are used to incrementally build the social relationships between the peers in the associated social groups. In such a P2P network, a search query is propagated along the social groups in the overlay social network. Our preliminary experiments have demonstrated that our method can significantly shorten search routes and result in a higher peer search performance. In addition, our method also enhances the trustworthiness of search results because searches go through trusted peers.     

Timetabling through Constrained Heuristic Search and Genetic Algorithms

Hybrid genetic algorithms are presented that use constrained heuristic search and genetic techniques for the timetabling problem (TP). The TP is an NP-hard problem for which a general polynomial time deterministic algorithm is not known. The paper describes the classification of constraints and the constraint ordering to obtain the minimization of backtracking and the maximization of parallelism. The school timetabling problem is discussed in detail as a case study. The genetic algorithm approach is particularly well suited to this kind of problem, since there exists an easy way to assess a good timetable, but not a well structured automatic technique for constructing it. So, a population of timetables is created that evolves toward the best solution. The evaluation function and the genetic operators are well separated from the domain-specific parts, such as the knowledge of the problem and the heuristics, i.e. from the timetable builder. The present paper illustrates an approach based on the hybridization of constrained heuristic search with novel genetic algorithm techniques. It compares favourably with known programs to solve decision problems under logic constraints. The cost of the new algorithm and the quality of the solutions obtained in significant experiments are reported.     

Adaptive search through constraint violations

Abstract

We describe HS, a production system that learns control knowledge through adaptive search. Unlike most other psychological models of skill acquisition, HS is a model of analytical, or knowledge-based, learning. HS encodes general domain knowledge in state constraints, patterns that describe those search states that are consistent with the principles of the problem domain. When HS encounters a search state that violates a state constraint it revises the production rule that generated that state. The appropriate revisions are computed by regressing the constraint through the action of the production rule. HS can learn to solve problems that it cannot solve without learning. We present a Blocks World example of a rule revision, empirical results from both initial learning experiments and transfer experiments in the domain of counting, and an informal analysis of the conditions under which this learning technique is likely to be useful.     

Heuristic search for scheduling flexible manufacturing systems using lower bound reachability matrix

For scheduling flexible manufacturing systems efficiently, we propose new heuristic functions for A^* algorithm that is based on the T-timed Petri net. In minimizing makespan, the proposed heuristic functions are usually more efficient than the previous functions in the required number of states and computation time. We prove that these heuristic functions are all admissible and one of them is more informed than that using resource cost reachability matrix. We also propose improved versions of these heuristic functions that find a first near-optimal solution faster. In addition, we modify the heuristic function of Yu, Reyes, Cang, and Lloyd (2003b) and propose an admissible version in all states. The experimental results using a random problem generator show that the proposed heuristic functions perform better as we expected.     

Heuristic search for scheduling flexible manufacturing systems using lower bound reachability matrix

For scheduling flexible manufacturing systems efficiently, we propose new heuristic functions for A^* algorithm that is based on the T-timed Petri net. In minimizing makespan, the proposed heuristic functions are usually more efficient than the previous functions in the required number of states and computation time. We prove that these heuristic functions are all admissible and one of them is more informed than that using resource cost reachability matrix. We also propose improved versions of these heuristic functions that find a first near-optimal solution faster. In addition, we modify the heuristic function of Yu, Reyes, Cang, and Lloyd (2003b) and propose an admissible version in all states. The experimental results using a random problem generator show that the proposed heuristic functions perform better as we expected.