Search

Recent advances in solving constraint satisfaction problems (CSPs) and heuristic search have made it possible to solve classical planning problems significantly faster. There is an increasing amount of work on extending these advances to solving planning problems in more expressive languages. These problems and languages contain metric time, quantifiers and resource quantities. SAT-based approaches are very effective at optimal planning. In this paper we report on SAT-based temporal planner T-SATPLAN. One key challenge in the development of planners casting planning as SAT or CSP is the identification of constraints which are satisfied if and only if there is a plan of k steps. In this paper we show how such a SAT encoding can be synthesized for temporal planning. As part of this, we generalize explanatory frame axioms for two states of fluents (true, false) to three states of fluents (true, false and undefined). We show how this SAT encoding can be simplified. We discuss two additional SAT encodings of temporal planning. The encoding schemes make it easier to exploit progress in SAT and CSP solving to solve temporal planning problems. We also report on an experimental evaluation of T-SATPLAN using one such encoding scheme. The evaluation shows that significantly large SAT encodings of temporal planning problems can be solved extremely fast. [ABSTRACT FROM AUTHOR]

General functional decomposition is mainly perceived as a logic synthesis method for implementing Boolean functions into FPGA-based architectures. However it also has important applications in many other fields of modern engineering and science. In this paper, advantages of functional decomposition are demonstrated on "real life" examples. Application of decomposition-based methods in other fields of modern engineering is presented. In the case of decision tables, application of decomposition methods leads to significant benefits in the analysis process of data dependencies, especially in cases when the input decision tables are unmanageably large. Experimental results demonstrate that it can help implementing sequential machines using flip-flops or ROM memory. It also can be efficiently used as multilevel logic synthesis method for VLSI technology. [ABSTRACT FROM AUTHOR]

This paper introduces a new ensemble technique, cluster-based concurrent decomposition (CBCD) that induces an ensemble of classifiers by decomposing the training set into mutually exclusive sub-samples of equal-size. The CBCD algorithm first clusters the instance space by using the K-means clustering algorithm. Afterwards it produces disjoint sub-samples using the clusters in such a way that each sub-sample is comprised of tuples from all clusters and hence represents the entire dataset. An induction algorithm is applied in turn to each subset, followed by a voting mechanism that combines the classifier's predictions. The CBCD algorithm has two tuning parameters: the number of clusters and the number of subsets to create. Using a suitable meta-learning it is possible to tune these parameters properly. In the experimental study we conducted, the CBCD algorithm, using an embedded C4.5 algorithm, outperformed the bagging algorithm of the same computational complexity. [ABSTRACT FROM AUTHOR]

The data staging problem involves positioning data within a distributed heterogeneous computing environment such that programs can access the requested data faster. This problem exists because applications constantly need up-to-date information to enable users to make decisions. In addition, these requests for information are normally occurring in an oversubscribed network. In such a heterogeneous distributed computing environment, each data storage location and intermediate node may have different data available, storage limitations, and communication links available. Sites in the heterogeneous network request data items and each request has an associated deadline and priority. This work extends the research presented in [ThT00] where a basic version of the data staging problem with static information was presented. This work introduces three new cost criteria and two new bounds on performance that were designed taking into account results from [ThT00]. A subset of the possible procedure/cost criterion combinations are evaluated in simulation studies considering a different priority weighting scheme, different average number of links used to satisfy each data request, and different network loadings, than was considered in [ThT00]. This paper also introduces a variable time, variable accuracy approach for using data items with "more desirable" and "less desirable" versions. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to present a new hybrid Elastic Net (EN) algorithm, by integrating the ideas of the Self Organization Map (SOM) and the strategy of the gradient ascent into the EN algorithm. The new hybrid algorithm has two phases: an EN phase based on SOM and a gradient ascent phase. We acquired the EN phase based on SOM by analyzing the weight between a city and its converging and non-converging nodes at the limit when the EN algorithm produces a tour. Once the EN phase based on SOM stuck in local minima, the gradient ascent algorithm attempts to fill up the valley by modifying parameters in a gradient ascent direction of the energy function. These two phases are repeated until the EN gets out of local minima and produces the short or better tour through cities. We test the algorithm on a set of TSP. For all instances, the algorithm is showed to be capable of escaping from the EN local minima and producing more meaningful tour than the EN. [ABSTRACT FROM AUTHOR]

We present a novel case-based plan recognition method that interprets observations of plan behavior using an incrementally constructed case library of past observations. The technique is novel in several ways. It combines plan recognition with case-based reasoning and leverages the strengths of both. The representation of a plan is a sequence of action-state pairs rather than only the actions. The technique compensates for the additional complexity with a unique abstraction scheme augmented by pseudo-isomorphic similarity relations to represent indices into the case base. Past cases are used to predict subsequent actions by adapting old actions and their arguments. Moreover, the technique makes predictions despite observations of unknown actions. This paper evaluates the algorithms and their implementation both analytically and empirically. The evaluation criteria include prediction accuracy at both an abstract and a concrete level and across multiple domains with and without case-adaptation. In each domain the system starts with an empty case base that grows to include thousands of past observations. Results demonstrate that this new method is accurate, robust, scalable, and general across domains. [ABSTRACT FROM AUTHOR]