Due to their increasing use by civil and federal authorities and vast commercial and amateur applications, Unmanned Aerial Systems (UAS) will be introduced into the National Air Space (NAS); the question is only how this can be done safely. Today, NASA and the FAA are designing a new, (NextGen) automated air traffic control system for all aircraft, manned or unmanned. New algorithms and tools will need to be developed to enable computation of the complex questions inherent in designing such a system while proving adherence to rigorous safety standards. Researchers must develop the tools of formal analysis to be able to address the UAS in the NAS problem, reason about UAS integration during the design phase of NextGen, and tie this design to on-board capabilities to provide runtime System Health Management (SHM), ensuring the safety of people and property on the ground. This proposal takes a holistic view and integrates advances in the state of the art from three intertwined perspectives to address safe integration of unmanned systems into the national airspace: from on-board the vehicle, from the environment (NAS), and from the underlying theory enabling their formal analysis. There has been rapid development of new UAS technologies yet few of them are formally mathematically rigorous to the degree needed for FAA safety-critical system certification. This project bridges that gap, integrating new UAS and air traffic control designs with advances in formal analysis. Within the wealth of promising directions for autonomous UAS capabilities, this project fills a unique need, providing a direct synergy between on-board UAS SHM, the NAS environment in which they must operate, and the theoretical foundations common to both of these. This research will help to build a safer NAS with increased capacity for UAS and create broadly impactful capabilities for SHM on-board UAS. Advancements will require theoretical research into more scalable model checking and debugging of safety properties. Safety properties express the sentiment that "something bad does not happen" during any system execution; they represent the vast majority of the requirements for NextGen designs and all requirements researchers can monitor on-board a UAS for system heath management during runtime. This research will tackle new frontiers in embedding health management capabilities on-board UAS. Collaborations with aerospace system designers at the National Aeronautics and Space Administration and tool designers at the Bruno Kessler Foundation will aid real-life utility and technology transfer. Broader impact will be achieved by involving undergraduate students in the design of an open-source, affordable, all-COTS and 3D-printable UAS, which will facilitate flight testing of this project's research advances. An open-UAS design for academia will be useful both for classroom demonstrations and as a research platform. Further impact will be achieved by using this UAS and the research it enables in interactive teaching experiences for K-12, undergraduate, and graduate students and in mentoring outreach specifically targeted at girls achieving in Science, Technology, Engineering and Mathematics (STEM) subjects.