Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> Given a robot model and a class of admissible environments, this paper provides a framework for automatically and verifiably composing controllers that satisfy high level task specifications expressed in suitable temporal logics. The desired task specifications can express complex robot behaviors such as search and rescue, coverage, and collision avoidance. In addition, our framework explicitly captures sensor specifications that depend on the environment with which the robot is interacting, resulting in a novel paradigm for sensor-based temporal logic motion planning. As one robot is part of the environment of another robot, our sensor-based framework very naturally captures multi-robot specifications. Our computational approach is based on first creating discrete controllers satisfying so-called general reactivity formulas. If feasible, the discrete controller is then used in order to guide the sensor-based composition of continuous controllers resulting in a hybrid controller satisfying the high level specification, but only if the environment is admissible. <s> BIB001 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> Autonomous robots are complex systems that require the interaction/cooperation of numerous heterogeneous software components. Nowadays, robots are critical systems and must meet safety properties including in particular temporal and real-time constraints. We present a methodology for modeling and analyzing a robotic system using the BIP component framework integrated with an existing framework and architecture, the LAAS Architecture for Autonomous System, based on GenoM. The BIP componentization approach has been successfully used in other domains. In this study, we show how it can be seamlessly integrated in the preexisting methodology. We present the componentization of the functional level of a robot, the synthesis of an execution controller as well as validation techniques for checking essential “safety” properties. <s> BIB002 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> Autonomous robots are complex systems that require the interaction/cooperation of numerous heterogeneous software components. Nowadays, robots are getting closer to humans and as such are becoming critical systems which must meet safety properties including in particular logical, temporal and real-time constraints. We present an evolution of the LAAS Architecture for Autonomous System and its tool GenoM. This evolution is based on the BIP (Behaviors Interactions Priorities) component based design framework which has been successfully used in other domains (e.g. embedded systems). In this study, we show how we seamlessly integrate BIP in the preexisting methodology. We present the componentization of the functional level of a robot, the synthesis of an execution controller as well as validation techniques for checking essential safety properties. This approach has been integrated in the LAAS architecture and we have performed a number of experiment in simulation but also on a real robot (DALA). <s> BIB003 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> Michigan/AFRL Collaborative Center on Control Sciences, AFOSR (grant no. FA 8650-07-2-3744) <s> BIB004 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> The paper addresses formal systems verification of autonomous underwater vehicles (AUV). The verification process includes hybrid system modelling and formulation of the discrete representation using natural language programming (sEnglish) via compositional abstraction - employing data, perception and action abstraction methods; the translation of the discrete abstraction into interpreted script programming language (ISPL) of a mainstream multi-agent model checker (MCMAS) for reachability verification of undesirable states, and ultimately the bridging into the discrete event system representation in Stateflow formalism. Using this technique, modelling and model checking can include the complete physical system of the autonomous vehicle, its multi-agent software on board and also the human interface represented as an agent. <s> BIB005 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> Knowledge processing is an essential technique for enabling autonomous robots to do the right thing to the right object in the right way. Using knowledge processing the robots can achieve more flexible and general behavior and better performance. While knowledge representation and reasoning has been a well-established research field in Artificial Intelligence for several decades, little work has been done to design and realize knowledge processing mechanisms for the use in the context of robotic control. In this paper, we report on KNOWROB, a knowledge processing system particularly designed for autonomous personal robots. KNOWROB is a first-order knowledge representation based on description logics that provides specific mechanisms and tools for action-centered representation, for the automated acquisition of grounded concepts through observation and experience, for reasoning about and managing uncertainty, and for fast inference — knowledge processing features that are particularly necessary for autonomous robot control. <s> BIB006 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> Self-adaptive systems have the capability to autonomously modify their behaviour at run-time in response to changes in their environment. Self-adaptation is particularly necessary for applications that must run continuously, even under adverse conditions and changing requirements; sample domains include automotive systems, telecommunications, and environmental monitoring systems. While a few techniques have been developed to support the monitoring and analysis of requirements for adaptive systems, limited attention has been paid to the actual creation and specification of requirements of self-adaptive systems. As a result, self-adaptivity is often constructed in an ad-hoc manner. In this paper, we argue that a more rigorous treatment of requirements explicitly relating to self-adaptivity is needed and that, in particular, requirements languages for self-adaptive systems should include explicit constructs for specifying and dealing with the uncertainty inherent in self-adaptive systems. We present RELAX, a new requirements language for self-adaptive systems and illustrate it using examples from the smart home domain. <s> BIB007 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> Robot swarms provide a way for a number of simple robots to work together to carry out a task. While swarms have been found to be adaptable, fault-tolerant and widely applicable, designing individual robot algorithms so as to ensure effective and correct swarm behaviour is very difficult. In order to assess swarm effectiveness, either experiments with real robots or computational simulations of the swarm are usually carried out. However, neither of these involve a deep analysis of all possible behaviours. In this paper we will utilise automated formal verification techniques, involving an exhaustive mathematical analysis, in order to assess whether our swarms will indeed behave as required. <s> BIB008 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> This paper proposes a novel approach to achieving fast reconfiguration of modular manufacturing systems, based on an ontology-based reconfiguration agent. The agent uses ontological knowledge of the manufacturing environment for the purpose of reconfiguration without human intervention. The current mass customization era requires increased flexibility and agility in the manufacturing systems to adapt changes in manufacturing requirements and environments. Our configuration agent minimises the overheads of the current reconfiguration process by automating it. It infers facts about the manufacturing environment from the ontological knowledge model and then decides whether the current environment can support the given manufacturing requirements. This paper proposes the agent architecture enabling the integration between the high level planning with the distributed low level control compliant with the upcoming IEC 61499 function blocks standard. <s> BIB009 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> We present a computational framework for automatic synthesis of control and communication strategies for a robotic team from task specifications given as regular expressions about servicing requests in an environment. Our approach is based on two main ideas. First, we extend recent results from formal synthesis of distributed systems to check for the distributability of the task specification and to generate local specifications, while accounting for the service and communication capabilities of the robots. Second, by using a technique inspired from LTL model checking, we generate individual control and communication strategies. We illustrate the method with experimental results in our Robotic Urban-Like Environment. <s> BIB010 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> A robot swarm is a collection of simple robots designed to work together to carry out some task. Such swarms rely on: the simplicity of the individual robots; the fault tolerance inherent in having a large population of often identical robots; and the self-organised behaviour of the swarm as a whole. Although robot swarms are being deployed in increasingly sophisticated areas, designing individual control algorithms that can guarantee the required global behaviour is difficult. In this paper we apply and assess the use of formal verification techniques, in particular that of model checking, for analysing the emergent behaviours of robotic swarms. These techniques, based on the automated analysis of systems using temporal logics, allow us to analyse all possible behaviours and so identify potential problems with the robot swarm conforming to some required global behaviour. To show this approach we target a particular swarm control algorithm, and show how automated temporal analysis can help to refine and analyse such an algorithm. <s> BIB011 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> In this paper, we develop a computational framework for fully automatic deployment of a team of unicycles from a global specification given as an LTL formula over some regions of interest. Our hierarchical approach consists of four steps: (i) the construction of finite abstractions for the motions of each robot, (ii) the parallel composition of the abstractions, (iii) the generation of a satisfying motion of the team; (iv) mapping this motion to individual robot control and communication strategies. The main result of the paper is an algorithm to reduce the amount of inter-robot communication during the fourth step of the procedure. <s> BIB012 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> Recent work in robotics has applied formal verification tools to automatically generate correct-by-construction controllers for autonomous robots. However, when it is not possible to create such a controller, these approaches do not provide the user with feedback on the source of failure, making the experience of debugging a specification somewhat ad hoc and unstructured, and a source of frustration for the user. This paper describes an extension to the LTLMoP toolkit for robot mission planning that encloses the control-generation process in a layer of automated reasoning to identify the cause of failure, and targets the users attention to flawed portions of the specification. <s> BIB013 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> In this paper we assess the feasibility of using formal methods, and model checking in particular, for the certification of Unmanned Aircraft Systems (UAS) within civil airspace. We begin by modelling a basic UAS control system in PROMELA, and verify it against a selected subset of the CAA's Rules of the Air using the SPIN model checker. Next we build a more advanced UAS control system using the autonomous agent language Gwendolen, and verify it against the small subset of the Rules of the Air using the agent model checker AJPF. We introduce more advanced autonomy into the UAS agent and show that this too can be verified. Finally we compare and contrast the various approaches, discuss the paths towards full certification, and present directions for future research. <s> BIB014 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> Verification of component-based systems still suffers from limitations such as state space explosion since a large number of different components may interact in an heterogeneous environment. Those limitations entail the need for complementary verification methods such as runtime verification based on dynamic analysis and prone to scalability. In this paper, we integrate runtime verification into the BIP (Behavior, Interaction, and Priority) framework. BIP is a powerful component-based framework for the construction of heterogeneous systems. Our method augments BIP systems with monitors checking a user-provided specification. This method has been implemented in RV-BIP, a prototype tool that we used to validate the whole approach on a robotic application. <s> BIB015 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> The paper describes a design specification process for the development of novel and intelligent surgical robots. Nowadays, surgical robots are usually controlled by the surgeons manually by using teleoperation. The possibility to carry out simple surgical actions automatically has been the subject of academical research, but very few real-world applications exist. The main objective of this research is to address realistic case studies and develop systems and methods to provide surgeons with autonomous robotic assistants, performing basic surgical actions by combining sensing, dexterity and cognitive capabilities. This goal can only be achieved by means of a formal and rigorous assesment of surgical requirements, so that they can be analysed and translated into behavioral specifications for an autonomous robotic system. Therefore, the paper describes the application of Requirements Engineering to surgical knowledge formalization and propose a methodology for the transformation of requirements into formal models of robotic tasks. <s> BIB016 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> In this paper, we propose a novel top-down design method for the development of collective behaviors of swarm robotics systems called property-driven design. Swarm robotics systems are usually designed and developed using a code-and-fix approach, that is, the developer devises, tests and modifies the individual robot behaviors until a desired collective behavior is obtained. The code-and-fix approach can be very time consuming and relies completely on the ingenuity and expertise of the designer. The idea of property-driven design is that a swarm robotics system can be described by specifying formally a set of desired properties. In an iterative process similar to test-driven development, the developer produces a model of the system that satisfies the desired properties. Subsequently, the system is implemented in simulation and using real robots. Property-driven design helps to minimize the risk of developing a system that does not satisfy the required properties, and to promote the reuse of hardware independent models. In this paper, we start by giving a general description of the method. We then present a possible way to apply it by using Discrete Time Markov Chains (DTMC) and Probabilistic Computation Tree Logic* (PCTL*). Finally, we conclude by presenting the application of the proposed method to the design and development of a swarm robotics system performing aggregation. <s> BIB017 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> A robot swarm is a collection of simple robots designed to work together to carry out some task. Such swarms rely on the simplicity of the individual robots; the fault tolerance inherent in having a large population of identical robots; and the self-organised behaviour of the swarm as a whole. Although robot swarms present an attractive solution to demanding real-world applications, designing individual control algorithms that can guarantee the required global behaviour is a difficult problem. In this paper we assess and apply the use of formal verification techniques for analysing the emergent behaviours of robotic swarms. These techniques, based on the automated analysis of systems using temporal logics, allow us to analyse whether all possible behaviours within the robot swarm conform to some required specification. In particular, we apply model-checking, an automated and exhaustive algorithmic technique, to check whether temporal properties are satisfied on all the possible behaviours of the system. We target a particular swarm control algorithm that has been tested in real robotic swarms, and show how automated temporal analysis can help to refine and analyse such an algorithm. <s> BIB018 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> We propose a methodology for decentralized multi-agent control from Linear Temporal Logic (LTL) specifications. Each agent receives an independent specification to formally synthesize its own hybrid controller. Mutual satisfiability is not a priori guaranteed. Due to limited communication, the agents utilize meeting events to exchange their controller automata and verify satisfiability through model checking. Local interaction only when common atomic propositions exist reduces the overall computational cost, facilitating scalability. Provably correct collision avoidance and convergence is ensured by Decentralized Multi-Agent Navigation Functions. <s> BIB019 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> An alternative to deploying a single robot of high complexity can be to utilise robot swarms comprising large numbers of identical, and much simpler, robots. Such swarms have been shown to be adaptable, fault-tolerant and widely applicable. However, designing individual robot algorithms to ensure effective and correct overall swarm behaviour is actually very difficult. While mechanisms for assessing the effectiveness of any swarm algorithm before deployment are essential, such mechanisms have traditionally involved either computational simulations of swarm behaviour, or experiments with robot swarms themselves. However, such simulations or experiments cannot, by their nature, analyse all possible swarm behaviours. In this paper, we will develop and apply the use of automated probabilistic formal verification techniques to robot swarms, involving an exhaustive mathematical analysis, in order to assess whether swarms will indeed behave as required. In particular we consider a foraging robot scenario to which we apply probabilistic model checking. <s> BIB020 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> We present a novel formal verification approach for collective robotic systems that is based on the use of the formal language Klaim and related analysis tools. While existing approaches focus on either micro- or macroscopic views of a system, we model aspects of both the robot hardware and behaviour, as well as relevant aspects of the environment. We illustrate our approach through a robotics scenario, in which three robots cooperate in a decentralized fashion to transport an object to a goal area. We first model the scenario in Klaim. Subsequently, we introduce random aspects to the model by stochastically specifying actions execution time. Unlike other approaches, the specification thus obtained enables quantitative analysis of crucial properties of the system. We validate our approach by comparing the results with those obtained through physics-based simulations. <s> BIB021 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> We have recently started an effort to combine a state of the art tool for developing functional modules of robotic systems (G^e^noM) with a component based framework for implementing embedded real-time systems (BIP). Unlike some works which study the connection between formal approaches and the highest (decisional) level of the robot software architecture, where deliberative activities such as planning, diagnostics, and execution control are conducted, we tackle the problem of using formal methods for developing modules of the functional level of robots. Little attention has been drawn to the development of these modules whose robustness is paramount to the robustness of the overall platform. To this end, we have successfully developed the G^e^noM/BIP component based design approach and applied it to the functional level of a complex exploration rover. Here, we report on this work, and show how we: (i) produce a very fine grained formal computational model of the robot functional level; (ii) run the BIP engine on the real robot, which executes and enforces the model semantics at runtime; and (iii) check the model offline for deadlock-freedom, as well as other safety properties. Moreover, we also extended this paradigm in a number of promising directions: (i) introduced a real-time BIP engine which can now use and control a timed BIP model; (ii) distributed the model and the engine over multiple CPUs; (iii) proposed a user-friendly language for specifying constraints on the model; and (iv) linked the model with a temporal plan execution controller. Interestingly, although our approach was initially proposed for the lowest level of robot architectures, these more recent extensions now allow us to model and manage the deliberation taking place at the decisional layer. <s> BIB022 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> We present a computational framework for automatic synthesis of control and communication strategies for a robotic team from task specifications that are given as regular expressions about servicing requests in an environment. We assume that the location of the requests in the environment and the robot capacities and cooperation requirements to service the requests are known. Our approach is based on two main ideas. First, we extend recent results from formal synthesis of distributed systems to check for the distributability of the task specification and to generate local specifications, while accounting for the service and communication capabilities of the robots. Second, by using a technique that is inspired by linear temporal logic model checking, we generate individual control and communication strategies. We illustrate the method with experimental results in our robotic urban-like environment. <s> BIB023 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> I l l u S t r a t I o n b y a l I C I a k u b I S t a /a n D r I J b o r y S a S S o C I a t e S in This arTiCle we consider the question: How should autonomous systems be analyzed? in particular, we describe how the confluence of developments in two areas—autonomous systems architectures and formal verification for rational agents—can provide the basis for the formal verification of autonomous systems behaviors. We discuss an approach to this question that involves: 1. Modeling the behavior and describing the interface (input/output) to an agent in charge of making decisions within the system; 2. Model checking the agent within an unrestricted environment representing the “real world” and those parts of the systems external to the agent, in order to establish some property, j; 3. Utilizing theorems or analysis of the environment, in the form of logical statements (where necessary), to derive properties of the larger system; and 4. if the agent is refined, modify (1), but if environmental properties are clarified, modify (3). Autonomous systems are now being deployed in safety, mission, or business critical scenarios, which means a thorough analysis of the choices the core software might make becomes crucial. But, should the analysis and verification of autonomous software be treated any differently than traditional software used in critical situations? Or is there something new going on here? Autonomous systems are systems that decide for themselves what to do and when to do it. Such systems might seem futuristic, but they are closer than we might think. Modern household, business, and industrial systems increasingly incorporate autonomy. There are many examples, all varying in the degree of autonomy used, from almost pure human control to fully autonomous activities with minimal human interaction. Application areas are broad, ranging from healthcare monitoring to autonomous vehicles. But what are the reasons for this increase in autonomy? Typically, autonomy is used in systems that: 1. must be deployed in remote environments where direct human control is infeasible; 2. must be deployed in hostile environments where it is dangerous for humans to be nearby, and so difficult for humans to assess the possibilities; 3. involve activity that is too lengthy Verifying autonomous systems Doi:10.1145/2494558 <s> BIB024 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> 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. <s> BIB025 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> In this paper we analyse a swarm robotics system using Bio-PEPA. Bio-PEPA is a process algebra language originally developed to analyse biochemical systems. A swarm robotics system can be analysed at two levels: the macroscopic level, to study the collective behaviour of the system, and the microscopic level, to study the robot-to-robot and robot-to- environment interactions. In general, multiple models are necessary to analyse a system at different levels. However, developing multiple models increases the effort needed to analyse a system and raises issues about the consistency of the results. Bio-PEPA, instead, allows the researcher to perform stochastic simulation, fluid flow (ODE) analysis and statistical model checking using a single description, reducing the effort necessary to perform the analysis and ensuring consistency between the results. Bio-PEPA is well suited for swarm robotics systems: by using Bio-PEPA it is possible to model distributed systems and their space- time characteristics in a natural way. We validate our approach by modelling a collective decision-making behaviour. <s> BIB026 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> We applied quantified differential-dynamic logic (QdL) to analyze a control algorithm designed to provide directional force feedback for a surgical robot. We identified problems with the algorithm, proved that it was in general unsafe, and described exactly what could go wrong. We then applied QdL to guide the development of a new algorithm that provides safe operation along with directional force feedback. Using \KeYmaeraD (a tool that mechanizes QdL), we created a machine-checked proof that guarantees the new algorithm is safe for all possible inputs. <s> BIB027 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> Nowadays, robots interact more frequently with a dynamic environment outside limited manufacturing sites and in close proximity with humans. Thus, safety of motion and obstacle avoidance are vital safety features of such robots. We formally study two safety properties of avoiding both stationary and moving obstacles: (i) passive safety, which ensures that no collisions can happen while the robot moves, and (ii) the stronger passive friendly safety in which the robot further maintains sufficient maneuvering distance for obstacles to avoid collision as well. We use hybrid system models and theorem proving techniques that describe and formally verify the robot’s discrete control decisions along with its continuous, physical motion. Moreover, we formally prove that safety can still be guaranteed despite location and actuator uncertainty. <s> BIB028 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> In this paper, we present the current results of the newly formed IEEE-RAS Working Group, named Ontologies for Robotics and Automation. In particular, we introduce a core ontology that encompasses a set of terms commonly used in Robotics and Automation along with the methodology we have adopted. Our work uses ISO/FDIS 8373 standard developed by the ISO/TC184/SC2 Working Group as a reference. This standard defines, in natural language, some generic terms which are common in Robotics and Automation such as robot, robotic device, etc. Furthermore, we discuss the ontology development process employed along with the problems and decisions taken. <s> BIB029 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> We present ROSRV, a runtime verification framework for robotic applications on top of the Robot Operating System (ROS [8]), a widely used open-source framework for robot software development. ROSRV aims to address the safety and security issues of robots by providing a transparent monitoring infrastructure that intercepts and monitors the commands and messages passing through the system. Safety and security properties can be defined in a formal specification language, and are ensured by automatically generated monitors. ROSRV integrates seamlessly with ROS—no change in ROS nor the application code is needed. ROSRV has been applied and evaluated on a commercial robot. <s> BIB030 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> Self-adaptation enables a software system to deal autonomously with uncertainties, such as dynamic operating conditions that are difficult to predict or changing goals. A common approach to realize self-adaptation is with a MAPE-K feedback loop that consists of four adaptation components: Monitor, Analyze, Plan, and Execute. These components share Knowledge models of the managed system, its goals and environment. To provide guarantees of the adaptation goals, state of the art approaches propose using formal models of the knowledge. However, less attention is given to the formalization of the adaptation components themselves, which is important to provide guarantees of correctness of the adaptation behavior (e.g., does the execute component execute the plan correctly?). We propose Active FORmal Models for Self-adaptation (ActivFORMS) that uses an integrated formal model of the adaptation components and knowledge models. The formal model is directly executed by a virtual machine to realize adaptation, hence active model. The contributions of ActivFORMS are: (1) the approach assures that the adaptation goals that are verified offline are guaranteed at runtime, and (2) it supports dynamic adaptation of the active model to support changing goals. We show how we have applied ActivFORMS for a small-scale robotic system. <s> BIB031 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> Human‐robot teams are likely to be used in a variety of situations wherever humans require the assistance of robotic systems. Obvious examples include healthcare and manufacturing, in which people need the assistance of machines to perform key tasks. It is essential for robots working in close proximity to people to be both safe and trustworthy. In this paper we examine formal verification of a high-level planner/scheduler for autonomous personal robotic assistants such as CareO-bot R . We describe how a model of Care-O-bot and its environment was developed using Brahms, a multiagent workflow language. Formal verification was then carried out by translating this to the input language of an existing model checker. Finally we present some formal verification results and describe how these could be complemented by simulation-based testing and realworld end-user validation in order to increase the practical and perceived safety and trustworthiness of robotic assistants. <s> BIB032 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> Beliefs play an important role in human-robot teaming scenarios, where the robots must reason about other agents' intentions and beliefs in order to inform their own plan generation process, and to successfully coordinate plans with the other agents. In this paper, we cast the evolving and complex structure of beliefs, and inference over them, as a planning and plan recognition problem. We use agent beliefs and intentions modeled in terms of predicates in order to create an automated planning problem instance, which is then used along with a known and complete domain model in order to predict the plan of the agent whose beliefs are being modeled. Information extracted from this predicted plan is used to inform the planning process of the modeling agent, to enable coordination. We also look at an extension of this problem to a plan recognition problem. We conclude by presenting an evaluation of our technique through a case study implemented on a real robot. <s> BIB033 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> Before autonomous robotics can be used for dangerous or critical missions, performance guarantees should be made available. This paper overviews a software system for the verification of behavior-based controllers in context of chosen hardware and environmental models. Robotic controllers are automatically translated to a process algebra. The system comprising both the robot and the environment are then evaluated by VIPARS, a verification software module in development, and compared to specific performance criteria. The user is returned a probability that the performance criteria will hold in the uncertainty of real-world conditions. Experimental results demonstrate accurate verification for a mission related to the search for a biohazard. <s> BIB034 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> Ensuring that autonomous systems work ethically is both complex and difficult. However, the idea of having an additional ‘governor’ that assesses options the system has, and prunes them to select the most ethical choices is well understood. Recent work has produced such a governor consisting of a ‘consequence engine’ that assesses the likely future outcomes of actions then applies a Safety/Ethical logic to select actions. Although this is appealing, it is impossible to be certain that the most ethical options are actually taken. In this paper we extend and apply a well-known agent verification approach to our consequence engine, allowing us to verify the correctness of its ethical decision-making. <s> BIB035 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> Designing software systems that have to deal with dynamic operating conditions, such as changing availability of resources and faults that are difficult to predict, is complex. A promising approach to handle such dynamics is self-adaptation that can be realized by a MAPE-K feedback loop (Monitor-Analyze-Plan-Execute plus Knowledge). To provide evidence that the system goals are satisfied, given the changing conditions, the state of the art advocates the use of formal methods. However, little research has been done on consolidating design knowledge of self-adaptive systems. To support designers, this paper contributes with a set of formally specified MAPE-K templates that encode design expertise for a family of self-adaptive systems. The templates comprise: (1) behavior specification templates for modeling the different components of a MAPE-K feedback loop (based on networks of timed automata), and (2) property specification templates that support verification of the correctness of the adaptation behaviors (based on timed computation tree logic). To demonstrate the reusability of the formal templates, we performed four case studies in which final-year Masters students used the templates to design different self-adaptive systems. <s> BIB036 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> Abstract Autonomous systems such as unmanned vehicles are beginning to operate within society. All participants in society are required to follow specific regulations and laws. An autonomous system cannot be an exception. Inevitably an autonomous system will find itself in a situation in which it needs to not only choose to obey a rule or not, but also make a complex ethical decision. However, there exists no obvious way to implement the human understanding of ethical behaviour in computers. Even if we enable autonomous systems to distinguish between more and less ethical alternatives, how can we be sure that they would choose right? We consider autonomous systems with a hybrid architecture in which the highest level of reasoning is executed by a rational (BDI) agent. For such a system, formal verification has been used successfully to prove that specific rules of behaviour are observed when making decisions. We propose a theoretical framework for ethical plan selection that can be formally verified. We implement a rational agent that incorporates a given ethical policy in its plan selection and show that we can formally verify that the agent chooses to execute, to the best of its beliefs, the most ethical available plan. <s> BIB037 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> A new agent architecture called Limited Instruction Set Agent (LISA) is introduced for autonomous control. The new architecture is based on previous implementations of AgentSpeak and it is structurally simpler than its predecessors with the aim of facilitating design-time and run-time verification methods. The process of abstracting the LISA system to two different types of discrete probabilistic models (DTMC and MDP) is investigated and illustrated. The LISA system provides a tool for complete modelling of the agent and the environment for probabilistic verification. The agent program can be automatically compiled into a Discrete-Time Markov Chain (DTMC) or a Markov Decision Process (MDP) model for verification with PRISM. The automatically generated PRISM model can be used for both design-time and run-time verification. The run-time verification is investigated and illustrated in the LISA system as an internal modelling mechanism for prediction of future outcomes. <s> BIB038 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> It is essential for robots working in close proximity to people to be both safe and trustworthy. We present a case study on formal verification for a high-level planner/scheduler for the Care-O-bot, an autonomous personal robotic assistant. We describe how a model of the Care-O-bot and its environment was developed using Brahms, a multiagent workflow language. Formal verification was then carried out by automatically translating this model to the input language of an existing model checker. Four sample properties based on system requirements were verified. We then refined the environment model three times to increase its accuracy and the persuasiveness of the formal verification results. The first refinement uses a user activity log based on real-life experiments, but is deterministic. The second refinement uses the activities from the user activity log nondeterministically. The third refinement uses “conjoined activities” based on an observation that many user activities can overlap. The four samples properties were verified for each refinement of the environment model. Finally, we discuss the approach of environment model refinement with respect to this case study. <s> BIB039 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> Deep neural networks have achieved impressive experimental results in image classification, but can surprisingly be unstable with respect to adversarial perturbations, that is, minimal changes to the input image that cause the network to misclassify it. With potential applications including perception modules and end-to-end controllers for self-driving cars, this raises concerns about their safety. We develop a novel automated verification framework for feed-forward multi-layer neural networks based on Satisfiability Modulo Theory (SMT). We focus on safety of image classification decisions with respect to image manipulations, such as scratches or changes to camera angle or lighting conditions that would result in the same class being assigned by a human, and define safety for an individual decision in terms of invariance of the classification within a small neighbourhood of the original image. We enable exhaustive search of the region by employing discretisation, and propagate the analysis layer by layer. Our method works directly with the network code and, in contrast to existing methods, can guarantee that adversarial examples, if they exist, are found for the given region and family of manipulations. If found, adversarial examples can be shown to human testers and/or used to fine-tune the network. We implement the techniques using Z3 and evaluate them on state-of-the-art networks, including regularised and deep learning networks. We also compare against existing techniques to search for adversarial examples and estimate network robustness. <s> BIB040 </s> Formal Specification and Verification of Autonomous Robotic Systems: A Survey <s> Logics 6 32 <s> Noisy data, non-convex objectives, model misspecification, and numerical instability can all cause undesired behaviors in machine learning systems. As a result, detecting actual implementation errors can be extremely difficult. We demonstrate a methodology in which developers use an interactive proof assistant to both implement their system and to state a formal theorem defining what it means for their system to be correct. The process of proving this theorem interactively in the proof assistant exposes all implementation errors since any error in the program would cause the proof to fail. As a case study, we implement a new system, Certigrad, for optimizing over stochastic computation graphs, and we generate a formal (i.e. machine-checkable) proof that the gradients sampled by the system are unbiased estimates of the true mathematical gradients. We train a variational autoencoder using Certigrad and find the performance comparable to training the same model in TensorFlow. <s> BIB041
Temporal Logic 0 BIB016 , BIB017 , BIB035 , BIB037 , BIB011 , BIB018 , BIB019 , BIB024 , BIB025 , BIB030 ,  , BIB031 , BIB036 , BIB038 , BIB004 , BIB012 , BIB008 , BIB020 , BIB001 ,  , BIB026 , BIB005 ,  , BIB013 , BIB014 , BIB032 , BIB039 27 Dynamic Logic BIB027 , BIB028 2 BIB027 , BIB028 2 Other Logics BIB016 , [64] , BIB021 , BIB033 4 [64] , BIB021 , BIB033 3 Process Algebra  , BIB026 , BIB034 3 BIB034 1 Ontology BIB009 , BIB005 , BIB029 , BIB006 4 0 Other BIB035 , BIB037 , BIB024 ,  , BIB014 5 BIB022 , BIB002 ,  , BIB003 , BIB023 , BIB010 , BIB015 , BIB007 8 Note: Some references appear in one half of the table but not the other because they only describe the specification of the system (or vice versa). Logics have been further subdivided into Temporal, Dynamic, and Other Logics. Agent-based systems are not the only model of autonomy, but they encapsulate the description of autonomous behavior into one component and can be used to model interactions with other actors and the environment. A rational agent can explain its reasoning, which can be helpful during verification and in tackling the challenge of providing sufficient evidence for a certification body or to gain public trust (recall Section 3.2). Ensuring that agents are verifiable is a focus in the literature. Multirobot systems-both homogeneous swarms and heterogeneous teams-provide an interesting challenge to robotic systems. They provide resilient architectures, but their decentralization brings specific challenges for formal verification. Reconfigurable systems are key to dealing with changing environments and mission goals. However, ensuring that they reconfigure themselves in a safe way is a challenge, and the key focus in the literature. These are the internal challenges that we derived from the literature, but of course, there may be others. For example, machine-learning systems are becoming more prevalent in autonomous robotic systems and are notoriously difficult to formally verify, although recent work has emerged BIB040 BIB041 .