4.1: Can we build it?

When designing a large-scale system, many different fields of expertise are joined to work on a single project. Thus the whole project team is divided into multiple sub-teams, each of which is working on a sub-project. And we recurse downward: the sub-project is again factored into sub-sub-projects, each with their own team. One could refer to this sort of hierarchical design process as collaborative design, or co-design. In this chapter, we discuss a mathematical theory of co-design, due to Andrea Censi [Cen15].

Consider just one level of this hierarchy: a project and a set of teams working on it. Each team is supposed to provide resources—sometimes called “functionalities”—to the project, but the team also requires resources in order to do so. Different design teams must be allowed to plan and work independently from one another in order for progress to be made. Yet the design decisions made by one group affect the design decisions others can make: if A wants more space in order to provide a better radio speaker, then B must use less space. So these teams—though ostensibly working independently—are dependent on each other after all.

The combination of dependence and independence is crucial for progress to be made, and yet it can cause major problems. When a team requires more resources than it originally expected to require, or if it cannot provide the resources that it originally claimed it could provide, the usual response is for the team to issue a design-change notice. But these affect neighboring teams: if team A now requires more than originally claimed, team B may have to change their design, which can in turn affect team C. Thus these design-change notices can ripple through the system through feedback loops and can cause whole projects to fail [S+15].

As an example, consider the design problem of creating a robot to carry some load at some velocity. The top-level planner breaks the problem into three design teams: chassis team, motor team, and battery team. Each of these teams could break up into multiple parts and the process repeated, but let’s remain at the top level and consider the resources produced and the resources required by each of our three teams.

The chassis in some sense provides all the functionality it carries the load at the velocity—but it requires some things in order to do so. It requires money to build, of course, but more to the point it requires a source of torque and speed. These are supplied by the motor, which in turn needs voltage and current from the battery. Both the motor and the battery cost money, but more importantly they need to be carried by the chassis: they become part of the load. A feedback loop is created: the chassis must carry all the weight, even that of the parts that power the chassis. A heavier battery might provide more energy to power the chassis, but is the extra power worth the heavier load?

In the following picture, each part chassis, motor, battery, and robot is shown as a box with ports on the left and right. The functionalities, or resources produced by the part are shown as ports on the left of the box, and the resources required by the part are shown as ports on its right.

(4.1) The boxes marked \(\Sigma\) correspond to summing inputs. These boxes are not to be designed, but we will see later that they fit easily into the same conceptual framework. Note also the ≤’s on each wire; they indicate that if box A requires a resource that box B produces, then A’s requirement must be less-than-or-equal-to B’s production. The

chassis requires torque, and the motor must produce at least that much torque.
To formalize this a bit more, let’s call diagrams like the one above co-design diagrams. Each of the wires in a co-design diagram represents a preorder of resources. For example, in Eq. (4.1) every wire corresponds to a resource type—weights, velocities, torques, speeds, costs, voltages, and currents—where resources of each type can be ordered from less useful to more useful.

In general, these preorders do not have to be linear orders, though in the above cases each will likely correspond to a linear order: $10 ≤ $20, 5W ≤ 6W, and so on.

Each of the boxes in a co-design diagram corresponds to what we call a feasibility relation. A feasibility relation matches resource production with requirements. For every pair (p, r) \(\in\) P × R, where P is the preorder of resources to be produced and R is the preorder of resources to be required, the box says “true” or “false”—feasible or infeasible—for that pair. In other words, “yes I can provide p given r” or “no, I cannot provide p given r.”

Feasibility relations hence define a function Φ: P × R → Bool. For a function Φ: P × R → Bool to make sense as a feasibility relation, however, there are two conditions:

1. If Φ(p,r) = true and p′ ≤ p, then Φ(p′,r) = true.
2. If Φ(p,r) = true and r ≤ r′, then Φ (p,r′) = true.

These conditions, which we will see again in Definition 4.2, say that if you can produce p given resources r, you can (a) also produce less p′ ≤ p with the same resources r, and (b) also produce p given more resources r′ ≥ r.

We will see that these two conditions are formalized by requiring Φ to be a monotone map P\(^{op}\) × R → Bool.

A co-design problem, represented by a co-design diagram, asks us to find the com- posite of some feasibility relations. It asks, for example, given these capabilities of the chassis, motor, and battery teams, can we build a robot together? Indeed, a co-design diagram factors a problem—for example, that of designing a robot—into intercon- nected subproblems, as in Eq. (4.1). Once the feasibility relation is worked out for each of the subproblems, i.e. the inner boxes in the diagram, the mathematics provides an algorithm producing the feasibility relation of the whole outer box. This process can be recursed downward, from the largest problem to tiny subproblems.

In this chapter, we will understand co-design problems in terms of enriched pro- functors, in particular Bool-profunctors. A Bool-profunctor is like a bridge connecting one preorder to another. We will show how the co-design framework gives rise to a structure known as a compact closed category, and that any compact closed category can interpret the sorts of wiring diagrams we see in Eq. (4.1).