Engineering topics

Narkawicz, Anthony J.

Publications and source records attributed to Narkawicz, Anthony J..

14 records

NASA NTRS2018

UAS Autonomous Hazard Mitigation through Assured Compliance with Conformance Criteria

The behavior of a drone depends on the integrity of the data it uses and the reliability of the avionics systems that process that data to affect the operation of the aircraft. Commercial unmanned aircraft systems frequently rely on commercial-off-the-shelf and open source avionics components and data sources whose reliability and integrity are not easily assured. To mitigate failure events for aircraft that do not comply with conventional aviation safety standards, operational limitations are typically prescribed by regulators. Part 107 of the Federal Aviation Regulations serves as a good example of operational limitations that mitigate risk for small unmanned aircraft systems. These limitations, however, restrict growth possibilities for the industry. Any reasonable path toward achieving routine operation of all types of drones will have to address the need for assurance of avionics systems, especially their software. This paper discusses the possibility of strategically using assured systems as a stepping stone to routine operation of drones. A specimen system for assured geofencing, called Safeguard, is described as an example of such a stepping stone.

Dill, Evan, T.↗

NASA NTRS2016

Coordination Logic for Repulsive Resolution Maneuvers

This paper presents an algorithm for determining the direction an aircraft should maneuver in the event of a potential conflict with another aircraft. The algorithm is implicitly coordinated, meaning that with perfectly reliable computations and information, it will in- dependently provide directional information that is guaranteed to be coordinated without any additional information exchange or direct communication. The logic is inspired by the logic of TCAS II, the airborne system designed to reduce the risk of mid-air collisions between aircraft. TCAS II provides pilots with only vertical resolution advice, while the proposed algorithm, using a similar logic, provides implicitly coordinated vertical and horizontal directional advice.

Narkawicz, Anthony J.↗

NASA NTRS2015

Software Validation via Model Animation

This paper explores a new approach to validating software implementations that have been produced from formally-verified algorithms. Although visual inspection gives some confidence that the implementations faithfully reflect the formal models, it does not provide complete assurance that the software is correct. The proposed approach, which is based on animation of formal specifications, compares the outputs computed by the software implementations on a given suite of input values to the outputs computed by the formal models on the same inputs, and determines if they are equal up to a given tolerance. The approach is illustrated on a prototype air traffic management system that computes simple kinematic trajectories for aircraft. Proofs for the mathematical models of the system's algorithms are carried out in the Prototype Verification System (PVS). The animation tool PVSio is used to evaluate the formal models on a set of randomly generated test cases. Output values computed by PVSio are compared against output values computed by the actual software. This comparison improves the assurance that the translation from formal models to code is faithful and that, for example, floating point errors do not greatly affect correctness and safety properties.

Dutle, Aaron M.↗

NASA NTRS2015

Kodiak: An Implementation Framework for Branch and Bound Algorithms

Recursive branch and bound algorithms are often used to refine and isolate solutions to several classes of global optimization problems. A rigorous computation framework for the solution of systems of equations and inequalities involving nonlinear real arithmetic over hyper-rectangular variable and parameter domains is presented. It is derived from a generic branch and bound algorithm that has been formally verified, and utilizes self-validating enclosure methods, namely interval arithmetic and, for polynomials and rational functions, Bernstein expansion. Since bounds computed by these enclosure methods are sound, this approach may be used reliably in software verification tools. Advantage is taken of the partial derivatives of the constraint functions involved in the system, firstly to reduce the branching factor by the use of bisection heuristics and secondly to permit the computation of bifurcation sets for systems of ordinary differential equations. The associated software development, Kodiak, is presented, along with examples of three different branch and bound problem types it implements.

Smith, Andrew P.↗

NASA NTRS2015

Characterizing the Effects of a Vertical Time Threshold for a Class of Well-Clear Definitions

A fundamental requirement for the integration of unmanned aircraft into civil airspace is the capability of aircraft to remain well clear of each other and avoid collisions. This requirement has led to a broad recognition of the need for an unambiguous, formal definition of well clear. It is further recognized that any such definition must be interoperable with existing airborne collision avoidance systems (ACAS). A particular class of well-clear definitions uses logic checks of independent distance thresholds as well as independent time thresholds in the vertical and horizontal dimensions to determine if a well-clear violation is predicted to occur within a given time interval. Existing ACAS systems also use independent distance thresholds, however a common time threshold is used for the vertical and horizontal logic checks. The main contribution of this paper is the characterization of the effects of the decoupled vertical time threshold on a well-clear definition in terms of (1) time to well-clear violation, and (2) interoperability with existing ACAS. The paper provides governing equations for both metrics and includes simulation results to illustrate the relationships. In this paper, interoperability implies that the time of well-clear violation is strictly less than the time a resolution advisory is issued by ACAS. The encounter geometries under consideration in this paper are initially well clear and consist of constant-velocity trajectories resulting in near-mid-air collisions.

Upchurch, Jason M.↗

NASA NTRS2014

A Formally-Verified Decision Procedure for Univariate Polynomial Computation Based on Sturm's Theorem

Sturm's Theorem is a well-known result in real algebraic geometry that provides a function that computes the number of roots of a univariate polynomial in a semiopen interval. This paper presents a formalization of this theorem in the PVS theorem prover, as well as a decision procedure that checks whether a polynomial is always positive, nonnegative, nonzero, negative, or nonpositive on any input interval. The soundness and completeness of the decision procedure is proven in PVS. The procedure and its correctness properties enable the implementation of a PVS strategy for automatically proving existential and universal univariate polynomial inequalities. Since the decision procedure is formally verified in PVS, the soundness of the strategy depends solely on the internal logic of PVS rather than on an external oracle. The procedure itself uses a combination of Sturm's Theorem, an interval bisection procedure, and the fact that a polynomial with exactly one root in a bounded interval is always nonnegative on that interval if and only if it is nonnegative at both endpoints.

Narkawicz, Anthony J.↗

NASA NTRS2014

An Independent and Coordinated Criterion for Kinematic Aircraft Maneuvers

This paper proposes a mathematical definition of an aircraft-separation criterion for kinematic-based horizontal maneuvers. It has been formally proved that kinematic maneu- vers that satisfy the new criterion are independent and coordinated for repulsiveness, i.e., the distance at closest point of approach increases whether one or both aircraft maneuver according to the criterion. The proposed criterion is currently used in NASA's Airborne Coordinated Resolution and Detection (ACCoRD) set of tools for the design and analysis of separation assurance systems.

Narkawicz, Anthony J.↗

NASA NTRS2014

Analysis of Well-Clear Boundary Models for the Integration of UAS in the NAS

The FAA-sponsored Sense and Avoid Workshop for Unmanned Aircraft Systems (UAS) defnes the concept of sense and avoid for remote pilots as "the capability of a UAS to remain well clear from and avoid collisions with other airborne traffic." Hence, a rigorous definition of well clear is fundamental to any separation assurance concept for the integration of UAS into civil airspace. This paper presents a family of well-clear boundary models based on the TCAS II Resolution Advisory logic. Analytical techniques are used to study the properties and relationships satisfied by the models. Some of these properties are numerically quantifed using statistical methods.

Upchurch, Jason M.↗

NASA NTRS2014

A Well-Clear Volume Based on Time to Entry Point

A well-clear volume is a key component of NASA's Separation Assurance concept for the integration of UAS in the NAS. This paper proposes a mathematical definition of the well-clear volume that uses, in addition to distance thresholds, a time threshold based on time to entry point (TEP). The mathematical model that results from this definition is more conservative than other candidate definitions of the wellclear volume that are based on range over closure rate and time to closest point of approach.

Narkawicz, Anthony J.↗

NASA NTRS2011

Uncertainty Analysis via Failure Domain Characterization: Polynomial Requirement Functions

This paper proposes an uncertainty analysis framework based on the characterization of the uncertain parameter space. This characterization enables the identification of worst-case uncertainty combinations and the approximation of the failure and safe domains with a high level of accuracy. Because these approximations are comprised of subsets of readily computable probability, they enable the calculation of arbitrarily tight upper and lower bounds to the failure probability. A Bernstein expansion approach is used to size hyper-rectangular subsets while a sum of squares programming approach is used to size quasi-ellipsoidal subsets. These methods are applicable to requirement functions whose functional dependency on the uncertainty is a known polynomial. Some of the most prominent features of the methodology are the substantial desensitization of the calculations from the uncertainty model assumed (i.e., the probability distribution describing the uncertainty) as well as the accommodation for changes in such a model with a practically insignificant amount of computational effort.

Crespo, Luis G.↗

NASA NTRS2011

Formalizing Probabilistic Safety Claims

A safety claim for a system is a statement that the system, which is subject to hazardous conditions, satisfies a given set of properties. Following work by John Rushby and Bev Littlewood, this paper presents a mathematical framework that can be used to state and formally prove probabilistic safety claims. It also enables hazardous conditions, their uncertainties, and their interactions to be integrated into the safety claim. This framework provides a formal description of the probabilistic composition of an arbitrary number of hazardous conditions and their effects on system behavior. An example is given of a probabilistic safety claim for a conflict detection algorithm for aircraft in a 2D airspace. The motivation for developing this mathematical framework is that it can be used in an automated theorem prover to formally verify safety claims.

Herencia-Zapana, Heber↗

NASA NTRS2011

State-Based Implicit Coordination and Applications

In air traffic management, pairwise coordination is the ability to achieve separation requirements when conflicting aircraft simultaneously maneuver to solve a conflict. Resolution algorithms are implicitly coordinated if they provide coordinated resolution maneuvers to conflicting aircraft when only surveillance data, e.g., position and velocity vectors, is periodically broadcast by the aircraft. This paper proposes an abstract framework for reasoning about state-based implicit coordination. The framework consists of a formalized mathematical development that enables and simplifies the design and verification of implicitly coordinated state-based resolution algorithms. The use of the framework is illustrated with several examples of algorithms and formal proofs of their coordination properties. The work presented here supports the safety case for a distributed self-separation air traffic management concept where different aircraft may use different conflict resolution algorithms and be assured that separation will be maintained.

Narkawicz, Anthony J.↗

NASA NTRS2010

Time of Closest Approach in Three-Dimensional Airspace

In air traffic management, the aircraft separation requirement is defined by a minimum horizontal distance and a minimum vertical distance that the aircraft have to maintain. Since this requirement defines a cylinder around each aircraft rather than a sphere, the three-dimensional Euclidean distance does not provide an appropriate basis for the definition of time of closest approach. For instance, conflicting aircraft are not necessarily in loss of separation at the time of closest three-dimensional Euclidean distance. This paper proposes a definition of time of closest approach that characterizes conflicts in a three-dimensional airspace. The proposed time is defined as the time that minimizes a distance metric called cylindrical norm. An algorithm that computes the time of closest approach between two aircraft is provided and the formal verification of its main properties is reported.

Munoz, Cesar A.↗

NASA NTRS2010

Formal Verification of Air Traffic Conflict Prevention Bands Algorithms

In air traffic management, a pairwise conflict is a predicted loss of separation between two aircraft, referred to as the ownship and the intruder. A conflict prevention bands system computes ranges of maneuvers for the ownship that characterize regions in the airspace that are either conflict-free or 'don't go' zones that the ownship has to avoid. Conflict prevention bands are surprisingly difficult to define and analyze. Errors in the calculation of prevention bands may result in incorrect separation assurance information being displayed to pilots or air traffic controllers. This paper presents provably correct 3-dimensional prevention bands algorithms for ranges of track angle; ground speed, and vertical speed maneuvers. The algorithms have been mechanically verified in the Prototype Verification System (PVS). The verification presented in this paper extends in a non-trivial way that of previously published 2-dimensional algorithms.

Narkawicz, Anthony J.↗