Hybrid Planning in Self-adaptive Systems
thesisposted on 03.03.2020, 16:24 by Ashutosh PandeyAshutosh Pandey
Planning is one of the fundamental design considerations when building a self adaptive 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 ﬁnd a plan is critical to a successful self-adaptation. For many adaptive systems, an appropriate planner is the one that not only ﬁnds 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 ﬁnds a plan quickly and an approach that is slow but ﬁnds a higher-quality plan. To deal with this trade-off, this thesis proposes a hybrid planning approach for self-adaptive systems that combines off-the-shelf deliberative and reactive planners to ﬁndabalancebetweenqualityandtimeliness. The key ideas 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 beneﬁts of both worlds: providing plans quickly when the timing is critical, while allowing (nearly) optimal plans to be generated when the system has sufﬁcient 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 ﬁnd 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. Speciﬁcally, the thesis provides: (a) a formal framework deﬁning 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.
DepartmentInstitute for Software Research
- Doctor of Philosophy (PhD)