Distributed Allocation and Scheduling of Tasks With Cross-Schedule Dependencies for Heterogeneous Multi-Robot Teams

Received 12 March 2024, accepted 9 May 2024, date of publication 23 May 2024, date of current version 3 June 2024. Digital Object Identifier 10.1109/ACCESS.2024.3404823 Distributed Allocation and Scheduling of Tasks With Cross-Schedule Dependencies for Heterogeneous Multi-Robot Teams BARBARA ARBANAS FERREIRA 1, (Member, IEEE), TAMARA PETROVIĆ 1, (Member, IEEE), MATKO ORSAG 1, (Member, IEEE), J. RAMIRO MARTÍNEZ-DE DIOS 2, (Member, IEEE), AND STJEPAN BOGDAN 1, (Senior Member, IEEE) 1Faculty of Electrical Engineering and Computing, University of Zagreb, 10000 Zagreb, Croatia 2GRVC Robotics Laboratory, University of Seville, 41092 Seville, Spain Corresponding author: Barbara Arbanas Ferreira ([email protected]) This work was supported in part by European Union’s Horizon Europe Research Program Widening Participation and Spreading Excellence through Project Strengthening Research and Innovation Excellence in Autonomous Aerial Systems (AeroSTREAM) under Grant 101071270, and in part by Croatian Science Foundation under SPECULARIA Project UIP-2017-05-4042. ABSTRACT To enable safe and efficient use of multi-robot systems in everyday life, a robust and fast method for coordinating their actions must be developed. In this paper, we present a distributed task allocation and scheduling algorithm for missions where the tasks of different robots are tightly coupled with temporal and precedence constraints. The approach is based on representing the problem as a variant of the vehicle routing problem, and the solution is found using a distributed metaheuristic algorithm based on evolutionary computation (CBM-pop). Such an approach allows a fast and near-optimal allocation and can therefore be used for online applications. Simulation results show that the approach has better computational speed and scalability without loss of optimality compared to the state-of-the-art distributed methods. An application of the planning procedure to a practical use case of a greenhouse maintained by a multi-robot system is given. INDEX TERMS Multi-robot systems, multi-robot coordination, task allocation, task scheduling, vehicle routing problem, distributed optimization. I. INTRODUCTION Research on cooperative multi-robot systems (MRS) has received considerable attention in recent years due to its compelling advantages over single-robot applications. The main challenge is to create a robust and intelligent control system that enables seamless communication and task coordination between robots so that they can work efficiently as a team. Therefore, control architecture design, communication, and mission planning are the main problems discussed and solved in the literature. In this paper, we discuss the problems of task allocation (the question of who does what?) and task scheduling (the question of how to arrange the tasks in time?) of multi-robot systems, which are often summarized under the common term mission (task) planning. The associate editor coordinating the review of this manuscript and approving it for publication was Emanuele Crisostomi . In this paper, we propose a distributed solution for task planning problem in heterogeneous multi-robot teams for problems within the class XD[ST-SR-TA] defined in the taxonomy in [1]. These task types require execution by a single robot (SR, single-robot tasks), and robots are allowed to execute only one task at a time (ST, single-task robots). The task allocation and scheduling procedure considers both current and future assignments (TA, time-extended assignment). In terms of complexity, these tasks involve cross-schedule dependencies (XD), where various constraints relate tasks from plans of different robots. The cross-schedule dependencies we consider are precedence constraints and transitional dependencies. The heterogeneity within the system arises from various factors, including the different hardware configurations and physical capabilities of each robot, which include sensor diversity, perceptual capabilities and different actuation mechanisms. The intended roles VOLUME 12, 2024 2024 The Authors. This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License. For more information, see https://creativecommons.org/licenses/by-nc-nd/4.0/ 74327 B. Arbanas Ferreira et al.: Distributed Allocation and Scheduling of Tasks With Cross-Schedule Dependencies and behaviors, such as specialization in certain tasks, also contribute significantly to this diversity. In our approach, we reinterpret the task planning problem as a variant of the Vehicle Routing Problem (VRP). We combine the task planning problem with a variant of the well-studied Multi-Depot VRP model (MDVRP), in particular, the MDVRP with a heterogeneous fleet [2], hereafter referred to as HF-MDVRP. By doing so, we define a generic model of task planning problems that can be applied to different domains of multi-robot and multi-agent systems. Another advantage of the proposed modeling is that it exposes the task planning problems to a wide range of optimization techniques already available in the VRP literature, thus advancing the state of the art in task planning. To solve the task planning problem modeled as HFMDVRP, we propose a distributed metaheuristic algorithm based on the Coalition-Based Metaheuristic (CBM) paradigm [3] (CBM-pop1). We chose a distributed approach because it offers more reliability, flexibility, adaptability and robustness. This approach is particularly suitable for dynamic field applications with resource-constrained robots and can provide near-optimal solutions to difficult optimization problems in a reasonable amount of time. To empirically validate the proposed algorithm, we created a generic set of multi-robot task planning problems (a new benchmarking dataset, [4]) with precedence constraints and transitional dependencies and compared our solution with the following techniques: 1) Gurobi Optimizer [5]. Gurobi is a centralized solution that uses exact mathematical methods to solve Mixed-Integer Linear Programming (MILP) problems. Gurobi provides an optimality gap for each solution and can therefore serve as a measure of the optimality of the proposed solution. 2) State-of-the-art distributed auction-based approach with a single central agent acting as an auctioneer [6]. We slightly adapt the method to suit our problem class. Using an extensive series of simulation runs of these solutions, we have shown that our method is state-of-the-art in terms of optimality. The advantage of our approach is better computational speed and scalability, which is essential for online operation of multi-robot systems. Another important advantage is that our solution produces results in a distributed manner. The auction algorithm, on the other hand, assumes a central auctioneer agent that processes bids from other agents and makes task assignments. In distributed systems, this may be regarded as a tactically vulnerable point. Although our proposed method is suitable for dynamic setups with on-the- fly mission rescheduling, dynamic applications are beyond the scope of this paper and are deferred for future work. To illustrate the effectiveness of the method, we apply it to a case of multi-robot collaboration in a robotized greenhouse, as presented in the SPECULARIA project [7]. This contribution is part of a more comprehensive work 1https://github.com/barbara0811/cbm_pop_mdvrp_optimization presented in the dissertation by Arbanas Ferreira [8]. A more detailed examination of the results presented here can be found in the full dissertation. The paper is organized as follows. In the next section, we outline approaches to MDVRP problems and justify the solution we chose to model our problem. In Section III, we formally define the task planning problem and present our original contributions. Next, we define the unified model, which combines task planning and HF-MDVRP. In Section V, we present CBM-pop to solve the defined unified model. Section VI contains a detailed evaluation of the results and a discussion. In the same section, we show how the proposed approach can be applied to the SPECULARIA use case. Finally, we draw conclusions and give an outlook on future work in Section VII. II. RELATED WORK To improve readability, this section begins with a description of the current state of mission planning. We then focus on solutions specifically targeted at VRP-based models. A. MISSION PLANNING Some of the best-known distributed solutions to the mission planning problem are auction and market-based approaches [6],[9],[10]. These generally fall into the domain of task allocation (and omit scheduling of tasks), where robots use bidding mechanisms for a set of simple tasks to allocate tasks among themselves. However, the partial ordering between tasks and tight coupling, which are the basis for our cooperative missions, are rarely considered. These constraints concern a class of problems [1] where an agent’s effective utility for a task depends on other tasks assigned to that agent (In-Schedule Dependencies, ID) or additionally on the schedules of other agents (Cross-Schedule Dependencies, XD). More recently, the authors in [6] and [11] have addressed the problem of precedence constraints in iterative auctions. These algorithms can be run offline or online, and they solve the same class of problems as those considered in this work. However, all these solutions still require a central auctioneer node that is in constant communication with all other nodes, which can be considered as a weak point of the system. To alleviate this issue, solutions that use consensus algorithms for bid resolution have been suggested. A pioneering work in this area is the Consensus Based Bundle Algorithm (CBBA) [10]. Authors in [12] extended the basic algorithm to incorporate temporal constraints. However, the objective function remains rather simple, as it only accounts for a number of completed tasks without considering the usual metrics such as cost or duration of the mission. On the other side of the spectrum, various optimizationbased methods attempt to solve the task planning problem. They range from exact offline solutions [13] to heuristic approaches such as evolutionary computation and other AI optimization methods [14],[15]. In the former, a slightly broader class of problems is considered than in this 74328 VOLUME 12, 2024 B. Arbanas Ferreira et al.: Distributed Allocation and Scheduling of Tasks With Cross-Schedule Dependencies work, where robots may perform more than one task simultaneously. The problem is modeled as an instance of a MILP problem and solved using offline solvers or well-known optimization methods. Although optimal, the method involves a high computational burden and lacks reactivity in dynamic environments. In our previous work, we proposed the decentralized framework for multi-robot coordination [16],[17], which defines the design of particular decision-making modules and their architecture, as well as coordination mechanisms that ensure coordinated behavior. In these examples, fairly simple algorithms are used for task allocation and scheduling. In [16], tasks are assigned to robots using a greedy function that allots each task to the robot with the best score for that task and ignores the effects on other task assignments. In recent work [17], we extended the assignment function to a simple market-based task allocation scheme that aims to minimize the total mission duration. B. TASK PLANNING AS VRP The problems considered here (XD[ST-SR-TA]) fit well into the MDVRP model, particularly the HF-MDVRP variant. MDVRP is a VRP variation that deals with problems where customers are served from multiple depots with a given fleet of vehicles. It is a classic example of an NP-hard [18] combinatorial optimization problem. Even for relatively small problem sizes, it is challenging to solve MDVRP optimally. Given the rapid combinatorial explosion, it quickly becomes impossible to obtain optimal solutions for this type of problem. Similar modeling was proposed in [19], where task planning refers to the Dial-a-Ride Problem (DARP), a variant of VRP with pickup and delivery. To solve the problem, the authors use a centralized bounded optimal branch-and-price algorithm. Although the idea is similar, the set-partitioning formulation [19] is mainly suitable for solutions employing exact methods and cannot be directly used to solve non-trivial VRP instances due to the large number of possible routes. The method suffers from a high computational cost, scalability issues, and the inability to work online in distributed systems. Therefore, in this paper, we have defined a more manageable and general representation that can be easily used in various heuristic approaches. Many heuristic methods have been proposed for MDVRP problems, and distributed approaches have been particularly suitable for multi-robot systems. More recently, Distributed Artificial Intelligence (DAI) has extended to multi-agent systems that deal with complex combinatorial problems. These multi-agent concepts can be readily applied to various metaheuristics, in particular population-based, hybrid and distributed metaheuristics. The distributed approach provides higher computational performance by executing tasks in parallel and improves robustness and efficiency through agent collaboration. Our algorithm is inspired by the Coalition- Based Metaheuristic [3], which applies established DAI principles to solve VRP problems. Other approaches include distributed heuristic optimization algorithms such as Multi-Point Stochastic Insertion Cost Gradient Descent (MuPSICGD) [20], a distributed learning-based evolutionary algorithm [21], and the artificial bee colony algorithm [22]. In [23], the authors use a distributed game theoretic model to distribute products to customers without a central authority. Although each of these approaches would be suitable for solving our HF-MDVRP problem, we found that they are either comparatively slower or have worse optimality on the MDVRP benchmark dataset. The full comparison was not included in the paper for brevity, but can be found at [24]. ORIGINAL CONTRIBUTIONS OF THE PAPER The original contributions presented and discussed in this paper are: 1) The unified task planning model based on VRP paradigm. It combines problems of task planning with a variant of the well-studied Multi-Depot VRP (MDVRP) model, which generalizes the problem and makes it domain-agnostic. In particular, we consider MDVRP with heterogeneous fleet, HF-MDVRP. 2) Distributed metaheuristic algorithm for the defined problem based on the Coalition-Based Metaheuristic (CBM) paradigm (CBM-pop). 3) An open benchmark dataset repository of task planning problems of class XD[ST-SR-TA]. Our proposed benchmark dataset includes problems with 2n,2≤n≤ 10,n∈Ntasks and 2−8 robots, providing a large-scale test of the efficiency and scalability of task planning algorithms. III. TASK PLANNING PROBLEM In this paper we consider two mathematical formulations. First, we formally define the task planning problem in this section, followed by the mathematical representation of the unified model that represents task planning as a VRP variant. The solution to the task planning problem proposed in this paper is based on the unified mathematical model. We consider a problem where a team of heterogeneous robots R= {1,...,m}is available to perform a collection of simple single-agent tasks (actions) A= {1,...,n}. One or more robots can perform each a∈A, and we specify the set of actions that robot ican perform as Ai. Redundancy is possible, and in general Ai∩Aj= ∅,i= j,and i,j∈R. In addition, we define precedence constraints on the set of actions. If the action a∈Amust be completed before the action b∈Astarts, we can specify a constraint between the two as prec(a,b). This constraint forces af<bs, where af and bsindicate the times when the action afinishes and b starts. In addition to strict precedence constraints, the task planning problem also involves transitional dependencies between actions. The problem involves the transition time between two actions (setup time), which includes all the operations required to go from the execution of one action VOLUME 12, 2024 74329 B. Arbanas Ferreira et al.: Distributed Allocation and Scheduling of Tasks With Cross-Schedule Dependencies to the start of processing the next action. This term represents an additional temporal dependency on the order of actions, since direct predecessors and successors of actions strongly influence the total duration of the mission and the associated costs (setup costs). Another naturally occurring constraint inherent in the physical system itself is the capacity constraint, which is expressed in the limited battery resources of each robot. Each action requires a certain amount of energy to be performed, which depends on the physical properties of the robot and the current state of the system (i.e., robot position, battery status, and current payload). For a robot i∈Rwith the capacity Qi, we define the capacity constraint as Pa∈Siqi(a)≤Qi, where Si(Si⊆Ai) is the set of actions assigned to the robot ifor execution, and qi(a) is the energy requirement of the action a to be completed by robot i. A solution to the described problem is a set of time-related actions (schedule) for all robots that do not violate the specified constraints. Formally, the schedule sifor each robot i∈Ris defined as si= {(a,as,af)∀a∈Si}, where Siis the set of actions assigned to the robot i, and as(af) are the start (finish) times of the action a. In the evaluation procedure, each action a∈Ais assigned a couple (da(i),ca(i)),∀i∈R, where da(i) stands for the duration of the action awhen performed by robot iand ca(i) for the cost of the action. The robot estimates the duration and cost of a future task based on the current state of the system. The planning procedure aims to find a solution that meets all constraints and maximizes the global reward of the system. The objective function can be chosen at will, depending on the system requirements. All defined sets and variables are later summarized in Table 1, in direct comparison with HF-MDVRP and the unified model of task planning as VRP. IV. UNIFIED TASK PLANNING MODEL FORMULATION The problem modeling in this section is based on the VRP paradigm, which is included in Appendix Aof this paper for the convenience of readers. In this section, we describe the elements of HF-MDVRP through the lens of task planning and equate all the building blocks of the VRP-based model with a concept of task planning. Then we define the full unified mathematical model in terms of a MILP. A. TASK PLANNING AS HF-MDVRP In relating the task planning problem to the HF-MDVRP model, we associate the fundamental VRP concepts directly with the task planning paradigm. As shown in Figure 1, the idea of a depot in VRP problems is directly related to the initial position of the robot, and the vehicle in VRP represents a robot itself. Next, the concept of customer and customer demand is applied to the actions in task planning and the energy demand of each action, respectively. Consequently, the routes (sequences of customer nodes to be visited) as solutions to VRP problems represent the sequence of actions in the final robot schedules in the task planning model. Based on the metaphor thus specified, we describe the mathematical model of task planning problems defined as a VRP problem variant. In the modeling of task planning as a VRP variant, we use the term customer for the simple single-robot tasks, actions. We designate the set N= {1,...,n} = A, where Ais the set of actions, and Nis the set of customers in the original VRP modeling. This definition includes only actionable elements from the robot’s task structure, and all tasks must be decomposed down to the action level where vehicle routing is optimized. In the task planning paradigm, we directly equate the concept of a vehicle with robots, K= {1,...,m} = R, where Kis the set of vehicles, and Rthe corresponding robot set. Typically, the VRP paradigm requires vehicles to start at the depot, serve assigned customers along the route, and return to the depot. In our modeling, we equate the term depot with the initial location of the robot. Unlike the vehicles in typical VRP problems, the robot is not required to return to the starting point. Such a variant of VRP is referred to in the literature as open VRP [25]. The proposed model distinguishes between two different cost variants. On the one hand, the cost of transitioning between two tasks, setup cost, is directly related to the travel cost of HF-MDVRP. This cost can include any movement between locations and the possible setup cost between two tasks and is defined as cijr ,i,j∈ {0} ∪ A,i= j,r∈ R. Closely related to the setup cost is the setup time, tijr ,i,j∈ {0} ∪ A,i= j,r∈R, which defines the duration of the robot’s setup between two tasks. Next, the energy requirement of the specific action i∈Ais defined as qir ,r∈Rand characterized as the customer demand in HF-MDVRP. According to the specified modeling, the robot schedules are constructed based on the routes in the HF-MDVRP solution. The parallel is apparent since both constructs represent temporally ordered sequences of tasks. In the open VRP paradigm, a route is a sequence r∗=(i0,i1,...,is) with i0=0, where 0 denotes a depot node. In our modeling, we take the previously defined concept of a schedule and map the order of tasks in a schedule to the arranged sequence of tasks s∗ r=(i0,i1,...,i|Sr|),ij∈Sr,j∈ {1,...,|Sr|},r∈R, where i0is a zero-cost task associated with the robot’s starting location, and Sris a set of scheduled tasks. Temporal elements of the schedule are the task start time and the task duration, defined respectively as: ωir := as i,i∈Sr,r∈Rand σir := di=af i−as i,i∈Sr,r∈R. A schedule for a robot r∈Ris considered feasible if the capacity constraint qr(Sr):= Pi∈Srqir ≤Qrholds, no task is scheduled more than once, ij= ikfor all 1 ≤ j<k≤ |A|, and precedence and transitional constraints are respected. When it is necessary to perform repetitive tasks, each occurrence of the task should be treated as a separate entity. All previously defined relations are summarized in the Table 1and additionally illustrated in Figure 1. 74330 VOLUME 12, 2024 B. Arbanas Ferreira et al.: Distributed Allocation and Scheduling of Tasks With Cross-Schedule Dependencies TABLE 1. Task planning elements as HF-MDVRP. FIGURE 1. An illustration of the relationship of the HF-MDVRP model to the task planning paradigm. The diagram shows the direct relation between concepts in VRP and task planning problems, where depots represent initial robot positions, vehicles stand for robots, customers refer to actions, and vehicle routes represent final robot schedules. B. UNIFIED MODEL FORMULATION The mathematical representation of the unified task planning model as MILP is based on the graph structure. Let Vbe the set of vertices (or nodes) consisting of two distinct sets of nodes, the action nodes Va=A= {1,...,n}and the start position nodes Vs= {1,...,l}, where nand lrepresent the number of available tasks and robot start positions, respectively. It holds that V=Va∪Vsand Va∩Vs= ∅. The underlying graph G=(V,E) is complete and directed with edge set E= {e=(i,j):i,j∈V,i= j,iand jnot both in Vs}. We model heterogeneity motivated by a mixed fleet variant of MDVRP, in which the set of customers available to the vehicle corresponds in the task planning formulation to a subset of actions Arthat the robot r∈Rcan perform. To model unavailable tasks j∈A\Ar, we set cijr to a sufficiently large number Mfor all (i,j)∈Erelated to the unreachable task j. Further aspects of heterogeneity of multi-robot systems are achieved by replacing the general coefficients of HF-MDVRP with robot-specific ones, e.g., the capacity Qby Qr, the energy requirement qiby qir for all i∈Va, and the cost cij by cijr for all (i,j)∈E. For the given precedence constraints prec(ai,aj), ai,aj∈A and assuming that tasks ai(aj) correspond to nodes i(j)∈Va, we represent the precedence constraint in VRP notation by adding the pair of tasks to the set of constrained tasks 5= {(i,j),i,j∈Va}. The constraint on the tasks is then ωi+σi≤ωj,(i,j)∈5, (1) where ωiand ωjmark the beginning of the tasks iand j respectively, and σidenotes the duration of task i. We also distinguish particular ωir as the start time of task iwhen it is executed by robot r∈R, and the corresponding task duration σir . The expressions for these cases are defined in the full model representation. TABLE 2. Defined sets in the unified model. For convenience, all sets, variables, and constants of the model are summarized in Tables 2and 3. VOLUME 12, 2024 74331 B. Arbanas Ferreira et al.: Distributed Allocation and Scheduling of Tasks With Cross-Schedule Dependencies TABLE 3. Defined variables and constants in the unified model. Definition 1 (Unified Task Planning Model Formulation): Based on the relations defined in this section, we define the unified task planning model built according to the HF-MDVRP MILP formulation. The binary decision variable xijr is defined to indicate whether the robot r∈Rtraverses an edge (i,j)∈Ein a given solution. Then, the model is given as: min        δ=max(Xr∈RXi′∈Vxi′ir (ωir +σir )) −min(Xr∈RXj′∈Vxj′jr ωjr ) γ=Xr∈RX(i,j)∈Exijr (cijr +qjr ) (2.1) Subject to X r∈RX i∈V,i=j xijr ≤1,∀j∈Va,(2.2) X j∈Va xijr ≤1,∀i∈Vs,r∈Ri,(2.3) X (i,j)∈E xijr (ωir +σir +tijr −ωjr )≤0,∀r∈R (2.4) X r∈RX i′∈V xi′ir (ωir +σir )≤X r∈RX j′∈V xj′jr ωjr ,∀(i,j)∈5, (2.5) X i∈VX j∈V\{0},j=i qjr xijr ≤Qr,∀r∈R,(2.6) X r∈RX i∈SX j∈S,j=i xijr ≤ |S| − 1,∀S⊆Va, (2.7) xijr ∈ {0,1},∀r∈R,(i,j)∈E,(2.8) ωir ∈R,∀i∈V,r∈R.(2.9) The objectives of the optimization problem are represented by Equations (2.1). The goal is to find a solution that minimizes the makespan δ(the difference between the latest action finish time in the whole mission and the earliest action start) and the cost γ. Actions i′and j′are possible direct predecessors of actions iand j, respectively, in the schedules of the same robot. The sum Pi′∈Vxi′ir is equal to 1 for exactly one action i′that precedes iin the schedule of robot r. Constraints (2.2) require that each task is executed at most once. Equations (2.3) state that each robot may execute at most one schedule (only one edge starting at robot’s initial position can be incorporated in the solution). Note that flow constraints represented in previously defined versions of VRP in Equations (7.4) are omitted here. This is because we do not restrict this model to provide closed-loop solutions, as we consider the open VRP formulation. Next, constraints (2.4) guarantee schedule feasibility with respect to considerations in the schedule of each robot. The tijr represents the setup time between actions iand jfor robot r. The constraints defined by (2.5) enforce precedence constraints. Equations (2.6) ensure that the capacity constraints are met by the robots, while (2.7) eliminate all possible sub-tours in the solution. Finally, variable domains are provided in (2.8) and (2.9). V. SOLUTION APPROACH In this section, we present our algorithm inspired by the CBM paradigm to solve the problem described in Section IV. We provide a brief overview of the motivating algorithm that forms the basis for our approach. We then go into the details of our implementation, highlighting the novel elements. A. THE COALITION-BASED METAHEURISTIC (CBM) In CBM [3], multiple agents organized in a coalition simultaneously explore the solution space, cooperate, and self-adapt to solve the given problem collectively. The novelty introduced in this algorithm was the use of basic DAI principles, reinforcement, and mimetic learning, which not only allows agents to learn from their experiences and adapt their future behaviors accordingly, but also shares knowledge with other agents in the coalition. In addition to the learned behaviors, the agents also share the best solutions found, so that at the end of each iteration of the algorithm, the best global solution to the problem is obtained. FIGURE 2. CBM agent structure. The visual representation of the CBM agents is shown in Figure 2. During the search process, each agent maintains three solutions, similarly to particle swarm optimization [26]: a current solution, the best solution found by the agent, and the best solution found by the entire coalition. An agent uses 74332 VOLUME 12, 2024 B. Arbanas Ferreira et al.: Distributed Allocation and Scheduling of Tasks With Cross-Schedule Dependencies several operators that are applied to the current solution. The operators can be intensifiers or diversifiers. Intensifier operators concern improvement processes such as local search, and diversifier operators correspond to generation, mutation, or crossover procedures. The choice of operators to apply is not completely stochastic as in Genetic Algorithms (GA). Instead, it is determined by a decision process that uses perceived state and past experience to select the most appropriate operators and coordinate intensification and diversification procedures. The selection of operators is based on heuristic rules. The search behavior of an agent is adapted during the optimization process through an individual reinforcement learning mechanism and mimetic learning. These mechanisms modify the rules of the decision process based on the experience results of previous explorations. Although all agents in the coalition use the same set of operators, the learning mechanisms may ultimately lead to different strategies. Agents cooperate in two ways. First, an agent can inform the rest of the coalition about the newly found best coalition solution. Second, agents share their internal decision rules to enable mimetic behavior. This fosters search behavior in which desirable solutions are often found. In [3], the authors proposed the CBM solution for a case of VRP. In our case, we consider a HF-MDVRP and thus need to formulate a suitable set of operators. Moreover, we modified the basic CBM algorithm to keep more than one current solution so that a population of solutions is preserved, similar to GA methods. In the rest of the paper, we refer to the proposed algorithm as CBM-pop. Details on the implementation of the algorithm follow in this section. B. DISTRIBUTED METAHEURISTIC FOR HF-MDVRP The first feature to consider in the design of the algorithm is the representation of the solution. Since this metaheuristic is based on a set of operators commonly used in genetic algorithms, we use the same encoding of the solutions in terms of the chromosome. Inspired by an evolutionary process, each chromosome contains genetic material that defines a solution (genotype). In the case of HF-MDVRP, this refers to the assignment of actions to different robots and their order within a sequence of tasks in the schedule. An indirect coding, based on permutations of actions, similar to the one in [27], was used. Each chromosome is associated with a phenotype that evaluates the genetic material and, in our case, generates schedules for task sequences based on the temporal properties of the tasks. An example of a chromosome and its genotype and phenotype is shown in Figure 3. On the left is shown the genetic material of a solution containing specified task groupings of robots (robot1, robot2, robot3) and ordering. The genotype representation is maintained respecting intra-schedule precedence constraints. On the right is an example of a phenotype generated from the specified genotype. The schedule is formed by introducing time FIGURE 3. Solution representation – chromosome genotype and phenotype. The tasks presented here are arbitrarily named generic tasks ((A,B,C)×(1,2,3)). The idle times introduced in the schedules are a consequence of precedence constraints prec(A1,A3) and prec(A3,C1), since task A3 cannot start before task A1 finishes, and task C1 cannot start before the end of A3. elements into the ordered tasks (task durations, task setup times). If necessary, minimal idle times are inserted to ensure consistency with the defined precedence constraints. The phenotype represents the so-called semi-active schedule, where no left shift is possible in the Gantt graph. For any given sequence of robot operations, there is only one semiactive schedule [28]. One advantage of storing solutions in this way is faster exploration of the solution space, since all operators perform on a simpler genotype representation of the solution. The evaluation procedure renders the phenotype and evaluates the solutions found. The next point to consider is the evaluation of the solution. The usual approach to solution evaluation is to use a fitness function that maps each chromosome in a population to a value of the utility function in R. This usually works best when the search is limited to a single optimization objective. For multi-objective optimization problems, it is best to employ a ranking procedure because these objectives often interact in complex, nonlinear ways. In this work, we use a Pareto ranking procedure [29] that assigns ranks to all solutions based on the non-dominance property (i.e., a solution with a lower rank is clearly superior to solutions with a higher rank concerning all objectives). Therefore, solutions are stratified into multiple ranks based on their ability to meet the optimization objectives. An important property of the Pareto front is that it allows us to determine the trade-offs of each decision, namely the reduction in the performance of the other objectives if one is improved along the frontier. Therefore, we can easily determine the priority of the different criteria for the solutions that are on the Pareto front. An alternative approach of using weighted sum function was discarded since the problem of determining weights is often non-trivial and may not produce good results, but also it is impossible to obtain points on non-convex parts of the Pareto-optimal set in the criterion space. To evaluate solutions in a population P, we apply the double-rank strategy, which takes into account both the density information and the distribution of the solution in the rank. In the first step, an individual i∈Pis assigned a dummy rank value R′(i) representing the number of solutions that dominate it in the current population P: R′(i)= |{j,j∈P,i≺j}|,∀i∈P,(3) VOLUME 12, 2024 74333 B. Arbanas Ferreira et al.: Distributed Allocation and Scheduling of Tasks With Cross-Schedule Dependencies where the symbol ≺corresponds to the Pareto dominance relation, i.e., i≺jif the solution jperforms better than igiven all optimization criteria. The final rank of solution R(i) is then defined as the sum of its own dummy rank value and that of its dominators: R(i)=R′(i)+X j∈P,i≺j R′(j),∀i∈P.(4) The second part of the fitness function is the density function, which determines how similar the solution is to the other individuals in the population. Here we use a fairly simple solution where the density of an individual is inversely proportional to the distance to the nearest solution in the population and is calculated as follows: dens(i)=1 min(d(i,j),∀j∈P)+2,∀i∈P,(5) where d(i,j) represents the Euclidean distance between two individuals in the criteria space. Finally, the fitness of the solution is obtained as: fitness(i)=1 R(i)+dens(i)+1,∀i∈P.(6) In this setup, the rank of the solution has a much greater weight in the fitness function, since it is a natural number denoting a subset of solutions from the population, and the rank is a positive number smaller than 1/2. The role of the density function is to discriminate between solutions of the same rank and to favour the more diverse solutions, as they are deemed more likely to explore new regions of the solution space. Next, we briefly discuss the operators that form the core of the algorithm. We distinguish between generation, diversification (crossover and mutation operators), and intensification operators (local search algorithms). In our application, the generation operator is not used as a diversifier because it is applied during initial population creation. In the proposed solution, we use a single generation operator, a greedy insertion method that randomly takes an unassigned task and inserts it into existing routes at minimal cost, taking into account capacity constraints. Other operators are listed and described in Table 4. Diversification operators are first introduced in [30], and we implemented them for our specific problem. In the crossover procedure, we distinguish two cases of Best-Cost Route Crossover (BCRC), depending on the choice of parent chromosomes. One of the parents is always the current solution of the agent and the second parent is either the best solution found within the whole coalition or selected from the population. Similarly, we adapted the local search algorithms developed in [3] for a VRP problem class. In all these operators, the logic remains the same, but the additional ordering constraints arising from the precedence relation have been taken into account, which is a non-trivial task. For each chromosome, we maintain a directed graph with precedence constraints derived from the original constraints and the order of precedence-constrained nodes within the route. For each operator, we consider the precedence graph and allow insertion of nodes only in places that do not break the consistency of this graph (cyclic dependencies and breaking of precedence dependencies are not allowed). TABLE 4. Genetic operators used in our proposed solution. The behavior of a single CBM-pop agent is described in Algorithm 1. Before starting the algorithm, the agents exchange their specific problem parameters – task durations σir , setup times tijr , setup costs cijr , energy demands qir , and energy capacities Qr. During the runtime of the algorithm, the best solutions found and the weight matrices are exchanged among the agents, as noted in Algorithm 1. The procedure itself consists of Diversification-Intensification cycles (D-I cycles), where a diversification operator is first applied to the solution to guide the search out of the local optimum. After this perturbation, a series of local search procedures are applied to the solution to arrive at a new (local) optimum. The process is repeated until a termination criterion is reached. Further details on the definition of states, experience updates and learning mechanisms can originally be found in [3]. As mentioned, another novelty introduced here is that an agent stores a population of solutions instead of just one solution. The idea is to diversify the search further and allow for broader exploration. The role of the population is a dual one. First, after each n_cycles cycles without improvement over the best solution found, a new starting solution is randomly selected from the population. Second, solutions from the population participate as a second parent in the crossover operator, thereby introducing novelty from the genetic pool. VI. EVALUATION AND DISCUSSION The assessment involves large-scale testing on randomly generated task planning problems with precedence constraints and transitional dependencies [4]. Additionally, we apply the evaluation in a practical setting, specifically routing mobile 74334 VOLUME 12, 2024 B. Arbanas Ferreira et al.: Distributed Allocation and Scheduling of Tasks With Cross-Schedule Dependencies Algorithm 1 Population-Based CBM Algorithm (CBM-Pop) input : pop_size – number of solutions in population input : η– reinforcement learning factors input : ρ– mimetism rate input : n_cycles – number of cycles before changing exploration origin input : ϵ– minimal solution improvement variable: cbest ag – best solution found by the agent output : cbest coalition – best found solution /*initialization */ P←generate_population(pop_size) evaluate_population(P) ccurrent ←select_solution(P) W←init_weight_matrix() H←init_experience_memory() while stopping criterion is not reached do /*calculate current state */ s←perceive_state(H) if no change in best solution > ϵ for n_cycles cycles then evaluate_population(P) ccurrent ←select_solution(P) end o←choose_operator(W,s) cnew ←apply_op(o,ccurrent ,P, [cbest coalition]) /*update experience history */ gain ←f(ccurrent )−f(cnew) update_experience(H,s,o,gain)/*update solutions */ if cbest coalition improved then broadcast_solution(cnew) end /*learning mechanisms */ if end of D-I cycle then if cbest coalition improved in the cycle then W←individual_learning(W,H,η) else if cbest ag improved in the cycle then W←individual_learning(W,H,η) broadcast_weight_matrix(W) end end if weight matrix received from a neighbor then W←mimetism_learning(W,Wreceived ,ρ) end end robots in a greenhouse scenario. Our focus lies on evaluating optimality, computational speed, and scalability. The proposed solution is implemented in the Robot Operating System (ROS) [31] environment to enable vehicle-in- the-loop development of planning algorithms. This facilitates the rapid transition from the simulated environment to a real-world experiment. ROS also provides the underlying communication infrastructure through its message and service protocols. All simulations were run on Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz x 8, 32 GB RAM running Ubuntu 18.04 LTS operating system. One of the important factors affecting the algorithm performance is the selection and tuning of the parameters. In this paper, we define the parameters empirically, following some common practices in evolutionary computing. First, the population size defines the diversity of the algorithm’s solution pool. While a large diversity is good, larger populations lead to slower algorithm convergence. This parameter should be set considering the known properties of the problem to be solved. In our simulations, we set the pop_size to 50. Next, the reinforcement learning factors ηdefine the learning rate applied to the weight matrix after finding the best agent (coalition) solution. We set this parameter to [0,5,1], which determines a 50% larger weight increase for the case where the best coalition solution has improved compared to the only locally best solution. The mimetism rate ρ, which determines the rate of an agent’s mimetic behavior, is set to 0.3, where an agent mimics another agent’s weight matrix by 30% and retains 70% of its own learned behavior. Finally, the termination parameters n_cycles and ϵare set specifically for each of the application scenarios. A typical value for n_cycles would be no less than 10000 to obtain high-quality solutions, while ϵrepresents the smallest allowable improvement in the solution and we used the value of 0.01 to run the algorithm as long as there is progress. In Appendix B, we conduct a comparative analysis between the proposed population-based CBM and the original single-solution version of the CBM algorithm. A. COMPARATIVE ANALYSIS ON TASKS WITH CROSS-SCHEDULE PRECEDENCE CONSTRAINTS Despite the considerable complexity of benchmark problems available in the VRP literature, they do not include some important elements of the problem that our approach solves, namely cross-schedule dependencies. Therefore, we have developed a separate set of benchmark examples to evaluate problems with precedence constraints. The problems are solved for a team of two and eight robots. The problem instances include 4, 8, 16, 32, 64, 128, 256, 512, and 1024 tasks, and we generated 50 randomized examples for each setting. In each example, 20% of the tasks are precedence-constrained. Task durations and costs are generated using assumed robot characteristics (speed, energy requirements). Setup times and costs are calculated using the above-mentioned agent properties and the Euclidean distance between tasks associated with random positions in 3D space. The full benchmark set and results can be found at [4]. In analyzing the results, we compare the proposed distributed metaheuristic CBM-pop with an exact MILP-based solution provided by the Gurobi solver [5] and a state-of- the-art distributed auction-based algorithm presented in [6]. We opted for the Gurobi optimizer because of its precise VOLUME 12, 2024 74335 B. Arbanas Ferreira et al.: Distributed Allocation and Scheduling of Tasks With Cross-Schedule Dependencies BARBARA ARBANAS FERREIRA (Member, IEEE) received the Ph.D. degree from the Faculty of Electrical Engineering and Computing (FER), University of Zagreb (UNIZG), in February 2022, focusing on the decentralized coordination of heterogeneous multi-robot systems under the co-supervision of Prof. Stjepan Bogdan and Prof. Martínez-de Dios. She is currently a Postdoctoral Researcher with the Laboratory for Underwater Systems and Technologies (LABUST), UNIZG-FER. To date, she has authored or coauthored one book chapter, six journal articles, and nine conference papers. Her research interests include multi-robot coordination and planning, distributed artificial intelligence, scheduling, and optimization. She has been involved in several international and national research projects, including H2020 project subCULTron, FP7 EuRoC, and the Croatian Science Foundation project SPECULARIA. She also participated in the ERL Emergency Robots 2019 and MBZIRC 2020 Robotics Competitions as a member of the LARICS Team. She is currently working on the Horizon Europe project SeaTecHub and was the Team Leader of UNIZG-FER, which won the MBZIRC 2023 Competition. TAMARA PETROVIĆ (Member, IEEE) is currently an Assistant Professor with the Laboratory for Robotics and Intelligent Control Systems (LARICS), Faculty of Electrical Engineering and Computing, University of Zagreb. She has published two book chapters, six journal articles, 17 conference papers, and participates as a reviewer in several international scientific journals and conferences. Her scientific and research interests include multi-robot systems and discrete event systems. In 2016 and 2017, she was the Faculty Erasmus Coordinator in traineeships and control engineering and automation students’ mobility. She was the Vice President (2012–2013) and the President (2014–2015) of the Croatian Section of the IEEE Society for Robotics and Automation. MATKO ORSAG (Member, IEEE) is currently an Associate Professor with the Faculty of Electrical Engineering and Computing (FER), University of Zagreb (UNIZG). In 2011 and 2012, he was a Visiting Researcher with Drexel University, Philadelphia, USA, as a recipient of the Fulbright exchange grant. Currently, he is a Researcher in several EU projects: AeRoTwin, ENCORE, RoboCom, and NATO project MORUS. He is the PI of SPECULARIA and H2020 ENDORSE Project. He has authored or coauthored 30 scientific and professional articles, a monograph, and a book chapter on unmanned aerial systems and robotics. He is an Associate Editor of Automatika journal. He is currently the Co-Chair of the Croatian Section of IEEE RAS. J. RAMIRO MARTÍNEZ-DE DIOS (Member, IEEE) is currently a Full Professor with the University of Seville. His research and development activities are focused on aerial robot perception, multi-robot cooperation, robot localization and mapping, and sensor fusion. He has authored or coauthored >130 publications. He has coordinated >14 research and development projects and participated in other >60 research and development projects, including >18 projects funded by the European Commission in FPIV, FPV, FPVI, FP6, and H2020. He led and participated in >12 technology transfer actions to companies, such as AIRBUS, BR&TE, or IBERDROLA. He is a member of the editorial board of >seven journals, an Associate Editor of IEEE RA-L, and has been a TPC member in >60 conferences and workshops. He was a recipient or co-recipient of five international awards. STJEPAN BOGDAN (Senior Member, IEEE) is currently a Full Professor with the Laboratory for Robotics and Intelligent Control Systems (LARICS), Faculty of Electrical Engineering and Computing, University of Zagreb. He is the coauthor of four books and has published more than 200 conferences and journal articles. He was the Principal Investigator and a Researcher on 30 national and international scientific projects. His research interests include autonomous systems, aerial robotics, multi-agent systems, intelligent control systems, bio-inspired systems, and discrete event systems. He serves as an associate editor for several scientific journals and conferences and was a program and organizing committee member of major control and robotics conferences. 74342 VOLUME 12, 2024