Search

Partially Observable Markov Decision Processes (POMDPs) are powerful models for sequential decision making under transition and observation uncertainties. This paper studies the challenging yet important problem in POMDPs known as the (indefinite-horizon) Maximal Reachability Probability Problem (MRPP), where the goal is to maximize the probability of reaching some target states. This is also a core problem in model checking with logical specifications and is naturally undiscounted (discount factor is one). Inspired by the success of point-based methods developed for discounted problems, we study their extensions to MRPP. Specifically, we focus on trial-based heuristic search value iteration techniques and present a novel algorithm that leverages the strengths of these techniques for efficient exploration of the belief space (informed search via value bounds) while addressing their drawbacks in handling loops for indefinite-horizon problems. The algorithm produces policies with two-sided bounds on optimal reachability probabilities. We prove convergence to an optimal policy from below under certain conditions. Experimental evaluations on a suite of benchmarks show that our algorithm outperforms existing methods in almost all cases in both probability guarantees and computation time., Comment: Accepted to the Conference on Uncertainty in Artificial Intelligence (UAI) 2024

Robotic space missions have long depended on automation, defined in the 2015 NASA Technology Roadmaps as "the automatically-controlled operation of an apparatus, process, or system using a pre-planned set of instructions (e.g., a command sequence)," to react to events when a rapid response is required. Autonomy, defined there as "the capacity of a system to achieve goals while operating independently from external control," is required when a wide variation in circumstances precludes responses being pre-planned, instead autonomy follows an on-board deliberative process to determine the situation, decide the response, and manage its execution. Autonomy is increasingly called for to support adventurous space mission concepts, as an enabling capability or as a significant enhancer of the science value that those missions can return. But if autonomy is to be allowed to control these missions' expensive assets, all parties in the lifetime of a mission, from proposers through ground control, must have high confidence that autonomy will perform as intended to keep the asset safe to (if possible) accomplish the mission objectives. The role of mission assurance is a key contributor to providing this confidence, yet assurance practices honed over decades of spaceflight have relatively little experience with autonomy. To remedy this situation, researchers in JPL's software assurance group have been involved in the development of techniques specific to the assurance of autonomy. This paper summarizes over two decades of this research, and offers a vision of where further work is needed to address open issues., Comment: 9 pages, 0 figures. To be published in The 2nd International Conference on Assured Autonomy

Many sequential decision problems involve optimizing one objective function while imposing constraints on other objectives. Constrained Partially Observable Markov Decision Processes (C-POMDP) model this case with transition uncertainty and partial observability. In this work, we first show that C-POMDPs violate the optimal substructure property over successive decision steps and thus may exhibit behaviors that are undesirable for some (e.g., safety critical) applications. Additionally, online re-planning in C-POMDPs is often ineffective due to the inconsistency resulting from this violation. To address these drawbacks, we introduce the Recursively-Constrained POMDP (RC-POMDP), which imposes additional history-dependent cost constraints on the C-POMDP. We show that, unlike C-POMDPs, RC-POMDPs always have deterministic optimal policies and that optimal policies obey Bellman's principle of optimality. We also present a point-based dynamic programming algorithm for RC-POMDPs. Evaluations on benchmark problems demonstrate the efficacy of our algorithm and show that policies for RC-POMDPs produce more desirable behaviors than policies for C-POMDPs., Comment: Accepted to the Conference on Uncertainty in Artificial Intelligence (UAI) 2024

Technology Readiness Levels are a mainstay for organizations that fund, develop, test, acquire, or use technologies. Technology Readiness Levels provide a standardized assessment of a technology's maturity and enable consistent comparison among technologies. They inform decisions throughout a technology's development life cycle, from concept, through development, to use. A variety of alternative Readiness Levels have been developed, including Algorithm Readiness Levels, Manufacturing Readiness Levels, Human Readiness Levels, Commercialization Readiness Levels, Machine Learning Readiness Levels, and Technology Commitment Levels. However, while Technology Readiness Levels have been increasingly applied to emerging disciplines, there are unique challenges to assessing the rapidly developing capabilities of autonomy. This paper adopts the moniker of Space Trusted Autonomy Readiness Levels to identify a two-dimensional scale of readiness and trust appropriate for the special challenges of assessing autonomy technologies that seek space use. It draws inspiration from other readiness levels' definitions, and from the rich field of trust and trustworthiness. The Space Trusted Autonomy Readiness Levels were developed by a collaborative Space Trusted Autonomy subgroup, which was created from The Space Science and Technology Partnership Forum between the United States Space Force, the National Aeronautics and Space Administration, and the National Reconnaissance Office.

A close partnership between people and partially autonomous machines has enabled decades of space exploration. But to further expand our horizons, our systems must become more capable. Increasing the nature and degree of autonomy - allowing our systems to make and act on their own decisions as directed by mission teams - enables new science capabilities and enhances science return. The 2011 Planetary Science Decadal Survey (PSDS) and on-going pre-Decadal mission studies have identified increased autonomy as a core technology required for future missions. However, even as scientific discovery has necessitated the development of autonomous systems and past flight demonstrations have been successful, institutional barriers have limited its maturation and infusion on existing planetary missions. Consequently, the authors and endorsers of this paper recommend that new programmatic pathways be developed to infuse autonomy, infrastructure for support autonomous systems be invested in, new practices be adopted, and the cost-saving value of autonomy for operations be studied., Comment: 10 pages (compared to 8 submitted to PSADS), 2 figures, submitted to National Academy of Sciences Planetary Science and Astrobiology Decadal Survey 2023-2032

A close partnership between people and partially autonomous machines has enabled decades of space exploration. But to further expand our horizons, our systems must become more capable. Increasing the nature and degree of autonomy - allowing our systems to make and act on their own decisions as directed by mission teams - enables new science capabilities and enhances science return. The 2011 Planetary Science Decadal Survey (PSDS) and on-going pre-Decadal mission studies have identified increased autonomy as a core technology required for future missions. However, even as scientific discovery has necessitated the development of autonomous systems and past flight demonstrations have been successful, institutional barriers have limited its maturation and infusion on existing planetary missions. Consequently, the authors and endorsers of this paper recommend that new programmatic pathways be developed to infuse autonomy, infrastructure for support autonomous systems be invested in, new practices be adopted, and the cost-saving value of autonomy for operations be studied., Comment: 10 pages (compared to 8 submitted to PSADS), 2 figures, submitted to National Academy of Sciences Planetary Science and Astrobiology Decadal Survey 2023-2032

Verifying diagnostic procedures for complex systems is hard and labor-intensive. Usually this verification is accomplished primarily through extensive review of the procedures by experts. We aim to augment this review process by using insights from comparing the diagnostic steps described in the procedural definitions with diagnostics information derived from existing models of the system. These comparisons offer various conformance checks between the manually developed diagnostic procedures and the diagnostic trees autogenerated from the diagnostic system models. We previously described our DTV (Diagnostic Tree for Verification) technique based on these comparisons. This paper describes an extension to DTV, and reports results of an application of DTV to a representative system's diagnostic procedures. Specifically, it outlines four analyses (branch analysis, root cause coverage, path verification, and efficiency) that can be performed using DTV; illustrates the process for applying DTV; and reports results from our application of DTV to assure fifteen of the procedures developed for diagnosing problems in an electrical power system testbed for spacecraft., See also ADA548241. Presented at the Annual Conference of the Prognostics and Health Management Society (PHM 2010) Held in Portland, Oregon on October 10-14, 2010. U.S. Government or Federal Purpose Rights License., The original document contains color images. Prepared in cooperation with Jet Propulsion Lab., CA.

A vision is presented for fusing quantitative requirements analysis with model-based systems engineering. This vision draws upon and combines emergent themes in the engineering milieu. “Requirements engineering” provides means to explicitly represent requirements (both functional and non-functional) as constraints and preferences on acceptable solutions, and emphasizes early-lifecycle review, analysis and verification of design and development plans. “Design by shopping” emphasizes revealing the space of options available from which to choose (without presuming that all selection criteria have previously been elicited), and provides means to make understandable the range of choices and their ramifications. “Model-based engineering” emphasizes the goal of utilizing a formal representation of all aspects of system design, from development through operations, and provides powerful tool suites that support the practical application of these principles. A first step prototype towards this vision is described, embodying the key capabilities. Illustrations, implications, further challenges and opportunities are outlined.

This paper considers the problem of system deviations from requirements specifications. Such deviations may arise from lack of anticipation of possible behaviors of environment agents at specification time, or from evoking conditions in this environment. We discuss an architecture and a development process for monitoring system requirements at runtime to reconcile the requirements and the system's behavior. This process is deployed on three scenarios of requirements-execution reconciliation for the Meeting Scheduler system. The work builds on our previous work on goal-driven requirements engineering and on runtime requirements monitoring

Specification exemplars are familiar to most software engineering researchers. For instance, many will have encountered the well known library and lift problem statements, and will have seen one or more published specifications. Exemplars may serve several purposes: to drive and communicate individual research advances; to establish research agendas and to compare and contrast alternative approaches; and, ultimately, to lead to advances in software development practices. Because of their prevalence in the literature, exemplars are worth critical study. In this paper we consider the purposes that exemplars may serve, and explore the incompatibilities inherent in trying to serve several of them at once. Researchers should therefore be clear about what successfully handling an exemplar demonstrates. We go on to examine the use of exemplars not only for writing specifications (an end product of requirements engineering), but also for the requirements engineering process itself. In particular, requirements for good requirements exemplars are suggested and ways of obtaining such exemplars are discussed.

A series of workshops, of which this Seventh International Workshop on Software Specification and Design (IWSSD-7) is the latest instance, was begun in 1982. The first five of these workshops were held in conjunction with the International Conference on Software Engineering (ICSE). Specifically, the first workshop occurred in Kyoto following ICSE-6 (Tokyo, 1982), the second followed ICSE-7 (Orlando, 1984), the third followed ICSE-8 (London, 1985), the fourth followed ICSE-9 (Monterey, 1987) and the fifth followed ICSE-11 (Pittsburgh, 1989). The two most recent occurrences of the workshop have continued both the international character and the connection to major software engineering conferences that marked their predecessors. IWSSD-6, held in Como in 1991, followed the Third European Software Engineering Conference (Milan, 1991). This seventh IWSSD is being held in Redondo Beach, immediately preceding the 1993 SigSoft Symposium entitled "Foundations of Software Engineering." IWSSD-7, like its predecessors, is intended to provide a forum for exploring major trends and key issues in the specification and design of software. The format of the workshop will follow the model that has proven so successful in the previous meetings in this series: A fairly small number (approximately 80) of participants, selected on the basis of submitted papers, will spend most of the two day meeting discussing specific topics in one of five parallel working groups. Three plenary sessions will bring all the workshop participants together, once for an opening address (by Professor Tom Maibaum) and twice for presentation and discussion of the various working groups' deliberations.

This report describes a knowledge-based assistant for Acquisition of Requirements and Incremental Evolution of Specifications (ARIES). ARIES is a system developed by the University of Southern California Information Sciences Institute and Lockheed Sanders to address the needs of the Knowledge-Based Software Assistant (KBSA) for the early phases of a system life cycle. ARIES supports the evolutionary development of formal system specifications in a multi-presentational environment in which informal application requirements are captured and elaborated using representations familiar to users and applications engineers. ARIES, through the formalization of activities and creation of a knowledge base, enables extensive machine support for evaluation and reuse of system design artifacts. The concepts explored in this effort will be of interest to anyone interested in: (1) what lies ahead for computer aided software engineering; (2) identifying the key issues for automating the software development process; (3) the value of knowledge-based approaches to formal system development; and (4) the benefits of having a wide spectrum of representations available to the design process.

The process of converting formal specifications into valid implementations is central in the development of reliable software. As formal specification languages are enriched with constructs to enhance their expressive capabilities and as they increasingly afford specificational freedoms by requiring only a description of intended behavior rather than a prescription of particular algorithms, the gap between specification and implementation widens so that converting specifications into implementations becomes even more difficult. A major problem lies in the mapping of high-level specification constructs into an implementation that effects the desired behavior. In this report, we consider the issues involved in eliminating occurrences of high-level specification-oriented constructs during this process. We discuss mapping issues in the context of our development methodology, in which implementations are derived via the application of equivalence-preserving transformations to a specification language whose high-level expressive capabilities are modeled after natural language. After the general discussion, we demonstrate the techniques on a real system whose specification is written in this language. (Author)