Search

Research literature on Probabilistic Model Checking (PMC) encompasses a well-established set of algorithmic techniques whereby probabilistic models can be analyzed. In the last decade, owing to the increasing availability of effective tools, PMC has found applications in many domains, including computer networks, computational biology and robotics. In this paper, we evaluate PMC tools - namely COMICS, MRMC and PRISM - to investigate safe reinforcement learning in robots, i.e., to establish safety of policies learned considering feedback signals received upon acting in partially unknown environments. Introduced in previous contributions of ours, this application is a challenging domain wherein PMC tools act as back-engines of an automated methodology aimed to verify and repair control policies. We present an evaluation of the current state-of-the-art PMC tools to assess their potential on various case studies, including both real and simulated robots accomplishing navigation, manipulation and reaching tasks. [ABSTRACT FROM AUTHOR]

Twelve years have elapsed since the first Quantified Boolean Formulas (QBFs) evaluation was held as an event linked to SAT conferences. During this period, researchers have striven to propose new algorithms and tools to solve challenging formulas, with evaluations periodically trying to assess the current state of the art. In this paper, we present an experimental account of solvers and formulas with the aim to understand the progress in the QBF arena across these years. Unlike typical evaluations, the analysis is not confined to the snapshot of submitted solvers and formulas, but rather we consider several tools that were proposed over the last decade, and we run them on different formulas from previous QBF evaluations. The main contributions of our analysis, which are also the messages we would like to pass along to the research community, are: (i) many formulas that turned out to be difficult to solve in past evaluations, remain still challenging after twelve years, (ii) there is no single solver which can significantly outperform all the others, unless specific categories of formulas are considered, and (iii) effectiveness of preprocessing depends both on the coupled solver and the structure of the formula. [ABSTRACT FROM AUTHOR]

In recent years, Satisfiability Modulo Theory (SMT) solvers are becoming increasingly popular in the Computer Aided Verification and Reasoning community. Used natively or as back-engines, they are accumulating a record of success stories and, as witnessed by the annual SMT competition, their performances and capacity are also increasing steadily. Introduced in previous contributions of ours, a new application domain providing an outstanding challenge for SMT solvers is represented by verification of Multi-Layer Perceptrons (MLPs) a widely-adopted kind of artificial neural network. In this paper we present an extensive evaluation of the current state-of-the-art SMT solvers and assess their potential in the promising domain of MLP verification. [ABSTRACT FROM AUTHOR]

From an empirical point of view, the hardness of quantified Boolean formulas (QBFs), can be characterized by the (in)ability of current state-of-the-art QBF solvers to decide about the truth of formulas given limited computational resources. In this paper, we start from the problem of computing empirical hardness markers, i.e., features that can discriminate between hard and easy QBFs, and we end up showing that such markers can be useful to improve our understanding of QBF preprocessors. In particular, considering the connection between classes of tractable QBFs and the treewidth of associated graphs, we show that (an approximation of) treewidth is indeed a marker of empirical hardness and it is the only parameter which succeeds consistently in being so, even considering several other purely syntactic candidates which have been successfully employed to characterize QBFs in other contexts. We also show that treewidth approximations can be useful to describe the effect of QBF preprocessors, in that some QBF solvers benefit from a preprocessing phase when it reduces the treewidth of their input. Our experiments suggest that structural simplifications reducing treewidth are a potential enabler for the solution of hard QBF encodings. [ABSTRACT FROM AUTHOR]

In this paper we compare the performance of all the currently available suites to evaluate and certify QBFs. Our aim is to assess the current state of the art, and also to understand to which extent QBF encodings can be evaluated producing certificates that can be checked in a reliable and efficient way. We conclude that, while the evaluation of some QBFs is still an open challenge, producing and checking certificates for many medium-to-large scale QBFs is feasible with the current technology. [ABSTRACT FROM AUTHOR]