In this paper, we report our findings on the impact of providing users with varying degrees of control in an automated interactive scheduling system. While automated scheduling techniques such as constraint optimization have been widely adopted in a variety of scheduling applications, such applications require that users relinquish a certain amount of control to the system. The implications of such a shift in control are not clear for people who oversee the scheduling of human activities, for example, case managers scheduling patient appointments in hospitals and clinics. We asked our participants to use a working prototype system for clinic scheduling to complete a series of scheduling problems that we designed. We varied the size of the problems---i.e., the number of patients to be scheduled---and the style of interaction in ways that are associated with different degrees of user control. We recorded standard usability metrics and conducted post-task written surveys and interviews. Our results suggest that although maintaining full user control decreases efficiency as the problem becomes larger, the participants still preferred to have full user control in completing scheduling tasks. We end with design implications in supporting users' increased acceptance of automated scheduling systems.

In this work, we propose a new and efficient approach to the floorplan repair problem, where violated design constraints are satisfied by applying small changes to an existing rough floorplan. Such a floorplan can be produced by a human designer, a scalable placement algorithm, or result from engineering adjustments to an existing floorplan. In such cases, overlapping modules must be separated, and others may need to be repositioned to satisfy additional requirements. Our algorithmic framework uses an expressive graph-based encoding of constraints which can reflect fixed-outline, region, proximity and alignment constraints. By tracking the implications of existing constraints, we resolve violations by imposing gradual modifications to the floorplan, in an attempt to preserve the characteristics of its initial design. Empirically, our approach is effective at removing overlaps and repairing violations that may occur when design constraints are acquired and imposed dynamically.

We present a new algorithm for active learning embedded within an interactive calendar management system that learns its users' scheduling preferences. When the system receives a meeting request, the active learner selects a set of alternative solutions to present to the user; learning is then achieved by noting the user's preferences for the selected schedule over the others presented. To achieve the goals of presenting solutions that meet the user's needs while enhancing the preference-learning process, we introduce a new approach to active learning that makes online decisions about the technique to use in selecting the schedules to present in response to each meeting request. The decision is based on the entropy of the available options: a highly diverse set of possible solutions calls for a selection technique that chooses instances that are different from one another, maximizing coarse-grained learning, whereas a set of possible solutions containing little diversity is met with a selection strategy that promotes fine-grained learning. We present experimental results that indicate that our entropy-driven approach provides a better balance between learning efficiency and user satisfaction than static selection techniques.

Floorplanning algorithms have traditionally underperformed experienced designers, even when relatively simple interconnect metrics are concerned. However, the sheer scale of modern systems on chip makes an all-manual design flow infeasible. In this paper, we propose a new efficient automated approach to the floorplan repair problem, where a set of violated design constraints are satisfied by applying small changes to an existing rough floorplan. Such a floorplan can be produced by a human designer, by a scalable placement algorithm, or result from engineering adjustments to a pre-existing floorplan. In all cases, overlapping modules must be separated, and in some instances, modules may need to be repositioned to satisfy other requirements.The algorithmic framework we propose is built upon an expressive graph-based encoding of constraints. While capable of representing floorplans with or without overlapping modules, it can also support the outline of the core area, fixed module locations, region constraints, proximity and alignment constraints, etc. Instead of applying randomized local search in the hope of satisfying these constraints, we track all implications of imposed constraints and resolve violations by invoking gradual modifications to the floorplan.The primary focus of this paper is on a particularly efficient conflict-directed algorithm for floorplan repair and legalization. It is shown to completely eliminate overlaps from layouts produced by Capo 9.4, Feng Shui 5.1 and APlace 2.01 on IBM-HB benchmarks with hard blocks, typically requiring negligible runtime and increasing interconnect length by only several percent. Furthermore, we are able to generate legal solutions for these instances that surpass previously reported results in wirelength by an average of roughly 7%.

We present PLIANT, a learning system that supports adaptive assistance in an open calendaring system. PLIANT learns user preferences from the feedback that naturally occurs during interactive scheduling. It contributes a novel application of active learning in a domain where the choice of candidate schedules to present to the user must balance usefulness to the learning module with immediate benefit to the user. Our experimental results provide evidence of PLIANT's ability to learn user preferences under various conditions and reveal the tradeoffs made by the different active learning selection strategies.

Reminder systems support people with impaired prospective memory and/or executive function, by providing them with reminders of their functional daily activities. We integrate temporal constraint reasoning with reinforcement learning (RL) to build an adaptive reminder system and in a simulated environment demonstrate that it can personalize to a user and adapt to both short- and long-term changes. In addition to advancing the application domain, our integrated algorithm contributes to research on temporal constraint reasoning by showing how RL can select an optimal policy from amongst a set of temporally consistent ones, and it contributes to the work on RL by showing how temporal constraint reasoning can be used to dramatically reduce the space of actions from which an RL agent needs to learn.

A widespread recognition of the usefulness of graphical user interfaces (GUIs) has established their importance as critical components of today's software. GUIs have characteristics different from traditional software, and conventional testing techniques do not directly apply to GUIs. This paper's focus is on coverage critieria for GUIs, important rules that provide an objective measure of test quality. We present new coverage criteria to help determine whether a GUI has been adequately tested. These coverage criteria use events and event sequences to specify a measure of test adequacy. Since the total number of permutations of event sequences in any non-trivial GUI is extremely large, the GUI's hierarchical structure is exploited to identify the important event sequences to be tested. A GUI is decomposed into GUI components, each of which is used as a basic unit of testing. A representation of a GUI component, called an event-flow graph, identifies the interaction of events within a component and intra-component criteria are used to evaluate the adequacy of tests on these events. The hierarchical relationship among components is represented by an integration tree, and inter-component coverage criteria are used to evaluate the adequacy of test sequences that cross components. Algorithms are given to construct event-flow graphs and an integration tree for a given GUI, and to evaluate the coverage of a given test suite with respect to the new coverage criteria. A case study illustrates the usefulness of the coverage report to guide further testing and an important correlation between event-based coverage of a GUI and statement coverage of its software's underlying code.

The widespread use of GUIs for interacting with software is leading to the construction of more and more complex GUIs. With the growing complexity come challenges in testing the correctness of a GUI and its underlying software. We present a new technique to automatically generate test cases for GUIs that exploits planning, a well-developed and used technique in artificial intelligence. Given a set of operators, an initial state, and a goal state, a planner produces a sequence of the operators that will transform the initial state to the goal state. Our test case generation technique enables efficient application of planning by first creating a hierarchical model of a GUI based on its structure. The GUI model consists of hierarchical planning operators representing the possible events in the GUI. The test designer defines the preconditions and effects of the hierarchical operators, which are input into a plan-generation system. The test designer also creates scenarios that represent typical initial and goal states for a GUI user. The planner then generates plans representing sequences of GUI interactions that a user might employ to reach the goal state from the initial state. We implemented our test case generation system, called Planning Assisted Tester for Graphical User Interface Systems (PATHS) and experimentally evaluated its practicality and effectiveness. We describe a prototype implementation of PATHS and report on the results of controlled experiments to generate test cases for Microsoft's WordPad.

Graphical User Interfaces (GUIs) are critical components of today's software. Because GUIs have different characteristics than traditional software, conventional testing techniques do not apply to GUI software. In previous work, we presented an approach to generate GUI test cases, which take the form of sequences of actions. In this paper we develop a test oracle technique to determine if a GUI behaves as expected for a given test case. Our oracle uses a formal model of a GUI, expressed as sets of objects, object properties, and actions. Given the formal model and a test case, our oracle automatically derives the expected state for every action in the test case. We represent the actual state of an executing GUI in terms of objects and their properties derived from the GUI's execution. Using the actual state acquired from an execution monitor, our oracle automatically compares the expected and actual states after each action to verify the correctness of the GUI for the test case. We implemented the oracle as a component in our GUI testing system, called Planning Assisted Tester for grapHical user interface Systems (PATHS), which is based on AI planning. We experimentally evaluated the practicality and effectiveness of our oracle technique and report on the results of experiments to test and verify the behavior of our version of the Microsoft WordPad's GUI.

Systems with timing constraints have become pervasive in several disciplines, such as real-time artificial intelligence, operating systems, operations research, and local area networks. Most of the work in real-time system scheduling deals with admission control algorithms to guarantee that accepted tasks will meet their deadlines. In this paper, we compare the different algorithms, and suggest a novel algorithm that subsumes the previous ones with respect to schedulability in the case where the system may suffer from transient overloads and where tasks have precedence constraints among them. We show how our algorithm works in allocating time to competing reasoning modules in dynamic environments.

The widespread use of GUIs for interacting with soft-ware is leading to the construction of more and more complex GUIs. With the growing complexity comes challenges in testing the correctness of a GUI and the underlying software. We present a new technique to au-tomatically generate test cases for GUIs that exploits planning, a well developed and used technique in ar-tificial intelligence. Given a set of operators, an initial state and a goal state, a planner produces a sequence of the operators that will change the initial state to the goal state. Our test case generation technique first ana-lyzes a GUI and derives hierarchical planning operators from the actions in the GUI. The test designer deter-mines the preconditions and effects of the hierarchical operators, which are then input into a planning system. With the knowledge of the GUI and the way in which the user will interact with the GUI, the test designer creates sets of initial and goal states. Given these ini-tial and final states of the GUI, a hierarchical planner produces plans, or a set of test cases, that enable the goal state to be reached. Our technique has the ad-ditional benefit of putting verification commands into the test cases automatically. We implemented our tech-nique by developing the GUI analyzer and extending a planner. We generated test cases for Microsoft’s Word-Pad to demonstrate the viability and practicality of the approach.

Several recent studies have compared the relative efficiency of alternative flaw selection strategies for partial-order causal link (POCL) planning. We review this literature, and present new experimental results that generalize the earlier work and explain some of the discrepancies in it. In particular, we describe the Least-Cost Flaw Repair (LCFR) strategy developed and analyzed by Joslin and Pollack (1994), and compare it with other strategies, including Gerevini and Schubert's (1996) ZLIFO strategy. LCFR and ZLIFO make very different, and apparently conflicting claims about the most effective way to reduce search-space size in POCL planning. We resolve this conflict, arguing that much of the benefit that Gerevini and Schubert ascribe to the LIFO component of their ZLIFO strategy is better attributed to other causes. We show that for many problems, a strategy that combines least-cost flaw selection with the delay of separable threats will be effective in reducing search-space size, and will do so without excessive computational overhead. Although such a strategy thus provides a good default, we also show that certain domain characteristics may reduce its effectiveness.

We report on a mechanism for semantic and pragmatic interpretation that has been designed to take advantage of the generally compositional nature of semantic analysis, without unduly constraining the order in which pragmatic decisions are made. To achieve this goal, we introduce the idea of a conditional interpretation: one that depends upon a set of assumptions about subsequent pragmatic processing. Conditional interpretations are constructed compositionally according to a set of declaratively specified interpretation rules. The mechanism can handle a wide range of pragmatic phenomena and their interactions.

An architecture for a rational agent must allow for means‐end reasoning, for the weighing of competing alternatives, and for interactions betwen these two forms of reasoning. Such an architecture must also address the problem of resource boundedness. We sketch a solution of the first problem that points the way to a solution of the second. In particular, we present a high‐level specification of the practical‐reasoning component of an architecture for a resource‐bounded rational agent. In this architecture, a major role of the agent's plans is to constrain the amount of further practical reasoning she must perform.

Existing models of plan inference (PI) in conversation have assumed that the agent whose plan is being inferred (the actor) and the agent drawing the inference (the observer) have identical beliefs about actions in the domain. I argue that this assumption often results in failure of both the PI process and the communicative process that PI is meant to support. In particular, it precludes the principled generation of appropriate responses to queries that arise from invalied plans. I describe a model of PI that abandons this assumption. It rests on an analysis of plans as mental phenomena. Judgements that a plan is invalid are associated with particular discrepancies between the beliefs that the observer ascribes to the actor when the former believes that the latter has some plan, and the beliefs that the observer herself holds. I show that the content of an appropriate response to a query is affected by the types of any such discrepancies of belief judged to be present in the plan inferred to underlie that query. The PI model described here has been implemented in SPIRIT, a small demonstration system that answers questions about the domain of computer mail.

Transcripts of computer-mail users seeking advice from an expert were studied to investigate the complementary claims that people often do not know what information they need to obtain in order to achieve their goals, and consequently, that experts must identify inappropriate queries and infer and respond to the goals behind them. This paper reports on one facet of the transcript analysis, namely, the identification of the types of relation that hold between the action that an advice-seeker asks about and the action that an expert tells him how to perform. Three such relations between actions are identified: generates, enables, and is-alternative-to. The claim is made that a cooperative advice-providing system, such as a help system or an expert system, must be able to compute these relations between actions.