Cooperative Multi-Agent Planning: A Survey



<ccs2012> <concept> <concept\_id>10010147.10010178.10010199.10010202</concept\_id> <concept\_desc>Computing methodologies Multi-agent planning</concept\_desc> <concept\_significance>500</concept\_significance> </concept> <concept> <concept\_id>10010147.10010178.10010219.10010223</concept\_id> <concept\_desc>Computing methodologies Cooperation and coordination</concept\_desc> <concept\_significance>500</concept\_significance> </concept> <concept> <concept\_id>10010147.10010178.10010219.10010220</concept\_id> <concept\_desc>Computing methodologies Multi-agent systems</concept\_desc> <concept\_significance>300</concept\_significance> </concept> <concept> <concept\_id>10010147.10010178.10010199.10010200</concept\_id> <concept\_desc>Computing methodologies Planning for deterministic actions</concept\_desc> <concept\_significance>300</concept\_significance> </concept> <concept> <concept\_id>10010147.10010178.10010205.10010206</concept\_id> <concept\_desc>Computing methodologies Heuristic function construction</concept\_desc> <concept\_significance>300</concept\_significance> </concept> <concept> <concept\_id>10002978.10002991.10002995</concept\_id> <concept\_desc>Security and privacy Privacy-preserving protocols</concept\_desc> <concept\_significance>300</concept\_significance> </concept> </ccs2012>

This work is supported by the Spanish MINECO under project TIN2014-55637-C2-2-R, the Prometeo project II/2013/019 funded by the Valencian Government, and the 4-year FPI-UPV research scholarship granted to the first author by the Universitat Politècnica de València. Additionally, this research is partially supported by the Czech Science Foundation under grant 15-20433Y.

Author's addresses: A. Torreño (tnelson@example.org) <span>and</span> E. Onaindia (tnelson@example.org), Universitat Politècnica de València, Camino de Vera, s/n, Valencia, 46022, Spain; A. Komenda (tnelson@example.org) <span>and</span> M. Štolba (tnelson@example.org), Czech Technical University in Prague, Zikova 1903/4, 166 36, Prague, Czech Republic.

Introduction
============

Automated Planning is the field devoted to studying the reasoning side of acting. From the restricted conceptual model assumed in classical planning to the extended models that address temporal planning, on-line planning or planning in partially-observable and non-deterministic domains, the field of Automated Planning has experienced huge advances @Ghallab04.

Multi-Agent Planning (MAP) introduces a new perspective in the resolution of a planning task with the adoption of a distributed problem-solving scheme instead of the classical single-agent planning paradigm. Distributed planning is required "when planning knowledge or responsibility is distributed among agents or when the execution capabilities that must be employed to successfully achieve objectives are inherently distributed" @Desjardins99a.

The authors of @Desjardins99a analyze distributed planning from a twofold perspective; one approach, named *Cooperative Distributed Planning*, regards a MAP task as the process of formulating or executing a plan among a number of participants; the second approach, named *Negotiated Distributed Planning*, puts the focus on coordinating and scheduling the actions of multiple agents in a shared environment. The first approach has evolved to what is nowadays commonly known as *cooperative and distributed MAP*, with a focus on extending planning into a distributed environment and allocating the planning task among multiple agents. The second approach is primarily concerned with controlling and coordinating the actions of multiple agents in a shared environment so as to ensure that their local objectives are met. We will refer to this second approach, which stresses the coordination and execution of large-scale multi-agent planning problems, as *decentralized planning for multiple agents*. Moreover, while the first planning-oriented view of MAP relies on deterministic approaches, the study of decentralized MAP has yielded an intensive research work on coordination of activities in contexts under uncertainty and/or partial observability with the development of formal methods inspired by the use of Markov Decision Processes @Seuken08.

This paper surveys deterministic cooperative and distributed MAP methods. Our intention is to provide the reader with a broad picture of the current state of the art in this field, which has recently gained much attention within the planning community thanks to venues such as the Distributed and Multi-Agent Planning workshop[^1] and the 2015 Competition of Distributed and Multi-Agent Planning[^2] (<span><span>CoDMAP</span></span>). Interestingly, although there was a significant amount of work on planning in multi-agent systems in the 90's, most of this research was basically aimed at developing coordination methods for agents that adopt planning representations and algorithms to carry out their tasks. Back then, little attention was given to the problem of formulating collective plans to solve a planning task. However, the recent <span><span>CoDMAP</span></span>initiative of fostering <span><span>MA-STRIPS</span></span>a classical planning model for multi-agent systems @Brafman08$\;$ has brought back a renewed interest.

Generally speaking, cooperative MAP is about the collective effort of multiple planning agents to develop solutions to problems that each could not have solved as well (if at all) alone @Durfee99. A cooperative MAP task is thus defined as the collective effort of multiple agents towards achieving a *common goal*, irrespective of how the goals, the knowledge and the agents' abilities are distributed in the application domain. In @deWeerdt09, authors identify several phases to address a MAP task that can be interleaved depending on the characteristics of the problem, the agents and the planning model. Hence, MAP solving may require allocation of goals, formulating plans for solving goals, communicating planning choices and coordinating plans, and execution of plans. The work in @deWeerdt09 is an overview of MAP devoted to agents that plan and interact, presenting a rough outline of techniques for cooperative MAP and decentralized planning. A more recent study examines how to integrate planning algorithms and Belief-Desire-Intention (BDI) agent reasoning @MeneguzziS15. This survey puts the focus on the integration of agent behaviour aimed at carrying out predefined plans that accomplish a goal and agent behaviour aimed at formulating a plan that achieves a goal.

This paper presents a thorough analysis of the advances in cooperative and distributed MAP that have lately emerged in the field of Automated Planning. Our aim is to cover the wide and fragmented space of MAP approaches, identifying the main characteristics that define tasks and solvers and establishing a taxonomy of the main approaches of the literature. We explore the great variety of MAP techniques on the basis of different criteria, like agent distribution, communication or privacy models, among others. The survey thus offers a deep analysis of techniques and domain-independent MAP solvers from a broad perspective, without adopting any particular planning paradigm or programming language. Additionally, the contents of this paper are geared towards reviewing the broad range of MAP solvers that participated in the 2015 <span><span>CoDMAP</span></span>competition.

This survey is structured in five sections. Section \[related\_work\] offers a historical background on distributed planning with a special emphasis on work that has appeared over the last two decades. Section \[MAP\_task\] discusses the main modelling features of a MAP task. Section \[aspects\] analyzes the main aspects of MAP solvers, including distribution, coordination, heuristic search and privacy. Section \[taxonomy\] discusses and classifies the most relevant MAP solvers in the literature. Finally, section \[ongoing\] concludes and summarizes the ongoing and future trends and research directions in MAP.

Related Work: historical background on MAP {#related_work}
==========================================

The large body of work on distributed MAP started jointly with an intensive research activity on multi-agent systems (MAS) at the beginning of the 90's. Motivated by the distributed nature of the problems and reasoning of MAS, decentralized MAP focused on aspects related to distributed control including activities like the decomposition and allocation of tasks to agents and utilization of resources @Durfee91 [@Wilkins98]; reducing communication costs and constraints among agents @Decker92 [@Wolvertond98]; or incorporating group decision making for distributed plan management in collaborative settings (group decisions for selecting a high-level task decomposition or an agent assignation to a task, group processes for plan evaluation and monitoring, etc.) @GroszHK99. From this Distributed Artificial Intelligence (DAI) standpoint, MAP is fundamentally regarded as multi-agent *coordination of actions in decentralized system*s.

The inherently distributed nature of tasks and systems also fostered the appearance of techniques for *cooperative formation of global plans*. In DAI, this form of MAP puts greater emphasis on reasoning, stressing the deliberative planning activities of the agents as well as how and when to coordinate such planning activities to come up with a global plan. Given the cooperative nature of the planning task, where all agents are aimed at solving a common goal, this MAP approach features a more centralized view of the planning process. Investigations in this line have yield a great variety of planning and coordination methods such as techniques to merge the local plans of the agents @EphratiR94 [@Desjardins99b; @Cox04], heuristic techniques for agents to solve their individual sub-plans @Ephrati97, mechanisms to coordinate concurrent interacting actions @BoutilierB01 or distributed constraint optimization techniques to coordinate conflicts among agents @Cox09. In this latter work, the authors propose a general framework to coordinate the activities of several agents in a common environment such as partners in a military coordination, subcontractors working on a building, or airlines operating in an alliance.

Many of the aforementioned techniques and approaches were actually used by some of the early MAP tools. <span><span>Distributed NOAH</span></span> @Corkill79 is one of the first Partial-Order Planning (POP) systems that generates gradual refinements in the space of (abstract) plans using a representation similar to the Hierarchical Task Networks (HTNs). The scheme proposed in @Corkill79 relies on a distributed conflict-solving process across various agents that are able to plan without complete or consistent planning data; the limitation of <span><span>Distributed NOAH</span></span>is the amount of information that must be exchanged between planners and the lack of robustness to communication loss or error. In the domain-specific Partial Global Planning (<span><span>PGP</span></span>) method @Durfee91, agents build their partial global view of the planning problem, and the search algorithm finds local plans that can be then coordinated to meet the goals of all the agents. Generalized PGP (<span><span>GPGP</span></span>) is a domain-independent extension of <span><span>PGP</span></span>@Decker92 [@Lesser04] that separates the process of coordination from the local scheduling of activities and task selection, which enables agents to communicate more abstract and hierarchically organized information and has smaller coordination overhead. <span><span>DSIPE</span></span> @Desjardins99b is a distributed version of <span><span>SIPE-2</span></span> @Wilkins88 closely related to the <span><span>Distributed NOAH</span></span>planner. <span><span>DSIPE</span></span>proposes an efficient communication scheme among agents by creating partial views of sub-plans. The plan merging process is centralized in one agent and uses the conflict-resolution principle originally proposed in <span><span>NOAH</span></span>. The authors of @WeerdtBTW03 propose a plan merging technique that results in distributed plans in which agents become dependent on each other, but are able to attain their goals more efficiently.

HTN planning has also been exploited for coordinating the plans of multiple agents @Clement99. The attractiveness of approaches that integrate hierarchical planning in agent teams such as <span><span>STEAM</span></span> @Tambe97 is that they leverage the abstraction levels of the plan hierarchies for coordinating agents, thus enhancing the efficiency and quality of coordinating the agents' plans. <span><span>A-SHOP</span></span>@DixMNZ03 is a multi-agent version of the <span><span>SHOP</span></span>HTN planner @NauAIKMWY03 that implements capabilities for interacting with external agents, performs mixed symbolic/numeric computations, and makes queries to distributed, heterogeneous information sources without requiring knowledge about how and where these resources are located. Moreover, authors in @KabanzaSG04 propose a distributed version of <span><span>SHOP</span></span>that runs on a network of clusters through the implementation of a simple distributed backtrack search scheme.

As a whole, cooperative MAP approaches devoted to the construction of a plan that solves a common goal are determined by two factors, the underlying planning paradigm and the mechanism to coordinate the formation of the plan. The vast literature on multi-agent coordination methods is mostly concerned with the task of combining and adapting local planning representations into a global consistent solution. The adaptability of these methods to cooperative MAP is highly dependent on the particular agent distribution and the plan synthesis strategy of the MAP solver. Analyzing these aspects is precisely the aim of the following sections.

Cooperative Multi-Agent Planning Tasks {#MAP_task}
======================================

We define a (cooperative) MAP task as a process in which several agents that are not self-interested work together to synthesize a joint plan that solves a common goal. All agents wish thereby the goal to be reached at the end of the task execution.

First, this section presents the formalization of the components of a cooperative MAP task. Next, we discuss the main aspects that characterize a MAP task by means of two illustrative examples. Finally, we present how to model a MAP task with <span>*MA-PDDL*</span>, a multi-agent version of the well-known Planning Domain Description Language (<span>*PDDL*</span>) @Ghallab98.

Formalization of a MAP Task
---------------------------

Most of the cooperative MAP solvers that will be presented in this survey use a formalism that stems from <span><span>MA-STRIPS</span></span>@Brafman08 to a lesser or greater extent. For this reason, we will use <span><span>MA-STRIPS</span></span>as the baseline model for the formalization of a MAP task. <span><span>MA-STRIPS</span></span>is a minimalistic multi-agent extension of the well-known <span><span>STRIPS</span></span>planning model @Fikes71, which has become the most widely-adopted formalism for describing cooperative MAP tasks.

In <span><span>MA-STRIPS</span></span>, a MAP task is represented through a finite number of situations or *states*. States are described by a set of *atoms* or *propositions*. States change via the execution of planning *actions*. An action in <span><span>MA-STRIPS</span></span>is defined as follows:

\[action\] A **planning action** is a tuple $\alpha = \langle {pre(\alpha)}, {add(\alpha)}, {del(\alpha)}\rangle$, where ${pre(\alpha)}$, ${add(\alpha)}$ and ${del(\alpha)}$ are sets of atoms that denote the preconditions, *add effects*, and *delete effects* of the action, respectively.

An action $\alpha$ is executable in a state $S$ if and only if all its preconditions hold in $S$; that is, $\forall p \in {pre(\alpha)}$, $p \in S$. The execution of $\alpha$ in $S$ generates a state $S'$ such that $S' = S \setminus {del(\alpha)}\cup {add(\alpha)}$.

\[MAP\_task\_def\] A **MAP task** is defined as a 5-tuple ${{\mathcal T}}=\langle {{\mathcal{AG}}}, {{\mathcal P}}, \{ {{\mathcal A}}^i \}^n_{i=1},{{\mathcal I}},{{\mathcal G}}\rangle$ with the following components:

-   ${{\mathcal{AG}}}$ is a finite set of $n$ planning entities or agents.

-   ${{\mathcal P}}$ is a finite set of atoms or propositions.

-   ${{\mathcal A}}^i$ is the finite set of planning actions of the agent $i \in AG$. We will denote the set of actions of ${{\mathcal T}}$ as ${{\mathcal A}}= \bigcup_{\forall i \in {{\mathcal{AG}}}} {{\mathcal A}}^i$.

-   ${{\mathcal I}}\subseteq {{\mathcal P}}$ defines the *initial state* of ${{\mathcal T}}$.

-   ${{\mathcal G}}\subseteq {{\mathcal P}}$ denotes the *common goal* of ${{\mathcal T}}$.

A *solution plan* is an ordered set of actions whose application over the initial state ${{\mathcal I}}$ leads to a state $S_g$ that satisfies the task goals; i.e., ${{\mathcal G}}\subseteq S_g$. In <span><span>MA-STRIPS</span></span>a solution plan is defined as a sequence of actions $\Pi_g=\{\Delta, \prec\}$ that attains the task goals, where $\Delta \subseteq {{\mathcal A}}$ is a non-empty set of actions and $\prec$ is a total-order relationship among the actions of $\Delta$. However, other MAP models assume a more general definition of a plan; for example, as a set of of sequences of actions (one sequence per agent), as in @Kvarnstrom11; or as a partial-order plan @Torreno12ECAI. In the following, we will consider a solution plan as a set of partially-ordered actions.

The action distribution model of <span><span>MA-STRIPS</span></span>, introduced in Definition \[MAP\_task\_def\], classifies each atom $p \in {{\mathcal P}}$ as either *internal* (private) to an agent $i \in {{\mathcal{AG}}}$, if it is only used and affected by the actions in ${{\mathcal A}}^i$, or *public* to all the agents in ${{\mathcal{AG}}}$. ${{\mathcal P}}^i_{int}$ denotes the atoms that are internal to agent $i$, while ${{\mathcal P}}_{pub}$ refers to the public atoms of the task. The distribution of the information of a MAP task ${{\mathcal T}}$ configures the *local view* that an agent $i$ has over ${{\mathcal T}}$, ${{\mathcal T}}^i$, which is formally defined as follows:

\[Local\_view\] The **local view** of a task ${{\mathcal T}}=\langle {{\mathcal{AG}}}, {{\mathcal P}}, {{\mathcal A}},{{\mathcal I}},{{\mathcal G}}\rangle$ by an agent $i  \in {{\mathcal{AG}}}$ is defined as ${{\mathcal T}}^i =  \langle{{\mathcal P}}^i,{{\mathcal A}}^i,{{\mathcal I}}^i,{{\mathcal G}}\rangle$, which includes the following elements:

-   ${{\mathcal P}}^i={{\mathcal P}}^i_{int}\cup{{\mathcal P}}_{pub}$ denotes the atoms accessible by agent $i$.

-   ${{\mathcal A}}^i \subseteq {{\mathcal A}}$ is the set of planning actions of $i$.

-   ${{\mathcal I}}^i \subseteq {{\mathcal P}}^i$ is the set of atoms of the initial state accessible by agent $i$.

-   ${{\mathcal G}}$ denotes the common goal of the task ${{\mathcal T}}$. An agent $i$ knows all the atoms of ${{\mathcal G}}$ and it will contribute to their achievement either directly (achieving a goal $g \in {{\mathcal G}}$) or indirectly (reaching effects that help other agents achieve $g$).

Note that Definition \[Local\_view\] does not specify ${{\mathcal G}}^i$, a set of individual goals of an agent $i$, because in a cooperative MAP context the common goal ${{\mathcal G}}$ is shared among all agents and it is never assigned to some particular agent (see next section for more details).

Characterization of a MAP Task {#characterization}
------------------------------

This section introduces a brief example based on a logistics domain @Torreno14 in order to illustrate the characteristics of a MAP task.

![MAP task examples: task ${{\mathcal T}}_1$ (left) and task ${{\mathcal T}}_2$ (right)<span data-label="ExampleFig"></span>](Examples4.pdf){width="10.5cm"}

Consider the transportation task ${{\mathcal T}}_1$ in Figure \[ExampleFig\] (left), which includes three different agents. There are two transport agencies, $ta1$ and $ta2$, each of them having a truck, $t1$ and $t2$, respectively. The two transport agencies work in two different geographical areas, $ga1$ and $ga2$, respectively. The third agent is a factory, $ft$, located in the area $ga2$. In order to manufacture products, factory $ft$ requires a package of raw materials, $p$, which must be collected from area $ga1$. In this task, agents $ta1$ and $ta2$ have the same planning capabilities, but they operate in different geographical areas; i.e., they are *spatially* distributed agents. Moreover, the factory agent $ft$ is *functionally* different from $ta1$ and $ta2$.

The goal of task ${{\mathcal T}}_1$ is for $ft$ to manufacture a final product $fp$. For solving this task, $ta1$ will use its truck $t1$ to load the package of raw materials $p$, initially located in $l2$, and then it will transport $p$ to a storage facility, $sf$, that is located at the intersection of both geographical areas. Then, $ta2$ will complete the delivery by using its truck $t2$ to transport $p$ from $sf$ to the factory $ft$, which will in turn manufacture the final product $fp$. Therefore, this task involves three specialized agents, which are spatially or functionally distributed, and must cooperate to accomplish the common goal of having a final manufactured product $fp$.

Task ${{\mathcal T}}_1$ defines a <span>*group goal*</span>; i.e., a goal that requires the participation of all the agents in order to solve it. Given a task ${{\mathcal T}}_g=\langle {{\mathcal{AG}}}, {{\mathcal P}}, {{\mathcal A}}, {{\mathcal I}}, \{g\}\rangle$ which includes a single goal $g$, we say that $g$ is a <span>group goal</span>if for every solution plan $\Pi_g=\{\Delta, \prec\}$, $\exists \alpha, \beta \in \Delta: \alpha \in {{\mathcal A}}^i, \beta \in {{\mathcal A}}^j$ and $i \neq j$. We can thus distinguish between <span>group goals</span>, which require the participation of more than one agent, and non-<span>group goals</span>, which can be independently achieved by a single agent.

The presence or absence of <span>group goals</span>often determines the complexity of a cooperative MAP task. Figure \[ExampleFig\] (right) depicts task ${{\mathcal T}}_2$, where the goal is to deliver the package $p$ into the factory $ft$. This is a non-group goal because agent $ta1$ is capable of attaining it by itself, gathering $p$ in $l1$ and transporting it to $ft$ through the locations of its area $ga1$. However, the optimal solution for this task is that agent $ta1$ takes $p$ to $sf$ so that agent $ta2$ loads then $p$ in $sf$ and completes the delivery to the factory $ft$ through location $l7$. These two examples show that cooperative MAP involves multiple agents working together to solve tasks that they are unable to attain by themselves (task ${{\mathcal T}}_1$), or tasks that are accomplished better by cooperating (task ${{\mathcal T}}_2$) @deWeerdt09.

\[views\]

Tasks ${{\mathcal T}}_1$ and ${{\mathcal T}}_2$ emphasize most of the key elements of a MAP context. The spatial and/or functional distribution of the participants gives rise to *specialized agents* that have different capabilities and knowledge of the task. Information of the MAP tasks is distributed among the specialized agents as summarized in Table \[views\]. Atoms of the form $\mathit{(pos\;t1\;*)}$ (note that $*$ acts as a wildcard) are accessible to agent $ta1$, since they model the position of truck $t1$. Atoms of the form $\mathit{(pos\;t2\;*)}$, which describe the location of truck $t2$, are accessible to agent $ta2$. Finally, $\mathit{(pending\;fp)}$ belongs to agent $ft$ and denotes that the manufacturing of $fp$ (the goal of task ${{\mathcal T}}_1$) is still pending.

The atoms related to the location of the product $p$, $\mathit{(at\;p\;*)}$, as well as $\mathit{(manufactured\;fp)}$, which indicates that the final product $fp$ is already manufactured, are accessible to the three agents, $ta1$, $ta2$ and $ft$. Since agents ignore the configuration of the working area of the other agents, the knowledge of agent $ta1$ regarding the location of $p$ is restricted to the atoms $\mathit{(at\;p\;l1)}$, $\mathit{(at\;p\;l2)}$, $\mathit{(at\;p\;sf)}$ and $\mathit{(at\;p\;t1)}$, while agent $ta2$ knows $\mathit{(at\;p\;sf)}$, $\mathit{(at\;p\;l3)}$, $\mathit{(at\;p\;l4)}$, $\mathit{(at\;p\;t2)}$ and $\mathit{(at\;p\;ft)}$. The awareness of agent $ft$ with respect to the location of $p$ is limited to $\mathit{(at\;p\;ft)}$.

The information distribution of a MAP task stresses the issue of *privacy*, which is one of the basic aspects that must be considered in multi-agent applications @Such13. Agents manage information that is not relevant for their counterparts or sensitive data of their internal operational mechanisms that they are not willing to disclose. For instance, $ta1$ and $ta2$ cooperate in solving tasks ${{\mathcal T}}_1$ and ${{\mathcal T}}_2$ but they could also be potential competitors since they work in the same business sector. For these reasons, providing privacy mechanisms to guarantee that agents do not reveal the internal configuration of their working areas to each other is a key issue.

In general, agents in MAP seek to minimize the information they share with each other, thus exchanging only the information that is relevant for other participating agents to solve the MAP task.

Modelling of a MAP Task with <span>*MA-PDDL*</span> {#specification}
---------------------------------------------------

The adoption of a common language for modelling planning domains allows for a direct comparison of different approaches and increases the availability of shared planning resources, thus facilitating the scientific development of the field @Fox03. Modelling a cooperative MAP task involves defining several elements that are not present in single-agent planning tasks. Widely-adopted single-agent planning task specification languages, such as <span>*PDDL*</span>@Ghallab98, lack the required machinery to specify a MAP task. Recently, <span>*MA-PDDL*</span>[^3], the multi-agent version of <span>*PDDL*</span>, was developed in the context of the 2015 <span><span>CoDMAP</span></span>competition @Komenda16codmap as the first attempt to create a *de facto* standard specification language for MAP tasks. We will use <span>*MA-PDDL*</span>as the language for modelling MAP tasks.

MAP solvers that accept an *unfactored* specification of a MAP task use a single input that describes the complete task ${{\mathcal T}}$. In contrast, other MAP approaches require a *factored* specification; i.e., the local view of each agent, ${{\mathcal T}}^i$. Additionally, modelling a MAP task may require the specification of the private information that an agent cannot share with other agents.

<span>*MA-PDDL*</span>allows for the definition of both factored (<span>:factored-privacy</span> requirement) and unfactored (<span>:unfactored-privacy</span> requirement) task representations. In order to model the transportation task ${{\mathcal T}}_1$ (see Figure \[ExampleFig\] (left) in Section \[characterization\]), we will use the factored specification. Task ${{\mathcal T}}^i_1$ of agent $i$ is encoded by means of two independent files: the *domain* file describes general aspects of the task (${{\mathcal P}}^i$ and ${{\mathcal A}}^i$, which can be reused for solving other tasks of the same typology); the *problem* file contains a description of the particular aspects of the task to solve (${{\mathcal I}}^i$ and ${{\mathcal G}}$). For the sake of simplicity, we only display fragments of the task ${{\mathcal T}}_1^{ta1}$.

The domain description of agents of type <span><span>transport-agency</span></span>, like $ta1$ and $ta2$, is defined in Listing \[domain\_agency\].

    (define (domain transport-agency)
      (:requirements :factored-privacy :typing :equality :fluents)    
      (:types transport-agency area location package product - object
              truck place - location
              factory - place)  
      (:predicates 
        (manufactured ?p - product) (at ?p - package ?l - location)
        (:private
          (area ?ag - transport-agency ?a - area) (in-area ?p - place ?a - area)
          (owner ?a - transport-agency ?t - truck) (pos ?t - truck ?l - location)
          (link ?p1 - place ?p2 - place) 
        )
      )  
      (:action drive
        :parameters   (?ag - transport-agency ?a - area ?t - truck ?p1 - place ?p2 - place)
        :precondition (and (area ?ag ?a) (in-area ?p1 ?a) (in-area ?p2 ?a)
                      (owner ?a ?t) (pos ?t ?p1) (link ?p1 ?p2))
        :effect       (and (not (pos ?t ?p1)) (pos ?t ?p2))
      )  
    [...]
    )

The domain of <span><span>transport-agencies</span></span>starts with the type hierarchy, which includes the types <span><span>transport-agency</span></span>and <span>factory</span> to define the agents of the task. Note that the type <span>factory</span> is defined as a subtype of <span>place</span> because a <span>factory</span> is also interpreted as a <span>place</span> reachable by a truck. The remaining elements of the task are identified by means of the types <span>location</span>, <span>package</span>, <span>truck</span>, etc.

The <span>:predicates</span> section includes the set of first-order *predicates*, which are patterns to generate the agent's propositions, ${{\mathcal P}}^i$, through the instantiation of their parameters. The domain for <span><span>transport-agencies</span></span>includes the public predicates <span>at</span>, which models the position of the <span>packages</span>, and <span>manufactured</span>, which indicates that the task goal of manufacturing a <span>product</span> is fulfilled. Despite the fact that only the <span>factory</span> agent $ft$ has the ability to manufacture <span>products</span>, all the agents have access to the predicate <span>manufactured</span> so that the <span><span>transport-agencies</span></span>will be informed when the task goal is achieved.

The remaining predicates in Listing \[domain\_agency\] are in the section <span>:private</span> of each <span><span>transport-agency</span></span>, meaning that agents will not disclose information concerning the topology of their working <span>areas</span> or the status of their <span>trucks</span>.

Finally, the <span>:action</span> block of Listing \[domain\_agency\] shows the *action schema* <span>drive</span>. An action schema represents a number of different actions that can be derived by instantiating its variables. Agents $ta1$ and $ta2$ have three action schemas: <span>load</span>, <span>unload</span> and <span>drive</span>.

Regarding the *problem* description, the factored specification includes three problem files, one per agent, that contain ${{\mathcal I}}^i$, the initial state of each agent, and the task goals ${{\mathcal G}}$.

    (define (problem ta1)
      (:domain transport-agency)
      (:objects
        ta1 - transport-agency
        ga1 - area                  l1 l2 sf - place
        p - package                 fp - product
        (:private t1 - truck)
      )    
      (:init
        (area ta1 ga1) (pos t1 l1) (owner t1 ta1) (at p l1)
        (link l1 l2) (link l2 l1) (link l1 sf)
        (link sf l1) (link l2 sf) (link sf l2)
        (in-area l1 ga1) (in-area l2 ga1) (in-area sf ga1)
      )  
      (:goal (manufactured fp))
    )

Listing \[problem\_ta1\] depicts the problem description of task ${{\mathcal T}}_1^{ta1}$. The information managed by $ta1$ is related to its <span>truck t1</span> (which is defined as <span>:private</span> to prevent $ta1$ from disclosing the location or cargo of <span>t1</span>), along with the <span>places</span> within its working <span>area</span>, <span>ga1</span>, and the <span>package p</span>. The <span>:init</span> section of Listing \[problem\_ta1\] specifies ${{\mathcal I}}^{ta1}$; i.e., the location of <span>truck t1</span> and the position of <span>package p</span>, which is initially located in <span>ga1</span>. Additionally, $ta1$ is aware of the <span>links</span> and <span>places</span> within its <span>area</span> <span>ga1</span>. The <span>:goal</span> section is common to the three agents in ${{\mathcal T}}_1$ and includes a single goal indicating that the <span>product fp</span> must be <span>manufactured</span>.

This modelling example shows the flexibility of <span>*MA-PDDL*</span>for encoding the specific requirements of a MAP task, such as the agents' distributed information via factored input and the private aspects of the task. These functionalities make <span>*MA-PDDL*</span>a fairly expressive language to specify MAP tasks.

Main Aspects of a MAP Solver {#aspects}
============================

Solving a cooperative MAP task requires various features such as information distribution, specialized agents, coordination or privacy. The different MAP solving techniques in the literature can be classified according to the mechanisms they use to address these functionalities. We identify six main features to categorize cooperative MAP solvers:

-   **Agent distribution**: From a conceptual point of view, MAP is regarded as a task in which multiple agents are involved, either as entities participating in the plan synthesis (planning agents) or as the target entities of the planning process (actuators or execution agents).

-   **Computational process**: From a computational perspective, MAP solvers use a *centralized* or *monolithic* design that solves the MAP task through a central process, or a *distributed* approach that splits the planning activity among several processing units.

-   **Plan synthesis schemes**: There exist a great variety of strategies to tackle the process of synthesizing a plan for the MAP task, mostly characterized by how and when the *coordination* activity is applied. Coordination comprises the distributed information exchange processes by which the participating agents organize and harmonize their activities in order to work together properly.

-   **Communication mechanisms**: Communication among agents is an essential aspect that distinguishes MAP from single-agent planning. The type of communication enabled in MAP solvers is highly dependent on the type of computational process (centralized or distributed) of the solver. Thus, we will classify solvers according to the use of internal or external communication infrastructures.

-   **Heuristic search**: As in single agent planning, MAP solvers commonly apply heuristic search to guide the planning process. In MAP, we can distinguish between *local* heuristics (each agent $i$ calculates an estimate to reach the task goals ${{\mathcal G}}$ using only its accessible information in ${{\mathcal T}}^i$) or *global* heuristics (the estimate to reach ${{\mathcal G}}$ is calculated among all the agents in ${{\mathcal{AG}}}$).

-   **Privacy preservation**: Privacy is one of the main motivations to adopt a MAP approach. Privacy means coordinating agents without making sensitive information publicly available. Whereas this aspect was initially neglected in former MAP solvers @Krogt09, the most recent approaches tackle this issue through the development of robust privacy-preserving algorithms.

The following subsections provide an in-depth analysis of these aspects, which characterize and determine the performance of the existing MAP solvers.

Agent Distribution
------------------

Agents in MAP can adopt different roles: planning agents are *reasoning* entities that synthesize the course of action or plan that will be later executed by a set of *actuators* or *execution agents*. An execution agent can be, among others, a robot in a multi-robot system, or a software entity in an execution simulator.

From a conceptual point of view, MAP solvers are characterized by the agent distribution they apply; i.e., the number of planning and execution agents involved in the task. Typically, it is assumed that one planning agent from the set ${{\mathcal{AG}}}$ of a MAP task ${{\mathcal T}}$ is associated with one actuator in charge of executing the actions of this planning agent in the solution plan. However, some MAP solvers alter this balance between planning and acting agents.

Table \[conceptual\_schemes\] summarizes the different schemes according to the relation between the number of planning and execution agents. Single-agent planning is the simplest mapping: the task is solved by a single planning agent, i.e., $|{{\mathcal{AG}}}|=1$, and executed by a single actuator. We can mention Fast Downward (<span><span>FD</span></span>) @Helmert06 as one of the most utilized single-agent planners within the planning community.

\[conceptual\_schemes\]

MAP solvers like <span><span>Distoplan</span></span>@Fabre10, <span><span>A\#</span></span>@Jezequel12 and <span><span>ADP</span></span>@Crosby13 follow a *factored* agent distribution inspired by the factored planning scheme @Amir03. Under this paradigm, a single-agent planning task is decomposed into a set of independent factors (agents), thus giving rise to a MAP task with $|{{\mathcal{AG}}}|>1$. Then, factored methods to solve the agents' local tasks ${{\mathcal T}}^i$ are applied, and finally, the computed local plans are pieced together into a valid solution plan @Brafman06. Factored planning exploits locality of the solutions and a limited information propagation between components.

The second row of Table \[conceptual\_schemes\] outlines the classification of MAP approaches that build a plan that is conceived to be then executed by several actuators. Some solvers in the literature regard MAP as a single planning agent working *for* a set of actuators ($|{{\mathcal{AG}}}|=1$), while other approaches regard MAP as planning *by* multiple planners ($|{{\mathcal{AG}}}|>1$).

### Planning *for* multiple agents

Under this scheme, the actions of the solution plan are distributed among actuators typically via the introduction of constraints. <span><span>TFPOP</span></span>@Kvarnstrom11 applies single-agent planning for multi-agent domains where each execution agent is associated with a sequential thread of actions within a partial-order plan. The combination of forward-chaining and least-commitment of <span><span>TFPOP</span></span>provides flexible schedules for the acting agents, which execute their actions in parallel. The work in @Crosby14 transforms a MAP task that involves multiple agents acting concurrently and cooperatively in a single-agent planning task. The transformation compels agents to select joint actions associated with a single subset of objects at a time, and ensures that the concurrency constraints on this subset are satisfied.The result is a single-agent planning problem in which agents perform actions individually, one at a time.

The main limitation of this planning-for-multiple-agents scheme is its lack of privacy, since the planning entity has complete access to the MAP task ${{\mathcal T}}$. This is rather unrealistic if the agents involved in the task have sensitive private information they are not willing to disclose @Sapena08. Therefore, this scheme is not a suitable solution for privacy-preserving MAP tasks like task ${{\mathcal T}}_1$ described in section \[characterization\].

### Planning *by* multiple agents

This scheme distributes the MAP task among several planning agents where each is associated with a local task ${{\mathcal T}}^i$. Thus, planning-by-multiple-agents puts the focus on the coordination of the planning activities of the agents. Unlike single-planner approaches, the planning decentralization inherent to this scheme makes it possible to effectively preserve the agents' privacy.

In general, solvers that follow this scheme, such as <span><span>FMAP</span></span>@Torreno12ECAI, maintain a one-to-one correspondence between planning and execution agents; that is, planning agents are assumed to solve their tasks, which will be later executed by their corresponding actuators. There exist, however, some exceptions in the literature that break this one-to-one correspondence such as <span><span>MARC</span></span>@marc-codmap15, which rearranges the $n$ planning agents in ${{\mathcal{AG}}}$ into $m$ *transformer agents* ($m < n$), where a transformer agent comprises the planning tasks of several agents in ${{\mathcal{AG}}}$. All in all, <span><span>MARC</span></span>considers $m$ reasoning entities that plan for $n$ actuators, where $m < n$.

![Centralized (monolithic) vs. distributed (agent-based) implementation<span data-label="FigDistribution"></span>](Distribution2.pdf){width="10.4cm"}

Computational process
---------------------

From a computational standpoint, MAP solvers are classified as *centralized* or *distributed*. Centralized solvers draw upon a monolithic implementation in which a central process synthesizes a global solution plan for the MAP task. In contrast, distributed MAP methods are implemented as multi-agent systems in which the problem-solving activity is fully decentralized.

#### Centralized MAP

In this approach, the MAP task ${{\mathcal T}}$ is solved on a single machine regardless the number of planning agents conceptually considered by the solver. The main characteristic of a centralized MAP approach is that tasks are solved in a monolithic fashion, so that all the processes of the MAP solver, $\{P_1,\ldots,P_n\}$, are run in one same machine (see Figure \[FigDistribution\] (left)).

The motivation for choosing a centralized MAP scheme is twofold: 1) external communication mechanisms to coordinate the planning agents are not needed; and 2) robust and efficient single-agent planning technology can be easily reused.

Regarding agent distribution, MAP solvers that use a single planning agent generally apply a centralized computational scheme, as for example <span><span>TFPOP</span></span>@Kvarnstrom11 (see Table \[conceptual\_schemes\]). On the other hand, some algorithms that conceptually rely on the distribution of the MAP task among several planning agents do not actually implement them as software agents, but as a centralized procedure. For example, <span><span>MAPR</span></span>@Borrajo13 establishes a sequential order among the planning agents and applies a centralized planning process that incrementally synthesizes a solution plan by solving the agents' local tasks in the predefined order.

#### Distributed MAP

Many approaches that conceive MAP as planning by multiple agents (see Table \[conceptual\_schemes\]), are developed as multi-agent systems (MAS) defined by several independent *software agents*. By software agent, we refer to a computer system that 1) makes decisions without any external intervention (autonomy), 2) responds to changes in the environment (reactivity), 3) exhibits goal-directed behaviour by taking the initiative (pro-activeness), and 4) interacts with other agents via some communication language in order to achieve its objectives (social ability) @Wooldridge97.

In this context, a software agent of a MAS plays the role of a planning agent in ${{\mathcal{AG}}}$. This way, in approaches that follow the *planning by multiple agents* scheme introduced in the previous section, a software agent encapsulates the local task ${{\mathcal T}}^i$ of a planning agent $i \in {{\mathcal{AG}}}$. Given a task, where $|{{\mathcal{AG}}}|=n$, distributed MAP solvers can be run on up to $n$ different hosts or machines (see Figure \[FigDistribution\] (right)).

The emphasis of the distributed or agent-based computation lies in the coordination of the concurrent activities of the software planning agents. Since agents may be run on different hosts (see Figure \[FigDistribution\] (right)), having a proper communication infrastructure and message-passing protocols is vital for the synchronization of the agents.

Distributed solvers like <span><span>FMAP</span></span>@Torreno14 launch $|{{\mathcal{AG}}}|$ software agents that seamlessly operate on different machines. <span><span>FMAP</span></span>builds upon the MAS platform <span><span>Magentix2</span></span>@Such12, which provides the messaging infrastructure for agents to communicate over the network.

Plan synthesis schemes {#planning-coordination}
----------------------

In most MAP tasks, there are dependencies between agents' actions and none of the participants has sufficient competence, resources or information to solve the entire problem. For this reason, agents must coordinate with each other in order to cooperate and solve the MAP task properly.

Coordination is a multi-agent process that harmonizes the agents' activities, allowing them to work together in an organized way. In general, coordination involves a large variety of activities, such as distributing the task goals among the agents, making joint decisions concerning the search for a solution plan, or combining the agents' individual plans into a solution for a MAP task. Since coordination is an inherently distributed mechanism, it is only required in MAP solvers that conceptually draw upon multiple planning agents (see right column of Table \[conceptual\_schemes\]).

The characteristics of a MAP task often determine the coordination requirements for solving the task. For instance, tasks that feature <span>group goals</span>, like the task ${{\mathcal T}}_1$ depicted in section \[characterization\], usually demand a stronger coordination effort. Therefore, the capability and efficiency of a MAP solver is determined by the coordination strategy that governs its behaviour.

The following subsections analyse the two principal coordination strategies in MAP; namely, *unthreaded* and *interleaved* planning and coordination.

![Plan synthesis schemes in unthreaded planning and coordination<span data-label="FigUnthreaded"></span>](Unthreaded_schemes2.pdf){width="13.8cm"}

### Unthreaded Planning and Coordination

This strategy defines planning and coordination as *sequential* activities, such that they are viewed as two separate black boxes. Under this strategy, an agent $i \in {{\mathcal{AG}}}$ synthesizes a plan to its local view of the task, ${{\mathcal T}}^i$, and coordination takes place *before* or/and *after* planning.

#### Pre-planning coordination

Under this plan synthesis scheme, the MAP solver defines the necessary constrains to guarantee that the plans that solve the local tasks of the agents are properly combined into a consistent solution plan for the whole task ${{\mathcal T}}$ (see Figure \[FigUnthreaded\] (a)).

<span><span>ADP</span></span>@Crosby13 follows this scheme by applying an *agentification* procedure that distributes a <span><span>STRIPS</span></span>planning task among several planning agents (see Table \[conceptual\_schemes\]). More precisely, <span><span>ADP</span></span>is a fully automated process that inspects the multi-agent nature of the planning task and calculates an agent decomposition that results in a set of $n$ decoupled local tasks. By leveraging this agent decomposition, <span><span>ADP</span></span>applies a centralized, sequential and total-order planning algorithm that yields a solution for the original <span><span>STRIPS</span></span>task. Since the task ${{\mathcal T}}$ is broken down into several local tasks independent from each other, the local solution plans are consistently combined into a solution for ${{\mathcal T}}$. Ultimately, the purpose of pre-planning coordination is to guarantee that the agents' local plans are seamlessly combined into a solution plan that attains the goals of the MAP task, thus avoiding the use of plan merging techniques at post-planning time.

#### Post-planning coordination

Other unthreaded MAP solvers put the coordination emphasis *after* planning. In this case, the objective is to *merge* the plans that solve the agents' local tasks, $\{{{\mathcal T}}^1, \ldots, {{\mathcal T}}^n\}$, into a solution plan that attains the goals ${{\mathcal G}}$ of the task ${{\mathcal T}}$ by removing inconsistencies among the local solutions (see Figure \[FigUnthreaded\] (b)).

In <span><span>PMR</span></span>(Plan Merger by Reuse) @Luis14, the local plans of the agents are concatenated into a solution plan for the MAP task. Other post-planning coordination approaches apply an information exchange between agents to come up with the global solution. For instance, <span><span>PSM</span></span>@Tozicka15 draws upon a set of finite automata, called Planning State Machines (PSM), where each automaton represents the set of local plans of a given agent. In one iteration of the <span><span>PSM</span></span>procedure, each agent $i$ generates a plan that solves its local task ${{\mathcal T}}^i$, incorporating this plan into its associated PSM. Then, agents exchange the public projection of their PSMs, until a solution plan for the task ${{\mathcal T}}$ is found.

#### Iterative response planning

This plan synthesis scheme, firstly introduced by <span><span>DPGM</span></span>@Pellier10, successively applies a planning-coordination sequence, each corresponding to a planning agent. An agent $i$ receives the local plan of the preceding agent along with a set of constraints for coordination purposes, and *responds* by building up a solution for its local task ${{\mathcal T}}^i$ on top of the received plan. Hence, the solution plan is incrementally synthesized (see Figure \[FigUnthreaded\] (c)).

Multi-Agent Planning by Reuse (<span><span>MAPR</span></span>) @Borrajo13 is an iterative response solver based on *goal allocation*. The task goals ${{\mathcal G}}$ are distributed among the agents before planning, such that an agent $i$ is assigned a subset ${{\mathcal G}}^i \subset {{\mathcal G}}$, where $\bigcap_{i \in {{\mathcal{AG}}}} {{\mathcal G}}^i = \emptyset$. Additionally, agents are automatically arranged in a sequence that defines the order in which the iterative response scheme must be carried out.

In unthreaded planning and coordination schemes, agents do not need communication skills because they do not interact with each other during planning. This is the reason why the unthreaded strategy is particularly efficient for solving tasks that do not require a high coordination effort. In contrast, it presents several limitations when solving tasks with <span>group goals</span>, due to the fact that agents are unable to discover and address the cooperation demands of other agents. The needs of cooperation that arise when solving <span>group goals</span>are hard to discover at pre-planning time, and plan merging techniques are designed only to fix inconsistencies among local plans, rather than repairing the plans to satisfy the inter-agent coordination needs. Consequently, unthreaded approaches are more suitable for solving MAP task that do not contain <span>group goals</span>; that is, every task goal can be solved by at least one single agent.

![Multi-agent search in interleaved planning and coordination<span data-label="FigInterleaved"></span>](Interleaved_scheme.pdf){width="6.2cm"}

### Interleaved Planning and Coordination {#interleaved}

A broad range of MAP techniques *interleave* the planning and coordination activities. This coordination strategy is particularly appropriate for tasks that feature <span>group goals</span>since agents explore the search space jointly to find a solution plan, rather than obtaining local solutions individually. In this context, agents continuously coordinate with each other to communicate their findings, thus effectively intertwining planning and coordination.

Most interleaved solvers, such as <span><span>MAFS</span></span>@Nissim12 and <span><span>FMAP</span></span>@Torreno14, commonly rely on a *coordinated multi-agent search* scheme, wherein nodes of the search space are contributed by several agents (see Figure \[FigInterleaved\]). This scheme involves selecting a node for expansion (planning) and exchanging the successor nodes among the agents (coordination). Agents thus jointly explore the search space until a solution is found, alternating between phases of planning and coordination.

Different forms of coordination are applicable in the interleaved resolution strategy. In <span><span>FMAP</span></span>@Torreno14, agents share an open list of plans and jointly select the most promising plan according to global heuristic estimates. Each agent $i$ expands the selected node using its actions ${{\mathcal A}}^i$, and then, agents evaluate and exchange all the successor plans. In <span><span>MAFS</span></span>@Nissim12, each agent $i$ keeps an independent open list of states. Agents carry out the search simultaneously: an agent $i$ selects a state $S$ to expand from its open list according to a local heuristic estimate, and synthesizes all the nodes that can be generated through the application of the actions ${{\mathcal A}}^i$ over $S$. Out of all the successor nodes, agents only share the states that are relevant to other agents.

Interleaving planning and coordination is very suitable for solving complex tasks that involve <span>group goals</span>and a high coordination effort. By using this strategy, agents learn the cooperation requirements of other participants during the construction of the plan and can immediately address them. Hence, the interleaved scheme allows agents to efficiently address <span>group goals</span>.

The main drawback of this coordination strategy is the high communication cost in a distributed MAP setting because alternating planning and coordination usually entails exchanging a high number of messages in order to continuously coordinate agents.

Communication mechanisms {#comm}
------------------------

Communication among agents plays a central role in MAP solvers that conceptually define multiple planners (see Table \[conceptual\_schemes\]), since planning agents must coordinate their activities in order to accomplish the task goals. As shown in Figure \[FigDistribution\], different agent communication mechanisms can be applied, depending on the computational process followed by the MAP solver.

#### Internal communication

Solvers that draw upon a centralized implementation resort to *internal* or simulated multi-agent communication. For example, the centralized solver <span><span>MAPR</span></span>@Borrajo13 distributes the task goals, ${{\mathcal G}}$, among the planning agents, and agents solve their local tasks sequentially. Once a local plan $\Pi^i$ for an agent $i \in AG$ is computed, the information of $\Pi^i$ is used as an input for the next agent in the sequence, $j$, thus simulating a message passing between agents $i$ and $j$. This type of simple and simulated communication system is all that is required in centralized solvers that run all planning agents in a single machine.

#### External communication

As displayed in Figure \[FigDistribution\] (right), distributed MAP solvers draw upon *external* communication mechanisms by which different processes (agents), potentially allocated on different machines, exchange messages in order to interact with each other. External communication can be easily enabled by linking the different agents via network sockets or a messaging broker. For example, agents in <span><span>MAPlan</span></span>@maplan-codmap15 exchange data over the TCP/IP protocol when the solver is executed in a distributed manner. A common alternative to implement external communication in MAS implies using a message passing protocol compliant with the IEEE FIPA standards @FIPA02protocol, which are intended to promote the interoperation of heterogeneous agents. The <span><span>Magentix2</span></span>MAS platform @Such12 used by <span><span>MH-FMAP</span></span>@Torreno15 facilitates the implementation of agents with FIPA-compliant messaging capabilities.

The use of external communication mechanisms allows distributed solvers to run the planning agents in decentralized machines and to coordinate their activities by exchanging messages through the network. The flexibility provided by external communication mechanisms comes at the cost of performance degradation. The results of the 2015 <span><span>CoDMAP</span></span>competition @Komenda16codmap show that centralized solvers like <span><span>ADP</span></span>@Crosby13 outperform solvers executed in a distributed setting, such as <span><span>PSM</span></span>@psm-codmap15. Likewise, an analysis performed in @Torreno14 reveals that communication among agents is the most time-consuming activity of the distributed approach <span><span>FMAP</span></span>, thus compromising the overall scalability of this solver. Nevertheless, the participants in the distributed track of the <span><span>CoDMAP</span></span>exhibited a competitive performance, which proves that the development of fully-distributed MAP solvers is worth the overhead caused by external communication infrastructures.

Heuristic Search {#heuristic}
----------------

Ever since the introduction of <span><span>HSP</span></span> @Long00, the use of heuristic functions that guide the search by estimating the quality of the nodes of the search tree has proven to be one of the most robust and reliable problem-solving strategies in single-agent planning. Over the years, many solvers based on heuristic search, such as <span><span>FF</span></span> @Hoffmann01 or <span><span>LAMA</span></span> @Richter10, have consistently dominated the International Planning Competitions[^4].

Since most MAP solvers stem from single-agent planning techniques, heuristic search is one of the most common approaches in the MAP literature. In general, in solvers that synthesize a plan for multiple executors, the single planning agent (see Table \[conceptual\_schemes\]) has complete access to the MAP task ${{\mathcal T}}$, and so it can compute heuristics that leverage the *global* information of ${{\mathcal T}}$, in a way that is very similar to that of single-agent planners. However, in solvers that feature multiple planning agents, i.e., $|{{\mathcal{AG}}}| > 1$, each agent $i$ is only aware of the information defined in ${{\mathcal T}}^i$ and no agent has access to the complete task ${{\mathcal T}}$. Under a scheme of planning by multiple agents, one can distinguish between *local* and *global* heuristics.

In local heuristics, an agent $i$ estimates the cost of the task goals, ${{\mathcal G}}$, using only the information in ${{\mathcal T}}^i$. The simplicity of local heuristics, which do not require any interactions among agents, contrasts with the low accuracy of the estimates they yield due to the limited task view of the agents. Consider, for instance, the example task ${{\mathcal T}}_1$ presented in section \[characterization\]: agent $ta1$ does not have sufficient information to compute an accurate estimate of the cost to reach the goals of ${{\mathcal T}}_1$ since ${{\mathcal T}}^{ta1}_1$ does not include the configuration of the area $ga2$. In general, if ${{\mathcal T}}^i$ is a limited view of ${{\mathcal T}}$, local heuristics will not yield informative estimates of the cost of reaching ${{\mathcal G}}$.

In contrast, a global heuristic in MAP is the application of a heuristic function "carried out by several agents which have a different knowledge of the task and, possibly, privacy requirements" @Torreno15. The development of global heuristics for multi-agent scenarios must account for additional features that make heuristic evaluation an arduous task @Nissim12:

-   Solvers based on distributed computation require robust communication protocols for agents to calculate estimates for the overall task.

-   For MAP approaches that preserve agents' privacy, the communication protocol must ensure that estimates are computed without disclosing sensitive private data.

The application of local or global heuristics is also determined by the characteristics of the plan synthesis scheme of the MAP solver. Particularly, in an *unthreaded* planning and coordination scheme, agents synthesize their local plans through the application of local heuristic functions. For instance, in the sequential plan synthesis scheme of <span><span>MAPR</span></span>@Borrajo13, agents apply locally $h_{FF}$ @Hoffmann01 and $h_{Land}$ @Richter10 when solving their allocated goals.

Local heuristic search has also been applied by some *interleaved* MAP solvers. Agents in <span><span>MAFS</span></span>and <span><span>MAD-A\*</span></span>@Nissim14 generate and evaluate search states locally. An agent $i$ shares a state $S$ and local estimate $h^i(S)$ only if $S$ is relevant to other planning agents. Upon reception of $S$, agent $j$ performs its local evaluation of $S$, $h^j(S)$. Then, depending on the characteristics of the heuristic, the final estimate of $S$ by agent $j$ will be either $h^i(S)$, $h^j(S)$, or a combination of both. In @Nissim12, authors test <span><span>MAD-A\*</span></span>with two different optimal heuristics, <span><span>*LM-Cut*</span></span>@Helmert09 and <span><span>*Merge&Shrink*</span></span>@Helmert07, both locally applied by each agent. Despite heuristics being applied only locally, <span><span>MAD-A\*</span></span>is proven to be cost-optimal.

Unlike unthreaded solvers, the interleaved planning and coordination strategy makes it possible to accommodate global heuristic functions. In this case, agents apply some heuristic function on their tasks ${{\mathcal T}}^i$ and then they exchange their local estimates to come up with an estimate for the global task ${{\mathcal T}}$.

<span><span>GPPP</span></span>@Maliah14 introduces a distributed version of a privacy-preserving *landmark* extraction algorithm for MAP. A landmark is a proposition that must be satisfied in every solution plan of a MAP task @Hoffman04. The quality of a plan in <span><span>GPPP</span></span>is computed as the sum of the local estimates of the agents in ${{\mathcal{AG}}}$. <span><span>GPPP</span></span>outperforms <span><span>MAFS</span></span>thanks to the accurate estimates provided by this landmark-based heuristic. <span><span>MH-FMAP</span></span>@Torreno15, the latest version of <span><span>FMAP</span></span>, introduces a multi-heuristic alternation mechanism based on Fast Downward (<span><span>FD</span></span>) @Helmert06. Agents alternate two global heuristics when expanding a node in their tasks: $h_{DTG}$, which draws upon the information of the *Domain Transition Graphs* @Helmert04 associated with the state variables of the task, and the landmark-based heuristic $h_{Land}$, which only evaluates the *preferred successors* @Torreno15. Agents jointly build the DTGs and the landmarks graph of the task and each of them stores its own version of the graphs according to its knowledge of the MAP task.

Some recent work in the literature focuses on the adaptation of well-known single-agent heuristic functions to compute global MAP estimators. The authors of @Stolba14 adapt the single-agent heuristic $h_{FF}$ @Hoffmann01 by means of a compact structure, the *exploration queue*, that optimizes the number of messages exchanged among agents. This multi-agent version of $h_{FF}$, however, is not as accurate as the single-agent one. The work in @Stolba15 introduces a global MAP version of the admissible heuristic function <span><span>*LM-Cut*</span></span>that is proven to obtain estimates of the same quality as the single-agent <span><span>*LM-Cut*</span></span>. This multi-agent <span><span>*LM-Cut*</span></span>yields better estimates at the cost of a larger computational cost.

In conclusion, heuristic search in MAP, and most notably, the development of global heuristic functions in a distributed context, constitutes one of the main challenges of the MAP research community. The aforementioned approaches prove the potential of the development and combination of global heuristics towards scaling up the performance of MAP solvers.

Privacy
-------

The preservation of agents' sensitive information, or *privacy*, is one of the basic aspects that must be enforced in MAP. The importance of privacy is illustrated in the task ${{\mathcal T}}_1$ of section \[characterization\], which includes two different agents, $ta1$ and $ta2$, both representing a transport agency. Although both agents are meant to cooperate for solving this task, it is unlikely that they are willing to reveal sensitive information to a potential competitor.

Privacy in MAP has been mostly neglected and under-represented in the literature. Some paradigms like Hierarchical Task Network (HTN) planning apply an form of implicit privacy when an agent delegates subgoals to another agent, which solves them by concealing the resolution details from the requester agent. This makes HTN a very well-suited approach for practical applications like composition of web services @Sirin04. However, formal treatment of privacy is even more scarce. One of the first attempts to come up with a formal privacy model in MAP is found in @vanderKrogt07b, where authors quantify privacy in terms of the Shannon's information theory @Shannon48. More precisely, authors establish a notion of uncertainty with respect to plans and provide a measure of privacy loss in terms of the data uncovered by the agents along the planning process. Unfortunately, this measure is not general enough to capture details such as heuristic computation. Nevertheless, quantification of privacy is an important issue in MAP, as it is in distributed constraint satisfaction problems @Faltings08. A more recent work, also based on Shannon's information theory @Stolba16b, quantifies privacy leakage for <span><span>MA-STRIPS</span></span>according to the reduction of the number of possible transition systems caused by the revealed information. In this work, the main sources of privacy leakage are identified, but not experimentally evaluated.

\[tab:privacy\]

The next subsections analyze the privacy models adopted by the MAP solvers in the literature according to three different criteria (see summary in Table \[tab:privacy\]): the *modelling* of private information, the *information sharing* schemes, and the privacy *practical privacy guarantees* offered by the MAP solver.

### Modelling of Private Information

This feature is closely related to whether the language used to specify the MAP task enables explicit modelling of privacy or not.

Early approaches to MAP, such as <span><span>MA-STRIPS</span></span>@Brafman08, manage a notion of *induced privacy*. Since the <span>*MA-STRIPS*</span>language does not explicitly model private information, the agents' private data are inferred from the task structure. Given an agent $i \in {{\mathcal{AG}}}$ and a piece of information $p^i \in {{\mathcal T}}^i$, $p^i$ is defined as private if $\forall_{j \in {{\mathcal{AG}}}| j \neq i} p^i \not \in {{\mathcal T}}^j$; that is, if $p^i$ is known to $i$ and ignored by the rest of agents in ${{\mathcal T}}$.

<span><span>FMAP</span></span>@Torreno14 introduces a more general *imposed privacy* scheme, explicitly describing the private and shareable information in the task description. <span>*MA-PDDL*</span> @Kovacs12, the language used in the <span><span>CoDMAP</span></span>competition @Komenda16codmap, follows this imposed privacy scheme and allows the designer to model the private elements of the agents' tasks.

In general, both induced and imposed privacy schemes are commonly applied by current MAP solvers. The induced privacy scheme enables the solver to automatically identify the naturally private elements of a MAP task. The imposed privacy scheme, by contrast, offers a higher control and flexibility to model privacy, which is a helpful tool in contexts where agents wish to occlude sensitive data that would be shared otherwise.

### Information Sharing

Privacy-preserving algorithms vary accordingly to the number of agents that share a particular piece of information. In general, we can identify two information sharing models, namely <span><span>MA-STRIPS</span></span>and *subset privacy*.

#### <span><span>MA-STRIPS</span></span>

The <span><span>MA-STRIPS</span></span>information sharing model @Brafman08 defines as public the data that are shared among all the agents in ${{\mathcal{AG}}}$, so that a piece of information is either known to all the participants, or only to a single agent. More precisely, a proposition $p \in {{\mathcal P}}$ is defined as *internal* or *private* to an agent $i \in {{\mathcal{AG}}}$ if $p$ is only used and affected by the actions of ${{\mathcal A}}^i$. However, if the proposition $p$ is also in the preconditions and/or effects of some action $\alpha \in {{\mathcal A}}^j$, where $j \in {{\mathcal{AG}}}$ and $j\neq i$, then $p$ is publicly accessible to all the agents in ${{\mathcal{AG}}}$.

An action $\alpha \in {{\mathcal A}}^i$ that contains only public preconditions and effects is said to be public and it is known to all the participants in the task. In case $\alpha$ includes both public and private preconditions and effects, agents share instead $\alpha_p$, the *public projection* of $\alpha$, an abstraction that contains only the public elements of $\alpha$.

This simple dichotomic privacy model of <span><span>MA-STRIPS</span></span>does not allow for specifying MAP tasks that require some information to be shared only by a subset of the planning agents in ${{\mathcal{AG}}}$.

#### Subset privacy

Subset privacy is introduced in @Bonisoli14 and generalizes the <span><span>MA-STRIPS</span></span>scheme by establishing pairwise privacy. This model defines a piece of information as private to a single agent, publicly accessible to all the agents in ${{\mathcal{AG}}}$ or known to a *subset of agents*. This approach is useful in applications where agents wish to conceal some information from certain agents.

For instance, agent $ta2$ in task ${{\mathcal T}}_1$ of section \[characterization\] notifies the factory agent $ft$ whenever the proposition $(pos\;t2\;ft)$ is reached. This proposition indicates that the truck $t2$ is placed at the factory $ft$, a location that is known to both $ta2$ and $ft$. Under the <span><span>MA-STRIPS</span></span>model, agent $ta1$ would be notified that truck $t2$ is at the factory $ft$, an information that $ta2$ may want to conceal. However, the subset privacy model allows $ta2$ to hide $(pos\;t2\;ft)$ from $ta1$ by defining it as private between $ta2$ and $ft$.

Hence, subset privacy is a more flexible information sharing model compared to the more conservative and limited approach of <span><span>MA-STRIPS</span></span>, which enables representing more complex and realistic situations concerning information sharing.

### Privacy Practical Guarantees {#practical_privacy}

Recent studies devoted to a formal treatment of practical privacy guidelines in MAP @Nissim14 [@Shani16] conclude that some privacy schemes allow agents to infer private information from other agents through the transmitted data. According to these studies, it is possible to establish a four-level taxonomy to classify the practical privacy level of MAP solvers. The four levels of the taxonomy, from the least to the most secure one, are: *no privacy*, *weak privacy*, *object cardinality privacy* and *strong privacy*.

#### No privacy

Privacy has been mostly neglected in MAP but has been extensively treated within the MAS community @Such12. The 2015 <span><span>CoDMAP</span></span>competition introduced a more expressive definition of privacy than <span><span>MA-STRIPS</span></span>and this was a boost for many planners to model private data in the task descriptions. Nevertheless, we can cite a large number of planners that completely disregard the issue of privacy among agents such as early approaches like <span><span>GPGP</span></span>@Decker92 or more recent approaches like <span><span>$\mu$-SATPLAN</span></span>@Dimopoulos12, <span><span>A\#</span></span> @Jezequel12 or <span><span>DPGM</span></span>@Pellier10.

#### Weak privacy

A MAP system is weakly privacy-preserving if agents do not explicitly communicate their private information to other agents at execution time @Brafman15. This is accomplished by either *obfuscating* (encrypting) or *occluding* the private information they communicate to other agents in order to only reveal the public projection of their actions. In a weak privacy setting, agents may infer private data of other agents through the information exchanged during the plan synthesis.

*Obfuscating* the private elements of a MAP task is an appropriate mechanism when agents wish to conceal the meaning of propositions and actions. In obfuscation, the proposition names are encrypted but the number and unique identity of preconditions and effects of actions are retained, so agents are able to reconstruct the complete isomorphic image of their tasks. In <span><span>MAPR</span></span>@Borrajo13, <span><span>PMR</span></span>@Luis14 and <span><span>CMAP</span></span>@mapr-cmap-codmap15, when an agent communicates a plan, it encrypts the private information in order to preserve its sensitive information. Agents in <span><span>MAFS</span></span>@Nissim14, <span><span>MADLA</span></span>@madla-codmap15, <span><span>MAPlan</span></span>@maplan-codmap15 and <span><span>GPPP</span></span>@Maliah14 encrypt the private data of the relevant states that they exchange during the plan synthesis.

Other weak privacy-preserving solvers in the literature *occlude* the agents' private information rather than sharing obfuscated data. Agents in <span><span>MH-FMAP</span></span>@Torreno15 only exchange the public projection of the actions of their partial-order plans, thus occluding private information like preconditions, effects, links or orderings.

#### Object cardinality privacy

Recently, the <span><span>DPP</span></span>planner @Shani16 introduced a new level of privacy named object cardinality privacy. A MAP algorithm preserves object cardinality privacy if, given an agent $i$ and a type $t$, the cardinality of $i$'s private objects of type $t$ cannot be inferred by other agents from the information they receive @Shani16. In other words, this level of privacy strongly preserves the number of objects of a given type $t$ of an agent $i$, thus representing a middle ground between the weak and strong privacy settings.

Hiding the cardinality of private objects is motivated by real-world scenarios. Consider, for example, the logistics task ${{\mathcal T}}_1$ of section \[characterization\]. One can assume that the transport agencies that take part in the MAP task, $ta1$ and $ta2$, know that packages are delivered using trucks. However, it is likely that each agent would like to hide the number of trucks it possesses or the number of transport routes it uses.

#### Strong privacy

A MAP algorithm is said to strongly preserve privacy if none of the agents in ${{\mathcal{AG}}}$ is able to infer a private element of an agent's task from the public information it obtains during planning. In order to guarantee strong privacy, it is necessary to consider several factors, such as the nature of the communication channel (synchronous, asynchronous, lossy) or the computational power of the agents.

<span><span>Secure-MAFS</span></span>@Brafman15 is a theoretical proposal to strong privacy that builds upon the <span><span>MAFS</span></span>@Nissim14 model. In <span><span>Secure-MAFS</span></span>, two states that only differ in their private elements are not communicated to other agents in order to prevent them from deducing information through the non-private or public part of the states. <span><span>Secure-MAFS</span></span>is proved to guarantee strong privacy for a sub-class of tasks based on the well-known *logistics* domain.

In summary, weak privacy is easily achievable through obfuscation of private data, but provides little security. On the other hand, the proposal of <span><span>Secure-MAFS</span></span>lays the theoretical foundations to strong privacy in MAP but the complexity analysis and the practical implementation issues of this approach have not been studied yet. Additionally, object cardinality privacy accounts for a middle ground between weak and strong privacy. In general, the vast majority of MAP methods are classified under the no privacy or weak privacy levels: the former approaches to MAP do not consider privacy at all, while most of the recent proposals, which claim to be privacy preserving, resort in most cases to *obfuscation* to conceal private information.

\[tab:features\]

Distributed and Multi-Agent Planning Systems Taxonomy {#taxonomy}
=====================================================

As discussed in section \[introduction\], MAP is a long-running research field that has been covered in several articles @Desjardins99a [@deWeerdt09; @MeneguzziS15]. This section reviews the large number of domain-independent cooperative MAP solvers that have been proposed since the introduction of the <span><span>MA-STRIPS</span></span>model @Brafman08. This large body of research was recently crystallized in the 2015 <span><span>CoDMAP</span></span>competition @Komenda16codmap, the first attempt to directly compare MAP solvers through a benchmark encoded using the standardized <span>*MA-PDDL*</span>language.

The cooperative solvers analyzed in this section cover a wide range of different plan synthesis schemes. As discussed in section \[aspects\], one can identify several aspects that determine the features of MAP solvers; namely, *agent distribution*, *computational process*, *plan synthesis scheme*, *communication mechanism*, *heuristic search* and *privacy preservation*. This section presents an in-depth taxonomy that classifies solvers according to their main features and analyzes their similarities and differences (see Table \[tab:features\]).

This section also aims to critically analyze and compare the strengths and weaknesses of the planners regarding their applicability and experimental performance. Given that a comprehensive comparison of MAP solvers was issued as a result of the 2015 <span><span>CoDMAP</span></span>competition, Table \[tab:features\] arranges solvers according to their positions in the coverage ranking (number of problems solved) of this competition. The approaches included in this taxonomy are organized according to their plan synthesis scheme, an aspect that ultimately determines the types of MAP tasks they can solve. Section \[taxonomy\_unthreaded\] discusses the planners that follow an unthreaded planning and coordination scheme, while section \[taxonomy\_interleaved\] reviews interleaved approaches to MAP.

Unthreaded Planning and Coordination MAP Solvers {#taxonomy_unthreaded}
------------------------------------------------

The main characteristic of unthreaded planners is that planning and coordination are not intertwined but handled as two separate and independent activities. Unthreaded solvers are labelled as *UT* in the column *Coordination strategy* of Table \[tab:features\]. They typically apply local single-agent planning and a combinatorial optimization or satisfiability algorithm to coordinate the local plans.

### <span><span>Planning First</span></span>, 2008 (implemented in 2010) {#planning-first-2008-implemented-in-2010 .unnumbered}

<span><span>Planning First</span></span> @Nissim10 is the first MAP solver that builds upon the <span><span>MA-STRIPS</span></span>model. It is an early representative of the unthreaded strategy that inspired the development of many subsequent MAP solvers, which are presented in the next paragraphs. <span><span>Planning First</span></span>generates a local plan for each agent in a centralized fashion by means of the <span><span>FF</span></span>planner @Hoffmann01, and coordinates the local plans through a distributed Constraint Satisfaction Problem (DisCSP) solver to come up with a global solution plan. More precisely, <span><span>Planning First</span></span>distributes the MAP task among the agents and identifies the coordination points of the task as the actions whose application affects other agents. The DisCSP is then used to find consistent coordination points between the local plans. If the DisCSP solver finds a solution, the plan for the MAP task is directly built from the local plans since the DisCSP solution guarantees compatibility among the underlying local plans.

The authors of @Nissim10 empirically evaluate <span><span>Planning First</span></span>over a set of tasks based on the well-known *rovers*, *satellite* and *logistics* domains. The results show that a large number of coordination points among agents derived from the number of public actions limits the scalability and effectiveness of <span><span>Planning First</span></span>. Later, the <span><span>MAP-POP</span></span>solver outperformed <span><span>Planning First</span></span>in both execution time and coverage @Torreno12ECAI.

### <span><span>DPGM</span></span>, 2010 (implemented in 2013) {#dpgm-2010-implemented-in-2013 .unnumbered}

<span><span>DPGM</span></span>@Pellier10 makes also use of CSP techniques to coordinate the agents' local plans. Unlike <span><span>Planning First</span></span>, the CSP solver in <span><span>DPGM</span></span>is explicitly distributed across agents and it is used to extract the local plans from a set of distributed planning graphs. Under the *iterative response planning* strategy introduced by <span><span>DPGM</span></span>, the solving process is started by one agent, which proposes a local plan along with a set of coordination constraints. The subsequent agent uses its CSP to extract a local plan compatible with the prior agent's plan and constraints. If an agent is not able to generate a compliant plan, <span><span>DPGM</span></span>backtracks to the previous agent, which puts forward an alternative plan with different coordination constraints.

### <span><span>$\mu$-SATPLAN</span></span>, 2010 {#mu-satplan-2010 .unnumbered}

<span><span>$\mu$-SATPLAN</span></span>@Dimopoulos12 is a MAP solver that extends the satisfiability-based planner <span><span>SATPLAN</span></span>@Kautz06 to a multi-agent context. <span><span>$\mu$-SATPLAN</span></span>performs an *a priori* distribution of the MAP task goals, ${{\mathcal G}}$, among the agents in ${{\mathcal{AG}}}$. Similarly to <span><span>DPGM</span></span>, agents follow an iterative response planning strategy, where each participant takes the previous agent's solution as an input and extends it to solve its assigned goals via <span><span>SATPLAN</span></span>. This way, agents progressively generate a solution.

<span><span>$\mu$-SATPLAN</span></span>is unable to attain tasks that include <span>group goals</span>because it assumes that each agent can solve its assigned goals by itself. <span><span>$\mu$-SATPLAN</span></span>is experimentally validated on several multi-agent tasks of the *logistics*, *storage* and *TPP* domains. Although these tasks feature only two planning agents, the authors claim that <span><span>$\mu$-SATPLAN</span></span>is capable of solving tasks with a higher number agents.

### <span><span>MAPR</span></span>, <span><span>PMR</span></span>, <span><span>CMAP</span></span>, 2013-2015 {#mapr-pmr-cmap-2013-2015 .unnumbered}

Multi-Agent Planning by Reuse (<span><span>MAPR</span></span>) @Borrajo13 allocates the goals ${{\mathcal G}}$ of the task among the agents before planning through a relaxed reachability analysis. The private information of the local plans is encrypted, thus preserving weak privacy by obfuscating the agents' local tasks. <span><span>MAPR</span></span>also follows an iterative response plan synthesis scheme, wherein an agent takes as input the result of the prior agent's solution plan and runs the <span><span>LAMA</span></span>planner @Richter10 to obtain an extended solution plan that attains its allocated agent's goals. The plan of the last agent is a solution plan for the MAP task, which is parallelized to ensure that execution agents perform as many actions in parallel as possible. <span><span>MAPR</span></span>is limited to tasks that do not feature specialized agents or <span>group goals</span>. This limitation is a consequence of the assumption that each agent is able to solve its allocated goals by itself, which renders <span><span>MAPR</span></span>incomplete.

Plan Merging by Reuse (<span><span>PMR</span></span>) @Luis14 [@pmr-codmap15] draws upon the goal allocation and obfuscation privacy mechanisms of <span><span>MAPR</span></span>. Unlike <span><span>MAPR</span></span>, agents carry out the planning stage simultaneously instead of sequentially and each agent generates local plans for its assigned goals. In the post-planning plan merging strategy of <span><span>PMR</span></span>, the resulting local plans are concatenated, yielding a sequential global solution. If the result of the merging process is not a valid solution plan, local plans are merged through a repair procedure. If a merged solution is not found, the task is solved via a single-agent planner.

Although <span><span>CMAP</span></span>@mapr-cmap-codmap15 follows the same goal allocation and obfuscation strategy of <span><span>MAPR</span></span>and <span><span>PMR</span></span>, the plan synthesis scheme of <span><span>CMAP</span></span>transforms the encrypted local tasks into a single-agent task ($|{{\mathcal{AG}}}| = 1$), which is then solved through the planner <span><span>LAMA</span></span>. <span><span>CMAP</span></span>was the best-performing approach of this family of MAP planners in the 2015 <span><span>CoDMAP</span></span>competition as shown in Table \[tab:features\]. <span><span>CMAP</span></span>ranked 7th in the centralized track and exhibited a solid performance over the 12 domains of the <span><span>CoDMAP</span></span>benchmark (approximately 90% coverage). <span><span>PMR</span></span>and <span><span>MAPR</span></span>ranked 14th and 15th, with roughly 60% coverage. The plan synthesis scheme of <span><span>MAPR</span></span>affects its performance in domains that feature <span>group goals</span>, such as *depots* or *woodworking*, while <span><span>PMR</span></span>offers a more stable performance over the benchmark.

### <span><span>MAP-LAPKT</span></span>, 2015 {#map-lapkt-2015 .unnumbered}

<span><span>MAP-LAPKT</span></span>@map-lapkt-codmap15 conceives a MAP task as a problem that can be transformed and solved by a single-agent planner using the appropriate encoding. More precisely, <span><span>MAP-LAPKT</span></span>compiles the MAP task into a task that features one planning agent ($|{{\mathcal{AG}}}|=1$) and solves with the tools provided in the repository <span><span>LAPKT</span></span>@lapkt. The authors of @map-lapkt-codmap15 try three different variations of best-first and depth-first search that result in algorithms with different theoretical properties and performance. The task translation performed by <span><span>MAP-LAPKT</span></span>offers weak privacy preservation guarantees.

As shown in Table \[tab:features\], two of the three versions of <span><span>MAP-LAPKT</span></span>that participated in the <span><span>CoDMAP</span></span>ranked 2nd and 3rd in the centralized track. The coverage of <span><span>MAP-LAPKT</span></span>and of <span><span>CMAP</span></span>is roughly to 90% of the benchmark problems, an indication that shows the efficiency of the scheme that compiles a MAP task into a single-agent task.

### <span><span>MARC</span></span>, 2015 {#marc-2015 .unnumbered}

The Multi-Agent Planner for Required Cooperation (<span><span>MARC</span></span>) @marc-codmap15 is a centralized MAP solver based on the theory of required cooperation @Zhang14. <span><span>MARC</span></span>analyzes the agent distribution of the MAP task and comes up with a different arrangement of planning agents. Particularly, <span><span>MARC</span></span>compiles the original task into a task with a set of *transformer agents*, each one being an ensemble of various agents; i.e., $|{{\mathcal{AG}}}_{MARC}| < |{{\mathcal{AG}}}|$. A transformer agent comprises the representation of various agents of the original MAP task including all their actions. The current implementation of <span><span>MARC</span></span>compiles all the agents in ${{\mathcal{AG}}}$ into a single transformer agent ($|{{\mathcal{AG}}}_{MARC}| = 1$). Then, a solution plan is computed via <span><span>FD</span></span>@Helmert06 or the portfolio planner <span><span>IBACOP</span></span>@Cenamor14, and the resulting plan is subsequently translated into a solution for the original MAP task. <span><span>MARC</span></span>preserves weak privacy since private elements of the MAP task are occluded in the transformer agent task.

Regarding experimental performance, <span><span>MARC</span></span>ranks at the 4th position of the centralized <span><span>CoDMAP</span></span>with 90% coverage, thus being one of the best-performing MAP approaches. The experimental results also reveal the efficiency of this multi-to-one agent transformation.

### <span><span>ADP</span></span>, 2013 {#adp-2013 .unnumbered}

The Agent Decomposition-based Planner (<span><span>ADP</span></span>) @Crosby13 is a factored planning solver that exploits the inherently multi-agent structure (agentization) of some <span><span>STRIPS</span></span>-style planning tasks and comes up with a MAP task where $|{{\mathcal{AG}}}| > 1$. <span><span>ADP</span></span>applies a state-based centralized planning procedure to solve the MAP task. In each iteration, <span><span>ADP</span></span>determines a set of subgoals that are achievable from the current state by one of the agents. A search process, guided through the well-known $h_{FF}$ heuristic, is then applied to find a plan that achieves these subgoals, thus resulting in a new state. This mechanism iterates successively until a solution is found.

Experimentally, <span><span>ADP</span></span>outperforms several state-of-the-art classical planners (e.g., <span><span>LAMA</span></span>) and is the top-ranked solver at the centralized track of the <span><span>CoDMAP</span></span>, outperforming other approaches that compile the MAP task into a single-agent planning task, such as <span><span>MAP-LAPKT</span></span>or <span><span>CMAP</span></span>.

### <span><span>Distoplan</span></span>, 2010 {#distoplan-2010 .unnumbered}

<span><span>Distoplan</span></span>@Fabre10 is a factored planning approach that exploits independence within a planning task. Unlike other factored methods @Kelareva07, <span><span>Distoplan</span></span>does not set any bound on the number of actions or coordination points of local plans. In <span><span>Distoplan</span></span>, a component or abstraction of the global task is represented as a finite automaton, which recognizes the regular language formed by the local valid plan of the component. This way, all local plans are manipulated at once and a generic distributed optimization technique enables to limit the number of compatible local plans. With this unbounded representation, all valid plans can be computed in one run but stronger conditions are required to guarantee polynomial runtime. <span><span>Distoplan</span></span>is the first optimal MAP solver in the literature (note that <span><span>Planning First</span></span>is optimal with respect to the number of coordination points, but local planning is carried out through a suboptimal planner).

<span><span>Distoplan</span></span>was experimentally tested in a factored version of the *pipesworld* domain. However, the solver is unable to solve even the smallest instances of this domain in a reasonable time. The authors claim that the reason is that <span><span>Distoplan</span></span>scales roughly as $n^3$, where $n$ is the number of components of the global task. For obvious reasons, <span><span>Distoplan</span></span>has not been empirically compared against other MAP solvers in the literature.

### <span><span>A\#</span></span>, 2012 (not implemented) {#a-2012-not-implemented .unnumbered}

In the line of factored planning, <span><span>A\#</span></span>@Jezequel12 is a multi-agent A\* search that finds a path for the goal in each local component of a task and ensures that the component actions that must be jointly performed are compatible. <span><span>A\#</span></span>runs in parallel a modified version of the A\* algorithm in each component, and the local search processes are guided towards finding local plans that are compatible with each other. Each local A\* finds a plan as a path search in a graph and informs its neighbors of the common actions that may lead to a solution. Particularly, each agent searches its local graph or component while considering the constraints and costs of the rest of agents, received through an asynchronous communication mechanism. The authors of @Jezequel12 do not validate <span><span>A\#</span></span>experimentally; however, the soundness, completeness and optimality properties of <span><span>A\#</span></span>are formally proven.

### <span><span>PSM</span></span>, 2014 {#psm-2014 .unnumbered}

<span><span>PSM</span></span>@Tozicka15 [@psm-codmap15] is a recent distributed MAP solver that follows <span><span>Distoplan</span></span>'s compact representation of local agents plans into Finite Automata, called Planning State Machines (PSMs). This planner defines two basic operations: obtaining a public projection of a PSM and merging two different PSMs. These operations are applied to build a public PSM consisting of merged public parts of individual PSMs. The plan synthesis scheme gradually expands the agents' local PSMs by means of new local plans. A solution for the MAP task is found once the public PSM is not empty. <span><span>PSM</span></span>weakly preserves privacy as it obfuscates states of the PSMs in some situations. <span><span>PSM</span></span>applies an efficient handling of communication among agents, which grants this solver a remarkable experimental performance in both the centralized and distributed setting. In the centralized <span><span>CoDMAP</span></span>track, <span><span>PSM</span></span>ranks 12th (solving 70% of the tasks), and it is the top performer at the distributed track of the competition.

### <span><span>DPP</span></span>, 2016 {#dpp-2016 .unnumbered}

The DP-Projection Planner (<span><span>DPP</span></span>) @Shani16, is a centralized <span><span>MA-STRIPS</span></span>solver that uses the Dependency-Preserving (DP) projection, a novel and accurate public projection of the MAP task information with object cardinality privacy guarantees. The single planning agent of <span><span>DPP</span></span>uses the <span><span>FD</span></span>planner to synthesize a high-level plan which is then extended with the agents' private actions via the <span><span>FF</span></span>planner, thus resulting in a multi-agent solution plan.

The authors of @Shani16 provide a comprehensive experimental evaluation of <span><span>DPP</span></span>through the complete benchmark of the 2015 <span><span>CoDMAP</span></span>competition. The results show that <span><span>DPP</span></span>outperforms most of the top contenders of the competition (namely, <span><span>GPPP</span></span>, <span><span>MAPR</span></span>, <span><span>PMR</span></span>, <span><span>MAPlan</span></span>and <span><span>PSM</span></span>). All in all, <span><span>DPP</span></span>can be considered the current top <span><span>MA-STRIPS</span></span>-based solver, as well as one of the best-performing MAP approaches to date.

### <span><span>TFPOP</span></span>, 2011 {#tfpop-2011 .unnumbered}

<span><span>TFPOP</span></span>@Kvarnstrom11 is a hybrid approach that combines the flexibility of partial-order planning and the performance of forward-chaining search. Unlike most <span><span>MA-STRIPS</span></span>-based solvers, <span><span>TFPOP</span></span>supports temporal reasoning with durative actions. <span><span>TFPOP</span></span>is a centralized approach that synthesizes a solution for multiple executors. It computes *threaded partial-order plans*; i.e., non-linear plans that keep a thread of sequentially-ordered actions per agent, since authors assume that an execution agent performs its actions sequentially.

<span><span>TFPOP</span></span>is tested in a reduced set of domains, which include the well-known *satellite* and *zenotravel* domains, as well as a UAV delivery domain. The objective of this experimentation is to compare <span><span>TFPOP</span></span>against several partial-order planners. <span><span>TFPOP</span></span>is not compared to any MAP solver in this taxonomy.

Interleaved Planning and Coordination MAP Solvers {#taxonomy_interleaved}
-------------------------------------------------

Under the interleaved scheme, labelled as *IL* in the column *Coordination strategy* of Table \[tab:features\], agents jointly explore the search space intertwining their planning and coordination activities. The development of interleaved MAP solvers heavily relies on the design of robust communication protocols to coordinate agents during planning.

### <span><span>MAP-POP</span></span>, <span><span>FMAP</span></span>, <span><span>MH-FMAP</span></span>, 2010-2015 {#map-pop-fmap-mh-fmap-2010-2015 .unnumbered}

In this family of MAP solvers, agents apply a distributed exploration of the plan space. Agents locally compute plans through an embedded partial-order planning (POP) component and they build a joint search tree by following an A\* search scheme guided by global heuristic functions.

<span><span>MAP-POP</span></span>@Torreno12ECAI [@Torreno12KAIS] performs an incomplete search based on a classical backward POP algorithm and POP heuristics. <span><span>FMAP</span></span>@Torreno14 introduces a sound and complete plan synthesis scheme that uses a forward-chaining POP @Benton12 guided through the $h_{DTG}$ heuristic. <span><span>MH-FMAP</span></span>@fmap-codmap15 applies a multi-heuristic search approach that alternates $h_{DTG}$ and $h_{Land}$, building a Landmark Graph (LG) to estimate the number of pending landmarks of the partial-order plans. The three planners guarantee weak privacy since private information is occluded throughout the planning process and heuristic evaluation. The $h_{Land}$ estimator uses some form of obfuscation during the construction of the LG.

Regarding experimental results, <span><span>FMAP</span></span>is proven to outperform <span><span>MAP-POP</span></span>and <span><span>MAPR</span></span>in terms of coverage over 10 MAP domains, most of which are included in the <span><span>CoDMAP</span></span>benchmark. Results in @Torreno15 indicate that <span><span>MH-FMAP</span></span>obtains better coverage than both <span><span>FMAP</span></span>and <span><span>GPPP</span></span>. Interestingly, this planner exhibits a much worse performance in the <span><span>CoDMAP</span></span>(see Table \[tab:features\]), ranking 17th with only 42% coverage. This is due to the lose of accuracy of the $h_{DTG}$ heuristic when the internal state-variable representation of the tasks in <span><span>MH-FMAP</span></span>is transformed to a propositional representation to be tested in the <span><span>CoDMAP</span></span>benchmark, thus compromising the performance of the solver @fmap-codmap15.

### <span><span>MADLA</span></span>, 2013 {#madla-2013 .unnumbered}

The Multiagent Distributed and Local Asynchronous Planner (<span><span>MADLA</span></span>) @Stolba15 is a centralized solver that runs one thread per agent on a single machine and combines two versions of the $h_{FF}$ heuristic, a projected (local) variant ($h_L$) and a distributed (global) variant ($h_D$) in a multi-heuristic state-space search. The main novelty of <span><span>MADLA</span></span>is that the agent which is computing $h_D$, which requires contributions of the other agents for calculating the global heuristic estimator, is run asynchronously and so it can continue the search using $h_L$ while waiting for responses from other agents that are computing parts of $h_D$. <span><span>MADLA</span></span>evaluates as many states as possible using the global heuristic $h_D$, which is more informative than $h_L$. This way, <span><span>MADLA</span></span>can use a computationally hard global heuristic without blocking the local planning process of the agents, thus improving the performance of the system.

Experimentally, <span><span>MADLA</span></span>ranks 13th in the centralized <span><span>CoDMAP</span></span>, reporting 66% coverage. It outperforms most of the distributed MAP solvers of the competition, but it is not able to solve the most complex tasks of the <span><span>CoDMAP</span></span>domains, thus not reaching the figures of the top performers such as <span><span>ADP</span></span>, <span><span>MAP-LAPKT</span></span>or <span><span>MARC</span></span>.

### <span><span>MAFS</span></span>, <span><span>MAD-A\*</span></span>, 2012-2014 {#mafs-mad-a-2012-2014 .unnumbered}

<span><span>MAFS</span></span>@Nissim14 is an updated version of <span><span>Planning First</span></span>that implements a distributed algorithm wherein agents apply a heuristic state-based search (see section \[heuristic\]). In @Nissim12, authors present <span><span>MAD-A\*</span></span>, a cost-optimal variation of <span><span>MAFS</span></span>. In this case, each agent expands the state that minimizes $f=g+h$, where $h$ is estimated through an admissible heuristic. Particularly, authors tested the landmark heuristic *LM-Cut* @Helmert09 and the abstraction heuristic *Merge&Shrink* @Helmert07. <span><span>MAD-A\*</span></span>is the first distributed and interleaved solver based on <span><span>MA-STRIPS</span></span>.

<span><span>MAFS</span></span>is compared against <span><span>MAP-POP</span></span>and <span><span>Planning First</span></span>over the *logistics*, *rovers* and *satellite* domains, notably outperforming both solvers in terms of coverage and execution time @Nissim14. On the other hand, the authors of @Nissim14 only compare <span><span>MAD-A\*</span></span>against single-agent optimal solvers.

### <span><span>Secure-MAFS</span></span>, 2015 (not implemented) {#secure-mafs-2015-not-implemented .unnumbered}

<span><span>Secure-MAFS</span></span>@Brafman15 is an extension of <span><span>MAFS</span></span>towards secure MAP, and it is currently the only solver that offers *strong privacy* guarantees (see section \[practical\_privacy\]). Currently, <span><span>Secure-MAFS</span></span>is a theoretical work that has not been yet implemented nor experimentally evaluated.

### <span><span>GPPP</span></span>, 2014 {#gppp-2014 .unnumbered}

The Greedy Privacy-Preserving Planner (<span><span>GPPP</span></span>) @Maliah14 [@Maliah16] builds upon <span><span>MAFS</span></span>and improves its performance via a global landmark-based heuristic function. <span><span>GPPP</span></span>applies a *global planning* stage and then a *local planning* stage. In the former, agents agree on a joint coordination scheme by solving a relaxed MAP task that only contains public actions (thereby preserving privacy) and obtaining a skeleton plan. In the *local planning* stage, agents compute private plans to achieve the preconditions of the actions in the skeleton plan. Since coordination is done over a relaxed MAP task, the individual plans of the agents may not succeed at solving the actions' preconditions. In this case, the global planning stage is executed again to generate a different coordination scheme, until a solution is found. In <span><span>GPPP</span></span>, agents weakly preserve privacy by obfuscating the private information of the shared states through private state identifiers.

<span><span>GPPP</span></span>provides a notable experimental performance, ranking 10th in the centralized <span><span>CoDMAP</span></span>track. <span><span>GPPP</span></span>reaches 83% coverage and is only surpassed by the different versions of <span><span>ADP</span></span>, <span><span>MARC</span></span>, <span><span>MAP-LAPKT</span></span>, <span><span>CMAP</span></span>and <span><span>MAPlan</span></span>, which proves the accuracy of its landmark based heuristic and the overall efficiency of its plan synthesis scheme.

### <span><span>MAPlan</span></span>, 2015 {#maplan-2015 .unnumbered}

<span><span>MAPlan</span></span>@maplan-codmap15 is a heuristic <span><span>MAFS</span></span>-based solver that adapts several concepts from <span><span>MAD-A\*</span></span>and <span><span>MADLA</span></span>. <span><span>MAPlan</span></span>is a distributed and flexible approach that implements a collection of state-space search methods, such as best first or A<span>\*</span>, as well as several local and global heuristic functions ($h_{FF}$, *LM-Cut*, potential heuristics and others), which allows the solver to be run under different configurations. <span><span>MAPlan</span></span>can be executed in a single-machine, using local communication, or in a distributed fashion, where each agent is in a different machine and communication among agents is implemented through network message passing. Regarding privacy, <span><span>MAPlan</span></span>applies a form of obfuscation, replacing private facts in search states by unique local identifiers, which grants weak privacy.

<span><span>MAPlan</span></span>exhibits a very solid performance in the centralized and distributed tracks of the 2015 <span><span>CoDMAP</span></span>competition, ranking 9th and 2nd, respectively. In the centralized track, <span><span>MAPlan</span></span>obtains 83% coverage, outperforming <span><span>GPPP</span></span>and reaching similar figures than the top-performing centralized solvers.

Conclusions {#ongoing}
===========

The purpose of this article is to comprehensively survey the state of the art in cooperative MAP, offering an in-detail overview of this rapidly evolving research field, which has experienced multiple key advances over the last decade. These contributions crystallized in the 2015 <span><span>CoDMAP</span></span>competition, where MAP solvers were compared through an exhaustive benchmark testing encoded with <span>*MA-PDDL*</span>, the first standard modelling language for MAP tasks.

In this paper, the topic of MAP was studied from a twofold perspective: from the representational structure of a MAP task and from the problem-solving standpoint. We formally defined a MAP task following the well-known MA-STRIPS model and provided several examples which illustrate the features that distinguish MAP tasks from the more compact single-agent planning tasks. We also presented the modelling of these illustrative tasks with <span>*MA-PDDL*</span>.

MAP is a broad field that allows for a wide variety of problem-solving approaches. For this reason, we identified and thoroughly analyzed the main aspects that characterize a solver, from the architectural design to the practical features of a MAP tool. Among others, these aspects include the computational process of the solvers and the plan synthesis schemes that stem from the particular combination of planning and coordination applied by MAP tools, as well as other key features, such as the communication mechanisms used by the agents to interact with each other and the privacy guarantees offered by the existing solvers.

Finally, we compiled and classified the existing MAP techniques according to the aforementioned criteria. The taxonomy of MAP techniques presented in this survey prioritizes recent domain-independent techniques in the literature. Particularly, we focused on the approaches that took part in the 2015 <span><span>CoDMAP</span></span>competition, comparing their performance, strengths and weaknesses. The classification aims to provide the reader with a clear and comprehensive overview of the existing cooperative MAP solvers.

The body of work presented in this survey constitutes a solid foundation for the ongoing and future scientific development of the MAP field. Following, we summarize several research trends that have recently captured the attention of the community.

#### Theoretical properties

The aim of the earlier cooperative MAP solvers was to contribute with a satisficing approach capable of solving a relatively small number of problems in a reasonable time but without providing any formal properties @Nissim10 [@Borrajo13]. The current maturity of the cooperative MAP field has witnessed the introduction of some models that focus on granting specific theoretical properties, such as completeness @Torreno14, optimality @Nissim14 or stronger privacy preservation guarantees @Brafman15 [@Shani16].

#### Privacy {#privacy}

The state of the art in MAP shows a growing effort in analyzing and formalizing privacy in MAP solvers. Nowadays, various approaches to model private information and to define information sharing can be found in the literature, which reveals that privacy is progressively becoming a key topic in MAP. However, the particular implementation of a MAP solver may jeopardize privacy, if it is possible for an agent to infer private information from the received public data. Aside from the four-level classification exposed in section \[practical\_privacy\], other recent approaches attempt to theoretically quantify the privacy guarantees of a MAP solver @Stolba16b. In the same line, the authors of @Tozicka17 analyze the implications and limits of strong privacy and present a novel <span><span>PSM</span></span>-based planner that offers strong privacy guarantees.

On the other hand, one can also find work that proposes a smart use of privacy to increase the performance of MAP solvers, like <span><span>DPP</span></span>@Shani16, which calculates an accurate public projection of the MAP task in order to obtain a robust high-level plan that is then completed with private actions. This scheme minimizes the communication requirements, resulting in a more efficient search. In @Maliah17, authors introduce a novel weak privacy-preserving variant of <span><span>MAFS</span></span>which ensures that two agents that do not share any private variable never communicate with each other, significantly reducing the number of exchanged messages. In general, the study of privacy in MAP is gaining much attention and more and more sophisticated approaches have been recently proposed.

#### MAP with self-interesed agents

The mainstream in MAP with self-interested planning agents is handling situations which involve interactive decision making with possibly conflicting interests. Game theory, the study of mathematical models of conflict and cooperation between rational self-interested agents, arises naturally as a paradigm to address human conflict and cooperation within a competitive situation. Game-theoretic MAP is an active and interesting research field that reflects many real-world situations, and thus, it has a broad variety of applications, among which we can highlight congestion games @JonssonR11, cost-optimal planning @NissimB13, conflict resolution in the search of a joint plan @JordanO15 or auction systems @RobuNPS11.

From a practical perspective, game-theoretic MAP has been successfully applied to ridesharing problems on timetabled transport services @HrncirRJ15. In general, strategic approaches to MAP are very appropriate to model smart city applications like traffic congestion prevention: vehicles can be accurately modelled as rational self-interested agents that want to reach their destinations as soon as possible, but they are also willing to deviate from their optimal routes in order to avoid traffic congestion issues that would affect all the involved agents.

#### Practical applications

MAP is being used in a great variety of applications, like in product assembly problems in industry (e.g., car assembly). Agents plan the manufacturing path of the product through the assembly line, which is composed of a number of interconnected resources that can perform different operations. <span><span>ExPlanTech</span></span>, for instance, is a consolidated framework for agent-based production planning, manufacturing, simulation and supply chain management @Pechoucek07.

MAP has also been used to control the flow of electricity in the Smart Grid @Reddy11. The agents' actions are individually rational and contribute to desirable global goals such as promoting the use of renewable energy, encouraging energy efficiency and enabling distributed fault tolerance. Another interesting application of MAP is the automated creation of workflows in biological pathways like the Multi-Agent System for Genomic Annotation (<span><span>BioMAS</span></span>) @Decker02. This system uses <span><span>DECAF</span></span>, a toolkit that provides standard services to integrate agent capabilities, and incorporates the <span><span>GPGP</span></span>framework @Lesser04 to coordinate multi-agent tasks.

In decentralized control problems, MAP is applied in coordination of space rovers and helicopter flights, multi-access broadcast channels, and sensor network management, among others @Seuken08. MAP combined with argumentation techniques to handle belief changes about the context has been used in applications of ambient intelligence in the field of healthcare @Pajares13.

Aside from the aforementioned trends, there is still a broad variety of unexplored research topics in MAP. The solvers presented in this survey do not support tasks with advanced requirements. Particularly, handling temporal MAP tasks is an unresolved matter that should be addressed in the years to come. This problem will involve both the design of MAP solvers that explicitly support temporal reasoning and the extension of <span>*MA-PDDL*</span>to incorporate the appropriate syntax to model tasks with temporal constraints.

Cooperative MAP, as exposed in this paper, puts the focus on offline tasks, without paying much attention to the problematic of plan execution. Online planning carried out by several agents poses a series of challenges derived from the integration of planning and execution and the need to respond in complex, real-time environments. Real-time cooperative MAP is about planning and simultaneous execution by several cooperative agents in a changing environment. This interesting and exciting research line is very relevant in applications that involve, for example, soccer robots.

Additionally, the body of work presented in this survey does not consider agents with individual preferences. Preference-based MAP is an unstudied field that can be interpreted as a middle ground between cooperative and self-interested MAP, since it involves a set of rational agents that work together towards a common goal while having their own preferences concerning the properties of the solution plan.

All in all, we believe that the steps taken over the last years towards the standardization of MAP tasks and tools, such as the 2015 <span><span>CoDMAP</span></span>competition or the introduction of <span>*MA-PDDL*</span>, will decisively contribute to foster a rapid expansion of this field in a wide variety of research directions.

[^1]: http://icaps16.icaps-conference.org/dmap.html

[^2]: http://agents.fel.cvut.cz/codmap

[^3]: Please refer to <http://agents.fel.cvut.cz/codmap/MA-PDDL-BNF-20150221.pdf> for a complete BNF definition of the syntax of <span>*MA-PDDL*</span>.

[^4]: http://www.icaps-conference.org/index.php/Main/Competitions

{'source': 'arXiv_out/1711'}