Research Abstracts - 2006

Goal and Technique-based Scripting

Justin Mazzola Paluska, Hubert Pham, Umar Saif, Chris Terman & Steve Ward

Overview

We propose a system semantic in which specification-like Goals and Techniques to satisfy those Goals are formalized as formal language constructs. Goals provide an abstraction to state what a user wants or what a program requires in order to complete some task. Techniques are code objects that can satisfy some Goals.

The Goals runtime system hides the complexity of how each Goal is satisfied. Given a high-level Goal, the runtime system automatically explores the available Techniques, dynamically composes an implementation from the resources available in the user environment that the Techniques request, and, if necesary, successively revises the implementation to sustain the user Goal.

Rationale

As a tiny example, consider a user in a videoconference with a colleague as he wanders about a well equipped campus. As he moves from one room to another, his video switches from the small LCD display of his handheld to a wall-mounted plasma screen as the latter comes into view. Similarly, networking technologies might shift between 802.11b and CDMA depending on resource availability, and video may degrade or disappear altogether as communication bandwidth warrants.

Such behavior necessarily requires frequent reevaluation of available alternatives, as well as heuristic compromises to best address the user's needs with imperfect resources. Conventional techniques for constructing applications, in which top-level function is decomposed into statically-partitioned subfunctions each affixed to a particular API, makes such adaptation exceedingly difficult to program. If there is a change in available resources, it is often insufficient simply to reconsider how to implement the function specified at each API: it is necessary to reconsider the reason that API was selected, and whether an alternative function and API has now become more appropriate.

Approach

By formalizing Goals and Techniques, we create a basic framework on which we can guide the automatic construction of a component-based system. Semantically, Goals are similar to generic procedure calls: they involve a named generic service (the Goal name) as well as an arbitrary number of typed parameters. Thus, PlayMusic("jazz") might be a high-level Goal whose satisfaction requires the system to play jazz music the user likes using whatever resources are available.

Unlike procedure calls, however, Goals are disembodied from any block of code to be invoked during their execution. Rather, the system approaches the resolution of a Goal by searching for one or more Techniques, each of which constitutes a recipe for resolving a class of Goals. Each Technique specifies a pattern to be matched against a candidate Goal, optional subgoals that must be satisfied for it to proceed, and code to be run in order to cause an incoming Goal to be satisfied once the specified subgoals have been achieved. This semantic is reminiscent of Prolog and related logic languages of the 80s, although the implementation technology surrounding it is quite different.

Following implementation, however, the Goal tree persists as a record of the logic by which implementation choices were made, so long as the Goal remains active. As network connections break or new resources become available, the Goal tree is reevaluated and alternative implementation choices may be made and implemented in real time.

Each Technique is embodied as a script that plays an active role during the resolution process, in effect offering to satisfy the stated Goal so long as certain constraints (expressed as subgoals) are met. Typically the runtime will create and explore a Goal tree, heuristically choosing the most satisfactory branch of that tree to be implemented.

Technique Scripts

An individual Technique is a mix of declarative and imperative code that constructs a Solution for a single parameterized Goal. For example, a Technique for the PlayMusic Goal may be:

to PlayMusic(genre):
  via MP3s:
  subgoals:
    source = MusicStream(genre,
                         format="MP3")
    control = VolumeControl()
    sink = AudioSink(format="MP3")
  eval:
    solution.satisfaction = (source.satisfaction + 
                             sink.satisfaction) / 2
  exec:
    connect(source, sink)
    control.set_speaker(sink)
  update sink from old:
    disconnect(source, old)
    connect(source, sink)

The first few lines specify what Goal the Technique satisfies, as well as a name for the Technique for debugging purposes. The rest of the Technique is the Technique body, itself divided into stages:

• A subgoals stage that declares the subgoals of the Technique.
• An eval stage that investigates the results of the subgoals and synthesizes how well the Technique can satisfy its own goal given the Planner's choice of subgoal implementations.
• An exec stage that contains the code to run if the Planner chooses the Technique for execution.
• An update stage that contains code to swap out the sink subgoal for another one if necessary.

Technique code is not run all at once. Instead, the runtime environment executes and re-executes stages as necessary to build a Goal tree, evaluate what Techniques form the best implementation in the current environment, execute the best, and the monitor the chosen Techniques.

Progress and Plans

Early prototype Goal-oriented planners[2, 3] addressing toy problems in simple ubiquitous computing environments[1] have been demonstrated. Current efforts are directed toward generalization of the approach to other application areas, including the JustPlay environment[4]; evaluating the approach in the context of more realistic applications; and exploring user preferences in the context of a Goal-oriented system.

Funding

This project has been funded by the Oxygen project, CMI, the DARPA ACIP program, and the Quanta/CSAIL T-Party project.

References:

[1] Umar Saif, Hubert Pham, Justin Mazzola Paluska, Jason Waterman, Chris Terman, and Steve Ward, A Case for Goal-oriented Programming Semantics. In System Support for Ubiquitous Computing Workshop at the Fifth Annual Conference on Ubiquitous Computing (UbiComp '03).

[2] Early Goal-oriented concept demo, available at http://ward.lcs.mit.edu/curl/goalsdemo/index.html.

[3] Justin Mazzola Paluska. Automatic Implementation Generation for Pervasive Applications. Masters of Engineering Thesis, MIT, June 2004.

[4] Justin Mazzola Paluska, Hubert Pham, Umar Saif, Chris Terman, and Steve Ward, Reducing Configuration Overhead with Goal-oriented Programming. In Proceedings of the Fourth IEEE International Conference on Pervasive Computing and Computation Workshops (PerCom '06).