On Expected Value Strong Controllability

Frank, Jeremy D.

Home/Archive/NASA NTRS

NASA NTRS · 20190027408

On Expected Value Strong Controllability

Frank, Jeremy D.

View original source ↗Export metadata ↓

Abstract

The Probabilistic Simple Temporal Network (PSTN) generalizes Simple Temporal Networks with Uncertainty (STNUs) by introducing probability distributions over the timing of uncontrollable timepoints. PSTNs are controllable if there is a strategy to execute the controllable timepoints while bounding the risk of violating any constraint to a small value. If this risk bound can't be satisfied, PSTNs are not considered controllable. We introduce the Expected Value Probabilistic SimpleTemporal Network (EPSTN), which extends PSTNs by including a benefit to the satisfaction of temporal constraints. We study the problem of Expected Value Strong Controllability (EvSC) of EPSTNs, which seeks a schedule maximizing the expected value of satisfied constraints. We solve the EvSC problem by extending a previously developed linear program, combined with search over constraints to violate at execution time. We describe conditions under which the solution to this linear program is the maximum expected value schedule. We then show how to search for constraints to discard, using the linear program at the core of the search. While the general problem is shown to be exponential, we conclude by providing several methods to bound the complexity of search.

Explore related subjects

Planning Scheduling Uncertainty

Keep this discovery

Explore connections, maps & timelines

BibTeX RIS

Frank, Jeremy D.. 2019-07-11. On Expected Value Strong Controllability. https://ntrs.nasa.gov/citations/20190027408

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related reports

NASA NTRS2016

NASA Work Breakdown Structure (WBS) Handbook

The purpose of this document is to provide program/project teams necessary instruction and guidance in the best practices for Work Breakdown Structure (WBS) and WBS dictionary development and use for project implementation and management control. This handbook can be used for all types of NASA projects and work activities including research, development, construction, test and evaluation, and operations. The products of these work efforts may be hardware, software, data, or service elements (alone or in combination). The aim of this document is to assist project teams in the development of effective work breakdown structures that provide a framework of common reference for all project elements. The WBS and WBS dictionary are effective management processes for planning, organizing, and administering NASA programs and projects. The guidance contained in this document is applicable to both in-house, NASA-led effort and contracted effort. It assists management teams from both entities in fulfilling necessary responsibilities for successful accomplishment of project cost, schedule, and technical goals. Benefits resulting from the use of an effective WBS include, but are not limited to: providing a basis for assigned project responsibilities, providing a basis for project schedule and budget development, simplifying a project by dividing the total work scope into manageable units, and providing a common reference for all project communication.

Planning↗

NASA NTRSDate not supplied

Explaining Soft-Goal Conflicts through Constraint Relaxations

Recent work suggests to explain trade-offs between soft goals in terms of their conflicts, i. e., minimal unsolvable soft-goal subsets. But this does not explain the conflicts themselves: Why can a given set of soft-goals not be jointly achieved? Here we approach that question in terms of the underlying constraints on plans in the task at hand, namely resource availability and time windows. In this context, a natural form of explanation for a soft-goal conflict is a minimal constraint relaxation under which the conflict disappears (“if the deadline was 1 hour later, it would work”). We explore algorithms for computing such explanations. A baseline is to simply loop over all relaxed tasks and compute the conflicts for each separately. We improve over this by two algorithms that leverage information – conflicts, reachable states – across relaxed tasks. We show that these algorithms can exponentially outperform the baseline in theory, and we run experiments confirming that advantage in practice.

Planning↗

NASA NTRSDate not supplied

Integrating Planning, Diagnosis and Execution for Vehicle Systems Management

We describe a prototype Vehicle System Manager (VSM) for NASA’s Gateway, a human-capable spacecraft that will also be capable of autonomous operations. The VSM consists of an execution system, planner, and fault management system, integrated via an over-arching mission management compo- nent. We describe the VSM architecture and each of its com- ponents. We describe a series of use cases, centered on a spacecraft propulsive operation that can fail at different times, for different reasons, and how the VSM detects and responds to these failures. We show the VSM is capable of detecting faults and loss of capability, and subsequently replanning, in the presence of each failure scenario.

Planning↗