Results for “state machine” — Page 14

NASA NTRS2020

Actor-based Runtime Verification with MESA

This work presents a runtime verification approach implemented in the tool MESA (MEssage-based System Analysis) which allows for using concurrent monitors to check for properties specified in data parameterized temporal logic and state machines. The tool is implemented as an internal Scala DSL. We employ the actor programming model to implement MESA where monitors are captured by concurrent actors that communicate via messaging. The paper presents a case study in which MESA is used to effectively monitor a large number of flights from live US airspace data streams. We also perform an empirical study by conducting experiments using monitoring systems with different num- bers of concurrent monitors and different layers of indexing on the data contained in events. The paper describes the experiments, evaluates the results, and discusses challenges faced during the study. The evaluation shows the value of combining concurrency with indexing to handle data rich events.

Mehlitz, Peter↗

NASA NTRS2020

Model Checking as a Service: Towards Pragmatic Hidden Formal Methods

Executable models can be used to support all engineering activities in Model-Based Systems Engineering. Testing and simulation of such models can provide early feedback about design choices. How-ever, in today’s complex systems failures could arise due to subtle errors that are hard to find without checking all possible execution paths. Formal methods, and especially model checking can uncover such subtle errors, yet their usage in practice is limited due to the specialized expertise and high computing power required. There-fore we created an automated, cloud-based environment that can verify complex reachability properties on SysML State Machines using hidden model checkers. The approach and the prototype is illustrated using an example from the aerospace domain.

Karban, Robert↗

NASA NTRSDate not supplied

Humans as Automation Failsafe: HAT Assistant

Humans are frequently left to “backstop” automated systems, and Human Factors specialists have argued against this for decades with, at best, partial success. What if we took a different tack... and designed to support it? The participants were involved in a recent effort to review and document cases across multiple domains where operators acted as a “failsafe” for automation, intervening in unanticipated situations to maximize success and minimize damage. We defined a “Human As Failsafe” (HAF) incident and then investigated conditions and practices making HAF success more or less likely. Analyzing these historical incidents, we suggested remediation approaches. The project also examined the legal concept of culpability (i.e., when intervention should have happened but didn’t) and proposed a state-machine-based analytic simulation to identify when HAF interventions are plausible. The panel objective will be to briefly present these concepts, but more generally to discuss designing for inevitable HAF events. This presentation with review the concept of a HAT Assistant to support multi-vehicle control of drones in a wildland firefighting context.

humans as failsafe↗

NASA NTRSDate not supplied

Authoring, Analyzing, and Monitoring Requirements for a Lift-Plus-Cruise Aircraft

Requirements specification and analysis is widely applied to ensure the correctness of industrial systems in safety critical domains. Requirements are often initially written in natural language, which is highly ambiguous, and as a second step transformed into a language with rigorous semantics for formal analysis. [Question/problem] In this paper, we report on our experience in requirements creation and analysis, as well as run-time monitor generation using the Formal Requirement Elicitation Tool (FRET), on an industrial case study for a Lift-Plus-Cruise concept aircraft. [Principal ideas/results] We study the creation of requirements directly in the structured language of FRET without a prior definition of the same requirements in natural language. We focus on requirements describing state machines and discuss the challenges that we faced, in terms of creating requirements and generating monitors. We demonstrate how realizability, i.e., checking whether a requirements specification can be implemented, is crucial for understanding temporal interdependencies among requirements. [Contribution] Our study is the first complete attempt at using FRET to create industrial, realizable requirements and generate run-time monitors. Insight from lessons learned was materialized into new features in the FRET and JKind analysis frameworks.

Requirements engineering↗

NASA NTRSDate not supplied

Authoring, Analyzing, and Monitoring Requirements for a Lift-Plus-Cruise Aircraft

Requirements specification and analysis is widely applied to ensure the correctness of industrial systems in safety critical domains. Requirements are often initially written in natural language, which is highly ambiguous, and as a second step transformed into a language with rigorous semantics for formal analysis. In this paper, we report on our experience in requirements creation and analysis, as well as run-time monitor generation using the Formal Requirement Elicitation Tool (FRET), on an industrial case study for a Lift-Plus-Cruise concept aircraft. We study the creation of requirements directly in the structured language of FRET without a prior definition of the same requirements in natural language. We focus on requirements describing state machines and discuss the challenges that we faced, in terms of creating requirements and generating monitors. We demonstrate how realizability, i.e., checking whether a requirements specification can be implemented, is crucial for understanding temporal interdependencies among requirements. Our study is the first complete attempt at using FRET to create industrial, realizable requirements and generate run-time monitors. Insight from lessons learned was materialized into new features in the FRET and JKind analysis frameworks.

Requirements engineering↗

NASA NTRS2023

Compliant Behaviors for Supervised and Autonomous Robotic Operations

The demands of traditional industrial robotics differ significantly from those of remote, supervised operations in hostile environments, such as operations in space. While industry requires robots that can perform repetitive tasks with precision and speed, the space environment needs robots to cope with uncertainties, dynamics, and communication delays or interruptions, similar to human astronauts. These demands make a well-suited application for compliant robotics and behavior-based programming. Pose Target Wrench Limiting (PTWL) is a compliant behavior paradigm developed specifically to meet these demands. PTWL controls a robot by moving a virtual attractor to a target pose. The attractor applies virtual forces, based on stiffness and damping presets, to an underlying admittance controller. Guided by virtual forces, the robot will follow the attractor until safety conditions are violated or success criteria are met. PTWL was tested on a variety of quasi-static and dynamic tasks that may be useful for future space operations. Results demonstrate that PTWL is a powerful tool. It makes teleoperation easy and safe for a wide range of quasi-static tasks. It also facilitates the creation of semi-autonomous state machines that can reliably complete complex tasks with minimal human intervention.

Joseph D. Cressman↗

NASA NTRS2020

Integrated Modeling and Development of Component-Based Embedded Software in Scala

Programming of embedded systems is challenging due to the low-level design patterns normally applied in the implementation of such systems. Furthermore, programming languages normally considered suitable for this level of programming, such as C and C++, are themselves low-level compared to more modern programming languages. We report on an effort exploring modeling and programming of embedded systems in modern high-level programming languages combining object-oriented and functional programming. We present an integration of four separate internal DSLs (libraries), considered useful for embedded program- ming, in the Scala programming language, for programming and testing component-based systems. These include a DSL for defining components and their connections, and a DSL for programming the individual components as hierarchical state machines. Two additional DSLs support testing, and include a DSL for writing temporal logic flavored test oracles for monitoring program executions, and a DSL for rule-based test input generation. The paper discusses the gap between Scala as used here and the needs for embedded systems programming.

Bocchino, Robert↗

NASA NTRS2023

Compliant Robotic Behaviors for Satellite Servicing

The demands of traditional industrial robotics differ significantly from those of space robotics. While industry requires robots that can perform repetitive tasks with precision and speed, the space environment needs robots to cope with uncertainties, dynamics, and communication delays or interruptions, similar to human astronauts. These demands make a well-suited application for compliant robotics and behavior-based programming. Pose Target Wrench Limiting (PTWL) is a compliant behavior paradigm developed specifically to meet these demands. PTWL controls a robot by moving a virtual attractor to a target pose. The attractor applies virtual forces, based on stiffness and damping presets, to an underlying admittance controller. Guided by virtual forces, the robot will follow the attractor until safety conditions are violated or success criteria are met. We tested PTWL on a variety of quasi-static tasks that may be useful for future space operations. Our results demonstrate that PTWL is an extremely powerful tool. It makes teleoperation easy and safe for a wide range of quasi-static tasks. It also facilitates the creation of semi-autonomous state machines that can reliably complete complex tasks with minimal human intervention.

Compliance↗

NASA NTRSDate not supplied

Design, Formalization, and Verification of Decision Making for Intelligent Systems

The development of autonomous systems requires a rigorous process that can guarantee a system’s reliability in critical applications. At its core, an autonomous system bases its behavior on a well-defined decision making system. In this paper, we present a methodological basis for the design, formalization and formal verification of Decision Making systems for autonomous agents. The approach is generally applicable to operational objectives that can be functionally decomposed and subsequently represented as Hierarchical Finite State Machines. As a case study, we present the application of this method to implement a Decision Making model in Simulink. Furthermore, we present how we use NASA’s FRET tool to write requirements in structured natural language and generate formal specifications that can be automatically digested by NASA’s CoCoSim tool. Finally, we present how, by leveraging CoCoSim, we perform formal verification against the Simulink model and present analysis results.

Model-based development↗

NASA NTRSDate not supplied

Design, Formalization, and Verification of Decision Making for Intelligent Systems

The development of autonomous systems requires a rigorous process that can guarantee a system’s reliability in critical applications. At its core, an autonomous system bases its behavior on a well-defined decision making system. In this paper, we present a methodological basis for the design, formalization and formal verification of Decision Making systems for autonomous agents. The approach is generally applicable to operational objectives that can be functionally decomposed and subsequently represented as Hierarchical Finite State Machines. As a case study, we present the application of this method to implement a Decision Making model in Simulink. Furthermore, we present how we use NASA’s FRET tool to write requirements in structured natural language and generate formal specifications that can be automatically digested by NASA’s CoCoSim tool. Finally, we present how, by leveraging CoCoSim, we perform formal verification against the Simulink model and present analysis results.

Model-based development↗

NASA NTRSDate not supplied

Preliminary Design of Robotic Control Software for Mars Sample Return - Capture, Containment, and Return System

The Mars Sample Return (MSR) campaign aims to acquire and return to Earth a set of Mars samples for investigation in terrestrial laboratories. Mars 2020 has collected an adequate number of samples and deposited them in sealed sample tubes at a designated Martian depot. Sample tubes will be placed in cylindrical containers called Orbiting Samples (OS) by the Perseverance Rover, and later brought to Earth by the Earth Return Orbiter (ERO) and the MSR - Capture, Containment, and Return System (CCRS). Robot Software (RSW) is a set of software processes for commanding and monitoring the avionics that controls robotic mechanisms designed to sterilize and install OS into Earth Entry System (EES) for return to Earth. This paper describes a preliminary design of RSW including motion modes, architecture, and finite state machine. Additionally, software engineering procedures and testing of RSW is provided. A preliminary performance analysis is presented and the paper concludes with future work and a discussion of design decisions.

MSR↗

DOE OSTI2014

An Adaptive Memory Interface Controller for Improving Bandwidth Utilization of Hybrid and Reconfigurable Systems

Emerging applications such as data mining, bioinformatics, knowledge discovery, social network analysis are irregular. They use data structures based on pointers or linked lists, such as graphs, unbalanced trees or unstructures grids, which generates unpredictable memory accesses. These data structures usually are large, but difficult to partition. These applications mostly are memory bandwidth bounded and have high synchronization intensity. However, they also have large amounts of inherent dynamic parallelism, because they potentially perform a task for each one of the element they are exploring. Several efforts are looking at accelerating these applications on hybrid architectures, which integrate general purpose processors with reconfigurable devices. Some solutions, which demonstrated significant speedups, include custom-hand tuned accelerators or even full processor architectures on the reconfigurable logic. In this paper we present an approach for the automatic synthesis of accelerators from C, targeted at irregular applications. In contrast to typical High Level Synthesis paradigms, which construct a centralized Finite State Machine, our approach generates dynamically scheduled hardware components. While parallelism exploitation in typical HLS-generated accelerators is usually bound within a single execution flow, our solution allows concurrently running multiple execution flow, thus also exploiting the coarser grain task parallelism of irregular applications. Our approach supports multiple, multi-ported and distributed memories, and atomic memory operations. Its main objective is parallelizing as many memory operations as possible, independently from their execution time, to maximize the memory bandwidth utilization. This significantly differs from current HLS flows, which usually consider a single memory port and require precise scheduling of memory operations. A key innovation of our approach is the generation of a memory interface controller, which dynamically maps concurrent memory accesses to multiple ports. We present a case study on a typical irregular kernel, Graph Breadth First search (BFS), exploring different tradeoffs in terms of parallelism and number of memories.

BFS↗

DOE OSTI2015

Hardware enabled performance counters with support for operating system context switching

A device for supporting hardware enabled performance counters with support for context switching include a plurality of performance counters operable to collect information associated with one or more computer system related activities, a first register operable to store a memory address, a second register operable to store a mode indication, and a state machine operable to read the second register and cause the plurality of performance counters to copy the information to memory area indicated by the memory address based on the mode indication.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2016

Stochastic Modeling of Short-term Occupancy for Energy Efficient Buildings

In this paper, we present a simple yet effective algorithm to automatically assign reference temperature set-points based on the occupancy information. Both the binary and detailed occupancy estimation cases are considered. In the first case study, we assume the schedule involves only binary states (occupied or not occupied), i.e. the room is invariant. With long-term observations occupancy levels can be estimated using statistical tools. In the second case study, two techniques are introduced. Firstly, we propose an identification-based approaches. More precisely, we identify the models via Expectation Maximization (EM) approach. The statistical state space model is built in linear form for the mapping between the occupancy measurements and real occupancy states with noise considered. Secondly, we introduce a novel finite state automata (FSA) which is successfully reconstructed by general systems problem solver (GSPS). As far as we know, no studies have used the finite state machine or general system theory to estimate occupancy in buildings. All above estimates can be used to adaptively update the temperature set-points for Heating, Ventilation, and Air-Conditioning (HVAC) control strategy.

Djouadi, Seddik M↗

DOE OSTI2015

Code Seal v. 2.0

CodeSeal is a Sandia National Laboratories developed technology that provides a means of securely obfuscating finite state machines, ARM & x86 instruction sets in a mathematically provable way. The technology was developed in order to provide a solution for antireverse engineering, assured execution, and integrity of execution. CodeSeal accomplishes these goals with the addition of the concept of a trust anchor, a small piece of trust integrated into the system, to the model of code obfuscation. Code Obfuscation is an active area of academic research, but most findings have merely demonstrated that general obfuscation is impossible. By modifying the security model such that we may rely on the presence of a small, temper-protected device, however, Sandia has developed an effective method for obfuscating code.

Chavez, Adrian↗

DOE OSTI2017

Self-balanced modulation and magnetic rebalancing method for parallel multilevel inverters

A self-balanced modulation method and a closed-loop magnetic flux rebalancing control method for parallel multilevel inverters. The combination of the two methods provides for balancing of the magnetic flux of the inter-cell transformers (ICTs) of the parallel multilevel inverters without deteriorating the quality of the output voltage. In various embodiments a parallel multi-level inverter modulator is provide including a multi-channel comparator to generate a multiplexed digitized ideal waveform for a parallel multi-level inverter and a finite state machine (FSM) module coupled to the parallel multi-channel comparator, the FSM module to receive the multiplexed digitized ideal waveform and to generate a pulse width modulated gate-drive signal for each switching device of the parallel multi-level inverter. The system and method provides for optimization of the output voltage spectrum without influence the magnetic balancing.

24 POWER TRANSMISSION AND DISTRIBUTION↗

DOE OSTI2021

High-Level Synthesis of Parallel Specifications Coupling Static and Dynamic Controllers

The increased need for efficient ways to implement domain-specific accelerators is driving design methodologies towards the use of abstractions higher than the Register Transfer Level (RTL). In this scenario, High Level Synthesis (HLS) plays a significant role by enabling the automatic generation of custom hardware accelerators starting from high level descriptions (e.g., C code). Conventional HLS tools exploit parallelism mostly at the Instruction Level (ILP). They statically schedule the input specifications, and build centralized Finite State Machine (FSM) controllers. However, aggressive exploitation of ILP in many applications has diminishing returns and, usually, centralized approaches do not efficiently exploit coarser parallelism because FSMs are inherently serial. In this paper we present a HLS framework able to synthesize applications that, beside ILP, also expose Task Level Parallelism (TLP). An application can expose TLP through annotations that identify the parallel functions (i.e., tasks). To generate accelerators that efficiently execute concur- rent tasks, we need to solve several issues: devise a mechanism to support concurrent execution flows, exploit memory parallelism, and manage synchronization. To support concurrent execution flows, we introduce a novel adaptive controller. The adaptive controller is composed of a set of interacting control elements that independently manage the execution of a single operation or function call. These control elements check dependencies and resource constraints at runtime, enabling as soon as possible execution. To support parallel access to shared memories and synchronization, we introduce a novel Hierarchical Memory Interface (HMI). With respect to previous solutions, the proposed interface supports multi-ported memories and atomic memory operations, which commonly occur in parallel programming. Our framework can generate the hardware implementation of C functions by employing two different approaches, depending on its characteristics. If a function exposes TLP, then the framework generates hardware implementations based on the adaptive controller. Otherwise, the framework implements the function by exploiting a more conventional FSM approach, which is optimized for ILP exploitation. We evaluate our framework on a set of parallel applications, and show substantial performance improvements (average speedup of 4.7) with limited area over- heads (average area increase of 5.48 times).

Castellana, Vito G.↗

DOE OSTI2021

High-Level Synthesis of Parallel Specifications Coupling Static and Dynamic Controllers

The increased need for efficient ways to implement domain-specific accelerators is driving design methodologies towards the use of abstractions higher than the Register Transfer Level (RTL). In this scenario, High Level Synthesis (HLS) plays a significant role by enabling the automatic generation of custom hardware accelerators starting from high level descriptions (e.g., C code). Conventional HLS tools exploit parallelism mostly at the Instruction Level (ILP). They statically schedule the input specifications, and build centralized Finite State Machine (FSM) controllers. However, aggressive exploitation of ILP in many applications has diminishing returns and, usually, centralized approaches do not efficiently exploit coarser parallelism because FSMs are inherently serial. In this paper we present a HLS framework able to synthesize applications that, beside ILP, also expose Task Level Parallelism (TLP). An application can expose TLP through annotations that identify the parallel functions (i.e., tasks). To generate accelerators that efficiently execute concur- rent tasks, we need to solve several issues: devise a mechanism to support concurrent execution flows, exploit memory parallelism, and manage synchronization. To support concurrent execution flows, we introduce a novel adaptive controller. The adaptive controller is composed of a set of interacting control elements that independently manage the execution of a single operation or function call. These control elements check dependencies and resource constraints at runtime, enabling as soon as possible execution. To support parallel access to shared memories and synchronization, we introduce a novel Hierarchical Memory Interface (HMI). With respect to previous solutions, the proposed interface supports multi-ported memories and atomic memory operations, which commonly occur in parallel programming. Our framework can generate the hardware implementation of C functions by employing two different approaches, depending on its characteristics. If a function exposes TLP, then the framework generates hardware implementations based on the adaptive controller. Otherwise, the framework implements the function by exploiting a more conventional FSM approach, which is optimized for ILP exploitation. We evaluate our framework on a set of parallel applications, and show substantial performance improvements (average speedup of 4.7) with limited area over- heads (average area increase of 5.48 times).

Castellana, Vito G.↗