Search-based Plan Reuse in Self-* Systems

Created by W.Langdon from gp-bibliography.bib Revision:1.7778

@PhdThesis{Kinneer2021,

• author = "Cody Kinneer",
• title = "Search-based Plan Reuse in Self-* Systems",
• school = "Institute for Software Research, School of Computer Science, Carnegie Mellon University",
• year = "2021",
• address = "Pittsburgh, PA 15213, USA",
• month = may,
• keywords = "genetic algorithms, genetic programming, self-star, planning, uncertainty, reuse, evolutionary computation",
• URL = "https://kilthub.cmu.edu/articles/thesis/Search-based_Plan_Reuse_in_Self-_Systems/16645735",
• DOI = "doi:10.1184/R1/16645735.v1",
• size = "122 pages",
• abstract = "Increasingly software systems operate in environments of change and uncertainty, where the system ability to satisfy its quality objectives depends on its ability to adapt. Self-adaptation allows these systems to manage this challenge by autonomously adapting to changes in their environments. While self-* systems are designed precisely to manage uncertainty, unexpected changes may violate design assumptions, resulting in the system failing to satisfy its quality attribute requirements. When this occurs, the planner must generate a new plan, an expensive operation for large systems. As autonomous systems increase in size, interconnectedness, and complexity, this cost can quickly become prohibitive.

  This thesis addresses this problem by leveraging information contained in prior plans to reduce the re-planning necessary to respond to an unexpected change. Even in the face of an unexpected change, some of the insights contained in existing plans are likely to remain applicable. For example, an autonomous aerial vehicle encountering an unexpected obstacle will need to replan to avoid the obstacle, but the drone may be able to return to its prior plan after this maneuver. A larger change will reduce the amount of reuse that is possible, for example changing the drones mission to fly to a new location, but still, the take-off and landing procedures may be reused. This thesis reuses existing adaptation plans by seeding a genetic algorithm with these plans. This enables a scalable self-star planner that can replan in complex systems with large search spaces.

  While the idea of plan reuse is intuitive, in practice plan reuse is difficult and may even be worse than replanning from scratch if not performed carefully. This dissertation provides reuse enhancing approaches to reduce the evaluation time of candidate plans, an approach for building reusable repertoires of plans and identifying generalizable plan fragments, and a co-evolutionary extension to enable plan reuse for security. The thesis is evaluated on three simulated case study systems, including a cloud-based web service provider, a team of autonomous aerial vehicles, and an enterprise business system under a cyber attack. Ultimately, plan reuse will enable large self-* systems to replan even after unexpected changes.",

• notes = "'We can enable self-* systems with large state spaces to evolve in response to un-expected changes by reusing existing plans with stochastic search in the following three ways:

  (a) reusing existing plans using genetic programming and reuse enhancing approaches to reduce evaluation time,

  (b) building reusable repertoires by identifying generalisable plan fragments to build resilience against a wide range of unexpected scenarios, and

  (c) reusing strategies in adversarial settings.'

  Supervisors: Claire Le Goues and David Garlan",

}

Genetic Programming entries for Cody Kinneer

Citations