# Evolutionary System Design with Answer Set Programming
## 7 Summary  
We tackled the evolutionary system design (ESD) problem using answer set programming modulo difference constraints. Evolutionary system design consists of two steps:  
1. Perform design space exploration for a system synthesis problem and obtain and implement a high-quality solution;
2. Perform design space exploration for a similar system synthesis problem while maximizing similarity to the previously obtained high quality solution. This process allows for the swift finding of new design points that, first, are likely to have better quality because of the system synthesis problems having similar structure, and second, enhance the time-to-market for the implementation of a given design point as a product. We can use ESD for a variety of applications pertaining to embedded systems, such as successor generations, intra-generation variants, low-cost or high-performance variants, or functionality updates. We formalize all aspects of ESD, namely, the system synthesis problem, along with the design space exploration process, which consist of finding the Pareto front regarding the quality measures of latency, cost, and energy consumption, and similarity measures between two implementations. We then presented AMT encodings that capture all these aspects. The system synthesis problem has been previously tackled with ASP [17; 18; 19; 20; 21]. This application is inherently hybrid as routing and conflict detection and resolution of messages are combinatorial in nature and require reachability, which can be easily handled with plain ASP. On the other hand, scheduling requires fine-grained timing involving linear constraints over integer variables, which we captured via difference constraints. A similar division of labor was also applied to other applications involving scheduling, e.g., train scheduling [22] and job shop scheduling [23]. Furthermore, we provided alternative message routing techniques for improving the solving performance. We introduced three classes of techniques for achieving similarity between implementations: strategies, preferences, and heuristics. Strategies restrict the search space and only allow for similar solutions. Preferences include similarity as an additional objective in Pareto optimization. Heuristics reorder the search space such that similar implementations are found first. To our knowledge, ESD has not been tackled to the extent presented in this paper with technologies such as ASP, satisfiability testing (SAT [24]), or similar combinatorial approaches. The underlying design space exploration, however, was addressed via different meta-heuristic techniques (e.g., [25; 26]), exact methods such as integer linear programming (ILP) (e.g., [27; 28]), and meta-heuristics combined with SAT (e.g., [29; 30]). While meta-heuristics usually generate solutions faster for large instances, they might output the same or infeasible solutions repeatably; AMT, as with other exact methods, does not suffer from that drawback. Compared with other exact methods, though, ASP is uniquely suited to encode reachability, which is used for routing. As a matter of fact, reachability can be encoded natively and more succinctly in ASP compared with SAT. Finally, most of the previously mentioned methods only allow for single-objective optimization, while our ASP-based framework allows for a full Paretooptimization. ESD can be compared with the minimal perturbation problem [31]; for instance, this problem has been solved using ASP for curriculum-based timetabling [32] and nurse re-rosteering [33]. The main difference to our approach is that the quality is single-objective. We could formulate the ESD in terms of a minimal perturbation problem by having a hierarchical Pareto optimization, where the top level is bi-objective with stability defined with the Hamming distance and quality given by a vector of cost, latency, and energy consumption. We systematically and empirically evaluated our techniques.