Finding diverse solutions has become important in many combinatorial search domains, including Automated Planning, Path Planning and Constraint Programming. Much of the work in these directions has however focussed on coming up with appropriate diversity metrics and compiling those metrics in to the solvers/planners. Most approaches use linear-time greedy algorithms for exploring the state space of solution combinations for generating a diverse set of solutions, limiting not only their completeness but also their effectiveness within a time bound. In this paper, we take a combinatorial search perspective on generating diverse solutions. We present a generic bi-level optimization framework for finding cost-sensitive diverse solutions. We propose complete methods under this framework, which guarantee finding a set of cost sensitive diverse solutions satisficing the given criteria whenever there exists such a set. We identify various aspects that affect the performance of these exhaustive algorithms and propose techniques to improve them. Experimental results show the efficacy of the proposed framework compared to an existing greedy approach.

Given the growing importance of large-scale graph analytics, there is a need to improve the performance of graph analysis frameworks without compromising on productivity. GraphMat is our solution to bridge this gap between a user-friendly graph analytics framework and native, hand-optimized code. GraphMat functions by taking vertex programs and mapping them to high performance sparse matrix operations in the backend. We thus get the productivity benefits of a vertex programming framework without sacrificing performance. GraphMat is a single-node multicore graph framework written in C++ which has enabled us to write a diverse set of graph algorithms with the same effort compared to other vertex programming frameworks. GraphMat performs 1.1-7X faster than high performance frameworks such as GraphLab, CombBLAS and Galois. GraphMat also matches the performance of MapGraph, a GPU-based graph framework, despite running on a CPU platform with significantly lower compute and bandwidth resources. It achieves better multicore scalability (13-15X on 24 cores) than other frameworks and is 1.2X off native, hand-optimized code on a variety of graph algorithms. Since GraphMat performance depends mainly on a few scalable and well-understood sparse matrix operations, GraphMat can naturally benefit from the trend of increasing parallelism in future hardware.

Fault-tolerance of embedded control systems is of great importance, given their wide usage in various domains such as aeronautics, automotive, medical, and so on. Signal perturbations such as small amounts of noise, shift, and spikes, can sometimes severely hamper the performance of the system, apart from complete failure of components and links. Finding minimal counterexamples (perturbations on the system leading to violation of fault-tolerance requirements) can be of great assistance to control system designers in understanding and adjusting the fault-tolerance behavior of the system. Fault injection is an effective method for dependability analysis of such systems. In this paper, we introduce the concept of dominating sets of perturbations, and define a minimal set of counterexamples called the basis. We propose effective methods using a simulation-based fault injection technique on Simulink models for finding the basis set at an early stage of design, given the fault specification and fault-tolerance requirements. Experimental results on two different control system examples from the Simulink automotive library demonstrate the efficacy of the proposed framework.

We present a mobility simulation framework that simulates the movement behaviors of people to generate spatiotemporal movement data. There is a growing interest in applications that make use of patterns mined from spatio-temporal data. However, since the availability of actual spatio-temporal movement data in the public domain is limited, it is useful to have simulation frameworks that generate data close to the real life behavior of people, so that data mining techniques can be tested. We argue that modeling group behavior effectively is a key element of any real-life simulation framework, because there are many applications that require the knowledge of groups and events. In this work, we propose generic models to represent individual and group movement behaviors. We present an algorithm that takes various behaviors created using the proposed models, and generates spatio-temporal movement data for as many individuals as needed. Experimental analysis shows the efficacy of the proposed framework handling a broad spectrum of behaviors with high scalability.

This work presents a static-analysis based method for analyzing the robustness of a given embedded control system design, in the presence of quality-faults in sensors, software components, and inter-connections. The method characterizes the individual components of the system by storing the relations between the precision of inputs and the precision of outputs in what we call, lookup tables (LUTs). A network of LUTs thus formed which represent the given control system is converted into a satisfiability modulo theory (SMT) instance, such that a satisfying assignment corresponds to a potential counterexample (the set of quality-faults which violate the given fault-tolerance requirements) or hot-spot in the design. Hot-spots obtained in this manner are counter-verified through simulation to filter the false-positives. Experimental results on the fault-tolerant fuel controller from Simulink automotive library demonstrate the efficacy of the proposed approach.

This paper presents a heuristic-search algorithm called Memory-bounded Anytime Window A∗ (MAWA∗), which is complete, anytime, and memory bounded. MAWA∗ uses the window-bounded anytime-search methodology of AWA∗ as the basic framework and combines it with the memory-bounded A∗ -like approach to handle restricted memory situations. Simple and efficient versions of MAWA∗ targeted for tree search have also been presented. Experimental results of the sliding-tile puzzle problem and the traveling-salesman problem show the significant advantages of the proposed algorithm over existing methods.