Planning is one of the fundamental design considerations when building a selfadaptive software system. Planning helps the adaptive system to determine an appropriate course of action at run time that seeks to change the system's behavior in response to faults, changing environments and security threats. Therefore, having an appropriate planner to find a plan is critical to a successful self-adaptation.

For many adaptive systems, an appropriate planner is the one that not only finds a plan quickly, particularly, in urgent circumstances but also the plan provides a near-optimal long-term performance. However, due to the fundamental trade-off between quality and timeliness of planning, today designers often have to compromise between an approach that finds a plan quickly and an approach that is slow but finds a higher-quality plan.

To deal with this trade-off, this thesis proposes a hybrid planning approach for self-adaptive systems that combines of-the-shelf deliberative and reactive planners to find a balance between quality and timeliness. The key idea is to use reactive planning to provide a quick (although potentially a sub-optimal) response, but simultaneously invoke deliberative planning to determine quality plans. Once the deliberative plan is ready, it takes over the execution from the reactive plan to provide a higher quality adaptation thereafter.

Such a combination of planners can, in principle, reap the benefits of both worlds: providing plans quickly when the timing is critical, while allowing (nearly) optimal plans to be generated when the system has sufficient time to do so. Moreover, instead of going through the non-trivial process of developing a new algorithm/heuristic, hybrid planning combines off-the-shelf planners; therefore, hybrid planning does not require software engineers to master the complexity of developing new planning algorithms/heuristics.

This thesis demonstrates that, compared to its constituent reactive and deliberative planners, hybrid planning can find a better balance between the timeliness and the quality of planning, thereby improve adaptation effectiveness as measured by a multidimensional utility function capturing different dimensions of a system's goal. In the process, the thesis makes contributions to both the theory and the practice of hybrid planning in self-adaptive systems. Specifically, the thesis provides: (a) a formal framework defining the problem of hybrid planning; (b) a practical approach (grounded in the formal model) to apply hybrid planning to self-adaptive systems; (c) informal guidelines and a quantitative approach to help engineers to select an appropriate set of planners to instantiate hybrid planning for a given domain, and (d) evaluation of hybrid planning using two realistic systems to bridge the gap between theory and practice.

164 pages

Thesis Committee:
David Garlan (Chair)
Jonathan Aldrich
John Dolan (Robotics)
Hausi Müller (University of Victoria, Canada)

James D. Herbsleb, Director, Institute for Software Research
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu