Constructing models of mobile agents can be difficult without domain-specific knowledge. Parametric models flexible enough to capture all mobility patterns that an expert believes are possible are often large, requiring a great deal of training data. In contrast, nonparametric models are extremely flexible and can generalize well with relatively little training data. We propose modeling the mobility patterns of moving agents as a mixture of Gaussian processes (GP) with a Dirichlet process (DP) prior over mixture weights. The GP provides a flexible representation for each individual mobility pattern, while the DP assigns observed trajectories to particular mobility patterns. Both the GPs and the DP adjust the model's complexity based on available data, implicitly avoiding issues of over-fitting or under-fitting. We apply our model to a helicopter-based tracking task, where the mobility patterns of the tracked agents — cars — are learned from real data collected from taxis in the greater Boston area.

It is standard in multiagent settings to assume that agents will adopt Nash equilibrium strategies. However, studies in experimental economics demonstrate that Nash equilibrium is a poor description of human players' initial behavior in normal-form games. In this paper, we consider a wide range of widely-studied models from behavioral game theory. For what we believe is the first time, we evaluate each of these models in a meta-analysis, taking as our data set large-scale and publicly-available experimental data from the literature. We then propose modifications to the best-performing model that we believe make it more suitable for practical prediction of initial play by humans in normal-form games.

Online social networks are becoming increasingly popular and are being used as the means for a variety of rich activities. This demands the evaluation of the trustworthiness between two unknown participants along a certain social trust path between them in the social network. However, there are usually many social trust paths between participants. Thus, a challenging problem is finding which social trust path is the optimal one that can yield the most trustworthy evaluation result. In this paper, we first present a new complex social network structure and a new concept of Quality of Trust (QoT) to illustrate the ability to guarantee a certain level of trustworthiness in trust evaluation. We then model the optimal social trust path selection as a Multi-Constrained Optimal Path (MCOP) selection problem which is NP-Complete. For solving this problem, we propose an efficient approximation algorithm MONTE K based on the Monte Carlo method. The results of our experiments conducted on a real dataset of social networks illustrate that our proposed algorithm significantly outperforms existing approaches in both efficiency and the quality of selected social trust paths.

Many real-world applications, such as Supply Chain Management (SCM), can be modeled using multi-agent systems. One shortcoming of current SCM models is that their trust models are ad hoc and do not have a strong theoretical basis. We propose a trust model for SCM that is grounded in probabilistic game theory. In this model, trust can be gained through direct interactions, and/or by asking for information from other trustworthy agents. We will use this model to simulate and study supply chain market behavior.

The Gibbard-Satterthwaite Theorem asserts that any reasonable voting rule cannot be strategyproof. A large body of research in AI deals with circumventing this theorem via computational considerations; the goal is to design voting rules that are computationally hard, in the worst-case, to manipulate. However, recent work indicates that the prominent voting rules are usually easy to manipulate. In this paper, we suggest a new CS-oriented approach to circumventing Gibbard-Satterthwaite, using randomization and approximation. Specifically, we wish to design strategyproof randomized voting rules that are close, in a standard approximation sense, to prominent score-based (deterministic) voting rules. We give tight lower and upper bounds on the approximation ratio achievable via strategyproof randomized rules with respect to positional scoring rules, Copeland, and Maximin.

Trial-based approaches offer an efficient way to solve single-agent MDPs and POMDPs. These approaches allow agents to focus their computations on regions of the environment they encounter during the trials, leading to significant computational savings. We present a novel trial-based dynamic programming (TBDP) algorithm for DEC-POMDPs that extends these benefits to multi-agent settings. The algorithm uses trial-based methods for both belief generation and policy evaluation. Policy improvement is implemented efficiently using linear programming and a sub-policy reuse technique that helps bound the amount of memory. The results show that TBDP can produce significant value improvements and is much faster than the best existing planning algorithms.

This paper investigates search techniques for multi-agent settings in which the most suitable agent, according to given criteria, needs to be found. In particular, it considers the case where the searching agent incurs a cost for learning the value of an agent and the goal is to minimize the expected overall cost of search by iteratively increasing the extent of search. This kind of search is applicable to various domains, including auctions, first responders, and sensor networks. Using an innovative transformation of the extents-based sequence to a probability-based one, the optimal sequence is proved to consist of either a single search iteration or an infinite sequence of increasing search extents. This leads to a simplified characterization of the the optimal search sequence from which it can be derived. This method is also highly useful for legacy economic-search applications, where all agents are considered suitable candidates and the goal is to optimize the search process as a whole. The effectiveness of the method for both best-valued search and economic search is demonstrated numerically using a synthetic environment.

We present an instance-based, online method for learning action models in unanticipated, relational domains. Our algorithm memorizes pre- and post-states of transitions an agent encounters while experiencing the environment, and makes predictions by using analogy to map the recorded transitions to novel situations. Our algorithm is implemented in the Soar cognitive architecture, integrating its task-independent episodic memory module and analogical reasoning implemented in procedural memory. We evaluate this algorithm’s prediction performance in a modified version of the blocks world domain and the taxi domain. We also present a reinforcement learning agent that uses our model learning algorithm to significantly speed up its convergence to an optimal policy in the modified blocks world domain.

Decentralized agent groups typically require complex mechanisms to accomplish coordinated tasks. In contrast, biological systems can achieve intelligent group behaviors with each agent performing simple sensing and actions. We summarize our recent papers on a biologically-inspired control framework for multi-agent tasks that is based on a simple and iterative control law. We theoretically analyze important aspects of this decentralized approach, such as the convergence and scalability, and further demonstrate how this approach applies to real-world applications with a diverse set of multi-agent applications. These results provide a deeper understanding of the contrast between centralized and decentralized algorithms in multi-agent tasks and autonomous robot control.

As autonomous agents proliferate in the real world, both in software and robotic settings, they will increasingly need to band together for cooperative activities with previously unfamiliar teammates. In such ad hoc team settings, team strategies cannot be developed a priori. Rather, an agent must be prepared to cooperate with many types of teammates: it must collaborate without pre-coordination. This paper challenges the AI community to develop theory and to implement prototypes of ad hoc team agents. It defines the concept of ad hoc team agents, specifies an evaluation paradigm, and provides examples of possible theoretical and empirical approaches to challenge. The goal is to encourage progress towards this ambitious, newly realistic, and increasingly important research goal.