Edmund Durfee

AAAI Conference 2020 Conference Paper

Modeling Probabilistic Commitments for Maintenance Is Inherently Harder than for Achievement

• Qi Zhang
• Edmund Durfee
• Satinder Singh

Most research on probabilistic commitments focuses on commitments to achieve enabling preconditions for other agents. Our work reveals that probabilistic commitments to instead maintain preconditions for others are surprisingly harder to use well than their achievement counterparts, despite strong semantic similarities. We isolate the key difference as being not in how the commitment provider is constrained, but rather in how the commitment recipient can locally use the commitment specification to approximately model the provider’s effects on the preconditions of interest. Our theoretic analyses show that we can more tightly bound the potential suboptimality due to approximate modeling for achievement than for maintenance commitments. We empirically evaluate alternative approximate modeling strategies, confirming that probabilistic maintenance commitments are qualitatively more challenging for the recipient to model well, and indicating the need for more detailed specifications that can sacrifice some of the agents’ autonomy.

AAAI Conference 2020 Conference Paper

Querying to Find a Safe Policy under Uncertain Safety Constraints in Markov Decision Processes

• Shun Zhang
• Edmund Durfee
• Satinder Singh

An autonomous agent acting on behalf of a human user has the potential of causing side-effects that surprise the user in unsafe ways. When the agent cannot formulate a policy with only side-effects it knows are safe, it needs to selectively query the user about whether other useful side-effects are safe. Our goal is an algorithm that queries about as few potential side-effects as possible to find a safe policy, or to prove that none exists. We extend prior work on irreducible infeasible sets to also handle our problem’s complication that a constraint to avoid a side-effect cannot be relaxed without user permission. By proving that our objectives are also adaptive submodular, we devise a querying algorithm that we empirically show finds nearly-optimal queries with much less computation than a guaranteed-optimal approach, and outperforms competing approximate approaches.

AIJ Journal 2020 Journal Article

Recursively modeling other agents for decision making: A research perspective

• Prashant Doshi
• Piotr Gmytrasiewicz
• Edmund Durfee

Individuals exhibit theory of mind, attributing beliefs, intent, and mental states to others as explanations of observed actions. Dennett's intentional stance offers an analogous abstraction for computational agents seeking to understand, explain, or predict others' behaviors. These recognized theories provide a formal basis to ongoing investigations of recursive modeling. We review and situate various frameworks for recursive modeling that have been studied in game- and decision- theories, and have yielded methods useful to AI researchers. Sustained attention given to these frameworks has produced new analyses and methods with an aim toward making recursive modeling practicable. Indeed, we also review some emerging uses and the insights these yielded, which are indicative of pragmatic progress in this area. The significance of these frameworks is that higher-order reasoning is critical to correctly recognizing others' intent or outthinking opponents. Such reasoning has been utilized in academic, business, military, security, and other contexts both to train and inform decision-making agents in organizational and strategic contexts, and also to more realistically predict and best respond to other agents' intent.

AAAI Conference 2019 Conference Paper

Learning to Communicate and Solve Visual Blocks-World Tasks

• Qi Zhang
• Richard Lewis
• Satinder Singh
• Edmund Durfee

We study emergent communication between speaker and listener recurrent neural-network agents that are tasked to cooperatively construct a blocks-world target image sampled from a generative grammar of blocks configurations. The speaker receives the target image and learns to emit a sequence of discrete symbols from a fixed vocabulary. The listener learns to construct a blocks-world image by choosing block placement actions as a function of the speaker’s full utterance and the image of the ongoing construction. Our contributions are (a) the introduction of a task domain for studying emergent communication that is both challenging and affords useful analyses of the emergent protocols; (b) an empirical comparison of the interpolation and extrapolation performance of training via supervised, (contextual) Bandit, and reinforcement learning; and (c) evidence for the emergence of interesting linguistic properties in the RL agent protocol that are distinct from the other two.

RLDM Conference 2017 Conference Abstract

Approximately-Optimal Queries in Reward-Uncertain Markov Decision Processes

• Shun Zhang
• Edmund Durfee
• Satinder Singh

When planning actions to take on behalf of its human operator, a robot might be uncertain about its operator’s reward function. We address the problem of how the robot should formulate an (approxi- mately) optimal query to pose to the operator, given how its uncertainty affects which policies it should plan to pursue. We explain how a robot whose queries ask the operator to choose the best from among k choices can, without loss of optimality, restrict consideration to choices only over alternative policies. Fur- ther, we present a method for constructing an approximately-optimal policy query that enjoys a performance bound, where the method need not enumerate all policies. Finally, because queries posed to the operator of a robotic system are often expressed in terms of preferences over trajectories rather than policies, we show how our constructed policy query can be projected into the space of trajectory queries. Our empirical results demonstrate that our projection technique can outperform prior techniques for choosing trajectory queries, particularly when the number of trajectories the operator is asked to compare is small.

IJCAI Conference 2016 Conference Paper

Commitment Semantics for Sequential Decision Making under Reward Uncertainty

• Qi Zhang
• Edmund Durfee
• Satinder Singh
• Anna Chen
• Stefan Witwicki

Cooperating agents can make commitments to help each other, but commitments might have to be probabilistic when actions have stochastic outcomes. We consider the additional complication in cases where an agent might prefer to change its policy as it learns more about its reward function from experience. How should such an agent be allowed to change its policy while still faithfully pursuing its commitment in a principled decision-theoretic manner? We address this question by defining a class of Dec-POMDPs with Bayesian reward uncertainty, and by developing a novel Commitment Constrained Iterative Mean Reward algorithm that implements the semantics of faithful commitment pursuit while still permitting the agent's response to the evolving understanding of its rewards. We bound the performance of our algorithm theoretically, and evaluate empirically how it effectively balances solution quality and computation cost.

AAAI Conference 2014 Conference Paper

Multiagent Metareasoning through Organizational Design

• Jason Sleight
• Edmund Durfee

We formulate an approach to multiagent metareasoning that uses organizational design to focus each agent’s reasoning on the aspects of its local problem that let it make the most worthwhile contributions to joint behavior. By employing the decentralized Markov decision process framework, we characterize an organizational design problem that explicitly considers the quantitative impact that a design has on both the quality of the agents’ behaviors and their reasoning costs. We describe an automated organizational design process that can approximately solve our organizational design problem via incremental search, and present techniques that efficiently estimate the incremental impact of a candidate organizational influence. Our empirical evaluation confirms that our process generates organizational designs that impart a desired metareasoning regime upon the agents.

AAAI Conference 2013 Conference Paper

Decoupling the Multiagent Disjunctive Temporal Problem

• James Boerkoel Jr.
• Edmund Durfee

The Multiagent Disjunctive Temporal Problem (MaDTP) is a general constraint-based formulation for scheduling problems that involve interdependent agents. Decoupling agents’ interdependent scheduling problems, so that each agent can manage its schedule independently, requires agents to adopt additional local constraints that effectively subsume their interdependencies. In this paper, we present the first algorithm for decoupling MaDTPs. Our distributed algorithm is provably sound and complete. Our experiments show that the relative efficiency of using temporal decoupling to find solution spaces for MaDTPs, compared to algorithms that find complete solution spaces, improves with the interconnectedness between agents schedules, leading to orders of magnitude relative speeedup. However, decoupling by its nature restricts agents’ scheduling flexibility; we define novel flexibility metrics for MaDTPs, and show empirically how the flexibility sacrificed depends on the degree of coupling between agents’ schedules.

AAAI Conference 2012 Conference Paper

A Distributed Approach to Summarizing Spaces of Multiagent Schedules

• James Boerkoel Jr.
• Edmund Durfee

We introduce the Multiagent Disjunctive Temporal Problem (MaDTP), a new distributed formulation of the widely-adopted Disjunctive Temporal Problem (DTP) representation. An agent that generates a summary of all viable schedules, rather than a single schedule, can be more useful in dynamic environments. We show how a (Ma)DTP with the properties of minimality and decomposability provides a particularly efficacious solution space summary. However, in the multiagent case, these properties sacrifice an agent’s strategic interests while incurring significant computational overhead. We introduce a new property called local decomposability that exploits loose-coupling between agents’ problems, protects strategic interests, and supports typical queries. We provide and evaluate a new distributed algorithm that summarizes agents’ solution spaces in significantly less time and space by using local, rather than full, decomposability.

AAAI Conference 2011 Conference Paper

Comparing Action-Query Strategies in Semi-Autonomous Agents

• Robert Cohn
• Edmund Durfee
• Satinder Singh

We consider settings in which a semi-autonomous agent has uncertain knowledge about its environment, but can ask what action the human operator would prefer taking in the current or in a potential future state. Asking queries can improve behavior, but if queries come at a cost (e. g. , due to limited operator attention), the value of each query should be maximized. We compare two strategies for selecting action queries: 1) based on myopically maximizing expected gain in long-term value, and 2) based on myopically minimizing uncertainty in the agent’s policy representation. We show empirically that the first strategy tends to select more valuable queries, and that a hybrid method can outperform either method alone in settings with limited computation.

AAMAS Conference 2007 Conference Paper

Commitment-Driven Distributed Joint Policy Search

• Stefan Witwicki
• Edmund Durfee

Decentralized MDPs provide powerful models of interactions in multi-agent environments, but are often very difficult or even computationally infeasible to solve optimally. Here we develop a hierarchical approach to solving a restricted set of decentralized MDPs. By forming commitments with other agents and modeling these concisely in their local MDPs, agents effectively, efficiently, and distributively formulate coordinated local policies. We introduce a novel construction that captures commitments as constraints on local policies and show how Linear Programming can be used to achieve local optimality subject to these constraints. In contrast to other commitment enforcement approaches, we show ours to be more robust in capturing the intended commitment semantics while maximizing local utility. We also describe a commitment-space heuristic search algorithm that can be used to approximate optimal joint policies. A preliminary empirical evaluation suggests that our approach yields faster approximate solutions than the conventional encoding of the problem as a multiagent MDP would allow and, when wrapped in an exhaustive commitment-space search, will find the optimal global solution.

AAMAS Conference 2006 Conference Paper

Mathematical Programming for Deliberation Scheduling in Time-limited Domains

• Jianhui Wu
• Edmund Durfee

AAMAS Conference 2006 Conference Paper

Mixed-integer Linear Programming for Transition-independent Decentralized MDPs

• Jianhui Wu
• Edmund Durfee

AAMAS Conference 2006 Conference Paper

Resource Allocation Among Agents with Preferences Induced by Factored MDPs

• Dmitri Dolgov
• Edmund Durfee

AAMAS Conference 2005 Conference Paper

A Distributed Framework for Solving the Multiagent Plan Coordination Problem

• Jeffrey Cox
• Edmund Durfee
• Thomas Bartold

AAMAS Conference 2005 Conference Paper

An Efficient Algorithm for Multiagent Plan Coordination

• Jeffrey Cox
• Edmund Durfee

AAMAS Conference 2005 Conference Paper

Computationally-Efficient Combinatorial Auctions for Resource Allocation in Weakly-Coupled MDPs

• Dmitri Dolgov
• Edmund Durfee

AAMAS Conference 2004 Conference Paper

Graphical Models in Local, Asymmetric Multi-Agent Markov Decision Processes

• Dmitri Dolgov
• Edmund Durfee

AAMAS Conference 2004 Conference Paper

The Impact of Communication Costs and Limitations on Price Wars

• Jianhui Wu
• Edmund Durfee

AAMAS Conference 2003 Conference Paper

Limiting Disruption in Multiagent Replanning

• Thomas Bartold
• Edmund Durfee