The multi-agent path finding (MAPF) problem is a generalization of the single-agent path finding problem for k > 1 agents. It consists of a graph and a number of agents. Foreach agent, a unique start state and a unique goal state are given, the task is to find paths for all agents from their start states to their goal states, under the constraint that agents cannot collide during their movements. In many cases there is an additional goal of minimizing a cumulative cost function such as the sum of the time steps required for every agent to reach its goal. The goal of my research is providing new methods to solve MAPF optimally and provide theoretical understandings that will help choose the best solver given a problem instance.

Commitment protocols provide an effective formalism for the regulation of agent interaction. Although existing work mainly focus on the design-time development of static commitment protocols, recent studies propose methods to create them dynamically at run-time with respect to the goals of the agents. These methods require agents to verify new commitment protocols taking their goals, and beliefs about the other agents’ behavior into account. Accordingly, in this paper, we first propose a probabilistic model to formally capture commitment protocols according to agents’ beliefs. Secondly, we identify a set of important properties for the verification of a new commitment protocol from an agent’s perspective and formalize these properties in our model. Thirdly, we develop probabilistic model checking algorithms with advanced reduction for efficient verification of these properties. Finally, we implement these algorithms as a tool and evaluate the proposed properties over different commitment protocols.

This paper introduces a modal logic for reasoning about game strategies. The logic is based on a variant of the well-known game description language for describing game rules and further extends it with two modalities for reasoning about actions and strategies. We develop an axiomatic system and prove its soundness and completeness with respect to a specific semantics based on the state transition model of games. Interestingly, the completeness proof makes use of forgetting techniques that have been widely used in the KR&R literature. We demonstrate how general game-playing systems can apply the logic to develop game strategies.

Most real-world games and many recreational games are games of incomplete information. Over the last dozen years, abstraction has emerged as a key enabler for solving large incomplete-information games. First, the game is abstracted to generate a smaller, abstract game that is strategically similar to the original game. Second, an approximate equilibrium is computed in the abstract game. Third, the strategy from the abstract game is mapped back to the original game. In this paper, I will review key developments in the field. I present reasons for abstracting games, and point out the issue of abstraction pathology. I then review the practical algorithms for information abstraction and action abstraction. I then cover recent theoretical breakthroughs that beget bounds on the quality of the strategy from the abstract game, when measured in the original game. I then discuss how to reverse map the opponent's action into the abstraction if the opponent makes a move that is not in the abstraction. Finally, I discuss other topics of current and future research.

Many scenarios require that robots work together as a team in order to effectively accomplish their tasks. However, pre-coordinating these teams may not always be possible given the growing number of companies and research labs creating these robots. Therefore, it is desirable for robots to be able to reason about ad hoc teamwork and adapt to new teammates on the fly. Past research on ad hoc teamwork has focused on relatively simple domains, but this paper demonstrates that agents can reason about ad hoc teamwork in complex scenarios. To handle these complex scenarios, we introduce a new algorithm, PLASTIC–Policy, that builds on an existing ad hoc teamwork approach. Specifically, PLASTIC– Policy learns policies to cooperate with past teammates and reuses these policies to quickly adapt to new teammates. This approach is tested in the 2D simulation soccer league of RoboCup using the half field offense task.

The success of applying policy gradient reinforcement learning (RL) to difficult control tasks hinges crucially on the ability to determine a sensible initialization for the policy. Transfer learning methods tackle this problem by reusing knowledge gleaned from solving other related tasks. In the case of multiple task domains, these algorithms require an inter-task mapping to facilitate knowledge transfer across domains. However, there are currently no general methods to learn an inter-task mapping without requiring either background knowledge that is not typically present in RL settings, or an expensive analysis of an exponential number of inter-task mappings in the size of the state and action spaces. This paper introduces an autonomous framework that uses unsupervised manifold alignment to learn inter-task mappings and effectively transfer samples between different task domains. Empirical results on diverse dynamical systems, including an application to quadrotor control, demonstrate its effectiveness for cross-domain transfer in the context of policy gradient RL.

Many models and mechanisms in resource and cost allocation have been developed that are simple and abstract. By means of two case studies, I argue that it is now timely to consider richer models for the fair division of resources and for the allocation of costs. Such models should have features like asynchronicity which reflect more of the true complexity of many fair division and cost allocation problems met in the real world. I suggest that computation can be used in such models to increase both efficiency and fairness of the allocations. As a result, we may be able to do more with fewer resources and greater fairness.

In a heterogeneous multiagent system it can be useful to have knowledge about the different types of agents in the system. Agent modeling develops agent models based on interactions between agents, then predicts agent actions. This approach is effective in small domains but does not scale well. We develop an approach where an agent can learn using an abstract model identification or stereotype rather than an explicit and unique model for each agent. We associate each agent with a stereotype and learn a policy incorporating this knowledge. The benefits of this approach are that it is simple, scalable, and degrades gracefully with misidentification.

We consider the following problem: There is a set of items (e.g., movies) and a group of agents (e.g., passengers on a plane); each agent has some intrinsic utility for each of the items. Our goal is to pick a set of K items that maximize the total derived utility of all the agents (i.e., in our example we are to pick K movies that we put on the plane's entertainment system). However, the actual utility that an agent derives from a given item is only a fraction of its intrinsic one, and this fraction depends on how the agent ranks the item among the chosen, available, ones. We provide a formal specification of the model and provide concrete examples and settings where it is applicable. We show that the problem is hard in general, but we show a number of tractability results for its natural special cases.

We consider the problem of repeatedly matching a set of alternatives to a set of agents in the absence of monetary transfer. We propose a generic framework for evaluating sequential matching mechanisms with dynamic preferences, and show that unlike single-shot settings, the random serial dictatorship mechanism is manipulable.