# Evolutionary System Design with Answer Set Programming
## 4 Encoding the System Synthesis Problem with ASP Modulo Difference Constraints
### General Problem Encoding
Note that this encoding does not produce all valid routings but only valid routings with acyclic routes. To facilitate cyclic routes, one must add an additional order when resources are visited, akin to a time step in action encodings. We decided against this since cycles offer little merit because we use a circuit switching scheduling strategy. For our parent implementation in Figure 2, the atoms capturing the routing are as follows:  
```
route((t1,t2),r1,r5) route((t2,t4),r3,r7) route((t1,t2),r5,r7) route((t2,t4),r7,r5) route((t1,t2),r7,r3) route((t2,t4),r5,r1)
```  
```
route((t1,t3),r1,r5) route((t3,t4),r3,r7) route((t1,t3),r5,r7) route((t3,t4),r7,r5) route((t1,t3),r7,r3) route((t3,t4),r5,r1)
```  
For several conditions on valid schedulings, we require the number of links used in every communication, the so-called _hops_. Listing 4 achieves this goal via a technique called chaining. First, we need to find an upper bound to the possible number of hops so that grounding is possible. This is the number of links in the network (Line 1). Then, we initialize the count with zero at the resource where the sending task is bound to (Line 2). Recursively, we add one to our count for every link the communication uses in Line 3 if we have not yet reached the maximum limit. Finally, we can determine the number of hops by selecting the hop count at the resource that the receiving task is bound to (Line 5). In detail, atom hops(\(d,n\)) determines that communication \(d\) takes \(n\) hops. Note that we can use the #count directive to count the links as this is static information and the count is determined at grounding time. On the other hand, it would lead to an exponential number of rules if we encoded the counting of the hops in the same way because all possible subsets of routes taken need to be considered. Our chaining encoding scales with the number of links multiplied by the number of resources. So, in the worst case, it is cubic in the number of resources and has better propagation properties compared with the #count-based method. ```
1 nr_links(NR):-NR=#count{link(N,N'):link(N,N')}. 2 hops((T,T'),R,0):-send(T,T'),bind(T,R). 3 hops(C,R',H+1):-hops(C,R,H),route(C,R,R'),
4H<HR,nr_links(NR). 5 hops(C,H):-hops(C,R,H),send(T,T'),bind(T',R). ```  
**Listing 4**. Calculating number of hops for every communication. Because scheduling relies on deciding what tasks to execute first on the same resource, or what communications to send first if they use the same link, we need to facilitate that choice in our encoding. Listing 5 detects conflicts among tasks and communications and assigns priorities via atoms over predicate priority/2. In detail, atom priority(\(t,t^{\prime}\)) expresses that \(t\) is executed before \(t^{\prime}\) may start for \(t\in\mathbb{T}\cup\mathbb{D}\). In order to narrow the search for conflicts, we first analyze which tasks and communications depend on each other, i.e., which are sequentially executed in one application and therefore cannot be simultaneously executed. We first determine direct dependencies in Lines 1 to 2; here, task dependencies are directly given and communication dependencies arise whenever the receiver task of a communication becomes a sender task of another communication. Then, we build the transitive closure in Lines 4 to 5. Note that this is usually expensive with respect to memory and performance, but here, we only build the transitive closure on domain predicates that are decided during grounding. The rule in Line 7 determines the conflicts between resources. Two tasks are in a conflict if they are bound to the same resource and they do not depend on each other. Note that the grounding is quadratic in the number of tasks. We reduce the problem size by ordering the tasks alphanumerically and by only considering conflicts where the first task is smaller. We explain in the scheduling encoding that this does not lead to a loss of information. Similarly, Line 12 determines conflicts between communications.