Publications

Pointer variables have long been considered useful for constructing and manipulating data structures in traditional programming languages. This paper discusses how pointer variables can be integrated into one-way constraint models and indicates how these constraints can be usefully employed in user interfaces. Pointer variables allow constraints to model a wide array of dynamic application behavior, simplify the implementation of structured objects and demonstrational systems, and improve the storage and efficiency of constraint-based applications. This paper also presents two incremental algorithms---one lazy and one eager---for solving constraints with pointer variables. Both algorithms are capable of handling 1) arbitrary systems of one-way constraints, including constraints that involve cycles; and 2) editing models that allow multiple changes between calls to the constraint solver. These algorithms are also fault-tolerant in that they can gracefully handle and recover from formulas that crash due to programmer error. Constraints that use pointer variables have been implemented in a comprehensive user interface toolkit, Garnet, and our experiences with applications written in Garnet have proven the usefulness of pointer-variable constraints. Many large scale applications have now been implemented using these constraints.

We address the problem of coordinating the activities of a team of agents in a dynamic, uncertain, nonlinear environment. Bounded rationality, bounded communication, subjectivity and distribution make it extremely challenging to find effective strategies. In these domains it is difficult to accurately predict whether potential policy modifications will lead to an increase in the value of the team re- ward. Our Predictability and Criticality Metrics (PCM) approach errs on the side of safety, and advocates considering policy modifi- cations that are guaranteed to not harm the current policy, and uses simple metrics to choose from within that set a modification that increases the team reward. In the context of the DARPA Coordi- nators program, we show how the PCM approach yielded a system that significantly outperformed several competing approaches in an extensive independent evaluation.

The magnitude of data available on the web prompts the need for an easy to use query interface that enables users to integrate data from multiple web sources in an intelligent fashion. Past work in the area of databases has resulted in different query interface systems that simplify query formulation. While these approaches reduce the user's effort to compose queries, the user is still required to pick data sources to use and the interaction is not guaranteed to yield a non-empty result set. We introduce a novel approach that exploits the structure of the relational data source(s) to formulate a set of constraints. These constraints are used in conjunction with partial plans to produce an intelligent query interface that (a) does not require the user to know details about data sources or existing values (b) suggests valid inputs to the user (c) creates consistent queries that always return values. ACM Classification Keywords

The CAMERA project produced the SNAP (Schedules Negotiated by Agent-based Planners) flight scheduling software in experimental use by Harrier squadrons of Marine Air Group 13, stationed in Yuma, AZ; it was also fielded aboard the USS Bonhomme Richard, the USS Belleau Wood, the USS Pelleliu and the USS Essex that conducted operations in Iraq, Japan and Afghanistan. The CAMERA project also produced an open hybrid solver architecture that allows off-the-shelf solvers to be combined to solve a problem. Finally, it produced a family of market-inspired negotiation algorithms called MARBLES.

We investigate the problem of keeping the plans of mul- tiple agents synchronized during execution. We assume that agents only have a partial view of the overall plan. They know the tasks they must perform, and know the tasks of other agents with whom they have direct depen- dencies. Initially, agents are given a schedule of tasks to perform together with a collection of contingency plans that they can engage during execution in case execu- tion deviates from the plan. During execution, agents monitor the status of their tasks, adjusting their local schedules as necessary and informing dependent agents about the changes. When agents determine that their schedule is broken or that a contingency schedule may be better, they engage in coordinating plan changes with other agents. We present a "dynamic partial central- ization" approach to coordination. When a unit detects a problem (task delay, inability to perform a task), it will dynamically form a cluster of the critically affected agents (a subset of all potentially affected agents). The cluster will elect a leader, who will retrieve all task and contingency plan information from the cluster members and compute a solution depending on the situation.

Recent structured Peer-to-Peer (P2P) systems such as Distributed Hash Tables (DHTs) offer scalable key-based lookup for distributed resources. However, they cannot be simply applied to grid information services because grid resources need to be registered and searched using multiple attributes. This paper proposes a Multi-Attribute Addressable Network (MAAN) that extends Chord to support multi-attribute and range queries. MAAN addresses range queries by mapping attribute values to the Chord identifier space via uniform locality preserving hashing. It uses an iterative or single attribute dominated query routing algorithm to resolve multi-attribute based queries. Each node in MAAN only has O(logN) neighbors for N nodes. The number of routing hops to resolve a multi- attribute range query is O(log N + N × smin), where smin is the minimum range selectivity on all attributes. When smin = ε, it is logarithmic to the number of nodes, which is scalable to a large number of nodes and attributes. We also measured the performance of our MAAN implementation and the experimental results are consistent with our theoretical analysis.

Recent structured peer-to-peer (P2P) systems such as distributed hash tables (DHTs) offer scalable key-based lookup for distributed resources. However, they cannot be simply applied to grid information services because grid resources need to be registered and searched using multiple attributes. We propose a multiattribute addressable network (MAAN) which extends chord to support multiattribute and range queries. MAAN addresses range queries by mapping attribute values to the chord identifier space via uniform locality preserving hashing. It uses an iterative or single attribute dominated query routing algorithm to resolve multiattribute based queries. Each node in MAAN only has O(logN) neighbors for N nodes. The number of routing hops to resolve a multiattribute range query is O(logN+N times;smin), where smin is the minimum range selectivity on all attributes. When smin= #949;, it is logarithmic to the number of nodes, which is scalable to a large number of nodes and attributes. We also measured the performance of our MAAN implementation and the experimental results are consistent with our theoretical analysis.

Large NP-hard combinatorial resource allocation problems are best solved via approximation techniques which produce acceptable solutions in the time available. The best of such "good-enough/soon-enough" techniques handle large problems, run in distributed environments, adapt rapidly to changes to the problem while solving, and exhibit good anytime performance.

Ontologies define hierarchies of classes and attributes; they are meta-data: data about data. In the "traditional approach" to on- tology engineering, experts add new data by carefully analyzing others' ontologies and fitting their new concepts into the existing hierarchy. In the emerging "Semantic Web approach", ordinary users may not look at anyone's ontology before creating theirs - instead, they may simply define a new local schema from scratch that addresses their immediate needs, without worrying if and how their data may some day integrate with others' data. This paper describes WebScripter, a tool for trans- lating between the countless mini-ontologies that the "Semantic Web approach" yields. In our approach, ordinary users graphically align data from multiple sources in a simple spreadsheet-like view without having to know anything about ontologies. The resulting web of equivalency state- ments is then mined by WebScripter to help users find related ontologies and data, and to automatically align the related data with their own.

Ontologies define hierarchies of classes and attributes; they are meta-data: data about data. In the "traditional approach" to ontology engineering, experts add new data by carefully analyzing others' ontologies and fitting their new concepts into the existing hierarchy. In the emerging "Semantic Web approach", ordinary users may not look at anyone's ontology before creating theirs - instead, they may simply define a new local schema from scratch that addresses their immediate needs, without worrying if and how their data may some day integrate with others' data. This paper describes WebScripter, a tool for translating between the countless mini-ontologies that the "Semantic Web approach" yields. In our approach, ordinary users graphically align data from multiple sources in a simple spreadsheet-like view without having to know anything about ontologies. The resulting web of equivalency statements is then mined by WebScripter to help users find related ontologies and data, and to automatically align the related data with their own.

Historically, application and solution developers have confronted relatively simple and stable targeting problems. When designing applications and solutions, developers would identify and develop for a single dominant design point (or "sweet spot") - i.e., a targeted role (or business function), a targeted user, and a targeted hardware/software platform -- for the application. The Intemet and e-business transformation revolutions have made these targeting and .design problems much more challenging. Application and solution developers now confront several major and rapidly changing "variety challenges" that threaten their ability to develop, implement, and evolve high performance e-business solutions.

Synchronized punch-card displays are an interface technique to visualize tens of thousands of variables by encoding their values as color chips in a rectangular array. Our technique ties multiple such displays to a timeline of events enabling the punch-card displays to show animations of the behavior of complex systems. Punch-card displays not only make it easy to understand the high-level behavior of systems, but also enable users to quickly focus on individual variables and on fine-grained time intervals. This paper describes synchronized punch-card displays and shows how this technique is extremely powerful for understanding the behavior of complex multi-agent systems.

Marbles schemes are a family of cooperative and adaptive algorithms for distributed resource allocation problems. Long-term goals for these schemes are fault-tolerance and real-time performance in which a good timely solution is preferable to an optimal but too late solution. This paper reports work in progress where we compare the performance and analyze characteristics of different Marbles schemes and centralized solvers working on large scale and complex resource allocation problems.

One-way, dataflow constraints are commonly used in graphical interface toolkits, programming en- vironments, and circuit applications. Previous papers on dataflow constraints have focused on the design and implementation of individual algorithms. In contrast, this article focuses on the lessons we have learned from a decade of implementing competing algorithms in the Garnet and Amulet graphical interface toolkits. These lessons reveal the design and implementation tradeoffs for dif- ferent one-way, constraint satisfaction algorithms. The most important lessons we have learned are that (1) mark-sweep algorithms are more efficient than topological ordering algorithms; (2) lazy and eager evaluators deliver roughly comparable performance for most applications; and (3) con- straint satisfaction algorithms have more than adequate speed, except that the storage required by these algorithms can be problematic.

This paper presents an architecture for information retrieval agents in which each agent declaratively describes its domain, input, output, and user interface. A mediating piece of software can then assemble software agents for a given information retrieval task, and produce a single, unified user interface for that task from the individual agents' descriptions.

The central problem that we seek to address is: How does the average person communicate complex intent to an agent? A number of factors make this difficult. (For a more detailed discussion of these issues, see Neches, 92.) These include: limited understanding of the agent's capabilities, limited understanding of the language available to instruct the agent, limited ability to think and communicate in terms of algorithms, limited ability to analyze interactions between high-level requests. Our approach attempts to offer a sensible alternative. It is built upon two key ideas: (1) the Business Rule Manager, a set of mechanisms for providing constrained dialogues between user and system; and, (2) and a tiered interaction framework, a system that supports social evolution of communications by helping a community of users help each other develop a common language for talking with their agents. We present our approach to this problem in the context of DEALMAKER, an agent for selecting the best source of supply to fill orders. It receives requisitions for items in electronic form, queries a database of preferred vendors to determine possible sources of supply, and applies rules to filter and rank these sources according to policies established by contract managers.

Interface builders and multi-media authoring tools only support the construction of static displays where the components of the display are known at design time (e.g., buttons, menus). High-level UIMSs and automated designers support more sophisticated displays but are not easy to use as they require dealing explicitly with elaborate abstract concepts. This paper describes a GUI development environment, HandsOn, where complex displays of dynamically changing data can be constructed by direct manipulation. HandsOn integrates principles of graphic design, supports constraint-based layout, and has facilities for easily specifying the layout of collections of data. The system incorporates Programming By Example techniques to relieve the designer from having to deal with abstractions, and relies on a model-based language for the representation of the displays being constructed and as a means to provide information for the tool to reason about.

We present a system called DEALMAKER that allows users to specify policies that control selection among preferred suppliers in an automated purchasing system. The system gives users control over the automation by providing an expressive language and a convenient, easy- to-use user interface to specify the policies. The interesting and challenging aspect of the problem arises from the context in which the system operates. The end users are contract managers and buyers who are not trained in computers or programming. They enter their new supply contracts and define policy rules to control selection of the best contracts for buying requested parts. They act as their own knowledge engineers, even though the system is expected to have hundreds of rules for hundreds of contracts. The users interact with the system infrequently, perhaps only a few times a month when they begin or modify contracts, or change policies. Along with a moderate turnover rate of users, this makes it crucial that they can easily maintain correct rules with minimal training. In this paper, we describe a rule system and an interactive rule authoring tool designed to address the problems raised by this context. We believe these issues arise in most application domains where rule systems are put in the hands of the end users.

Many software applications solicit input from the user via a "forms" paradigm that emulates their paper equivalent. It exploits the users' familiarity with these and is well suited for the input of simple attribute-value data (name, phone number, ...). The paper-forms paradigm starts breaking down when there is user input that may or may not be applicable depending on previous user input. In paper-based forms, this manifests itself by sections marked "fill out only if you entered yes in question 8a above", and simple electronic forms suffer from the same problem -- much space is taken up for input fields that are not applicable. One possible approach to making only relevant sections appear is to hand-write program fragments to hide and show them. As an alternative, we have developed a form specification language based on a context-free grammar that encodes data dependencies of the input, together with an accompanying run-time interpreter that uses novel layout techniques for collapsing already-entered input fields, for "blending" input fields possibly yet to come, and for showing only the applicable sections of the form.

This paper presents a language for specifying the presentation of data in Web pages. The language is an extension of HTML that includes constructs for specifying how to present one or more instances of a given class of data, and constructs for tailoring the presentation to the features of the data, to information in user profiles and to the capabilities of the userÂ’s platform. We describe the architecture of the system, the features of the page specification language, and present examples of generated pages.

Current interface development tools cannot be used to specify complex displays without resorting to programming using a toolkit or graphics package. Interface builders and multi-media authoring tools only support the construction of static displays where the components of the display are known at design time (e.g., buttons, menus). This paper describes a presentation modeling system where complex displays of dynamically changing data can be modeled declaratively. The system incorporates principles of graphic design such as guides and grids, supports constraint-based layout and automatic update when data changes, has facilities for easily specifying the layout of collections of data, and has facilities for making displays sensitive to the characteristics of the data being presented and the presentation context (e.g., amount of space available). Finally, the models are designed to be amenable to interactive specification and specification using demonstrational techniques.

Research on model-based user interface development tools is about 10 years old. Many approaches and prototype systems have been investigated in universities and research laboratories around the world. This paper proposes a generic architecture for these tools, reviews the different approaches in light of this architecture, and discusses their progress towards the goals of increasing the quality and reducing the cost of developing interfaces. The paper closes with a discussion of challenges for future model-based development tools.

Currently, building a user interface involves creating a large procedural program. Model- based programming provides an alternative new paradigm. In the model-based paradigm, developers create a declarative model that describes the tasks that users are expected to accomplish with a system, the functional capabilities of a system, the style and requirements of the interface, the characteristics and preferences of the users, and the I/O techniques supported by the delivery platform. Based on the model, a much smaller procedural program then determines the behavior of the system. There are several advantages to this approach. The declarative model is a common representation that tools can reason about, enabling the construction of tools that automate various aspects of interface design, that assist system builders in the creation of the model, that automatically provide context sensitive help and other run-time assistance to users. The common model also allows the tools that operate on it to cooperate. Because all components of the system share the knowledge in the model, this promotes interface consistency within and across systems and reusability in the construction of new interfaces. The declarative nature of the model allows system builders to more easily understand and extend systems. This paper describes the modeling language of MASTERMIND, a model-based user interface development environment.

Model-based interface design can save substantial effort in building help systems for interactive applications by generating help automatically from the model used to implement the interface, and by providing a framework for developers to easily refine the automatically-generated help texts. This paper describes a system that generates hypertext-based help about data presented in application displays, commands to manipulate data, and interaction techniques to invoke commands. The refinement component provides several levels of customization, including programming-by-example techniques to let developers edit directly help windows that the system produces, and the possibility to refine help generation rules.

This paper describes Humanoid's approach for assisting designers in the construction of the presentation component of a user interface (discussions of Humanoid's support for other aspects of interface design appear in [Szekely92]). The approach represents a compromise between two main approaches used in other systems: power tools for designers, and automated designers.

Pointer variables have long been considered useful for constructing and manipulating data structures in traditional programming languages. This article discusses how pointer variables can be integrated into one-way constraint models and indicates how these constraints can be usefully employed in user interfaces. Pointer variables allow constraints to model a wide array of dynamic application behavior, simplify the implementation of structured objects and demonstrational systems, and improve the storage and efficiency of constraint-based applications. This article presents two incremental algorithms --- one lazy and one eager --- for solving constraints with pointer variables. Both algorithms are capable of handling (1) arbitrary systems of one-way constraints, including constraints that involve cycles, and (2) editing models that allow multiple changes between calls to the constraint solver. These algorithms are fault tolerant in that they can handle and recover gracefully from formulas that crash due to programmer error. Constraints that use pointer variables have been implemented in a comprehensive user interface toolkit, Garnet, and our experience with applications written in Garnet have proven the usefulness of pointer variable constraints. Many large-scale applications have been implemented using these constraints.

Model-based interface development is a new paradigm for developing interfaces that offers solutions to the main shortcomings of current tools. This paradigm is based on constructing a declarative description of how an interface should look and behave (model), and using the description to control the execution of an interface. This paper briefly summarizes the main shortcomings of interface development tools used today, discusses the main elements of the model-based approach, and closes with a discussion of the state of the art and the challenges that lie ahead.

One of the strongest limitations of knowledge-acquisition metatools---tools that automate the development of knowledge-acquisition tools---is that the interface-design knowledge employed by such metatools to produce domain-specific knowledge-acquisition tools is not explicit and cannot be used by other metatools. Therefore, the usefulness of a metatool is restricted to its own implementation environment. A possible solution to this problem is the definition of a shareable ontology of knowledge-acquisition tools that represents explicitly the relevant knowledge of tool design and development. We take the position that the design of knowledge-acquisition tools is similar to the design of user interfaces, and that an ontology of knowledge-acquisition tools is a special case of an interface ontology. We propose that a shareable interface ontology can be defined by analyzing interface ontologies used in model-based user-interface development systems, and by resolving differences and conflicts among the ontologies---a process called model alignment. We present the initial results of a model alignment for the interface ontologies of two user-interface development systems: SHELTER and Mecano. We also show how the resulting shareable interface ontology underpins a framework in which each system can be applied to different parts of the process of generating a single, domain-specific knowledge-acquisition tool, thus creating a generation of metatools useful across multiple implementation environments.

Today's interface design tools either force designers to handle a tremendous number of design details, or limit their control over design decisions. Neither of these approaches taps the true strengths of either human designers or computers in the design process. This paper presents a human-computer collaborative system that uses a model-based approach for interface design to help designers search the design space effectively and construct executable specifications of application user interfaces. This human-in-the-loop environment focuses human designers on decision making, and utilizes the bookkeeping capabilities of computers for regular and tedious tasks. We describe (a) the underlying modeling technique and an execution environment that allows even incompletely-specified designs to be executed for evaluation and testing purposes, and (b) a tool that decomposes high-level design goals into the necessary implementation steps, and helps designers manage the myriad of details that arise during design.

We describe MASTERMIND, a step toward our vision of a knowledge-based design-time and run-time environment in which human-computer interfaces development is centered around an all-encompassing design model. The MASTERMIND approach is intended to provide integration and continuity across the entire life cycle of the user interface. In addition, it facilitates higher quality work within each phase of the life cycle. MASTERMIND is an open framework, in which the design knowledge base allows multiple tools to come into play and makes knowledge created by each tool accessible to the others.

Interface builders only support the construction of the menus and dialogue boxes of an application. They do not support the construction of interfaces of many application classes (visualization, simulation, command and control, domain-specific editors) because of the dynamic and complex information that these applications process. HUMANOID is a model-based interface design and construction tool where interfaces are specified by building a declarative description (model) of their presentation and behavior. HUMANOID's modeling language provides simple abstraction, iteration and conditional constructs to model the interface features of these application classes. HUMANOID provides an easy-to-use designer's interface that lets designers build complex interfaces without programming.

HUMANOID is a user interface design tool that lets designers express abstract conceptualizations of an interface in an executable form, allowing designers to experiment with scenarios and dialogues even before the application model is completely worked out. Three properties of the HUMANOID approach allow it to do so: a modularization of design issues into independent dimensions, support for multiple levels of specificity in mapping application models to user interface constructs, and mechanisms for constructing executable default user interface implementations from whatever level of specificity has been provided by the designer.

Graphical tools are increasingly using constraints to specify the graphical layout and behavior of many parts of an application. However, conventional constraints directly encode the objects they reference, and thus cannot provide support for the dynamic runtime creation and manipulation of application objects. This paper discusses an extension to current constraint models that allows constraints to indirectly reference objects through pointer variables. Pointer variables permit programmers to create the constraint equivalent of procedures in traditional programming languages. This procedural abstraction allows constraints to model a wide array of dynamic application behavior, simplifies the implementation of structured object and demonstrational systems, and improves the storage and efficiency of highly interactive, graphical applications. It also promotes a simpler, more effective style of programming than conventional constraints. Constraints that use pointer variables are powerful enough to allow a comprehensive user interface toolkit to be built for the first time on top of a constraint system.

This paper describes a template-basedmethod for construct- inginteractivedisplayswiththebuilding-blocks (widgets1 provided in a user interface toolkit. Templates specify how to break down complex application objects into smaller pieces, specify the graphical components (widgets) to be used for displaying each piece, and specify their layout. Complex interfaces are constructed by recursively applying templates, thus constructing a tree of widgets to display a complex application object. The template-basedmethod is more general than the interactive, WYSIWYG interface builders in that it can specify dynamic displays for applica- tion data that changesat run time. The template-based method also leads to more consistent, extendable and modi- fiable interfaces.

The user interface building blocks of any User Interface Management System (UIMS) have built-in assumptions about what information about application programs they need, and assumptions about how to get that information. The lack of a standard to represent this information leads to a proliferation of different assumptions by different building blocks, hampering changeability of the user interface and portability of applications to different sets of building blocks. This paper describes a formalism for specifying the information about applications needed by the user interface building blocks (i.e. the UIMS/Application interface) so that all building blocks share a common set of assumptions. The paper also describes a set of user interface building blocks specifically designed for these standard UIMS/Application interfaces. These building blocks can be used to produce a wide variety of user interfaces, and the interfaces can be changed without having to change the application program.

One of the most difficult aspects of creating graphical, direct manipulation user interfaces is managing the relationships between the graphical objects on the screen and the application data structures that they represent. Coral (Constraint-based Object-oriented Relations And Language) is a new user interface toolkit under development that uses efficiently-implemented constraints to support these relationships. Using Coral, user interface designers can construct interaction techniques such as menus and scroll bars. More importantly, Coral makes it easy to construct direct-manipulation user interfaces specialized to particular applications. Unlike previous constraint-based toolkits, Coral supports defining constraints in the abstract, and then applying them to different object instances. In addition, it provides iteration constructs where lists of items (such as those used in menus) can be constrained as a group. Coral has two interfaces: a declarative interface that provides a convenient way to specify the desired constraints, and a procedural interface that will allow a graphical user interface management system (UIMS) to automatically create Coral calls.

The presentation of an application program specifies how the data and operations provided by an application are presented to users. Most traditional techniques for implementing presentations lead to unstructured, unmodular implementations that are hard to construct and change. We present a model of presentation that identifies the dependencies between the presentation and functionality portions of an application. Based on this model, we show how several implementation techniques can be used to construct presentations in a modular way.

Constructing graphical user interfaces for interactive applications is a difficult and time consuming task, typically requiring extensive programming and experimentation with many prototypes. Thus, the ability to package portions of the specification of user interfaces into components that can be reused in the construction of many interfaces, and the ability to change an application's user interface without impacting the implementation of the functionality are crucial. These abilities can be realized in the measure that the dependencies between the implementation of an application's functionality and the user interface can be minimized.

User interface management systems (UIMSs) provide user interfaces to application systems based on an abstract definition of the interface required. This approach can provide higher-quality interfaces at a lower construction cost. In this paper we consider three design choices for UIMSs which critically affect the quality of the user interfaces built with a UIMS, and the cost of constructing the interfaces. The choices are examined in terms of a general model of a UIMS. They concern the sharing of control between the UIMS and the applications it provides interfaces to, the level of abstraction in the definition of the information exchanged between user and application, and the level of abstraction in the definition of the sequencing of the dialogue. For each choice, we argue for a specific alternative. We go on to present COUSIN, a UIMS that provides graphical interfaces for a variety of applications based on highly abstracted interface definitions. COUSIN's design corresponds to the alternatives we argued for in two out of three cases, and partially satisfies the third. An interface developed through, and run by COUSIN is described in some detail.

Currently available interactive command interfaces often fail to provide adequate error correction or on-line help facilities, leading to the perception of an unfriendly interface and consequent frustration and reduced productivity on the part of the user. The COUSIN project of Carnegie-Mellon University is developing command interfaces which appear more friendly and supportive to their users, using a form-based model of communication, and incorporating error correction and on-line help. Because of the time and effort involved in constructing truly user-friendly interfaces, we are working on interface system designed to provide interfaces to many different application systems, as opposed to separate interfaces to individual applications. A COUSIN interface system gets the information it needs to provide these services for a given application from a declarative description of that application's communication needs.