Back in 2004 the Boston Globe newspaper ran a story about “the most influential academic discipline you’ve never heard of”. What was the discipline? Operations research.

Operation everything

It stocks your grocery store, schedules your favorite team’s games, and helps plan your vacation. A primer on the most influential academic discipline you’ve never heard of.

This is rather ironic for those of us in Constraint Programming, since CP deals with many of the same applications as Operations Research, and is, if anything, less well known.

Part of the problem unquestionably lies in the name. “Operations Research”, what is that? The study of hospitals? And the alternative, “Mathematical Programming”, is even worse. Is it mathematics? Is it coding? The only worse name for a field? “Constraint Programming”.

I once had a fellow from a company that I was trying to interest in working with my lab tell me he liked the idea, but ask me if there was some other name for what I did, because “constraints” had such a negative connotation, it turned other people in his company off. Of course, we do have some very positive terms associated with the field: “satisfaction”, “relaxation”, “optimization”. But if I said “I use relaxation for optimal satisfaction”, people might think I was some kind of new age guru.

Indeed even “optimization” is an imperfect standard bearer. I once had a fellow at a commercially-oriented conference tell me that “optimization” could turn his potential customers off. Astonished, I asked why, and he explained that they worried that it meant that the computer would make all the decisions and they would be cut out of the loop. Of course, it doesn’t have to mean that, but perhaps such fears help to explain the current popularity of terms like “human-centred” and “human-aware” as modifiers to “Artificial Intelligence”.

In any case, if we are to compete with such media-friendly terms as “artificial intelligence” and “deep learning” we need to work at getting the message out about what we can do. Actually Operations Research is currently doing a pretty good job of that for their field. See “O.R. & Analytics Impact Everything” at the INFORMS website, and the INFORMS Success Stories.

The ACP has its Success Stories as well, of course, and there are other resources, but we can always do more. I’ve started work on a new page, Sample Applications of Constraint Satisfaction, to make a small contribution towards “getting the word out”.

I had so much fun with The Application Game that I decided to play again googling “constraint satisfaction problem” and “refrigerator”. I came up with “Service robot planning via solving constraint satisfaction problem“.

The problem of demographic shifts towards the elderly is deteriorating, as the relative number of caregivers is insufficient to provide the support required for their wellbeing, which is further aggravated by the increasingly hectic lifestyle. Service robot is getting more prominent as a possible solution. Robot manipulation and mobility is an important field, but they also require high level planning for these minute actions in order to provide ample support. Automatic service composition, contributed significantly by web services, offers the necessary technology for the task. Robot planning problem can be solved by representing it as constraint satisfaction problem (CSP) due to it being able to support loose binding of services and variables of wider domain. 

What does this have to do with refrigerators?

Given a certain goal, planner module will compose a sequence of plans for the robot to execute such that after the plans are completed, the goal is achieved. For example, given that the goal is to place a canned soft drink in the fridge and that all cabinet needs to be closed, the robot will first find where the soft drink is. If there is one that happens to be in the kitchen cabinet, the robot will approach it, open the cabinet and pick up the soft drink, and then close it. It will subsequently approach and open the fridge, after which it will place the canned drink before closing it. No prior programming is required for the plan.

Ok, tenuous, but this paper illustrates an interesting point.

The paper is published in the ROBOMECH Journal. Its authors are in a Graduate School of System Design, not a computer science department. The closest it comes to referencing the CP literature seems to be a 2008 paper by De Moura and BjØrner on Z3: An efficient SMT solver, in the International Conference on Tools and Algorithms for the Construction and Analysis of Systems and a 2014 paper by Georgievski and Aiello, “An Overview of Hierarchical Task Network Planning” in ArXiv.

In other words, your typical attendee at the CP conference or reader of the Constraints journal might well not have run across this paper. I believe there are many such papers. In a way, this is a positive sign, of the degree to which our “baby” has moved out into the world. Still, the more we are aware of applications of constraint satisfaction the better. The more that people applying constraint satisfaction are aware of the broader body of work in our field the better. The more that people in general are aware of the breadth of applications of constraint satisfaction the better. An application like this one to service robots could help interest students in the field or convince funding agencies of our “impact”. It could suggest new collaboration opportunities or suggest new directions for basic research.

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.