Research Abstracts - 2007

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.bitrate = source.bitrate
    solution.frequency = source.frequence
    solution.stream_title = source.stream_title
    solution.wattage = sink.wattage
  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 properties of a solution. The properties describe to the planner the estimates of the Technique’s performance parameters 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. Our current planner can respond to voice commands (both in Chinese and English) to play movies and music [4], adapting itself as necessary to the language the user utters and the availability of runtime resources.

Current efforts are directed toward re-evaluating the semantics of Goals and Techniques:

• Technique Evaluation
  Previous implementations of the chose between Techniques based on a satisfaction provided by each Technique. We are moving to a new model where Techniques only provide properties of the solutions that they are creating. In turn, the Planner synthesizes a satisfaction value from the Technique's properties.
• Dependency Tracking
  The existing Technique interpretation engine evaluates the phases of Techniques in text order and keeps track of the property dependencies in order to "rollback" when properties change. For future techniques, we plan on changing the Planner to work solely with dependencies, allowing Techniques stages to run in data-flow order, and to use dependency information to more efficiently schedule Techniques for execution.
• Heuristic Plan Exploration
  The Planner implementation used in the JustPlay system searches only a small number of the Technique and Goal combinations available to it. We plan on adding mechanism to the Planner to track the properties of individual combinations and use this information to intelligently expand its search space.

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).