Interactive visualization of large state spaces

Insight into the global structure of a state space is of great help in the analysis of the underlying process. We advocate the use of visualization for this purpose and present a method to visualize the structure of very large state spaces with millions of nodes. The method uses a clustering based on an equivalence relation to obtain a simplified representation, which is used as a backbone for the display of the entire state space. With this visualization we are able to answer questions about the global structure of a state space that cannot easily be answered by conventional methods. We show this by presenting a number of visualizations of real-world protocols .     

Exploring very large state spaces using genetic algorithms

We present a novel framework for exploring very large state spaces of concurrent reactive systems. Our framework exploits application-independent heuristics using genetic algorithms to guide a state-space search toward error states. We have implemented this framework in conjunction with VeriSoft, a tool for exploring the state spaces of software applications composed of several concurrent processes executing arbitrary code. We present experimental results obtained with several examples of programs, including a C implementation of a public-key authentication protocol. We discuss heuristics and properties of state spaces that help a genetic search detect deadlocks and assertion violations. For finding errors in very large state spaces, our experiments show that a genetic search using simple heuristics can significantly outperform random and systematic searches.     

A probabilistic dynamic technique for the distributed generation of very large state spaces

Conventional methods for state space exploration are limited to the analysis of small systems because they suffer from excessive memory and computational requirements. We have developed a new dynamic probabilistic state exploration algorithm which addresses this problem for general, structurally unrestricted state spaces.

Our method has a low state omission probability and low memory usage that is independent of the length of the state vector. In addition, the algorithm can be easily parallelised. This combination of probability and parallelism enables us to rapidly explore state spaces that are an order of magnitude larger than those obtainable using conventional exhaustive techniques.

We derive a performance model of this new algorithm in order to quantify its benefits in terms of distributed run-time, speedup and efficiency. We implement our technique on a distributed-memory parallel computer and demonstrate results which compare favourably with the performance model. Finally, we discuss suitable choices for the three hash functions upon which our algorithm is based.     

Learning via human feedback in continuous state and action spaces

This paper considers the problem of extending Training an Agent Manually via Evaluative Reinforcement (TAMER) in continuous state and action spaces. Investigative research using the TAMER framework enables a non-technical human to train an agent through a natural form of human feedback (negative or positive). The advantages of TAMER have been shown on tasks of training agents by only human feedback or combining human feedback with environment rewards. However, these methods are originally designed for discrete state-action, or continuous state-discrete action problems. This paper proposes an extension of TAMER to allow both continuous states and actions, called ACTAMER. The new framework utilizes any general function approximation of a human trainer’s feedback signal. Moreover, a combined capability of ACTAMER and reinforcement learning is also investigated and evaluated. The combination of human feedback and reinforcement learning is studied in both settings: sequential and simultaneous. Our experimental results demonstrate the proposed method successfully allowing a human to train an agent in two continuous state-action domains: Mountain Car and Cart-pole (balancing).     

Potential functions based sampling heuristic for optimal path planning

Rapidly-exploring Random Tree star (RRT*) is a recently proposed extension of Rapidly-exploring Random Tree (RRT) algorithm that provides a collision-free, asymptotically optimal path regardless of obstacles geometry in a given environment. However, one of the limitation in the RRT* algorithm is slow convergence to optimal path solution. As a result it consumes high memory as well as time due to the large number of iterations utilised in achieving optimal path solution. To overcome these limitations, we propose the potential function based-RRT* that incorporates the artificial potential field algorithm in RRT*. The proposed algorithm allows a considerable decrease in the number of iterations and thus leads to more efficient memory utilization and an accelerated convergence rate. In order to illustrate the usefulness of the proposed algorithm in terms of space execution and convergence rate, this paper presents rigorous simulation based comparisons between the proposed techniques and RRT* under different environmental conditions. Moreover, both algorithms are also tested and compared under non-holonomic differential constraints.     

Sequential stratified regeneration: MCMC for large state spaces with an application to subgraph count estimation

Data Mining and Knowledge Discovery - This work considers the general task of estimating the sum of a bounded function over the edges of a graph, given neighborhood query access and where access to...     

HSM2: A new heuristic state minimization algorithm for finite state machine

This paper proposes a heuristic state minimization algorithm (HSM2) for finite state machines (FSM). HSM2 focuses on the generation and adjustment of the closed cover. First an initial closed cover is generated by heuristically selecting proper maximal compatibles to satisfy all the covering and closure conditions, and then it is adjusted to be a minimal or near minimal closed cover by heuristically removing repeated states. Experimental results show that the algorithm is faster and obtains better or the same solutions compared with conventional methods.     

An aggregation heuristic for large scale p-median problem

The p-median problem (PMP) consists of locating p facilities (medians) in order to minimize the sum of distances from each client to the nearest facility. The interest in the large-scale PMP arises from applications in cluster analysis, where a set of patterns has to be partitioned into subsets (clusters) on the base of similarity.In this paper we introduce a new heuristic for large-scale PMP instances, based on Lagrangean relaxation. It consists of three main components: subgradient column generation, combining subgradient optimization with column generation; a “core” heuristic, which computes an upper bound by solving a reduced problem defined by a subset of the original variables chosen on a base of Lagrangean reduced costs; and an aggregation procedure that defines reduced size instances by aggregating together clients with the facilities. Computational results show that the proposed heuristic is able to compute good quality lower and upper bounds for instances up to 90,000 clients and potential facilities.     

Condensed state spaces for symmetrical Coloured Petri Nets

This paper deals with state spaces. A state space is a directed graph with a node for each reachable state and an arc for each possible state change. We describe how symmetries of the modelled system can be exploited to obtain much more succinct state space analysis. The symmetries induce equivalence classes of states and equivalence classes of state changes. It is then possible to construct a condensed state space where each node represents an equivalence class of states while each arc represents an equivalence class of state changes. Such a condensed state space is often much smaller than the full state space and it is also much faster to construct. Nevertheless, it is possible to use the condensed state space to verify the same kind of behavioural properties as the full state space. hence, we do not lose analytic power.We define state spaces and condensed state spaces for a language called Coloured Petri Nets (CP-nets). This language is in widespread use for the modelling and analysis of concurrent systems. However, our techniques are general and they can be used for many other kinds of labelled transition systems. The paper does not assume that the reader is familiar with CP-nets (or Petri nets in general)—although such knowledge will, of course, be a help. The first four sections of the paper introduce the basic concepts of CP-nets. The next three sections deal with state spaces, condensed state spaces and computer tools for state space analysis. Finally, there is a short conclusion.     

Simplex filter: A novel heuristic filter for nonlinear systems state estimation

This paper introduces a new filter for nonlinear systems state estimation. The new filter formulates the state estimation problem as a stochastic dynamic optimization problem and utilizes a new stochastic method based on simplex technique to find and track the best estimation. The vertices of the simplex search the state space dynamically in a similar scheme to the optimization algorithm, known as Nelder-Mead simplex. The parameters of the proposed filter are tuned, using an information visualization technique to identify the optimal region of the parameters space. The visualization is performed using the concept of parallel coordinates. The proposed filter is applied to estimate the state of some nonlinear dynamic systems with noisy measurement and its performance is compared with other filters.     

General sampling theorems for functions in reproducing kernel Hilbert spaces

In this paper we prove general sampling theorems for functions belonging to a reproducing kernel Hilbert space (RKHS) which is also a closed subspace of a particular Sobolev space. We present details of this approach as applied to the standard sampling theory and its extension to nonuniform sampling. The general theory for orthogonal sampling sequences and nonorthogonal sampling sequences is developed. Our approach includes as concrete cases many recent extensions, for example, those based on the Sturm-Liouville transforms, Jacobi transforms, Laguerre transforms, Hankel transforms, prolate spherical transforms, etc., finite-order sampling theorems, as well as new sampling theorems obtained by specific choices of the RKHS. In particular, our setting includes nonorthogonal sampling sequences based on the theory of frames. The setting and approach enable us to consider various types of errors (truncation, aliasing, jitter, and amplitude error) in the same general context. This work was supported in part by the National Science Foundation under Grant DMS-901526.     

An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem (CCVRP) is a variation of the classical capacitated vehicle routing problem in which the objective is the minimization of the sum of arrival times at customers, instead of the total routing cost. This paper presents an adaptive large neighborhood search heuristic for the CCVRP. This algorithm is applied to a set of benchmark instances and compared with two recently published memetic algorithms.     

An efficient variable neighborhood search heuristic for very large scale vehicle routing problems

In this paper, we present an efficient variable neighborhood search heuristic for the capacitated vehicle routing problem. The objective is to design least cost routes for a fleet of identically capacitated vehicles to service geographically scattered customers with known demands. The variable neighborhood search procedure is used to guide a set of standard improvement heuristics. In addition, a strategy reminiscent of the guided local search metaheuristic is used to help escape local minima. The developed solution method is specifically aimed at solving very large scale real-life vehicle routing problems. To speed up the method and cut down memory usage, new implementation concepts are used. Computational experiments on 32 existing large scale benchmarks, as well as on 20 new very large scale problem instances, demonstrate that the proposed method is fast, competitive and able to find high-quality solutions for problem instances with up to 20,000 customers within reasonable CPU times.     

A large neighbourhood search heuristic for ship routing and scheduling with split loads

The purpose of this paper is to present and solve a new, important planning problem faced by many shipping companies dealing with the transport of bulk products. These shipping companies are committed to carrying some contract cargoes and will try to derive additional revenue from optional spot cargoes. In most of the literature on ship routing and scheduling problems a cargo cannot be transported by more than one ship. By introducing split loads this restriction is removed and each cargo can be transported by several ships. In this paper we propose a large neighbourhood search heuristic for the ship routing and scheduling problem with split loads. Computational results show that the heuristic provides good solutions to real-life instances within reasonable time. It is also shown that introducing split loads can yield significant improvements.     

Optimal compression of combinatorial state spaces

Innovations in Systems and Software Engineering - Efficiently deciding reachability for model checking problems requires storing the entire state space. We provide an information theoretical lower...     

A distributed algorithm for strong bisimulation reduction of state spaces

It is a known problem that state spaces can grow very large, which makes operating on them (including reducing them) difficult because of operational memory shortage. In an attempt to extend the size of the state spaces that can be dealt with, we designed and implemented a bisimulation reduction algorithm for distributed memory settings using message passing communication. By using message passing, the same implementation can be used on both clusters of workstations and large shared memory machines. The algorithm performs reduction of large labeled transition systems modulo strong bisimulation. We justify its correctness and termination and provide an evaluation of the worst-case time and message complexity and some performance data from a prototype implementation. Both theory and practice show that the algorithm scales up with the number of workstations.     

Properties of state spaces and their applications

Explicit model checking algorithms explore the full state space of a system. State spaces are usually treated as directed graphs without any specific features. We gather a large collection of state spaces and extensively study their structural properties. Our results show that state spaces have several typical properties, i.e., they are not arbitrary graphs. We also demonstrate that state spaces differ significantly from random graphs and that different classes of models (application domains, academic vs. industrial) have different properties. We discuss consequences of these results for model checking experiments and we point out how to exploit typical properties of state spaces in practical model checking algorithms. R. Pelánek was partially supported by GA ČR grant no. 201/07/P035.     

Learning counting functions with queries

We investigate the problem of learning disjunctions of counting functions, which are general cases of parity and modulo functions, with equivalence and membership queries. We prove that, for any prime number p, the class of disjunctions of integer-weighted counting functions with modulus p over the domain Z_qⁿ (or Zⁿ) for any given integer q 2 is polynomial time learnable using at most n + 1 equivalence queries, where the hypotheses issued by the learner are disjunctions of at most n counting functions with weights from Z_p. In general, a counting function may have a composite modulus. We prove that, for any given integer q 2, over the domain Z₂ⁿ, the class of read-once disjunctions of Boolean-weighted counting functions with modulus q is polynomial-time learnable with only one equivalence query and O(n^q) membership queries.     

General quadratic cost functions for optimal partial state feedback

For a single-input linear system, the quadratic cost functionintmin{0}max{infty}x^{T}Qx + dot{x}^{T}Rdot{x}is used to generate optimal control laws which do not feedback the highest derivative present inx. The method is applied to a fourth-order single-input system.     

Learning local objective functions for robust face model fitting

Model-based techniques have proven to be successful in interpreting the large amount of information contained in images. Associated fitting algorithms search for the global optimum of an objective function, which should correspond to the best model fit in a given image. Although fitting algorithms have been the subject of intensive research and evaluation, the objective function is usually designed ad hoc, based on implicit and domain-dependent knowledge. In this article, we address the root of the problem by learning more robust objective functions. First, we formulate a set of desirable properties for objective functions and give a concrete example function that has these properties. Then, we propose a novel approach that learns an objective function from training data generated by manual image annotations and this ideal objective function. In this approach, critical decisions such as feature selection are automated, and the remaining manual steps hardly require domain-dependent knowledge. Furthermore, an extensive empirical evaluation demonstrates that the obtained objective functions yield more robustness. Learned objective functions enable fitting algorithms to determine the best model fit more accurately than with designed objective functions.