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.     

Parallel planning via the distribution of operators

This paper describes Operator Distribution Method for parallel Planning (ODMP), a parallelization method for efficient heuristic planning. The method innovates in that it parallelizes the application of the available operators to the current state and the evaluation of the successor states using the heuristic function. In order to achieve better load balancing and a lift in the scalability of the algorithm, the operator set is initially enlarged, by grounding the first argument of each operator. Additional load balancing is achieved through the reordering of the operator set, based on the expected amount of imposed work. ODMP is effective for heuristic planners, but it can be applied to planners that embody other search strategies as well. It has been applied to GRT, a domain-independent heuristic planner, and CL, a heuristic planner for simple logistics problems, and has been thoroughly tested on a set of logistics problems adopted from the AIPS-98 planning competition, giving quite promising results.     

An approach to efficient planning with numerical fluents and multi-criteria plan quality

Dealing with numerical information is practically important in many real-world planning domains where the executability of an action can depend on certain numerical conditions, and the action effects can consume or renew some critical continuous resources, which in pddl can be represented by numerical fluents. When a planning problem involves numerical fluents, the quality of the solutions can be expressed by an objective function that can take different plan quality criteria into account.We propose an incremental approach to automated planning with numerical fluents and multi-criteria objective functions for pddl numerical planning problems. The techniques in this paper significantly extend the framework of planning with action graphs and local search implemented in the lpg planner. We define the numerical action graph (NA-graph) representation for numerical plans and we propose some new local search techniques using this representation, including a heuristic search neighborhood for NA-graphs, a heuristic evaluation function based on relaxed numerical plans, and an incremental method for plan quality optimization based on particular search restarts. Moreover, we analyze our approach through an extensive experimental study aimed at evaluating the importance of some specific techniques for the performance of the approach, and at analyzing its effectiveness in terms of fast computation of a valid plan and quality of the best plan that can be generated within a given CPU-time limit. Overall, the results show that our planner performs quite well compared to other state-of-the-art planners handling numerical fluents.     

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.     

A case-based approach to heuristic planning

Most of the great success of heuristic search as an approach to AI Planning is due to the right design of domain-independent heuristics. Although many heuristic planners perform reasonably well, the computational cost of computing the heuristic function in every search node is very high, causing the planner to scale poorly when increasing the size of the planning tasks. For tackling this problem, planners can incorporate additional domain-dependent heuristics in order to improve their performance. Learning-based planners try to automatically acquire these domain-dependent heuristics using previous solved problems. In this work, we present a case-based reasoning approach that learns abstracted state transitions that serve as domain control knowledge for improving the planning process. The recommendations from the retrieved cases are used as guidance for pruning or ordering nodes in different heuristic search algorithms applied to planning tasks. We show that the CBR guidance is appropriate for a considerable number of planning benchmarks.     

基于缩减信念状态的Conformant 规划方法

Conformant 规划问题通常转化为信念状态空间的搜索问题来求解.提出了通过降低信念状态的不确定性来提高规划求解效率的方法.首先给出缩减信念状态的增强爬山算法,在此基础上,提出了基于缩减信念状态的Conformant 规划方法,设计了CFF-Lite 规划系统.该规划器的求解过程包括两次增强爬山过程,分别用于缩减信念状态和搜索目标.首先对初始信念状态作最大程度的缩减,提高启发函数的准确性;然后从缩减后的信念状态开始执行启发式搜索.实验结果表明,CFF-Lite 规划系统通过快速缩减信念状态降低了问题的求解难度,在大多数问题上,求解效率和规划解质量与Conformant-FF 相比,都有显著的提高.     

Sampling-based online motion planning for mobile robots: utilization of Tabu search and adaptive neuro-fuzzy inference system

Despite the proven advantages of sampling-based motion planning algorithms, their inability to handle online navigation tasks and providing low-cost solutions make them less efficient in practice. In this paper, a novel sampling-based algorithm is proposed which is able to plan in an unknown environment and provides solutions with lower cost in terms of path length, runtime and stability of the results. First, a fuzzy controller is designed which incorporates the heuristic rules of Tabu search to enable the planner for solving online navigation tasks. Then, an adaptive neuro-fuzzy inference system (ANFIS) is proposed such that it constructs and optimizes the fuzzy controller based on a set of given input/output data. Furthermore, a heuristic dataset generator is implemented to provide enough data for the ANFIS using a randomized procedure. The performance of the proposed algorithm is evaluated through simulation in different motion planning queries. Finally, the proposed planner is compared to some of the similar motion planning algorithms to support the claim of superiority of its performance.

     

Exploiting graphical processing units for data‐parallel scientific applications

Graphical processing units (GPUs) have recently attracted attention for scientific applications such as particle simulations. This is partially driven by low commodity pricing of GPUs but also by recent toolkit and library developments that make them more accessible to scientific programmers. We discuss the application of GPU programming to two significantly different paradigms—regular mesh field equations with unusual boundary conditions and graph analysis algorithms. The differing optimization techniques required for these two paradigms cover many of the challenges faced when developing GPU applications. We discuss the relevance of these application paradigms to simulation engines and games. GPUs were aimed primarily at the accelerated graphics market but since this is often closely coupled to advanced game products it is interesting to speculate about the future of fully integrated accelerator hardware for both visualization and simulation combined. As well as reporting the speed‐up performance on selected simulation paradigms, we discuss suitable data‐parallel algorithms and present code examples for exploiting GPU features like large numbers of threads and localized texture memory. We find a surprising variation in the performance that can be achieved on GPUs for our applications and discuss how these findings relate to past known effects in parallel computing such as memory speed‐related super‐linear speed up. Copyright © 2009 John Wiley & Sons, Ltd.     

Landmark-based heuristic online contingent planning

In contingent planning problems, agents have partial information about their state and use sensing actions to learn the value of some variables. When sensing and actuation are separated, plans for such problems can often be viewed as a tree of sensing actions, separated by conformant plans consisting of non-sensing actions that enable the execution of the next sensing action. We propose a heuristic, online method for contingent planning which focuses on identifying the next useful sensing action. We select the next sensing action based on a landmark heuristic, adapted from classical planning. We discuss landmarks for plan trees, providing several alternative definitions and discussing their merits. The key part of our planner is the novel landmarks-based heuristic, together with a projection method that uses classical planning to solve the intermediate conformant planning problems. The resulting heuristic contingent planner solves many more problems than state-of-the-art, translation-based online contingent planners, and in most cases, much faster, up to 3 times faster on simple problems, and 200 times faster on non-simple domains.     

Hypercubic storage layout and transforms in arbitrary dimensions using GPUs and CUDA

Many simulations in the physical sciences are expressed in terms of rectilinear arrays of variables. It is attractive to develop such simulations for use in 1‐, 2‐, 3‐ or arbitrary physical dimensions and also in a manner that supports exploitation of data‐parallelism on fast modern processing devices. We report on data layouts and transformation algorithms that support both conventional and data‐parallel memory layouts. We present our implementations expressed in both conventional serial C code as well as in NVIDIA's Compute Unified Device Architecture concurrent programming language for use on general purpose graphical processing units. We discuss: general memory layouts; specific optimizations possible for dimensions that are powers‐of‐two and common transformations, such as inverting, shifting and crinkling. We present performance data for some illustrative scientific applications of these layouts and transforms using several current GPU devices and discuss the code and speed scalability of this approach. Copyright © 2010 John Wiley & Sons, Ltd.     

Experimental evaluation of pheromone models in ACOPlan

In this paper the system ACOPlan for planning with non uniform action cost is introduced and analyzed. ACOPlan is a planner based on the ant colony optimization framework, in which a colony of planning ants searches for near optimal solution plans with respect to an overall plan cost metric. This approach is motivated by the strong similarity between the process used by artificial ants to build solutions and the methods used by state?Cbased planners to search solution plans. Planning ants perform a stochastic and heuristic based search by interacting through a pheromone model. The proposed heuristic and pheromone models are presented and compared through systematic experiments on benchmark planning domains. Experiments are also provided to compare the quality of ACOPlan solution plans with respect to state of the art satisficing planners. The analysis of the results confirm the good performance of the Action?CAction pheromone model and points out the promising performance of the novel Fuzzy?CLevel?CAction pheromone model. The analysis also suggests general principles for designing performant pheromone models for planning and further extensions of ACOPlan to other optimization models.     

图规划框架下的启发式搜索的研究与发展

随着智能规划研究的深入,以往的规划器已不能满足实际应用的需要.为了提高规划器求解实际问题的能力,启发式搜索产生了.对近10年来各种启发式搜索方法进行了分析,指出了它们的优缺点,并进行了比较.同时对智能规划及其启发式搜索的未来发展方向进行了分析与预测,旨在让研究和关心该领域的学者较为全面地了解这一领域.     

Localized event-based reasoning for multiagent domain1

This paper presents the GEM concurrency model and GEMPLAN, a multiagent planner based on this model. Unlike standard state-based AI representations, GEM is unique in its explicit emphasis on events and domain structure. In particular, a world domain is modeled as a set of regions composed of interrelated events. Event-based temporal-logic constraints are then associated with each region to delimit legal domain behavior. The GEMPLAN planner directly reflects this emphasis on domain structure and constraints. It can be viewed as a general-purpose constraint satisfaction facility which constructs a network of interrelated events (a “plan”) that is subdivided into regions (“subplans”), satisfies all applicable regional constraints, and also achieves some stated goal. GEMPLAN extends and generalizes previous planning architectures in the range of constraint forms it handles and in the flexibility of its constraint satisfaction search strategy. One critical aspect of our work has been an emphasis on localized reasoning—techniques that make explicit use of domain structure. For example, GEM localizes the applicability of domain constraints and imposes additional “locality constraints” on the basis of domain structure. Together, constraint localization and locality constraints provide semantic information that can be used to alleviate several aspects of the frame problem for multiagent domains. The GEMPLAN planner reflects the use of locality by subdividing its constraint satisfaction search space into regional planning search spaces. Utilizing constraint and property localization, GEMPLAN can pinpoint and rectify interactions among these regional search spaces, thus reducing the burden of “interaction analysis” ubiquitous to most planning systems. Because GEMPLAN is specifically geared towards parallel, multiagent domains, we believe that its natural application areas will include scheduling and other forms of organizational coordination.     

Strong planning under partial observability

Rarely planning domains are fully observable. For this reason, the ability to deal with partial observability is one of the most important challenges in planning. In this paper, we tackle the problem of strong planning under partial observability in nondeterministic domains: find a conditional plan that will result in a successful state, regardless of multiple initial states, nondeterministic action effects, and partial observability.We make the following contributions. First, we formally define the problem of strong planning within a general framework for modeling partially observable planning domains. Second, we propose an effective planning algorithm, based on and-or search in the space of beliefs. We prove that our algorithm always terminates, and is correct and complete. In order to achieve additional effectiveness, we leverage on a symbolic, bdd-based representation for the domain, and propose several search strategies. We provide a thorough experimental evaluation of our approach, based on a wide selection of benchmarks. We compare the performance of the proposed search strategies, and identify a uniform winner that combines heuristic distance measures with mechanisms that reduce runtime uncertainty. Then, we compare our planner mbp with other state-of-the art-systems. mbp is able to outperform its competitor systems, often by orders of magnitude.     

Action Planning for Directed Model Checking of Petri Nets

Petri nets are fundamental to the analysis of distributed systems especially infinite-state systems. Finding a particular marking corresponding to a property violation in Petri nets can be reduced to exploring a state space induced by the set of reachable markings. Typical exploration(reachability analysis) approaches are undirected and do not take into account any knowledge about the structure of the Petri net. This paper proposes heuristic search for enhanced exploration to accelerate the search. For different needs in the system development process, we distinguish between different sorts of estimates.Treating the firing of a transition as an action applied to a set of predicates induced by the Petri net structure and markings, the reachability analysis can be reduced to finding a plan to an AI planning problem. Having such a reduction broadens the horizons for the application of AI heuristic search planning technology. In this paper we discuss the transformations schemes to encode Petri nets into PDDL. We show a concise encoding of general place-transition nets in Level 2 PDDL2.2, and a specification for bounded place-transition nets in ADL/STRIPS. Initial experiments with an existing planner are presented.     

Parallelization and scalability issues of a multilevel elastohydrodynamic lubrication solver

The computation of numerical solutions to elastohydrodynamic lubrication problems is only possible on fine meshes by using a combination of multigrid and multilevel techniques. In this paper, we show how the parallelization of both multigrid and multilevel multi‐integration for these problems may be accomplished and discuss the scalability of the resulting code. A performance model of the solver is constructed and used to perform an analysis of the results obtained. Results are shown with good speed‐ups and excellent scalability for distributed memory architectures and in agreement with the model. Copyright © 2006 John Wiley & Sons, Ltd.     

Parallel eigenvalue calculation based on multiple shift–invert Lanczos and contour integral based spectral projection method

We discuss the possibility of using multiple shift–invert Lanczos and contour integral based spectral projection method to compute a relatively large number of eigenvalues of a large sparse and symmetric matrix on distributed memory parallel computers. The key to achieving high parallel efficiency in this type of computation is to divide the spectrum into several intervals in a way that leads to optimal use of computational resources. We discuss strategies for dividing the spectrum. Our strategies make use of an eigenvalue distribution profile that can be estimated through inertial counts and cubic spline fitting. Parallel sparse direct methods are used in both approaches. We use a simple cost model that describes the cost of computing k eigenvalues within a single interval in terms of the asymptotic cost of sparse matrix factorization and triangular substitutions. Several computational experiments are performed to demonstrate the effect of different spectrum division strategies on the overall performance of both multiple shift–invert Lanczos and the contour integral based method. We also show the parallel scalability of both approaches in the strong and weak scaling sense. In addition, we compare the performance of multiple shift–invert Lanczos and the contour integral based spectral projection method on a set of problems from density functional theory (DFT).     

On the importance of breaking ties in the relaxed plan heuristic

The relaxed plan heuristic is a domain-independent heuristic for automated planning that computes an estimate of the cost for achieving the goals from a given state. This heuristic is based on the idea of solving a relaxed version of the planning task. Due to the great size of the state space, most heuristic search algorithms in planning suffer from scalability problems. These algorithms have to evaluate a great amount of states, and the time devoted to heuristic evaluations is one of the causes of the scalability problems. We argue that one way to lighten this problem is breaking ties in the heuristic value using additional information computed during the relaxed plan construction. We add a complementary value to the heuristic, allowing algorithms to discriminate between states with relaxed plans of the same length but with a different difficulty. The experimental evaluation in some planning benchmarks shows that the modification to the original heuristic can reduce the number of evaluated nodes for the most common algorithms used in heuristic planning.     

Planning with Multistep Forward Search with Forced Goal‐Ordering Constraints

To solve a real‐world planning problem with interfering subgoals, it is essential to perform early detection of subgoal dependencies and achieve the subgoals in the correct order. This is also the case for planning problems with forced goal‐ordering (FGO) constraints. In automated planning, forward search with FGO constraints has been proposed many times over the years, but there are still major difficulties in realizing these FGOs in plan generation. Many existing methods such as goal agenda manager and ordered landmarks cannot detect the FGOs accurately, and thus, the undiscovered ordering relationship may cause the forward search to suffer from deadlocks. In this article, we put forward an approach via an effective search heuristic to constrain a planner to satisfy the FGOs. We make use of an atomic goal‐achievement graph in a look‐ahead search under the FGO constraints. This allows a forward search strategy to plan forward efficiently in multiple steps toward a goal state along a search path. Experimental results illustrate that, by avoiding deadlocks, we can solve more benchmark planning problems more efficiently than previous approaches. We also prove several formal properties for search that are related to FGO detection.     

Anytime pack search

Heuristic search is one of the fundamental problem solving techniques in artificial intelligence, which is used in general to efficiently solve computationally hard problems in various domains, especially in planning and optimization. In this paper, we present an anytime heuristic search algorithm called anytime pack search (APS) which produces good quality solutions quickly and improves upon them over time, by focusing the exploration on a limited set of most promising nodes in each iteration. We discuss the theoretical properties of APS and show that it is complete. We also present the complexity analysis of the proposed algorithm on a tree state-space model and show that it is asymptotically of the same order as that of A*, which is a widely applied best-first search method. Furthermore, we present a parallel formulation of the proposed algorithm, called parallel anytime pack search (PAPS), which is applicable for searching tree state-spaces. We theoretically prove the completeness of PAPS. Experimental results on the sliding-tile puzzle problem, traveling salesperson problem, and single machine scheduling problem depict that the proposed sequential algorithm produces much better anytime performance when compared to some of the existing methods. Also, the proposed parallel formulation achieves super-linear speedups over the sequential method.