CINXE.COM

<!DOCTYPE html>     <html class="no-js" lang="en">  <head><META http-equiv="Content-Type" content="text/html; charset=UTF-8"> <meta content="text/html; charset=UTF-8" http-equiv="Content-Type"> <meta content="IE=edge,chrome=1" http-equiv="X-UA-Compatible"> <meta content="width=device-width,initial-scale=1" name="viewport"> <link rel="shortcut icon" href="https://cdn.libraries.mit.edu/files/branding/favicons/favicon.ico"> <link rel="apple-touch-icon" href="https://cdn.libraries.mit.edu/files/branding/favicons/apple-touch-icon.png"> <meta name="Generator" content="DSpace 6.3"> <link type="text/css" rel="stylesheet" media="screen" href="/themes/Mirage2/../../themes/ReportingSuite/lib/statistics-style.css"> <link type="text/css" rel="stylesheet" media="screen" href="/themes/Mirage2/../../themes/ReportingSuite/lib/statistics-style-ie.css"> <link href="/themes/Mirage2/styles/main.css" rel="stylesheet"> <link type="application/opensearchdescription+xml" rel="search" href="https://dspace.mit.edu:443/open-search/description.xml" title="DSpace"> <script> //Clear default text of empty text areas on focus function tFocus(element) { if (element.value == ''){element.value='';} } //Clear default text of empty text areas on submit function tSubmit(form) { var defaultedElements = document.getElementsByTagName("textarea"); for (var i=0; i != defaultedElements.length; i++){ if (defaultedElements[i].value == ''){ defaultedElements[i].value='';}} } //Disable pressing 'enter' key to submit a form (otherwise pressing 'enter' causes a submission to start over) function disableEnterKey(e) { var key; if(window.event) key = window.event.keyCode; //Internet Explorer else key = e.which; //Firefox and Netscape if(key == 13) //if "Enter" pressed, then disable! return false; else return true; } </script><script src="/themes/Mirage2/vendor/modernizr/modernizr.min.js"> </script> <title>Chance Constrained Finite Horizon Optimal Control</title> <link rel="schema.DCTERMS" href="http://purl.org/dc/terms/" /> <link rel="schema.DC" href="http://purl.org/dc/elements/1.1/" /> <meta name="DC.creator" content="Ono, Masahiro" /> <meta name="DC.creator" content="Williams, Brian Charles" /> <meta name="DC.creator" content="Blackmore, Lars" /> <meta name="DCTERMS.dateAccepted" content="2011-12-08T17:40:01Z" scheme="DCTERMS.W3CDTF" /> <meta name="DCTERMS.available" content="2011-12-08T17:40:01Z" scheme="DCTERMS.W3CDTF" /> <meta name="DCTERMS.issued" content="2010-07" scheme="DCTERMS.W3CDTF" /> <meta name="DC.identifier" content="978-1-4244-7426-4" /> <meta name="DC.identifier" content="0743-1619" /> <meta name="DC.identifier" content="http://hdl.handle.net/1721.1/67480" scheme="DCTERMS.URI" /> <meta name="DCTERMS.abstract" content="This paper considers finite-horizon optimal control for dynamic systems subject to additive Gaussian-distributed stochastic disturbance and a chance constraint on the system state defined on a non-convex feasible space. The chance constraint requires that the probability of constraint violation is below a user-specified risk bound. A great deal of recent work has studied joint chance constraints, which are defined on the a conjunction of linear state constraints. These constraints can handle convex feasible regions, but do not extend readily to problems with non-convex state spaces, such as path planning with obstacles. In this paper we extend our prior work on chance constrained control in non-convex feasible regions to develop a new algorithm that solves the chance constrained control problem with very little conservatism compared to prior approaches. In order to address the non-convex chance constrained optimization problem, we present two innovative ideas in this paper. First, we develop a new bounding method 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. However, the slow computation of the branch and bound algorithm prevents practical applications. This issue is addressed by our second innovation called Fixed Risk Relaxation (FRR), which efficiently gives a tight lower bound to the convex chance-constrained optimization problem. Our empirical results show that the FRR typically makes branch and bound algorithm 10-20 times faster. In addition we show that the new algorithm is significantly less conservative than the existing approach." xml:lang="en_US" /> <meta name="DC.description" content="Boeing Company (Grant MIT-BA-GTA-1)" xml:lang="en_US" /> <meta name="DC.description" content="United States. National Aeronautics and Space Administration" xml:lang="en_US" /> <meta name="DC.language" content="en_US" scheme="DCTERMS.RFC1766" /> <meta name="DC.publisher" content="American Automatic Control Council" xml:lang="en_US" /> <meta name="DC.rights" content="Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use." xml:lang="en_US" /> <meta name="DC.source" content="IEEE" xml:lang="en_US" /> <meta name="DC.title" content="Chance Constrained Finite Horizon Optimal Control" xml:lang="en_US" /> <meta name="DC.type" content="Article" xml:lang="en_US" /> <meta name="DCTERMS.bibliographicCitation" content="Ono, M., L. Blackmore, and B.C. Williams. “Chance constrained finite horizon optimal control with nonconvex constraints.” Proceedings of the American Control Conference (ACC), Marriott Waterfront, Baltimore, MD, USA June 30-July 02, 2010. 1145-1152.© 2010 American Automatic Control Council." xml:lang="en_US" /> <meta name="DC.contributor" content="Massachusetts Institute of Technology. Department of Aeronautics and Astronautics" xml:lang="en_US" /> <meta name="DC.contributor" content="Williams, Brian Charles" /> <meta name="DC.contributor" content="Ono, Masahiro" /> <meta name="DC.contributor" content="Williams, Brian Charles" /> <meta name="DC.relation" content="American Control Conference, 2010. ACC '10." xml:lang="en_US" /> <meta name="DC.type" content="http://purl.org/eprint/type/ConferencePaper" xml:lang="en_US" /> <meta name="DC.identifier" content="https://orcid.org/0000-0002-1057-3940" /> <meta content="Article" name="citation_keywords"> <meta content="978-1-4244-7426-4" name="citation_isbn"> <meta content="Chance Constrained Finite Horizon Optimal Control" name="citation_title"> <meta content="0743-1619" name="citation_issn"> <meta content="American Automatic Control Council" name="citation_publisher"> <meta content="en_US" name="citation_language"> <meta content="Ono, Masahiro" name="citation_author"> <meta content="Blackmore, Lars" name="citation_author"> <meta content="Williams, Brian C." name="citation_author"> <meta content="https://dspace.mit.edu/bitstream/1721.1/67480/2/Williams-2010-Chance%20Constrained%20Finite%20Horizon%20Optimal%20Control.pdf" name="citation_pdf_url"> <meta content="2010-07" name="citation_date"> <meta content="https://dspace.mit.edu/handle/1721.1/67480" name="citation_abstract_html_url"> </head><body> <div class="wrap-outer-header layout-band"> <div class="wrap-header"> <header role="banner" class="header-site header-slim"> <div class="wrap-header-core"> <h1 class="name-site group nav-logo"> <a href="https://libraries.mit.edu/" class="logo-mit-lib"><img height="35" alt="MIT Libraries logo" src="https://cdn.libraries.mit.edu/files/branding/local/mitlib-wordmark.svg"></a><a href="/" class="platform-name">DSpace@MIT</a> </h1> </div> <div class="wrap-header-supp"> <a href="https://www.mit.edu" class="link-logo-mit"><img height="35" alt="MIT" src="https://cdn.libraries.mit.edu/files/branding/local/mit_logo_std_rgb_white.svg"></a> </div> </header> </div> </div> <div class="trail-wrapper hidden-print"> <div> <div> <div> <div class="breadcrumb dropdown visible-xs"> <a data-toggle="dropdown" class="dropdown-toggle" role="button" href="#" id="trail-dropdown-toggle">View Item <b class="caret"></b></a> <ul aria-labelledby="trail-dropdown-toggle" role="menu" class="dropdown-menu"> <li role="presentation"> <a role="menuitem" href="/">DSpace@MIT Home</a> </li> <li role="presentation"> <a role="menuitem" href="/handle/1721.1/49432">MIT Open Access Articles</a> </li> <li role="presentation"> <a role="menuitem" href="/handle/1721.1/49433">MIT Open Access Articles</a> </li> <li role="presentation" class="disabled"> <a href="#" role="menuitem">View Item</a> </li> </ul> </div> <ul class="wrap-breadcrumb breadcrumb hidden-xs"> <li> <a href="/">DSpace@MIT Home</a> </li> <li> <a href="/handle/1721.1/49432">MIT Open Access Articles</a> </li> <li> <a href="/handle/1721.1/49433">MIT Open Access Articles</a> </li> <li class="active">View Item</li> </ul> </div> </div> </div> </div> <div class="hidden" id="no-js-warning-wrapper"> <div id="no-js-warning"> <div class="notice failure">JavaScript is disabled for your browser. Some features of this site may not work without it.</div> </div> </div> <div class="wrap-content" id="main-container"> <div class="starter"> <button type="button" class="navbar-toggle visible-xs visible-sm pull-right" data-toggle="offcanvas"><span class="sr-only">Toggle navigation</span><span class="icon-bar"></span><span class="icon-bar"></span><span class="icon-bar"></span></button> </div> <div class="row row-offcanvas row-offcanvas-right"> <div class="horizontal-slider clearfix"> <div class="col-xs-12 col-sm-12 col-md-9 main-content"> <div> <div id="aspect_versioning_VersionNoticeTransformer_div_item-view" class="ds-static-div primary">  <div class="item-summary-view-metadata"> <h2 class="page-header first-page-header">Chance Constrained Finite Horizon Optimal Control</h2> <div class="simple-item-view-authors item-page-field-wrapper table"> <h5>Author(s)</h5> <span class=" ds-dc_contributor_author-authority "><span class="author-list-1">Ono, Masahiro</span></span><span class="author-spacer-list-2">; </span><span class=" ds-dc_contributor_author-authority "><span class="author-list-2">Williams, Brian Charles</span></span><span class="author-spacer-list-3">; </span><span class=" ds-dc_contributor_author-authority "><span class="author-list-3">Blackmore, Lars</span></span> </div> <div class="row"> <div class="col-sm-4 smaller-font"> <div class="row"> <div class="col-xs-6 col-sm-12"> <div class="thumbnail"> <img alt="Thumbnail" class="img-thumbnail" src="/bitstream/handle/1721.1/67480/Williams-2010-Chance%20Constrained%20Finite%20Horizon%20Optimal%20Control.pdf.jpg?sequence=5&isAllowed=y"></div> </div> <div class="col-xs-6 col-sm-12"> <div class="item-page-field-wrapper table word-break"> <div> <a class="btn btn-primary download-button" href="/bitstream/handle/1721.1/67480/Williams-2010-Chance%20Constrained%20Finite%20Horizon%20Optimal%20Control.pdf?sequence=2&isAllowed=y">Download</a>Williams-2010-Chance Constrained Finite Horizon Optimal Control.pdf (528.5Kb)</div> <div class="bitstream-license"> <a href="#" class="license-key"><i class="glyphicon glyphicon-list-alt" aria-hidden="true"></i> OPEN_ACCESS_POLICY</a> <div class="hidden license-content"><!DOCTYPE html> <html> <body> <h1>Open Access Policy</h1> <p>Creative Commons Attribution-Noncommercial-Share Alike</p> </body> </html></div> </div> </div> <div class="item-page-field-wrapper table word-break"></div> </div> </div> <div class="simple-item-view-terms item-page-field-wrapper"> <h5>Terms of use</h5> <div> <field mdschema="dc" language="en_US" element="rights">Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use.</field> </div> </div> <div class="simple-item-view-show-full item-page-field-wrapper table"> <h5>Metadata</h5> <a href="/handle/1721.1/67480?show=full">Show full item record</a> </div> </div> <div class="col-sm-8"> <div class="simple-item-view-description item-page-field-wrapper table"> <h5>Abstract</h5> <div>This paper considers finite-horizon optimal control for dynamic systems subject to additive Gaussian-distributed stochastic disturbance and a chance constraint on the system state defined on a non-convex feasible space. The chance constraint requires that the probability of constraint violation is below a user-specified risk bound. A great deal of recent work has studied joint chance constraints, which are defined on the a conjunction of linear state constraints. These constraints can handle convex feasible regions, but do not extend readily to problems with non-convex state spaces, such as path planning with obstacles. In this paper we extend our prior work on chance constrained control in non-convex feasible regions to develop a new algorithm that solves the chance constrained control problem with very little conservatism compared to prior approaches. In order to address the non-convex chance constrained optimization problem, we present two innovative ideas in this paper. First, we develop a new bounding method 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. However, the slow computation of the branch and bound algorithm prevents practical applications. This issue is addressed by our second innovation called Fixed Risk Relaxation (FRR), which efficiently gives a tight lower bound to the convex chance-constrained optimization problem. Our empirical results show that the FRR typically makes branch and bound algorithm 10-20 times faster. In addition we show that the new algorithm is significantly less conservative than the existing approach.</div> </div> <div class="simple-item-view-date word-break item-page-field-wrapper table"> <h5>Date issued</h5>2010-07</div> <div class="simple-item-view-uri item-page-field-wrapper table"> <h5>URI</h5> <span><a href="http://hdl.handle.net/1721.1/67480">http://hdl.handle.net/1721.1/67480</a></span> </div> <div class="simple-item-view-department item-page-field-wrapper"> <h5>Department</h5> <span>Massachusetts Institute of Technology. Department of Aeronautics and Astronautics</span> </div> <div class="simple-item-view-journal item-page-field-wrapper"> <h5>Journal</h5> <div>American Control Conference, 2010. ACC '10.</div> </div> <div class="simple-item-view-journal item-page-field-wrapper"> <h5>Publisher</h5> <div>American Automatic Control Council</div> </div> <div class="simple-item-view-citation item-page-field-wrapper"> <h5>Citation</h5> <div>Ono, M., L. Blackmore, and B.C. Williams. “Chance constrained finite horizon optimal control with nonconvex constraints.” Proceedings of the American Control Conference (ACC), Marriott Waterfront, Baltimore, MD, USA June 30-July 02, 2010. 1145-1152.© 2010 American Automatic Control Council.</div> <div>Version: <field qualifier="version" mdschema="dc" language="en_US" element="eprint">Final published version</field> </div> </div> <div class="simple-item-view-identifier item-page-field-wrapper"> <h5>ISBN</h5> <div>978-1-4244-7426-4</div> </div> <div class="simple-item-view-identifier item-page-field-wrapper"> <h5>ISSN</h5> <div>0743-1619</div> </div> <hr class="collection-separator"> <div class="simple-item-view-collections item-page-field-wrapper table"> <h5>Collections</h5> <ul class="ds-referenceSet-list">  <li> <a href="/handle/1721.1/49433">MIT Open Access Articles</a> </li> </ul> </div> </div> </div> </div> </div> <div id="aspect_statistics_statlet_StatletTransformer_div_showStats" class="ds-static-div"> <p class="ds-paragraph"> <a href="#" class="btn btn-default">Show Statistical Information</a> </p> <p class="ds-paragraph"> <input id="aspect_statistics_statlet_StatletTransformer_field_contextpath" class="ds-hidden-field form-control" name="contextpath" type="hidden" value=""> </p> <p class="ds-paragraph"> <input id="aspect_statistics_statlet_StatletTransformer_field_statlet-ms-hide" class="ds-hidden-field form-control" name="statlet-ms-hide" type="hidden" value="Hide Statistical Information"> </p> <p class="ds-paragraph"> <input id="aspect_statistics_statlet_StatletTransformer_field_statlet-ms-ajax-timeout" class="ds-hidden-field form-control" name="statlet-ms-ajax-timeout" type="hidden" value="The server did not respond in time. Please try again."> </p> <p class="ds-paragraph"> <input id="aspect_statistics_statlet_StatletTransformer_field_statlet-ms-ajax-timeout-retry" class="ds-hidden-field form-control" name="statlet-ms-ajax-timeout-retry" type="hidden" value="Retry"> </p> <p class="ds-paragraph"> <input id="aspect_statistics_statlet_StatletTransformer_field_statlet-ms-ajax-error" class="ds-hidden-field form-control" name="statlet-ms-ajax-error" type="hidden" value="No statistical information could be retrieved. Please try again later."> </p> <p class="ds-paragraph"> <input id="aspect_statistics_statlet_StatletTransformer_field_statlet-ajax-call" class="ds-hidden-field form-control" name="statlet-ajax-call" type="hidden" value="/statlet/em/handle/1721.1/67480"> </p> <p class="ds-paragraph"> <input id="aspect_statistics_statlet_StatletTransformer_field_statlet-ajax-handle" class="ds-hidden-field form-control" name="statlet-ajax-handle" type="hidden" value="1721.1/67480"> </p> </div> </div> </div> <div role="navigation" id="sidebar" class="col-xs-6 col-sm-3 sidebar-offcanvas"> <div class="word-break hidden-print" id="ds-options"> <div class="ds-option-set" id="ds-search-option"> <form method="post" class="" id="ds-search-form" action="/discover"> <fieldset> <div class="input-group"> <input placeholder="Search" type="text" class="ds-text-field form-control" aria-label="Search MIT DSpace" name="query"><span class="input-group-btn"><button title="Go" class="ds-button-field btn btn-primary"><span aria-hidden="true" class="glyphicon glyphicon-search"></span></button></span> </div> <div class="radio"> <label><input checked value="" name="scope" type="radio" id="ds-search-form-scope-all">Search DSpace</label> </div> <div class="radio"> <label><input name="scope" type="radio" id="ds-search-form-scope-container" value="1721.1/49433">This Collection</label> </div> </fieldset> </form> </div> <h2 class="ds-option-set-head h6">Browse</h2> <div id="aspect_viewArtifacts_Navigation_list_browse" class="list-group"> <a class="list-group-item active"><span class="h5 list-group-item-heading h5">All of DSpace</span></a><a href="/community-list" class="list-group-item ds-option">Communities & Collections</a><a href="/browse?type=dateissued" class="list-group-item ds-option">By Issue Date</a><a href="/browse?type=author" class="list-group-item ds-option">Authors</a><a href="/browse?type=title" class="list-group-item ds-option">Titles</a><a href="/browse?type=subject" class="list-group-item ds-option">Subjects</a><a class="list-group-item active"><span class="h5 list-group-item-heading h5">This Collection</span></a><a href="/handle/1721.1/49433/browse?type=dateissued" class="list-group-item ds-option">By Issue Date</a><a href="/handle/1721.1/49433/browse?type=author" class="list-group-item ds-option">Authors</a><a href="/handle/1721.1/49433/browse?type=title" class="list-group-item ds-option">Titles</a><a href="/handle/1721.1/49433/browse?type=subject" class="list-group-item ds-option">Subjects</a> </div> <h2 class="ds-option-set-head h6">My Account</h2> <div id="aspect_viewArtifacts_Navigation_list_account" class="list-group"> <a href="/login" class="list-group-item ds-option">Login</a> </div> <div id="aspect_viewArtifacts_Navigation_list_context" class="list-group"></div> <div id="aspect_viewArtifacts_Navigation_list_administrative" class="list-group"></div> <div id="aspect_discovery_Navigation_list_discovery" class="list-group"></div> <h2 class="ds-option-set-head h6">Statistics</h2> <div id="aspect_statistics_Navigation_list_reportingSuite" class="list-group atmire-module"> <a href="/oastats" class="list-group-item ds-option">OA Statistics</a><a href="/handle/1721.1/49433/most-popular/country" class="list-group-item ds-option">Statistics by Country</a><a href="/handle/1721.1/49433/most-popular/department" class="list-group-item ds-option">Statistics by Department</a> </div> </div> </div> </div> </div> </div> <footer> <div class="wrap-outer-footer layout-band"> <div class="wrap-footer footer-slim"> <div aria-label="MIT Libraries footer" class="footer-main"> <div class="identity"> <div class="wrap-logo-lib"> <a class="logo-mit-lib" href="https://libraries.mit.edu"><img width="150" alt="MIT Libraries" src="https://cdn.libraries.mit.edu/files/branding/local/mitlib-wordmark.svg"></a> </div> <div class="wrap-middle"> <div class="wrap-policies"> <nav aria-label="MIT Libraries policy menu"> <span class="item"><a class="link-sub" href="https://libraries.mit.edu/privacy">Privacy</a></span><span class="item"><a class="link-sub" href="https://libraries.mit.edu/permissions">Permissions</a></span><span class="item"><a class="link-sub" href="https://libraries.mit.edu/accessibility">Accessibility</a></span><span class="item"><a class="link-sub" href="https://libraries.mit.edu/contact">Contact us</a></span> </nav> </div> </div> </div> </div> </div> </div> <div class="wrap-outer-footer-institute layout-band"> <div class="wrap-footer-institute"> <div class="footer-info-institute"> <a href="https://www.mit.edu" class="link-logo-mit"><img width="150" alt="MIT" src="https://cdn.libraries.mit.edu/files/branding/local/mit_lockup_std-three-line_rgb_white.svg"></a> <div class="license">Content created by the MIT Libraries, <a href="https://creativecommons.org/licenses/by-nc/4.0/">CC BY-NC</a> unless otherwise noted. <a href="https://libraries.mit.edu/research-support/notices/copyright-notify/">Notify us about copyright concerns</a>. </div> </div> </div> </div> </footer> <script type="text/javascript"> if(typeof window.import === 'undefined'){ window.import={}; }; window.import.contextPath= '';window.import.themePath= '/themes/Mirage2/';</script><script type="text/javascript"> if(typeof window.publication === 'undefined'){ window.publication={}; }; window.publication.contextPath= '';window.publication.themePath= '/themes/Mirage2/';</script><script type="text/javascript"> if(typeof window.DSpace === 'undefined'){ window.DSpace={}; };</script><script>if(!window.DSpace){window.DSpace={};}window.DSpace.context_path='';window.DSpace.theme_path='/themes/Mirage2/';</script><script src="/themes/Mirage2/scripts/theme.js"> </script><script src="/aspects/ReportingSuite/scripts/statlet_main.js"> </script><script src="/aspects/MetadataQuality/mqm-global.js"> </script><script> var _paq = window._paq = window._paq || []; /* tracker methods like "setCustomDimension" should be called before "trackPageView" */ _paq.push(['trackPageView']); _paq.push(['enableLinkTracking']); (function() { var u="https://matomo.libraries.mit.edu/"; _paq.push(['setTrackerUrl', u+'matomo.php']); _paq.push(['setSiteId', '7']); var d=document, g=d.createElement('script'), s=d.getElementsByTagName('script')[0]; g.async=true; g.src=u+'matomo.js'; s.parentNode.insertBefore(g,s); })(); </script> </body></html>