Edmund H. Durfee

JAAMAS Journal 2026 Journal Article

Congregation Formation in Multiagent Systems

• Christopher H. Brooks
• Edmund H. Durfee

Abstract We present congregating both as a metaphor for describing and modeling multiagent systems (MAS) and as a means for reducing coordination costs in large-scale MAS. When agents must search for other agents to interact with, congregations provide a way for agents to bias this search towards groups of agents that have tended to produce successful interactions in the past. This causes each agent's search problem to scale with the size of a congregation rather than the size of the population as a whole. In this paper, we present a formal model of a congregation and then apply Vidal and Durfee's CLRI framework [24] to the congregating problem. We apply congregating to the affinity group domain, and show that if agents are unable to describe congregations to each other, the problem of forming optimal congregations grows exponentially with the number of agents. The introduction of labelers provides a means of coordinating agent decisions, thereby reducing the problem's complexity. We then show how a structured label space can be exploited to simplify the labeler's decision problem and make the congregating problem linear in the number of labels. We then present experimental evidence demonstrating how congregating can be used to reduce agents' search costs, thereby allowing the system to scale up. We conclude with a comparison to other methods for coordinating multiagent behavior, particularly teams and coalitions.

JAAMAS Journal 2026 Journal Article

Emergent Properties of a Market-based Digital Library with Strategic Agents

• Sunju Park
• Edmund H. Durfee
• William P. Birmingham

Abstract The University of Michigan Digital Library (UMDL) is designed as an open system that allows third parties to build and integrate their own profit-seeking agents into the marketplace of information goods and services. The profit-seeking behavior of agents, however, risks inefficient allocation of goods and services, as agents take strategic stances that might backfire. While it would be good if we could impose mechanisms to remove incentives for strategic reasoning, this is not possible in the UMDL. Therefore, our approach has instead been to study whether encouraging the other extreme—making strategic reasoning ubiquitous—provides an answer. Toward this end, we have designed a strategy (called the p-strategy) that uses a stochastic model of the market to find the best offer price. We have then examined the collective behavior of p-strategy agents in the UMDL auction. Our experiments show that strategic thinking is not always beneficial and that the advantage of being strategic decreases with the arrival of equally strategic agents. Furthermore, a simpler strategy can be as effective when enough other agents use the p-strategy. Consequently, we expect the UMDL is likely to evolve to a point where some agents use simpler strategies and some use the p-strategy.

JAAMAS Journal 2026 Journal Article

Planning and Resource Allocation for Hard Real-time, Fault-Tolerant Plan Execution

• Ella M. Atkins
• Tarek F. Abdelzaher
• Edmund H. Durfee

Abstract We describe the interface between a real-time resource allocation system with an AI planner in order to create fault-tolerant plans that are guaranteed to execute in hard real-time. The planner specifies the task set and all execution deadlines required to ensure system safety, then the resource utilization. A new interface module combines information from planning and resource allocation to enforce development of plans feasible for execution during a variety of internal system faults. Plans that over-utilize any system resource trigger feedback to the planner, which then searches for an alternate plan. A valid plan for each specified fault, including the nominal no-fault situation, is stored in a plan cache for subsequent real-time execution. We situate this work in the context of CIRCA, the Cooperative Intelligent Real-time Control Architecture, which focuses on developing and scheduling plans that make hard real-time safety guarantees, and provide an example of an autonomous aircraft agent to illustrate how our planner-resource allocation interface improves CIRCA performance.

JAAMAS Journal 2026 Journal Article

Predicting the Expected Behavior of Agents that Learn About Agents: The CLRI Framework

• José M. Vidal
• Edmund H. Durfee

Abstract We describe a framework and equations used to model and predict the behavior of multi-agent systems (MASs) with learning agents. A difference equation is used for calculating the progression of an agent's error in its decision function, thereby telling us how the agent is expected to fare in the MAS. The equation relies on parameters which capture the agent's learning abilities, such as its change rate, learning rate and retention rate, as well as relevant aspects of the MAS such as the impact that agents have on each other. We validate the framework with experimental results using reinforcement learning agents in a market system, as well as with other experimental results gathered from the AI literature. Finally, we use PAC-theory to show how to calculate bounds on the values of the learning parameters.

JAAMAS Journal 2026 Journal Article

Rational Communication in Multi-Agent Environments

• Piotr J. Gmytrasiewicz
• Edmund H. Durfee

Abstract We address the issue of rational communicative behavior among autonomous self-interested agents that have to make decisions as to what to communicate, to whom, and how. Following decision theory, we postulate that a rational speaker should design a speech act so as to optimize the benefit it obtains as the result of the interaction. We quantify the gain in the quality of interaction in terms of the expected utility, and we present a framework that allows an agent to compute the expected utilities of various communicative actions. Our framework uses the Recursive Modeling Method as the specialized representation used for decision-making in a multi-agent environment. This representation includes information about the agent's state of knowledge, including the agent's preferences, abilities and beliefs about the world, as well as the beliefs the agent has about the other agents, the beliefs it has about the other agents' beliefs, and so on. Decision-theoretic pragmatics of a communicative act can be then defined as the transformation the act induces on the agent's state of knowledge about its decision-making situation. This transformation leads to a change in the quality of interaction, expressed in terms of the expected utilities of the agent's best actions before and after the communicative act. We analyze decision-theoretic pragmatics of a number of important kinds of communicative acts and investigate their expected utilities using examples. Finally, we report on the agreement between our method of message selection and messages that human subjects choose in various circumstances, and show an implementation and experimental validation of our framework in a simulated multi-agent environment.

JAAMAS Journal 2026 Journal Article

Rational Coordination in Multi-Agent Environments

• Piotr J. Gmytrasiewicz
• Edmund H. Durfee

Abstract We adopt the decision-theoretic principle of expected utility maximization as a paradigm for designing autonomous rational agents, and present a framework that uses this paradigm to determine the choice of coordinated action. We endow an agent with a specialized representation that captures the agent's knowledge about the environment and about the other agents, including its knowledge about their states of knowledge, which can include what they know about the other agents, and so on. This reciprocity leads to a recursive nesting of models. Our framework puts forth a representation for the recursive models and, under the assumption that the nesting of models is finite, uses dynamic programming to solve this representation for the agent's rational choice of action. Using a decision-theoretic approach, our work addresses concerns of agent decision-making about coordinated action in unpredictable situations, without imposing upon agents pre-designed prescriptions, or protocols, about standard rules of interaction. We implemented our method in a number of domains and we show results of coordination among our automated agents, among human-controlled agents, and among our agents coordinating with human-controlled agents.

AIJ Journal 2023 Journal Article

Risk-aware analysis for interpretations of probabilistic achievement and maintenance commitments

• Qi Zhang
• Edmund H. Durfee
• Satinder Singh

Probabilistic commitments provide a computational framework for multi-agent coordination, where one autonomous agent (the commitment provider), commits to a future course of action that probabilistically influences the local state of another agent (the commitment recipient) in ways that the recipient desires. Conventionally, a probabilistic commitment is specified abstractly so as to give the provider latitude at run time about how to achieve it. Unfortunately, as we analyze in this article, this abstraction incurs a risk of suboptimal performance for the recipient. For (achievement) commitments by the provider to achieve conditions that the recipient prefers but that do not initially hold, we prove that the recipient can make modeling choices that bound its risk of suboptimality. Somewhat surprisingly, however, for (maintenance) commitments by the provider to maintain conditions whose initial values are already ones the recipient prefers, we prove that no such bounds on suboptimality risk are possible. We study the two types of commitments empirically to measure the suboptimality they incur under different conditions, and based on our theoretical and empirical results suggest that adding selective details when specifying probabilistic maintenance commitments can be beneficial.

AAAI Conference 2021 Conference Paper

Efficient Querying for Cooperative Probabilistic Commitments

• Qi Zhang
• Edmund H. Durfee
• Satinder Singh

Multiagent systems can use commitments as the core of a general coordination infrastructure, supporting both cooperative and non-cooperative interactions. Agents whose objectives are aligned, and where one agent can help another achieve greater reward by sacrificing some of its own reward, should choose a cooperative commitment to maximize their joint reward. We present a solution to the problem of how cooperative agents can efficiently find an (approximately) optimal commitment by querying about carefully-selected commitment choices. We prove structural properties of the agents’ values as functions of the parameters of the commitment specification, and develop a greedy method for composing a query with provable approximation bounds, which we empirically show can find nearly optimal commitments in a fraction of the time methods that lack our insights require.

AAMAS Conference 2021 Conference Paper

On Teammate-Pattern-Aware Autonomy

• Edmund H. Durfee
• Abhishek Thakur
• Eli Goldweber

We describe an approach for constraining robot autonomy based on the robot’s awareness of patterns of its human teammates’ behaviors, rather than either ignoring its teammates (which is fast but dangerous) or inferring their plans (which is safer but slow). We evaluate this approach in a series of simulated problems where an unmanned ground vehicle and its human teammates must rapidly respond to a sudden context shift, and identify conditions that should be (purposely) met such that a pattern-aware approach is particularly effective compared to the alternatives.

JAAMAS Journal 2020 Journal Article

Semantics and algorithms for trustworthy commitment achievement under model uncertainty

• Qi Zhang
• Edmund H. Durfee
• Satinder Singh

Abstract We focus on how an agent can exercise autonomy while still dependably fulfilling commitments it has made to another, despite uncertainty about outcomes of its actions and how its own objectives might evolve. Our formal semantics treats a probabilistic commitment as constraints on the actions an autonomous agent can take, rather than as promises about states of the environment it will achieve. We have developed a family of commitment-constrained (iterative) lookahead algorithms that provably respect the semantics, and that support different tradeoffs between computation and plan quality. Our empirical results confirm that our algorithms’ ability to balance (selfish) autonomy and (unselfish) dependability outperforms optimizing either alone, that our algorithms can effectively handle uncertainty about both what actions do and which states are rewarding, and that our algorithms can solve more computationally-demanding problems through judicious parameter choices for how far our algorithms should lookahead and how often they should iterate.

JAAMAS Journal 2020 Journal Article

Teammate-pattern-aware autonomy based on organizational self-design principles

• Edmund H. Durfee
• Abhishek Thakur
• Eli Goldweber

Abstract We describe an approach for constraining robot autonomy based on the robot’s awareness of patterns of its human teammates’ behaviors, rather than either ignoring its teammates (which is fast but dangerous) or inferring their plans (which is safer but slow). We explore the promise, and limitations, of this approach in a series of simulated problems where an unmanned ground vehicle and its human teammates must rapidly respond to a sudden context shift. Our results help us discern conditions under which a pattern-aware approach can be more effective than the alternatives, and our current efforts investigate how the manned–unmanned team can adopt biases to more readily establish such conditions that are more favorable to the pattern-aware approach.

IJCAI Conference 2018 Conference Paper

Minimax-Regret Querying on Side Effects for Safe Optimality in Factored Markov Decision Processes

• Shun Zhang
• Edmund H. Durfee
• Satinder Singh

As it achieves a goal on behalf of its human user, an autonomous agent's actions may have side effects that change features of its environment in ways that negatively surprise its user. An agent that can be trusted to operate safely should thus only change features the user has explicitly permitted. We formalize this problem, and develop a planning algorithm that avoids potentially negative side effects given what the agent knows about (un)changeable features. Further, we formulate a provably minimax-regret querying strategy for the agent to selectively ask the user about features that it hasn't explicitly been told about. We empirically show how much faster it is than a more exhaustive approach and how much better its queries are than those found by the best known heuristic.

AAMAS Conference 2018 Conference Paper

On Querying for Safe Optimality in Factored Markov Decision Processes

• Shun Zhang
• Edmund H. Durfee
• Satinder Singh

As it achieves a goal on behalf of its human user, an autonomous agent’s actions may have side effects that change features of its environment in ways that negatively surprise its user. An agent that can be trusted to operate safely should thus only change features the user has explicitly permitted. We formalize this problem, and develop a planning algorithm that avoids potentially negative side effects given what the agent knows about (un)changeable features. Further, we formulate a provably minimax-regret querying strategy for the agent to selectively ask the user about features that it hasn’t explicitly been told about. We empirically show how much faster it is than a more exhaustive approach and how much better its queries are than those found by the best known heuristic.

ICAPS Conference 2017 Conference Paper

Approximately-Optimal Queries for Planning in Reward-Uncertain Markov Decision Processes

• Shun Zhang
• Edmund H. Durfee
• Satinder Singh 0001

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 (approximately) 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. Further, 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.

ICAPS Conference 2017 Conference Paper

Minimizing Maximum Regret in Commitment Constrained Sequential Decision Making

• Qi Zhang 0038
• Satinder Singh 0001
• Edmund H. Durfee

In cooperative multiagent planning, it can often be beneficial for an agent to make commitments about aspects of its behavior to others, allowing them in turn to plan their own behaviors without taking the agent's detailed behavior into account. Extending previous work in the Bayesian setting, we consider instead a worst-case setting in which the agent has a set of possible environments (MDPs) it could be in, and develop a commitment semantics that allows for probabilistic guarantees on the agent's behavior in any of the environments it could end up facing. Crucially, an agent receives observations (of reward and state transitions) that allow it to potentially eliminate possible environments and thus obtain higher utility by adapting its policy to the history of observations. We develop algorithms and provide theory and some preliminary empirical results showing that they ensure an agent meets its commitments with history-dependent policies while minimizing maximum regret over the possible environments.

AAMAS Conference 2013 Conference Paper

Decoupling the Multiagent Disjunctive Temporal Problem

• James C. Boerkoel Jr.
• Edmund H. Durfee

In multiagent scheduling, each agent has to schedule its activities to respect its local (internal) temporal constraints, and also to satisfy external constraints between its activities and activities of other agents. A scheduling problem is decoupled if each agent can independently (and thus privately, autonomously, etc.) form a solution to its local problem such that agents’ combined solutions are guaranteed to satisfy all external constraints. We expand previous work that decouples multiagent scheduling problems containing strictly conjunctive temporal constraints to more general problems containing disjunctive constraints. While this raises a host of challenging issues, agents can leverage shared information as early and as often as possible to quickly adopt additional temporal constraints within their local problems that sacrifice some local scheduling flexibility in favor of decoupled, independent, and rapid local scheduling.

AAMAS Conference 2011 Conference Paper

Comparing Action-Query Strategies in Semi-Autonomous Agents

• Robert Cohn
• Edmund H. Durfee
• Satinder Singh

We consider semi-autonomous agents that have uncertain knowledge about their environment, but can ask what action the operator would prefer taking in the current or in a potential future state. Asking queries can help improve behavior, but if queries come at a cost (e. g. , due to limited operator attention), the number of queries needs to be minimized. We develop a new algorithm for selecting action queries by adapting the recently proposed Expected Myopic Gain (EMG) from its prior use in settings with reward or transition probability queries to our setting of action queries, and empirically compare it to the current state of the art.

AAMAS Conference 2011 Conference Paper

Distributed Algorithms for Solving the Multiagent Temporal Decoupling Problem

• James C. Boerkoel
• Edmund H. Durfee

Scheduling agents can use the Multiagent Simple Temporal Problem (MaSTP) formulation to efficiently find and represent the complete set of alternative consistent joint schedules in a distributed and privacy-maintaining manner. However, continually revising this set of consistent joint schedules as new constraints arise may not be a viable option in environments where communication is uncertain, costly, or otherwise problematic. As an alternative, agents can find and represent a temporal decoupling in terms of locally independent sets of consistent schedules that, when combined, form a set of consistent joint schedules. Unlike current algorithms for calculating a temporal decoupling that require centralization of the problem representation, in this paper we present a new, provably correct, distributed algorithm for calculating a temporal decoupling. We prove that this algorithm has the same theoretical computational complexity as current state-of-the-art MaSTP solution algorithms, and empirically demonstrate that it is more efficient in practice. We also introduce and perform an empirical cost/benefit analysis of new techniques and heuristics for selecting a maximally flexible temporal decoupling.

AAMAS Conference 2011 Conference Paper

Towards a Unifying Characterization for Quantifying Weak Coupling in Dec-POMDPs

• Stefan J. Witwicki
• Edmund H. Durfee

Researchers in the field of multiagent sequential decision making have commonly used the terms "weakly-coupled" and "loosely-coupled" to qualitatively classify problems involving agents whose interactions are limited, and to identify various structural restrictions that yield computational advantages to decomposing agents' centralized planning and reasoning into largely-decentralized planning and reasoning. Together, these restrictions make up a heterogeneous collection of facets of "weakly-coupled" structure that are conceptually related, but whose purported computational benefits are hard to compare evenhandedly. The contribution of this paper is a unified characterization of weak coupling that brings together three complementary aspects of agent interaction structure. By considering these aspects in combination, we derive new bounds on the computational complexity of optimal DecPOMDP planning, that together quantify the relative benefits of exploiting different forms of interaction structure. Further, we demonstrate how our characterizations can be used to explain why existing classes of decoupled solution algorithms perform well on some problems but poorly on others, as well as to predict the performance of a particular algorithm from identifiable problem attributes.

ICAPS Conference 2010 Conference Paper

A Comparison of Algorithms for Solving the Multiagent Simple Temporal Problem

• James C. Boerkoel Jr.
• Edmund H. Durfee

The Simple Temporal Problem (STP) is a popular representation for solving centralized scheduling and planning problems. When scheduling agents are associated with different users who need to coordinate some of their activities, however, considerations such as privacy and scalability suggest solving the joint STP in a more distributed manner. Building on recent advances in STP algorithms that exploit loosely-coupled problem structure, this paper develops and evaluates algorithms for solving the multiagent STP. We define a partitioning of the multiagent STP with provable privacy guarantees, and show that our algorithms can exploit this partitioning while still finding the tightest consistent bounds on timepoints that must be coordinated across agents. We also demonstrate empirically that our algorithms can exploit concurrent computation, leading to solution time speed-ups over state-of-the-art centralized approaches, and enabling scalability to problems involving larger numbers of loosely-coupled agents.

ICAPS Conference 2010 Conference Paper

Influence-Based Policy Abstraction for Weakly-Coupled Dec-POMDPs

• Stefan J. Witwicki
• Edmund H. Durfee

Decentralized POMDPs are powerful theoretical models for coordinating agents' decisions in uncertain environments, but the generally-intractable complexity of optimal joint policy construction presents a significant obstacle in applying Dec-POMDPs to problems where many agents face many policy choices. Here, we argue that when most agent choices are independent of other agents' choices, much of this complexity can be avoided: instead of coordinating full policies, agents need only coordinate policy abstractions that explicitly convey the essential interaction influences. To this end, we develop a novel framework for influence-based policy abstraction for weakly-coupled transition-dependent Dec-POMDP problems that subsumes several existing approaches. In addition to formally characterizing the space of transition-dependent influences, we provide a method for computing optimal and approximately-optimal joint policies. We present an initial empirical analysis, over problems with commonly-studied flavors of transition-dependent influences, that demonstrates the potential computational benefits of influence-based abstraction over state-of-the-art optimal policy search methods.

AAMAS Conference 2009 Conference Paper

Evaluating Hybrid Constraint Tightening for Scheduling Agents

• James C. Boerkoel Jr.
• Edmund H. Durfee

Hybrid Scheduling Problems (HSPs) combine temporal and finite-domain variables via hybrid constraints that dictate that specific bounds on temporal constraints rely on assignments to finite-domain variables. Hybrid constraint tightening (HCT) reformulates hybrid constraints to apply the tightest consistent temporal bound possible, assisting in search space pruning. The contribution of this paper is to empirically evaluate the HCT approach using a state-of-the-art Satisfiability Modulo Theory solver on realistic, interesting problems related to developing scheduling agents to assist people with cognitive impairments. We demonstrate that HCT leads to orders of magnitude reduction of search complexity. The success of HCT is enhanced as we apply HCT to hybrid constraints involving increasing numbers of finite-domain variables and finite-domains with increasing size, as well as hybrid constraints expressing increasing temporal precision. We show that while HCT reduces search complexity for all but the simplest problems, the relative effectiveness is dampened on problems with partially conditional temporal constraints and hybrid constraints with increasing temporal disjunctions. Finally, we present our preliminary investigations that indicate that HCT can assist in increasing communication efficacy in a multiagent setting.

AAMAS Conference 2007 Conference Paper

Making Social Choices from Individuals' CP-nets

• Keith Purrington
• Edmund H. Durfee

CP-nets are an attractive model for representing individual preferences, in part because they allow us to find the best outcome for an agent in time that is proportional to just the number of features in an outcome. In this paper, we investigate whether similar efficiencies can apply to finding the best social outcome for agents whose individual preferences are captured in CP-nets. Because CP-nets provide only qualitative information, we adopt a way to compare outcomes across agents based on each outcome's relative standing in the individuals' spaces of possible outcomes. This in turn guides the search through the outcome preference graphs that are induced by the agents' CP-nets to find the optimal social outcome. Because these induced preference graphs are exponential in the number of features, we examine the conditions under which the agents can search directly using their CP-nets, and show that our approach yields near-optimal social outcomes in exponentially less time.

AAMAS Conference 2007 Conference Paper

Sequential Resource Allocation in Multi-agent Systems with Uncertainties

• Jianhui Wu
• Edmund H. Durfee

Exchanging scarce resources during execution among a group of agents is one way to improve the overall performance in multi-agent systems with limited shared resources, but implementing optimal sequential resource allocation is often a nontrivial problem in complex systems with uncertainties. In this paper, we present an MILP-based algorithm that can automatically break a large mission into multiple phases and make optimal resource (re)allocations at the entry of each phase. We illustrate our algorithms through several increasingly complex classes of sequential resource allocation problems, and show through experiments that our techniques can increase agents' rewards for varying levels of constraints on resources and constraints on exchanging resources.

AAMAS Conference 2007 Conference Paper

Solving Large TÆMS Problems Efficiently by Selective Exploration and Decomposition

• Jianhui Wu
• Edmund H. Durfee

TÆMS is a hierarchical modeling language capable of representing complex task networks with intra-task uncertainties and inter-task dependencies. The uncertainty and complexity of the application domains represented in TÆMS models often lead to very large state spaces, which push the need to design efiient solution algorithms for TÆMS problems. In this paper, we present a solver that integrates selective state space search techniques with state space decomposition techniques. Our experiments demonstrate that the solver can find an (approximately) optimal solution much faster than prior approaches.

ICAPS Conference 2004 Conference Paper

Optimal Resource Allocation and Policy Formulation in Loosely-Coupled Markov Decision Processes

• Dmitri A. Dolgov
• Edmund H. Durfee

The problem of optimal policy formulation for teams of resource-limited agents in stochastic environments is composed of two strongly-coupled subproblems: a resource allocation problem and a policy optimization problem. We show how to combine the two problems into a single constrained optimization problem that yields optimal resource allocations and policies that are optimal under these allocations. We model the system as a multiagent Markov decision process (MDP), with social welfare of the group as the optimization criterion. The straightforward approach of modeling both the resource allocation and the actual operation of the agents as a multiagent MDP on the joint state and action spaces of all agents is not feasible, because of the exponential increase in the size of the state space. As an alternative, we describe a technique that exploits problem structure by recognizing that agents are only loosely-coupled via the shared resource constraints. This allows us to formulate a constrained policy optimization problem that yields optimal policies among the class of realizable ones given the shared resource limitations. Although our complexity analysis shows the constrained optimization problem to be NP-complete, our results demonstrate that, by exploiting problem structure and via a reduction to a mixed integer program, we are able to solve problems orders of magnitude larger than what is possible using a traditional multiagent MDP formulation.

IJCAI Conference 2003 Conference Paper

Approximating Optimal Policies for Agents with Limited Execution Resources

• Dmitri A. Dolgov
• Edmund H. Durfee

An agent with limited consumable execution resources needs policies that attempt to achieve good performance while respecting these limitations. Otherwise, an agent (such as a plane) might fail catastrophically (crash) when it runs out of resources (fuel) at the wrong time (in midair). We present a new approach to constructing policies for agents with limited execution resources that builds on principles of real-time Al, as well as research in constrained Markov decision processes. Specifically, we formulate, solve, and analyze the policy optimization problem where constraints are imposed on the probability of exceeding the resource limits. We describe and empirically evaluate our solution technique to show that it is computationally reasonable, and that it generates policies that sacrifice some potential reward in order to make the kinds of precise guarantees about the probability of resource overutilization that are crucial for missioncritical applications.

AAMAS Conference 2003 Conference Paper

Bounded-Optimal Policies for Agents with Resource-Limited Architectures

• Dmitri A. Dolgov
• Edmund H. Durfee

AAMAS Conference 2003 Conference Paper

Discovering and Exploiting Synergy Between Hierarchical Planning Agents

• Jeffrey S. Cox
• Edmund H. Durfee

AAMAS Conference 2003 Conference Paper

Multiagent Planning for Agents with Internal Execution Resource Constraints

• Haksun Li
• Edmund H. Durfee
• Kang G. Shin

AAMAS Conference 2003 Conference Paper

Resource Allocation for a Limited Real-time Agent

• Haksun Li
• Ella M. Atkins
• Edmund H. Durfee
• Kang G. Shin

AAMAS Conference 2002 Conference Paper

Congregating and Market Formation

• Christopher H. Brooks
• Edmund H. Durfee

AAMAS Conference 2002 Conference Paper

Satisficing Strategies for Resource-Limited Policy Search in Dynamic Environments

• Dmitri A. Dolgov
• Edmund H. Durfee

IROS Conference 2001 Conference Paper

Using abstraction to coordinate multiple robotic spacecraft

• Bradley J. Clement
• Anthony C. Barrett
• Gregg R. Rabideau
• Edmund H. Durfee

The trend toward multiple-spacecraft missions requires autonomous teams of spacecraft to coordinate their activities when sharing limited resources. The paper describes how an iterative repair planner/scheduler can reason about the activities of multiple spacecraft at abstract levels in order to greatly improve the scheduling of their use of shared resources. By finding consistent schedules at abstract levels, refinement choices can be preserved for use in robust plan execution systems. We present an algorithm for summarizing the metric resource requirements of an abstract activity based on the resource usages of its potential refinements. We find that reasoning about this summary information and that of state constraints can offer exponential improvements in the time to find consistent schedules with an iterative repair planner. We analytically describe the conditions under which these improvements are made and show that sometimes the extra overhead involved does not warrant their use. We apply these techniques within the ASPEN planner/scheduler to a domain where a team of rovers must coordinate their schedules to avoid conflicts over shared resources. Experiments using the ASPEN planner/scheduler in a Mars multi-rover domain support our analyses and compare techniques for controlling decomposition.

AAAI Conference 1999 Conference Paper

Theory for Coordinating Concurrent Hierarchical Planning Agents Using Summary Information

• Bradley J. Clement
• Edmund H. Durfee
• University of Michigan

Interactingagentsthat interleaveplanning, plan coordination, andplanexecution for hierarchical plans (e. g. HTNs or proceduresfor PRS)should reasonaboutabstract plans andtheir concurrent execution beforetheyare fully refined. Poordecisionsmade at abstractlevels canleadto costly backtracking or evenfailure. We claimthat better decisionsrequireinformation at abstractlevels that summarizes the preconditions andeffects that mustor may applywhen a plan is refined. Hereweformallycharacterizeconcurrenthierarchical plans anda method for deriving summary information for them, andweillustrate how summaryconditionscan be used to coordinatethe concurrent interactions of plansat differentlevels of abstraction. Theproperties of summary conditions andrules determining whatinteractions can or mightholdamong asynchronously executing plansare provento supportthe construction of soundand completecoordinationmechanisms for concurrent hierarchicalplanning agents.

IJCAI Conference 1997 Conference Paper

Development of Iterative Real-time Scheduler to Planner Feedback

• Charles B. McVey
• Ella M. Atkins
• Edmund H. Durfee
• Kang G. Shin

Planning for real-time applications involves decisions not only about what actions to take in what states to progress toward achieving goals (the traditional decision problem faced by AI planning systems), but also about how to realize those actions within hard real-time deadlines given the inherent limitations of an execution platform. Determining how to arrange actions in a sequence such that timely execution is guaranteed within constraints is a manifestation of the scheduling problem. All cases of the scheduling problem in any domain of nontrivial complexity are difficult to solve (NP-Hard). To more efficiently solve the real-time plan scheduling problem, we propose and analyze an iterative feedback/constraint relaxation method in which a scheduler and planner iteratively interact to efficiently develop a well-utilized schedule which includes as many planned actions as possible. This method has been successfully implemented within the Cooperative Intelligent Real-time Control Architecture (CIRCA).

AAAI Conference 1997 Short Paper

Development of Iterative Scheduler to Planner Feedback

• Charles B. McVey
• Edmund H. Durfee

UAI Conference 1996 Conference Paper

Plan Development using Local Probabilistic Models

• Ella M. Atkins
• Edmund H. Durfee
• Kang G. Shin

Approximate models of world state transitions are necessary when building plans for complex systems operating in dynamic environments. External event probabilities can depend on state feature values as well as time spent in that particular state. We assign temporally -dependent probability functions to state transitions. These functions are used to locally compute state probabilities, which are then used to select highly probable goal paths and eliminate improbable states. This probabilistic model has been implemented in the Cooperative Intelligent Real-time Control Architecture (CIRCA), which combines an AI planner with a separate real-time system such that plans are developed, scheduled, and executed with real-time guarantees. We present flight simulation tests that demonstrate how our probabilistic model may improve CIRCA performance.

AIJ Journal 1995 Journal Article

World modeling for the dynamic construction of real-time control plans

• David J. Musliner
• Edmund H. Durfee
• Kang G. Shin

As intelligent, autonomous systems are embedded in critical real-world environments, it becomes increasingly important to rigorously characterize how these systems will perform. Research in real-time computing and control has developed ways of proving that a given control system will meet the demands of an environment, but has not addressed the dynamic planning of control actions. Building an agent that can flexibly achieve its goals in changing environments requires a blending of real-time computing and AI technologies. The Cooperative Intelligent Real-time Control Architecture (CIRCA) implements this blending by executing complex AI methods and guaranteed real-time control plans on separate subsystems. We describe the formal model of agent/environment interactions that CIRCA uses to build control plans, and we show how those control plans are guaranteed to meet domain requirements. CIRCA's world model provides the information required to make real-time performance guarantees, but avoids unnecessary complexity.

UAI Conference 1994 Conference Paper

The Automated Mapping of Plans for Plan Recognition

• Marcus J. Huber
• Edmund H. Durfee
• Michael P. Wellman

To coordinate with other agents in its environment, an agent needs models of what the other agents are trying to do. When communication is impossible or expensive, this information must be acquired indirectly via plan recognition. Typical approaches to plan recognition start with a specification of the possible plans the other agents may be following, and develop special techniques for discriminating among the possibilities. Perhaps more desirable would be a uniform procedure for mapping plans to general structures supporting inference based on uncertain and incomplete observations. In this paper, we describe a set of methods for converting plans represented in a flexible procedural language to observation models represented as probabilistic belief networks.

IJCAI Conference 1993 Conference Paper

Elements of a Utilitarian Theory of Knowledge and Action

• Piotr J. Gmytrasiewicz
• Edmund H. Durfee

According to the utilitarian paradigm, an autonomous intelligent agent's interactions with the environment should be guided by the principle of expected utility maximization. We apply this paradigm to reasoning about an agent's physical actions and exploratory behavior in urgent, time-constrained situations. We model an agent's knowledge with a temporalized version of Kripke structures—as a set of branching time lines described by fluents, with accessibility relations holding among the states comprising the time lines. We describe how to compute utility based on this model which reflects the urgency that the environment imposes on time. Since the physical and exploratory actions that an agent could undertake transform the model of branching time lines in specific ways, the expected utilities of these actions can be computed, dictating rational tradeoffs among them depending on the agent's state of knowledge and the urgency of the situation.

AAAI Conference 1993 Conference Paper

Overeager Reciprocal Rationality and Mixed Strategy Equilibria

• Edmund H. Durfee

IJCAI Conference 1991 Conference Paper

A Decision-Theoretic Approach to Coordinating Multi-agent Interactions

• Piotr J. Gmytrasiewicz
• Edmund H. Durfee
• David K

AAAI Conference 1990 Conference Paper

A Hierarchical Protocol for Coordinating Mulitagent Behaviors

• Edmund H. Durfee

AAAI Conference 1988 Conference Paper

Predictability Versus Responsiveness: Coordinating Problem Solvers in Dynamic Domains

• Edmund H. Durfee

Coordination in dynamic domains involves balancing predictability and responsiveness: agents must be predictable enough to anticipate and plan future interactions while being responsive enough to react to unexpected situations. The partial global planning approach to coordination provides a framework for flexibly balancing these opposing needs. In this approach, agents communicate about their current local plans to build up partial global plans (PGPs) that specify cooperative actions and interactions. When their plans change, agents must decide whether the time and effort of reformulating their PGPs is worthwhile, or whether working predictably with slightly out-of-date PGPs is more cost effective. In this paper, we briefly outline the partial global planning approach, discuss how it flexibly balances predictability and responsiveness, and experimentally show how different balances affect behavior in a simulated problem-solving network.

IJCAI Conference 1987 Conference Paper

Using Partial Global Plans to Coordinate Distributed Problem Solvers

• Edmund H. Durfee
• Victor R. Lesser

Communicating problem solvers can cooperate in various ways, such as negotiating over task assignments, exchanging partial solutions to converge on global results, and planning interactions that help each other perform their tasks better. We introduce a new framework that supports different styles of cooperation by using partial global plana to specify effective, coordinated actions for groups of problem solvers. In this framework, problem solvers summarise their local plans into node-plant that they selectively exchange to dynamically model network activity and to develop partial global plans. However, because network and problem characteristics can change and communication channels have delays and limited capacity, problem solvers' models and partial global plans may be incomplete, out-of-date, and inconsistent. Our mechanisms allow problem solvers to agree on consistent partial global plans when possible, and to locally form partial global plans that lead to satisfactory cooperation even in rapidly changing environments where complete agreement is impossible. In this paper, we describe the mechanisms, knowledge representations, and algorithms that we have developed for generating and maintaining partial global plans in a distributed system. We use experiments to illustrate how these mechanisms improve and promote cooperation in a variety of styles.

AAAI Conference 1986 Conference Paper

Incremental Planning to Control a Blackboard-based Problem Solver

• Edmund H. Durfee

To control problem solving activity, a planner must resolve uncertainty about which specific long-term goals (solutions) to pursue and about which sequences of actions will best achieve those goals. In this paper, we describe a planner that abstracts the problem solving state to recognize possible competing and compatible solutions and to roughly predict the importance and expense of developing these solutions. With this information, the planner plans sequences of problem solving activities that most efficiently resolve its uncertainty about which of the possible solutions to work toward. The planner only details actions for the near future because the results of these actions will influence how (and whether) a plan should be pursued. As problem solving proceeds, the planner adds new details to the plan incrementally, and monitors and repairs the plan to insure it achieves its goals whenever possible. Through experiments, we illustrate how these new mechanisms significantly improve problem solving decisions and reduce overall computation. We briefly discuss our current research directions, including how these mechanisms can improve a problem solver’s real-time response and can enhance cooperation in a distributed problem solving network.

IJCAI Conference 1985 Conference Paper

Increasing Coherence in a Distributed Problem-Solving Network

• Edmund H. Durfee
• Victor R. Lesser
• Daniel D. Corkill