Constraint programming has an amazing variety of applications. To illustrate this, I’ve come up with “The Application Game”. It is a very simple game: you type “constraint satisfaction problem” and some other random topic into Google search and see if you come up with an application of constraint satisfaction to that topic.

I first tried “bananas”. Unfortunately “bananas” returns too many references to the classic “monkey and bananas” problem. I assumed many of those did not actually apply constraint satisfaction to that problem, and even if they did, I was looking for a “real world” application.

Nevertheless the resulting hits provided some interesting diversions. I encountered this piece in Stanford’s “digital stacks” by Rodney Brooks (long before Roomba presumably) about Fikes’ REF-ARF. REF-ARF plays an interesting role in the history of constraint saatisfaction. It provides an example of constraint satisfaction in the very first issue of the Artificial Intelligence journal. In his piece on REF-ARF, Brooks says that the type of problem of which the monkey and bananas problem is an example “cannot be stated as a boolean constraint satisfaction problem because the length of the sequence of operators q is not specified”, in other words because the length of the plan required to solve it is not given, so REF-ARF’s heuristic search component must be used instead. Of course, later this “constraint” in applying constraint satisfaction to planning was overcome by simply using successively longer planning horizons. This is an example of the type of approach (see “iterative deepening“) that is easily dismissed as impractically wasteful, but can turn out to be worth investigating.

And then there was this: BANANAS: Automated design and autonomous control of hybrid solver cooperations.

However, I eventually gave up on “bananas” and tried googling for something more timely: “constraint satisfaction problem” and “COVID”. I quickly found Validating Optimal COVID-19 Vaccine Distribution Models.

I’m sure there are other COVID-related applications; I know of at least one. I didn’t conduct an exhaustive search, but I couldn’t resist looking at a just few more Google hits, and almost immediately turned up this: Constraint-Checking Editor for Procedure Tracking (ConCEPT). Now this is from 2013 and so, of course, has nothing to do with COVID. It is related instead to operational procedures for manned space operations! This is cool, though not totally unexpected: I myself once did some work with NASA. The principal investigator on the ConCEPT project was Mark Boddy, whom some of you may know: for example, Mark was co-chair of ICAPS 2007. Mark is co-owner and Chief Scientist at Adventium Labs. Here is a paper on ConCEPT from the Workshop on AI in Space at the 2015 International Joint Conferences on Artificial Intelligence. I find particularly interesting its relationship to maintenance, which I think is an understudied area. I did some work a while ago on Maintaining constraint-based applications with Tomas Nordlander and Rick Wallace.

So, isn’t The Application Game fun? 🙂 Try it yourself, and I encourage you to report your experiences in the Comments.