After seeing David Spivak’s talk on operads for design at FMCS 2015, I immediately thought of Brooks’ subsumption architecture. The subsumption architecture was one of the first formalisms for programming mobile robots—simple, insect-like robots capable of feeling their way around without needing to plan or learn. Operads, on the other hand, are certain objects in category theory used to model “modularity”, e.g. situations where multiple things of a sort can be combined to form a single thing of the same sort.
I’d like to formalize subsumption using operads.
But why would anyone want to formalize an derelict robotics architecture with high-falutin’ mathematics?
The answer is simple. It’s not that subsumption on its own is important (though it is) or that it requires formalizing (though it does). What I’d really like to understand is how operads give domain-specific languages (and probably much more) and whether categories are the right way to pose problems that involve combining and stacking many such DSLs—think of a robot that can move, plan, and learn all at the same time—which, for lack of a better term, I will call hard integration problems.
(The rest of this post is currently in process! I will come back throughout the fall and update it.)
The psychologist Robert Sternberg once said of wisdom: “practical wisdom is domain-specific […] but wisdom can exist on a general level as knowing the limits of this domain-specific wisdom.” But how can we study the limits of this domain-specific wisdom?
I think we can start by formalizing what we mean by domain-specific knowledge. I’d like to focus on something really simple and dumb: the idea of “domain-specific” is that there is a domain: a closed-off, special area where some kind of unique logic or principle applies. The operad gives the architecture of that domain—a suite of tools for thinking about and comparing the particular algebras over the operad, i.e. the particular examples of objects in that domain.
Example: matrix multiplication vs tensor product vs using a simple 3-box wiring diagram.
Example: a man walking through a series of rooms: this is an algebra over the same operad! 
Example: context-free grammars, e.g. postal address = {name = {first, m, last}, address, zip}. This is a “free operad”.
Example: Matriach at MIT.
Example: a diagram in the operad gives morphisms in a cospan category (e.g. of finite sets). Rel : U \to Set, then 
An easy integration problem is…
% Operads were originally developed in algebraic topology by Peter May to express the natural, many-to-one operations in iterated loop spaces. [Do we need the history or is that a distraction?]
Why subsumption?
- Subsumption is distinguished for being one of the first reactive architectures. Reactive, e.g. “pre-wired”. Sensors project directly to motors, without intervening abstraction.
- It’s a platform on which we can build more complicated faculties like planning, inference, and learning.
- Subsumption is cheap compared to deliberative, sequential, symbolic architectures like Sense-Plan-Act (Shakey).
- Distributed control leads to graceful degradation.
- The key to subsumption is arbitration. Higher priority tasks, when flagged “true”, subsume lower priority tasks.
Why operads for subsumption?
- Better theoretical insight into subsumption and what it means to be “reactive”.
- Want new design tools for subsumption, that will help us handle the combinatorial explosion as we add behaviors.
- Use category theory to relate it to other methods in AI (e.g. symbolic logic, ML, KR), e.g. we want a good theory of how to “add in” subsumption to some other architecture when reactivity is needed.
What are operads?
- The tree operad
- May’s box operad
- Spivak’s wiring diagrams
- Despite the pictures, fundamentally an algebraic construct
- Define colored operads
- Intuition from Massey products and homotopical algebra, e.g. this survey
Construct an example of a subsumption diagram, e.g. the classic one for Genghis, as described here.
- Composed of augmented finite state machines (augmented with timer, so there needs to be a notion of time or at least recurrence—see ideas from operads for functional reactive programming, and FRP + robots.)
- Each AFSM has input signals and output signals. Like a neuron, it “activates” (i.e. sends an output signal) when a certain threshold is passed, given by the sum of input signals.
- Suppression gates (and task priority)
- Inhibition gates
- Code it up in a robot simulator, e.g. Simbad.
Define the colored operad for this diagram. Actually, better yet, generate the operad in OPL.