Sequential Monte Carlo in reachability heuristics for probabilistic planning

Some of the current best conformant probabilistic planners focus on finding a fixed length plan with maximal probability. While these approaches can find optimal solutions, they often do not scale for large problems or plan lengths. As has been shown in classical planning, heuristic search outperforms bounded length search (especially when an appropriate plan length is not given a priori). The problem with applying heuristic search in probabilistic planning is that effective heuristics are as yet lacking.In this work, we apply heuristic search to conformant probabilistic planning by adapting planning graph heuristics developed for non-deterministic planning. We evaluate a straight-forward application of these planning graph techniques, which amounts to exactly computing a distribution over many relaxed planning graphs (one planning graph for each joint outcome of uncertain actions at each time step). Computing this distribution is costly, so we apply Sequential Monte Carlo (SMC) to approximate it. One important issue that we explore in this work is how to automatically determine the number of samples required for effective heuristic computation. We empirically demonstrate on several domains how our efficient, but sometimes suboptimal, approach enables our planner to solve much larger problems than an existing optimal bounded length probabilistic planner and still find reasonable quality solutions.     

面向目标的博弈搜索策略及其应用

博弈是人工智能研究的重要分支,它涉及人工智能中的推理技术、搜索方法和决策规划。而搜索策略是博弈问题的关键。针对搜索技术中存在的由于搜索空间巨大而引起的搜索效率下降的缺点,结合五子棋的特点,探讨了相应博弈问题的求解策略,提出一种结合PVS算法、静态着法启发、历史启发算法的搜索策略。实验结果证明,该算法不但能保证博弈水平,还能得到较好的搜索效率。     

Goal distance estimation for automated planning using neural networks and support vector machines

Many of today’s most successful planners perform a forward heuristic search. The accuracy of the heuristic estimates and the cost of their computation determine the performance of the planner. Thanks to the efforts of researchers in the area of heuristic search planning, modern algorithms are able to generate high-quality estimates. In this paper we propose to learn heuristic functions using artificial neural networks and support vector machines. This approach can be used to learn standalone heuristic functions but also to improve standard planning heuristics. One of the most famous and successful variants for heuristic search planning is used by the Fast-Forward (FF) planner. We analyze the performance of standalone learned heuristics based on nature-inspired machine learning techniques and employ a comparison to the standard FF heuristic and other heuristic learning approaches. In the conducted experiments artificial neural networks and support vector machines were able to produce standalone heuristics of superior accuracy. Also, the resulting heuristics are computationally much more performant than related ones.     

N皇后问题的启发式算法探讨

搜索策略的选择与设计是人工智能领域问题求解的核心问题之一,直接影响到问题求解过程中存储空间的占用和计算的复杂性,影响到问题求解的效率。在给出N皇后问题形式化描述和现有搜索算法的基础上,设计了3种解决N皇后问题的启发式算法,并将其与深度优先和宽度优先等搜索策略进行了分析和比较,得出了几点关于设计启发式算法的启示。     

Symbolic and numeric knowledge integration in multiple fault troubleshooting

Many expert system researchers have reported in recent years that situation-action symbolic production rules frequently fail to provide adequate knowledge representation schemes without resorting to numeric computation. However, despite the need to integrate symbolic and quantitative computation into one coherent framework of knowledge, surprisingly few architectures have been proposed for achieving this goal. This paper explores the integration of qualitative and numeric processing in expert systems. We address the topic with respect to the construction of expert systems that perform the tasks of design and multiple fault troubleshooting. This paper shows that these tasks can be handled effectively when an appropriate interface is established between the heuristic and the numeric knowledge-based components. Specifically, we demonstrate how to interface heuristic knowledge with non-linear optimization models in order to allow an expert system greater expressiveness. An actual example is presented from the machining domain.     

Task allocation for maximizing reliability of distributed computing systems using honeybee mating optimization

This paper deals with the problem of task allocation (i.e., to which processor should each task of an application be assigned) in heterogeneous distributed computing systems with the goal of maximizing the system reliability. The problem of finding an optimal task allocation is known to be NP-hard in the strong sense. We propose a new swarm intelligence technique based on the honeybee mating optimization (HBMO) algorithm for this problem. The HBMO based approach combines the power of simulated annealing, genetic algorithms with a fast problem specific local search heuristic to find the best possible solution within a reasonable computation time. We study the performance of the algorithm over a wide range of parameters such as the number of tasks, the number of processors, the ratio of average communication time to average computation time, and task interaction density of applications. The effectiveness and efficiency of our algorithm are demonstrated by comparing it with recently proposed task allocation algorithms for maximizing system reliability available in the literature.     

用VC++实现基于A*算法的八数码问题

在人工智能领域中,八数码问题一直都是一个游戏难题。介绍了八数码问题,然后在启发式搜索算法上对A*算法定义进行了解释,并在其旨在提高搜索效率的方面作了比较详尽的介绍,详细描述了基于图搜索算法的解决此类问题的一种启发式搜索算法———A*算法。再依据这种算法用可视化编程语言VC 6.0来实现八数码问题的求解过程,取得了预期的搜索解,提高了搜索效率。     

基于PVM的启发式搜索的并行计算模型设计

通过分析人工智能中的A和A^*启发式搜索,提出了通过PVM工具包,设计和实现A和A^*启发式搜索的并行计算模型。在启发搜索过程中同时进行评估函数计算,使计算的速度加快。解决了在搜索解空间庞大,评估函数计算复杂的情况下,使用单计算机计算速度慢的问题。该文实现了基于PVM的启发式搜索过程,该模型可应用于一般性启发式搜索问题的并行计算模型。     

基于知识库的启发式智能搜索引擎的设计

为了实现智能化搜索,基于知识库的启发式智能搜索引擎(KHISE)采用基于Web挖掘技术的聚焦爬行器采集信息;使用正则表达式、自然语言理解等技术抽取信息并用向量空间距离测度算法(VSM)对信息进行分类;使用启发式搜索等技术支持信息查询.信息收集、信息处理和信息查询3个模块既相互独立又相互关联.在实验室环境下实现的原型所得到的结果表明,研究设计的基于知识库的启发式智能搜索引擎不但提高了信息处理的效率和效果,还在很大程度上弥补了现有搜索系统的局限性.     

A quantum production model

The production system is a theoretical model of computation relevant to the artificial intelligence field allowing for problem solving procedures such as hierarchical tree search. In this work we explore some of the connections between artificial intelligence and quantum computation by presenting a model for a quantum production system. Our approach focuses on initially developing a model for a reversible production system which is a simple mapping of Bennett’s reversible Turing machine. We then expand on this result in order to accommodate for the requirements of quantum computation. We present the details of how our proposition can be used alongside Grover’s algorithm in order to yield a speedup comparatively to its classical counterpart. We discuss the requirements associated with such a speedup and how it compares against a similar quantum hierarchical search approach.     

状态空间的启发式搜索方法研究

对人工智能中用于状态空间问题求解的启发式搜索方法－A算法和A^*算法进行了详细分析，并指出了影响搜索算法启发能力的主要因素和提高搜索效率的措施。     

Depth-m search in branch-and-bound algorithms

A new search strategy, called depth-m search, is proposed for branch-and-bound algorithms, wherem is a parameter to be set by the user. In particular, depth-1 search is equivalent to the conventional depth-first search, and depth- search is equivalent to the general heuristic search (including best-bound search as a special case). It is confirmed by computational experiment that the performance of depth-m search continuously changes from that, of depth-first search to that of heuristic search, whenm is changed from 1 to . The exact upper bound on the size of the required memory space is derived and shown to be bounded byO(n^m), wheren is the problem size. Some methods for controllingm during computation are also proposed and compared, to carry out the entire computation within a given memory space bound.     

An adaptive ant colony optimization algorithm for constructing cognitive diagnosis tests

A critical issue in the applications of cognitive diagnosis models (CDMs) is how to construct a feasible test that achieves the optimal statistical performance for a given purpose. As it is hard to mathematically formulate the statistical performance of a CDM test based on the items used, exact algorithms are inapplicable to the problem. Existing test construction heuristics, however, suffer from either limited applicability or slow convergence. In order to efficiently approximate the optimal CDM test for different construction purposes, this paper proposes a novel test construction method based on ant colony optimization (ACO-TC). This method guides the test construction procedure with pheromone that represents previous construction experience and heuristic information that combines different item discrimination indices. Each test constructed is evaluated through simulation to ensure convergence towards the actual optimum. To further improve the search efficiency, an adaptation strategy is developed, which adjusts the design of heuristic information automatically according to the problem instance and the search stage. The effectiveness and efficiency of the proposed method is validated through a series of experiments with different conditions. Results show that compared with traditional test construction methods of CDMs, the proposed ACO-TC method can find a test with better statistical performance at a faster speed.     

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.     

A*算法在Shortest-Path方面的优化研究

在游戏和地理信息系统开发等领域中,专门针对最短路径搜索方面的优化研究较多,尤其是最短路径中启发式搜索算法中的A*算法的效率优化研究.本文将针对在人工智能或算法研究中的使用的地图大多数是基于任意图而不是网格图的状况,通过任意图与网格图及方向的相结合,提出了三种优化A*算法的启发式函数搜索策略,较好地减小了算法搜索的范围和规模,有效地提高了A*算法的运行效率.最后的实验结果显示,与传统的A*算法相比较,优化启发搜索策略后的A*算法寻径更快速,更准确,计算效率更高.     

Solving the stochastic dynamic lot-sizing problem through nature-inspired heuristics

We investigate the dynamic lot-size problem under stochastic and non-stationary demand over the planning horizon. The problem is tackled by using three popular heuristic methods from the fields of evolutionary computation and swarm intelligence, namely particle swarm optimization, differential evolution and harmony search. To the best of the authors' knowledge, this is the first investigation of the specific problem with approaches of this type. The algorithms are properly manipulated to fit the requirements of the problem. Their performance, in terms of run-time and solution accuracy, is investigated on test cases previously used in relevant works. Specifically, the lot-size problem with normally distributed demand is considered for different planning horizons, varying from 12 up to 48 periods. The obtained results are analyzed, providing evidence on the efficiency of the employed approaches as promising alternatives to the established Wagner–Whitin algorithm, as well as hints on their proper configuration.     

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.     

Solving Systems of Difference Constraints Incrementally with Bidirectional Search

We propose an incremental algorithm for the problem of maintaining systems of difference constraints. As a difference from the unidirectional approach of Ramalingam et al., it employs bidirectional search, which is similar to that of Alpern et al., and has a bounded runtime complexity in the worst case in terms of the size of changes. The major challenge is how to update the solution efficiently after the bidirectional search discovers a region that needs changes. Experimental results show that our approach is much faster in runtime and generates much smaller changes than the algorithm in Ramalingam et al. We also perform an experimental study on the edge value heuristic Alpern et al. and results show that a simpler method may be faster in practice.     

On randomization and discovery

In the first part of this paper, traditional computability theory is extended to prove that the attainable density of knowledge is virtually unbounded. That is, the more bits available for storage, the more information that can be stored, where the density of information per bit cannot be bounded above. In the second part, the paper explains how machine intelligence becomes possible as a result of the capability for creating, storing, and retrieving virtually unlimited information/knowledge. It follows from this theory that there is no such thing as a valid non-trivial proof, which in turn implies the need for heuristic search/proof techniques. Two examples are presented to show how heuristics can be developed, which are randomizations of knowledge - establishing the connection with the first part of the paper. Even more intriguing, it is shown that heuristic proof techniques are to formal proof techniques what fuzzy logic is to classical logic.     

Theoretical comparisons of search strategies in branch-and-bound algorithms

Four known search strategies used in branch-and-bound algorithms-heuristic search, depth-first search, best-bound search, and breadth-first search-are theoretically compared from the viewpoint of the performance of the resulting algorithms. Heuristic search includes the other three as special cases. Since heuristic search is determined by a heuristic functionh, we first investigate how the performance of the resulting algorithms depends onh. In particular, we show that heuristic search is stable in the sense that a slight change inh causes only a slight change in its performance. The best and the worst heurstic functions are clarified, and also discussed is how the heuristic functionh should be modified to obtain a branch-and-bound algorithm with an improved performance. Finally, properties and limitations of depth-first search, best-bound search, and breadth-first search viewed as special cases of heuristic search are considered. In particular, it is shown that the stability observed for heuristic search no longer holds for depth-first search.