Multi-Agent Temporal Task Solving and Plan Optimization

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 21:01:56

Abstract: Several multi-agent techniques are utilized to reduce the complexity of classical planning tasks, however, their applicability to temporal planning domains is a currently open line of study in the field of Automated Planning.

In this paper, we present MA-LAMA, a centralized, unthreated, satisfying, total-order, multi-agent temporal planner, that exploits the 'multi-agent nature' of temporal domains to, as its predecessor LAMA, perform plan optimization.

In MA-LAMA, temporal tasks are translated to the constrained snap-actions paradigm, and an automatic agent decomposition, goal assignment and required cooperation analysis are carried to build independent search steps, called Search Phases. These Search Phases are then solved by consecutive agent local searches, using classical heuristics and temporal constraints.

Experimentation shows that MA-LAMA is able to solve a wide range of classical and temporal multi-agent domains, performing significantly better in plan quality than other state-of-the-art temporal planners.

Main paper: 
 : 
 threated, satisfying, total-order, multi-agent temporal planner, that exploits the 'multi-agent nature' of temporal domains to, as its predecessor LAMA, perform plan optimization. In MA-LAMA, temporal tasks are translated to the constrained snap-actions paradigm, and an automatic agent de-Introduction 20In numerous scenarios the systems we plan for are naturally viewed as multi-agent (MA) systems, and, additionally, MA systems inherently tend to require some degree of concurrency between agents to operate efficiently. Some examples of temporal MA planning (MAP) scenarios that present 'MA nature' can be found in the International Planning Competition (IPC) benchmark domains, e.g. Rovers and Satellites, with independent homogeneous agents; and Elevators or Logistics, where interaction between agents is required.In contrast, Automated Planning literature has classically considered temporal and MAP as two individual lines of work. This can be viewed in the MAP Survey (Torreño et al. 2017) , where it is stated that the handling of scenarios derived from temporal MA systems is an open point that needs to be addressed, as MAP solvers tend to focus on classical planning domains.In that survey, they also present some classifications for MAP solvers in terms of their taxonomy: threaded, with interleaved planning and coordination, and unthreaded, dealing with planning and coordination separately. Their compu-40 tational structure: centralized, with a monolithic design and a central process, and distributed, sharing the planning task across multiple processing units. And their privacy preservation: providing strong, object cardinality or weak privacy, depending on the extent to which each agent's sensitive information is preserved. For plan quality optimization (one of the main points of interest of this work), MAP systems tend to make use of cost aware classical planners, like LAMA (Richter and Westphal 2010) .MAP techniques used across all types of MAP solvers are different from those used in temporal planners, which tend to revolve around time and numeric reasoning to deal with the inherent complexity of concurrent actions search spaces (Rintanen 2007) . Our objective with this paper is to test the MAP techniques' effectiveness in dealing with temporal complexity, especially in areas where time reasoningbased planners struggle, as not coupled with makespan plan quality optimization.MA-LAMA is the result of the integration of these techniques: a centralized, unthreaded, satisfying, total-order, temporal MAP system that can deal with MA temporal tasks. Our contribution is centered around the application of automated task decomposition, goal assignment, and required cooperation MAP techniques to temporal tasks. This results in a planning algorithm that exploits the MA and concurrent nature of temporal MA domains.The paper is structured as follows. The next section presents the related literature. Then MA-LAMA is presented, first broadly and after, in a detailed per-component view. Finally, we provide an empirical evaluation of the planner, followed by the conclusions and future work.Literature on both MAP and temporal planning is extensive as separate lines of work. To our knowledge, TFPOP (Brafman and Domshlak 2008) is the only MA planner that is able to deal both with time and durative-actions. It follows a centralized scheme, producing non-linear plans that maintain a thread of sequentially ordered actions per agent, exploiting the concept of coordination points for loosely coupled agents and through CSP+planning. However, it was not compared to any other MAP solver.Regarding MA planning, some examples of threaded MAP planners are partial-order-planning (POP) based planners, as MH-FMAP (Torreño, Sapena, and Onaindia 2015) , which computes distributed versions of h DT G and h Land heuristics; MAD-A * (Nissim and Brafman 2013) , an optimal solver based in local agent evaluation of each state; GPPP (Maliah, Shani, and Stern 2014) , which builds a relaxed public plan before each local planning stage; and MAPlan (Fišer, Štolba, and Komenda 2015) , which follows a flexible distributed implementation of local agent state search methods, as well as both local and global heuristics, as h F F and LM-Cut, showing strong performance specially with distributed computation agents.For unthreaded MAP planners, some approaches to this type are: PMR (Luis, Fernández, and Borrajo 2020) , based in plan merging and reuse with simultaneous planning by all agents; CMAP (Borrajo and Fernández 2015), with weak privacy preservation in agents assembly and single-agent search; Distoplan (Fabre et al. 2010) , an optimal planner that exploits independence between agents, not limiting their possible interactions beforehand; PSM (Tožička, Jakubuv, and Komenda 2015) , which expands Other MA techniques include symmetry score based task decomposition for classical (Nissim, Apsel, and Brafman 2012) and numeric planning (Shleyfman, Kuroiwa, and Beck 2023) .In our case, MA-LAMA deals with MAP solving with a traditional approach, considering sequential total-order planning. We also make use of several MAP techniques not yet mentioned, such as: task decomposition into local search regions (Lansky 1991) , exploiting loosely coupled agents from TFPOP, coordination points detection and constraints definition from Planning First (Nissim, Brafman, and Domshlak 2010) , distributed planning graphs with coordination constraints from DPGM (Pellier 2010) , required cooperation (Zhang, Sreedharan, and Kambhampati 2016) , also used in the MARC planner (Sreedharan, Zhang, and 125 Kambhampati 2015); satisfiability through sequential MAP task solving from µ-SATPLAN (Dimopoulos, Hashmi, and Moraitis 2012) , and automatic MAP agent decomposition from ADP (Crosby, Rovatsos, and Petrick 2013) .Several of these MAP planners, and others, participated in the 2015 Competition of Distributed and Multi-Agent Planning (CoDMAP) (Komenda, Štolba, and Kovács 2016) , being the top performers ADP in coverage and CMAP-q in quality for the centralized track, and PSM and MAPlan for the distributed track overall.Regarding temporal planning, several temporal planners incorporate techniques that MA-LAMA makes us of, such us the snap-actions paradigm, continuous numeric effects treatment and temporal frontier state constraints from POPF (Coles et al. 2021 ) and OPTIC (Benton, Coles, and Coles 2012) , both from the COLIN (Coles et al. 2012 ) family of planners; and TFLAP (Sapena, Marzal, and Onaindia 2018) multi-heuristic search based in h F F and h Land , which had good performance in the 2018 IPC temporal track.Other participants in this competition were POPCORN (Savas ¸et al. 2016) , which is able to operate with control parameters, TemPorAl (Cenamor et al. 2018 ), a portfolio that was the top performer in the competition, and CP4TP (Furelos-Blanco and Jonsson 2018), another portfolio. From 2014 IPC temporal track, notable participants were: IT-SAT (Feyzbakhsh Rankooh and Ghassem-Sani 2015), a SAT-Based Temporally Expressive Planner; YAHSP3 (Vidal 2014), which computes lookahead relaxed plans and uses them in state-space heuristic search; and Temporal FD (TFD) (Eyerich, Mattmüller, and Röger 2012) , that uses context-enhanced additive heuristic over a temporal search space.In contrast, MA-LAMA opens a new way to study temporal domains, as we aim to deal with the temporal complexity of concurrent actions search spaces with only MA techniques, by making use of the necessary temporal techniques only to maintain temporal and numeric soundness.Following PDDL2.1 semantics (Fox and Long 2003), we define the input for our planning algorithm as: Definition 1. Temporal Planning Tasks A temporal planning task is defined as Λ = ⟨ρ, ϑ, O inst , O dur , s 0 , g⟩ where:• ρ is a set of atomic propositional facts,• ϑ is a set of real-valued numeric fluents,• O inst is a set of grounded instantaneous actions,• O dur is a set of grounded durative actions,• s 0 is the initial state, and • g is the goal condition.Instantaneous actions, a inst ∈ O inst , and durative actions, a dur ∈ O dur , differ from each other in the fact that durative actions take time, dur(a dur ), to perform a state transition from s to s ′ . Instantaneous actions preconditions, pre(a inst ), and effects, eff (a inst ) are expanded to start conditions, startCond(a dur ), end conditions, endCond(a dur ), over all dur(a dur ) conditions, inv(a dur ), start effects, start-Eff (a dur ), end effects endEff (a dur ) and numeric effects, contEff (a dur ).Start and end endpoints of a dur , a ⊢ and a ⊣ , can be encoded as instantaneous actions, with pre(a ⊢ ) = startCond(a dur ), eff (a ⊢ ) = startEff (a dur ), pre(a ⊣ ) = endCond(a dur ), and eff (a ⊣ ) = endEff (a dur ). This decomposition produces snap actions, allowing planners to reason with concurrent operators, as it allows them to overlap. The invariant condition, inv(adur), for a durative action (a dur ) must be maintained throughout the open interval between a ⊢ and a ⊣ .For the numeric effects, we impose the same restrictions as the COLIN family of planners: the contribution of any durative action to the rate of change of each numeric fluent, υ ∈ ϑ, remains constant, so the rate of change of a certain variable, δυ, only is modified when the snap actions are applied.Additionally, a metric, M , can be defined to determine the quality of a plan, and it would be the planner's duty to find which plan achieves a higher optimization of that metric. Different planners support a wide range of metric formulations, as the total-cost implementation in LAMA (Richter and Westphal 2010) and time-dependent continuous costs in OPTIC. In our case, we define M as a set of weighted numeric variables, {w 1 * υ 1 , w 2 * υ 2 , ..., w n * υ n } where υ n ∈ ϑ and w n is a real number. υ can also be the duration of the plan, the total-time.From this input, MA-LAMA translates it and utilises internally the multi-valued planning tasks (MPTs) representation, also referred as SAS + planning problems (Bäckström and Nebel 1995) . For ease of presentation, we consider a simplified version of MPTs that omits axioms and with conditional effects compiled away.A multi-valued planning task (MPT) is a 4-tuple ⟨V, I, G, A⟩ where:• V is a finite set of multi-valued variables υ, • I is the initial state for V ,• G is the goal condition and a partial state of V , and220 • A is a set of instantaneous actions.The key difference between the two planning task representations is that variables in an MPT are multi-valued, rather than standard booleans in PDDL2.1. However, for our work we need to extend the MPT definition to fully encompass all the temporal task components, thus, we include the set of multi-valued numeric variables, N, and the metric, M, resulting in our extended MPT (eMPT) definition: Definition 3. Extended Multi-valued planning tasks (eMPTs)An extended multi-valued planning task (MPT) is a 6-tuple ⟨V, I, G, A, N, M ⟩ where:• V , I, G, A are defined as in the MPT Definition.• N , a finite set of multi-valued numeric variables, n, each defined by a real numeric value and a finite set of exclu-235 sive states, and• M , a metric to measure the plan quality, directly assigned from the temporal task.This extension allow us to deal with any numeric operation as an effect over N . We will expand on how to calculate the possible values for each numeric variable n in the MA-LAMA details section.The MPT representation also allows us to build the casual graph (CG), which represents dependencies among variables according to the available actions, and is the root for the MA task decomposition techniques.For a MPT Φ with a set of variables V , the Casual Graph of Φ, CG(Φ) is the directed graph with a set of vertex V that contains an arc (υ, υ ′ ) iff υ ̸ = υ ′ and there exists an action that can affect the value of υ ′ , requiring a precondition that specifies the value of υ.MA-LAMA is a satisfying temporal planner that utilizes MA task decomposition and required cooperation techniques to deal with the temporal complexity of concurrent actions search spaces. Additionally, it is designed to deliver fast and highly optimized solutions for MAP tasks.Let us provide a comprehensive overview of the internal functioning of MA-LAMA, shown in Figure 1 . The first step involves a translation of the temporal task, where the durative actions are transformed to snap actions, adding the same control predicates between a ⊢ and a ⊣ actions as the COLIN planner (Coles et al. 2012) . Then, the snap temporal task is encoded into an eMPT and two MA algorithms take place:• Agent Decomposition (AD): following the ideas of ADP (Crosby, Rovatsos, and Petrick 2013) , MA-LAMA decomposes the eMPT in terms of mostly independent entities, called agents. • Goal Categorization and Assignment (GCA): coordination points are computed following the principles of required cooperation (Zhang, Sreedharan, and Kambhampati 2016) , and the task goals are categorized into cooperation and coordination subsets. Then, the goals are assigned to agents based on metric estimations, creating individual eMPTs to be solved subsequently and in groups, in what we call Search Phases.Our objective with these two algorithms is to be able to strive for near optimal Search Phases solving, and, although we are aware that our decomposition results in a non-complete search space, we assume this compromise to achieve efficiency.In each Search Phase, several eMPTs are solved, taking as an input the temporal constraints imposed by the previous agent eMPT and, similarly, Search Phases inherit the initial state from the previously solved one solution.For each eMPT, we launch a modified version of the LAMA planner, with numeric, temporal and constraints frameworks built on top. Each eMPT is solved by a WA* search using two classical heuristics: h F F (Hoffmann and Nebel 2001) and h Land (Hoffmann, Porteous, and Sebastia 2004) (Sebastia, Onaindia, and Marzal 2006) .All eMPTs in each Search Phase generate a partial plan based on snap actions, so, after all phases are solved, we need to launch a Unify module that translates them to the temporal paradigm and assembles them, checking their temporal soundness and producing the full temporal plan.Although privacy discussion is not a main topic for this work, we can safely state that MA-LAMA preserves weak privacy between the agents found by the AD, but not if a decomposition is not found, as MA-LAMA continues and solves the single-agent complete eMPT in this case.MA-LAMA makes use of the LAMA MPT representation, inherited from Fast Downward (FD) (Helmert 2006) , which only needs to be modified to support the snap task numeric conditions, numCond, and any form of contEff during the temporal task instantiation and multi-valued variables computation through the invariant search. Additionally, as we have expanded the original MPTs definition to eMPTs, we need to determine the possible values for the multi-valued numeric variables, n ∈ N . For each numeric variable n, the set of states, ϵ is obtained by: ∀a ∈ A → ϵ = ϵ ∪ {n ∈ N : n ∈ contEff (a)}, plus the undefined state, u. contEff (a) and numCond(a) are expanded so that all numeric operations that can be solved before the search are solved. Thus, in our eMPTs and for each fluent numeric variable, we encode the current numeric value and last applied numeric effect.Next, we will review in detail each MA-LAMA execution module, starting with Agent Decomposition and Goal Categorization and Assignment, and continue with Constrained Search and Unify, as shown in Figure 1 1-Agent DecompositionMost variable decompositions divide the domain variables between private, variables (that cannot be changed by and are not required by any other agent) and public (representing the environment in which the agents operate), P . We borrow from Crosby et al. (2013) their variable decomposition definition. In short, a variable decomposition of an eMPT divides it in a set of variable groups, Ω = {Ω 1 , Ω 2 , ..., Ω n }, and a set of public variables, P , that can be empty. In their work, they also define Agent Variable Decompositions (ADP); variable decompositions where there are no joint actions and no external actions that can affect any agent internal variables. We do not need to impose this restriction, as we will deal with required cooperation in a later stage.Algorithm 1 gives a pseudo-code overview of the MA-LAMA Agent Decomposition (AD) module, which produces a set of eMPTs ⟨V, I, G, A, N, M ⟩, where all components are set with the exception of G.We consider three main stages in the AD module: 1) Find Possible Agents starts with the ADP basis: removing 2-way cycles from the CG and take resulting root nodes that still have one successor left as possible agents. Then, the algorithms differ, as we aim for different objectives with the decompositions: minimize local agent search space for Algorithm 1: Agent Decomposition (AD) for Ω n ∈ Ω do 8:Input: eM P T ⟨V, I, G, A, N, M ⟩ Output: Agent Decomposed Task set Φ = {Φ 1 , Φ 2 , ...,Ω n ← Ω n ∪ {υ ∈ V : υ only successor of ∪ Ω n } 9:end for 10: until Ω can no longer be refined 11: for Ω n ∈ Ω do 15:A n ← {a ∈ A, υ ∈ Ω n : ∃υ ∈ ∪effΩ n ← Ω n ∪ {υ ∈ V : υ is connected with ∪ Ω n in the CG ∧ υ not yet assigned} 16: end for 17: until every υ ∈ V is assigned 18: A n ← {a ∈ A : ∪eff (a) ∪ ∪pre(a) ∈ Ω n ∧ a not assigned in previous step} 19: N n ← {n ∈ N : n ∈ ∪contEff ({a ∈ A n }) ∪ ∪numPre({a ∈ A n })} 20: I n ← {v ∈ I : v ∈ V n } 21: M n ← {(w * n) ∈ M : n ∈ N n } 22: return {Ω n , I n , ∅, A n , N n , M n }MA-LAMA, and minimize mandatory agent coordination in ADP.We run an Assemble Agents step before expanding all agent sets, so that possible agents are more refined and really coupled agents are merged. The full assembly step can be summarized in one rule:For two possible agents [υ, υ ′ ] in a root node set Ω, υ and 355 υ ′ are assembled if there is a path between υ and υ ′ in the CG.2) Extend Private Agent Sets Agents sets are then expanded so that every υ ∈ V that is only successor of an agent set, Ω n , is added to it. This process is repeated un-360 til all sets can no longer be refined, and a set of actions is added to each agent such that, for every action a ∈ A, it is added to the private set of actions of a certain agent, A n , if there exists a variable υ that exists in eff (a) or pre(a).This results in a private set of variables, Ω n and actions 365 A n for each agent; therefore, the rest of the variables and actions are assumed public, P .3) Extend Public Agent Sets Agent variable sets are completed with all the variables that are reachable in the CG for a certain agent, n: actions not yet assigned are added to Ω n 370 following the same past rule, but using the new complete variable set; numeric variables N and metric, M are added to N n and M n if they appear in the conteff(a) or numCond(a) for every a ∈ A n ; and the initial state I and metric M are decomposed and added to an agent n if they appear in V n .Algorithm 2: Goal Categorization and Assignment (GCA) Input: Agent Task Set, Φ = {Φ 1 , Φ 2 , ..., Φ n },Sol g ← Sol g ∪ relaxedSearch(Φ n , g) 12:end for 13: if Sol g ̸ = ∅ then 14: G coop ← G coop ∪ g,σ coop ← G coop , M inCostAssignment(Φ, G coop ) 23: σ coord ← ∅ 24: for g coord ∈ G coord do 25: σ n ← g coord ∪ CoorP in g coord .Sol g , Φ n in g coord .Sol g 26:σ coord ← σ coord ∪ σ n 27: end for 28: return σ coop ∪ σ coord Our variable decomposition for an eMPT is both sound and complete as we meet all the same three criteria explained in Crosby et al. (2013) , in Theorem 6.1.Finally, the output of the algorithm is a set of tasks, Φ = {Φ 1 , Φ 2 , ..., Φ n }, one for each agent and without any goal assigned. This set is the input for the Goal Categorization and Assignment stage.Algorithm 2 shows the Goal Categorization and Assignment (GCA). The objective is to further exploit the MA nature of the domains by studying how the goals from the original temporal task, G, can be assigned to the agent eMPT set, Φ, to achieve optimized solutions.The basis of the GCA algorithm is the Required Cooperation (RC) Analysis (Zhang, Sreedharan, and Kambhampati 2016) , in which they formally describe the possible agent interactions within an eMPT. From now on, we will refer to goals that require Type-1 RC (Heterogeneous Agents) or Type-2 RC (Homogeneous Agents) Casual Loops interactions as coordination goals, and goals that require Type-2 395 RC Traversability interactions, or no RC at all, as coopera-tion goals. The output of the GCA is a set of Search Phases, each one aiming to solve a goal subset of coordination or cooperation {g} ∈ G.We consider three main stages for the GCA module:1) Coordination Points Variables Coordination points are certain points in an agent plan where it possibly influences or is influenced by other agents. Following this idea, we obtain variables that may be coordination points in our Φ by extracting from P all variables that are both a precondition in one agent actions and an effect in other agent actions.2) Single Goal Relaxed Plans Obtention Then, we launch a relaxed (ignore delete effects and ignore numCond()) search for each goal g ∈ G and agent eMPT Φ n ∈ Φ and calculate a metric value for the relaxed solution, computing numeric variables limits and using the worst-case scenario for fluents in contEff().If a solution is found for any of Φ n , then the goal is considered a cooperation goal, and our aim is then changed to find the most optimized relaxed solution through iterative relaxed searches and for each agent that can achieve it.If a solution is not found, g requires coordination, and a relaxed search is launched for the same g with the full eMPT, trying to minimize the number of used agents in the relaxed solution. The values for variables selected as possible coordination points are stored for later use in the Search Steps creation. The optimization of all relaxed search processes take place for a configurable amount of time or until the complete search space has been explored.We deal with coordination and cooperation goals in different ways:• for cooperation goals, all goals are assigned in a way that minimizes the total sum of all relaxed metrics in a single Search Phase, σ 1 , where agents involved, Φ n ∈ Φ, are those with at least one goal assigned, and• for coordination goals, one Search Phase is created for each, {σ 2 , ..., σ n }, where agents involved are those that appear in the relaxed plan, additionally, the coordination points for each agent are also assigned as goals.We check if the assignments are valid from a numeric conditions perspective before continuing. If there are no relaxed solution for one of the agents in a Search Phase, the process is restarted assigning weights to each agent metric estimation, lowering the use of constrained agents.In average, the time it takes for the GCA to find the best relaxed solution is in the order of milliseconds.The Constrained Search process receives as an input the full set of Search Phases, σ = {σ 1 , σ 2 , ..., σ n }, each with a set of eMPT, Φ = {Φ 1 , Φ 2 , ..., Φ n }. We launch a multiheuristic constrained search over each eMPT, inheriting temporal constraints, (Φ n , υ, t, d), set by the public variables, P , between each agent search, so that interactions between agents are only considered when necessary.A Temporal Constraint, (Φ n , υ, t, d), states that the agent, Φ, sets a certain value, υ, at the moment, t, for the a certain duration, d. 1) Search details For each eMPT, We launch a WA* forward total-order search with two classical heuristics, h F F (Hoffmann and Nebel 2001) , Cost-Sensitive FF/add variant, and h L and (Hoffmann, Porteous, and Sebastia 2004) (Sebastia, Onaindia, and Marzal 2006) . This choice is based on the fact that most MA temporal domains revolve their temporal complexity over the concepts of cooperation and coordination, so the eMPTs that we solve at this point tend to not require complex necessary simultaneity.During search, all states are evaluated with respect to both heuristics, and, when choosing which state to expand, the search algorithm alternates between both based on numerical priorities. Inherited from the LAMA planner, we also make use of preferred-operators, which represent operators that are estimated to be useful in a given state.A temporal framework is introduced to deal with local concurrency, incorporating constraints among snap-actions to guarantee that the preconditions for the new actions are satisfied in the frontier state, as well as keep track of the makespan and running actions start-end times for each state.We follow the same principles with the numeric framework, including the necessary mechanisms to be able to deal with continuous numeric operations and numeric preconditions. Note that our only aim with these frameworks is to guarantee temporal and numeric soundness, and that we do not reason with time or incorporate other numeric solutions as LPs for the sake of fast search graphs exploration.2) Solving Search Phases All Search Phases need a temporal constraints system for two main purposes:• for cooperation goals, to assure that restrictions over variables υ ∈ P are preserved, and• for coordination goals, to synchronize the agents around the coordination points.In practice, temporal constraints are used as conditions in cooperation Search Phases (see Figure 2 ), computing them as inv() = v, starting at time, t, for the duration, d. When a cooperation agent finds a solution, it also computes a set of Temporal Constraints, containing all times a variable v ∈ P value was required or changed. Consecutive agents use this list as limitations to their own local search graphs, and adding their own restrictions when they find a solution.We solve coordination Search Phases, Figure 3 , following the agent order dictated by the coordination points, obtaining the coordination goal at the end. Each agent inherits from the last a set of temporal constraints representing the already obtained subgoals and end states, which serve as the initial state for each local search.Metric optimization in each Search Phase type is achieved differently. First, a cooperation Search Phase will be as optimized as its individual eMPTs are. Since several goals are achieved per agent, the ones with more goals are prioritized, so they solve their eMPTs less restricted by temporal constraints. Coordination Search Phases eMPTs generally only solve one goal, so they are not as promising in terms of numeric optimization. On the other hand, temporal concurrency can still be improved, and it is handled in the next step.The final step in MA-LAMA execution consists of the unification of all partial plans for each Search Phase to obtain a full temporal plan.The unification process of each agent in a Search Phase, Φ n ∈ σ j , snap partial plan, is simple, as we have already dealt with concurrency and constraints in all cases but in between coordination Search Phases. The partial plans for each Search Phase are obtained by assembling each Φ n partial plan in a concurrent manner for cooperation Search Phases, and consecutively in coordination Search Phases.In order to combine all partial plans, we first check for each coordination Search Phase pair, σ n , σ m , and the variables from P that are affected in their respective snap partial plans, P n , P m . If P n ∩ P m = ∅, then both σ n and σ m are added to the complete temporal plan in a concurrent manner.Finally, all remaining partial plans are combined consecutively. During this process, we also calculate the total cost of the final plan; check that the temporal, numeric and logic constraints soundness is maintained; and change the snap actions plan paradigm to temporal.Our experimentation is divided in two sections. First, we study the coverage results of MA-LAMA in temporal and non temporal domains against other classical and temporal solvers, in order to check if the AD and GCA MA algorithms are suitable to deal with a wide range of MA scenarios. And, second, we analyse MA-LAMA plan quality performance for increasingly difficult temporal problems, and against other state-of-the-art temporal planners. We first check the coverage of MA-LAMA in classical and temporal domains, results can be seen in Table 1 .For classical planning, we analyse over the CoDMAP domains and against the ADP-legacy and CMAP-q planners. These are the winners for the competition coverage and quality tracks, and both share internal functionalities with MA-LAMA: ADP shares the root of the agent decomposition, launching FF if the decomposition is not valid; and CMAP-q, that obfuscates the full domain information internally and makes use of the LAMA planner during search.We obtain a similar coverage performance to ADP when an agent decomposition is found, and to CMAP-q if the de-555 composition is invalid (generally, when the AD delivers a decomposition that does not match the competition original domain). Compared with ADP, the slightly worse coverage performance of MA-LAMA is explained by this, as we solve less domains when no decomposition is found. Overall, MA-LAMA achieves a coverage of 88,75%, compared to 92,5% from ADP-legacy and 85% from CMAP-q.For MA temporal domains, we compare against other state-of-the-art temporal planners, already mentioned in the related work section: OPTIC, TFLAP, TFD and POPCORN.We exclude Yahsp3, as its single-thread version is outperformed by TFD and does not work with metrics in our tests, and both TemPorAl and CP4TP, as they are portfolios and the comparisons would not be significant. The domains we chose are Rovers, Satellites and Zenotravel from IPC, and adapted Taxis and Logistics from CodMAP to make them temporal, as Logistics presents required cooperation and Taxis allow us to check a less complex scenario.In this case, MA-LAMA outperforms all planners, specially for IPC domains, where only TFLAP in Satellites and 575 TFD in Zenotravel are able to match MA-LAMA. Regarding the agent decompositions, we obtain the ones a human operator would set: planes in Zenotravel, rovers in Rovers, satel- lites in Satellites, planes and trucks in Logistics and taxis in Taxis. Additionally, only Logistics contained coordination goals, but this did not affect coverage performance. With these results, we can conclude that the AD and GCA algorithms are suitable to deal with MA temporal domains.The coverage results show that MA-LAMA is able to solve a wide range of problems in MA classical domains, and improves state-of-the-art coverage performance for the most complex MA temporal domains.In this section, we will study the plan quality performance in MA temporal domains, the main focus of our planner. For the reasons we outlined in the previous point, we launch the same five planners: OPTIC, TFLAP, TFD, POPCORN and MA-LAMA. Results are detailed in Table 2 . For all domains, we consider problems once the MA nature becomes relevant.MA-LAMA dominates in Rovers (weighted battery) and Zenotravel (weighted fuel + makespan) domains, delivering better quality plans in all instances for Rovers and almost all for Zenotravel, where TFLAP also wins in some problems. These two domains are launched with metrics that are not completely coupled with the makespan of the plan, and the two best performing planners (TFLAP only in Zenotravel) make use of classical heuristics and do not reason with time, meaning that this can be an advantage when optimizing metrics not coupled with the makespan.For Satellites (makespan), result are mixed, MA-LAMA gives better solutions in four problems, and OPTIC and TFD in three. It is clear that planners that reason with time perform better with the makespan metric, but, as instances get more complex, MA-LAMA deals better with them and is able to deliver good solutions in these last problems. This trend is present in the domains. The CodMAP domains are significantly less complex than the IPC ones, as several planners find optimal (or near optimal) solutions for several instances. In these cases, MA-LAMA depends on the GCA algorithm to deliver the best solution, as a non-optimal goal assignment results in a nonoptimal final solution, which happens in several instances of Taxis (weighted distance) and Logistics (weighted fuel). Similarly to the previous case, as problems incorporate more agents and variables, all planners begin to struggle to optimize the solutions, and the MA nature of MA-LAMA proves to be an advantage in these cases for both domains.Logistics has been incorporated as the case where coordination goals cannot be avoided, and MA-LAMA is able to find the optimal solution only in some easier domains, showing good performance in the latest ones. This proves that the GCA is only suitable for scenarios where finding optimal solutions in a short time span is not feasible, as it looses too much information in the estimation process for lighter ones.Lastly, we want to take a look on the search time and expanded nodes for each planner in the Rovers domain, shown in Figure 4 and Figure 5 . POPCORN and TFLAP are excluded since they do not solve the majority of the problems.For OPTIC, and more notably for TFD, the increase in expanded nodes can be tied to an increase in search time, and increasing the number of agents causes them to struggle to find good, if any, solution. MA-LAMA does not reproduce these behaviors, expanded nodes and search time remain stable through the whole domain, with peaks in expanded nodes when the individual agent eMPTs are harder, as in p16. Additionally, the increase in the number of agents does not translate in worse performance, as the AD and GCA algorithms remove much of the temporal complexity that this certain domain presents.To conclude, experiments infer that the MA techniques in MA-LAMA perform suitable decompositions for MA temporal domains, and that MA-LAMA delivers better plan quality performance than other state-of-the-art temporal solvers in the most complex problems for all tested domains.650 MA-LAMA does not reason with temporal or numeric information during search, so, in domains where a decomposition is not found, it is expected to underperform other planners. Other techniques, as symmetry based decompositions or search time reasoning could be incorporated for theses 655 cases. Additionally, the classical heuristics used can run into plateaus during search due to the lack of temporal reasoning.The AD algorithm can be improved to cover a wider range of MA domains, as currently there are several domains from CodMAP that remain hard to decompose automatically into 660 logical sets of variables.Finally, our experimentation shows that MA-LAMA improved plan quality performance over multi-agent temporal domains over the state-of-the-art, but it is expected to be dominated in other types of scenarios. A future line of work 665 may consider including MA-LAMA and other planners to build a portfolio, launching only selected planners based on a domain structure analysis performed before the search.In this paper, we presented MA-LAMA, a satisfying tempo-670 ral MA planner that utilises MA techniques to deal with concurrent action search spaces. The AD and GCA algorithms decompose the temporal MAP tasks in Search Phases in a way that reduces temporal complexity and that is suitable for metric optimization.Our experimentation shows that MA-LAMA outperforms other state-of-the-art temporal planners in terms of coverage and plan quality in MA temporal domains, especially in the most complex domain instances.  
 
 Appendix:  


Decision: The authors present a new algorithm for solving multi-agent temporal planning problems. The approach is sound and well established with respect to the state of the art. The empirical evaluation is well conducting and highlights important benefits in several well established benchmarks.

The rebuttal provides important clarifications, notably regarding proof sketches and the imposed sequencing of the decision-making, that should be integrated in the final manuscript.

Reviews: review: strength_weakness: strength_weakness: - minor: grammar through the paper has to be revisited/checked (e.g. start of system enumeration in the 2nd paragraph of related work, or the use of the term based in -> based on, or "makes us of", etc)
- minor: experiment includes non-temporal problems. I don't believe this is adding much here is the goal is to address temporal problem.
questions: questions: - The categorization provided in the 3rd paragraph of the Intro (from  (Torreno et al. 2017) is not completely aligned with the definition given for the proposed system "a centralized, unthreaded, satisfying, total-order, temporal MAP system". For example wrt privacy preservation doesn't seem to be in that definition. What is the categorization according to (Torreno et al. 2017)?
- the work proposes/includes ways to decompose the problem and solve them through this decomposition-unify process. I am wonder what is if there a certain type of characteristic of problems in which this decomposition approach fails to produce good plans.
- OPTIC seems to provide good results in the experiments. Do you consider the performance of the proposed planner to be significantly better than the other planners. Table 2 shows good results for MA-LAMA - it seems that it is ~2x better in some cases. I missed addidional data related to run time for instance, maybe there is significant difference between the runtimes?
strength_weakness: strength_weakness: The proofs for the correctness of the algorithms are missing.
questions: questions: 1. Do the authors have proofs for the correctness of the algorithms? 
2. This might not be a question but I was wondering whether MA-LAMA was tested with non-temporal domains such as logistics (multiple agents); if it was, whether MA-LAMA performs better than LAMA?
strength_weakness: strength_weakness: The paper seems to me nice. A weak point can be a negative impact of sequencing solving decisions (Agent decomposition and Goal Assignment steps). Namely, the application in sequence of decisions taken on agent selection/goal assignments may prevent to find other (better) valid solutions.
questions: questions: is it possible to assess the impact of agent decomposition decisions with respect to goal assignement?

Is it possible to evaluate whether these sequential decisions can actually influence the quality of the generated solutions?