# Evolutionary System Design with Answer Set Programming
## 4 Encoding the System Synthesis Problem with ASP Modulo Difference Constraints
### General Problem Encoding
Finally, Line 5 restricts the routing of every communication to the calculated number of hops, where it is either the shortest path across the network or zero depending on the binding. ```
1 hops((T,T'),N):-bind(T,R),bind(T',R'),R!=R',send(T,T'),
2 location(R,(X,Y,Z)),location(R',(X',Y',Z')),
3N=|X-Y'|+|Y-Y'|+|Z-Z'|+2. 4 hops((T,T'),0):-bind(T,R),bind(T',R),send(T,T'). 5:-hops(C,N),notN{route(C,_,_):route(C,_,_)}N.
```
Listing 8: Bind number of hops to shortest path according to grid coordinates. Our parent implementation in Figure 2 fulfills this property. We have as coordinates \((0,1,0)\) and \((0,0,0)\) for r1 and r3, respectively. Then, the shortest number of hops is \(|0-0|+|1-0|+|0-0|+2=3\) for all communications, which is the amount each communication requires in this implementation. This encoding ensures the shortest paths while allowing for variable routes. Furthermore, we restrict the search space, which should lead to an improvement in the solving performance. Listing 9 shows the encoding for dimension-ordered routing. The basic idea is to find a path from the source to the target that first diminishes the distance in the x-coordinates until no distance remains, then the same for the y-coordinates and z-coordinates accordingly. For that purpose, the encoding creates a routing table that is stored in atoms over predicate next/3 (Lines 1-13). Essentially, an atom next(\((x,y,z)\),\((x^{\prime},y^{\prime},z^{\prime})\),\((x^{\prime\prime},y^{\prime\prime},z^{\prime\prime})\)) indicates that the shortest path from \((x,y,z)\) to \((x^{\prime},y^{\prime},z^{\prime})\) involves the link from \((x,y,z)\) to \((x^{\prime\prime},y^{\prime\prime},z^{\prime\prime})\). For every two locations \((x,y,z)\) and \((x^{\prime},y^{\prime},z^{\prime})\), the rules identify in order whether x-, y-, or z-coordinates are equal and make the case distinction of whether one has to increment or decrement the respective unequal coordinate to get closer to the target. Depending on the case, x-, y-, or z-coordinate are incremented or decremented by one to determine the next destination. Then, Lines 14 to 21 use the routing table to determine the route for all communications given the specific binding of the tasks involved. Furthermore, we can use the same calculation in Listing 8 to determine the number of hops. Note that routing now completely depends on binding and no longer involves independent planning. As above, we guarantee the shortest paths and we restrict the search space even further. However, this routing is the most inflexible, so we might discard implementations that achieve a better quality as communication may evade each other with the more flexible routing variants. #### 4.2.2 Preference Encoding

This section describes how we implement Pareto optimization. To describe preferences, we use the fact format of the system _aspirin_ described in [13], and to achieve grounding, solving, and optimization, we employ a Python script based on _clingo_'s theory and application framework [14]; the script is a re-implementation of the design space exploration system described in [2]. The general idea is that difference constraints as well as Pareto optimization are handled by background theories that are integrated via _clingo_'s theory interface. While the former sanctions thne validity of answer sets with respect to schedulability, the latter holds an archive of currently non-dominated implementations, updates this archive when new and better solutions are found, and adds conflict clauses whenever (partial) answer sets are dominated by members of the archive. In this way, the quality of implementations in the archive improves over time as more answer sets are found; eventually, the archive is equal to the Pareto front once no more non-dominated implementations can be found. ```
1 coord(X,Y,Z):-location(_,(X,Y,Z)). 2 next((X,Y,Z),(X',Y',Z'),(X+1,Y,Z)):-coord(X,Y,Z),coord(X',Y',Z'),
3 coord(X+1,Y,Z),X<X'. 4 next((X,Y,Z),(X',Y',Z'),(X-1,Y,Z)):-coord(X,Y,Z),coord(X',Y',Z'),
5 coord(X-1,Y,Z),X>X'.