A number of real-world security scenarios can be cast as a problem of transiting an area guarded by a mobile patroller, where the transiting agent aims to choose its route so as to minimize the probability of encountering the patrolling agent, and vice versa. We model this problem as a two-player zero-sum game on a graph, termed the transit game. In contrast to the existing models of area transit, where one of the players is stationary, we assume both players are mobile. We also explicitly model the limited endurance of the patroller and the notion of a base to which the patroller has to repeatedly return. Noting the prohibitive size of the strategy spaces of both players, we develop single- and double-oracle based algorithms including a novel acceleration scheme, to obtain optimum route selection strategies for both players. We evaluate the developed approach on a range of transit game instances inspired by real-world security problems in the urban and naval security domains.

The importance of diversity in reasoning and learning to successfully address complex problems is examined. We discuss an approach by which a multiagent framework with decentralized control mechanisms provides diverse perspectives and hypotheses addressing a class of complex problems. We introduce the SNARE multiagent system. SNARE performs tasks to gain situational awareness of situations of interest in a Social Media Space. It applies a decentralized control mechanism for each agent; this mechanism enables an agent to interact with other agents to reason and learn. This approach facilitates dynamic agent organizations that adapt the topologies of interactions between agents based on the problem context.

A principal seeks production of a good within a limited time-frame with a hard deadline, after which any good procured has no value. There is inherent uncertainty in the production process, which in light of the deadline may warrant simultaneous production of multiple goods by multiple producers despite there being no marginal value for extra goods beyond the maximum quality good produced. This motivates a crowdsourcing model of procurement. We address efficient execution of such procurement from a social planner's perspective, taking account of and optimally balancing the value to the principal with the costs to producers (modeled as effort expenditure) while, crucially, contending with self-interest on the part of all players. A solution to this problem involves both an algorithmic aspect that determines an optimal effort level for each producer given the principal's value, and also an incentive mechanism that achieves equilibrium implementation of the socially optimal policy despite the principal privately observing his value, producers privately observing their skill levels and effort expenditure, and all acting only to maximize their own individual welfare. In contrast to popular "winner take all" contests, the efficient mechanism we propose involves a payment to every producer that expends non-zero effort in the efficient policy.

We present a statistical physics inspired approach to modeling, analysis, and design of distributed aggregation control policies for teams of homogeneous and heterogeneous robots. We assume high-level agent behavior can be described as a sequential composition of lower-level behavioral primitives. Aggregation or division of the collective into distinct clusters is achieved by developing a macroscopic description of the ensemble dynamics. The advantages of this approach are twofold: 1) the derivation of a low dimensional but highly predictive description of the collective dynamics and 2) a framework where interaction uncertainties between the low-level components can be explicitly modeled and control. Additionally, classical dynamical systems theory and control theoretic techniques can be used to analyze and shape the collective dynamics of the system. We consider the aggregation problem for homogeneous agents into clusters located at distinct regions in the workspace and discuss the extension to heterogeneous teams of autonomous agents. We show how a macroscopic model of the aggregation dynamics can be derived from agent-level behaviors and discuss the synthesis of distributed coordination strategies in the presence of uncertainty.

The paper discusses how a human-robot team can remain “cohesive” while performing under stress. By cohesive the paper understands the ability of the team to operate effectively, with individual members being interdependent-yet-autonomous in carrying out tasks. For a human-robot team, we argue that this requires robots to (1) have an adequate sense of that interde- pendency in terms of the social dynamics within the team, and to (2) maintain transparency towards the human team members in terms of what it is doing, why, and to what extent it can achieve its (possibly jointly agreed upon) goals. The paper re- ports of recent field experience showing that failure in trans- parency results in reduced acceptability of robot autonomous behavior by the human team members. This reduction in acceptability can have two negative impacts on cohesiveness: Humans and robots fail to maintain common ground, and as a result they fail to maintain trust.

We propose a dynamic logic of lying, wherein a 'lie that phi' (where phi is a formula in the logic) is an action in the sense of dynamic modal logic, that is interpreted as a state transformer relative to the formula phi. The states that are being transformed are pointed Kripke models encoding the uncertainty of agents about their beliefs. Lies can be about factual propositions but also about modal formulas, such as the beliefs of other agents or the belief consequences of the lies of other agents. We distinguish (i) an outside observer who is lying to an agent that is modelled in the system, from (ii) one agent who is lying to another agent, and where both are modelled in the system. For either case, we further distinguish (iii) the agent who believes everything that it is told (even at the price of inconsistency), from (iv) the agent who only believes what it is told if that is consistent with its current beliefs, and from (v) the agent who believes everything that it is told by consistently revising its current beliefs. The logics have complete axiomatizations, which can most elegantly be shown by way of their embedding in what is known as action model logic or the extension of that logic to belief revision.

Standard models of multi-agent modal logic do not capture the fact that information is often ambiguous, and may be interpreted in different ways by different agents. We propose a framework that can model this, and consider different semantics that capture different assumptions about the agents' beliefs regarding whether or not there is ambiguity. We consider the impact of ambiguity on a seminal result in economics: Aumann's result saying that agents with a common prior cannot agree to disagree. This result is known not to hold if agents do not have a common prior; we show that it also does not hold in the presence of ambiguity. We then consider the tradeoff between assuming a common interpretation (i.e., no ambiguity) and a common prior (i.e., shared initial beliefs).

Language evolution might have preferred certain prior social configurations over others. Experiments conducted with models of different social structures (varying subgroup interactions and the role of a dominant interlocutor) suggest that having isolated agent groups rather than an interconnected agent is more advantageous for the emergence of a social communication system. Distinctive groups that are closely connected by communication yield systems less like natural language than fully isolated groups inhabiting the same world. Furthermore, the addition of a dominant male who is asymmetrically favoured as a hearer, and equally likely to be a speaker has no positive influence on the disjoint groups.

The first decade of this century has seen the nascency of the first mathematical theory of general artificial intelligence. This theory of Universal Artificial Intelligence (UAI) has made significant contributions to many theoretical, philosophical, and practical AI questions. In a series of papers culminating in book (Hutter, 2005), an exciting sound and complete mathematical model for a super intelligent agent (AIXI) has been developed and rigorously analyzed. While nowadays most AI researchers avoid discussing intelligence, the award-winning PhD thesis (Legg, 2008) provided the philosophical embedding and investigated the UAI-based universal measure of rational intelligence, which is formal, objective and non-anthropocentric. Recently, effective approximations of AIXI have been derived and experimentally investigated in JAIR paper (Veness et al. 2011). This practical breakthrough has resulted in some impressive applications, finally muting earlier critique that UAI is only a theory. For the first time, without providing any domain knowledge, the same agent is able to self-adapt to a diverse range of interactive environments. For instance, AIXI is able to learn from scratch to play TicTacToe, Pacman, Kuhn Poker, and other games by trial and error, without even providing the rules of the games. These achievements give new hope that the grand goal of Artificial General Intelligence is not elusive. This article provides an informal overview of UAI in context. It attempts to gently introduce a very theoretical, formal, and mathematical subject, and discusses philosophical and technical ingredients, traits of intelligence, some social questions, and the past and future of UAI.

We focus on the problem of sequential decision making in partially observable environments shared with other agents of uncertain types having similar or conflicting objectives. This problem has been previously formalized by multiple frameworks one of which is the interactive dynamic influence diagram (I-DID), which generalizes the well-known influence diagram to the multiagent setting. I-DIDs are graphical models and may be used to compute the policy of an agent given its belief over the physical state and others' models, which changes as the agent acts and observes in the multiagent setting. As we may expect, solving I-DIDs is computationally hard. This is predominantly due to the large space of candidate models ascribed to the other agents and its exponential growth over time. We present two methods for reducing the size of the model space and stemming its exponential growth. Both these methods involve aggregating individual models into equivalence classes. Our first method groups together behaviorally equivalent models and selects only those models for updating which will result in predictive behaviors that are distinct from others in the updated model space. The second method further compacts the model space by focusing on portions of the behavioral predictions. Specifically, we cluster actionally equivalent models that prescribe identical actions at a single time step. Exactly identifying the equivalences would require us to solve all models in the initial set. We avoid this by selectively solving some of the models, thereby introducing an approximation. We discuss the error introduced by the approximation, and empirically demonstrate the improved efficiency in solving I-DIDs due to the equivalences.