Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “chance constraint optimization”

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.

Risk-Constrained Dynamic Programming for Optimal Mars Entry, Descent, and Landing

A chance-constrained dynamic programming algorithm was developed that is capable of making optimal sequential decisions within a user-specified risk bound. This work handles stochastic uncertainties over multiple stages in the CEMAT (Combined EDL-Mobility Analyses Tool) framework. It was demonstrated by a simulation of Mars entry, descent, and landing (EDL) using real landscape data obtained from the Mars Reconnaissance Orbiter. Although standard dynamic programming (DP) provides a general framework for optimal sequential decisionmaking under uncertainty, it typically achieves risk aversion by imposing an arbitrary penalty on failure states. Such a penalty-based approach cannot explicitly bound the probability of mission failure. A key idea behind the new approach is called risk allocation, which decomposes a joint chance constraint into a set of individual chance constraints and distributes risk over them. The joint chance constraint was reformulated into a constraint on an expectation over a sum of an indicator function, which can be incorporated into the cost function by dualizing the optimization problem. As a result, the chance-constraint optimization problem can be turned into an unconstrained optimization over a Lagrangian, which can be solved efficiently using a standard DP approach.

Ono, Masahiro↗

Chance-Constrained Guidance With Non-Convex Constraints

Missions to small bodies, such as comets or asteroids, require autonomous guidance for descent to these small bodies. Such guidance is made challenging by uncertainty in the position and velocity of the spacecraft, as well as the uncertainty in the gravitational field around the small body. In addition, the requirement to avoid collision with the asteroid represents a non-convex constraint that means finding the optimal guidance trajectory, in general, is intractable. In this innovation, a new approach is proposed for chance-constrained optimal guidance with non-convex constraints. Chance-constrained guidance takes into account uncertainty so that the probability of collision is below a specified threshold. In this approach, a new bounding method has been developed to obtain a set of decomposed chance constraints that is a sufficient condition of the original chance constraint. The decomposition of the chance constraint enables its efficient evaluation, as well as the application of the branch and bound method. Branch and bound enables non-convex problems to be solved efficiently to global optimality. Considering the problem of finite-horizon robust optimal control of dynamic systems under Gaussian-distributed stochastic uncertainty, with state and control constraints, a discrete-time, continuous-state linear dynamics model is assumed. Gaussian-distributed stochastic uncertainty is a more natural model for exogenous disturbances such as wind gusts and turbulence than the previously studied set-bounded models. However, with stochastic uncertainty, it is often impossible to guarantee that state constraints are satisfied, because there is typically a non-zero probability of having a disturbance that is large enough to push the state out of the feasible region. An effective framework to address robustness with stochastic uncertainty is optimization with chance constraints. These require that the probability of violating the state constraints (i.e., the probability of failure) is below a user-specified bound known as the risk bound. An example problem is to drive a car to a destination as fast as possible while limiting the probability of an accident to 10(exp -7). This framework allows users to trade conservatism against performance by choosing the risk bound. The more risk the user accepts, the better performance they can expect.

FROM↗

Robust Path Planning and Feedback Design Under Stochastic Uncertainty

Autonomous vehicles require optimal path planning algorithms to achieve mission goals while avoiding obstacles and being robust to uncertainties. The uncertainties arise from exogenous disturbances, modeling errors, and sensor noise, which can be characterized via stochastic models. Previous work defined a notion of robustness in a stochastic setting by using the concept of chance constraints. This requires that mission constraint violation can occur with a probability less than a prescribed value.In this paper we describe a novel method for optimal chance constrained path planning with feedback design. The approach optimizes both the reference trajectory to be followed and the feedback controller used to reject uncertainty. Our method extends recent results in constrained control synthesis based on convex optimization to solve control problems with nonconvex constraints. This extension is essential for path planning problems, which inherently have nonconvex obstacle avoidance constraints. Unlike previous approaches to chance constrained path planning, the new approach optimizes the feedback gain as wellas the reference trajectory.The key idea is to couple a fast, nonconvex solver that does not take into account uncertainty, with existing robust approaches that apply only to convex feasible regions. By alternating between robust and nonrobust solutions, the new algorithm guarantees convergence to a global optimum. We apply the new method to an unmanned aircraft and show simulation results that demonstrate the efficacy of the approach.

autonomuys vehicles↗

A Framework for the Optimization of Discrete-Event Simulation Models

With the growing use of computer modeling and simulation, in all aspects of engineering, the scope of traditional optimization has to be extended to include simulation models. Some unique aspects have to be addressed while optimizing via stochastic simulation models. The optimization procedure has to explicitly account for the randomness inherent in the stochastic measures predicted by the model. This paper outlines a general purpose framework for optimization of terminating discrete-event simulation models. The methodology combines a chance constraint approach for problem formulation, together with standard statistical estimation and analyses techniques. The applicability of the optimization framework is illustrated by minimizing the operation and support resources of a launch vehicle, through a simulation model.

Joshi, B. D.↗

Joint Chance-Constrained Dynamic Programming

This paper presents a novel dynamic programming algorithm with a joint chance constraint, which explicitly bounds the risk of failure in order to maintain the state within a specified feasible region. A joint chance constraint cannot be handled by existing constrained dynamic programming approaches since their application is limited to constraints in the same form as the cost function, that is, an expectation over a sum of one-stage costs. We overcome this challenge by reformulating the joint chance constraint into a constraint on an expectation over a sum of indicator functions, which can be incorporated into the cost function by dualizing the optimization problem. As a result, the primal variables can be optimized by a standard dynamic programming, while the dual variable is optimized by a root-finding algorithm that converges exponentially. Error bounds on the primal and dual objective values are rigorously derived. We demonstrate the algorithm on a path planning problem, as well as an optimal control problem for Mars entry, descent and landing. The simulations are conducted using a real terrain data of Mars, with four million discrete states at each time step.

Ono, Masahiro↗

Mixed-Strategy Chance Constrained Optimal Control

This paper presents a novel chance constrained optimal control (CCOC) algorithm that chooses a control action probabilistically. A CCOC problem is to find a control input that minimizes the expected cost while guaranteeing that the probability of violating a set of constraints is below a user-specified threshold. We show that a probabilistic control approach, which we refer to as a mixed control strategy, enables us to obtain a cost that is better than what deterministic control strategies can achieve when the CCOC problem is nonconvex. The resulting mixed-strategy CCOC problem turns out to be a convexification of the original nonconvex CCOC problem. Furthermore, we also show that a mixed control strategy only needs to "mix" up to two deterministic control actions in order to achieve optimality. Building upon an iterative dual optimization, the proposed algorithm quickly converges to the optimal mixed control strategy with a user-specified tolerance.

Ono, Masahiro↗

Team Formation and Communication Restrictions in Collectives

A collective of agents often needs to maximize a "world utility" function which rates the performance of an entire system, while subject to communication restrictions among the agents. Such communication restrictions make it difficult for agents which try to pursue their own "private" utilities to take actions that also help optimize the world utility. Team formation presents a solution to this problem, where by joining other agents, an agent can significantly increase its knowledge about the environment and improve its chances of both optimizing its own utility and that its doing so will contribute to the world utility. In this article we show how utilities that have been previously shown to be effective in collectives can be modified to be more effective in domains with moderate communication restrictions resulting in performance improvements of up to 75%. Additionally we show that even severe communication constraints can be overcome by forming teams where each agent of a team shares the same utility, increasing performance an additional 25%. We show that utilities and team sizes can be manipulated to form the best compromise between how "aligned" an agent s utility is with the world utility and how easily an agent can learn that utility.

Agogino, Adrian K.↗

SAMPEX science pointing with velocity avoidance

The Solar, Anomalous, and Magnetospheric Particle Explorer (SAMPEX) science pointing mode is presented with the additional constraint of velocity avoidance. This constraint has been added in light of the orbital debris and micrometeoroid fluxes that have been revealed by the Long Duration Exposure Facility (LDEF) recovered in January 1990. These fluxes are 50-100 times higher than the flux tables that were used in the September 1988 proposal to NASA for the SAMPEX mission. The SAMPEX Heavey Ion Large Telescope (HILT) sensor includes a flow-through isobutane proportional counter that is susceptible to penetration by orbital debris and micrometeoroids. Thus, keeping the HILT sensor pointed away from the velocity vector, the direction of maximum flux, will compensate for the higher than expected fluxes. Using an orbital debris model and a micrometeoroid model developed at the Johnson Space Center (JSC), and a SAMPEX dynamic simulator developed by the Guidance and Control Branch at the Goddard Space Flight Center (GSFC), an 'optimal' minimum ram angle (the angle between the HILT boresight and the velocity vector) of 90 degrees has been determined. It is optimal in the sense of minimizing the science pointing performance degradation while providing approximately an 89 percent chance of survival for the HILT sensor over a three year period.

Frakes, Joseph P.↗

Proposed Mars Surveyor Landing Sites in Northern Meridiani Sinus, Southern Elysium Planitia, and Argyre Planitia

Our objective is to propose two landing sites that the Mars Surveyor 2001 Lander and Athena Rover could go to on Mars that should meet the safety requirements of the spacecraft landing system and optimize surface operations (chiefly driven by power and communications requirements). An additional site within Argyre Planitia, initially proposed by Parker to the Mars Surveyor Landing Site program, is also proposed for potential consideration for post-2001 missions to Mars, as it is well outside the current latitude limits for the Athena Rover. All three sites are designed to be situated as close to a diversity of geologic units within a few kilometers of the landing site so that diversity can be placed in a geologic context. This objective is very different from the Mars Pathfinder requirement to land at a site with a maximum chance for containing a diversity of rocks within a few tens of meters of the lander. That requirement was driven by the Sojourner mobility limit of a few tens of meters. It can be argued that the Athena project, with its much larger mobility capability, might actually want to avoid such a site, because placing collected samples in geologic context would be difficult. While it has been argued, both before and after the Mars Pathfinder landing, that the provenance for local blocks may be determined by orbiter spectra, primarily from the MGS TES instrument, our ability to do so has yet to be demonstrated. Indeed, several months after conclusion of the Pathfinder mission, we have yet to reach a consensus on the composition of local materials. Our primary data set for selecting a landing site within the latitude and elevation constraints of the 2001 mission is the Viking Orbiter image archive. The site must be selected to place the landing ellipse so as to avoid obvious hazards, such as steep slopes, large or numerous craters, or abundant large knobs. For this purpose, we chose a resolution limit of better than 50 m/pixel. This necessarily excludes from the present study images from current and future orbiter spacecraft, until such data does become readily available. Within each proposed region, it may be possible to identify additional sites once these data become available. Second, the fine-component thermal inertia data, should be greater than about 5 or 6 cgs Units (10(exp -3) cal/sq cm s(exp -0.5)/K). Low thermal inertias imply dusty environments, which could pose a mobility hazard. Similarly, the albedo of the site should not be particularly high, which would also suggest dusty surfaces. Low albedos are preferred, as they often coincide with low Viking red:violet ratios and indicate less dusty surfaces. Next, the Modeled Block Abundance should also not be too high or too low. Based on the Viking Lander and Mars Pathfinder experiences, percentages of blocks should be on the order of 5-25%. Too many blocks could pose a hazard to the landing and mobility. Too few blocks could also indicate a dusty surface. Primary Landing Site: Northern Meridiani Sinus (Proposed by T. J. Parker and K., S. Edgett) Vital Statistics: (1) Latitude, Longitude: 0-3 N, 350-2 W. *Elevation (Viking): about0.5-1.5 Ian. (2) Viking Orbiter Image coverage: Excellent coverage by 15 - 25 m/pixel images (orbits 709A and 410B). Possible stereo coverage in region where two orbits overlap (probably small parallax angle, as these orbits are not listed in NASA Contractor Report 3501) (3) Albedo: about .18 -.26 (4) Block Abundance: 5-26% (5)Fine-Component Thermal Inertia: 5-9 cgs units This region consists of bright deposits similar to those described by Edgett et al, that also lie within a prominent dark albedo region. These deposits are flat-lying, to such a degree that they ramp against topography rather than draping over it. This led Edgett and Parker to suggest that they may be subaqueous sediments, possibly lacustrine or marine evaporites, laid down sometime from the late Noachian to middle Hesperian (age determination pending crater counts). A contact between this material and elevated, dissected highlands to the south was identified , and is described by Edgett et al. Our desire in proposing this landing site is to sample the edge of this deposit where it has been exposed through etching, presumably eolian deflation (the deposit, though in the highlands, is itself only lightly to moderately cratered). This should enable access to in situ stratigraphy. The actual landing site will be selected where slopes are not expected to be steep, such that the rover itself should be able to traverse them and sample layered materials on the way, either up or down the slope. Perhaps due to uncertainties at this time as to the friability or meter-scale roughness of the deposit, it might make sense to place the landing ellipse on the exhumed highland surface adjacent to the deflated margin of the deposit and plan on driving to the deposit rather than landing on it and driving downslope. This should also enable imaging the margin for evidence of layering should it prove too difficult to climb. A target ellipse on the highland surface should also allow Athena access to ancient Noachian highland materials, particularly if placed near crater ejecta or an inlier of knobby material. Secondary Landing Site: Southern Elysium Planitia (Proposed by T. J. Parker) Vital Statistics: (1) Latitude, Longitude: 1.5-3.5 S, 195-198 W. (2) Elevation (Viking): -1.0 km. (3) Viking Orbiter Image coverage: Excellent coverage by 15 - 25 m/pixel images (orbit 725). Possible stereo coverage between images from beginning and end of orbit that overlap (probably small parallax angle) (4) Albedo: about .27-.28 (5) Block Abundance: 4-7% (6) Fine-Component Thermal Inertia: about 3 cgs units This region consists of eroded knobby material, probably of Noachian age, though much of the crater population has been destroyed, that is onlapped at a sharp contact by an extensive plains unit in southern Elysium Planitia that is Amazonian in age. The plains materials have been attributed to unusually low-viscosity flood lavas from fissures south of the Elysium volcanic rise, or to lacustrine materials associated with a large, Amazonian lake at the source of Marte Vallis. Parker and Schenk presented evidence in support of the latter interpretation, though they attributed the putative shore morphology to an embayment of a northern plains ocean into the southern Elysium region. Detailed examination of the margin of the deposit, showing erosion, not simply burial, of small crater rims and fluidized ejecta blankets, also points to lacustrine or marine sedimentation rather than volcanic plains burial. The plains surface exhibits a "crusty" appearance that many researchers have attributed to pressure ridges in lava flows. In a lacustrine context, they also resemble pressure ridges in desiccated evaporite deposits and salt-rimmed pools (now dry) similar in scale and morphology to spectacular, hundred meter-scale pool rims in alkaline Lake Natron, East African Rift. The eroded highland margin surface adjacent to these plains appears to be fairly smooth, even at 15 m/pixel. Isolated knob inliers are scattered from a few kilometers to several tens of "kilometers apart. Heights of the knobs have not been measured yet but, based on experience with similar features in the Pathfinder landing ellipse, are probably typically on the order of several tens of meters high and smaller, though some of the largest knobs in the region are probably up to a few hundred meters high. Two craters larger than a kilometer in diameter, with fluidized deposits, lie nearby the proposed landing site. Very high-resolution images from MOC should help to determine whether a landing site navigable by the Athena rover could be placed in this region. The space between knobs and craters is large enough to enable placement of a target landing ellipse between them but still provide access to one or more of them and to the margin of the Elysium plains material. Post-2001 Mars Surveyor Landing Site: Argyre Planitia (Proposed by T. J. Parker) Vital Statistics: (1) Latitude, Longitude: 55-56 S, 41-43 W. (2) Elevation (Viking): 1.0 km. (3) Viking Orbiter Image coverage: Excellent coverage by 40 m/pixel images (orbits 567B, 568B, and 569B). Excellent stereo coverage with large parallax angles over the entire landing site region, and much of central and southern Argyre. (4) Albedo: about .23-.24 (5) Block Abundance: No data (6) Fine-Component Thermal Inertia: No data The floors of both the Argyre and Hellas basins contain etched layered materials that are probably thick accumulations of channel or lacustrine sediments. The deposits in Hellas are much more eroded than those in Argyre, and Hellas lacks a channel outlet. Argyre is unique in that Uzboi Vallis flowed out of the basin, requiring overflow of a standing body of water within Argyre. This makes it the largest impact basin on Mars with channels both draining into it and flowing out from it. Hellas' channels may be catastrophic flood channels, whereas Argyre was fed by modest-scale valley networks, though the outlet at Uzboi Vallis was a catastrophic flood Highland craters and basins of this kind should be high-priority landing targets for missions intended to focus on the search for either prebiotic organic materials or even simple fossil microorganisms. Basins with internally-draining valley networks should be preferred over flood channels, as they could have provided the long-term influx of water favorable to the origin of life. (Catastrophic floods are not conducive to fossil preservation, due to their very short durations and high transportation energies). They also afford an opportunity to study the evolution of the planet's climate and volatiles during the period of time between the late Noachian and early Hesperian, when a drastic change from a proposed early warm, wet climate to one more closely resembling the modern environment is thought to have occurred. Large basin

Parker, T. J.↗