Supple Project at the University of Washington

Earlier this week I took a break from my usual routine and took a drive out to the University of Washington for a morning meeting. My destination was the Department of Computer Science & Engineering, headquartered in the new (and spectacular) Paul G Allen Center for Computer Science and Engineering.

The day before my meeting I had received a brief email from Kiera Henning. She told me that her group was building an application around AWS, and that I would probably find it interesting.

I entered the building, met Kiera, and she took me up to their lab, where I met her co-worker, Krzysztof Gajos.

Krzysztof and Kiera (and several others that I did not meet) are working on a project called Supple. Supple is intended to move the state of the art in user interface design past the “one size fits all” model. The goal is to start with an abstract description and end up with an interface suited to a display of any size, ranging from a compact cell phone all the way up to the Apple Cinema display that Krzysztof had on his desk.

In a nutshell, the input to Supple is a functional specification of the user interface, information about the display device, and information about the user. The output is a dynamic, fully customized user interface layout. The layout will be comprised of one or more windows, with a number of user interface widgets on each window, laid out in a pleasing and logical fashion. It is important to know that the output can consist of more than one window. On a large display, Supple can create a “flat” layout, putting many widgets in the window. On a more constrained display, Supple will automatically create a hierarchy consisting of a main window and child windows.

The user interface is specified in abstract form using a tree structure with the application at the root. Child nodes are then used to specify logical groups of values and the values themselves. The values can be basic types (integers, strings, and so forth), constrained basic types (an integer within a fixed range, or a string chosen from a list of values) , vectors, containers, actions, and optional hints. The constraints are an important aspect of the model because they allow Supple to do a better job of mapping the value into the most appropriate widget.

The device model consists of a set of constraints, a widget library representing the repertoire of functionality available for the device), and a “cost function” for each widget. The cost function expresses the amount of user effort needed to make a change to the widget.

The user model is still under development, and we didn’t talk too much about it. As described in one of the Supple papers, the user model includes traces derived from actual use of the interface.

The layout algorithm takes the functional specification and assigns widgets and windows to it. It essentially creates a gigantic search space of all possible widget and window assignments and then applies artificial intelligence techniques to optimize the tree for the best possible solution, as expressed by a cost function. The cost function is rather complex; it takes in to account a number of factors, including the effort needed to navigate between widgets and the actual pattern of interface usage as derived from the trace data collected from the user. In plain English, this means that the system has the information it needs to ensure that the most frequently used widgets, and the widgets used in conjunction with each other, are the ones that are the most readily accessible. That’s pretty cool.

The real effort here is in minimizing the search space and quickly coming up with the best possible solution. Any real user interface will have billions and billions of possible solutions; doing a full layout and computing the resulting cost for each one would be prohibitively expensive. Krzysztof explained to me that he is able to prune the search in a very opportune manner, eliminating many solutions which have no chance at all of being the best one. He called this an “A* Search”.

So, how does it all work in practice? Really well! They showed me a Java implementation which uses the Java Swing widget library. Complex UI’s with dozens of elements were laid out in a matter of a few seconds. This is perfectly reasonable, and I am sure that it will get even faster in the future. Some applications will do UI layout at startup time, others will do it on the fly, and others will probably be shipped from the factory with some starter layouts.

The fact that Supple can generate a fresh UI layout more or less in real time opens the door to some new types of application behavior. As we enter into the era of ubiquitous computing, interfaces which can morph into the form appropriate for a wide variety of devices will become increasingly important. For example, I generally read my mail at home using Thunderbird. Supple would allow this same application to present an appropriate user interface when I need to get my mail from my Motorola cell phone, my flat-panel TV, or from a web browser. At this point, applications need to be able to work well on devices that didn’t actually exist at the time the application was designed and built. A late-binding, dynamic approach as exemplified by Supple is going to be an essential aspect of many types of applications in the future.

We also talked about some ways in which a Supple-based system could help to blur the boundaries between applications. For example, this morning I needed to copy a picture off of my cell phone (via Bluetooth), to my PC, tweak the size, and then upload it to this blog. I had to use tiny parts of four different applications. A more powerful system would be able to see that sequence of events and create a workflow or custom application to do all of this in one fell swoop.

So what happens next? Supple will be released as a toolkit in the near future. They will also release it as a web service; this makes a whole lot of sense. Using such a “layout service” an application running on a small device without a whole lot of memory or computational power can make a call which says “create an optimized layout for my display”.

It was wonderful to get a glimpse of the future, and I look forward to watching this technology as it matures and grows in breadth and scope.

More information can be found at the main Supple site.