| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | June 20, 2014 |
| Latest Amendment Date: | June 20, 2014 |
| Award Number: | 1422658 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Phillip Regalia
pregalia@nsf.gov (703)292-2981 CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | July 1, 2014 |
| End Date: | December 31, 2018 (Estimated) |
| Total Intended Award Amount: | $499,962.00 |
| Total Awarded Amount to Date: | $499,962.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
601 S HOWES ST FORT COLLINS CO US 80521-2807 (970)491-6355 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
200 W. Lake St. Fort Collins CO US 80521-4593 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Comm & Information Foundations |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
In a great number of problems in engineering and applied science, we are faced with optimally choosing a sequence of actions over a finite horizon to maximize an objective function. The problem arises in sequential decision making in engineering, economics, management science, and medicine. However, in such problems, optimal strategies are hard to compute in general. On the other hand, greedy strategies, though suboptimal in general, are easy to compute because they only involve finding an action at each stage to maximize the step-wise gain in the objective function. This research provides a systematic method to bound the suboptimality of greedy strategies relative to optimal strategies. This research has broad impact both in application areas and educationally.
New results extend the notion of submodular functions over sets to submodular functions over strings. These results establish that, under string submodularity, the greedy strategies achieve a performance that is no worse than a factor of (approximately) 63% of optimal strategies in sequential decision problems. Under additional curvature conditions, this bound becomes even sharper. This research involves a number of issues related to this new string-submodularity framework as follows: 1) Identifying canonical problems in sensing and control that can be treated systematically using the string-submodularity framework; 2) Bounding the performance of approximate dynamic programming (ADP) by reducing a given ADP method into a greedy strategy associated with an induced submodular string function; 3) Going beyond submodularity by investigating relaxed definitions of submodularity and curvature in order to greatly expand the scope of the applicability of the theory.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
In a great number of problems in engineering and applied science, we are faced with optimally choosing a string (finite sequence) of actions over a finite horizon to maximize an objective function. The problem arises in sequential decision making in engineering, economics, management science, and medicine. However, optimal strategies are hard to compute in general. One approach is to use dynamic programing via Bellman’s principle. However, the computational complexity of this approach grows exponentially with the size of the action space and the decision horizon. On the other hand, the greedy strategy, though suboptimal in general, is easy to compute because it only involves finding an action at each stage to maximize the step-wise gain in the objective function. But how does the greedy strategy compare to the optimal strategy in terms of the objective function?
This project resulted in the development of a systematic method, based on string-submodularity theory, for bounding the suboptimality of greedy strategies relative to optimal strategies in sequential decision problems. It also led to identifying canonical problems that can be treated systematically using the string-submodularity framework. In each canonical problem, the relationship between the problem features (e.g., problem parameter values) and string-submodularity was established. The project also led to the development of a general framework for bounding the performance of approximate dynamic programming (ADP) schemes in the deterministic setting. This framework provides the first step toward developing a systematic approach to bounding the performance of ADP schemes in the stochastic setting, as they arise in numerous problems in optimal control and adaptive sensing.
The results of the project were disseminated in a number of journal papers and conference presentations.
Last Modified: 03/27/2019
Modified by: Ali Pezeshki
Please report errors in award information by writing to: awardsearch@nsf.gov.
