We develop a novel circuit-level stochastic local search (SLS) method D-CRSat for Boolean satisfiability by integrating a structure-based heuristic into the recent CRSat algorithm. D-CRSat significantly improves on CRSat on real-world application benchmarks on which other current CNF and circuit-level SLS methods tend to perform weakly. We also give an intricate proof of probabilistically approximate completeness for D-CRSat, highlighting key features of the method.

The Partner Units Problem is a specific type of configuration problem with important applications in the area of surveillance and security. In this work we show that a special case of the problem, that is of great interest to our partners in industry, can directly be tackled via a structural problem decompostion method. Combining these theoretical insights with general purpose AI techniques such as constraint satisfaction and SAT solving proves to be particularly effective in practice.

Multi-Agent Plan Recognition (MAPR) seeks to proposed to formalize MAPR with a new model, revealing identify the dynamic team structures and team behaviors the distinction between the hardness of single and multi-agent from the observed activity sequences (team plan recognition, and solve MAPR problems in the model using traces) of a set of intelligent agents, based on a a first-cut approach, provided that a fully observed team library of known team activity sequences (team trace and a library of full team plans were given as input plans). Previous MAPR systems require that team [Banerjee et al., 2010]; etc. traces and team plans are fully observed. In this Despite the success of previous approaches, they either assume paper we relax this constraint, i.e., team traces and that agents in the same team can only execute a common team plans are allowed to be partial. This is an important activity, i.e., coordinated activities of agents are not allowed task in applying MAPR to real-world domains, in a team, or require that the team trace and team plans are since in many applications it is often difficult complete, i.e., missing values (activities that are missing) are to collect full team traces or team plans due not allowed. In many real-world applications, however, it is to environment limitations, e.g., military operation.

We study distributed task-allocation problems wherecooperative agents need to perform some tasks simultaneously. Examples are multi-agent routing problems where several agents need to visit some targets simultaneously, for example, to move obstacles out of the way cooperatively. In this paper, we first generalize the concept of reaction functions proposed in the literature to characterize the agent costs of performing multiple complex tasks. Second, we show how agents can construct and approximate reaction functions in a distributed way. Third, we show how reaction functions can be used by an auction-like algorithm to allocate tasks to agents. Finally, we show empirically that the team costs of our algorithms are substantially smaller than those of an existing state-of-the-art allocation algorithm for complex tasks.

This paper examines an extended double auction model where market clearing is restricted by temporal constraints. It is found that the allocation problem in this model can be effectively transformed into a weighted bipartite matching in graph theory. By using the augmentation technique, we propose a Vickrey-Clarke-Groves (VCG) mechanism in this model and demonstrate the advantages of the payment compared with the classical VCG payment (the Clarke pivot payment). We also show that the algorithms for both allocation and payment calculation run in polynomial time. It is expected that the method and results provided in this paper can be applied to the design and analysis of dynamic double auctions and futures markets.

Continuous state DEC-MDPs are critical for agent teams in domains involving resources such as time, but scaling them up is a significant challenge. To meet this challenge, we first introduce a novel continuous-time DEC-MDP model that exploits transition independence in domains with temporal constraints. Moreimportantly, we present a new locally optimal algorithm called SPAC. Compared to the best previous algorithm, SPAC finds solutions of comparable quality substantially faster; SPAC also scales to larger teams of agents.

Computing the market maker price of a security in a combinatorial prediction market is #P-hard. We devise a fully polynomial randomized approximation scheme (FPRAS) that computes the price of any security in disjunctive normal form (DNF) within an ε multiplicative error factor in time polynomial in 1ε and the size of the input, with high probability and under reasonable assumptions. Our algorithm is a Monte-Carlo technique based on importance sampling. The algorithm can also approximately price securities represented in conjunctive normal form (CNF) with additive error bounds. To illustrate the applicability of our algorithm, we show that many securities in Yahoo!'s popular combinatorial prediction market game called Predictalot can be represented by DNF formulas of polynomial size.

In many of the possible applications as well as the theoretical models of computational social choice,the agents’ preferences are represented as partialorders. In this paper, we extend the maximum likelihood approach for defining “optimal” voting rules to this setting. We consider distributions in which the pairwise comparisons / incomparabilities between alternatives are drawn i.i.d. We call suchmodels pairwise-independentmodels and show that they correspond to a class of voting rules that we call pairwise scoring rules. This generalizes rulessuch as Kemeny and Borda. Moreover, we show that Borda is the only pairwise scoring rule that satisfies neutrality, when the outcome space is the set of all alternatives. We then study which voting rules defined for linear orders can be extended to partial orders via our MLE model. We show that any weakly neutral outcome scoring rule (includingany ranking/candidate scoring rule) based onthe weighted majority graph can be represented as the MLE of a weakly neutral pairwise-independent model. Therefore, all such rules admit natural extensionsto profiles of partial orders. Finally, we propose a specific MLE model π k for generating a set of k winning alternatives, and study the computational complexity of winner determination for the MLE of π k .

We propose a novel online planning algorithm for ad hoc team settings — challenging situations in which an agent must collaborate with unknown teammates without prior coordination. Our approach is based on constructing and solving a series of stage games, and then using biased adaptive play to choose actions. The utility function in each stage game is estimated via Monte-Carlo tree search using the UCT algorithm. We establish analytically the convergence of the algorithm and show that it performs well in a variety of ad hoc team domains.

In multi-issue automated negotiation against unknown opponents, a key part of effective negotiation is the choice of concession strategy. In this paper, we develop a principled concession strategy, based on Gaussian processes predicting the opponent's future behaviour. We then use this to set the agent's concession rate dynamically during a single negotiation session. We analyse the performance of our strategy and show that it outperforms the state-of-the-art negotiating agents from the 2010 Automated Negotiating Agents Competition, in both a tournament setting and in self-play, across a variety of negotiation domains.