一种利用非确定规划的LTL合成方法

LTL合成(Linear Temporal Logic synthesis)是程序合成(program synthesis)的一类重要子问题, 旨在自动构建一个控制器(controller), 且要求该控制器和环境(environment)的行为交互满足给定的LTL公式.一般来说, 可以将LTL合成定义为二人博弈(two-player game)问题, 博弈的双方是环境和控制器, 该问题的解称为合成策略.近年来, 有研究从理论角度讨论了LTL合成与非确定规划(non-deterministic planning)的相关性.基于此, 本文提出了一种新的利用非确定规划求解LTL合成问题的方法, 并证明了方法的正确性和完备性.具体而言, 首先获得LTL公式对应的Büchi自动机, 结合二人博弈定义, 将LTL合成问题转换为完全可观测的非确定规划模型, 然后交由高效规划器求解.通过实验结果说明, 与其他LTL合成方法相比, 本文提出的基于规划的合成方法在解质量方面具有较大的优势, 能够获得规模较小的合成策略.     

Rewriting-Based Techniques for Runtime Verification

Techniques for efficiently evaluating future time Linear Temporal Logic (abbreviated LTL) formulae on finite execution traces are presented. While the standard models of LTL are infinite traces, finite traces appear naturally when testing and/or monitoring real applications that only run for limited time periods. A finite trace variant of LTL is formally defined, together with an immediate executable semantics which turns out to be quite inefficient if used directly, via rewriting, as a monitoring procedure. Then three algorithms are investigated. First, a simple synthesis algorithm for monitors based on dynamic programming is presented; despite the efficiency of the generated monitors, they unfortunately need to analyze the trace backwards, thus making them unusable in most practical situations. To circumvent this problem, two rewriting-based practical algorithms are further investigated, one using rewriting directly as a means for online monitoring, and the other using rewriting to generate automata-like monitors, called binary transition tree finite state machines (and abbreviated BTT-FSMs). Both rewriting algorithms are implemented in Maude, an executable specification language based on a very efficient implementation of term rewriting. The first rewriting algorithm essentially consists of a set of equations establishing an executable semantics of LTL, using a simple formula transforming approach. This algorithm is further improved to build automata on-the-fly via caching and reuse of rewrites (called memoization), resulting in a very efficient and small Maude program that can be used to monitor program executions. The second rewriting algorithm builds on the first one and synthesizes provably minimal BTT-FSMs from LTL formulae, which can then be used to analyze execution traces online without the need for a rewriting system. The presented work is part of an ambitious runtime verification and monitoring project at NASA Ames, called PathExplorer, and demonstrates that rewriting can be a tractable and attractive means for experimenting and implementing logics for program monitoring.Supported in part by joint NSF/NASA grant CCR-0234524.     

Translating Structured English to Robot Controllers

Recently, Linear Temporal Logic (LTL) has been successfully applied to high-level task and motion planning problems for mobile robots. One of the main attributes of LTL is its close relationship with fragments of natural language. In this paper, we take the first steps toward building a natural language interface for LTL planning methods with mobile robots as the application domain. For this purpose, we built a structured English language which maps directly to a fragment of LTL.     

From liveness to promptness

Liveness temporal properties state that something “good” eventually happens, e.g., every request is eventually granted. In Linear Temporal Logic (LTL), there is no a priori bound on the “wait time” for an eventuality to be fulfilled. That is, F θ asserts that θ holds eventually, but there is no bound on the time when θ will hold. This is troubling, as designers tend to interpret an eventuality F θ as an abstraction of a bounded eventuality F ^≤k θ, for an unknown k, and satisfaction of a liveness property is often not acceptable unless we can bound its wait time. We introduce here prompt-LTL, an extension of LTL with the prompt-eventually operator F _p . A system S satisfies a prompt-LTL formula φ if there is some bound k on the wait time for all prompt-eventually subformulas of φ in all computations of S. We study various problems related to prompt-LTL, including realizability, model checking, and assume-guarantee model checking, and show that they can be solved by techniques that are quite close to the standard techniques for LTL.     

Piecewise output feedback control for affine systems with disturbances based on linear temporal logic specifications

In the paper,we investigate the problem of finding a piecewise output feedback control law for an uncertain affine system such that the resulting closed-loop output satisfies a desired linear temporal logic (LTL) specification.A two-level hierarchical approach is proposed to solve the problem in a triangularized output space.In the lower level,we explore whether there exists a robust output feedback control law to make the output starting in a simplex either remains in it or leaves via a specific facet.In the higher level,for the triangularization,we construct the transition system according to the reachability relationship obtained in the lower level and search for feasible paths that meet the LTL specification.The control approach is then applied to solve a motion planning problem.     

Introduction to planning, scheduling and constraint satisfaction

Planning, scheduling and constraint satisfaction are important areas in artificial intelligence (AI). Many real-world problems are known as AI planning and scheduling problems, where resources must be allocated so as to optimize overall performance objectives. Therefore, solving these problems requires an adequate mixture of planning, scheduling and resource allocation to competing goal activities over time in the presence of complex state-dependent constraints. Constraint satisfaction plays also an important role to solve real-life problems, so that integrated techniques that manage planning and scheduling with constraint satisfaction remains necessary. This special issue on Planning, Scheduling and Constraint Satisfaction compiles a selection of papers of CAEPIA’2007 workshop on Planning, Scheduling and Constraint Satisfaction and COPLAS’2007: CP/ICAPS 2007 Joint Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems. This issue presents novel advances on planning, scheduling, constraint programming/constraint satisfaction problems (CSPs) and many other common areas that exist among them. On the whole, this issue mainly focus on managing complex problems where planning, scheduling, constraint satisfaction and search must be combined and/or interrelated, which entails an enormous potential for practical applications and future research. Furthermore, this issue also includes a complete survey about constraint satisfaction, planning, scheduling and integration among these areas.     

A logic-based agent that plans for extended reachability goals

Planning to reach a goal is an essential capability for rational agents. In general, a goal specifies a condition to be achieved at the end of the plan execution. In this article, we introduce nondeterministic planning for extended reachability goals (i.e., goals that also specify a condition to be preserved during the plan execution). We show that, when this kind of goal is considered, the temporal logic ctl turns out to be inadequate to formalize plan synthesis and plan validation algorithms. This is mainly due to the fact that the ctl’s semantics cannot discern among the various actions that produce state transitions. To overcome this limitation, we propose a new temporal logic called α-ctl. Then, based on this new logic, we implement a planner capable of synthesizing reliable plans for extended reachability goals, as a side effect of model checking.     

Combining Proof Plans with Partial Order Planning for Imperative Program Synthesis

The structured programming literature provides methods and a wealth of heuristic knowledge for guiding the construction of provably correct imperative programs. We investigate these methods and heuristics as a basis for mechanizing program synthesis. Our approach combines proof planning with conventional partial order planning. Proof planning is an automated theorem proving technique which uses high-level proof plans to guide the search for proofs. Proof plans are structured in terms of proof methods, which encapsulate heuristics for guiding proof search. We demonstrate that proof planning provides a local perspective on the synthesis task. In particular, we show that proof methods can be extended to represent heuristics for guiding program construction. Partial order planning complements proof planning by providing a global perspective on the synthesis task. This means that it allows us to reason about the order in which program fragments are composed. Our hybrid approach has been implemented in a semi-automatic system called Bertha. Bertha supports partial correctness and has been tested on a wide range of non-trivial programming examples.     

Cache Coherency in SCI: Specification and a Sketch of Correctness

SCI – Scalable Coherent Interface – is an IEEE standard for specifying communication between multiprocessors in a shared memory model. In this paper we model part of SCI by a program written in a UNITY-like programming language. This part of SCI is formally specified in Manna and Pnueli's Linear Time Temporal Logic (LTL). We give a sketch of our proof that the program satisfies its specification. The proof has been carried out within LTL. It uses history variables. Structuring of the proof has been achieved by careful formulation of lemmata and the use of auxiliary predicates as an abstraction mechanism. Received September 1997 / Accepted in revised form November 1999     

LTL satisfiability checking

We report here on an experimental investigation of LTL satisfiability checking via a reduction to model checking. By using large LTL formulas, we offer challenging model-checking benchmarks to both explicit and symbolic model checkers. For symbolic model checking, we use CadenceSMV, NuSMV, and SAL-SMC. For explicit model checking, we use SPIN as the search engine, and we test essentially all publicly available LTL translation tools. Our experiments result in two major findings. First, most LTL translation tools are research prototypes and cannot be considered industrial quality tools. Second, when it comes to LTL satisfiability checking, the symbolic approach is clearly superior to the explicit approach.     

Limited context semantic translation from a single knowledge-base for a natural language and structuring metarules

The article introduces an experimental system which produces multilingual semantic translations from relatively short texts from a given context. The system was conceived as an investigation instrument whose characteristics are the following: —the elaboration of a single analyzer and generator able to receive, in the form of data, specific information concerning national language, within the limits of a given area of application; —the use of exclusively semantic internal representation, whose formation is derived from “frames” (an object is defined as a list of “attribute-value” couples, permitting recursion); —a single knowledge-base is used for each natural language as initial data (the grammar transmitted was of a semantic-syntacticatn type); —the structure of grammar used in computer language processing being rarely as well adapted to analysis as to generation, the system itself is provided with the possibility of transforming and reorganizing the information for more efficient use at one stage of processing (thus, theatns are used directly in analysis, whereas for the purposes of generation they are “explored” and their information reorganized); —to produce a text, the use of general structuring principles (independent of language) are experimented with. These principles are given in the form of metarules. The application of these metarules to the restructured grammar of a natural language produces specific structuration rules, peculiar to this language. Although the system was conceived for any conceptual area or language, the present knowledge-base of the system (the experimental support) is based on a collection of elementary exercises in three-dimensional geometry written in Rumanian and in French. She does research in the CNRS group C.F. Picard headed by Professor Pitrat, University of Paris 6.     

从基于迁移的扩展Büchi自动机到Büchi自动机

目前的模型检测方法中,有一种方法是基于自动机来实现的.具体做法是:将抽象出的系统模型用Büchi自动机来表示,将需要验证的性质用LTL(linear temporal logic)公式来表达;然后将LTL公式取反后转化为Büchi自动机,并检查这两个自动机接受语言之间的包含关系.有一类LTL公式转化为Büchi自动机的算法是:在计算过程中,首先得到一个标注在迁移上的扩展Büchi自动机(transition-based generalized Büchi automaton,简称TGBA),然后把这种扩展Büchi自动机转换成非扩展的Büchi自动机.针对这类转换算法,根据Büchi自动机接受语言的特点,重新定义了基于迁移的扩展Büchi自动机的求交运算,减少了需要复制的状态个数,使转换后的自动机具有较少的状态.测试的结果表明:对随机产生的公式,新算法相对于以往的算法有明显的优势.     

An embeddable virtual machine for state space generation

The semantics of modelling languages are not always specified in a precise and formal way, and their rather complex underlying models make it a non-trivial exercise to reuse them in newly developed tools. We report on experiments with a virtual machine-based approach for state space generation. The virtual machine’s (VM) byte-code language is straightforwardly implementable, facilitates reuse and makes it an adequate target for translation of higher-level languages like the SPIN model checker’s Promela, or even C. As added value, it provides efficiently executable operational semantics for modelling languages. Several tools have been built around the VM implementation we developed, to evaluate the benefits of the proposed approach.     

A case-based approach to heuristic planning

Most of the great success of heuristic search as an approach to AI Planning is due to the right design of domain-independent heuristics. Although many heuristic planners perform reasonably well, the computational cost of computing the heuristic function in every search node is very high, causing the planner to scale poorly when increasing the size of the planning tasks. For tackling this problem, planners can incorporate additional domain-dependent heuristics in order to improve their performance. Learning-based planners try to automatically acquire these domain-dependent heuristics using previous solved problems. In this work, we present a case-based reasoning approach that learns abstracted state transitions that serve as domain control knowledge for improving the planning process. The recommendations from the retrieved cases are used as guidance for pruning or ordering nodes in different heuristic search algorithms applied to planning tasks. We show that the CBR guidance is appropriate for a considerable number of planning benchmarks.     

Collecting Statistics Over Runtime Executions

We present an extension to linear-time temporal logic (LTL) that combines the temporal specification with the collection of statistical data. By collecting statistics over runtime executions of a program we can answer complex queries, such as “what is the average number of packet transmissions' in a communication protocol, or “how often does a particular process enter the critical section while another process remains waiting' in a mutual exclusion algorithm. To decouple the evaluation strategy of the queries from the definition of the temporal operators, we introduce algebraic alternating automata as an automata-based intermediate representation. Algebraic alternating automata are an extension of alternating automata that produce a value instead of acceptance or rejection for each trace. Based on the translation of the formulas from the query language to algebraic alternating automata, we obtain a simple and efficient query evaluation algorithm. The approach is illustrated with examples and experimental results.     

Construction of CFC-Programs by LTL-Specification

This article continues a cycle of papers, which describe an approach to construction and verification of discrete PLC-programs by an LTL-specification. The approach provides a possibility of PLC-program correctness analysis by the model checking method. For the specification of the program behaviour the linear-time temporal logic LTL is used. The correctness analysis of an LTL specification is performed automatically by the symbolic model checking tool Cadence SMV. It was previously shown how ST-, LD- and IL-programs are constructed by a correct (with verified program properties) LTL-specification. In this article, a technology of CFC-program construction by an LTL-specification is described. The language CFC (Continuous Function Chart) is a variation of FBD (Function Block Diagram). FBD is a graphical language for microcircuits. CFC provides a possibility of free allocation of program components and connections on a screen. The approach to construction of CFC-programs is shown by an example. PLC-program representation on CFC within the approach to programming by LTLspecification differs from other representations. It gives the visualization of a data flow from inputs to outputs. The influence and dependence among variables is explicitly shown during the program execution within one PLC working cycle. In fact, CFC-program is a scheme of PLC-program data flow.     

Seven at one stroke: LTL model checking for high-level specifications in B, Z, CSP, and more

The size of formal models is steadily increasing and there is a demand from industrial users to be able to use expressive temporal query languages for validating and exploring high-level formal specifications. We present an extension of LTL, which is well adapted for validating B, Z and CSP specifications. We present a generic, flexible LTL model checker, implemented inside the PROB tool, that can be applied to a multitude of formalisms such as B, Z, CSP, B||CSP, as well as Object Petri nets, compensating CSP, and dSL. Our algorithm can deal with deadlock states, partially explored state spaces, past operators, and can be combined with existing symmetry reduction techniques of PROB. We establish correctness of our algorithm in general, as well as combined with symmetry reduction. Finally, we present various applications and empirical results of our tool, showing that it can be applied successfully in practice.