Multi-agent path planning on grid maps is a challenging problem and has numerous real-life applications. Running a centralized, systematic search such as A* is complete and cost-optimal but scales up poorly in practice, since both the search space and the branching factor grow exponentially in the number of mobile units. Decentralized approaches, which decompose a problem into several subproblems, can be faster and can work for larger problems. However, existing decentralized methods offer no guarantees with respect to completeness, running time, and solution quality. To address such limitations, we introduce MAPP, a tractable algorithm for multi-agent path planning on grid maps. We show that MAPP has low-polynomial worst-case upper bounds for the running time, the memory requirements, and the length of solutions. As it runs in low-polynomial time, MAPP is incomplete in the general case. We identify a class of problems for which our algorithm is complete. We believe that this is the first study that formalises restrictions to obtain a tractable class of multi-agent path planning problems.

Computing a Nash equilibrium in multiplayer stochastic games is a notoriously difficult problem. Prior algorithms have been proven to converge in extremely limited settings and have only been tested on small problems. In contrast, we recently presented an algorithm for computing approximate jam/fold equilibrium strategies in a three-player no-limit Texas hold'em tournament — a very large real-world stochastic game of imperfect information. In this paper we show that it is possible for that algorithm to converge to a non-equilibrium strategy profile. However, we develop an ex post procedure that determines exactly how much each player can gain by deviating from his strategy, and confirm that the strategies computed in that earlier paper actually do constitute an epsilon-equilibrium for a very small epsilon (0.5% of the tournament entry fee). Next, we develop several new algorithms for computing a Nash equilibrium in multiplayer stochastic games (with perfect or imperfect information) which can provably never converge to a non-equilibrium. Experiments show that one of these algorithms outperforms the original algorithm on the same poker tournament. In short, we present the first algorithms for provably computing an epsilon-equilibrium of a large stochastic game for small epsilon. Finally, we present an efficient algorithm that minimizes external regret in both the perfect and imperfect information case.

Evaluating an agent's performance in a stochastic setting is necessary for agent development, scientific evaluation, and competitions. Traditionally, evaluation is done using Monte Carlo estimation; the magnitude of the stochasticity in the domain or the high cost of sampling, however, can often prevent the approach from resulting in statistically significant conclusions. Recently, an advantage sum technique has been proposed for constructing unbiased, low variance estimates of agent performance. The technique requires an expert to define a value function over states of the system, essentially a guess of the state's unknown value. In this work, we propose learning this value function from past interactions between agents in some target population. Our learned value functions have two key advantages: they can be applied in domains where no expert value function is available and they can result in tuned evaluation for a specific population of agents (e.g., novice versus advanced agents). We demonstrate these two advantages in the domain of poker. We show that we can reduce variance over state-of-the-art estimators for a specific population of limit poker players as well as construct the first variance reducing estimators for no-limit poker and multi-player limit poker.

The problem of fairly dividing a cake (as a metaphor for a heterogeneous divisible good) has been the subject of much interest since the 1940's, and is of importance in multiagent resource allocation. Two fairness criteria are usually considered: proportionality, in the sense that each of the n agents receives at least 1/n of the cake; and the stronger property of envy-freeness, namely that each agent prefers its own piece of cake to the others' pieces. For proportional division, there are algorithms that require O(nlogn) steps, and recent lower bounds imply that one cannot do better. In stark contrast, known (discrete) algorithms for envy-free division require an unbounded number of steps, even when there are only four agents. In this paper, we give an Omega(n 2 ) lower bound for the number of steps required by envy-free cake-cutting algorithms. This result provides, for the first time, a true separation between envy-free and proportional division, thus giving a partial explanation for the notorious difficulty of the former problem.

Runtime commitment verification is an important, open issue in multiagent research. To address it, we build on Yolum and Singh's formalization of commitment operations, on Chittaro and Montanari's cached event calculus, and on the SCIFF abductive logic programming proof-procedure. We propose a framework consisting of a declarative and compact language to express the domain knowledge, and a reactive and complete procedure to track the status of commitments effectively, producing provably sound and irrevocable answers.

We study the problem of multi-robot perimeter patrol in adversarial environments, under uncertainty of adversarial behavior. The robots patrol around a closed area using a nondeterministic patrol algorithm. The adversary's choice of penetration point depends on the knowledge it obtained on the patrolling algorithm and its weakness points. Previous work investigated full knowledge and zero knowledge adversaries, and the impact of their knowledge on the optimal algorithm for the robots. However, realistically the knowledge obtained by the adversary is neither zero nor full, and therefore it will have uncertainty in its choice of penetration points. This paper considers these cases, and offers several approaches to bounding the level of uncertainty of the adversary, and its influence on the optimal patrol algorithm. We provide theoretical results that justify these approaches, and empirical results that show the performance of the derived algorithms used by simulated robots working against humans playing the role of the adversary is several different settings.

Voting is a general method for aggregating the preferences of multiple agents. Each agent ranks all the possible alternatives, and based on this, an aggregate ranking of the alternatives (or at least a winning alternative) is produced. However, when there are many alternatives, it is impractical to simply ask agents to report their complete preferences. Rather, the agents' preferences, or at least the relevant parts thereof, need to be elicited. This is done by asking the agents a (hopefully small) number of simple queries about their preferences, such as comparison queries, which ask an agent to compare two of the alternatives. Prior work on preference elicitation in voting has focused on the case of unrestricted preferences. It has been shown that in this setting, it is sometimes necessary to ask each agent (almost) as many queries as would be required to determine an arbitrary ranking of the alternatives. In contrast, in this paper, we focus on single-peaked preferences. We show that such preferences can be elicited using only a linear number of comparison queries, if either the order with respect to which preferences are single-peaked is known, or at least one other agent's complete preferences are known. We show that using a sublinear number of queries does not suffice. We also consider the case of cardinally single-peaked preferences. For this case, we show that if the alternatives' cardinal positions are known, then an agent's preferences can be elicited using only a logarithmic number of queries; however, we also show that if the cardinal positions are not known, then a sublinear number of queries does not suffice. We present experimental results for all elicitation algorithms. We also consider the problem of only eliciting enough information to determine the aggregate ranking, and show that even for this more modest objective, a sublinear number of queries per agent does not suffice for known ordinal or unknown cardinal positions. Finally, we discuss whether and how these techniques can be applied when preferences are almost single-peaked.

Vickrey-Clarke-Groves (VCG) mechanisms are often used to allocate tasks to selfish and rational agents. VCG mechanisms are incentive compatible, direct mechanisms that are efficient (i.e., maximise social utility) and individually rational (i.e., agents prefer to join rather than opt out). However, an important assumption of these mechanisms is that the agents will "always" successfully complete their allocated tasks. Clearly, this assumption is unrealistic in many real-world applications, where agents can, and often do, fail in their endeavours. Moreover, whether an agent is deemed to have failed may be perceived differently by different agents. Such subjective perceptions about an agent's probability of succeeding at a given task are often captured and reasoned about using the notion of "trust". Given this background, in this paper we investigate the design of novel mechanisms that take into account the trust between agents when allocating tasks. Specifically, we develop a new class of mechanisms, called "trust-based mechanisms", that can take into account multiple subjective measures of the probability of an agent succeeding at a given task and produce allocations that maximise social utility, whilst ensuring that no agent obtains a negative utility. We then show that such mechanisms pose a challenging new combinatorial optimisation problem (that is NP-complete), devise a novel representation for solving the problem, and develop an effective integer programming solution (that can solve instances with about 2x10^5 possible allocations in 40 seconds).

Requirement volatility is an issue in software engineering in general, and in Web-based clinical applications in particular, which often originates from an incomplete knowledge of the domain of interest. With advances in the health science, many features and functionalities need to be added to, or removed from, existing software applications in the biomedical domain. At the same time, the increasing complexity of biomedical systems makes them more difficult to understand, and consequently it is more difficult to define their requirements, which contributes considerably to their volatility. In this paper, we present a novel agent-based approach for analyzing and managing volatile and dynamic requirements in an ontology-driven laboratory information management system (LIMS) designed for Web-based case reporting in medical mycology. The proposed framework is empowered with ontologies and formalized using category theory to provide a deep and common understanding of the functional and nonfunctional requirement hierarchies and their interrelations, and to trace the effects of a change on the conceptual framework.

The paper proposes an analysis on some existent ontologies, in order to point out ways to resolve semantic heterogeneity in information systems. Authors are highlighting the tasks in a Knowledge Acquisiton System and identifying aspects related to the addition of new information to an intelligent system. A solution is proposed, as a combination of ontology reasoning services and natural languages generation. A multi-agent system will be conceived with an extractor agent, a reasoner agent and a competence management agent.