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.

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.

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.

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.

In finite decision problems where an agent can query its human user to obtain information about its environment before acting, a query’s usefulness is in terms of its Expected Value of Information (EVOI). The usefulness of a query set is similarly measured in terms of the EVOI of the queries it contains. When the only constraint on what queries can be asked is that they have exactly k possible responses (with k \ge 2), we show that the set of k-response decision queries (which ask the user to select his/her preferred decision given a choice of k decisions) is EVOI-Sufficient, meaning that no single k-response query can have higher EVOI than the best single k-response decision query for any decision problem. When multiple queries can be asked before acting, we provide a negative result that shows the set of depth-n query trees constructed from k-response decision queries is not EVOI-Sufficient. However, we also provide a positive result that the set of depth-n query trees constructed from k-response decision-set queries, which ask the user to select from among k sets of decisions as to which set contains the best decision, is EVOI-Sufficient. We conclude with a discussion and analysis of algorithms that draws on a connection to other recent work on decision-theoretic knowledge elicitation.

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.

This research focuses on building foundational algorithms for scheduling agents that assist people in managing their activities in environments where tempo and complex activity interdependencies outstrip people's cognitive capacity. We address the critical challenge of reasoning over individuals' interacting schedules to efficiently answer queries about how to meet scheduling goals while respecting individual privacy and autonomy to the extent possible. We formally define the Multiagent Simple Temporal Problem for naturally capturing and reasoning over the distributed but interconnected scheduling problems of multiple individuals. Our hypothesis is that combining bottom-up and top-down approaches will lead to effective solution techniques. In our bottom-up phase, an agent externalizes constraints that compactly summarize how its local subproblem affects other agents' subproblems, whereas in our top-down phase an agent proactively constructs and internalizes new local constraints that decouple its subproblem from others'. We confirm this hypothesis by devising distributed algorithms that calculate summaries of the joint solution space for multiagent scheduling problems, without centralizing or otherwise redistributing the problems. The distributed algorithms permit concurrent execution to achieve significant speedup over the current art and also increase the level of privacy and independence in individual agent reasoning. These algorithms are most advantageous for problems where interactions between the agents are sparse compared to the complexity of agents' individual problems.

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.

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.

Because an agent's resources dictate what actions it can possibly take, it should plan which resources it holds over time carefully, considering its inherent limitations (such as power or payload restrictions), the competing needs of other agents for the same resources, and the stochastic nature of the environment. Such agents can, in general, achieve more of their objectives if they can use --- and even create --- opportunities to change which resources they hold at various times. Driven by resource constraints, the agents could break their overall missions into an optimal series of phases, optimally reconfiguring their resources at each phase, and optimally using their assigned resources in each phase, given their knowledge of the stochastic environment. In this paper, we formally define and analyze this constrained, sequential optimization problem in both the single-agent and multi-agent contexts. We present a family of mixed integer linear programming (MILP) formulations of this problem that can optimally create phases (when phases are not predefined) accounting for costs and limitations in phase creation. Because our formulations multaneously also find the optimal allocations of resources at each phase and the optimal policies for using the allocated resources at each phase, they exploit structure across these coupled problems. This allows them to find solutions significantly faster(orders of magnitude faster in larger problems) than alternative solution techniques, as we demonstrate empirically.

Except in very controlled or fortuitous circumstances, good coordination between agents does not spontaneously occur. In general, agents need to plan for coordination, anticipating how their activities can affect each other and choosing actions that dovetail well together to achieve their separate and common goals. Of course, this is easier said than done, since the potential space of agents' action and interaction sequences to consider is intractable. I discuss some technologies that make it practical to plan for good coordination by exploiting algorithmic, representational, and problem-specific structure. Furthermore, when conducted by the involved agents, the processes for planning coordination need to be coordinated themselves. Toward this end, I also outline meta-level strategies for coordinating the agents' planning processes.

Allocating scarce resources among agents to maximize global utility is, in general, computationally challenging. We focus on problems where resources enable agents to execute actions in stochastic environments, modeled as Markov decision processes (MDPs), such that the value of a resource bundle is defined as the expected value of the optimal MDP policy realizable given these resources. We present an algorithm that simultaneously solves the resource-allocation and the policy-optimization problems. This allows us to avoid explicitly representing utilities over exponentially many resource bundles, leading to drastic (often exponential) reductions in computational complexity. We then use this algorithm in the context of self-interested agents to design a combinatorial auction for allocating resources. We empirically demonstrate the effectiveness of our approach by showing that it can, in minutes, optimally solve problems for which a straightforward combinatorial resource-allocation technique would require the agents to enumerate up to 2^100 resource bundles and the auctioneer to solve an NP-complete problem with an input of that size.

As computational agents are developed for increasingly complicated e-commerce applications, the complexity of the decisions they face demands advances in artificial intelligence techniques. For example, an agent representing a seller in an auction should try to maximize the seller?s profit by reasoning about a variety of possibly uncertain pieces of information, such as the maximum prices various buyers might be willing to pay, the possible prices being offered by competing sellers, the rules by which the auction operates, the dynamic arrival and matching of offers to buy and sell, and so on. A naive application of multiagent reasoning techniques would require the seller?s agent to explicitly model all of the other agents through an extended time horizon, rendering the problem intractable for many realistically-sized problems. We have instead devised a new strategy that an agent can use to determine its bid price based on a more tractable Markov chain model of the auction process. We have experimentally identified the conditions under which our new strategy works well, as well as how well it works in comparison to the optimal performance the agent could have achieved had it known the future. Our results show that our new strategy in general performs well, outperforming other tractable heuristic strategies in a majority of experiments, and is particularly effective in a 'seller?s market', where many buy offers are available.

No abstract available.

As online markets for the exchange of goods and services become more common, the study of markets composed, at least in part, of autonomous agents has taken on increasing importance. In contrast to traditional complete–information economic scenarios, agents that are operating in an electronic marketplace often do so under considerable uncertainty. In order to reduce their uncertainty, these agents must learn about the world around them. When an agent producer is engaged in a learning task in which data collection is costly, such as learning the preferences of a consumer population, it is faced with a classic decision problem: when to explore and when to exploit. If the agent has a limited number of chances to experiment, it must explicitly consider the cost of learning (in terms of foregone profit) against the value of the information acquired. Information goods add an additional dimension to this problem; due to their flexibility, they can be bundled and priced according to a number of different price schedules. An optimizing producer should consider the profit each price schedule can extract, as well as the difficulty of learning of this schedule. In this paper, we demonstrate the tradeoff between complexity and profitability for a number of common price schedules. We begin with a one–shot decision as to which schedule to learn. Schedules with moderate complexity are preferred in the short and medium term, as they are learned quickly, yet extract a significant fraction of the available profit. We then turn to the repeated version of this one–shot decision and show that moderate complexity schedules, in particular two–part tariff, perform well when the producer must adapt to nonstationarity in the consumer population. When a producer can dynamically change schedules as it learns, it can use an explicit decision–theoretic formulation to greedily select the schedule which appears to yield the greatest profit in the next period. By explicitly considering both the learnability and the profit extracted by different price schedules, a producer can extract more profit as it learns than if it naively chose models that are accurate once learned.

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.

Electronic goods are flexible and have negligible marginal costs. These features allow a producer of electronic goods to explore pricing schemes, and in particular bundling, that would not be feasible with physical goods. However, they can also make it more difficult for a producer to differentiate itself from competitors offering identical goods. Previous research in this area indicates that in markets where producers compete over the sale of identical information goods, cyclical price wars often develop. In this paper, we provide a characterization of the conditions that result in price wars and show analytically how the existence of niches within the consumer population can lead duopolist producers to each target separate niches and avoid price wars. In situations where producers have incomplete information about consumer preferences, and so must learn a strategy, producers will be concerned not only with the relative benefits of niche targeting as opposed to a price war, but also with th...

In an automated market for electronic goods new problems arise that have not been well studied previously. For example, information goods are very flexible. Marginal costs are negligible and nearly limitless bundling and unbundling of these items are possible, in contrast to physical goods. Consequently, producers can offer complex pricing schemes. However, the profit-maximizing design of a complex pricing schedule depends on a producer's knowledge of the distribution of consumer preferences for the available information goods. Preferences are private and can only be gradually uncovered through market experience. In this paper we compare dynamic performance across price schedules of varying complexity. We provide the producer with two machine learning methods producer that is performing a naive, knowledge-free form of leanings (function approximation and hill-climbing) which implement a strategy that balances exploitation to maximize current profits against exploration of the profit landscape to improve future profits. We find that the tradeoff between exploitation and exploration is different depending on the learning algorithms employed, and in particular depending on the complexity of the price schedule that if offered. In general, simpler price schedules are more robust and give up less profit during the learning periods even though in our stationary environment learning eventually is complete and the more complex schedules have high long-run profits. These results hold for both learning methods, even though the relative performance of the methods is quite sensitive to choice of initial conditions and differences in the smoothness of the profit landscape for different price schedules. Our results have implications for automated learning and strategic pricing in non-stationary environments, which arise when the consumer population changes, individuals change their preferences, or competing firms change their strategies.

. We present our approach to the problem of how an agent, within an economic multi-agent system, can determine when it should behave strategically (i.e. learn and use models of other agents), and when it should act as a simple price-taker. We provide a framework for the incremental implementation of modelling capabilities in agents, and a description of the forms of knowledge required. The agents were implemented and different populations simulated in order to learn more about their behaviour and the merits of using and learning agent models. Our results show, among other lessons, how savvy buyers can avoid being ‘cheated’ by sellers, how price volatility can be used to quantitatively predict the benefits of deeper models, and how specific types of agent populations influence system behaviour.

We develop a formalism called a distributed constraint satisfaction problem (distributed CSP) and algorithms for solving distributed CSPs. A distributed CSP is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various application problems in distributed artificial intelligence can be formalized as distributed CSPs. We present our newly developed technique called asynchronous backtracking that allows agents to act asynchronously and concurrently without any global control, while guaranteeing the completeness of the algorithm. Furthermore, we describe how the asynchronous backtracking algorithm can be modified into a more efficient algorithm called an asynchronous weak-commitment search, which can revise a bad decision without exhaustive search by changing the priority order of agents dynamically. The experimental results on various example problems show that the asynchronous weak-commitment search algorithm is, by far more, efficient than the asynchronous backtracking algorithm and can solve fairly large-scale problems.

Cooperative information agents need mechanisms that enable them to work together effectively while solving common problems. We investigate the use of commitment by agents to proposed actions as a mechanism that allow agents to work concurrently on interdependent problems. Judicious use of commitment can not only increase the throughput of cooperative information systems, but also allow them to deal flexibly with dynamically changing environments. We use the domain of distributed scheduling to demonstrate that static commitment strategies are ineffective. Results from simulated experiments are used to identify the environmental features on which an adaptive commitment strategy should be predicated.

Most research into applying AI techniques to real-time control problems has limited the power of AI methods or embedded reactivity in an AI system. An alternative, cooperative architecture is presented. It uses separate AI and real-time subsystems to address the problems for which each is designed. A structured interface allows the subsystems to communicate without compromising their respective performance goals. By reasoning about its own bounded reactivity, cooperative intelligent real-time control architecture (CIRCA) can guarantee that it will meet hard deadlines while still using unpredictable AI methods. With its abilities to guarantee or trade off the timeliness, precision, confidence, and completeness of its output, CIRCA provides more flexible performance than previous systems.>

Viewing cooperative distributed problem solving (CDPS) as distributed constraint satisfaction provides a useful formalism for characterizing CDPS techniques. This formalism and algorithms for solving distributed constraint satisfaction problems (DCSPs) are compared. A technique called asynchronous backtracking that allows agents to act asynchronously and concurrently, in contrast to the traditional sequential backtracking techniques used in constraint satisfaction problems, is presented. Experimental results show that solving DCSPs in a distributed fashion is worthwhile when the problems solved by individual agents are loosely coupled.>

A distributed computer network management system consisting of cooperating autonomous computing agents allows network management to be more responsive due to information gathering and network recovery activities being performed in parallel. However, to perform these tasks, the network of agents requires a stable organizational infrastructure. In addition, to meet the needs of human network administrators, the distributed system must allow ultimate authority to be centralized at a single location. Distributed Big Brother (DBB) represents a pragmatic blending of diverse technologies from the field of distributed AI, such as contract formation, organizational structuring, election for role assignment, and hierarchical control. The result is an infrastructure for a network management system in which separate agents reconfigure themselves when hardware and software failures occur in order to assure the authority structure demanded by network operators. Our efforts illustrate how integrating existing distributed AI technologies can meet realistic needs, and highlight open problems that require the development of new technologies.

Partial global planning is used to provide a framework for coordinating multiple AI systems that are cooperating in a distributed sensor network. By combining a variety of coordination techniques into a single, unifying framework, partial global planning enables separate AI systems to reason about their roles and responsibilities as part of group problem solving, and to modify their planned processing and communication actions to act as a more coherent team. Partial global planning is uniquely suited for coordinating systems that are working in continuous, dynamic, and unpredictable domains because it interleaves coordination with action and allows systems to make effective decisions despite incomplete and possibly obsolete information about network activity. The authors implement and evaluate partial global planning in a simulated vehicle monitoring application and identifying promising extensions to the framework.>

It is theorized that the process of coordination is a distributed search through a hierarchical space of agent behaviors. By specifying agent activities along multiple dimensions and at different levels of abstraction, the hierarchical behavior space provides a single, rich representation that agents can use to organize, plan, and schedule their collective actions. A computational instance of the evolving theory, which implements a particular choice of distributed protocol, local algorithm, metrics, and heuristics, as applied to resolving resource conflicts in an unstructured delivery domain, is described. In this domain, agents that initially do not know with whom they might interact exploit the hierarchical behavior representation to selectively exchange more details about themselves until they can resolve conflicting behaviors. It was experimentally demonstrated how the hierarchical protocol and multidimensional representation provide powerful and practical mechanisms for coordinating these agents, and important research issues to be addressed are highlighted.>

The authors present an overview of cooperative distributed problem solving (CDPS), an emerging research area that combines aspects of AI (artificial intelligence) and distributed processing. CDPS can be used to study how a loosely coupled network of sophisticated problem-solving nodes can solve a complex problem which consists of a set of interdependent subproblems. Subproblems arise because of spatial, temporal, and functional distribution of data, knowledge, and processing capabilities. Application areas include distributed interpretation, distributed planning and control, cooperating expert systems, and computer-supported human cooperation. The authors survey the important approaches and empirical investigations that have been developed. The approaches covered include negotiation, functionally accurate cooperation, organizational structuring, multiagent planning, sophisticated local control, and theoretical frameworks.>

When two or more computing agents work on interacting tasks, their activities should be coordinated so that they cooperate coherently. Coherence is particularly problematic in domains where each agent has only a limited view of the overall task, where communication between agents is limited, and where there is no ``controller'' to coordinate the agents. Our approach to coherent cooperation in such domains is developed in the context of a distributed problem-solving network where agents cooperate to solve a single problem. The approach stresses the importance of sophisticated local control by which each problem-solving node integrates knowledge of the problem domain with (meta-level) knowledge about network coordination. This allows nodes to make rapid, intelligent local decisions based on changing problem characteristics with only a limited amount of intercommunication to coordinate these decisions. We describe three mechanisms that improve network coherence: 1) an organizational structure that provides a long-term framework for network coordination to guide each node's local control decisions; 2) a planner at each node that develops sequences of problem-solving activities based on the current situation; and 3) meta-level communication about the current state of local problem solving that enables nodes to dynamically refine the organization. We present a variety of problem-solving situations to show the benefits and limitations of these mechanisms, and we provide simulation results showing the mechanisms to be particularly cost effective in more complex problem-solving situations. We also discuss how these mechanisms might be of more general use in other distributed computing applications.