On-line task allocation for multi-robot teams under dynamic scenarios

Abstract

Multi-Robot Task Allocation (MRTA) is a complex problem domain with the majority of problem representations categorized as NP-hard. Existing solution approaches handling dynamic MRTA scenarios do not consider the problem structure changes as a possible system dynamic. RoSTAM (Robust and Self-adaptive Task Allocation for Multi-robot teams) presents a novel approach to handle a variety of MRTA problem representations without any alterations to the task allocation framework. RoSTAM’s capabilities against a range of MRTA problem distributions have already been established. This paper further validates RoSTAM’s performance against the more conventional dynamics, such as robot failure and new task arrival, while performing allocations against two of the most frequently faced problem representations. The framework’s performance is evaluated against a state-of-the-art online auction scheme. The results validate RoSTAM’s capability to allocate tasks across a range of dynamics efficiently.

Keywords

Computational intelligence evolutionary algorithm multi-robot task allocation scheduling multi-robot systems multi-agent systems

1. Introduction

Multi-Robot Task Allocation (MRTA) as a paradigm deals with the efficient allocation of tasks to a team of robots for the successful completion of the mission on hand. Taxonomies classifying different MRTA problem distributions identify the majority of them as NP-hard and structurally distant from one another [1, 2]. The three axes based taxonomy presented in [1] represents the axes using two alphabet acronyms for each axis within the distribution such as ST for Single Task vs. MT for Multi-Task robots, SR for Single Robot vs. MR for Multi-Robot tasks, and finally, IA for Instantaneous (IA) vs. TA for Time extended Allocations. Individual problem distributions identified by the taxonomy are represented as combinations of these acronyms, such as ST-SR-TA where Single Task capable robots attempt Single Robot tasks in a Time extended Allocation manner. In this paper, these MRTA problem structures are referred to as problem distributions.

Many of the real-world multi-robot settings observe a significant amount of dynamics during operation. Conventionally, task allocation schemes are designed for static problem setups, where environmental variables such as team configuration and task requirements do not change throughout execution. Schemes designed for such static setups suffer against any dynamics within the system [3, 4]. Online planning methods adjust to environmental changes by reformulating their plans whenever necessary [3, 4, 5]. However, these online schemes are designed for situations where the environmental dynamics do not alter the underlying problem distribution. Changes in the underlying problem distribution can make the task allocation scheme completely inapplicable to the new scenario. Taking a firefighting situation as an example, the changes encountered can simply be due to fire expansion, needing more than one unmanned firefighting vehicle for task completion. Expanding an SR task to an MR task, hence changing the ST-SR-TA problem distribution to an ST-MR-TA distribution. It must be highlighted that these problem distributions can be mathematically and/or structurally distinct from one another [6]. This can render the task allocation scheme inapplicable to the changed scenario if it does not hold the capacity to handle the new problem distribution.

The aim behind RoSTAM (Robust and Self-adaptive Task Allocation for Multi-robot Teams) is to present a unified task allocation framework for quality task allocations across a variety of MRTA problem distribution and environmental dynamics. RoSTAM uses a metaheuristic-based design to achieve this task. Meta-heuristics such as Evolutionary Algorithms (EAs) have been used in the past for flexible solutions capable of solving a variety of problems [7] or variants of a single complex problem [8]. Furthermore, EAs have been used to provide solutions to dynamic problems [9, 10, 11], even in the MRTA domain [12]. However, there is a lack of solutions in the MRTA literature capable of making quality allocations across a variety of problem distributions.

This paper validates the adaptive capabilities of RoSTAM against a variety of changes in the environment across two of the most frequently faced MRTA problem distributions, namely the ST-SR-TA and the ST-MR-TA. An earlier study [6] has already demonstrated RoSTAM’s capability to work across a variety of MRTA problem distributions. However, RoSTAM’s capability to handle more conventional environmental changes, such as robot failure and new task arrival, has not been explored in depth. RoSTAM’s performance in this paper is benchmarked against a state-of-the-art online auction scheme inspired by [3, 5, 13]. RoSTAM exhibits better performance in all cases. It is worth noting that the enhanced performance is achieved without any fine-tuning of case-specific parameters generally required by meta-heuristics [14].

The rest of the paper is organized as follows. Section 2 reviews the existing literature and identifies the contributions made by this research. Section 3 provides the mathematical formulation of the problem on hand. Section 4 presents RoSTAM, whereas Section 5 provides the details of the online auction scheme used for benchmarking. Sections 6 and 7 discuss the experimental design used for the evaluation and the results of the experiments, respectively. Finally, Section 8 concludes the paper along with the future research directions.

2. Literature review

Task allocation strategies handling dynamic situations, such as new task arrivals and robot failures, use exact or approximate solution approaches for online planning. Exact mathematical solution approaches such as Integer Programming (IP) are favored due to high solution quality [15, 16]. A robust solution using IP for closed-loop discrete resource allocation problems has been proposed [17]. However, the heavy computational requirement of the multi-robot task allocation problem means that these approaches become impractical for even medium-sized problems [18] or unpredictable environments [16]. Furthermore, for exact solution approaches, certain mathematical preconditions must be satisfied, and each problem distribution has to be appropriately formulated before the allocations are performed. Hence, complicating the transition between MRTA problem distributions especially for online operations. To cater to these difficulties, approximate, heuristic, and meta-heuristic schemes are often utilized.

Within the heuristic approaches, auction/market-based schemes are the most popular choice for such dynamic systems [16, 19, 20]. Auctions take their inspiration from human auctions [21, 22], where bids are invited for all the available tasks. Any robot willing to attempt a particular task submits its bid based on the cost it is expected to incur while executing that task. Winning bids for each task are identified by the auctioneer and tasks are allocated to the best bid for each task.

In dynamic scenarios, auction-based schemes are initialized by computing a feasible task allocation plan. For any changes in the environment, the plans are recomputed by (a) rescheduling the already allocated tasks and allowing bidding for any newly arriving tasks [3, 5, 16] or (b) reallocating all the tasks from scratch [23]. Despite their wide acceptance, variations in solution quality have been observed for different auction-based schemes against simple environmental variations [24, 25]. These variations include, but are not restricted to, robot starting locations and task distribution within the environment [24, 25]. Hybrid techniques have been developed to cater to these challenges [24, 25]. However, these hybrid techniques need to train portfolio-based algorithm selection mechanisms to enable the selection of a suitable task allocation scheme from a variety of existing task allocation strategies.

Meta-heuristics are also popular task allocation schemes in MRTA due to their low mathematical requirements for problem formulation [26], close to optimal results, better scalability, and low time requirements [27]. Meta-heuristics, including Particle Swarm Optimization [28], Ant Colony Optimization [29], Genetic Algorithm (GA) [27], and Evolutionary Algorithm (EA) [11, 30] have often been utilized for efficient multi-robot task allocation. It must be highlighted that EAs, by and large, are considered similar to GAs except that EAs have phenotype representation of chromosomes, whereas GAs have genotype representation.

EAs are a popular choice when designing meta-heuristic based MRTA schemes. However, EA-based solutions for IA distributions [31] do not cater to the dynamics present in the environment. EA-based schemes handling TA allocations either explicitly consider a static environment [32] or make simplistic assumptions. One such frequently considered simplification is the total resource requirement of any dynamically arriving tasks always being less than the available robots in the team [33]. A unique GA-based solution is proposed for target allocation to unmanned aerial vehicles in dynamic environments [11]. However, the scheme works as an active planner against situations where fuzzy cost evaluations can be made for the uncertainties that exist in the environment. Later, task allocations are made utilizing those fuzzy evaluations.

This research analyzes the online capabilities of an existing EA-based task allocation framework named RoSTAM. The paper analyzes RoSTAM’s capability to handle a variety of environmental dynamics, including new task arrival, task expansions, robot failure, and changes in problem distribution during execution. All this is achieved against two of the most frequently faced MRTA problem distributions without allowing RoSTAM to make any structural changes throughout its operations. To the best of our knowledge, there is no existing online, meta-heuristic MRTA framework capable of adjusting to environmental changes and having the flexibility to work against a variety of problem distributions.

The paper builds upon earlier contributions made in the direction of formulating a unified framework for efficiently allocating tasks across multiple MRTA problem distributions [6]. The capability to seamlessly transition across multiple MRTA problem distributions has already been established in [6]. However, the findings in [6] are presented through a single case study and a comprehensive analysis of more conventional environmental variations was missing. Also, no comparisons were made against existing schemes. Within static setups, the capabilities of RoSTAM have also been tested against an exact task allocation scheme for the ST-SR-TA distribution [30] and against a GA and an auction-based scheme in [34] for the ST-SR-TA and ST-MR-TA problem distributions. Both of these analyses [30, 34] are performed against loosely coupled MR tasks. Being MR tasks, loosely coupled tasks do require services from multiple robots for completion. However, simultaneous execution from all the robots for task completion is not required. The framework has also been tested and its performance has been benchmarked against an auction-based scheme for tightly coupled ST-MR-TA operations [35]. Tightly coupled task instances, unlike loosely coupled MR tasks, require simultaneous execution from multiple robots for task completion. An enhancement of the framework for IA-based problem distributions was reported in [36] and the performance was compared against exact and heuristic solutions. It must be stated that throughout these analyses, heuristic-based auction schemes were found to be potentially the best existing scheme for comparison across multiple problem distributions due to their acceptable performance in all the test cases.

3. Problem formulation

Suppose there are $m$ identified tasks $T={\{}t_{1},t_{2},\ldots\ldots,t_{m}{\}}$ which needs to be visited by a team of $n$ robots $R={\{}r_{1},r_{2},\ldots r_{n}{\}}$ . The objective is to find an ordered allocation of tasks ${f:R\to T}$ based on some performance metric ${P:R\times T\to{\mathbb{R}}+}$ , such that all tasks $t_{i}\in T$ are allocated to a robot $r\in R$ while ensuring efficient completion of the overall operation. A task $t_{i}$ is represented as a tuple such that $t_{i}{={\{}(x}_{i},y_{i},q_{i}):x_{i},y_{i},q_{i}{\in N{\}}}$ , where $x_{i}$ and $y_{i}$ are the task coordinates, and $q_{i}$ gives the number of robots required by the task. This problem is an ST-SR-TA type if $m>n$ and ${(\forall t}_{i}\in T:q_{i}=1)$ and an ST-MR-TA type if $m>n$ , and ${(\exists t}_{i}\in T:q_{i}>1)$ . Based on the robot requirements of the tasks, qi, separate occurrences of each task are created. These task occurrences are referred to as task instances in the rest of the paper. Hence for any SR task having $q_{i}=1$ , 1 task instance is created within $T$ ; ensuring the allocation of a single robot to that task (ST-SR-TA). Whereas for another arbitrary MR task having $q_{i}=3$ , 3 task instances are created within $T$ ensuring the allocation of 3 robots to the task for completion (ST-MR-TA). For time-extended allocations (TA) the execution schedule for any robot $r$ is given by $S^{r}=\left\{{t_{1}^{r},t_{2}^{r},t_{3}^{r},t_{4}^{r}\ldots\ldots,t_{m\left(r% \right)}^{r}}\right\}$ .

Hence, if $S^{r}=\left\{{t_{1}^{r},t_{2}^{r},t_{3}^{r},t_{4}^{r}\ldots\ldots,t_{m\left(r% \right)}^{r}}\right\}$ then robot $r$ is responsible for executing task instances $t_{1}^{r},t_{2}^{r},t_{3}^{r}$ , up to $t_{m\left(r\right)}^{r}$ in the given order. A symmetric, non-negative function $D\left({t_{i},t_{j}}\right)$ denotes the time a robot takes to travel from the task $t_{i}$ to task $t_{j}$ , where $D\left({t_{i},t_{j}}\right)=D\left({t_{j},t_{i}}\right)$ . Furthermore, for a depot based execution, two time instances $D\left({t_{0},t_{1}^{r}}\right)$ and $D\left({t_{m\left(r\right)}^{r},t_{0}}\right)$ , marking robot $r$ ’s commute from depot $t_{0}$ to its first and from its last task back to the depot $t_{0}$ respectively are added to the robot’s schedule. Using all these measures, the tour cost for robot $r$ marking the time it takes to accomplish its allocated tasks is computed using Eq (1).

$\displaystyle\textit{Tour}_{r}=D\left({t_{0},t_{1}^{r}}\right)+D\left({t_{m% \left(r\right)}^{r},t_{0}}\right)+\mathop{\sum}\limits_{k=2}^{m\left(r\right)}% D\left({t_{k-1}^{r},t_{k}^{r}}\right)$ (1)

Where:

•

$D\left({t_{0},t_{1}^{r}}\right)$ gives the time requirement of the robot $r$ to commute from the depot to its first task.

•

$D\left({t_{m\left(r\right)}^{r},t_{0}}\right)$ gives the time requirement of robot $r$ to commute from its last task back to the depot.

•

$\mathop{\sum}\limits_{k=2}^{m\left(r\right)}D\left({t_{k-1}^{r},t_{k}^{r}}\right)$ gives the total time requirement of executing tasks from task 1 till the last task $m(r)$ for the robot $r$ .

•

$t_{1}^{r},\{t_{k}^{r}\}_{k=2}^{m\left(r\right)}\in S^{r}$

The schedule $S$ for the team is denoted as a set of individual schedules for each robot present in the team $S=\left\{{S^{r}}\right\}_{r=1}^{n}$ . The overall solution quality is then evaluated using the maximum time taken by any robot in the team as the total team time for the operation. The overall operation time for the team can be evaluated using Eq. (2). The same equation is used to evaluate the quality of different solutions provided by RoSTAM and the auction-based scheme.

$\displaystyle\textit{Tour}_{\textit{Timer}}\left\{{\left\{{S^{r}}\right\}_{r=1% }^{n}}\right\}={\max}_{r}\left[{D\left({t_{0},t_{1}^{r}}\right)+D\left({t_{m% \left(r\right)}^{r},t_{0}}\right)+\mathop{\sum}\limits_{k=2}^{m\left(r\right)}% D\left({t_{k-1}^{r},t_{k}^{r}}\right)}\right]$ (2)

The objective function is then to minimize the duration of the whole operation for the team by minimizing individual robot tour times as presented in Eq. (3).

$\displaystyle\textit{Objective Function}={\min}_{r}\left[{\textit{Tour}_{% \textit{Timer}}\left\{{\left\{{S^{r}}\right\}_{r=1}^{n}}\right\}}\right]$ (3)

The objective function only considers the commute times for fitness evaluation and does not consider the task execution times. This is motivated by the literature [15, 37]. A few assumptions taken in this work are given below:

•

The robots hold the execution capabilities of any task allocated to them. The framework handles efficient task allocation to the robot and does not concern task execution.

•

The robots have perfect localization and can predict the cost of travel between locations.

•

The study uses a homogeneous team of robots, thus the cost of travel between two tasks is uniform across all the robots.

•

All the tasks must be allocated the appropriate number of robots as per their requirements. Any solution failing to allocate even a single task instance is deemed infeasible.

•

Multiple instances of an MR task $(q_{i}>1)$ should not be allocated to a single robot. Each instance of such a task should be entertained by a different robot.

•

The tasks, even different instances of a single MR task, are not bounded by any precedence constraints and can be attempted in any order (loosely coupled).

4. Proposed framework

RoSTAM targets the capability to efficiently allocate tasks across two of the most frequently used MRTA problem distributions while being able to handle environmental dynamics such as robot failure and new task arrivals. This substantially enhances the autonomous ability of multi-robot teams while handling a variety of environmental dynamics. This section provides an introduction to RoSTAM and its functional components. The components adopted from previous works [6, 30, 34, 35, 36] are presented briefly, while any features introduced into the framework for handling or supporting dynamic changes in the environment are explained in more detail.

4.1 EA design

RoSTAM employs an EA to allocate tasks among the robots. The EA utilizes a two-part chromosome structure for solution representation. A valid permutation of task IDs against the existing task instances is presented within the first part of the chromosome. Genes within this part of the chromosome use a decimal point notation to represent each task instance with a unique task ID. The second part of the chromosome hosts a count of individual robot allocations from within the permutation of tasks present in the first part of the chromosome.

Figure 1.

RoSTAM’s two-part chromosome design.

The decimal notation-based gene values in the first part of the chromosome allow for the representation of both SR and MR tasks. A candidate solution is presented in Fig. 1 for easier reference. In Fig. 1 all task IDs having only X.1 representations, such as 1.1 and 6.1, are Single Robot (SR) tasks. Tasks having IDs of X.1 and more, such as 3.1, 3.2, and 3.3, are Multi-Robot (MR) tasks. RoSTAM creates multiple instances of an MR task against the multi-robot requirement of that task. Individual robot tours for each robot can be identified through the whole numbers present in the second part of the two-part chromosome representation. Thus, for Fig. 1, robot 1 attempts the first two tasks, robot 2 executes the next seven tasks, whereas robot 3 attempts the last three tasks from the permutation.

Figure 2.

Pseudocode for RoSTAM and the basic structure of the EA used.

The first part of the chromosome encapsulating a permutation of all the tasks uses an Ordered Crossover (ORX) [38], whereas no crossovers are used for the second part of the chromosome. Inverse and Swap mutations are also randomly utilized for the first part of the chromosome. In contrast, Creep mutation is applied to the 2nd part of the chromosome. A detailed explanation of the chromosome design, along with crossover and mutation operators, is provided in [34] and must be consulted if required. Individual robot times are computed using a pre-computed cost matrix and Eq. (1). The overall fitness of the solution is then computed using Eq. (2). Figure 2 provides an overview of the organization of RoSTAM and the structure of the EA. The additional components introduced to handle dynamic changes in the environment, namely, population diversity, adaptive penalty function, and online plan reformulation are discussed next.

4.1.1 Online plan reformulation

Figure 3.

Pseudocode for Plan reformulation routine, responsible for adjusting the previous archived population as per the changes in the environment.

Dynamic EAs usually adapt individuals from the previous population to the new solution space when changes in the environment are discovered [10]. RoSTAM, on the completion of every task allocation cycle, saves the last population of solutions to be used as a seed value in case any reallocations are to be made. In the case of a re-initiation against a change in the environment, the archived population of solutions is pre-processed before being used as a seed. Figure 3 provides the pseudocode for the plan reformulation routine used by RoSTAM. A complete list of the pre-processing possibilities includes:

•

Removing and appropriately recording each robot’s attempted tasks from the population of solutions archived from RoSTAM’s last run.

•

Withdrawing any failed robots from the solution pool and submitting their allocated, unattempted tasks to the unallocated tasks pool.

•

Inserting any newly generated instances of the expanded tasks or any newly discovered tasks into the unallocated task pool.

•

Incorporating any robot reinforcements into the solution representation.

As shown in Fig. 2, the re-initiations are handled as a conventional run of the task allocation routine. The only alteration is the use of a seed value for population initialization during any reallocations. Also, these re-initiations are not considered isolated events within the planning operation. Instead, the record of the already executed tasks by each robot is placed within each robot’s archive. This helps appropriately evaluate and penalize any future allocations made to the robots.

4.1.2 Adaptive penalty function

A candidate ST-MR-TA solution where multiple instances of an MR task are assigned to a single robot is penalized using an adaptive penalty function. The adaptive penalty function is utilized to allow RoSTAM to adjust to a large range of problem distributions and environmental scenarios. The adaptive penalty function initiates with a fixed value and adjusts its value in every generation as per the following conditions:

If the best solution from each of the previous 10 generations were:

•
All infeasible solutions, the penalty value is increased by 15% to drive the search towards the feasible regions.
•
All feasible solutions, the penalty value is reduced by 15% to allow infeasible solutions a higher chance of survival.
•
Had a mix of feasible and infeasible solutions, then the penalty value remained unaltered.

Figure 4.
Pseudocode for the adaptive penalty function used by RoSTAM.

An adaptive penalty function supports RoSTAM towards its flexible behavior. It allows RoSTAM more flexibility to explore the feasible-infeasible boundaries within the solution space for any of the possible scenarios faced by the framework. Figure 4 provides the working flow of the adaptive penalty function used by RoSTAM.
4.2 Population diversity

Being an EA based task allocation framework, RoSTAM utilizes a population of solutions for exploring the solution landscape. As an intrinsic ability, EAs are designed to converge towards a single “fitter” solution [39]. This allows EAs to converge to potentially good solutions in the solution landscape. However, RoSTAM uses its population of solutions not only for extracting promising solutions but also for solution space profiling [26, 39]. This profiling helps RoSTAM make an informed start, in case of a rerun against potential changes. For online EAs, it becomes hard to come out of this single convergence point if the solution landscape experiences any changes and the previous population is used as a seed value for re-initiation [10]. In such implementations, population diversity measures are put in place to allow faster adaptation toward changes in the solution space [10]. Furthermore, adaptive EAs have the drawback of falling for locally optimum solutions in a complex solution space landscape [11].

To cater to these limitations in RoSTAM, an Artificial Immune System (AIS) [40] inspired mechanism similar to [11] is used to keep the population diversity alive. To reduce the possibility of converging to a local optimum and to ensure a healthy solution space profiling for any future re-initiations of the framework against environmental dynamics, 20% randomly generated new solutions are injected into the population in every generation to maintain population diversity. These new solutions randomly replace any existing solutions from within the population. It is ensured that the best solution from the existing generation is not replaced during this operation. In this manner, the framework is allowed the possibility of converging to good regions within the landscape using 80% of its population while the 20% newly injected solutions work towards keeping the population diversity alive.

It must be stated that all of the hyperparameters used for RoSTAM such as the introduction of 20% new solutions for population diversity, increment or decrement of 15% penalty value every 10 generations for adaptive penalty function, or on a broader level, use of specific penalty, crossover, and mutation operators to be used, have been reached through comprehensive preliminary experimentation.

5. Validation schemes

This section provides background information about the task allocation scheme implemented to validate RoSTAM’s performance against dynamic scenarios. RoSTAM is tested under a range of changes such as robot failure, new task arrival, task expansions, and possible problem distribution changes. Its performance across these dynamics is evaluated using a state-of-the-art auction scheme. The results validate RoSTAM’s capability to efficiently allocate tasks across a range of dynamics.

The majority of the online task allocation schemes in the MRTA literature use auction-based allocation mechanisms. Variants of Sequential auctions are usually preferred for such online allocations [3, 4, 5, 13, 23]. Sequential Single Item (SSI) auctions allocate one task per round against the lowest bid submitted; hence, undergoing $m$ auction rounds for $m$ tasks [21]. SSI is known to provide solutions in polynomial time, does not require identification of synergies amongst tasks before allocations, and provides proven optimality bounds in a completely known environment [21]. Also, dynamic implementations of SSI, in certain conditions, provide even better allocation than their static variants [13]. Finally, SSI auctions are found to be the best-performing auction scheme in both static and dynamic situations for both simulated and real-world environments when a distance-based optimization function is used [22].

Figure 5.

Visualization of SSI auction (a) Complete allocation, (b) Partial allocation and bid computation (cheapest insertion heuristic).

Pertaining to the aforementioned characteristics of auction mechanisms, an auction scheme inspired by [3, 5, 9] is implemented for validation against RoSTAM. The implemented auction scheme evaluates bids through Sequential Auctions for task allocations. Figure 5(a) provides an illustration of how SSI works for a four task, two robot scenario. The tasks are represented as $T_{1}$ , $T_{2}$ , $T_{3}$ , and $T_{4}$ whereas the two robots are marked as $R_{1}$ and $R_{2}$ . Initially, bids are received from all robots against all available tasks. Upon startup (first round) $R_{1}$ wins $T_{1}$ by presenting the lowest bid in the round among all the submitted bids. In the next round, $R_{1}$ wins $T_{2}$ by providing another lowest bid. Bid computation is based on the cheapest insertion heuristic. Hence, for the $T_{2}-R_{1}$ bid computation, robot $R_{1}$ considers attempting $T_{2}$ from both its starting location and after attempting $T_{1}$ . Figure 5(b) provides a visual depiction of this scenario where new bids are being computed after the allocation of task $T_{1}$ to robot $R_{1}$ . The computed bids are represented through dotted arrows, whereas the unallocated tasks are represented through dotted boxes. After the allocation of $T_{2}$ , $R_{1}$ wins task $T_{3}$ as it provides another lowest bid from the remaining tasks. Finally, $R_{2}$ wins $T_{2}$ as its bid for attempting the task is lower than $R_{1}^{\prime}s$ bid for executing it from any of its already allocated tasks or its starting location.

A more formal representation of the auction mechanism can be presented by considering $T^{\prime}$ to be the set of all unallocated tasks. Initially $T^{\prime}$ encapsulates all the tasks present in the environment. Next, let $\textit{\v{T}}\left(r\right)$ represent the set of tasks allocated to a robot $r$ and $P\left({r,\left(\textit{\v{T}}r\right)}\right)$ be the least accumulative cost of executing all the tasks within $\left(\textit{\v{T}}r\right)$ by robot $r$ . Then Eq. (4) can be used by robot $r$ to compute its bid for any unallocated task $t_{i}\in T$ .

$\displaystyle\textit{bid}\left({r,t_{i}}\right)=P\left({r,\textit{\v{T}}\left(% r\right)}\right)-P\left(r,\left(\textit{\v{T}}(r)\cup t_{i}\right)\right)$ (4)

Utilizing the cheapest insertion heuristic, robot $r$ computes its bid as the smallest change in the current execution cost of its existing schedule after adding task $t_{i}$ to the list of its already allocated tasks. In each round, all the robots submit their bids for all the unallocated tasks. However, only the task against the smallest bid is allocated to the robot submitting that bid. Hence, $n$ unallocated tasks will take $n$ auction rounds for complete allocation. This method of task allocation ensures a minimum increase in the sum of all path costs of the team $\mathop{\sum}\limits_{r\in R}P\left({r,\textit{\v{T}}\left(r\right)}\right)$ . For simplification, all the robots submit their smallest bid in each round. This reduces the number of bids received in each round while maintaining the allocation quality. For the implementation in this paper, bids are computed using the centralized pre-computed cost matrix generated by RoSTAM for its evaluation. This replicates the situations where the robots have complete information about the environment and the resource requirements of the tasks. Enhancements in the bid evaluation mechanism for distributed online variants are often tested [3, 4]. However, they are not required for a centralized implementation within a completely known environment.

Any changes in the environment trigger a global re-auction process for all the unattempted tasks. Global re-auctions are found to outperform local replanning against environmental dynamics [13]; however, they require greater computation compared to local replanning. Hence, as a benchmark, global replanning appears to be a better choice despite the computational overhead. The re-auction procedure followed against individual environmental changes is as follows:

•

Failed robots do not participate in the re-auction process.

•

The re-auction process is initiated for new robots, robot failure, new tasks entering the system, or any existing task expanding and demanding more resources (MR task).

•

Any expanding MR task is re-auctioned with all other unattempted tasks. However, robots that have already attempted previous instances of the MR task do not participate in the bidding process of the newly generated instances.

It must be reiterated that an in-depth analysis of RoSTAM’s performance across a variety of problem distributions in static setups has already been performed against exact, heuristic, and meta-heuristic schemes [6, 30, 34, 35, 36]. The auction-based scheme was found to be the most appropriate choice as a generic task allocation strategy and is used as a validation scheme for online operations.

6. Experimental design

This section describes the experiments conducted to test RoSTAM’s capability against a variety of environmental changes. The environmental changes were introduced for two of the most frequently faced MRTA task distributions, namely ST-SR-TA and ST-MR-TA. It is worth mentioning that IA-based executions do not face the challenge of plan readjustments and hence were not part of the experiments. RoSTAM’s performance was evaluated against a state-of-the-art auction mechanism. Different scenarios were developed to test situations such as robot failure, team expansion, robot re-initiation, task expansion, and new task introduction.

The evaluations were done against a range of problem sizes comprising 10, 15, 20, 25, 30, 35, 40, 45, and 50 tasks, with three random instances generated for each situation. Due to the stochastic nature of RoSTAM, its results were averaged over five runs for each instance. For example, for the 10 tasks case, three problem sets are randomly generated. These problem sets are referred to as problem sets a, b, and c. For each of these 3 problem sets, RoSTAM was made to allocate tasks five times to observe an average behavior. Thus, for the 10 tasks count a total of 15 runs (3 problem sets times 5 runs for each set) were performed to observe the average response of RoSTAM. On the other hand, the online auction scheme is run only once for each problem set a, b, and c due to its deterministic nature. The average of these three runs is reported as its performance for the 10 task cases. The experiments for the other task counts (15, 20, 25, 30, 35, 40, 45, and 50) are reported similarly.

Team sizes vary from 2–7 robots for different experiments. In terms of task requirements, any SR task demanded services from a single robot. However, the MR tasks demand 2–4 robots for completion, thus, creating multiple instances for a single task. This expands a problem size beyond its original task count. For example, one of the 50 task ST-MR cases summed up to a total of 137 task instances.

Table 1
Experiment summary

Exp.#	Distribution	Changes introduced	Robot count	Task count
1.	ST-SR-TA	NIL	3	10–50
	ST-MR-TA		5	10–50 (MR)
2.	ST-SR-TA	Partial & complete robot failure	2–3	10–50
	ST-MR-TA		4–6	10–50 (MR)
3.	ST-SR-TA	Partial & complete robot failure with team expansion	3–4	10–50
	ST-MR-TA		5–7	10–50 (MR)
4.	ST-SR-TA	New tasks	3	30–50
	ST-MR-TA	New tasks & task expansion (MR)	6	30–50 (MR)
5.	ST-SR-TA	Team expansion, robot failure, & new task arrival	3–4	30–50
	ST-MR-TA	Team expansion, robot failure, new task arrival & expansion (MR)	5–7	30–50 (MR)

A summary of different experiments is provided below while a more detailed description is given in Table 1.

•

Experiment 1 – Static environment: All the tasks are known upfront with no dynamics present.

•

Experiment 2 – Robot Failure: The team undergoes partial or complete robot failures during operation.

•

Experiment 3 – Team Expansion and Failure: The team undergoes expansion along with partial or complete robot failures during operation.

•

Experiment 4 – Dynamic Task Arrival: New task arrivals or expansion of already introduced tasks.

•

Experiment 5 – Dynamic Task Arrival with Team Expansion and Robot Failure: New task arrival, task expansion, team expansion, and robot failures are encountered during operation.

For all the experiments, changes in the environment were handled in a periodic and stochastic manner. The terms are defined as follows:

•

Periodic Handling: Changes in the environment can occur at any instance but are only considered for plan inclusion during planned breaks. This depicts situations such as robot refueling or robot capacity constraints. The condition is referred to as event-based replanning in the rest of the paper.

•

Stochastic Handling: Changes are to be entertained the moment they appear in the system. This condition is referred to as time-based replanning in the remainder of the paper.

For event-based replanning, robots are considered to have a fixed capacity of handling five tasks per period. RoSTAM, in each round, has to provide a complete allocation of all the unallocated tasks present in the environment. Once the plan formulation is completed, each robot is allocated the first five tasks from its computed plan as per the fixed robot capacity. The fixed robot capacity is also referred to as window size. In some cases, a robot may be assigned less than five tasks in a period by the task allocation mechanism as allocating at least five tasks is not mandatory. The system replans against any changes introduced in the environment right after assigning these five tasks to the robots.

Figure 6.

Window based task allocation at the end of the task allocation cycle.

Figure 6 illustrates a single task allocation cycle for a 11 Task, 3 Robot solution with a 5 task window. The 11 tasks create up to 18 task instances due to some of the tasks being MR tasks. RoSTAM formulates a plan for all 18 task instances, without considering the allowed window size for each robot. Once the plan formulation is complete, allocations are then made at the end of the planning cycle as five tasks per robot from within the final formulated plan of each robot. The task windows for each robot are separately identified in Fig. 6. Any tasks that are outside the window are re-considered for allocation in the next cycle. As per Fig. 6, the last two tasks for robot 2, namely tasks 2.2 and 10.1, and the final task in the plan for robot 3, 10.2, fall outside the windows and are not allocated in the initial allocation cycle. RoSTAM will undergo replanning for these 3 tasks and then re-allocate them to the robots in the next round.

Time-based replanning also starts similarly to its event-driven counterpart. Once the initial plan formulation is completed, the robots commence operation as per the initial allocations. The changes are introduced in the environment at random time instances during execution and the scheme must replan against these changes immediately. Tasks that are already completed are not considered for future allocations.

To prove its robustness, RoSTAM’s parameters were kept constant throughout Experiments 1–5. The only exception was the population size and the number of allowed generations. Due to their simpler structure, ST-SR-TA cases had a population size of 50 chromosomes, while the number of generations was set to 1200 generations for the initial run and 1000 generations for any replanning instances. The more complex ST-MR-TA cases had a population of 100 solutions, while the number of generations was set to 2500 generations for the initial run and 2000 generations for replanning. Since the aim of the paper is to assess the impact and effectiveness of online allocations for RoSTAM, the paper did not simulate the movements of the robots involved in the exercise. Instead, the plan qualities for both RoSTAM and the online auction-based scheme were evaluated using precompiled cost matrices for each problem set against each task count. This decision is well motivated by the literature and similar evaluations are also adopted in [15, 23, 28].

7. Results

7.1 Experiment 1, static environment

Table 2
Average performance of RoSTAM and online auction for experiment 1, ST-SR-TA and ST-MR-TA distributions

Task #	ST-SR-TA			ST-MR-TA
	RoSTAM	Online auction	Difference (%)	RoSTAM	Online auction	Difference (%)
10	10.63	14.17	33.23	15.39	21.05	36.78
15	13.05	16.71	28.03	23.81	28.98	21.71
20	14.84	19.15	28.99	24.52	29.58	20.62
25	16.36	20.52	25.44	27.84	33.84	21.52
30	17.70	27.73	56.62	29.91	35.58	18.94
35	18.96	28.65	51.11	33.01	38.84	17.65
40	20.97	28.38	35.36	34.30	43.71	27.41
45	21.73	32.05	47.47	37.39	42.65	14.06
50	26.72	32.52	21.70	42.01	49.28	17.30
	Average		36.43	Average		21.77

As highlighted in Table 1, no changes were introduced into the environment for the simplest of the experiments. The team comprised three robots for the ST-SR-TA and five robots for the ST-MR-TA distribution. Being a static task allocation problem, the initial allocations provided by the allocation schemes were treated as final. Table 2 gives the average performance comparison of RoSTAM and online auction for both the ST-SR-TA and ST-MR-TA problem distributions. Being a minimization problem, the lower the performance value of an allocation scheme, the better it is. As evident from the table, RoSTAM maintained a steady behavior and observed a clear advantage over the online auction scheme for both the problem distributions.

7.2 Experiment 2, partial or complete robot failure

Table 3
Experiment 2, robot failure and reintroduction – details of changes introduced in the system (event based)

S.No.	Event	Changes introduced	Active robots
	ST-SR-TA
1.	Startup	Nil, team starts with 3 robots	3
2.	$\leqslant 5$ Tasks/robot	Robot 2 fails	2
3.	$\leqslant 5$ Tasks/robot	Robot 2 still unavailable	2
4.	$\leqslant 5$ Tasks/robot	Robot 2 available, robot 3 fails	2
5.	$\leqslant 5$ Tasks/robot	Robot 3 still unavailable	2
6.	$\leqslant 5$ Tasks/robot	Robot 3 still unavailable	2
	ST-MR-TA
S.No.	Event	Changes introduced	Active robots
1.	Startup	Nil, team starts with 6 robots	6
2.	$\leqslant 5$ Tasks/robot	Robot 4 fails	5
3.	$\leqslant 5$ Tasks/robot	Robot 4 still unavailable	5
4.	$\leqslant 5$ Tasks/robot	Robot 4 available, Robot 5 fails	5
5.	$\leqslant 5$ Tasks/robot	Robot 5 unavailable, robot 6 fails	4
6.	$\leqslant 5$ Tasks/robot	Robot 6 available, 5 still unavailable	5

Experiment 2 describes a situation where the team undergoes partial or complete robot failure during the execution of tasks. Table 3 provides the breakdown of the environmental changes introduced during the experiment. As per the window size, the changes were introduced after five tasks were allocated to each active robot from the generated plan. For example, Row 2 of Table 3 for the ST-SR-TA problem distribution describes the following situation. Robot 2 failed after the completion of the initial five tasks allocated to it. By this time, the team had executed $\leqslant$ 15 Tasks as each of the three active robots was allocated at most five tasks from the initial plan. Robot 2 did not contribute to any other task executions until Event 4 as per the table. Robot 3 also failed for the rest of the run during Event 4.

Table 4

Experiment 2, robot failure and reintroduction: Details of changes introduced in the system (time based)

	ST-SR-TA
S.No.	Time instant	Changes introduced	Active robots
1.	Startup	Nil, team starts with 3 robots	3
2.	5 mins	Robot 2 fails	2
3.	12 mins	Robot 2 still unavailable	2
4.	22 mins	Robot 2 available, robot 3 fails	2
5.	28 mins	Robot 3 still unavailable	2
6.	$\infty$	No changes	–
	ST-MR-TA
S.No.	Time instant	Changes introduced	Active robots
1.	Startup	Nil, team starts with 6 robots	6
2.	10 mins	Robot 4 fails	5
3.	20 mins	Robot 4 still unavailable	5
4.	25 mins	Robot 4 available, robot 5 fails	5
5.	35 mins	Robot 5 unavailable, robot 6 fails	4
6.	$\infty$	No changes	–

For the time-based execution of the same experiment, Table 4 provides the details of the dynamics introduced for both the problem distributions. The dynamics were introduced at different time instances mentioned as time units, such as “5 mins” in the “Time Instant” column of the table. The entries in this column are additive, meaning that a “12 mins” entry after a “5 mins” entry translates to the change happening at 12 minutes after the operation commenced, and 7 minutes after the previous change was introduced (12–5 $=$ 7). An “ $\infty$ ” entry in this column means that no further changes were introduced into the system until the termination of the operation.

For the ST-MR-TA problem distribution, the changes identified in Table 4 can now be observed as the team started with 6 robots. The initial plan formulation was executed until 10 minutes into the execution. At this point Robot 4 failed, triggering a replanning for all the unattempted tasks. 20 minutes into the operation, another replanning was triggered without any changes in the environment. 25 minutes into the plan execution, Robot 4 became available whereas Robot 5 now failed. The remaining operation follows the same observations from Table 4.

Table 5

Average performance of RoSTAM and online auction for experiment 2, ST-SR-TA distribution

Task #	Event-based			Time-based
	RoSTAM	Online auction	Difference (%)	RoSTAM	Online auction	Difference (%)
10	10.52	13.42	27.62	13.39	15.05	12.35
15	13.78	16.26	18.09	17.73	16.50	$-$ 6.91
20	18.95	19.02	0.35	19.13	19.54	2.16
25	20.86	23.12	10.84	20.63	21.55	4.46
30	23.37	24.40	4.41	21.16	21.21	0.24
35	26.09	29.24	12.05	21.51	23.98	11.47
40	27.81	34.97	25.74	25.14	26.28	4.53
45	28.04	26.52	$-$ 5.42	26.79	28.66	6.98
50	28.29	37.73	33.39	27.65	30.88	11.69
	Average		14.11	Average		5.21

The average performance of both RoSTAM and online auction for all ST-SR-TA, 10–50 tasks test cases combined, is presented in Table 5. The performance is recorded for both Event-driven and Time-based replanning. As per the table, RoSTAM was able to achieve better quality allocations and adjusted better to the dynamics compared to the online auction scheme. The online auction scheme was able to provide better allocations than RoSTAM for one instance each for the Event-Driven and Time-Based execution.

Table 6

Average performance of RoSTAM and online auction for experiment 2, ST-MR-TA distribution

Task #	Event-based			Time-based
	RoSTAM	Online auction	Difference (%)	RoSTAM	Online auction	Difference (%)
10	12.71	15.60	22.69	12.50	15.60	24.74
15	20.87	27.75	32.99	22.14	25.80	16.53
20	23.49	28.99	23.40	24.09	28.13	16.81
25	25.66	29.57	15.24	26.40	29.18	10.55
30	28.11	33.36	18.67	28.64	30.29	5.79
35	31.50	37.44	18.88	33.39	34.95	4.68
40	33.55	36.98	10.21	33.71	35.29	4.67
45	35.62	38.84	9.04	36.72	38.71	5.43
50	41.47	44.66	7.71	43.38	46.53	7.26
	Average		17.64	Average		10.71

Similar to Table 5, Table 6 provides the average performance of RoSTAM and the online auction-based scheme for the ST-MR-TA distribution with robot failure and reintroduction. The performance gap between RoSTAM and online auction for both event and time-based variants is more defined for the ST-MR-TA distribution, with RoSTAM providing better allocations throughout the operation. Furthermore, RoSTAM appears to perform more consistently with a steady increase in solution costs against increasing task count. On the contrary, the online auction scheme appears to have a more random performance response towards an increasing task count.

For the online operations (Experiment 2 to 5) performance curves of both RoSTAM and online auction are also presented. These performance curves are plotted for a single 50 task case. The individual cases a, b, and c (as discussed in Section 6) are switched randomly between graphs. Also, alterations between time-based and event-based replanning structures have been made alternatively. The single 50 task cases used for the performance curves go through the same dynamics as presented for the experiment itself. As already discussed, RoSTAM’s performance is averaged over 5 runs due to its stochastic nature. Additionally, the standard deviations are also plotted for RoSTAM along with the average performance curves. Meanwhile, the auction-based performance is plotted against a single allocation cycle due to its deterministic nature. Similar behaviors were observed between the two allocation schemes for the task counts not presented.

Figure 7.

50 Task performance curves for RoSTAM and online auction with robot failures for the ST-SR-TA distribution for event-based replanning.

Figure 7 presents the performance graph for the ST-SR-TA execution of Experiment 2. The graph is plotted for the event-based replanning against 50 tasks. The figure is accompanied by a legend summarizing the dynamics faced during the experiment. These are the same environmental dynamics that are already presented in Table 3. As per Fig. 7, the planning starts with a team of 3 robots and 50 tasks. For the first event, RoSTAM presents a substantially better plan compared to SSI auction. From within this plan, up to 5 tasks were allocated to each robot. By Event 2, robot 2 fails and cannot work on any more tasks. After replanning, RoSTAM again comes out with a better plan compared to the auction-based scheme. With the allocations of up to 5 more tasks per available robot and robot 2 still unavailable, both the schemes again undergo replanning (Event 3). By Event 4, robot 2 is available for operation, whereas robot 3 fails. Robot 3 stays unavailable until the completion of operations (Event 5). All these replanning result in RoSTAM providing better solutions compared to the auction scheme.

Figure 8.

50 Task performance curves for RoSTAM and online auction with robot failures for the ST-MR-TA distribution for time-based replanning.

Figure 8 presents a single, 50 task, performance curve for the ST-MR-TA distributions against robot failures as presented in Table 4. The graph provides results for the time-based replanning instance. Similar to Fig. 7, a legend in Fig. 8 also summarizes all the time intervals and the environmental dynamics faced during them. These legends are not provided for any future performance curves and are only provided initially for easier comprehension.

The operations for Fig. 8 initiate with a team of 6 robots planning against the 50 Multi-Robot Tasks present. 10 minutes into the operation robot 4 fails, which remains so until the fourth time interval. By time interval 4, robot 4 becomes available while robot 5 fails. 35 minutes into the plan execution Robot 6 also fails triggering another replanning. This team configuration continues until the end of operations. As evident from the performance cures, RoSTAM comes out with a better plan compared to the auction-based scheme for all the replanning instances. Furthermore, the SSI encounters drastic fluctuations in solution quality throughout its operation. RoSTAM on the other hand, provides good quality solutions with even smaller standard deviations compared to the ST-SR-TA results.

7.3 Experiment 3, team expansion and robot failure

Table 7
Experiment 3, robot addition, failure, and re-introduction, details of changes introduced in the system

	ST-SR-TA
S.No.	Time instant	Changes introduced	Active robots
1.	Startup	Nil, team starts with 3 robots	3
2.	5 mins	Team expands to 4 robots, and robot 2 fails	3
3.	12 mins	Robot 2 still unavailable	3
4.	22 mins	Robot 2 ready, Robot 3 fails	3
5.	28 mins	Robot 3 still unavailable	3
6.	$\infty$	No changes	–
	ST-MR-TA
S.No.	Time instant	Changes introduced	Active robots
1.	Startup	Nil, team starts with 5 robots	5
2.	10 mins	Expands to 7 robots	7
3.	20 mins	Robot 2 fails	6
4.	25 mins	Robot 2 still unavailable, 6 also fails	5
5.	35 mins	Robot 2 ready, 6 unavailable	6
6.	$\infty$	No changes	–

Experiment 3 is designed as a relatively more complex scenario compared to Experiment 2. In this experiment, the task allocation frameworks had to cope with team expansion and robot failures during execution. Table 7 provides the breakdown of the dynamics introduced during the experiments. Only the time-based table representations are provided in Table 7 onwards for simpler narration.

Table 8 provides the average performance of RoSTAM and online auction for the ST-SR-TA problem distribution. A comparison between RoSTAM and online auction reveals that the auction-based scheme managed to meet RoSTAM’s solution quality in only one or two task counts in both distributions combined.

Table 8

Average performance of RoSTAM and online auction for experiment 3, ST-SR-TA distribution

Task #	Event-based			Time-based
	RoSTAM	Online auction	Difference (%)	RoSTAM	Online auction	Difference (%)
10	10.58	13.43	26.89	9.96	12.20	22.55
15	13.64	16.27	19.26	13.66	16.18	18.46
20	16.26	16.37	0.69	16.37	17.37	6.07
25	16.13	20.03	24.15	17.33	18.22	5.16
30	18.33	21.61	17.93	19.00	20.42	7.47
35	19.21	25.52	32.85	19.87	22.29	12.17
40	21.18	26.61	25.62	21.42	24.71	15.35
45	21.81	23.82	9.24	22.35	22.30	$-$ 0.23
50	23.88	24.05	0.72	23.20	28.21	21.60
	Average		17.48	Average		12.06

Table 9

Average performance of RoSTAM and online auction for experiment 3, ST-MR-TA distribution

Task #	Event-based			Time-based
	RoSTAM	Online auction	Difference (%)	RoSTAM	Online auction	Difference (%)
10	15.33	18.69	21.90	13.91	13.76	$-$ 1.05
15	20.19	25.90	28.27	21.21	25.07	18.18
20	20.81	26.59	27.75	21.50	21.96	2.13
25	21.56	26.66	23.62	24.57	26.84	9.24
30	23.79	31.18	31.05	26.35	31.85	20.87
35	28.76	34.34	19.42	30.52	34.27	12.29
40	31.46	37.10	17.95	32.71	33.22	1.56
45	32.89	36.11	9.80	33.05	34.58	4.63
50	37.86	43.79	15.66	38.64	41.24	6.73
	Average		21.71	Average		8.28

Table 10

Experiment 4, task introduction and expansion, details of changes introduced in the system

	ST-SR-TA
S.No.	Time instant	Changes introduced	Revealed tasks (% of original)
1.	Startup	20–30% tasks hidden	70–80%
2.	5 mins	50% of the hidden tasks introduced	80–85%
3.	12 mins	Remaining 50% of the hidden tasks introduced	100%
4.	22 mins	No changes	100%
5.	$\infty$	No changes	100%
	ST-MR-TA
S.No.	Time instant	Changes introduced	Revealed tasks (% of original)
1.	Startup	20–30% tasks hidden	70–80%
2.	10 mins	50% of the hidden tasks introduced	80–85%
3.	20 mins	Remaining 50% of the hidden tasks introduced	100%
4.	30 mins	No changes	100%
5.	$\infty$	No changes	100%

Table 9 provides the Event and Time-based average performance comparison of the two schemes for the ST-MR-TA problem distribution for Experiment 3. RoSTAM seems to have a more comprehensive dominance in the ST-MR-TA distribution than the ST-SR-TA counterpart. Furthermore, the non-consistent increase in the task allocation cost of the online auction against increasing task counts becomes more prominent for the more complex case.

The single case performance curves for experiment 3 are presented in Figs 9 and 10 for the ST-SR-TA and ST-MR-TA distributions respectively. For both scenarios, RoSTAM appears to be the better allocation scheme. However, like Experiment 2, the performance difference seems to be more pronounced for the more complex ST-MR-TA problem distribution.

7.4 Experiment 4, dynamic task arrival and task expansion

Experiment 4 shifted the focus from team-based changes to task-based dynamics. In Experiment 4, tasks ranging from 20% to 30% of the actual task count were hidden from the planner at startup and were incrementally introduced at future intervals. For the ST-MR-TA distribution, this percentage was applied to the total number of instances present against the MR type of tasks rather than the actual task count. Also, for the ST-MR-TA distribution, these experiments also depicted task expansion, occasionally causing the tasks to change from SR to MR tasks. As an example, consider task 12 as an MR task requiring 2 robots for completion. One of its instances, for example, 12.1, is hidden from the planner initially making task 12 appear as an SR task to the planner having only one instance, namely 12.2. At a later instance, when task instance 12.1 is introduced into the environment the task expands into an MR task. The newly introduced task instance should be allocated appropriately by the task allocation framework.

Table 11
Average performance of RoSTAM and online auction for experiment 4, ST-SR-TA distribution

Task #	Event-based			Time-based
	RoSTAM	Online auction	Difference (%)	RoSTAM	Online auction	Difference (%)
30	24.32	28.16	15.77	22.86	30.49	33.35
35	26.03	26.14	0.44	24.63	30.04	21.94
40	27.65	27.60	$-$ 0.16	26.87	29.80	10.89
45	27.27	30.94	13.45	27.23	32.69	20.04
50	29.04	30.54	5.189	28.43	31.79	11.79
	Average		6.93	Average		19.60

Table 12

Average performance of RoSTAM and online auction for experiment 4, ST-MR-TA distribution

Task #	Event-based			Time-based
	RoSTAM	Online auction	Difference (%)	RoSTAM	Online auction	Difference (%)
30	29.42	33.15	12.66	32.83	35.41	7.87
35	32.35	34.03	5.17	35.09	39.79	13.36
40	34.90	37.24	6.70	38.22	43.23	13.09
45	36.05	38.80	7.63	38.59	40.85	5.85
50	39.73	42.82	7.77	44.14	51.46	16.57
	Average		7.98	Average		11.34

Figure 9.

50 Task performance curves for RoSTAM and online auction with team expansion and robot failures for the ST-SR-TA distribution for event-based replanning.

Figure 10.

50 Task performance curves for RoSTAM and online auction with team expansion and robot failures for the ST-MR-TA distribution for time-based replanning.

Table 10 provides the breakdown of the task arrivals for the experiments. These experiments were conducted for the 30–50 task cases as the smaller task counts did not allow many iterations to run before all tasks were completely allocated and executed deeming any new arrival of tasks to be handled as fresh initiation of the allocation framework.

The Event and Time-based average performance of the new task arrival experiment against the ST-SR-TA, and ST-MR-TA problem distributions are provided in Tables 11 and 12, respectively. The results identify RoSTAM as a better allocation scheme and a more consistent performer, experiencing a steady increase in allocation cost with increasing problem size. The online auction-based scheme demonstrates a more stochastic behavior than RoSTAM.

Figure 11.

50 Task performance curves for RoSTAM and online auction with 20% new tasks arrival for the ST-SR-TA distribution for time-based replanning.

Figure 12.

50 Task performance curves for RoSTAM and online auction with 30% new task arrivals for the ST-MR-TA distribution for event-based replanning.

Figures 11 and 12 present the single-case performance curves for Experiment 4. The curves are again plotted for a single 50 task case. For the ST-SR-TA distribution (Fig. 11) the curves are plotted against 20% tasks appearing as new tasks after initial allocations are complete. Whereas, for the ST-MR-TA distribution (Fig. 12) the curves are plotted with 30% tasks appearing as new tasks.

7.5 Experiment 5, task arrival and expansion with team expansion and robot failure

Table 13
Experiment 5, task introduction and expansion, robot addition, failure, and re-introduction, details of changes introduced in the system

S.No.	Time instant	Changes introduced	Active robots
	ST-SR-TA
1.	Startup	Nil, team starts with 3 robots and 20–30% tasks hidden	3
2.	5 mins	The team expands to 4 robots, and Robot 2 fails, 50% of the hidden tasks introduced	3
3.	12 mins	Robot 2 still unavailable, remaining hidden tasks introduced	3
4.	22 mins	Robot 2 available, robot 3 fails	3
5.	28 mins	Robot 3 still unavailable	3
6.	$\infty$	No change	3
	ST-MR-TA
S.No.	Time instant	Changes introduced	Active robots
1.	Startup	Nil, team starts with 5 robots and 20–30% tasks hidden	5
2.	10 mins	Expands to 7 robots, 50% of the hidden tasks introduced	7
3.	20 mins	Robot 2 fails, the remaining 50% of the hidden tasks introduced	6
4.	25 mins	Robot 2 unavailable, 6 also fails	5
5.	35 mins	Robot 2 available, 6 unavailable	6
6.	$\infty$	No change	5

Experiment 5 depicted the most complex situations where the environment underwent both team and task-based changes. A detailed breakdown of the dynamics is presented in Table 13.

Table 14

Average performance of RoSTAM and online auction for experiment 5, ST-SR-TA distribution event based

Task #	Event-based			Time-based
	RoSTAM	Online auction	Difference (%)	RoSTAM	Online auction	Difference (%)
30	21.48	22.73	5.81	18.82	22.74	20.86
35	22.52	22.76	1.08	20.63	21.09	2.26
40	24.97	26.99	8.09	21.88	23.60	7.879
45	26.31	28.86	9.60	22.07	22.08	0.01
50	26.87	27.95	4.02	24.01	26.21	9.15
	Average		5.72	Average		8.03

Table 15

Average performance of RoSTAM and online auction for experiment 5, ST-MR-TA distribution event based

Task #	Event-based			Time-based
	RoSTAM	Online auction	Difference (%)	RoSTAM	Online auction	Difference (%)
30	27.51	35.91	30.50	28.79	30.21	4.94
35	29.83	35.74	19.82	32.47	37.03	14.03
40	33.99	35.23	3.63	34.01	40.61	19.42
45	34.64	37.77	9.02	34.66	36.76	6.04
50	39.19	44.07	12.43	39.33	43.48	10.53
	Average		15.08	Average		10.99

Figure 13.

50 Task performance curves for RoSTAM and online auction with 30% new task arrivals, robot addition and failure, for the ST-SR-TA distribution for time-based replanning.

Figure 14.

50 Task performance curves for RoSTAM and online auction with 30% new task arrivals, robot addition and failure, for the ST-MR-TA distribution for time-based replanning.

For the experiment, the overall behavior for RoSTAM and online auction against the ST-SR-TA and SR-MR-TA distributions is given by Tables 14 and 15, respectively. In all the cases, RoSTAM led in performance other than 1 instance. The instance was for the 45 tasks ST-SR-TA distribution. Finally, Figs 13 and 14 provide the single case performance curves of both the schemes for Experiment 5.

Figure 15.

Comparison of average difference between RoSTAM and online auction for experiment 2 to 5 against ST-SR-TA problem distribution.

Figure 16.

Comparison of average difference between RoSTAM and online auction for experiment 2 to 5 against ST-MR-TA problem distribution.

In addition to all the individual experiment results, Figs 15 and 16 provide a comparison of the average difference computed between RoSTAM and the online auction scheme across the 4 online experiments (Experiments 2 to 5). The plots are provided for both Event and Time-based replannings. Simultaneous analysis of all the average differences across experiments provides valuable insight into RoSTAM’s capability to handle environmental dynamics using event-based and time-based replanning methods. Figure 15provides the plot for the ST-SR-TA problem distribution, whereas Fig. 16 provides the comparison for the ST-MR-TA problem distribution. It can be observed from both figures that for the experiments involving team configuration changes (Experiments 2 and 3), the event-based replanning approach seems to provide a greater performance margin between the two allocation schemes. Whereas experiments involving changes in tasks (Experiments 4 and 5), the time-based replanning approach seems to provide the greater performance gap between RoSTAM and online auction.

8. Conclusion and future directions

In conclusion, this research presents RoSTAM, a novel task allocation framework for efficiently managing multi-robot teams in dynamic environments against two of the most frequently faced MRTA problem distributions. RoSTAM’s flexible design enables it to handle diverse MRTA task distributions while allowing it to adapt to more conventional environmental changes such as robot failure, team expansion, and new task arrivals, without any structural changes to its framework. This characteristic is vitally important to ensure complete planning autonomy in dynamic working environments especially with different problem distributions being mathematically and structurally distinct from one another.

The research also explores two formats of handling environmental dynamics, namely, event-based replanning and time interval-based replanning. The exploration revealed the existence of performance variations between different replanning techniques and different environmental dynamics. Comparative analysis against the online auction scheme validates all of the initial assumptions made about the framework.

Future work will focus on the parameter optimization of RoSTAM across all the problem distributions and environmental dynamics it can handle. Experiments will also be conducted to further elaborate the performance variation between event-based and time interval-based replanning. Another interesting exploration will be the use of other meta-heuristic schemes, such as Particle Swarm Optimization and Artificial Bee Colony, as an optimization tool for comparative analysis against EA design used for RoSTAM.

References

Gerkey

Matarić

. A formal analysis and taxonomy of task allocation in multi-robot systems. The International Journal of Robotics Research. 2004; 23: 939-54. doi: 10.1177/0278364904045564.

Korsah

Stentz

Dias

. A comprehensive taxonomy for multi-robot task allocation. The International Journal of Robotics Research. 2013; 32: 1495-512. doi: 10.1177/0278364913496484.

Farinelli

Iocchi

Nardi

. Distributed on-line dynamic task assignment for multi-robot patrolling. Auton Robot. 2017; 41: 1321-45. doi: 10.1007/s10514-016-9579-8.

ElGibreen

Youcef-Toumi

. Dynamic task allocation in an uncertain environment with heterogeneous multi-agents. Autonomous Robots. 2019; 1-26.

Nanjanath

Gini

. Repeated auctions for robust task execution by a robot team. Robotics and Autonomous Systems. 2010; 58: 900-9. doi: 10.1016/j.robot.2010.03.011.

Arif

Haider

. A flexible framework for diverse multi-robot task allocation scenarios including multi-tasking. ACM Transactions on Autonomous and Adaptive Systems (TAAS). 2022; 16: 1-23.

Deb

Tiwari

. Omni-optimizer: A generic evolutionary algorithm for single and multi-objective optimization. European Journal of Operational Research. 2008; 185: 1062-87.

Vidal

Crainic

Gendreau

Prins

. A unified solution framework for multi-attribute vehicle routing problems. European Journal of Operational Research. 2014; 234: 658-73.

Zhou

Liu

. A multi-agent genetic algorithm for multi-period emergency resource scheduling problems in uncertain traffic network. 2017 IEEE Congress on Evolutionary Computation (CEC). 2017; 43-50. doi: 10.1109/CEC.2017.7969294.

10.

Woldesenbet

Yen

. Dynamic evolutionary algorithm with variable relocation. IEEE Transactions on Evolutionary Computation. 2009; 13: 500-13. doi: 10.1109/TEVC.2008.2009031.

11.

Zhao

Chen

Zhen

Jiang

. Multi-weapon multi-target assignment based on hybrid genetic algorithm in uncertain environment. International Journal of Advanced Robotic Systems. 2020; 17: 1729881420905922.

12.

Beck

Teacy

Rogers

Jennings

. Online planning for collaborative search and rescue by heterogeneous robot teams. Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems, Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems. 2016; 1024-33.

13.

Heap

Pagnucco

. Repeated sequential single-cluster auctions with dynamic tasks for multi-robot task allocation with pickup and delivery. Multiagent System Technologies, Springer, Berlin, Heidelberg. 2013; 87-100. doi: 10.1007/978-3-642-40776-5_10.

14.

Toth

Vigo

. The vehicle routing problem. SIAM. 2002.

15.

Song

Kim

Morrison

. Rolling horizon path planning of an autonomous system of uavs for persistent cooperative service: Milp formulation and efficient heuristics. J Intell Robot Syst. 2016; 84: 241-58. doi: 10.1007/s10846-015-0280-5.

16.

Sariel-Talay

Balch

Erdogan

. A generic framework for distributed multirobot cooperation. J Intell Robot Syst. 2011; 63: 323-58. doi: 10.1007/s10846-011-9558-4.

17.

Zhou

Guo

Gan

Dai

. Robust control reconfiguration of resource allocation systems with Petri nets and integer programming. Automatica. 2014; 50: 915-23.

18.

Meng

Dai

. Collision-free scheduling of multi-bridge machining systems: a colored traveling salesman problem-based approach. IEEE/CAA Journal of Automatica Sinica. 2017; 5: 139-47.

19.

Botelho

Alami

. M+: a scheme for multi-robot cooperation through negotiated task allocation and achievement. IEEE International Conference on Robotics and Automation, 1999 Proceedings. 1999; 2: 1234-9. IEEE.

20.

Guidotti

Baião

Bastos

Leite

AHR

. A Murdoch-based ROS package for multi-robot task allocation. 2018 Latin American Robotic Symposium, 2018 Brazilian Symposium on Robotics (SBR) and 2018 Workshop on Robotics in Education (WRE), IEEE. 2018; 51-7.

21.

Koenig

Tovey

Lagoudakis

Markakis

Kempe

Keskinocak

, et al. The power of sequential single-item auctions for agent coordination. Proceedings of The National Conference on Artificial Intelligence. 2006; 21: 1625. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999.

22.

Schneider

Sklar

Parsons

Özgelen

. Auction-Based Task Allocation for Multi-robot Teams in Dynamic Environments. Towards Autonomous Robotic Systems, Springer, Cham. 2015; 246-57. doi: 10.1007/978-3-319-22416-9_29.

23.

Schoenig

Pagnucco

. Evaluating sequential single-item auctions for dynamic task allocation. AI 2010: Advances in Artificial Intelligence. Springer, Berlin, Heidelberg. 2010; 506-15. doi: 10.1007/978-3-642-17432-2_51.

24.

Sen

Adams

. An influence diagram based multi-criteria decision making framework for multirobot coalition formation. Auton Agent Multi-Agent Syst. 2015; 29: 1061-90. doi: 10.1007/s10458-014-9276-y.

25.

Schneider

Sklar

Parsons

. Mechanism selection for multi-robot task allocation. Towards Autonomous Robotic Systems, Springer, Cham. 2017; 421-35. doi: 10.1007/978-3-319-64107-2_33.

26.

Abdoun

Abouchabaka

Tajani

. Analyzing the performance of mutation operators to solve the travelling salesman problem. arXiv12033099 [Cs]; 2012.

27.

Badreldin

Hussein

Khamis

. A comparative study between optimization and market-based approaches to multi-robot task allocation, a comparative study between optimization and market-based approaches to multi-robot task allocation. Advances in Artificial Intelligence, Advances in Artificial Intelligence. 2013; 2013: e256524. doi: 10.1155/2013/256524, doi: 10.1155/2013/256524.

28.

Zhu

Tang

Yuan

. Multirobot task allocation based on an improved particle swarm optimization approach. International Journal of Advanced Robotic Systems. 2017; 14: 1729881417710312.

29.

Wang

. Multi-robot task allocation based on ant colony algorithm. Journal of Computers. 2012; 7. doi: 10.4304/jcp.7.9.2160-2167.

30.

Arif

Haider

. An Evolutionary Traveling Salesman Approach for Multi-Robot Task Allocation. 9th International Conference on Agents and Artificial Intelligence. 2017; 567-74.

31.

Muhuri

Rauniyar

. Immigrants based adaptive genetic algorithms for task allocation in multi-robot systems. International Journal of Computational Intelligence and Applications. 2017; 16: 1750025.

32.

Darrah

Wilhelm

Munasinghe

Duling

Yokum

Sorton

, et al. A flexible genetic algorithm system for multi-UAV surveillance: algorithm and flight testing. Un Sys. 2015; 3: 49-62. doi: 10.1142/S2301385015500041.

33.

Liu

Chen

. Multi-Robot Cooperation Coalition Formation Based on Genetic Algorithm. 2006 International Conference on Machine Learning and Cybernetics. 2006; 85-8. doi: 10.1109/ICMLC.2006.258820.

34.

Arif

Haider

. A flexible evolutionary algorithm for task allocation in multi-robot team. International Conference on Computational Collective Intelligence, Springer. 2018; 89-99.

35.

Arif

. Robot coalition formation against time-extended multi-robot tasks. IJIUS. 2021. doi: 10.1108/IJIUS-12-2020-0070.

36.

Arif

. A generic evolutionary algorithm for efficient multi-robot task allocations. Canadian Conference on Artificial Intelligence, Springer. 2019; 486-91.

37.

Zitouni

Maamri

Harous

. FA–QABC–MRTA: a solution for solving the multi-robot task allocation problem. Intelligent Service Robotics. 2019; 1-12.

38.

Davis

. Applying adaptive algorithms to epistatic domains. IJCAI. 1985; 85: 162-4.

39.

Michalewicz

Fogel

. How to Solve It: Modern Heuristics. 2nd ed. Berlin Heidelberg: Springer-Verlag; 2004.

40.

Hunt

Cooke

. Learning using an artificial immune system. Journal of Network and Computer Applications. 1996; 19: 189-212.

On-line task allocation for multi-robot teams under dynamic scenarios

Abstract

Keywords

1. Introduction

2. Literature review

3. Problem formulation

4.1 EA design

5. Validation schemes

Table 1 Experiment summary

7.1 Experiment 1, static environment

Table 2 Average performance of RoSTAM and online auction for experiment 1, ST-SR-TA and ST-MR-TA distributions

Table 3 Experiment 2, robot failure and reintroduction – details of changes introduced in the system (event based)

Table 7 Experiment 3, robot addition, failure, and re-introduction, details of changes introduced in the system

Table 11 Average performance of RoSTAM and online auction for experiment 4, ST-SR-TA distribution

Table 13 Experiment 5, task introduction and expansion, robot addition, failure, and re-introduction, details of changes introduced in the system

References

Table 1
Experiment summary

Table 2
Average performance of RoSTAM and online auction for experiment 1, ST-SR-TA and ST-MR-TA distributions

Table 3
Experiment 2, robot failure and reintroduction – details of changes introduced in the system (event based)

Table 7
Experiment 3, robot addition, failure, and re-introduction, details of changes introduced in the system

Table 11
Average performance of RoSTAM and online auction for experiment 4, ST-SR-TA distribution

Table 13
Experiment 5, task introduction and expansion, robot addition, failure, and re-introduction, details of changes introduced in the system