SOLICITED NASA PROPOSAL APPLICATION / 1.1.1.1.1.1.1LEAVE BLANK
SOLICITED NASA PROPOSAL APPLICATION / LEAVE BLANK
IN RESPONSE TO ANNOUNCEMENT NRA2-38169 / NUMBER
REVIEW GROUP
PLEASE FOLLOW INSTRUCTIONS CAREFULLY / DATE RECEIVED
1a. COMPLETE TITLE OF PROJECT:
1b. PROPOSAL TOPIC:
2. PRINCIPAL INVESTIGATOR/PROGRAM DIRECTOR (First, middle, andlast name; degrees; position)
3. COMPLETE MAILING ADDRESS
Congressional District:
4. TELEPHONE NUMBER (area code, number, extension) / 5. / TAXPAYER IDENTIFICATION NO. (TIN)
FAX NUMBER: / 6. / NAIS CODE / CAGE CODE
E-MAIL ADDRESS:
7. HAS THIS PROPOSAL (OR SIMILAR REQUEST) BEEN SUBMITTED TO ANY OTHER AGENCY?
No Yes IF YES, SPECIFY AGENCY AND YEAR SUBMITTED:
8. WILL HUMAN SUBJECTS BE USED IN THE PROPOSED RESEARCH: No Yes
9. CO-INVESTIGATORS (First, middle, and last name; degrees) / 10. CO-INVESTIGATOR'S ORGANIZATION
11. OTHER PARTICIPATING ORGANIZATIONS (e.g., NASAFieldCenters or Other Institutions):
12. DATES OF ENTIRE / 13. FY2004 BUDGET / 14. FY2005 BUDGET / 15. FY2006 BUDGET / 16. TOTAL BUDGET
PROPOSED PROJECT PERIOD / Total Cost: / Total Cost: / Total Cost: / Total Cost:
From: / NASA / NASA / NASA / NASA
Through: / Contribution: / Contribution: / Contribution: / Contribution:
17. APPLICANT ORGANIZATION (Organization Name)
18. TYPE OF ORGANIZATION (U.S. ONLY)
For Profit (General) For Profit (Small Business) For Profit (Woman-owned Business) / For Profit (Minority-owned Business) Non Profit
College or University (General) College or University (Historically Black or other Minority) / Public, Specify: Federal State Local
19. ORGANIZATION OFFICIAL TO BE NOTIFIED IF AN AWARD IS / 20. OFFICIAL SIGNING FOR APPLICANT
MADE(Name, title, address, and telephone number) / ORGANIZATION(Name, title, and telephone number)
21. PRINCIPAL INVESTIGATOR/PROGRAM DIRECTOR ASSURANCE: / SIGNATURE OF PERSON NAMED IN BLOCK 2
I agree to accept responsibility for the technical conduct of the project and to provide the
required progress reports if a grant is awarded as a result of this application. Willful provision
of false information is a criminal offense (U.S. Code, Title 18, Section 1001). / (In ink; "Per" signature not acceptable.)
______Date:______
22. CERTIFICATION AND ACCEPTANCE:
By submitting the proposal identified in this Cover Sheet/Proposal Summary in response
to NRA2-38169, the Authorizing Official of the proposing institution (or the individual proposer
if there is no proposing institution): 1) certifies that the statements made in this proposal are
true and complete to the best of his/her knowledge; 2) agrees to accept the obligations to comply with the sponsoring agency award terms and conditions if an award is made as a result of this proposal; and 3) if the applicant organization is an entity of the United States of America, confirms compliance with all provisions, rules, and stipulations set forth in the three Certifications contained in this NRA (namely, i) Certification Regarding Debarment, Suspension, and Other Responsibility Matters -- Primary Covered Transactions, ii) Certification Regarding Lobbying, and iii) Certification of Compliance with the National Aeronautics and Space Administration Regulations Pursuant to Nondiscrimination in Federally Assisted Programs). Willful provision of false information in this proposal and/or its supporting documents, or in reports required under an ensuing award, is a criminal offense (U.S. Code, Title 18, Section 1001). / SIGNATURE OF PERSON NAMED IN BLOCK 20
(or person named in 2, if there is no proposing institution)
(In ink; "Per" signature not acceptable.)
______
Date:______
Model-based Execution of Mobile Systems—Brian C. Williams
Cooperative Model-based Programming and Execution of Mobile Systems by Unifying Fast, Optimal Activity and Path Planning
Table of Contents
1Abstract
2NASA Relevance
3Technical Plan
4Management Plan
5Cost Plan
6Resumes
7Letters of Endorsement
8Letters of Commitment and Participation
9Reprints
1
Model-based Execution of Mobile Systems—Brian C. Williams
1Abstract
The next generation of autonomous NASA explorers will be mobile instruments that must navigate difficult terrains. Controlling these complex systems robustly is inherently difficult, motivating the need for a model-based executive that allows mission designers to program exploration robots in terms of intended states and locations. To satisfy this need, we provide the Kirk Model-based Executive, which performs unified optimal activity and path planning for mobile systems. This system will allow for mobile robotic missions to operate with greater autonomy on any terrain type, reducing the lag time between the rover and the ground station on earth and therefore increasing science return.
Objective
We will develop a model-based executive that allows for four basic features. First, program activities within Kirk’s modeling language, RMPL, are specified in terms of goal states and goal locations, allowing for greater autonomy. Second, the system executes robustly in the face of uncertain environments, plan failures, and complex terrain features by retaining flexibility in the generated plans. Third, it unifies activity and path planning and uses both elements as cost heuristics in order to discover a solution that is globally optimal. Finally, the system operates effectively under limited memory and computational resources by using memory-bounded optimal search and incremental algorithms, respectively.
Scientific Significance
First, the proposed work will serve as an investigation into the unification of activity-level and trajectory-level planning. This can serve to significantly improve the generation of plans that are globally optimal rather than optimal at just the activity or path planning level. Second, we apply fast, memory-bounded and optimal search algorithms to model-based temporal plans. This serves to greatly improve the impact and valuemodel-based executives for autonomous vehicles. Third, the research will involve the use of constraint-level search techniques with lower-level mathematical program solving techniques. The integration of these two fields is a research topic that is only beginning to be investigated. Lastly, we integrate simultaneous localization and mapping (SLAM) into the model-based planning framework to achieve more robust planning.
Expected Results
Kirk will be demonstrated in the context of three scenarios: the Mars ‘03 shadow mission, the August ‘04 IS demonstration, and the MSL technology gate in ‘05. In each demonstration, we expect to see continued development towards rover missions that execute an optimal unified activity/path plan that reacts in a timely manner under limited resources.
Value to Program
The proposed capability allows for significantly reduced down time of rover missions due to the increased level of autonomy and reduction in planning time. It also enables NASA to focus more on mission-level planning elements, and leave low-level planning to the autonomous rover. Both of these advances ultimately lead to increased science return by maximizing the efficiency of the vehicles and of NASA personnel, respectively.
2NASA Relevance
A major objective of all NASA missions is to maximize science return given a fixed amount of time to perform experiments. Nevertheless, the current Mars '09 approach to moving a rover about a science site is relatively slow and inefficient due to the limited degree of autonomy of the vehicles. Because trustworthy optimal methods of autonomous state estimation and system-level planning are not available to the rovers, scientists and engineers must halt a vehicle between motions and perform detailed planning on the ground. Additionally, the lack of a framework to robustly execute complex plans on the rover causes scientists to send up only short, simple plans for a rover to perform.
We depict the timeline for a Mars '09 scenario for performing rover experiments using current technologies in Figure 1 [14]. In the scenario, scientists on Earth use sensor data from the rover to evaluate the performance of the vehicle and determine the vehicle's current state. Scientists then pick out the next science targets and perform detailed path and activity planning, finally sending up a fully fleshed-out plan to the rover. Because path planning and activity planning require knowledge of the current state (e.g. the location) of the rover, and because the rover can only send sensor data down to Earth during fixed communication passes, the rover cannot move while planning occurs on Earth. Therefore significant time is wasted keeping the rover idle as shown in this scenario.
The Mars '09 framework for rover experiments is fundamentally limited by a lack of robust optimal autonomous planning and execution on the rovers. Our proposed research will move the framework beyond these limitations in two major ways. First, by having the rovers perform state estimation and system-level planning autonomously, a vehicle is no longer forced to remain idle while scientists plan on the ground. Instead, rovers can operate continuously, with mission controllers sending periodic goal sequence updates. Second, by providing fast, optimal, reliable system-level planning and model-based execution on the rovers, our research will allow NASA scientists to be confident that high-level goals and states will be accomplished, and accomplished efficiently. They will therefore be able to give a rover long, complex sets of goals, have the rover execute all of the goals at once, and then quickly verify the execution on Earth. This procedure is opposed to the current procedure of breaking up a complex task into many simple subtasks, doing low-level planning for a subtask, having the rover execute the subtask, and then doing performance analysis on the ground before having the rover execute the next subtask.
We will achieve the integration of autonomous state estimation into system-level planningby having path planning occur dynamically on the rover using the most up to datemap produced by simultaneous localization and mapping (SLAM)available. The SLAM map provides a dynamically updated estimate of the position and orientation of the rover in its environment.
We will achieve fast, optimal, and robust system-level planning and execution on the rovers by extending our current model-based executive, Kirk, into an autonomous executive for mobile systems that develops optimal plans by unifying activity, path, and trajectory planning. Currently Kirk allows mission designers to compose missions by specifying goal state evolutions, as opposed to low-level hardware commands. Kirk achieves robustness by selecting between redundant procedures to achieve goals, ensures plan consistency, and supports dynamic scheduling. We will extend Kirk to support mobile robots in three ways. First, we address optimality by having Kirk generate candidate plans that are globally optimal over the space of hybrid activity/path-plans. Through the use of memory-bounded algorithms, we ensure that the rover can achieve optimality. Second, we will augment Kirk’s robust execution techniques through the incorporation ofphysics-based path planning and resource management, as well as dynamic SLAM. These additions will allow rovers to handle difficult terrains effectively. Finally, we will improve both Kirk’s speed and robustness by using reactive planning. Our method for reactive planning provides speed by allowing the planner to reuse previous work, focus the search on the next best mission plan, and reduce the number of potential mission plans to consider.
The impact to NASA, first and foremost, will be improved mission robustness and a dramatic increase in science return. Controllers on Earth will no longer need to provide rovers with simple plans that are executed and then evaluated one at a time. With the added level of autonomy provided by the Kirk system, complex plans are executed in concert with data analysis on the ground, maximizing science return. Consider Figure 2; once planning for the first mission is completed, high-level planning for subsequent missions takes place on Earth while the first mission is executed on the rover. Additionally, a robust onboard incremental planner enables autonomous re-planning, which is far faster than requiring Earth-based mission specialists to re-plan from scratch. The vastly improved speed and efficiency will allow for a proportional increase in science return. Finally, our autonomous rover capability will free NASA mission specialists from doing low-level planning and allow them instead to focus on science target identification.
Looking beyond the Mars ‘09 mission, cooperative elements will become highly relevant in future explorations. One illustrative scenario is the cooperative exploration of a rover and a piggybacked agile scorpion robot (shown below). The rover’s speed enables the team to quickly cover vast distances over smooth terrain. When a science feature is discovered amidst rough terrain, the scorpion will be able to disembark from the rover and explore the feature using its agile maneuvering capabilities.
Scorpion Robot (left) and ATRV Jr. rover
3Technical Plan
In order to achieve the increased science gain of exploratory rovers through the use of fast, optimal, and robust system-level planning, we offer the Kirk Model-based Executive, shown in Figure 3. Kirk takes as input two RMPL programs: a control program describing the intended goals and states, and a vehicle description program describing the modeled vehicle dynamics. Kirk also takes as input a series of dynamically updated maps that allow Kirk to perform activities based on the current state of the environment. From these inputs, Kirk selects the optimal strategic plan on a unified activity/path-planning graph. This strategy is passed to Kirk’s deductive controller where physics-based path planning and onboard localization mapping is performed. From the deductive controller, low-level commands are sent to the rovers for execution. Observations returned from the hardware are used to update current maps of the environment and to notify Kirk of the need to select new optimal strategies due to unexpected events.
3.1Task Objectives
We offer four main requirements to assure safe robust execution in uncertain environments:
1)The system must make it easy to encode vehicle activities and work within the scope of what is allowed by the programmer. We address this by using RMPL operators within the plan specification. RMPL’s flexibility allows either high-level commands that increase rover autonomy or lower-level commands that increase user control over the rovers.
2)The system must allow dynamically-schedulable robust execution in response to execution uncertainty, plan failures, and complex, unknown terrain features. Uncertainty is addressed via flexible temporal constraints that allow small perturbations in execution time. Failures are addressed through fast online selection of contingent plans. Complex and unknown terrains are dealt with using physics-based path planning and onboard autonomous localization and mapping
3)The system will execute an optimally selected plan based on the activities and paths that maximize science gain. Both these elements – activities and paths – will be incorporated as the costs and heuristic estimates in an A* framework.
4)The system will be timely under limited computational and memory resources. We achieve this through the use of incremental algorithms and memory-bounded optimal search methods to increase the speed of plan selection in the face of plan failures and environmental changes.
3.2Evaluation Through Demonstration and Testbeds
Our objective is to demonstrate relevance to the MSL 2009 mission and beyond, through a three-step demonstration. During the first year, we will work with the MER mission in shadow mode to establish a baseline performance capability. Demonstrated capabilities include: 1) mission planning using Europa [6]; 2) Contingent non-optimal execution; 3) traditional, decoupled path planning; and 4) overhead vision-based localization. This and subsequent demonstrations will utilize the testbed at the MIT Space Systems Lab which consists of 4 RWI rovers (1 ATRV and 3 ATRV Jr.). We may also do concurrent separately-funded research on coupling the rover testbed to the NASA CLARAty architecture.
Our mid-project assessment will be through the IS program Level I milestone demonstration in August 2004 at NASA Ames or JPL. Technical elements verified will include optimal, unified contingent execution, global path planning, and sensor-based localization. This will require the use of numerous sensors such as laser scanners, vision hardware, including stereo and overhead cameras, and science instrumentation (e.g. VIS/NIR spectrometer).
Finally, in our third year we will incorporate mathematical dynamics and cooperative multi-vehicle elements into our planner. Capabilities will include optimal execution with physics-based path planning, concurrent mapping and path planning, and cooperation between vehicles. In particular we will test with scenarios that use rovers combined with piggybacked agile scorpion robots for science target exploration. We will also support a demonstration for the 2005 MSL technology gate, highlighting safe, optimal execution in MSL-relevant scenarios.
3.3Model-based Execution of Activities, Movements, and Contingencies
3.3.1RMPL for Mobile Systems
Robotic execution languages, such as RAPS [5]have been used widely in NASA testbeds at JSC, JPL, and ARC to execute the temporal activities of a mission plan. A key feature of these languages is that they introduce plan adaptation at the system-level by selectingbetween functionally redundant methods (e.g. choosing an alternate path to a science target). In addition, scientists are often uncomfortable using onboard autonomous mission-level planners, due to uncertainties in their reasoning abilities. Modeling languages address this problem by providing flexible operators that allow the specification of focused sets of contingencies. A model-based executive chooses from these contingencies at execution-time, maximizing robustness.