Search

In the context of assistive robotics, myocontrol is one of the so-far unsolved problems of upper-limb prosthetics. It consists of swiftly, naturally, and reliably converting biosignals, non-invasively gathered from an upper-limb disabled subject, into control commands for an appropriate self-powered prosthetic device. Despite decades of research, traditional surface electromyography cannot yet detect the subject’s intent to an acceptable degree of reliability, that is, enforce an action exactly when the subject wants it to be enforced.. In this paper, we tackle one such kind of mismatch between the subject’s intent and the response by the myocontrol system, and show that formal verification can indeed be used to mitigate it. Eighteen intact subjects were engaged in two target achievement control tests in which a standard myocontrol system was compared to two “repaired” ones, one based on a non-formal technique, thus enforcing no guarantee of safety, and the other using the satisfiability modulo theories (SMT) technology to rigorously enforce the desired property. The experimental results indicate that both repaired systems exhibit better reliability than the non-repaired one. The SMT-based system causes only a modest increase in the required computational resources with respect to the non-formal technique; as opposed to this, the non-formal technique can be easily implemented in existing myocontrol systems, potentially increasing their reliability. [ABSTRACT FROM AUTHOR]

Model-based synthesis allows to generate plans to achieve high-level tasks while satisfying certain properties of interest. However, when such plans are executed on concrete systems, several modeling assumptions may be challenged, jeopardizing their real applicability. This paper presents an integrated system for generating, executing and monitoring optimal-by-construction plans for multi-robot systems. This system unites the power of Optimization Modulo Theories with the flexibility of an on-line executive, providing optimal solutions for high-level task planning, and runtime feedback on their feasibility. After presenting how our system orchestrates static and runtime components, we demonstrate its capabilities using the RoboCup Logistics League as testbed. We do not only present our final solution but also its chronological development, and draw some general observations for the development of OMT-based approaches. [ABSTRACT FROM AUTHOR]

Resolution is the rule of inference at the basis of most procedures for automated reasoning. In these procedures, the input formula is first translated into an equisatisfiable formula in conjunctive normal form (CNF) and then represented as a set of clauses. Deduction starts by inferring new clauses by resolution, and goes on until the empty clause is generated or satisfiability of the set of clauses is proven, e.g., because no new clauses can be generated. In this paper, we restrict our attention to the problem of evaluating Quantified Boolean Formulas (QBFs). In this setting, the above outlined deduction process is known to be sound and complete if given a formula in CNF and if a form of resolution, called "Q-resolution", is used. We introduce Q-resolution on terms, to be used for formulas in disjunctive normal form. We show that the computation performed by most of the available procedures for QBFs -based on the Davis-Logemann-Loveland procedure (DLL) for propositional satisfiabifity- corresponds to a tree in which Q-resolution on terms and clauses alternate. This poses the theoretical bases for the introduction of learning, corresponding to recording Q-resolution formulas associated with the nodes of the tree. We discuss the problems related to the introduction of learning in DLL based procedures, and present solutions extending state-of-the-art proposals coming from the literature on propositional satisfiability. Finally, we show that our DLL based solver extended with learning, performs significantly better on benchmarks used in the 2003 QBF solvers comparative evaluation. [ABSTRACT FROM AUTHOR]

Self-stabilization in distributed systems is a technique to guarantee convergence to a set of legitimate states without external intervention when a transient fault or bad initialization occurs. Recently, there has been a surge of efforts in designing techniques for automated synthesis of self-stabilizing algorithms that are correct by construction. Most of these techniques, however, are not parameterized, meaning that they can only synthesize a solution for a fixed and predetermined number of processes. In this paper, we report a breakthrough in parameterized synthesis of self-stabilizing algorithms in symmetric networks, including ring, line, mesh, and torus. First, we develop cutoffs that guarantee (1) closure in legitimate states, and (2) deadlock-freedom outside the legitimate states. We also develop a sufficient condition for convergence in self-stabilizing systems. Since some of our cutoffs grow with the size of the local state space of processes, scalability of the synthesis procedure is still a problem. We address this problem by introducing a novel SMT-based technique for counterexample-guided synthesis of self-stabilizing algorithms in symmetric networks. We have fully implemented our technique and successfully synthesized solutions to maximal matching, three coloring, and maximal independent set problems for ring and line topologies. [ABSTRACT FROM AUTHOR]

Reactive synthesis for the GR(1) fragment of LTL has been implemented and studied in many works. In this work we present and evaluate a list of heuristics to potentially reduce running times for GR(1) synthesis and related algorithms. The list includes several heuristics for controlled predecessor computation and BDDs, early detection of fixed-points and unrealizability, fixed-point recycling, and several heuristics for unrealizable core computations. We have implemented the heuristics and integrated them in our synthesis environment Spectra Tools, a set of tools for writing specifications and running synthesis and related analyses. We evaluate the presented heuristics on SYNTECH15, a total of 78 specifications of 6 autonomous Lego robots, on SYNTECH17, a total of 149 specifications of 5 autonomous Lego robots, all written by 3rd year undergraduate computer science students in two project classes we have taught, as well as on benchmarks from the literature. The evaluation investigates not only the potential of the suggested heuristics to improve computation times, but also the difference between existing benchmarks and the robot's specifications in terms of the effectiveness of the heuristics. Our evaluation shows positive results for the application of all the heuristics together, which get more significant for specifications with slower original running times. It also shows differences in effectiveness when applied to different sets of specifications. Furthermore, a comparison between Spectra, with all the presented heuristics, and two existing tools, RATSY and Slugs, over two well-known benchmarks, shows that Spectra outperforms both on most of the specifications; the larger the specification, the faster Spectra becomes relative to the two other tools. [ABSTRACT FROM AUTHOR]

Variational systems can produce a (potentially huge) number of related systems, known as products or variants, by using features (configuration options) to mark the variable functionality. In many of the application domains, their rigorous verification and analysis are very important, yet the appropriate tools rarely are able to analyse variational systems. Recently, this problem was addressed by designing specialized so-called family-based model checking algorithms, which allow simultaneous verification of all variants in a single run by exploiting the commonalities between the variants. Yet, their computational cost still greatly depends on the number of variants (the size of configuration space), which is often huge. Moreover, their implementation and maintenance represent a costly research and development task. One of the most promising approaches to fighting the configuration space explosion problem is variability abstractions, which simplify variability away from variational systems. In this work, we show how to achieve efficient family-based model checking of CTL ⋆ temporal properties using variability abstractions and off-the-shelf (single-system) tools. We use variability abstractions for deriving abstract family-based model checking, where the variability model of a variational system is replaced with an abstract (smaller) version of it, called modal transition system, which preserves the satisfaction of both universal and existential temporal properties, as expressible in CTL ⋆ . Modal transition systems contain two kinds of transitions, termed may- and must-transitions, which are defined by the conservative (over-approximating) abstractions and their dual (under-approximating) abstractions, respectively. The variability abstractions can be combined with different partitionings of the configuration space to infer suitable divide-and-conquer verification plans for the given variational system. We illustrate the practicality of this approach for several variational systems using the standard version of (single-system) NuSMV model checker. [ABSTRACT FROM AUTHOR]