Search NASA⌕ Search

SEARCH · Search NASA

Results for “state machine”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 271 records · Page 15

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↗

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↗

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↗

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↗

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↗

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↗

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↗

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↗

Ontology Language to Support Description of Experiment Control System Semantics, Collaborative Knowledge-Base Design and Ontology Reuse

In this paper we discuss the control domain specific ontology that is built on top of the domain-neutral Resource Definition Framework (RDF). Specifically, we will discuss the relevant set of ontology concepts along with the relationships among them in order to describe experiment control components and generic event-based state machines. Control Oriented Ontology Language (COOL) is a meta-data modeling language that provides generic means for representation of physics experiment control processes and components, and their relationships, rules and axioms. It provides a semantic reference frame that is useful for automating the communication of information for configuration, deployment and operation. COOL has been successfully used to develop a complete and dynamic knowledge-base for experiment control systems, developed using the AFECS framework.

43 PARTICLE ACCELERATORS↗

Fast BPM data distribution for global orbit feedback using commercial gigabit ethernet technology

In order to correct beam perturbations in RHIC around 10Hz, a new fast data distribution network was required to deliver BPM position data at rates several orders of magnitude above the capability of the existing system. The urgency of the project limited the amount of custom hardware that could be developed, which dictated the use of as much commercially available equipment as possible. The selected architecture uses a custom hardware interface to the existing RHIC BPM electronics together with commercially available Gigabit Ethernet switches to distribute position data to devices located around the collider ring. Using the minimum Ethernet packet size and a field programmable gate array (FPGA) based state machine logic instead of a software based driver, real-time and deterministic data delivery is possible using Ethernet. The method of adapting this protocol for low latency data delivery, bench testing of Ethernet hardware, and the logic to construct Ethernet packets using FPGA hardware will be discussed. A robust communications system using almost all commercial off-the-shelf equipment was developed in under a year which enabled retrofitting of the existing RHIC BPM system to provide 10 KHz data delivery for a global orbit feedback scheme using 72 BPMs. Total latencies from data acquisition at the BPMs to delivery at the controller modules, including very long transmission distances, were kept under 100 {micro}s, which provide very little phase error in correcting the 10 Hz oscillations. Leveraging off of the speed of Gigabit Ethernet and wide availability of Ethernet products enabled this solution to be fully implemented in a much shorter time and at lower cost than if a similar network was developed using a proprietary method.

43 PARTICLE ACCELERATORS↗

Massively Multi-core Acceleration of a Document-Similarity Classifier to Detect Web Attacks

This paper describes our approach to adapting a text document similarity classifier based on the Term Frequency Inverse Document Frequency (TFIDF) metric to two massively multi-core hardware platforms. The TFIDF classifier is used to detect web attacks in HTTP data. In our parallel hardware approaches, we design streaming, real time classifiers by simplifying the sequential algorithm and manipulating the classifier's model to allow decision information to be represented compactly. Parallel implementations on the Tilera 64-core System on Chip and the Xilinx Virtex 5-LX FPGA are presented. For the Tilera, we employ a reduced state machine to recognize dictionary terms without requiring explicit tokenization, and achieve throughput of 37MB/s at slightly reduced accuracy. For the FPGA, we have developed a set of software tools to help automate the process of converting training data to synthesizable hardware and to provide a means of trading off between accuracy and resource utilization. The Xilinx Virtex 5-LX implementation requires 0.2% of the memory used by the original algorithm. At 166MB/s (80X the software) the hardware implementation is able to achieve Gigabit network throughput at the same accuracy as the original algorithm.

97 MATHEMATICS AND COMPUTING↗

Hardware support for software controlled fast reconfiguration of performance counters

Hardware support for software controlled reconfiguration of performance counters may include a plurality of performance counters collecting one or more counts of one or more selected activities. A storage element stores data value representing a time interval, and a timer element reads the data value and detects expiration of the time interval based on the data value and generates a signal. A plurality of configuration registers stores a set of performance counter configurations. A state machine receives the signal and selects a configuration register from the plurality of configuration registers for reconfiguring the one or more performance counters.

97 MATHEMATICS AND COMPUTING↗

Hardware support for software controlled fast reconfiguration of performance counters

Hardware support for software controlled reconfiguration of performance counters may include a plurality of performance counters collecting one or more counts of one or more selected activities. A storage element stores data value representing a time interval, and a timer element reads the data value and detects expiration of the time interval based on the data value and generates a signal. A plurality of configuration registers stores a set of performance counter configurations. A state machine receives the signal and selects a configuration register from the plurality of configuration registers for reconfiguring the one or more performance counters.

97 MATHEMATICS AND COMPUTING↗

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↗

Hardware support for collecting performance counters directly to memory

Hardware support for collecting performance counters directly to memory, in one aspect, may include a plurality of performance counters operable to collect one or more counts of one or more selected activities. A first storage element may be operable to store an address of a memory location. A second storage element may be operable to store a value indicating whether the hardware should begin copying. A state machine may be operable to detect the value in the second storage element and trigger hardware copying of data in selected one or more of the plurality of performance counters to the memory location whose address is stored in the first storage element.

97 MATHEMATICS AND COMPUTING↗

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↗

Code Seal v 1.0

CodeSeal is a Sandia National Laboratories developed technology that provides a means of securely obfuscating finite state machines in a mathematically provable way. The technology was developed in order to provide a solution for anti-reverse 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, tamper-protected device, however, Sandia has developed an effective method for obfuscating code. An open publication describing the technology in more detail can be found at http://eprint.iacr.org/2008/184.pdf.Independent Software/Hardware monitors, Use control, Supervisory Control And Data Acquisition (SCADA), Algorithm obfuscation

Chavez, Adrian↗

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↗