Search

We present a new approach to automated scenario-based testing of the safety of autonomous vehicles, especially those using advanced artificial intelligence-based components, spanning both simulation-based evaluation as well as testing in the real world. Our approach is based on formal methods, combining formal specification of scenarios and safety properties, algorithmic test case generation using formal simulation, test case selection for track testing, executing test cases on the track, and analyzing the resulting data. Experiments with a real autonomous vehicle at an industrial testing facility support our hypotheses that (i) formal simulation can be effective at identifying test cases to run on the track, and (ii) the gap between simulated and real worlds can be systematically evaluated and bridged.

Enriched Lawvere theories are a generalization of Lawvere theories that allowus to describe the operational semantics of formal systems. For example, agraph enriched Lawvere theory describes structures that have a graph ofoperations of each arity, where the vertices are operations and the edges arerewrites between operations. Enriched theories can be used to equip systemswith operational semantics, and maps between enriching categories can serve totranslate between different forms of operational and denotational semantics.The Grothendieck construction lets us study all models of all enriched theoriesin all contexts in a single category. We illustrate these ideas with theSKI-combinator calculus, a variable-free version of the lambda calculus.

Propositional model counting, or #SAT, is the problem of computing the numberof satisfying assignments of a Boolean formula. Many problems from differentapplication areas, including many discrete probabilistic inference problems,can be translated into model counting problems to be solved by #SAT solvers.Exact #SAT solvers, however, are often not scalable to industrial sizeinstances. In this paper, we present Neuro#, an approach for learning branchingheuristics to improve the performance of exact #SAT solvers on instances from agiven family of problems. We experimentally show that our method reduces thestep count on similarly distributed held-out instances and generalizes to muchlarger instances from the same problem family. It is able to achieve theseresults on a number of different problem families having very differentstructures. In addition to step count improvements, Neuro# can also achieveorders of magnitude wall-clock speedups over the vanilla solver on largerinstances in some problem families, despite the runtime overhead of queryingthe model.

We present a new approach to automated scenario-based testing of the safety of autonomous vehicles, especially those using advanced artificial intelligence-based components, spanning both simulation-based evaluation as well as testing in the real world. Our approach is based on formal methods, combining formal specification of scenarios and safety properties, algorithmic test case generation using formal simulation, test case selection for track testing, executing test cases on the track, and analyzing the resulting data. Experiments with a real autonomous vehicle at an industrial testing facility support our hypotheses that (i) formal simulation can be effective at identifying test cases to run on the track, and (ii) the gap between simulated and real worlds can be systematically evaluated and bridged.

In an earlier paper [Rational choice and AGM belief revision, Artificial Intelligence, 2009] a correspondence was established between the choice structures of revealed-preference theory (developed in economics) and the syntactic belief revision functions of the AGM theory (developed in philosophy and computer science). In this paper we extend the re-interpretation of (a generalized notion of) choice structure in terms of belief revision by adding: (1) the possibility that an item of “information” might be discarded as not credible (thus dropping the AGM success axiom) and (2) the possibility that an item of information, while not accepted as fully credible, may still be “taken seriously” (we call such items of information “allowable”). We establish a correspondence between generalized choice structures (GCS) and AGM belief revision; furthermore, we provide a syntactic analysis of the proposed notion of belief revision, which we call filtered belief revision.

In an earlier paper [Rational choice and AGM belief revision, Artificial Intelligence, 2009] a correspondence was established between the choice structures of revealed-preference theory (developed in economics) and the syntactic belief revision functions of the AGM theory (developed in philosophy and computer science). In this paper we extend the re-interpretation of (a generalized notion of) choice structure in terms of belief revision by adding: (1) the possibility that an item of “information” might be discarded as not credible (thus dropping the AGM success axiom) and (2) the possibility that an item of information, while not accepted as fully credible, may still be “taken seriously” (we call such items of information “allowable”). We establish a correspondence between generalized choice structures (GCS) and AGM belief revision; furthermore, we provide a syntactic analysis of the proposed notion of belief revision, which we call filtered belief revision.

Enriched Lawvere theories are a generalization of Lawvere theories that allowus to describe the operational semantics of formal systems. For example, agraph enriched Lawvere theory describes structures that have a graph ofoperations of each arity, where the vertices are operations and the edges arerewrites between operations. Enriched theories can be used to equip systemswith operational semantics, and maps between enriching categories can serve totranslate between different forms of operational and denotational semantics.The Grothendieck construction lets us study all models of all enriched theoriesin all contexts in a single category. We illustrate these ideas with theSKI-combinator calculus, a variable-free version of the lambda calculus.

We propose a measure and a metric on the sets of infinite traces generated bya set of atomic propositions. To compute these quantities, we first mapproperties to subsets of the real numbers and then take the Lebesgue measure ofthe resulting sets. We analyze how this measure is computed for Linear TemporalLogic (LTL) formulas. An implementation for computing the measure of boundedLTL properties is provided and explained. This implementation leverages SATmodel counting and effects independence checks on subexpressions to compute themeasure and metric compositionally.

We demonstrate how to learn efficient heuristics for automated reasoningalgorithms for quantified Boolean formulas through deep reinforcement learning.We focus on a backtracking search algorithm, which can already solve formulasof impressive size - up to hundreds of thousands of variables. The mainchallenge is to find a representation of these formulas that lends itself tomaking predictions in a scalable way. For a family of challenging problems, welearned a heuristic that solves significantly more formulas compared to theexisting handwritten heuristics.

Incremental determinization is a recently proposed algorithm for solving quantified Boolean formulas with one quantifier alternation. In this paper, we formalize incremental determinization as a set of inference rules to help understand the design space of similar algorithms. We then present additional inference rules that extend incremental determinization in two ways. The first extension integrates the popular CEGAR principle and the second extension allows us to analyze different cases in isolation. The experimental evaluation demonstrates that the extensions significantly improve the performance.

Reactive synthesis is a paradigm for automatically building correct-by-construction systems that interact with an unknown or adversarial environment. We study how to do reactive synthesis when part of the specification of the system is that its behavior should be random. Randomness can be useful, for example, in a network protocol fuzz tester whose output should be varied, or a planner for a surveillance robot whose route should be unpredictable. However, existing reactive synthesis techniques do not provide a way to ensure random behavior while maintaining functional correctness. Towards this end, we generalize the recently-proposed framework of control improvisation (CI) to add reactivity. The resulting framework of reactive control improvisation provides a natural way to integrate a randomness requirement with the usual functional specifications of reactive synthesis over a finite window. We theoretically characterize when such problems are realizable, and give a general method for solving them. For specifications given by reachability or safety games or by deterministic finite automata, our method yields a polynomial-time synthesis algorithm. For various other types of specifications including temporal logic formulas, we obtain a polynomial-space algorithm and prove matching PSPACE -hardness results. We show that all of these randomized variants of reactive synthesis are no harder in a complexity-theoretic sense than their non-randomized counterparts.

Real-world applications often naturally decompose into several sub-tasks. In many settings (e.g., robotics) demonstrations provide a natural way to specify the sub-tasks. However, most methods for learning from demonstrations either do not provide guarantees that the artifacts learned for the sub-tasks can be safely recombined or limit the types of composition available. Motivated by this deficit, we consider the problem of inferring Boolean non-Markovian rewards (also known as logical trace properties or specifications) from demonstrations provided by an agent operating in an uncertain, stochastic environment. Crucially, specifications admit well-defined composition rules that are typically easy to interpret. In this paper, we formulate the specification inference task as a maximum a posteriori (MAP) probability inference problem, apply the principle of maximum entropy to derive an analytic demonstration likelihood model and give an efficient approach to search for the most likely specification in a large candidate pool of specifications. In our experiments, we demonstrate how learning specifications can help avoid common problems that often arise due to ad-hoc reward composition.

Incremental determinization is a recently proposed algorithm for solving quantified Boolean formulas with one quantifier alternation. In this paper, we formalize incremental determinization as a set of inference rules to help understand the design space of similar algorithms. We then present additional inference rules that extend incremental determinization in two ways. The first extension integrates the popular CEGAR principle and the second extension allows us to analyze different cases in isolation. The experimental evaluation demonstrates that the extensions significantly improve the performance.

Weighted model counting (WMC) is a well-known inference task on knowledgebases, used for probabilistic inference in graphical models. We introducealgebraic model counting (AMC), a generalization of WMC to a semiringstructure. We show that AMC generalizes many well-known tasks in a variety ofdomains such as probabilistic inference, soft constraints and network anddatabase analysis. Furthermore, we investigate AMC from a knowledge compilationperspective and show that all AMC tasks can be evaluated using sd-DNNFcircuits. We identify further characteristics of AMC instances that allow forthe use of even more succinct circuits.

We present SGDPLL(T), an algorithm that solves (among many other problems)probabilistic inference modulo theories, that is, inference problems overprobabilistic models defined via a logic theory provided as a parameter(currently, propositional, equalities on discrete sorts, and inequalities, morespecifically difference arithmetic, on bounded integers). While many solutionsto probabilistic inference over logic representations have been proposed,SGDPLL(T) is simultaneously (1) lifted, (2) exact and (3) modulo theories, thatis, parameterized by a background logic theory. This offers a foundation forextending it to rich logic languages such as data structures and relationaldata. By lifted, we mean algorithms with constant complexity in the domain size(the number of values that variables can take). We also detail a solver forsummations with difference arithmetic and show experimental results from ascenario in which SGDPLL(T) is much faster than a state-of-the-artprobabilistic solver.

Probabilistic logic programs are logic programs in which some of the facts are annotated with probabilities. This paper investigates how classical inference and learning tasks known from the graphical model community can be tackled for probabilistic logic programs. Several such tasks, such as computing the marginals, given evidence and learning from (partial) interpretations, have not really been addressed for probabilistic logic programs before. The first contribution of this paper is a suite of efficient algorithms for various inference tasks. It is based on the conversion of the program and the queries and evidence to a weighted Boolean formula. This allows us to reduce inference tasks to well-studied tasks, such as weighted model counting, which can be solved using state-of-the-art methods known from the graphical model and knowledge compilation literature. The second contribution is an algorithm for parameter estimation in the learning from interpretations setting. The algorithm employs expectation-maximization, and is built on top of the developed inference algorithms. The proposed approach is experimentally evaluated. The results show that the inference algorithms improve upon the state of the art in probabilistic logic programming, and that it is indeed possible to learn the parameters of a probabilistic logic program from interpretations.

Auto-active verifiers provide a level of automation intermediate betweenfully automatic and interactive: users supply code with annotations as inputwhile benefiting from a high level of automation in the back-end. This paperpresents AutoProof, a state-of-the-art auto-active verifier for object-orientedsequential programs with complex functional specifications. AutoProof fullysupports advanced object-oriented features and a powerful methodology forframing and class invariants, which make it applicable in practice to idiomaticobject-oriented patterns. The paper focuses on describing AutoProof'sinterface, design, and implementation features, and demonstrates AutoProof'sperformance on a rich collection of benchmark problems. The results attestAutoProof's competitiveness among tools in its league on cutting-edgefunctional verification of object-oriented programs.

Most discussions of G\"odel's theorems fall into one of two types: either they emphasize perceived philosophical, cultural "meanings" of the theorems, and perhaps sketch some of the ideas of the proofs, usually relating G\"odel's proofs to riddles and paradoxes, but do not attempt to present rigorous, complete proofs; or they do present rigorous proofs, but in the traditional style of mathematical logic, with all of its heavy notation and difficult definitions, and technical issues which reflect G\"odel's original approach and broader logical issues. Many non-specialists are frustrated by these two extreme types of expositions and want a complete, rigorous proof that they can understand. Such an exposition is possible, because many people have realized that variants of G\"odel's first incompleteness theorem can be rigorously proved by a simpler middle approach, avoiding philosophical discussions and hand-waiving at one extreme; and also avoiding the heavy machinery of traditional mathematical logic, and many of the harder detail's of G\"odel's original proof, at the other extreme. This is the just-right Goldilocks approach. In this exposition we give a short, self-contained Goldilocks exposition of G\"odel's first theorem, aimed at a broad, undergraduate audience.

Counterexample-guided inductive synthesis (CEGIS) is used to synthesize programs from a candidate space of programs. The technique is guaranteed to terminate and synthesize the correct program if the space of candidate programs is finite. But the technique may or may not terminate with the correct program if the candidate space of programs is infinite. In this paper, we perform a theoretical analysis of counterexample-guided inductive synthesis technique. We investigate whether the set of candidate spaces for which the correct program can be synthesized using CEGIS depends on the counterexamples used in inductive synthesis, that is, whether there are good mistakes which would increase the synthesis power. We investigate whether the use of minimal counterexamples instead of arbitrary counterexamples expands the set of candidate spaces of programs for which inductive synthesis can successfully synthesize a correct program. We consider two kinds of counterexamples: minimal counterexamples and history bounded counterexamples. The history bounded counterexample used in any iteration of CEGIS is bounded by the examples used in previous iterations of inductive synthesis. We examine the relative change in power of inductive synthesis in both cases. We show that the synthesis technique using minimal counterexamples MinCEGIS has the same synthesis power as CEGIS but the synthesis technique using history bounded counterexamples HCEGIS has different power than that of CEGIS, but none dominates the other.

Counterexample-guided inductive synthesis (CEGIS) is used to synthesize programs from a candidate space of programs. The technique is guaranteed to terminate and synthesize the correct program if the space of candidate programs is finite. But the technique may or may not terminate with the correct program if the candidate space of programs is infinite. In this paper, we perform a theoretical analysis of counterexample-guided inductive synthesis technique. We investigate whether the set of candidate spaces for which the correct program can be synthesized using CEGIS depends on the counterexamples used in inductive synthesis, that is, whether there are good mistakes which would increase the synthesis power. We investigate whether the use of minimal counterexamples instead of arbitrary counterexamples expands the set of candidate spaces of programs for which inductive synthesis can successfully synthesize a correct program. We consider two kinds of counterexamples: minimal counterexamples and history bounded counterexamples. The history bounded counterexample used in any iteration of CEGIS is bounded by the examples used in previous iterations of inductive synthesis. We examine the relative change in power of inductive synthesis in both cases. We show that the synthesis technique using minimal counterexamples MinCEGIS has the same synthesis power as CEGIS but the synthesis technique using history bounded counterexamples HCEGIS has different power than that of CEGIS, but none dominates the other.

We introduce a new class of abstract structures, which we call generalized ultrametric semilattices, and in which the meet operation of the semilattice coexists with a generalized distance function in a tightly coordinated way. We prove a constructive fixed-point theorem for strictly contracting functions on directed-complete generalized ultrametric semilattices, and introduce a corresponding induction principle. We cite examples of application in the semantics of logic programming and timed computation, where, until now, the only tool available has been the non-constructive fixed-point theorem of Priess-Crampe and Ribenboim for strictly contracting functions on spherically complete generalized ultrametric semilattices.

We introduce a new class of abstract structures, which we call generalized ultrametric semilattices, and in which the meet operation of the semilattice coexists with a generalized distance function in a tightly coordinated way. We prove a constructive fixed-point theorem for strictly contracting functions on directed-complete generalized ultrametric semilattices, and introduce a corresponding induction principle. We cite examples of application in the semantics of logic programming and timed computation, where, until now, the only tool available has been the non-constructive fixed-point theorem of Priess-Crampe and Ribenboim for strictly contracting functions on spherically complete generalized ultrametric semilattices.