Symposium on Abstraction, Reformuation, and Approximation

Last Saturday, I finished my second conference in a week. This one is SARA (Symposium on Abstraction, Reformulation, and Approximation).

The subject matter ranges from constraint programming to search/planning in AI to the mathematization of related topics.

For quite a while I've wondered why constraint programming hasn't caught on as an problem solving tool. Mainly, I think, it's been the lack of CP systems that are written for non-CP researchers to use. A great deal of work has been going on in CP. There are now a great many solvers, with more being written every day. But there are no CP systems that have interfaces that someone with a real problem would want to use. Also, Integer Programming and related disciplines have established themselves in the engineering community and solve a great many problems already. Two of the invited papers suggest that this will change. (I hope so.) The first was about work on a higher level language called ESSENCE.

It allows one to write in a very high-level language in expressing one's problem. The ESSENCE processor will translate that to a form suitable to one of the solvers, which are more and more powerful these days. For example, here's how the n-queens problem would be expressed.

given n : int(1...)
letting INDEX be domain int(1..n)
find Arrangement : INDEX -> (bijective) INDEX
such that 
  forall q_1 : INDEX . 
    forall q_2 : INDEX . 
      |Arrangement(q_1) - Arrangement(q_2)| != q_2-1

The second talk (by John Hooker) was about a framework for integrating CP, OR, and other constraint and optimization technologies.

The third talk was about real-time planning--also a very interesting talk in which A* has been extended so that one can use it in real time. A great deal of the motivation was to make planners in computer games more effective. The world of computer game is driving a lot of work in both AI and graphics.

In the context of the conference, Abstraction means grouping elements together (at least initially) to get a simpler problem. The Real-time search talk used abstraction by grouping search nodes together into super nodes to find an overall plan, which would then be extended to a concrete plan. This isn't new. The work that was reported made it real time and added refinements.

Reformulation means re-writing from one language to another. The first talk is an example in that the higher level language is re-written into a lower level language (of some solver). It's much like compilation theory.

Approximation is not numerical. An example is finding a boolean expression that is an approximation of the boolean expression that you want to solve but that is easier to solve.

One of the things that struck me is how dense the literature is in computer science these days. So many people have studied so many topics that we now have a fairly deep and wide literature on a great many topics. It's quite impressive -- and very different from the way the world was only 2-3 decades ago. Most of you probably don't remember that period. But for those of us who are old enough to remember, the world is very different.