In cooperative multiagent planning, it can often be beneficial for an agent to make commitments about aspects of its behavior to others, allowing them in turn to plan their own behaviors without taking the agent's detailed behavior into account. Extending previous work in the Bayesian setting, we consider instead a worst-case setting in which the agent has a set of possible environments (MDPs) it could be in, and develop a commitment semantics that allows for probabilistic guarantees on the agent's behavior in any of the environments it could end up facing. Crucially, an agent receives observations (of reward and state transitions) that allow it to potentially eliminate possible environments and thus obtain higher utility by adapting its policy to the history of observations. We develop algorithms and provide theory and some preliminary empirical results showing that they ensure an agent meets its commitments with history-dependent policies while minimizing maximum regret over the possible environments.

Recent work in multi-agent path planning has provided a number of optimal and suboptimal solvers that can efficiently find solutions to problems of growing complexity. Solvers based on Conflict-Based Search (CBS) combine single-agent solvers with shared constraints between agents to find feasible solutions. Suboptimal variants of CBS introduce alternate heuristics to avoid conflicts. In this paper we study the multi-agent planning problem in the context of non-holonomic vehicles planning on a lattice. We propose that in addition to using heuristics to avoid conflicts, we can plan using a hierarchy of movement constraints to efficiently avoid conflicts. We develop a new extension to the CBS algorithm, CBS with constraint layering (CBS CL), which iteratively applies different movement constraint models during the CBS planning process. Our results show that this approach allows us to solve for about 2.4 times more agents in the same amount of time when compared to regular CBS without using a constraint hierarchy.

Multi-agent planning using MA-STRIPS-related models is often motivated by the preservation of private information. Such motivation is not only natural for multi-agent systems, but it is one of the main reasons, why multi-agent planning (MAP) problems cannot be solved centrally. In this paper, we analyze privacy-preserving multi-agent planning (PP-MAP) from the perspective of secure multiparty computation (MPC). We discuss the concept of strong privacy and its implications and present two variants of a novel planner, provably strong privacy-preserving in general. As the main contribution, we formulate the limits of strong privacy-preserving planning in the terms of privacy, completeness and efficiency and show that, for a wide class of planning algorithms, all three properties are not achievable at once. Moreover, we provide a restricted variant of strong privacy based on equivalence classes of planning problems and show that an efficient, complete and strong privacy-preserving planner exists for such restriction.

Multi-agent forward search (MAFS) is a state-of-the-art privacy-preserving planning algorithm. We describe a new variant of MAFS, called multi-agent forward-backward search (MAFBS) that uses both forward and backward messages to reduce the number of messages sent and obtain new privacy properties. While MAFS requires agents to send a state s produced by an action a to all agents that can apply any action in s, MAFBS sends such messages forward only to agents that have an action that requires one of the effects of a. To achieve completeness, it sends messages backward to agents that can supply a missing precondition. This more focused message passing scheme reduces states exchanged, and requires that agents be aware only of other agents that they directly interact with, leading to agent privacy.

Agents operating in a multi-agent environment must consider not just their own actions, but also those of the other agents in the system. Artificial social systems are a well known means for coordinating a set of agents, without requiring centralized planning or online negotiation between agents. Artificial social systems enact a social law which restricts the agents from performing some actions under some circumstances. A good social law prevents the agents from interfering with each other, but does not prevent them from achieving their goals. However, designing good social laws, or even checking whether a proposed social law is good, are hard questions. In this paper, we take a first step towards automating these processes, by formulating criteria for good social laws in a multi-agent planning framework. We then describe an automated technique for verifying if a proposed social law meets these criteria, based on a compilation to classical planning.

So far, there have been few attempts to provide a succinct language for representing them that can also support efficient centralized and distributed privacy preserving planning. In this paper we suggest an approach for representing interacting actions succinctly and show how such a domain model can be compiled into a standard single-agent planning problem as well as to privacy preserving multi-agent planning. We test the performance of our method on a number of novel domains involving interacting actions and privacy.

In a multiagent system or MAS, due to agent interactions, the agents as a group may make decisions that none of them would make alone; this phenomenon is called emergence. Emergence is characterized by an unanticipated system behavior caused by nonlinear interactions.

Multi-agent systems are used in domains where individual component autonomy and cooperation are necessary. The overall system performance requires that the diverse agents maintain quality interactions to facilitate cooperation. A complication to inter-agent interaction occurs when the agents learn (change their own functionality), when new agents are introduced, or existing agents are functionally modified. This research focuses on creating a general use multi-agent system, Middleware Unifying Framework for Independent Nodes System (MUFFINS), and implementing a mechanism, the Megagent, that addresses the interaction challenges. The Megagent provides the ability for agents to assess their performance per data source and to improve it with transformations based on feedback.

In this paper, we present RALE-ACL, a communication language for case-based agents in multi-agent systems (MAS) that utilize case-based reasoning (CBR) as the main means of decision making for their agents. RALE-ACL is an accompanying approach of RALE-CBR, a methodology for construction of CBR-based approaches and systems that adds more flexibility to the classic 4R cycle of case-based reasoning. The main goal of RALE-ACL is to establish a much more CBR-compatible alternative to the KQML and FIPA-ACL-based languages, that are currently used in many multi-agent systems, but are too generic and therefore only cumbersomely usable for the specific structure and purposes of case-based agents. This paper is the final part in the trilogy about the RALE methodology.

Coordination between processing entities is one of the most widely studied areas in multi-agent planning research. Recently, efforts have been made to understand the formal computational issues of this important area. In this paper, we make a step toward this direction, and analyze a certain class of coordination problems for dependent agents with independent goals acting in the same environment. We assume that a state-transition description of each agent is given, and that preconditioning an agent's transitions by the states of other agents is the only considered kind of inter-agent dependence. Off-line coordination between the agents is considered. We analyze some structural properties of these problems, and investigate the relationship between these properties and the complexity of coordination in this domain. We show that our general problem is provably intractable, but some significant subclasses are in NP and even polynomial.