In the efficient social choice problem, the goal is to assign values, subject to side constraints, to a set of variables to maximize the total utility across a population of agents, where each agent has private information about its utility function. In this paper we model the social choice problem as a distributed constraint optimization problem (DCOP), in which each agent can communicate with other agents that share an interest in one or more variables. Whereas existing DCOP algorithms can be easily manipulated by an agent, either by misreporting private information or deviating from the algorithm, we introduce M-DPOP, the first DCOP algorithm that provides a faithful distributed implementation for efficient social choice. This provides a concrete example of how the methods of mechanism design can be unified with those of distributed optimization. Faithfulness ensures that no agent can benefit by unilaterally deviating from any aspect of the protocol, neither information-revelation, computation, nor communication, and whatever the private information of other agents. We allow for payments by agents to a central bank, which is the only central authoritythat we require. To achieve faithfulness, we carefully integrate the Vickrey-Clarke-Groves (VCG) mechanism with the DPOP algorithm, such that each agent is only asked to perform computation, report information, and send messages that is in its own best interest. Determining agent i's payment requires solving the social choice problem without agent i. Here, we present a method to reuse computation performed in solving the main problem in a way that is robust against manipulation by the excluded agent. Experimental results on structured problems show that as much as 87% of the computation required for solving the marginal problems can be avoided by re-use, providing very good scalability in the number of agents. On unstructured problems, we observe a sensitivity of M-DPOP to the density of the problem, and we show that reusability decreases from almost 100% for very sparse problems to around 20% for highly connected problems. We close with a discussion of the features of DCOP that enable faithful implementations in this problem, the challenge of reusing computation from the main problem to marginal problems in other algorithms such as ADOPT and OptAPO, and the prospect of methods to avoid the welfare loss that can occur because of the transfer of payments to the bank.

In fact, DARPA, which funded the project, ways. Elves) (Scerri, Pynadath, and Tambe 2002; Finally, we will present some lessons Pynadath and Tambe 2003) and required learned and recent research that was motivated detailed information about the calendars by our experiences in deploying the of people using the system. Thus, we decided to deploy a new application of the Electric The Travel Elves introduced two major Elves, called the Travel Elves. This application advantages over traditional approaches to appeared to be ideal for wider deployment travel planning. First, the Travel Elves provided since it could be hosted entirely outside an interactive approach to making an organization and communication travel plans in which all of the data could be performed over wireless devices, required to make informed choices is such as cellular telephones. For example, when The mission of the Travel Elves (Ambite deciding whether to park at the airport or et al. 2002, Knoblock 2004) was to facilitate take a taxi, the system compares the cost planning a trip and to ensure that the of parking and the cost of a taxi given other resulting travel plan would execute selections, such as the airport, the specific smoothly. Initial deployment of the Travel parking lot, and the starting location Elves at DARPA went smoothly.

This was a large applied research effort that presented many opportunities for unusual experiences. In one such experience, I was called in, at the last minute, to help improve our ALV proposal. The proposal was a 300-page document that segued smoothly from problem description to corporate capabilities and managerial plan, omitting any mention of technical approach. This taught me a rule of thumb I have seen validated many times: the larger the project (in dollars and scope), the poorer the technical proposal. In a second experience, I was demonstrating a dynamic programming algorithm at a quarterly review.

Software personal assistants continue to be a topic of significant research interest. This article outlines some of the important lessons learned from a successfully-deployed team of personal assistant agents (Electric Elves) in an office environment. In the Electric Elves project, a team of almost a dozen personal assistant agents were continually active for seven months. Each elf (agent) represented one person and assisted in daily activities in an actual office environment. This project led to several important observations about privacy, adjustable autonomy, and social norms in office environments. In addition to outlining some of the key lessons learned we outline our continued research to address some of the concerns raised.

On March 27, 2006, I gave a light-hearted and occasionally bittersweet presentation on “Whatever Happened to AI?” at the Stanford Spring Symposium presentation – to a lively audience of active AI researchers and formerly-active ones (whose current inaction could be variously ascribed to their having aged, reformed, given up, redefined the problem, etc.)  This article is a brief chronicling of that talk, and I entreat the reader to take it in that spirit: a textual snapshot of a discussion with friends and colleagues, rather than a scholarly article. I begin by whining about the Turing Test, but only for a thankfully brief bit, and then get down to my top-10 list of factors that have retarded progress in our field, that have delayed the emergence of a true strong AI.

Crisis events, like the 9.11 attack, Hurricane Katrina and the tsunami devastation, have dramatic impact on human society, economy and environment. The crisis response term is defined as the immediate protection of property and life during the crises events to reduce deaths and injuries. Crisis response requires urgent action and the coordinated application of resources, facilities, and efforts. It includes actions taken before the actual crisis event (e.g., hurricane warning is received), in response to the immediate impact of a crisis, and as sustained effort during the course of the crisis. Depending upon the magnitude and complexity of the crisis, response may be a large-scale and multiorganizational operation involving many layers of authorities, commercial entities, volunteer organizations, media organizations, and the public.

Multi-agent planning in stochastic environments can be framed formally as a decentralized Markov decision problem. Many real-life distributed problems that arise in manufacturing, multi-robot coordination and information gathering scenarios can be formalized using this framework. However, finding the optimal solution in the general case is hard, limiting the applicability of recently developed algorithms. This paper provides a practical approach for solving decentralized control problems when communication among the decision makers is possible, but costly. We develop the notion of communication-based mechanism that allows us to decompose a decentralized MDP into multiple single-agent problems. In this framework, referred to as decentralized semi-Markov decision process with direct communication (Dec-SMDP-Com), agents operate separately between communications. We show that finding an optimal mechanism is equivalent to solving optimally a Dec-SMDP-Com. We also provide a heuristic search algorithm that converges on the optimal decomposition. Restricting the decomposition to some specific types of local behaviors reduces significantly the complexity of planning. In particular, we present a polynomial-time algorithm for the case in which individual agents perform goal-oriented behaviors between communications. The paper concludes with an additional tractable algorithm that enables the introduction of human knowledge, thereby reducing the overall problem to finding the best time to communicate. Empirical results show that these approaches provide good approximate solutions.

Ontologies and automated reasoning are the building blocks of the Semantic Web initiative. Derivation rules can be included in an ontology to define derived concepts, based on base concepts. For example, rules allow to define the extension of a class or property, based on a complex relation between the extensions of the same or other classes and properties. On the other hand, the inclusion of negative information both in the form of negation-as-failure and explicit negative information is also needed to enable various forms of reasoning. In this paper, we extend RDF graphs with weak and strong negation, as well as derivation rules. The ERDF stable model semantics of the extended framework (Extended RDF) is defined, extending RDF(S) semantics. A distinctive feature of our theory, which is based on Partial Logic, is that both truth and falsity extensions of properties and classes are considered, allowing for truth value gaps. Our framework supports both closed-world and open-world reasoning through the explicit representation of the particular closed-world assumptions and the ERDF ontological categories of total properties and total classes.

We discuss a generic model of Bayesian inference with binary variables defined on edges of a planar graph. The Loop Calculus approach of [1, 2] is used to evaluate the resulting series expansion for the partition function. We show that, for planar graphs, truncating the series at single-connected loops reduces, via a map reminiscent of the Fisher transformation [3], to evaluating the partition function of the dimer matching model on an auxiliary planar graph. Thus, the truncated series can be easily re-summed, using the Pfaffian formula of Kasteleyn [4]. This allows to identify a big class of computationally tractable planar models reducible to a dimer model via the Belief Propagation (gauge) transformation. The Pfaffian representation can also be extended to the full Loop Series, in which case the expansion becomes a sum of Pfaffian contributions, each associated with dimer matchings on an extension to a subgraph of the original graph. Algorithmic consequences of the Pfaffian representation, as well as relations to quantum and non-planar models, are discussed.

We provide deterministic, polynomial-time computable voting rules that approximate Dodgson's and (the ``minimization version'' of) Young's scoring rules to within a logarithmic factor. Our approximation of Dodgson's rule is tight up to a constant factor, as Dodgson's rule is $\NP$-hard to approximate to within some logarithmic factor. The ``maximization version'' of Young's rule is known to be $\NP$-hard to approximate by any constant factor. Both approximations are simple, and natural as rules in their own right: Given a candidate we wish to score, we can regard either its Dodgson or Young score as the edit distance between a given set of voter preferences and one in which the candidate to be scored is the Condorcet winner. (The difference between the two scoring rules is the type of edits allowed.) We regard the marginal cost of a sequence of edits to be the number of edits divided by the number of reductions (in the candidate's deficit against any of its opponents in the pairwise race against that opponent) that the edits yield. Over a series of rounds, our scoring rules greedily choose a sequence of edits that modify exactly one voter's preferences and whose marginal cost is no greater than any other such single-vote-modifying sequence.