Martha E. Pollack

IJCAI Conference 2007 Conference Paper

• Michael D. Moffitt
• Martha E. Pollack

In this paper, we focus on extending the expressive power of constraint-based temporal reasoning formalisms. We begin with the well-known Simple Temporal Problem with Uncertainty, and incorporate three extensions: prior observability, in which the values of uncontrollable events become known prior to their actual occurrence; partial shrinkage, in which an observation event triggers the reduction of a contingent temporal interval; and a generalization of partial shrinkage to requirement links, making it possible to express certain types of uncertainty that may arise even when the time points in a problem are themselves fully controllable. We describe levels of controllability in the resulting formalism, the Generalized STPU, and relate this formalism to related developments in disjunctive temporal reasoning. Throughout, we motivate our approach with simple, real-world examples that illustrate the limitations of existing formalisms and the flexibility of our proposed extensions.

ICAPS Conference 2006 Conference Paper

Optimal Rectangle Packing: A Meta-CSP Approach

• Michael D. Moffitt
• Martha E. Pollack

We present a new approach to optimal rectangle packing, an NP-complete problem that can be used to model many simple scheduling tasks. Recent attempts at incorporating artificial intelligence search techniques to the problem of rectangle packing have focused on a CSP formulation, in which partial assignments are defined to be the fixed placement of a subset of rectangles. Our technique takes a significant departure from this search space, as we instead view partial assignments as subsets of relative pairwise relationships between rectangles. This approach recalls the meta-CSP commonly constructed in constraint-based temporal reasoning, and is thus a candidate for several pruning techniques that have been developed in that field. We apply these to the domain of rectangle packing, and develop a suite of new techniques that exploit both the symmetry and geometry present in this particular domain. We then provide experimental results demonstrating that our approach performs competitively compared to the previous state-of-the-art on a series of benchmarks, matching or surpassing it in speed on nearly all instances. Finally, we conjecture that our technique is particularly appropriate for problems containing large rectangles, which are difficult for the fixed-placement formulation to handle efficiently.

IJCAI Conference 2005 Conference Paper

Identifying Conflicts in Overconstrained Temporal Problems

• Mark H. Liffiton
• Michael D. Moffitt
• Martha E. Pollack
• Karem A

We describe a strong connection between maximally satisfiable and minimally unsatisfiable subsets of constraint systems. Using this relationship, we develop a two-phase algorithm, employing powerful constraint satisfaction techniques, for the identification of conflicting sets of constraints in infeasible constraint systems. We apply this technique to overconstrained instances of the Disjunctive Temporal Problem (DTP), an expressive form of temporal constraint satisfaction problems. Using randomly-generated benchmarks, we provide experimental results that demonstrate how the algorithm scales with problem size and constraint density.

ICAPS Conference 2005 Conference Paper

Solving Over-constrained Disjunctive Temporal Problems with Preferences

• Bart Peintner
• Michael D. Moffitt
• Martha E. Pollack

We present an algorithm and pruning techniques for efficiently finding optimal solutions to over-constrained instances of the Disjunctive Temporal Problem with Preferences (DTPP). Our goal is to remove the burden from the knowledge engineer who normally must reason about an inherent trade-off: including more events and tighter constraints in a DTP leads to higher-quality solutions, but decreases the chances that a solution will exist. Our method solves a potentially over-constrained DTPP by searching through the space of induced DTPPs, which are DTPPs that include a subset of the events in the original problem. The method incrementally builds an induced DTPP and uses a known DTPP algorithm to find the value of its optimal solution. Optimality is defined using an objective function that combines the value of a set of included events with the value of a DTPP induced by those events. The key element in our approach is the use of powerful pruning techniques that dramatically lower the time required to find an optimal solution. We present empirical results that show their effectiveness.

ICML Conference 2004 Conference Paper

Adaptive cognitive orthotics: combining reinforcement learning and constraint-based temporal reasoning

• Matthew R. Rudary
• Satinder Singh 0001
• Martha E. Pollack

AAAI Conference 2004 Conference Paper

Low-cost Addition of Preferences to DTPs and TCSPs

• Bart Peintner
• Martha E. Pollack

We present an efficient approach to adding soft constraints, in the form of preferences, to Disjunctive Temporal Problems (DTPs) and their subclass Temporal Constraint Satisfaction Problems (TCSPs). Specifically, we describe an algorithm for checking the consistency of and finding optimal solutions to such problems. The algorithm borrows concepts from previous algorithms for solving TCSPs and Simple Temporal Problems with Preferences (STPPs), in both cases using techniques for projecting and solving component sub-problems. We show that adding preferences to DTPs and TCSPs requires only slightly more time than corresponding algorithms for TCSPs and DTPs without preferences. Thus, for problems where DTPs and TCSPs make sense, adding preferences provides a substantial gain in expressiveness for a marginal cost.

ICAPS Conference 2002 Conference Paper

A Plan-Based Personalized Cognitive Orthotic

• Colleen E. McCarthy
• Martha E. Pollack

The majority of reminder systems are inflexible; reminders are issued at static, prespecified times. To be effective, cognitive orthotics should reason about what reminders should be issued and when. This paper describes the personalized cognitive orthotic (PCO), a system that uses plan-based reasoning to attain flexibility. PCO relies on local search techniques to generate high-quality reminder plans based on knowledge of the user’s plans and her typical behavior. PCO is being developed in concert with other technologies aimed at improved plan management, including systems that update a user’s plans and track action execution. We describe the PCO as it is implemented in the Nursebot application: where it provides timely and relevant reminders to elderly people who have cognitive decline that necessitates assistance in managing their daily activities.

ICAPS Conference 2002 Conference Paper

Execution Monitoring with Quantitative Temporal Dynamic Bayesian Networks

• Dirk Colbry
• Bart Peintner
• Martha E. Pollack

The goal of execution monitoring is to determine whether a system or person is following a plan appropriately. Monitoring information may be uncertain, and the plan being monitored may have complex temporal constraints. We develop a new framework for reasoning under uncertainty with quantitative temporal constraints - Quantitative Temporal Bayesian Networks -- and we discuss its application to plan-execution monitoring. QTBNs extend the major previous approaches to temporal reasoning under uncertainty: Time Nets, Dynamic Bayesian Networks and Dynamic Object Oriented Bayesian Networks. We argue that Time Nets can model quantitative temporal relationships but cannot easily model the changing values of fluents, while DBNs and DOOBNs naturally model fluents, but not quantitative temporal relationships. Both capabilities are required for execution monitoring, and are supported by QTBNs.

ICAPS Conference 2002 Invited Paper

Planning Technology for Intelligent Cognitive Orthotics

• Martha E. Pollack

The aging of the world’s population poses a challenge and an opportunity for the design of intelligent technology. This paper focuses on one type of assistive technology, cognitive orthotics, which can help people adapt to cognitive declines and continue satisfactory performance of routine activities, thereby potentially enabling them to remain in their own homes longer. Existing cognitive orthotics mainly provide alarms for prescribed activities at fixed times that are specified in advance. In contrast, we describe Autominder, a system we have designed that uses AI planning and plan management technology to carefully model an individual’s daily plans, attend to and reason about the execution of those plans, and make flexible and adaptive decisions about when it is most appropriate to issue reminders. The paper concentrates on one of Autominder’s three main components, the Plan Manager; other papers in this volume describe its other components.

AIJ Journal 2001 Journal Article

Evaluating new options in the context of existing plans

• John F. Horty
• Martha E. Pollack

This paper contributes to the foundations of a theory of rational choice for artificial agents in dynamic environments. Our work is developed within a theoretical framework, originally due to Bratman, that models resource-bounded agents as operating against the background of some current set of intentions, which helps to frame their subsequent reasoning. In contrast to the standard theory of rational choice, where options are evaluated in isolation, we therefore provide an analysis of situations in which the options presented to an agent are evaluated against a background context provided by the agent's current plans—commitments to future activities, which may themselves be only partially specified. The interactions between the new options and the background context can complicate the task of evaluating the option, rendering it either more or less desirable in context than it would have been in isolation.

ICAPS Conference 2000 Conference Paper

Merging Plans with Quantitative Temporal Constraints, Temporally Extended Actions, and Conditional Branches

• Ioannis Tsamardinos
• Martha E. Pollack
• John F. Horty

Wedevelop ml algorithm for merging plans that m’c represented in a richly expressive language. Specifically. we arc concernedwith plans that have (i) quantitative temporalconstraints, (ii} at. lions that are not instantaneous, but rather have temporal extent, and (iii) conditional branches. Given a set ~q of such plans, our algorithmfinds a set of constraints that jointly ensure that the plans in 8 are mutually consistent, if such a set of constraints exists. The algorithm has three phases. In the first, it employsa new data structtu-e, a conditional simple temporal network (CSTN). identify conflicts betweenthe plans. Next. it uses an approach developed by Yang (1997) to suggest a potential resolution of the identified conflicts. Finally, the CSTNis again used to check whether the proposed resolution observes all the temporal constraints. Wehave implemented our approach, mid we present preliminary experimental evidence about domainfactors that influence its performance.

ICAPS Conference 2000 Conference Paper

Plan Generation for GUI Testing

• Atif M. Memon
• Martha E. Pollack
• Mary Lou Soffa

Graphical user interfac,:s ((. ItL,,) have become nearly ul)itluitous its a reel. ms of int. eractillg wilh, ~, ~l’! wart. sysl ellS. ill’is are typically highly comI)lt’x l)i(’ct: s of software, and testing their correctiness poses a large challenge. In this paper, we present a new approach to automatic testing of (.;U Is that builds on AI ph-, mning techniques The mot/vating idtut ix that (; I i I I esl. tlcsigulers will ofIt: n find il c, t~it, r to specify typiral goals that uselx of Iheir software might have than to spt: cil’y sequences of GT’I actions that. users might perlbrm I. o achieve timse goals. Thus we cast (I1~1 ttrslrast: generation a. s an insl. aug: e or plan generatiou: given a specification of initial And goal states for a (J III, a plannc. ris ulsedI, o gt. iiei’al, (~ st: title, /ices of (jl. il actionsttiat leadfromthe initial sl. aic I. O/, he gual~tat, c. Wct. le, ~cril>t, oHr(. IUi I, esting SySleiii, I)AT]IS {lllmining.,_%s>isLcd Testerfor gi’ilplii,:al ilSei" interface. l~vslenls), ~uldwereport, oil i. ’~pet’iillOrtls ilSilig I.)ATIISIt) generat. clest ca, ~esfor Mirrosoft’s WordPAd.

AAAI Conference 1999 Conference Paper

Conditional, Probabilistic Planning: A Unifying Algorithm and Effective Search Control Mechanisms

• Nilufer Onder
• Martha E. Pollack
• University of Pittsburgh

Several recent papers describe algorithms for generating conditional and/or probabilistic plans. In this paper, we synthesize this work, and present a unifying algorithm that incorporates andclarifies the main techniques that have been developed in the previous literature. Ouralgorithm decouplesthe search-control strategy for conditional and/or probabilistic planning from the underlying plan-refinementprocess. A similar decouplinghas provento be very useful in the analysis of classical planning algorithms, and weshowthat it can be at least as useful here, wherethe search-control decisions are even morecrucial. Previous probabilistic/conditional planners havebeenseverely limited by the fact that they do not knowhowto handle failure points to advantage. Weshowhowa principled selection of failure points can be performedwithin the frameworkour algorithm. Wealso describe and show the effectiveness of additional heuristics. Wedescribe our implemented system called Mahinurand experimentally demonstrate that our methodsproduce efficiency improvements of several orders of magnitude.

TARK Conference 1998 Conference Paper

Evaluating Qptions in a Context

• John F. Horty
• Martha E. Pollack

ICAPS Conference 1998 Conference Paper

Rationale-Based Monitoring for Planning in Dynamic Environments

• Manuela Veloso
• Martha E. Pollack
• Michael T. Cox

Wedescribe a framework for planning in dynamic environments. A central question is how to focus the sensing performed by such a system, so that it responds appropriately to relevant changes, but does not attempt to monitor all the changesthat could possibly occur in the world. To achieve the required balance, we introduce rationale. based monitors, whichrepresent the features of the world state that are included in the plan rationale, i. e., the reasons for the plannln~ decisions so far made. Rationalebased monitors capture information both about the plan currently under developmentand the alternative choices that were found but not pursued. Wediscuss the plan transformations that mayresult from the firing of a rationale-based monitor, for examplewhenan alternative choice is detected. Wehave implemented the generation of and response to rationale-based monitoring within the Prodigy planner, and we describe experimentsthat showthe feasibility of our approach.

IJCAI Conference 1995 Conference Paper

Deriving Multi-Agent Coordination through Filtering Strategies

• Eithan Ephrati
• Martha E. Pollack
• Sigalit Ur

We examine an approach to multi-agent coordination that builds on earlier work on enabling single agents to control their reasoning in dynamic environments. Specifically, we study a generalization of the filtering strategy. Where single-agent filtering means tending to bypass options that are incompatible with an agent's own goals, multi-agent filtering means tending to bypass options that are incompatible with other agents' known or presumed goals. We examine several versions of multi-agent filtering, which range from purely implicit to minimally explicit, and discuss the trade-offs among these. We also describe a series of experiments that demonstrate initial results about the feasibility of using multi-agent filtering to achieve coordination without explicit negotiation.

ICAPS Conference 1994 Conference Paper

Decomposition and Causality in Partial-order Planning

• R. Michael Young
• Martha E. Pollack
• Johanna D. Moore

Wedescribe DPOCL, a partinl-order csnsal llnk planner that includes action decomposition. DPOCL builds directly on the SNLPalgorithm (McAllester Rosenbiltt 1991), and hence is clear and simple, ud can readily be integrated with other SNLPextensions. In addition, DPOCL is specifically designed to handle partially specified action decompositions. Plan generation in DPOCL exploits the planner’s ability to fill in the missing pieces of n partially specified subplan in s way that uses the existing context of the larger plan being constructed.

IJCAI Conference 1993 Conference Paper

A Representationalist Theory of Intention

• Kurt Konolige
• Martha E. Pollack

Several formalizations of cognitive state that include intentions and beliefs based on normal modal logics (NMLs) have appeared in the recent literature. We argue that NMLs are not an appropriate representation for intention, and provide an alternative model, one that is representationalist, in the sense that its semantic objects provide a more direct representation of cognitive state of the intending agent. We argue that this approach results in a much simpler model of intention than does the use of an NML, and that, moreover, it allows us to capture interesting properties of intention that have not been addressed in previous work

AIJ Journal 1992 Journal Article

The uses of plans

• Martha E. Pollack

AIJ Journal 1991 Journal Article

Incremental interpretation

• Fernando C.N. Pereira
• Martha E. Pollack

We present a system for the incremental interpretation of natural-language utterances in context. The main goal of the work is to account for the influences of context on interpretation, while preserving compositionality to the extent possible. To achieve this goal, we introduce a representational device, conditional interpretations, and a rule system for constructing them. Conditional interpretations represent the potential contributions of phrases to the interpretation of an utterance. The rules specify how phrase interpretations are combined and how they are elaborated with respect to context. The control structure defined by the rules determines the points in the interpretation process at which sufficient information becomes available to carry out specific inferential interpretation steps, such as determining the plausibility of particular referential connections or modifier attachments. We have implemented these ideas in Candide, a system for interactive acquisition of procedural knowledge.

AAAI Conference 1990 Conference Paper

Introducing the Tileworld: Experimentally Evaluating Agent Architectures

• Martha E. Pollack

IJCAI Conference 1989 Conference Paper

Ascribing Plans to Agents

• Kurt Konolige
• Martha E. Pollack

Intelligent agents who are situated in nuiltiagent domains must reason about one anotIters' actions and plans. Following the tradition of earlier work in A l, we present a model of plan recognition as belief and intention ascription, an inherently defeasible reasoning process. However, we encode this process using a direct argumentation system. Within this system, we can make explicit statements about why one candidate ascription should be preferred over another. And we can avoid the overly strong assumption that the actor's plan is correct from the perspective of the observer—an assumption that was necessary in previous formalizations of plan recognition.

AAAI Conference 1982 Conference Paper

User Participation in the Reasoning Processes of Expert Systems

• Martha E. Pollack

We argue that expert systems, if they are to satisfy the legitimate needs of their users, must include dialogue capabilities as sophisticated as those proposed in current Natural Language research. In particular they must allow the user to direct the flow of the dialogue and must take into account the user’s goals and expectations both in analyzing the user’s statements and in providing appropriate responses. Our claims are corroborated by an analysis of transcripts of a "naturally occurring" expert system, a radio talk show in which callers ask an expert for financial advice. We present data demonstrating that user-expert dialogues are best viewed as a negotiation process, and we describe the exchanges that compose the dialogue in terms of the motivations, goals, strategies, and moves of the participants.