Plan generation and hard real -time execution with application to safe, autonomous flight.

We address the problem of constructing and executing control plans for safe, fully-autonomous operation within a complex real-time domain where the combination of an incomplete knowledge base, limited computational resources, and hard real-time deadlines precludes the success of traditional planning and scheduling algorithms. To meet hard deadlines with limited computational resources, we employ a stochastic world model to prioritize the state-space during planning, then utilize feedback from the scheduler to set a threshold below which the planner removes unlikely states from consideration in order to generate a schedulable plan. Our probabilistic planning algorithm minimizes domain knowledge size and explicitly provides for the construction of real-time control plans. Although approximate instead of optimal, the representational efficiency gained by our approach makes it a viable alternative to the well-established Markov Decision Process for complex real-time problem domains. When resource limits require plan modification, our heuristic algorithms for communicating task resource utilization information from real-time scheduler to planner provide a novel method for directing the expensive planner backtracking process specifically toward a schedulable plan. The tradeoff in ignoring reachable but unlikely states, as well as allowing incomplete domain knowledge, is that we must now provide explicitly for the detection of and reaction to these unexpected states our system may encounter while executing a plan. By detecting such unhandled states and caching contingency plans for events which, though unlikely, could lead to catastrophic failure, we can still guarantee system safety in the probabilistic sense. Ultimately, however, we are still constrained by plan-execution resource limits regardless of the tradeoff algorithms employed. We apply the resultant architecture (CIRCA-II) to simulated autonomous aircraft flight and demonstrate its utility for intelligently making tradeoffs that maximize mission success probability even under adverse circumstances in which other planner/scheduler algorithms would fail. We also describe progress toward fully-automating the University of Michigan Uninhabited Aerial Vehicle (UAV). When UAV hardware and low-level control software development are complete, we hope to apply a combination of CIRCA-II and state-of-the-art dynamic model identification algorithms to detect and react in real-time to dangerous in-flight emergencies including engine failure and airframe icing.PhDAerospace engineeringApplied SciencesComputer scienceElectrical engineeringSystems scienceUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/132068/2/9959698.pd