The Experts below are selected from a list of 14274 Experts worldwide ranked by ideXlab platform
Emilio Frazzoli - One of the best experts on this subject based on the ideXlab platform.
-
incremental synthesis of control policies for heterogeneous multi agent systems with Linear Temporal Logic specifications
International Conference on Robotics and Automation, 2013Co-Authors: Tichakorn Wongpiromsarn, Calin Belta, Alphan Ulusoy, Emilio Frazzoli, Daniela RusAbstract:We consider automatic synthesis of control policies for non-independent, heterogeneous multi-agent systems with the objective of maximizing the probability of satisfying a given specification. The specification is expressed as a formula in Linear Temporal Logic. The agents are modeled by Markov decision processes with a common set of actions. These actions, however, may or may not affect the behaviors of all the agents. To alleviate the well-known state explosion problem, an incremental approach is proposed where only a small subset of agents is incorporated in the synthesis procedure initially and more agents are successively added until the limitations on computational resources are reached. The proposed algorithm runs in an anytime fashion, where the probability of satisfying the specification increases as the algorithm progresses.
-
Linear Temporal Logic vehicle routing with applications to multi uav mission planning
International Journal of Robust and Nonlinear Control, 2011Co-Authors: Sertac Karaman, Emilio FrazzoliAbstract:Missions with high combinatorial complexity involving several Logical and Temporal constraints often arise in cooperative control of multiple Uninhabited Aerial Vehicles. In this paper, we propose a new class of problems that generalizes the standard Vehicle Routing Problem (VRP) by addressing complex tasks and constraints on the mission, called the ‘mission specifications’, expressed in a high-level specification language. In the generalized problem setup, these mission specifications are naturally specified using the Linear Temporal Logic language LTL−X. Using a novel systematic procedure, the LTL−X specification is converted to a set of constraints suitable to a Mixed-Integer Linear Programming (MILP) formulation, which in turn can be incorporated into two widely-used MILP formulations of the standard VRP. Solving the resulting MILP provides an optimal plan that satisfies the given mission specification. The paper also presents two mission planning applications. Copyright © 2011 John Wiley & Sons, Ltd.
-
vehicle routing with Linear Temporal Logic specifications applications to multi uav mission planning
AIAA Guidance Navigation and Control Conference and Exhibit, 2008Co-Authors: Sertac Karaman, Emilio FrazzoliAbstract:The Vehicle Routing Problem (VRP) and several of its variants have been used as an algorithmic basis for mission planning and trajectory generation for Uninhabited Aerial Vehicles (UAVs). This paper proposes a new class of problems that generalizes the standard VRP to incorporate more complex mission specifications, for example relative timing constraints on the completion of tasks. These timing constraints are specified using the Linear Temporal Logic language LTL−X. A systematic procedure is presented that converts a given set of LTL−X specifications into a set of constraints suitable to a Mixed-Integer Linear Programming (MILP) formulation of optimal mission planning problems. The application of this new variant of VRP to complex mission planning and UAV-routing problems are also considered by employing two different MILP formulations of VRP commonly used in related literature. Examples of UAV mission planning problems are discussed in detail.
-
complex mission optimization for multiple uavs using Linear Temporal Logic
American Control Conference, 2008Co-Authors: Sertac Karaman, Emilio FrazzoliAbstract:This paper discusses a class of mission planning problems in which mission objectives and relative timing constraints are specified using the Linear Temporal Logic language LTL-x. Among all mission plans that satisfy the LTL-x specifications, it is desired to find those minimizing a given cost functional. We show that such an optimization problem can be formulated as a mixed-integer Linear program, and present an algorithm for this purpose. This algorithm mainly relies on a novel systematic procedure which converts a given LTL-x formula into a set of mixed-integer Linear constraints. The approach presented here can be used for multiple-UAV mission planning purposes, allowing the operator to specify complex mission objectives in LTL-x in a very natural manner; the proposed algorithm constructs the optimal mission plan satisfying the given LTL-x specification. Examples for practical problem sizes are presented and discussed in the paper.
-
Optimal control of Mixed Logical Dynamical systems with Linear Temporal Logic specifications
2008 47th IEEE Conference on Decision and Control, 2008Co-Authors: Sertac Karama, Ricardo G. Sanfelice, Emilio FrazzoliAbstract:Recently, Linear Temporal Logic (LTL) has been employed as a tool for formal specification in dynamical control systems. With this formal approach, control systems can be designed to provably accomplish a large class of complex tasks specified via LTL. For this purpose, language generating Buchi automata with finite abstractions of dynamical systems have been used in the literature. In this paper, we take a mathematical programming-based approach to control of a broad class of discrete-time dynamical systems, called mixed Logic dynamical (MLD) systems, with LTL specifications. MLDs include discontinuous and hybrid piecewise discrete-time Linear systems. We apply these tools for model checking and optimal control of MLD systems with LTL specifications. Our algorithms exploit mixed integer Linear programming (MILP) as well as, in the appropriate setting, mixed integer quadratic programming (MIQP) techniques. Our solution approach introduces a general technique useful in representing LTL constraints as mixed-integer Linear constraints.
Moshe Y. Vardi - One of the best experts on this subject based on the ideXlab platform.
-
Linear Temporal Logic and Linear dynamic Logic on finite traces
International Joint Conference on Artificial Intelligence, 2013Co-Authors: Giuseppe De Giacomo, Moshe Y. VardiAbstract:In this paper we look into the assumption of interpreting LTL over finite traces. In particular we show that LTLf, i.e., LTL under this assumption, is less expressive than what might appear at first sight, and that at essentially no computational cost one can make a significant increase in expressiveness while maintaining the same intuitiveness of LTLf. Indeed, we propose a Logic, LDLf for Linear Dynamic Logic over finite traces, which borrows the syntax from Propositional Dynamic Logic (PDL), but is interpreted over finite traces. Satisfiability, validity and Logical implication (as well as model checking) for LTLf. are PSPACE-complete as for LTLf. (and LTL).
-
explicit or symbolic translation of Linear Temporal Logic to automata
2012Co-Authors: Moshe Y. Vardi, Kristin Yvonne RozierAbstract:Formal verification techniques are growing increasingly vital for the development of safety-critical software and hardware in practice. Techniques such as requirements-based design and model checking for system verification have been successfully used to verify systems for air traffic control, airplane separation assurance, autopilots, CPU Logic designs, life-support, medical equipment, and other functions that ensure human safety. Formal behavioral specifications written early in the system-design process and communicated across all design phases increase the efficiency, consistency, and quality of the system under development. We argue that to prevent introducing design or verification errors, it is crucial to test specifications for satisfiability. We advocate for the adaptation of a new sanity check via satisfiability checking for property assurance. Our focus here is on specifications expressed in Linear Temporal Logic (LTL). We demonstrate that LTL satisfiability checking reduces to model checking and satisfiability checking for the specification, its complement, and a conjunction of all properties should be performed as a first step to LTL model checking. We report on an experimental investigation of LTL satisfiability checking. We introduce a large set of rigorous benchmarks to enable objective evaluation of LTL-to-automaton algorithms in terms of scalability, performance, correctness, and size of the automata produced. For explicit model checking, we use the Spin model checker; we tested all LTL-to-explicit automaton translation tools that were publicly available when we conducted our study. For symbolic model checking, we use CadenceSMV, NuSMV, and SAL-SMC for both LTL-to-symbolic automaton translation and to perform the satisfiability check. Our experiments result in two major findings. First, scalability, correctness, and other debilitating performance issues afflict most LTL translation tools. Second, for LTL satisfiability checking, the symbolic approach is clearly superior to the explicit approach. Ironically, the explicit approach to LTL-to-automata had been heavily studied while only one algorithm existed for LTL-to-symbolic automata. Since 1994, there had been essentially no new progress in encoding symbolic automata for BDD-based analysis. Therefore, we introduce a set of 30 symbolic automata encodings. The set consists of novel combinations of existing constructs, such as different LTL formula normal forms, with a novel transition-labeled symbolic automaton form, a new way to encode transitions, and new BDD variable orders based on algorithms for tree decomposition of graphs. An extensive set of experiments demonstrates that these encodings translate to significant, sometimes exponential, improvement over the current standard encoding for symbolic LTL satisfiability checking. Building upon these ideas, we return to the explicit automata domain and focus on the most common type of specifications used in industrial practice: safety properties. We show that we can exploit the inherent determinism of safety properties to create a set of 26 explicit automata encodings comprised of novel aspects including: state numbers versus state labels versus a state look-up table, finite versus infinite acceptance conditions, forward-looking versus backward-looking transition encodings, assignment-based versus BDD-based alphabet representation, state and transition minimization, edge abbreviation, trap-state elimination, and determinization either on-the-fly or up-front using the subset construction. We conduct an extensive experimental evaluation and identify an encoding that offers the best performance in explicit LTL model checking time and is constantly faster than the previous best explicit automaton encoding algorithm.
-
enhanced vacuity detection in Linear Temporal Logic
Computer Aided Verification, 2003Co-Authors: Roy Armoni, Limor Fix, Alon Flaisher, Orna Grumberg, Nir Piterman, Andreas Tiemeyer, Moshe Y. VardiAbstract:One of the advantages of Temporal-Logic model-checking tools is their ability to accompany a negative answer to a correctness query with a counterexample to the satisfaction of the specification in the system. On the other hand, when the answer to the correctness query is positive, most model-checking tools provide no witness for the satisfaction of the specification. In the last few years there has been growing awareness of the importance of suspecting the system or the specification of containing an error also in cases where model checking succeeds. In particular, several works have recently focused on the detection of the vacuous satisfaction of Temporal Logic specifications. For example, when verifying a system with respect to the specification ϕ = G(req →Fgrant) (“every request is eventually followed by a grant”), we say that ϕ is satisfied vacuously in systems in which requests are never sent. Current works have focused on detecting vacuity with respect to subformula occurrences. In this work we investigate vacuity detection with respect to subformulas with multiple occurrences.
-
enhanced vacuity detection in Linear Temporal Logic
Lecture Notes in Computer Science, 2003Co-Authors: Roy Armoni, Limor Fix, Alon Flaisher, Orna Grumberg, Nir Piterman, Andreas Tiemeyer, Moshe Y. VardiAbstract:One of the advantages of Temporal-Logic model-checking tools is their ability to accompany a negative answer to a correctness query with a counterexample to the satisfaction of the specification in the system. On the other hand, when the answer to the correctness query is positive, most model-checking tools provide no witness for the satisfaction of the specification. In the last few years there has been growing awareness of the importance of suspecting the system or the specification of containing an error also in cases where model checking succeeds. In particular, several works have recently focused on the detection of the vacuous satisfaction of Temporal Logic specifications. For example, when verifying a system with respect to the specification φ = G(req → Fgrant) (every request is eventually followed by a grant), we say that φ is satisfied vacuously in systems in which requests are never sent. Current works have focused on detecting vacuity with respect to subformula occurrences. In this work we investigate vacuity detection with respect to subformulas with multiple occurrences. The generality of our framework requires us to re-examine the basic intuition underlying the concept of vacuity, which until now has been defined as sensitivity with respect to syntactic perturbation. We study sensitivity with respect to semantic perturbation, which we model by universal propositional quantification. We show that this yields a hierarchy of vacuity notions. We argue that the right notion is that of vacuity defined with respect to traces. We then provide an algorithm for vacuity detection and discuss pragmatic aspects.
-
improved automata generation for Linear Temporal Logic
Computer Aided Verification, 1999Co-Authors: Marco Daniele, Fausto Giunchiglia, Moshe Y. VardiAbstract:We improve the state-of-the-art algorithm for obtaining an automaton from a Linear Temporal Logic formula. The automaton is intended to be used for model checking, as well as for satisfiability checking. Therefore, the algorithm is mainly concerned with keeping the automaton as small as possible. The experimental results show that our algorithm outperforms the previous one, with respect to both the size of the generated automata and computation time. The testing is performed following a newly developed methodology based on the use of randomly generated formulas.
Calin Belta - One of the best experts on this subject based on the ideXlab platform.
-
reinforcement learning with Temporal Logic rewards
Intelligent Robots and Systems, 2017Co-Authors: Cristian Ioan Vasile, Calin BeltaAbstract:Reinforcement learning (RL) depends critically on the choice of reward functions used to capture the desired behavior and constraints of a robot. Usually, these are handcrafted by a expert designer and represent heuristics for relatively simple tasks. Real world applications typically involve more complex tasks with rich Temporal and Logical structure. In this paper we take advantage of the expressive power of Temporal Logic (TL) to specify complex rules the robot should follow, and incorporate domain knowledge into learning. We propose Truncated Linear Temporal Logic (TLTL) as a specification language, We propose Truncated Linear Temporal Logic (TLTL) as a specification language, that is arguably well suited for the robotics applications, We show in simulated trials that learning is faster and policies obtained using the proposed approach outperform the ones learned using heuristic rewards in terms of the robustness degree, i.e., how well the tasks are satisfied. Furthermore, we demonstrate the proposed RL approach in a toast-placing task learned by a Baxter robot.
-
Optimal Control of Markov Decision Processes With Linear Temporal Logic Constraints
IEEE Transactions on Automatic Control, 2014Co-Authors: Xuchu Ding, Stephen L. Smith, Calin BeltaAbstract:In this paper, we develop a method to automatically generate a control policy for a dynamical system modeled as a Markov Decision Process (MDP). The control specification is given as a Linear Temporal Logic (LTL) formula over a set of propositions defined on the states of the MDP. Motivated by robotic applications requiring persistent tasks, such as environmental monitoring and data gathering, we synthesize a control policy that minimizes the expected cost between satisfying instances of a particular proposition over all policies that maximize the probability of satisfying the given LTL specification. Our approach is based on the definition of a novel optimization problem that extends the existing average cost per stage problem. We propose a sufficient condition for a policy to be optimal, and develop a dynamic programming algorithm that synthesizes a policy that is optimal for a set of LTL specifications.
-
incremental synthesis of control policies for heterogeneous multi agent systems with Linear Temporal Logic specifications
International Conference on Robotics and Automation, 2013Co-Authors: Tichakorn Wongpiromsarn, Calin Belta, Alphan Ulusoy, Emilio Frazzoli, Daniela RusAbstract:We consider automatic synthesis of control policies for non-independent, heterogeneous multi-agent systems with the objective of maximizing the probability of satisfying a given specification. The specification is expressed as a formula in Linear Temporal Logic. The agents are modeled by Markov decision processes with a common set of actions. These actions, however, may or may not affect the behaviors of all the agents. To alleviate the well-known state explosion problem, an incremental approach is proposed where only a small subset of agents is incorporated in the synthesis procedure initially and more agents are successively added until the limitations on computational resources are reached. The proposed algorithm runs in an anytime fashion, where the probability of satisfying the specification increases as the algorithm progresses.
-
receding horizon surveillance with Temporal Logic specifications
Conference on Decision and Control, 2010Co-Authors: Xuchu Ding, Calin Belta, Christos G CassandrasAbstract:In this paper we consider a setting where a robotic vehicle is commissioned to provide surveillance in an area where there are multiple targets, while satisfying a set of high level, rich specifications expressed as Linear Temporal Logic formulas. Each target has an associated reward. The goal of the vehicle is to maximize the cumulative collected reward while satisfying the given high level task specification. By the nature of a surveillance mission, targets points of interest are detected in real time around the current location of the vehicle; hence we employ a receding horizon controller to compute the optimal path of the vehicle inside a subset of the mission space. This paper provides a framework which guarantees that the overall trajectory of the system satisfies the desired Linear Temporal Logic specification, while the control decisions are made based on local information obtained in real time.
Dimos V Dimarogonas - One of the best experts on this subject based on the ideXlab platform.
-
coupled multi robot systems under Linear Temporal Logic and signal Temporal Logic tasks
IEEE Transactions on Control Systems and Technology, 2021Co-Authors: Lars Lindemann, Meng Guo, Jakub Nowak, Lukas Schonbachler, Jana Tumova, Dimos V DimarogonasAbstract:This brief presents the implementation and experimental results of two frameworks for multi-agent systems under Temporal Logic tasks, which we have recently proposed. Each agent is subject to either a local Linear Temporal Logic (LTL) or a local signal Temporal Logic (STL) task where each task may further be coupled, i.e., the satisfaction of a task may depend on more than one agent. The agents are represented by mobile robots with different sensing and actuation capabilities. We propose to combine the two aforementioned frameworks to use the strengths of both LTL and STL. For the implementation, we take into account practical issues, such as collision avoidance, and, in particular, for the STL framework, input saturation, the digital implementation of continuous-time feedback control laws, and a controllability assumption that was made in the original work. The experimental results contain three scenarios that show a wide variety of tasks.
-
revising motion planning under Linear Temporal Logic specifications in partially known workspaces
International Conference on Robotics and Automation, 2013Co-Authors: Meng Guo, Karl Henrik Johansson, Dimos V DimarogonasAbstract:In this paper we propose a generic framework for real-time motion planning based on model-checking and revision. The task specification is given as a Linear Temporal Logic formula over a finite abstraction of the robot motion. A preliminary motion plan is first generated based on the initial knowledge of the system model. Then real-time information obtained during the runtime is used to update the system model, verify and further revise the motion plan. The implementation and revision of the motion plan are performed in real-time. This framework can be applied to partially-known workspaces and workspaces with large uncertainties. Computer simulations are presented to demonstrate the efficiency of the framework.
Sertac Karaman - One of the best experts on this subject based on the ideXlab platform.
-
Linear Temporal Logic vehicle routing with applications to multi uav mission planning
International Journal of Robust and Nonlinear Control, 2011Co-Authors: Sertac Karaman, Emilio FrazzoliAbstract:Missions with high combinatorial complexity involving several Logical and Temporal constraints often arise in cooperative control of multiple Uninhabited Aerial Vehicles. In this paper, we propose a new class of problems that generalizes the standard Vehicle Routing Problem (VRP) by addressing complex tasks and constraints on the mission, called the ‘mission specifications’, expressed in a high-level specification language. In the generalized problem setup, these mission specifications are naturally specified using the Linear Temporal Logic language LTL−X. Using a novel systematic procedure, the LTL−X specification is converted to a set of constraints suitable to a Mixed-Integer Linear Programming (MILP) formulation, which in turn can be incorporated into two widely-used MILP formulations of the standard VRP. Solving the resulting MILP provides an optimal plan that satisfies the given mission specification. The paper also presents two mission planning applications. Copyright © 2011 John Wiley & Sons, Ltd.
-
vehicle routing with Linear Temporal Logic specifications applications to multi uav mission planning
AIAA Guidance Navigation and Control Conference and Exhibit, 2008Co-Authors: Sertac Karaman, Emilio FrazzoliAbstract:The Vehicle Routing Problem (VRP) and several of its variants have been used as an algorithmic basis for mission planning and trajectory generation for Uninhabited Aerial Vehicles (UAVs). This paper proposes a new class of problems that generalizes the standard VRP to incorporate more complex mission specifications, for example relative timing constraints on the completion of tasks. These timing constraints are specified using the Linear Temporal Logic language LTL−X. A systematic procedure is presented that converts a given set of LTL−X specifications into a set of constraints suitable to a Mixed-Integer Linear Programming (MILP) formulation of optimal mission planning problems. The application of this new variant of VRP to complex mission planning and UAV-routing problems are also considered by employing two different MILP formulations of VRP commonly used in related literature. Examples of UAV mission planning problems are discussed in detail.
-
complex mission optimization for multiple uavs using Linear Temporal Logic
American Control Conference, 2008Co-Authors: Sertac Karaman, Emilio FrazzoliAbstract:This paper discusses a class of mission planning problems in which mission objectives and relative timing constraints are specified using the Linear Temporal Logic language LTL-x. Among all mission plans that satisfy the LTL-x specifications, it is desired to find those minimizing a given cost functional. We show that such an optimization problem can be formulated as a mixed-integer Linear program, and present an algorithm for this purpose. This algorithm mainly relies on a novel systematic procedure which converts a given LTL-x formula into a set of mixed-integer Linear constraints. The approach presented here can be used for multiple-UAV mission planning purposes, allowing the operator to specify complex mission objectives in LTL-x in a very natural manner; the proposed algorithm constructs the optimal mission plan satisfying the given LTL-x specification. Examples for practical problem sizes are presented and discussed in the paper.