Adaptation in Dynamic Environments: A Case Study in Mission Planning

• Published in: IEEE transactions on evolutionary computation 2012-04, Vol.16 (2), p.190-209
• Main Authors: Bui, L. T., Michalewicz, Z., Parkinson, E., Abello, M. B.
• Format: Article
• Language: English
• Subjects: Adaptation; Applied sciences; Computer science; control theory; systems; Data processing. List processing. Character string processing; Decision theory. Utility theory; dynamic environments; Dynamic scheduling; evolutionary algorithms; Exact sciences and technology; Genetic algorithms; Memory organisation. Data processing; multiobjective optimization; Operational research and scientific management; Operational research. Management science; Optimal scheduling; Planning; Software; Software engineering; Vectors
• ISSN: 1089-778X; 1941-0026
• DOI: 10.1109/TEVC.2010.2104156

Many random events usually are associated with executions of operational plans at various companies and organizations. For example, some tasks might be delayed and/or executed earlier. Some operational constraints can be introduced due to new regulations or business rules. In some cases, there might be a shift in the relative importance of objectives associated with these plans. All these potential modifications create a huge pressure on planning staff for generating plans that can adapt quickly to changes in environment during execution. In this paper, we address adaptation in dynamic environments. Many researchers in evolutionary community addressed the problem of optimization in dynamic environments. Through an overview on applying evolutionary algorithms for solving dynamic optimization problems, we classify the paper into two main categories: 1) finding/tracking optima, and 2) adaptation and we discuss their relevance for solving planning problems. Based on this discussion, we propose a computational approach to adaptation within the context of planning. This approach models the dynamic planning problem as a multiobjective optimization problem and an evolutionary mechanism is incorporated; this adapts the current solution to new situations when a change occurs. As the multiobjective model is used, the proposed approach produces a set of non-dominated solutions after each planning cycle. This set of solutions can be perceived as an information-rich data set which can be used to support the adaptation process against the effect of changes. The main question is how to exploit this set efficiently. In this paper, we propose a method based on the concept of centroids over a number of changing-time steps; at each step we obtain a set of non-dominated solutions. We carried out a case study on this proposed approach. Mission planning was used for our experiments and experimental analysis. We selected mission planning as our test environment because battlefields are always highly dynamic and uncertain and can be conveniently used to demonstrate different types of changes, especially time-varying constraints. The obtained results support the significance of our centroid-based approach.