Cost-efficient inter-robot delivery for resource-constrained and interdependent multi-robot schedules

Abstract

A multi-robot system in resource-constrained environments needs to obtain resources for task execution. Typically, resources can be fetched from fixed stations, which, however, can be costly and even impossible when fixed stations are unavailable, depleted or distant from task execution locations. We present a method that allows robots to acquire urgently required resources from those robots with superfluous residual resources, by conducting rendezvouses with these robots. We consider a scenario where tasks are organised into a schedule on each robot for sequential execution, with cross-schedule dependencies for inter-robot collaboration. We design an algorithm to systematically generate such rendezvouses for entire multi-robot system to increase the proportion of tasks whose resource demands are satisfied. We also design an algorithm that periodically reallocates tasks among robots to improve the cost-efficiency of schedules. Our experiment shows the synergetic effectiveness of both algorithms, when fixed stations are unavailable and all resources are fetched through inter-robot delivery. We also investigate the effectiveness of inter-robot delivery in scenarios where fixed stations are existent but distant from the locations of tasks.

Introduction

The application of multi-robot systems (MRSs) is rapidly growing, due to their capability of performing large amount of tasks more efficiently and robustly than individual robots, in a collaborative manner. During task execution, an MRS often needs to consume certain resources, for example, electric power or fuels, tools or materials, or even abstract resources such as empty spaces. In certain scenarios, robots can fetch resources from fixed resource stations in the environment. However, in such cases when such fixed stations are unavailable, depleted or distant from the locations where the robots perform their tasks, fetching from fixed stations is either infeasible or costly, making it preferable to have robots deliver resources to each other, so that the robots in urgent demand of resources can find nearby robots that happen to possess these resources and conduct rendezvouses with these robots to acquire these resources.

Our research is related to the domain of multi-robot task allocation (MRTA) that aims to optimise assignment of the tasks to a set of robots in terms of overall performance (utility) of the MRS. In many MRTA researches, for example, that presented by Vig, ¹ Zhang, ^2,3 Chen and Sun, ⁴ Maoudj et al., ⁵ resources refer to (1) functional parts of robotic system, for example, sensors, actuators, controllers or software modules, (2) standalone indivisible objects used for task execution. In such cases, robots typically need to form coalitions to perform tasks collaboratively, which allows sharing resources among robots. In contrary, our research concerns consumable resources, for example, energy resources, vehicle capacity or materials, whose amount may change as a result of task execution.

Current MRTA approaches deal with consumable resources by representing resource usage in the construction of MRTA problem. Lee ⁶ presents a resource-oriented MRTA approach considering multiple types of resources, fixed resource stations and limited robot communication range, which considers resource consumption and cost of resource acquisition while allocating tasks. Nam ⁷ deals with inter-robot resource contention, that is, the situation in which multiple robots use the same resource. Their method penalises contentions in the computation of total utility of the MRS, to reduce contentions. Kim ⁸ presents the concept of resource welfare, which enables market-based MRTA method to optimise collectively (1) average residual resources of each coalition and (2) the balance of resources among coalitions. ⁹ Wu ¹⁰ introduces Gini coefficient into market-based MRTA, for measuring the balance between resource consumption and task completion, to retain as many resources as possible to complete more tasks. The majority of researches about resource-constrained MRTA consider the residual resources of robots to be static rather than dynamically rechargeable. For those research studies that consider rechargeable resources, they typically assume the resources are fetched from fixed resource stations rather than allowing inter-robot delivery. This limits the application of these methods in such scenarios when fixed resource stations are unavailable, depleted or distant from task locations. In addition, most research studies do not consider the influence of cross-schedule dependencies (e.g. precedence constraints and/or rendezvouses) on resource acquisition. These dependencies are more common when relations among tasks become more complex in real-world scenarios.

In addition to MRTA research studies considering resource consumption, there are research studies that focus specifically on planning or scheduling problem of resource recharging, as exemplified by: (1) optimal unmanned aerial vehicle (UAV) refuelling scheduling, by Jin ^11,12 ; (2) aerial fleet refuelling, by Barnes ¹³ ; (3) satellite servicing scheduling, by Shen ¹⁴ ; (4) energy-efficient inter-robot rendezvous, by Litus ¹⁵ ; (5) rendezvous-based robot recharging, by Mathew. ¹⁶ However, these researches usually explicitly separate the charging stations from robots executing ordinary tasks, rather than allowing robots to exchange resources. They also rarely consider the dynamic interplay between recharging planning and task reallocation.

In this article, we consider the case when an MRS performs tasks in a time-extended manner, with each robot executing a schedule composed of a sequence of tasks in the given order. The schedules enable robots to dynamically plan their task execution in a long-term manner, according to the priorities of different tasks, their locations in the physical environment and the constraints among them. Each task corresponds to one location in the two-dimensional space and requires the robot to perform certain operations at the location, which will cost the robot certain amount of resources. According to the taxonomy by Gerkey et al. ¹⁷ and Korsahk et al., ¹⁸ our work overlaps with the single-task (ST) multi-robot (MR) time-extended assignment (TA) with cross-schedule dependencies (XD [ST-MR-TA]) category of MRTA problem. In specific, our research is related to the MRTA problem in resource-constrained environment in which each task requires certain resources for execution, and the completion ratio of assigned tasks is a major optimisation objective of the MRTA problem.

We use the concept of feasibility (the schedule(s) of each individual robot or of entire MRS) to describe the extent to which the tasks in the schedule(s) can be successfully executed because their resource demands can be satisfied by the residual resources of each robot. Robots can persistently maintain the feasibility of the schedule(s) by conducting inter-robot delivery which transits resources among robots. Inter-robot delivery is expected to be conducted in a coordinated manner, to ensure the following qualities of feasibility maintenance.

1. Monotonic improvement of feasibility. The feasibility of different schedules should be improved monotonically, that is, the feasibility of any schedule cannot be improved at the expense of the feasibility of another schedule. For example, consider delivering resources from robot ${\alpha }^{\prime }$ to robot α: if satisfying one task of α means taking away the resources necessary for executing tasks on ${\alpha }^{\prime }$ , thereby reducing the feasibility of the schedule of ${\alpha }^{\prime }$ , then such delivery should not be conducted. Otherwise, resource conflicts among robots may frequently occur, which invalidate the resources already scheduled to be obtained by specific robots and cause possibly infinite negotiation among robots about who will possess a specific set of resources, thereby hindering the improvement of the feasibility of the MR schedules.

2. Compliance with constraints among tasks. Real-world tasks are usually not independent of each other; instead, there are typically constraints among tasks, regulating how tasks scattered in the MRS work integrally. We consider two types of constraints among tasks, including (i) precedence constraint, which requires the completion of one task to precede the commencement of another task; (ii) rendezvous, which requires multiple tasks to be performed at the same time and location through close inter-robot collaboration. These constraints regulate in what order should the resource demands of tasks be satisfied.

3. Deadlock-free schedules. Deadlock is such a situation in which a cycle is formed by the relations among tasks waiting for each other to finish, blocking the execution of successive tasks. The relations forming a deadlock include the aforementioned precedence constraints and rendezvouses, as well as the execution order of tasks within each schedule. In particular, since inter-robot delivery requires rendezvouses between robots, an improper rendezvous may result in the deadlock among multiple schedules. To ensure the smooth execution of the schedules, we must take precautions to prevent inter-robot delivery from introducing such deadlocks.

4. Cost-efficiency of MR schedules. The execution of the schedules is typically expected to be cost-efficient, that is, at as low cost as possible. The total cost of schedules depends on the cost of executing each task and of transiting between tasks. With the introduction of inter-robot delivery, the cost of entire MR schedules can be divided into following parts: (i) the cost of executing ordinary tasks, (ii) the cost of performing rendezvouses for inter-robot delivery and of transiting between ordinary tasks and the rendezvouses. Both parts are expected to be reduced at runtime, without having significantly negative effect on feasibility maintenance.

In this article, we present a method of inter-robot delivery for improving the feasibility of MR schedules. We propose an algorithm (Algorithm 1) that generates rendezvouses for inter-robot delivery. Algorithm 1 ensures (i) no deadlocks will be introduced; (ii) monotonic improvement of the feasibility of each schedule; (iii) compliance with inter-task constraints, by enforcing the resource demands of the tasks being satisfied in particular order according to inter-task constraints. Algorithm 1 also dynamically selects the nearest available resource provider in the vicinity of a robot to minimise the cost for inter-robot delivery. The capability of Algorithm 1 in preventing deadlocks and ensuring monotonic improvement is theoretically proven. We use an experiment (‘Effectiveness of inter-robot resource delivery for maintaining feasibility’ section) to show the effectiveness of Algorithm 1 in improving the feasibility of MR schedules. The role of Algorithm 1 for MRS can be seen as redistributing resources among robots according to the distribution of resource demands on robots. In addition, we present an algorithm (Algorithm 2) which is capable of repeatedly reallocating the tasks to different positions in the MR schedules to incrementally reduce the cost for inter-robot delivery and seek to reallocate the tasks to robots with sufficient residual resources so that it may not need inter-robot delivery to satisfy the resource demands of these tasks in the first place. The role of Algorithm 2 for MRS can be seen as redistributing resource demands (of tasks) among robots according to the distribution of residual resources on robots. We use an experiment (‘Effect of persistent task reallocation on inter-robot resource delivery’ section) to show the effect of combining Algorithm 2 with Algorithm 1 on the effectiveness of Algorithm 1. For the scenarios when the fixed stations are available but distant from the task locations, we use an experiment (‘Effectiveness of inter-robot resource delivery in scenarios with fixed resource stations’ section) to show the effectiveness of Algorithm 1 together with Algorithm 2 in providing resources with lower cost.

The remainder of this article is organised as follows. Second section describes related work. Third section presents the research problems of this article. Fourth section presents the feasibility maintenance algorithm and the task reallocation algorithm. Fifth section presents the experiment results. Sixth section presents the conclusion and future work. Symbols used throughout this paper are defined in Table 1.

Table 1.

Table of symbols.

Symbol	Description
$\mathfrak{P}(\cdot )$	The power set of a set $(\cdot )$
$\kappa$	The configuration of a MRS
Π	A set of tasks in MRS
P	A set of precedence constraints among tasks in Π
ϒ	A set of rendezvouses among robots in MRS
U	A set of allocation bundles
Σ	A set of schedules in MRS
π	A task to be executed by a robot
υ	A rendezvous, containing tasks to be conducted by multiple robots
U	An allocation bundle, containing the tasks to be allocated as a whole among robots
σ	A schedule of tasks, to be executed by a robot sequentially
$\sigma (i)$	The i th task in schedule σ
$\sigma (\pi )$	The schedule to which the task π belongs
${\iota }_{\sigma }(\pi )$	The index of task π in schedule σ
$|\sigma |$	The length of schedule σ
$\stackrel{\text{s}}{{\displaystyle \to }}$	A relation between two tasks, showing the constraints imposed by the order of tasks in the same schedule, defined by definition 1
$\stackrel{\text{p}}{{\displaystyle \to }}$	A relation between two tasks, showing the constraints imposed by precedence constraints P, defined by definition 2
$\stackrel{\text{v}}{{\displaystyle \to }}$	A relation between two tasks, showing the constraints imposed by rendezvouses ϒ, defined by definition 3
≺	A relation between two tasks, showing the combined influence of $\stackrel{\text{s}}{{\displaystyle \to }},\stackrel{\text{p}}{{\displaystyle \to }},\stackrel{\text{v}}{{\displaystyle \to }}$ , defined by definition 4
${\prec }^{\star }$	A relation between two tasks, showing the reachability between tasks with respect to ≺, defined by definition 5
r	A set of resources
r	A resource of specific type $r\mathrm{.}y$ and amount $r\mathrm{.}m$
$Y(R)$	The set of resource types involved in set of resources r
$R_{⊲}(\pi )$	The set of resources demanded by the execution of task π
$\Delta R(\pi )$	The set of resources contributed by the execution of task π
$R_{⊳}(\pi )$	The set of residual resources in the schedule $\sigma (\pi )$ after the execution of task π, defined by equation (8)
${\widehat{\mathbb{T}}}_{\text{fsb}}[\pi ]$	A Boolean value indicating that task π is feasible, defined by equation (10)
${\mathbb{T}}_{\text{fsb}}[\pi ]$	A Boolean value indicating that the resource demands of task π is satisfied by the residual resources of schedule $\sigma (\pi )$ , see equation (11)
${\widehat{\mathbb{T}}}_{\text{fsb}}[\sigma ]$	A Boolean value indicating that all tasks in schedule σ are feasible, defined by equation (12)
$d_{\text{fsb}}(\sigma )$	The degree of feasibility of schedule σ, defined by equation (13)
$d_{\text{fsb}}(\Sigma )$	The degree of feasibility of MR schedules Σ, see equation (14)
$\parallel \Sigma \parallel$	The energy cost of MR schedules Σ, defined by equation (15)
${\Upsilon }_{\text{r}}(\pi )$	The set of rendezvouses for providing resources to task π
${\Upsilon }_{\text{r}}(\Sigma )$	The set of rendezvouses for providing resources to all tasks in MR schedules Σ, defined by equation (17)
$\parallel \Sigma {\parallel }_{\text{v}}$	The energy cost of the set of rendezvouses ${\Upsilon }_{\text{r}}(\Sigma )$ , see equation (18)
$\text{M}$	A set of SMO, see ‘Approach’ section
μ	An SMO
χ	The search frontier of CreateRendezvous algorithm, see equation (20)
$\varphi (\mu )$	A measurement of effectiveness of each SMO μ, see equation (21) and (39)
$d_{\text{stf}}(\sigma ,\pi )$	The degree of satisfaction of the resource demand of task π in schedule σ, defined by equation (23)
${\widehat{\Pi }}_{\star \leftarrow }(\pi )$	The set of tasks that precede task π by ${\prec }^{\star }$ relation, see equation (44)
${\widehat{\Pi }}_{\to \star }(\pi )$	The set of tasks that succeed task π by ${\prec }^{\star }$ relation, see equation (45)
${\underset{\_}{\iota }}_{\sigma }(\pi )$	The lower bound of the index of task π in schedule σ, determined by ${\widehat{\Pi }}_{\star \leftarrow }(\pi )$ , defined by equation (43)
${\overline{\iota }}_{\sigma }(\pi )$	The upper bound of the index of task π in schedule σ, determined by ${\widehat{\Pi }}_{\to \star }(\pi )$ , defined by equation (43)

MRS: multi-robot system; MR: multi-robot; SMO: schedule manipulation operation.

Problem statement

In this section, we present the model of an MRS (‘Task-level model of multi-robot system with cross-schedule dependencies’ section), which depicts the composition of the schedules of the MRS and the cross-schedule dependencies that need to be respected during the execution of the schedules and the inter-robot resource delivery. Based on this model, we define two major optimisation objectives to be achieved by inter-robot delivery: (1) feasibility, which refers to the proportion of the tasks (in the MR schedules) whose resource demands are completely satisfied, and (2) cost-efficiency, which refers to the capability of the MR schedules to be executed with relatively low cost. It finally presents the problem statement based on these optimisation objectives.

Task-level model of MRS with cross-schedule dependencies

In this section, we present the model of the task level configuration of the MRS, which consists of the set of tasks and the constraints among tasks. These constraints regulate the execution of the tasks and the satisfaction of the resource demands of the tasks and form the basis of the cross-schedule dependencies among tasks. ¹⁸ The configuration of a MRS can be described as a tuple $\kappa =〈\Pi ,P,\Upsilon ,U,\Sigma 〉$ , where (1) Π is the set of tasks assigned to the MRS, where each task π describes an indivisible unit of action that the robot is required to perform at a given location in the two-dimensional environment; (2) $P\subseteq \Pi \times \Pi$ is the set of precedence constraints among Π, which constrains the execution order of the tasks Π on the MR schedule Σ; (3) $\Upsilon \subseteq \mathfrak{P}(\Pi )$ is a set of rendezvouses; each $\upsilon \in \Upsilon$ is a set of tasks, in which each task $\pi \in \upsilon$ is assigned to a distinctive robot, while all tasks in υ must be performed at the same time and location through the close collaboration among the involved robots; particularly in this article, we use rendezvouses as a means to describe inter-robot resource delivery; (4) U is a set of allocation bundles that are the basic units of task allocation; each $u\in U$ indicates that any two tasks ${\pi }_1,{\pi }_2\in u$ must be assigned to the same schedule, that is, $\exists \sigma \in \Sigma :{\pi }_1,{\pi }_2\in \sigma$ ; (5) Σ is the set of schedules of the MRS, in which each schedule $\sigma \in \Sigma$ is a sequence of tasks $\sigma =〈{\pi }_1\mathrm{,...},{\pi }_n〉$ , where (a) $\sigma (i)={\pi }_i$ is the i th task in σ, (b) ${\iota }_{\sigma }({\pi }_i)=i$ is the index of ${\pi }_i$ in σ, (c) $|\sigma |\hspace{0.17em}=n$ is the length of σ, that is, the count of tasks contained in σ.

For the MR schedules Σ to be executed smoothly, the tasks in Σ should satisfy the following conditions: (1) the positions of tasks in Σ should comply with the constraints imposed by P and ϒ. (2) There should not be any deadlocks in Σ. To facilitate the representation and analysis of these conditions, we define the following relations, as shown in definitions 1, 2 and 3.

Definition 1. For any ${\pi }_1,{\pi }_2\in \sigma \in \Sigma$ with ${\pi }_1\ne {\pi }_2$ , define relation ${\pi }_1\stackrel{s}{{\displaystyle \to }}{\pi }_2$ (also ${\pi }_2\stackrel{\text{s}}{{\displaystyle \leftarrow \hspace{0.17em}}}{\pi }_1$ ) as

${\pi }_1\stackrel{\text{s}}{{\displaystyle \to }}\hspace{0.17em}{\pi }_2\hspace{1em}\iff \hspace{1em}{\iota }_{\sigma }({\pi }_1)<{\iota }_{\sigma }({\pi }_2)$

1

where for any $\pi \in \sigma$ , ${\iota }_{\sigma }(\pi )$ is the current index of π in σ.

By definition 1, for any tasks ${\pi }_1$ and ${\pi }_2$ , ${\pi }_1\stackrel{\text{s}}{{\displaystyle \to }}\hspace{0.17em}{\pi }_2$ means that ${\pi }_1$ and ${\pi }_2$ are in the same schedule σ, and that ${\pi }_1$ is located ahead of ${\pi }_2$ in σ.

Definition 2. For any ${\pi }_1,{\pi }_2\in \Pi$ with ${\pi }_1\ne {\pi }_2$ , define relation ${\pi }_1\stackrel{\text{p}}{{\displaystyle \to }}\hspace{0.17em}{\pi }_2$ (also ${\pi }_2\stackrel{\text{p}}{{\displaystyle \leftarrow \hspace{0.17em}}}{\pi }_1$ ) as

${\pi }_1\stackrel{\text{p}}{{\displaystyle \to \hspace{0.17em}}}{\pi }_2\hspace{1em}\iff \hspace{1em}〈{\pi }_1,{\pi }_2〉\in P$

2

By definition 2, for any task ${\pi }_1$ and ${\pi }_2$ , ${\pi }_1\stackrel{\text{p}}{{\displaystyle \to }}\hspace{0.17em}{\pi }_2$ means that ${\pi }_1$ is required by the precedence constraints P to precede ${\pi }_2$ in the actual execution.

Definition 3. For any ${\pi }_1,{\pi }_2\in \Pi$ with ${\pi }_1\ne {\pi }_2$ , define relation ${\pi }_1\stackrel{\text{v}}{{\displaystyle \to }}\hspace{0.17em}{\pi }_2$ (also ${\pi }_2\stackrel{\text{v}}{{\displaystyle \leftarrow }}\hspace{0.17em}{\pi }_1$ ) as

${\pi }_1\stackrel{\text{v}}{{\displaystyle \to \hspace{0.17em}}}{\pi }_2\hspace{1em}\iff \hspace{1em}\exists \upsilon \in \Upsilon :{\pi }_1,{\pi }_2\in \upsilon$

3

By definition 3, for any task ${\pi }_1$ and ${\pi }_2$ , ${\pi }_1\stackrel{\text{v}}{{\displaystyle \to }}{\pi }_2$ means that ${\pi }_1$ and ${\pi }_2$ belong to the same rendezvous υ. Note that this means ${\pi }_1\stackrel{\text{v}}{{\displaystyle \to }}\hspace{0.17em}{\pi }_2\iff {\pi }_2\stackrel{\text{v}}{{\displaystyle \to }}{\pi }_1$ , that is, the relation $\stackrel{\text{v}}{{\displaystyle \to }}$ can be seen as bidirectional, which indicates that ${\pi }_1$ is required to both precede and succeed (i.e. to happen simultaneously with) ${\pi }_2$ in the execution. This requirement is not in conflict with the requirement that ${\pi }_1$ and ${\pi }_2$ must be assigned to different robots.

Definition 4 defines a relation $\prec$ among tasks, which combines the relations given by definitions 1, 2, 3 into one, to grasp the execution order constraints of tasks in a compact manner.

Definition 4. For any ${\pi }_1,{\pi }_2\in \Pi$ with ${\pi }_1\ne {\pi }_2$ , define relation ${\pi }_1\prec {\pi }_2$ (also ${\pi }_2\succ {\pi }_1$ ) as

${\pi }_1\prec {\pi }_2\hspace{1em}\iff \hspace{1em}{\pi }_1\stackrel{\text{s}}{{\displaystyle \to }}\hspace{0.17em}{\pi }_2\vee {\pi }_1\stackrel{\text{p}}{{\displaystyle \to \hspace{0.17em}}}{\pi }_2\vee {\pi }_1\stackrel{\text{v}}{{\displaystyle \to }}\hspace{0.17em}{\pi }_2$

4

Based on the above relation ≺, we can recursively define the relation ${\pi }_1{\prec }^{\star }{\pi }_2$ (also ${\pi }_2{\succ }^{\star }{\pi }_1$ ) between each two tasks ${\pi }_1$ and ${\pi }_2$ , as shown in definition 5. This relation is later used to describe the situation when such relations form a deadlock – a cycle of multiple tasks waiting for each other to finish.

Definition 5. For any ${\pi }_1,{\pi }_2\in \Pi$ , define relation ${\pi }_1{\prec }^{\star }{\pi }_2$ (also ${\pi }_2{\succ }^{\star }{\pi }_1$ ) recursively as

${\pi }_1{\prec }^{\star }{\pi }_2\hspace{1em}\iff \hspace{1em}\exists \pi \in \Pi \backslash \{{\pi }_1,{\pi }_2\}:{\pi }_1\prec \pi \wedge \pi {\prec }^{\star }{\pi }_2$

5

For any ${\pi }_1,{\pi }_2\in \Pi$ , as long as ${\pi }_1{\prec }^{\star }{\pi }_2$ holds, the commencement of ${\pi }_2$ must wait until the completion of ${\pi }_1$ . If such waiting relations form a cycle among more than one tasks, then Σ must contain a deadlock.

We now present the condition which guarantees that the schedules Σ are without deadlock, that is, there are no cycles formed by multiple tasks (possibly from different schedules) waiting for each other to finish. We first define the concept of Σ being cyclic, that is, there exist such cycles among tasks in Σ, as shown in definition 6.

Definition 6. Σ is cyclic, iff

$\exists \pi \in \sigma \in \Sigma :\pi \text{is} cyclic$

6

where each task π being cyclic is defined by definition 7, based on the relations ${\prec }^{\star }$ involving π.

Definition 7. Task π is cyclic, iff

$\exists {\pi }^{\prime }\in \Pi \backslash \left\{\pi \right\}:{\pi }^{\prime }{\prec }^{\star }\pi \wedge {\pi }^{\prime }{\succ }^{\star }\pi \wedge \neg \left({\pi }^{\prime }\stackrel{\text{v}}{{\displaystyle \to \hspace{0.17em}}}\pi \right)$

7

Note that as long as Σ is not cyclic, all the tasks in Σ must also satisfy the constraints imposed by P and ϒ.

Feasibility of MR schedules

The main objective of inter-robot delivery is to improve the feasibility of the MR schedules Σ, that is, the degree to which the resource demands of the tasks in Σ are satisfied by the residual resources of the robots. We first introduce the representation of the resources to be consumed by tasks or provided by robots. Each resource r is defined as a tuple $〈y,m〉$ , where (1) $y\in {\mathbb{Z}}^{+}$ is the type of r, which is application-specific; (2) $m\in ℝ$ is the amount of resource of type y represented by r. A set of resources r is defined as a subset of $\{r\in 〈y,m〉:y\in Y,m\in ℝ\}$ . Thus, r can also be seen as a function $R:Y\to ℝ$ , so that for each $y\in Y$ , $R(y)$ represents the amount of resource of type y contained in r. We use $Y(R)=\left\{y\in Y:\exists m\in ℝ:〈y,m〉\in R\right\}$ to represent the set of resource types involved in r.

In this article, we assume resources are linear and define their following operations for a single resource: (1) $〈y,m_1〉+〈y,m_2〉=〈y,m_1+m_2〉$ ; (2) $k\cdot 〈y,m〉=〈y,k\cdot m〉$ , where $k\in ℝ$ .

We further define the following operations for any two sets of resources $R_1$ and $R_2$ : (1) $R_1\hspace{0.17em}\tilde{\cup }\hspace{0.17em}{R}_2=\varsigma (R_1\cup R_2)$ is the union of $R_1$ and $R_2$ ; (2) $R_1\tilde{\cap }\hspace{0.17em}{R}_2=\varsigma (R_1\cap R_2)$ is the intersection of $R_1$ and $R_2$ ; (3) $R_1 \tilde{\backslash } R_2=\varsigma (R_1\cup -R_2)$ is the difference of $R_1$ and $R_2$ . The function ς is defined by $\varsigma (R)=\left\{r^{\prime }\in {\displaystyle {\cup }_{y\in Y(R)}}\left\{〈y,{\displaystyle {\sum }_{r\in R,r\cdot y=y}}r\mathrm{.}\hspace{0.17em}m〉\right\}:z_y(r^{\prime }\mathrm{.}\hspace{0.17em}m)=1\right\}$ , which is used to merge all the resources (in r) which have the same type, and eliminate the resources whose amounts can be omitted for being slight enough. The function $z_y:ℝ\to \{0,1\}$ is used to indicate whether the amount m of y-typed resources is slight enough (e.g. close to 0 or below a certain threshold). If $z_y(m)=0$ , then m can be omitted, otherwise, $z_y(m)=1$ .

For any two sets of resources $R_1$ and $R_2$ , they can have the following relations: (1) $R_1<R_2$ (i.e. $R_2>R_1$ ), which is defined as $\forall y\in Y(R_1)\cap Y(R_2):R_1(y)<R_2(y)$ ; (2) $R_1\le R_2$ (i.e. $R_2\ge R_1$ ), which is defined as $\forall y\in Y(R_1)\cap Y(R_2):R_1(y)\le R_2(y)$ . These relations are later used to define the feasibility of the schedules.

For each schedule $\sigma \in \Sigma$ and task $\pi \in \sigma$ , we can define: (1) $R_{⊲}(\pi )$ is the set of resources demanded by π, which is application-specific; (2) $\Delta R(\pi )$ is the set of resources contributed by π; for each $y\in Y$ , whether $\Delta R(\pi )(y)$ is positive or negative represents whether the contribution is an increment or a decrement, respectively; (3) $R_{⊳}(\pi )$ is the set of residual resources which remains on the robot owning σ after executing π, which can be defined as below (assuming $\pi ={\pi }_i$ is the i th element of a schedule σ)

$R_{⊳}({\pi }_i)=\left(R_{⊳}({\pi }_{i-1}) \tilde{\backslash } \parallel {\pi }_{i-1},{\pi }_i\parallel \right) \tilde{\cup } \Delta R({\pi }_i)$

8

where

$R_{⊳}({\pi }_{i-1}) \tilde{\backslash } \parallel {\pi }_{i-1},{\pi }_i\parallel \hspace{0.17em}\ge R_{⊲}({\pi }_i)$

9

and $\parallel {\pi }_{i-1},{\pi }_i\parallel \hspace{0.17em}\subseteq Y\times ℝ$ is the transition cost from ${\pi }_{i-1}$ to ${\pi }_i$ , that is the cost (i.e. resource consumption) of the activities of a robot from the completion of task ${\pi }_{i-1}$ to the commencement of task ${\pi }_i$ , which normally includes cost for travelling to the location for executing ${\pi }_i$ or for making necessary preparations.

We now introduce the concept of feasibility for tasks and schedules. For each task π, the Boolean value ${\widehat{\mathbb{T}}}_{\text{fsb}}[\pi ]$ indicates that π is feasible, which is defined as below

${\widehat{\mathbb{T}}}_{\text{fsb}}[\pi ]={\mathbb{T}}_{\text{fsb}}[\pi ]\wedge \underset{{\pi }^{\prime }\in {\widehat{\Pi }}_{\leftarrow }(\pi )}{{\displaystyle \wedge }}{\widehat{\mathbb{T}}}_{\text{fsb}}[{\pi }^{\prime }]$

10

where ${\mathbb{T}}_{\text{fsb}}[\pi ]$ is a Boolean value which indicates that the resource demands of π is satisfied by the residual resource of the schedule σ, that is

${\mathbb{T}}_{\text{fsb}}[\pi ]=(R_{⊳}(\sigma ({\iota }_{\sigma }(\pi )-1))\ge R_{⊲}(\pi ))$

11

For each schedule σ, the Boolean value ${\mathbb{T}}_{\text{fsb}}[\sigma ]$ indicates that σ is feasible, which is defined as below

${\widehat{\mathbb{T}}}_{\text{fsb}}[\sigma ]=\underset{\pi \in \sigma }{{\displaystyle \wedge }}{\widehat{\mathbb{T}}}_{\text{fsb}}[\pi ]$

12

The ideal situation is when all the schedules are feasible. However, for a schedule σ, it is possible that only the resource demands of some tasks in σ are satisfied, that is σ is partially feasible. To represent such situation, we introduce the concept of degree of feasibility, represented by function $d_{\text{fsb}}:\Sigma \to [0,1]$ , which is defined as below

$d_{\text{fsb}}(\sigma )={\displaystyle \sum _{y\in Y}}\frac{{\displaystyle {\sum }_{\pi \in \sigma ,{\widehat{\mathbb{T}}}_{\text{fsb}}[\pi ]}{R}_{⊲}(\pi )(y)}}{{\displaystyle {\sum }_{\pi \in \sigma }{R}_{⊲}(\pi )(y)}}/|{\displaystyle \underset{\pi \in \sigma }{\cup }}Y(R_{⊲}(\pi ))|$

13

It is obvious that (1) when ${\widehat{\mathbb{T}}}_{\text{fsb}}[\sigma ]$ , $d_{\text{fsb}}(\sigma )=1$ , (2) when $\neg {\widehat{\mathbb{T}}}_{\text{fsb}}[\sigma ]$ , $d_{\text{fsb}}(\sigma )=0$ , (3) in other cases, $d_{\text{fsb}}(\sigma )\in (0,1)$ .

We now present the degree of feasibility of entire MRS, $d_{\text{fsb}}(\Sigma )$ , as one of the optimisation objective of the problem about inter-robot delivery, which is defined as below

$d_{\text{fsb}}(\Sigma )={\displaystyle \sum _{\sigma \in \Sigma }}{d}_{\text{fsb}}(\sigma )/|\Sigma |$

14

It is obvious that (1) when all tasks on all robots are feasible, $d_{\text{fsb}}(\Sigma )=1$ ; (2) when all tasks on all robots are infeasible, $d_{\text{fsb}}(\Sigma )=0$ ; (3) the reduction of the degree of feasibility of whichever robot will cause the reduction of $d_{\text{fsb}}(\Sigma )$ .

Through inter-robot delivery, for each task $\pi \in \sigma$ whose resource demand is not satisfied, assuming σ is owned by robot α, we can let α conduct a set of rendezvous ${\Upsilon }_{\text{r}}(\pi )$ with a set of different robots who happen to possess the required resources, at the rendezvous positions determined by α and these robots. The set ${\Upsilon }_{\text{r}}(\pi )$ will be inserted into the schedules of α and all the relevant robots. Note that ${\Upsilon }_{\text{r}}(\pi )$ is also capable of describing such case in which α acquires resources from fixed stations, by conducting rendezvous with these stations. The only difference is that the fixed stations cannot autonomously move to the rendezvous position with α, hence the rendezvous positions for the fixed stations are always unchangeable. It is expected that after executing ${\Upsilon }_{\text{r}}(\pi )$ , the resource demand of π can be satisfied, thereby improving the degree of feasibility of entire MR schedules Σ.

Problem I. How to improve the degree of feasibility of the MR schedules via inter-robot delivery, so that (1) feasibility of different schedules are improved monotonically, (2) no deadlocks will be introduced through inter-robot delivery.

Cost-efficiency of MR schedules

The cost-efficiency of the schedules is a measurement of performance of the execution of the MR schedules, provided that the schedules are consistent. An MRS is usually expected to execute its tasks with higher cost-efficiency, that is, at as low cost as possible. When the tasks are arranged in time-extended MR schedules Σ, the cost of Σ, denoted as $\parallel \Sigma \parallel$ , depends on the cost of executing each task π and the transition cost between adjacent tasks in each $\sigma \in \Sigma$ . In this article, $\parallel \Sigma \parallel$ is defined as below

$\parallel \Sigma \parallel ={\displaystyle \sum _{\sigma \in \Sigma }}{\displaystyle \sum _{i=1}^{|\sigma |}}{\displaystyle \sum _{y\in Y}}{w}_y\left(\parallel {\pi }_{i-1},{\pi }_i\parallel (y)+\parallel {\pi }_i\parallel (y)\right)$

15

where (1) $\parallel {\pi }_{i-1},{\pi }_i\parallel \hspace{0.17em}\subseteq Y\times ℝ$ is the transition cost from ${\pi }_{i-1}$ to ${\pi }_i$ ; (2) $\parallel {\pi }_i\parallel$ is the cost of a robot for completing task ${\pi }_i$ , as defined by equation (16); (3) $w_y$ is the weight of the y-type resource.

$\parallel {\pi }_i\parallel (y)=\{\begin{array}{ll}-\Delta R(\pi )(y)\hfill & \text{if} \Delta R({\pi }_i)(y)<0\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$

16

Reducing $\parallel \Sigma \parallel$ can normally be done using conventional task allocation/reallocation methods. In addition, the use of inter-robot delivery as a means to improve the degree of feasibility of Σ, implies a considerable amount of costs dedicated to ${\Upsilon }_{\text{r}}(\Sigma )$ , that is, the set of rendezvouses among robots for inter-robot delivery. ${\Upsilon }_{\text{r}}(\Sigma )$ is defined as below

${\Upsilon }_{\text{r}}(\Sigma )={\displaystyle \underset{\sigma \in \Sigma }{\cup }}{\displaystyle \underset{\pi \in \sigma }{\cup }}{\Upsilon }_{\text{r}}(\pi )$

17

where ${\Upsilon }_{\text{r}}(\pi )$ is the set of rendezvouses for acquiring resources for each task $\pi \in \sigma \in \Sigma$ and is itself part of Σ.

To estimate the contribution of ${\Upsilon }_{\text{r}}(\Sigma )$ to the cost $\parallel \Sigma \parallel$ , we define the cost of ${\Upsilon }_{\text{r}}(\Sigma )$ as $\parallel \Sigma {\parallel }_{\text{v}}$ , which can be calculated using the following formula

$\parallel \Sigma {\parallel }_{\text{v}}={\displaystyle \sum _{\upsilon \in {\Upsilon }_{\text{r}}(\Sigma )}}{\displaystyle \sum _{y\in Y}}{w}_y\cdot \parallel \upsilon \parallel (y)$

18

where $\parallel \upsilon \parallel (y)$ is the y-type resource used by rendezvous υ and is defined as below

$\parallel \upsilon \parallel (y)={\displaystyle \sum _{\sigma \in \Sigma }}{\displaystyle \sum _{\pi \in \upsilon \cap \sigma }}\left(\parallel \sigma ({\iota }_{\sigma }(\pi )-1),\pi \parallel (y)+\parallel \pi \parallel (y)\right)$

19

There exists close relation between the degree of feasibility $d_{\text{fsb}}(\Sigma )$ and the cost $\parallel \Sigma \parallel$ , due to the contribution of ${\Upsilon }_{\text{r}}(\Sigma )$ to $\parallel \Sigma \parallel$ . When the MRS adds more rendezvouses into ${\Upsilon }_{\text{r}}(\Sigma )$ , it will probably increase $d_{\text{fsb}}(\Sigma )$ , while also increasing $\parallel \Sigma {\parallel }_{\text{v}}$ , which is a part of $\parallel \Sigma \parallel$ . When we try to improve the cost $\parallel \Sigma \parallel$ , probably by adapting Σ, we also risk disturbing the original matching between residual resources and the resource demands on each robot, thereby causing uncertain influence to $d_{\text{fsb}}(\Sigma )$ . To effectively reduce the cost $\parallel \Sigma \parallel$ , we need to find a way to seamlessly integrate the reduction of $\parallel \Sigma \parallel$ and the increase of $d_{\text{fsb}}(\Sigma )$ , to achieve synergetic improvement of both objectives and avoid the possible conflicts between them.

Problem II. How to improve the cost-efficiency of MR schedules Σ, considering the contribution of inter-robot delivery to the cost $\parallel \Sigma \parallel$ , while maintaining feasibility of Σ.

Approach

This section presents a scheme of feasibility maintenance which consists of two algorithms, namely CreateRendezvous and ReAllocate, which provide solution to problems (I) and (II), respectively.

The algorithm CreateRendezvous (see ‘Rendezvous creation algorithm’ section) is responsible for maintaining the feasibility of MR schedules Σ through generating tasks for inter-robot delivery. It applies the concept of search frontier to coordinate the progress of each robot to satisfy the resource demands of its schedule, to ensure the following features of Σ: (1) Σ complies with the constraints among tasks; (2) Σ is deadlock-free; (3) the feasibility of Σ and each $\sigma \in \Sigma$ is improved monotonically. The capability of CreateRendezvous algorithm in ensuring the above features of Σ is guaranteed by Theorem 1 and Theorem 2.

The algorithm ReAllocate (see ‘Task reallocation algorithm’ section) adopts the market-based task reallocation method to persistently improve the cost-efficiency of Σ. This algorithm is used alongside CreateRendezvous algorithm with the expectation that the cost-efficiency can be maintained throughout the life-cycle of the MRS despite the introduction of rendezvouses for inter-robot delivery.

To represent the dynamic manipulation of the schedules Σ by both algorithms, we define the concept of schedule manipulation operation (SMO), which is used throughout both algorithms. The set of all SMOs is denoted as $\text{M}$ . Each SMO $\mu \in \text{M}$ is a map $\mu :\mathfrak{P}(\Sigma )\to \mathfrak{P}(\Sigma )$ that shows the effect of manipulating the schedules Σ by adding/removing/moving tasks into/from/in specific schedules. Both Algorithms 1 and 2 optimise specific SMOs according to their respective objectives.

Rendezvous creation algorithm

This section presents an algorithm (Algorithm 1), as shown in Figure 1, which maintains the feasibility of the MR schedules Σ by detecting and eliminating the infeasible tasks in Σ. For each infeasible task π on robot α, it will insert tasks ahead of π that conduct rendezvouses between α and other robots with superfluous residual resources, so as to deliver these resources to α. This algorithm scans entire Σ until the resource demands of all tasks in Σ are satisfied. We base our algorithm on the concept of search frontier, which is the boundary between the satisfied and unsatisfied parts of the MR schedules and can be denoted as a function $\chi :\Sigma \to \mathbb{Z}$ , which is defined as below

Figure 1.

An algorithm for generating rendezvouses for inter-robot delivery to improve feasibility of the MR schedules.

$\chi =\left\{〈\sigma ,i〉:\sigma \in \Sigma ;\left(\forall j<i:{\widehat{\mathbb{T}}}_{\text{fsb}}[\sigma (j)]\right)\wedge \neg {\widehat{\mathbb{T}}}_{\text{fsb}}[\sigma (i)]\right\}$

20

That is, for any $\sigma \in \Sigma$ , $\chi (\sigma )$ returns index i in σ, so that the task $\sigma (i)$ is the first infeasible task in σ. The frontier is used to record the current progress of the algorithm in satisfying each schedule, to coordinate feasibility maintenance of different schedules, so that no schedule will improve its degree of feasibility at the expense of the loss of degree of feasibility of other schedules. At the beginning, all schedules in Σ are assumed completely infeasible, that is, $\forall \sigma \in \Sigma :\chi (\sigma )=0$ (or shortened as $\chi =0$ ). The entire algorithm will gradually push forward the frontier $\chi$ to the end of the schedules, where $\forall \sigma \in \Sigma :\chi (\sigma )=\hspace{0.17em}|\sigma |$ (or shortened as $\chi =\infty$ ) and then the algorithm terminates.

The entire algorithm consists of a while loop which persists until $\chi =\infty$ is satisfied. Line 2 updates χ using equation (20). Line 3 sorts all tasks on χ according to the ascending order of the estimated start time $t_{\text{st}}(\pi )$ of each task π, so that the more urgent tasks have higher chance of being first satisfied. Lines 4–35 process each task on χ according to the sorted order ${\widehat{\Pi }}_{\chi }$ . Line 5 checks whether the preceding tasks ${\widehat{\Pi }}_{\star \leftarrow }(\pi )$ has been satisfied. Only if this condition holds, π will be processed. The reason of doing this is to prevent introducing deadlocks caused by inter-robot resource delivery, as explained by Theorem 1. If π is to be processed, the algorithm will generate a set of rendezvouses ${\Upsilon }_{\text{r}}(\pi )$ for delivering resources for π. Lines 6–8 removes the obsolete ${\Upsilon }_{\text{r}}(\pi )$ which are generated in previous processing by this algorithm. Lines 9–34 consists of a while loop which generates resource-delivering rendezvouses and add them to ${\Upsilon }_{\text{r}}(\pi )$ , until π becomes feasible (i.e. ${\widehat{\mathbb{T}}}_{\text{fsb}}[\pi ]$ ), or fails to find a way to make π feasible (i.e. $b_{\text{fail}}$ ). We use $k$ to record the current number of iterations in the while loop. We use ${\Sigma }_{\text{r}}$ to record the robots that have already agreed to provide resources to π in the previous iterations of the while loop and therefore do not need to be requested in this iteration. In k th iteration, it searches (in lines 12–26) for the proper robot σ that can provide as many required resources with as low additional cost as possible. The robot of schedule σ is expected to conduct a rendezvous ${\upsilon }_{\pi ,k}=\left\{{\pi }_{\text{c},\pi ,k},{\pi }_{\text{p},\pi ,k}\right\}$ with ${\sigma }^{\prime }$ to obtain the resources $R_{\pi ,k}$ , where ${\pi }_{\text{c},\pi ,k}$ (and ${\pi }_{\text{p},\pi ,k}$ ) will be respectively executed by σ (and ${\sigma }^{\prime }$ ) for delivering $R_{\pi ,k}$ from ${\sigma }^{\prime }$ to σ and will be respectively inserted at $\chi (\sigma )$ (and $\chi ({\sigma }^{\prime })$ ) (as shown by lines 13–15). Lines 16–18 initialises the resources $R_{\pi ,k}=\Delta R({\pi }_{\text{c},\pi ,k})=\Delta R({\pi }_{\text{p},\pi ,k})$ to be delivered from ${\sigma }^{\prime }$ to σ by ${\upsilon }_{\pi ,k}$ . Lines 19–20 initialises the rendezvous position $x({\pi }_{\text{c},\pi ,k})=x({\pi }_{\text{p},\pi ,k})$ that minimises the travelling distance for both robots participating in the rendezvous ${\upsilon }_{\pi ,k}$ . Lines 21–22 simulates the effect of inserting ${\upsilon }_{\pi ,k}$ into σ and ${\sigma }^{\prime }$ . Line 23 preserves the effect of the insertion into a SMO ${\mu }_{\pi ,k}$ which is added to the set ${\text{M}}_{\pi ,k}$ and is later used to evaluate the different resource providers in $\Sigma \backslash \left\{\sigma \right\}$ . After all possible ${\mu }_{\pi ,k}$ are generated, line 26 selects the best SMO ${\mu }_{\pi ,k}^{\star }$ from ${\text{M}}_{\pi ,k}$ , which maximises the function $\varphi (\mu )$ that evaluates the effectiveness of each $\mu \in {\text{M}}_{\pi ,k}$ in satisfying the resource demands of π while improving the feasibility of the MR schedules Σ. The function $\varphi (\mu )$ is defined as below

$\varphi (\mu )={\displaystyle \sum _{i=1}^{N_{\varphi }}}{w}_i\cdot \text{tanh}\frac{{\varphi }_i(\mu )}{A_i}$

21

which combines $N_{\varphi }$ different optimisation objectives into one, where for each $i\in \{1,\mathrm{...},N_{\varphi }\}$ , (1) $w_i$ is an adjustable weight of the i th objective ${\varphi }_i(\mu )$ ; (2) $A_i$ is an adjustable amplification coefficient for ${\varphi }_i(\mu )$ , which adjusts the sensitivity of the tanh function to ${\varphi }_i(\mu )$ ; (3) ${\varphi }_i(\mu )$ measures from one specific aspect the effectiveness of applying the SMO μ. In this article, we use $N_{\varphi }=3$ optimisation objectives for the insertion of resource-delivering tasks. These objectives are:

(1) The improvement (after executing μ) of the degree of satisfaction of the resource demand of task π, which is denoted as ${\varphi }_1(\mu )$ , and is defined as below

${\varphi }_1(\mu )=d_{\text{stf}}\left(\mu (\sigma ),\pi \right)-d_{\text{stf}}(\sigma ,\pi )$

22

where $d_{\text{stf}}:\Sigma \times \Pi \to [0,1]$ is a function, which, for each schedule $\sigma \in \Sigma$ and $\pi \in \Pi$ , $d_{\text{stf}}(\sigma ,\pi )$ returns the degree of satisfaction of $R_{⊲}(\pi )$ in its current position in σ, that is,

$d_{\text{stf}}(\sigma ,\pi )={\displaystyle \sum _{y\in Y}}\frac{\left(R_{⊳}({\pi }_{i-1}) \tilde{\cap } R_{⊲}({\pi }_i)\right)(y)}{R_{⊲}(\pi )(y)}/|Y(R_{⊲}(\pi ))|$

23

where ${\pi }_i=\pi$ , ${\pi }_{i-1}=\sigma ({\iota }_{\sigma }(\pi )-1)$ and $\mu (\sigma )$ is the new schedule resulting from the execution of μ on σ. This is the major optimisation objective in $\varphi (\mu )$ and is given the highest weight, since the algorithm is expected to finish acquiring resources for π in as few rendezvouses as possible. If the rendezvous ${\upsilon }_{\pi ,k}$ to be inserted by μ is infeasible itself, possibly due to insufficient residual resources for both robots participating in ${\upsilon }_{\pi ,k}$ , inserting ${\upsilon }_{\pi ,k}$ will result in the decrease of the degree of satisfaction $d_{\text{stf}}(\sigma ,\pi )$ , that is, ${\varphi }_1(\mu )<0$ , and will not be selected in the first place (see also equation (26)).

(2) The improvement (after executing μ) of the degree of feasibility of the MR schedules Σ, which is denoted as ${\varphi }_2(\mu )$ , is defined as below

${\varphi }_2(\mu )=d_{\text{fsb}}(\mu (\Sigma ))-d_{\text{fsb}}(\Sigma )$

24

where $\mu (\Sigma )$ is the new MR schedules resulting from the execution of μ on Σ.

(3) The improvement (after executing μ) of the cost of the MR schedules Σ, which is denoted as ${\varphi }_3(\mu )$ , is defined as below

${\varphi }_3(\mu )=-\left(\parallel \mu (\Sigma )\parallel -\parallel \Sigma \parallel \right)$

25

where the negative sign is used because we want the cost to be as low as possible.

The above three objectives should comply with the following constraints

${\varphi }_1(\mu )>0,{\varphi }_2(\mu )\ge 0$

26

After the ${\mu }_{\pi ,k}^{\star }$ is successfully chosen (i.e. ${\mu }_{\pi ,k}^{\star }\ne \perp$ ), ${\mu }_{\pi ,k}^{\star }$ is applied onto Σ, $\upsilon ({\mu }_{\pi ,k}^{\star })$ (i.e. the rendezvous added by ${\mu }_{\pi ,k}^{\star }$ ) is added to the rendezvous set ${\Upsilon }_{\text{r}}(\pi )$ , and the current search frontier χ is updated (as shown in lines 28–30). If Algorithm 1 fails to find a valid rendezvous (i.e. ${\mu }_{\pi ,k}^{\star }=\perp$ ), then (in line 32) all the previously generated rendezvouses in ${\Upsilon }_{\text{r}}(\pi )$ should be removed, $b_{\text{fail}}$ is set to be $true$ , and the while loop of lines 10–34 terminates.

Figure 2 shows the structure of rendezvous set ${\Upsilon }_{\text{r}}(\pi )$ which is used by the MRS to deliver the resources from other robots to the robot owning task π, to satisfy the resource demand $R_{⊲}(\pi )$ of π. Assume before ${\Upsilon }_{\text{r}}(\pi )$ is inserted, the $R_{⊲}(\pi )$ is only partially satisfied by the residual resource $R_{⊳}\left(\sigma ({\iota }_{\sigma }(\pi )-1)\right)$ . Then the additional resource required to be provided by ${\Upsilon }_{\text{r}}(\pi )$ is $R_{⊲}(\pi ) \tilde{\backslash } R_{⊳}\left(\sigma ({\iota }_{\sigma }(\pi )-1)\right)$ . Assume ${\Upsilon }_{\text{r}}(\pi )=\{{\upsilon }_1\mathrm{,...},{\upsilon }_n\}$ , where each rendezvous ${\upsilon }_k\in {\Upsilon }_{\text{r}}(\pi )$ (generated in k th iteration) is responsible of providing resource $R_{\pi ,k}$ that constitutes part of the required resources. Then under ideal situation, ${\displaystyle {\cup }_{i=0}^n}{R}_i=R_{⊲}(\pi ) \tilde{\backslash } R_{⊳}\left(\sigma ({\iota }_{\sigma }(\pi )-1)\right)$ .

Figure 2.

Structure of rendezvous set ${\Upsilon }_{\text{r}}(\pi )$ for acquiring resources for task π.

Theorem 1 guarantees that the execution of Algorithm 1 will not introduce cycles into the MR schedules, thereby ensuring the deadlock-free schedules.

Theorem 1

Deadlock-free schedules. If the MR schedules before and after Algorithm 1 are respectively Σ and ${\Sigma }^{\prime }$ , where Σ is not cyclic and ${\Sigma }^{\prime }$ is not cyclic

Proof

Use mathematical induction. Assume the order of tasks being processed by Algorithm 1 is ${\pi }_1\mathrm{,...},{\pi }_n$ . Assume initially the MR schedules is $\Sigma ={\Sigma }_0$ . The schedules before and after each task ${\pi }_i$ being processed by Algorithm 1, are denoted as ${\Sigma }_{i-1}$ and ${\Sigma }_i$ , respectively. The final schedules is ${\Sigma }_n={\Sigma }^{\prime }$ . For the base case, obviously, according to the premise, ${\Sigma }_0$ is not cyclic. For the induction step, we need to prove that, if ${\Sigma }_{i-1}$ is not cyclic, then ${\Sigma }_i$ is not cyclic.

We now use reductio ad absurdum (In logic, reductio ad absurdum is a form of argument that attempts either to disprove a statement by showing it inevitably leads to a ridiculous, absurd or impractical conclusion, or to prove one by showing that if it were not true, the result would be absurd or impossible.) to prove the induction step. Given ${\Sigma }_{i-1}$ is not cyclic, assume ${\Sigma }_i$ is cyclic. Then there must be a set of cycles $C$ within the MR schedules ${\Sigma }_i$ , in which each cycle $c\in C$ consists of a set of tasks, which satisfy $\forall \pi ,{\pi }^{\prime }\in c:\pi {\prec }^{\star }{\pi }^{\prime }$ . Since ${\Sigma }_{i-1}$ is not cyclic, while ${\Sigma }_i$ is cyclic; and the only difference between ${\Sigma }_{i-1}$ and ${\Sigma }_i$ is that after ${\pi }_i$ is processed by Algorithm 1, a set of rendezvouses ${\Upsilon }_{\text{r}}({\pi }_i)=\left\{{\upsilon }_1=\{{\pi }_{\text{p}\mathrm{,1}},{\pi }_{\text{c}\mathrm{,1}}\}\mathrm{,...},{\upsilon }_K={\pi }_{\text{p},K},{\pi }_{\text{c},K}\right\}$ is inserted into ${\Sigma }_{i-1}$ to produce ${\Sigma }_i$ . Obviously, the cycles C must involve ${\Upsilon }_{\text{r}}({\pi }_i)$ , that is, ${\displaystyle {\cup }_{c\in C}}c\cap {\displaystyle {\cup }_{\upsilon \in {\Upsilon }_{\text{r}}({\pi }_i)}}\upsilon \ne \mathrm{Ø}$ , otherwise ${\Sigma }_{i-1}$ is cyclic, which is contradictory to the premise. Also note that the cycles C must also contain at least one task ${\pi }^{\prime }$ which is already in the schedules ${\Sigma }_{i-1}$ , that is, ${\displaystyle {\cup }_{c\in C}}c\cap {\displaystyle {\cup }_{\sigma \in {\Sigma }_{i-1}}}\sigma \ne \text{Ø}$ , otherwise it means that the cycles C consists solely of the tasks involved in the newly added rendezvouses ${\Upsilon }_{\text{r}}({\pi }_i)$ , which is impossible, because the ${\Upsilon }_{\text{r}}({\pi }_i)$ itself doesn’t contain any cycles, as shown in Figure 2. Given these conditions, we can enumerate the general cases in which the MR schedules Σ becomes cyclic as a result of inserting ${\Upsilon }_{\text{r}}({\pi }_i)$ , as shown in Figure 3.

Figure 3.

The general cases in which the MR schedules ${\Sigma }_{i-1}$ becomes cyclic ${\Sigma }_i$ as a result of inserting the set of rendezvouses ${\Upsilon }_{\text{r}}({\pi }_i)$ . A dashed arrow ‘ $\to$ ’ connecting task π to task ${\pi }^{\prime }$ indicates that $\pi {\prec }^{\star }{\pi }^{\prime }$ .

Case 1 (1 rendezvous is involved in the cycle)

Initially Σ is not cyclic, as shown in Figure 3 (1-1). After the set of rendezvouses ${\Upsilon }_{\text{r}}({\pi }_i)$ is inserted into Σ, the Σ becomes cyclic as the tasks $\pi ={\pi }_i,{\pi }^{\prime }$ and ${\pi }_{\text{p},k},{\pi }_{\text{c},k}\in {\Upsilon }_{\text{r}}({\pi }_i)$ are connected into a cycle (as shown in Figure 3 (1-2)), where (1) ${\pi }_{\text{p},k}$ and ${\pi }^{\prime }$ belong to the same schedule ${\sigma }^{\prime }$ ; (2) ${\pi }_{\text{p},k}$ and ${\pi }_{\text{c},k}$ belong to the same rendezvous ${\upsilon }_k\in {\Upsilon }_{\text{r}}({\pi }_i)$

Now we show that the case 1 will lead to contradiction.

First, as shown by the condition at line 5 in Algorithm 1, the infeasible tasks in ${\Sigma }_{i-1}$ must be processed by Algorithm 1 in the order specified by the ${\prec }^{\star }$ relation among them. Also, as shown in Figure 3 (1-1), $\pi {\prec }^{\star }{\pi }^{\prime }$ in ${\Sigma }_{i-1}$ . Hence, ${\pi }^{\prime }$ must be processed by Algorithm 1 ( to become feasible) after π become feasible, provided that π is not feasible.

Also, as shown by line 14 and lines 21–22 in Algorithm 1, resource-providing tasks such as ${\pi }_{\text{p},k}$ can only be inserted at $\chi ({\sigma }^{\prime })$ , to not influence the feasible part of σ. Since ${\pi }^{\prime }$ is not feasible (according to $\pi {\prec }^{\star }{\pi }^{\prime }$ and the definition of feasibility of each task), ${\pi }^{\prime }$ must be situated before $\chi ({\sigma }^{\prime })$ . Hence, there is no way that ${\pi }_{\text{p},k}$ be inserted before ${\pi }^{\prime }$ , otherwise ${\pi }^{\prime }$ must be already feasible in ${\Sigma }_{i-1}$ , which is contradictory with the aforementioned fact that ${\pi }^{\prime }$ cannot become feasible as long as π is not feasible.

Case 2 (2 rendezvouses are involved in the cycle)

Initially Σ is not cyclic, as shown in Figure 3 (2-1). After the set of rendezvouses ${\Upsilon }_{\text{r}}({\pi }_i)$ is inserted into Σ, the Σ becomes cyclic as the tasks ${\pi }^{\prime },\pi ″$ and ${\pi }_{\text{p},k},{\pi }_{\text{c},k},{\pi }_{\text{p},l},{\pi }_{\text{c},l}\in {\Upsilon }_{\text{r}}({\pi }_i)$ are connected into a cycle (as shown in Figure 3 (2-2)), where (1) ${\pi }_{\text{p},k}$ and ${\pi }^{\prime }$ belong to the same schedule ${\sigma }^{\prime }$ ; (2) ${\pi }_{\text{p},l}$ and $\pi ″$ belong to the same schedule ${{\sigma }^{\prime }}^{\prime }$ ; (3) ${\pi }_{\text{p},k}$ and ${\pi }_{\text{c},k}$ belong to the same rendezvous ${\upsilon }_k$ ; (4) ${\pi }_{\text{p},l}$ and ${\pi }_{\text{c},l}$ belong to the same rendezvous ${\upsilon }_l$

Now we show that the case 2 will lead to contradiction.

Similar to case 1, since $\pi ″{\prec }^{\star }{\pi }^{\prime }$ , thus ${\pi }^{\prime }$ can become feasible only after $\pi ″$ becomes feasible. However, according to the current insertion positions of ${\pi }_{\text{p},k}$ and ${\pi }_{\text{p},l}$ in the schedules, as shown by Figure 3 (2-2), (1) since ${\pi }_{\text{p},k}$ is inserted after ${\pi }^{\prime }$ , ${\pi }^{\prime }$ is feasible in ${\Sigma }_{i-1}$ ; (2) since ${\pi }_{\text{p},l}$ is inserted before $\pi ″$ , $\pi ″$ is not feasible in ${\Sigma }_{i-1}$ . This is in contradiction with the requirement that ${\pi }^{\prime }$ can become feasible only after $\pi ″$ becomes feasible. $\square$

Theorem 2 ensures that under Algorithm 1, the feasibility of every schedule $\sigma \in \Sigma$ is improved monotonically.

Theorem 2

Monotonic improvement of feasibility. If the MR schedules before and after Algorithm 1 are respectively Σ and ${\Sigma }^{\prime }=\mu (\Sigma )$ , then $d_{\text{fsb}}({\Sigma }^{\prime })\ge d_{\text{fsb}}(\Sigma )$ , and $\forall \sigma \in \Sigma :d_{\text{fsb}}(\mu (\sigma ))\ge d_{\text{fsb}}(\sigma )$

Proof

Assume the order of tasks being processed by Algorithm 1 is ${\pi }_1\mathrm{,...},{\pi }_n$ . Assume initially the MR schedules is $\Sigma ={\Sigma }_0$ . The schedules before and after each task ${\pi }_i$ being processed by Algorithm 1, are denoted as ${\Sigma }_{i-1}$ and ${\Sigma }_i$ , respectively. The final schedules is ${\Sigma }_n={\Sigma }^{\prime }$ . For each $i=1,\mathrm{\dots },n$ , let ${\mu }_i$ be the SMO that transforms ${\Sigma }_{i-1}$ to ${\Sigma }_i$ , so that ${\Sigma }_i=\left\{{\sigma }_{i\mathrm{,1}}\mathrm{,\dots },{\sigma }_{i,m}\right\}={\mu }_i({\Sigma }_{i-1})=\left\{{\mu }_i({\sigma }_{i-1,1})\mathrm{,\dots },{\mu }_i({\sigma }_{i-1,m})\right\}$ . According to the premise of Algorithm 1, initially (1) the schedule Σ is infeasible, that is, $d_{\text{fsb}}({\Sigma }_0)=0$ ; (2) the frontier χ is at the beginning position, that is, $\chi {|}_{{\Sigma }_0}=0$ . Figure 4 shows the layout of the schedules of the MRS before and after applying the SMO ${\mu }_i$ , which are denoted as ${\Sigma }_{i-1}$ and ${\Sigma }_i$ , respectively.

Figure 4.

The effect of inserting the set of rendezvouses ${\Upsilon }_{\text{r}}({\pi }_i)$ on the MR schedules. Assume ${\Upsilon }_{\text{r}}({\pi }_i)$ contains two rendezvouses: $〈{\pi }_{\text{p}\mathrm{,1}},{\pi }_{\text{c}\mathrm{,1}}〉$ and $〈{\pi }_{\text{p}\mathrm{,2}},{\pi }_{\text{c}\mathrm{,2}}〉$ , without loss of generality. A white-coloured symbol represents such a task π which falls before the search frontier χ, that is, ${\iota }_{\sigma }(\pi )<\chi (\sigma )$ . A dark-coloured symbol represents such a task π which falls after the search frontier χ, that is, ${\iota }_{\sigma }(\pi )\ge \chi (\sigma )$ . (a) Schedules and the search frontier before inserting the rendezvouses and (b) schedules and the search frontier after inserting the rendezvouses.

By definition, before applying ${\mu }_i$ to insert ${\Upsilon }_{\text{r}}({\pi }_i)$ into ${\Sigma }_{i-1}$ , feasibility $d_{\text{fsb},y}(\sigma )$ of each schedule $\sigma \in {\Sigma }_{i-1}$ w.r.t. y-type resource can be unanimously expressed by equation (27).

$d_{\text{fsb},y}(\sigma )=\frac{{\displaystyle {\sum }_{\pi \in \sigma ,{\widehat{\mathbb{T}}}_{\text{fsb}}[\pi ]}{R}_{⊲}(\pi )(y)}}{{\displaystyle {\sum }_{\pi \in \sigma }{R}_{⊲}(\pi )(y)}}=\frac{R_{⊲}{|}_1^{\chi (\sigma )-1}}{R_{⊲}{|}_1^{\chi (\sigma )-1}+R_{⊲}{|}_{\chi (\sigma )}^{|\sigma |}}$

27

where $R_{⊲}{|}_{j_1}^{j_2}={\displaystyle \sum _{j=j_1}^{j_2}}{R}_{⊲}(\sigma (j))(y)$ for $1\le j_1\le j_2\le \hspace{0.17em}|\sigma |$ .

After applying ${\mu }_i$ , which inserts ${\Upsilon }_{\text{r}}({\pi }_i)$ into ${\Sigma }_{i-1}$ , the feasibility $d_{\text{fsb}}({\mu }_i(\sigma ))$ of each schedule $\sigma \in {\Sigma }_{i-1}$ can be expressed respectively under following cases:

Case 1 (receive resource)

Schedule σ satisfies ${\pi }_i\in \sigma$ for which the set of rendezvouses ${\Upsilon }_{\text{r}}({\pi }_i)$ is generated by Algorithm 1. Then, after inserting ${\Upsilon }_{\text{r}}({\pi }_i)$ by SMO ${\mu }_i$ , a series of resource-receiving tasks ${\pi }_{\text{c}\mathrm{,1}}\mathrm{,...},{\pi }_{\text{c},|{\Upsilon }_{\text{r}}({\pi }_i)|}$ will be inserted before task ${\pi }_i$ , making ${\pi }_i$ feasible. In this case, the feasibility of ${\mu }_i(\sigma )$ w.r.t. y-type resource can be expressed by equation (28)

$d_{\text{fsb},y}\left({\mu }_i(\sigma )\right)=\frac{R_{⊲}{|}_1^{\chi (\sigma )-1}+{\displaystyle \sum _{k=1}^{|{\Upsilon }_{\text{r}}({\pi }_i)|}}{R}_{⊲}({\pi }_{\text{c},k})(y)}{R_{⊲}{|}_1^{\chi (\sigma )-1}+{\displaystyle \sum _{k=1}^{|{\Upsilon }_{\text{r}}({\pi }_i)|}}{R}_{⊲}({\pi }_{\text{c},k})(y)+R_{⊲}{|}_{\chi (\sigma )}^{|\sigma |}}$

28

Case 2 (provide resource)

A resource-providing task ${\pi }_{\text{p},k}$ is inserted into schedule σ by SMO ${\mu }_i$ . Then, the feasibility of ${\mu }_i(\sigma )$ w.r.t. y-type resource can be expressed by equation (29)

$d_{\text{fsb},y}\left({\mu }_i(\sigma )\right)=\frac{R_{⊲}{|}_1^{\chi (\sigma )-1}+R_{⊲}({\pi }_{\text{p},k})(y)}{R_{⊲}{|}_1^{\chi (\sigma )-1}+R_{⊲}({\pi }_{\text{p},k})(y)+R_{⊲}{|}_{\chi (\sigma )}^{|\sigma |}}$

29

For both Case 1 and Case 2, obviously, equation (30) holds

$d_{\text{fsb},y}\left({\mu }_i(\sigma )\right)-d_{\text{fsb},y}(\sigma )>0$

30

Case 3 (not affected)

Schedule σ is not affected by insertion of ${\Upsilon }_{\text{r}}({\pi }_i)$ , i.e. $\sigma ={\mu }_i(\sigma )$ . Then obviously the feasibility of σ will not change, that is, equation (31) holds

$d_{\text{fsb},y}\left({\mu }_i(\sigma )\right)-d_{\text{fsb},y}(\sigma )=0$

31

From Case 1, 2, 3 shown above, we have equation (32)

$d_{\text{fsb},y}\left({\mu }_i(\sigma )\right)-d_{\text{fsb},y}(\sigma )\ge 0$

32

Since for Case 1, 2, 3, inserting rendezvouses doesn’t introduce new types of resources, hence we have equation (33)

${\displaystyle \underset{\pi \in \sigma }{\cup }}Y\left(R_{⊲}(\pi )\right)={\displaystyle \underset{\pi \in {\mu }_i(\sigma )}{\cup }}Y\left(R_{⊲}(\pi )\right)$

33

Hence, according to the definition of degree of feasibility (w.r.t. each schedule σ) given by equation (13), we have equation (34) for schedules ${\Sigma }_{i-1}$

$d_{\text{fsb}}({\mu }_i(\sigma ))-d_{\text{fsb}}(\sigma )\ge 0$

34

Hence, according to the definition of degree of feasibility (w.r.t. entire MR schedules Σ) given by equation (14), we have equation (35).

$d_{\text{fsb}}\left({\mu }_i({\Sigma }_{i-1})\right)-d_{\text{fsb}}({\Sigma }_{i-1})\ge 0$

35

Applying equation (34) to all $n$ steps, we get equation (36)

$d_{\text{fsb}}({\sigma }^{\prime })-d_{\text{fsb}}(\sigma )=d_{\text{fsb}}(\mu (\sigma ))-d_{\text{fsb}}(\sigma )\ge 0$

36

Therefore $\forall \sigma \in \Sigma :d_{\text{fsb}}({\sigma }^{\prime })\ge d_{\text{fsb}}(\sigma )$ .

Applying equation (35) to all n steps, we get equation (37)

$d_{\text{fsb}}({\Sigma }^{\prime })-d_{\text{fsb}}(\Sigma )=d_{\text{fsb}}\left(\mu (\Sigma )\right)-d_{\text{fsb}}(\Sigma )\ge 0$

37

Therefore $d_{\text{fsb}}(\Sigma )\ge d_{\text{fsb}}(\Sigma )$ . □

Computational complexity

The accurate analysis of the complexity requires considering the influence of concrete probabilistic distribution of residual resources and resource demands. For simplicity, we only concern the worst-case complexity, when (1) all tasks are infeasible at the beginning of Algorithm 1; (2) after the resource demand of each task π in schedule σ is satisfied, the tasks succeeding π in σ still cannot be satisfied by the residual resource of σ, that is, all tasks need rendezvous to provide resources. Assume Algorithm 1 is implemented in a centralised and single-threaded manner. For each infeasible task π, in the worst case, each robot σ needs to conduct one rendezvous with every other robot in $\Sigma \backslash \left\{\sigma \right\}$ to obtain all the required resources. Hence, the worst-case computational cost of the while loop in lines 10–34 is $O(|\Sigma |\cdot (|\Sigma |-1)/2)$ . Since the count of all tasks in Σ is ${\displaystyle {\sum }_{\sigma \in \Sigma }}|\sigma |$ , the worst-case complexity of entire algorithm can be approximated as

$O\left({\displaystyle \sum _{\sigma \in \Sigma }}|\sigma |\cdot |\Sigma |\cdot (|\Sigma |-1)/2\right)$

38

The complexity of Algorithm 1 can be reduced by realising the algorithm in a distributed manner, so that each robot is only responsible of maintaining the feasibility of its own schedule and responding to the request from other robots to establish rendezvouses. The distributed realisation of Algorithm 1 is beyond the scope of this article and will be discussed in our future research.

Task reallocation algorithm

This section presents a greedy algorithm (Algorithm 2), as shown by Figure 5, which is periodically invoked, and is intended to maintain the cost-efficiency of the MR schedules Σ, by reallocating the allocation bundles U among Σ. Nanjanath et al. ¹⁹ have shown that the cost of Σ (especially when the locations of the tasks in the physical environment are dynamically changing) can be significantly reduced by allowing robots to repeatedly reallocate among themselves their tasks. In this article, we intend to use this algorithm as a means to (1) reduce the cost resulting from the introduction of rendezvouses for inter-robot resource delivery and (2) take any opportunity to improve the feasibility of Σ by reallocating the tasks to those robots that have sufficient residual resources to support their execution.

Figure 5.

A greedy algorithm for reducing the cost of the MR schedules via task reallocation. MR: multi-robot.

Since each allocation bundle $u\in U$ may contain multiple tasks, the operation of the algorithm contains the following two levels: (1) for each $u\in U$ , find the target schedule σ to which U can be allocated, as shown by lines 1–30; (2) for each $\pi \in u$ , and the target schedule σ to that U is supposed to be allocated, find the best way to insert π into the σ, as shown by lines 5–19.

In the first level (lines 1–30), for each $u\in U$ , Algorithm 2 first removes U from Σ (as shown in line 2), and then for each σ that satisfies the rule that the tasks within the same rendezvous must be assigned to different robots (as shown in line 3), Algorithm 2 attempts to insert U into σ, through the second level (lines 5–19). All the possible ways to reinsert U are preserved (by line 21) in the set of SMOs ${\text{M}}_u$ . Line 22 invokes Algorithm 1 to simulate the influence of insertion operation ${\mu }_u$ on the MR schedules Σ, which embodies also the set of rendezvouses ${\Upsilon }_{\text{r}}(\Sigma )={\displaystyle {\cup }_{\sigma \in \Sigma }}{\displaystyle {\cup }_{\pi \in \sigma }}{\Upsilon }_{\text{r}}(\pi )$ generated by Algorithm 1. The influence of the invocation to Algorithm 1 is preserved in the SMO ${\mu }_{\text{fsb}}({\mu }_u)$ (as shown in line 23). Line 27 selects the best SMO ${\mu }_u^{\star }$ from ${\text{M}}_u$ which maximises the function $\varphi (\mu )$ defined by equation (39), where $\mu ={\mu }_{\text{fsb}}({\mu }_u)\circ {\mu }_u$ , which indicates that $\varphi (\mu )$ considers the influence of ${\mu }_u$ on ${\Upsilon }_{\text{r}}(\Sigma )$ (which will be generated in the future by Algorithm 1) rather than merely the current schedules Σ. If ${\mu }_u^{\star }$ is successfully found (i.e. ${\mu }_u^{\star }\ne \perp$ ), then ${\mu }_u^{\star }$ is applied to the current MR schedules Σ (as shown in line 28), by reinserting U. Otherwise, U will remain in its original position in Σ. The function $\varphi (\mu )$ for evaluating the effectiveness of each SMO μ is defined as below

$\varphi (\mu )={\displaystyle \sum _{i=1}^{N_{\varphi }}}{w}_i\cdot \text{tanh}\frac{{\varphi }_i(\mu )}{A_i}$

39

which is defined in the same manner as equation (21). In this case, we use $N_{\varphi }=2$ optimisation objectives for the reinsertion of allocation bundles. These objectives are

${\varphi }_1(\mu )=-\left(\parallel \mu (\Sigma )\parallel -\parallel \Sigma \parallel \right)$

40

${\varphi }_2(\mu )=d_{\text{fsb}}\left(\mu (\Sigma )\right)-d_{\text{fsb}}(\Sigma )$

41

The above objectives should comply with the following constraints

${\varphi }_1(\mu )>0, {\varphi }_2(\mu )\ge 0$

42

which means that the optimisation step in Algorithm 2 only accepts positive improvement of the cost $\parallel \Sigma \parallel$ and will not accept lowering the feasibility $d_{\text{fsb}}(\Sigma )$ .

In the second level (lines 5–19), for the $u\in U$ to be reinserted to σ, Algorithm 2 finds the best way to insert each task $\pi \in u$ into σ. Lines 7–12 attempts to insert π to each position $i\in \left({\underset{\_}{\iota }}_{\sigma }(\pi ),{\overline{\iota }}_{\sigma }(\pi )\right]$ , where ${\underset{\_}{\iota }}_{\sigma }(\pi )$ (and ${\overline{\iota }}_{\sigma }(\pi )$ ) are, respectively, the lower (and upper) bound of ${\iota }_{\sigma }(\pi )$ , that is, the index of π in σ, which are defined as below

${\underset{\_}{\iota }}_{\sigma }(\pi )=\underset{{\pi }^{\prime }\in {\widehat{\Pi }}_{\star \leftarrow }({\pi }^{\prime })}{{\displaystyle \text{max}}}{\iota }_{\sigma }({\pi }^{\prime }), {\overline{\iota }}_{\sigma }(\pi )=\underset{{\pi }^{\prime }\in {\widehat{\Pi }}_{\to \star }({\pi }^{\prime })}{{\displaystyle \text{min}}}{\iota }_{\sigma }({\pi }^{\prime })$

43

where ${\widehat{\Pi }}_{\star \leftarrow }(\pi )$ and ${\widehat{\Pi }}_{\to \star }(\pi )$ are, respectively, the set of tasks that precede or succeed π in terms of ${\prec }^{\star }$ relation, as defined by equations (44) and (45)

${\widehat{\Pi }}_{\star \leftarrow }(\pi )=\left\{{\pi }^{\prime }\in \Pi :{\pi }^{\prime }{\prec }^{\star }\pi \right\}$

44

${\widehat{\Pi }}_{\to \star }(\pi )=\left\{{\pi }^{\prime }\in \Pi :{\pi }^{\prime }{\succ }^{\star }\pi \right\}$

45

According to Theorem 3, as long as ${\iota }_{\sigma }(\pi )$ (i.e. the index of every task π in schedule σ) satisfies ${\iota }_{\sigma }(\pi )\in \left({\underset{\_}{\iota }}_{\sigma }(\pi ),{\overline{\iota }}_{\sigma }(\pi )\right)$ after being inserted to σ, π will not be cyclic. Lines 8–9 attempts to insert π to index i in σ, and preserve the corresponding SMO into ${\text{M}}_{\pi }$ . Similar to lines 22–23 in the first level, lines 10–11 invokes the Algorithm 1 and preserves the effect of Algorithm 1 in ${\mu }_{\text{fsb}}({\mu }_{\pi })$ . If ${\text{M}}_{\pi }$ is not empty, then lines 13–18 first selects (see line 14) the best SMO ${\mu }_{\pi }^{\star }$ for inserting π with maximal $\varphi (\mu )$ , and if such ${\mu }_{\pi }^{\star }$ is found (see line 15), then (in line 16) it appends ${\mu }_{\pi }^{\star }$ to ${\mu }_u$ , which is the operation for inserting entire U. Similar to line 27 in the first level, in line 14, $\mu ={\mu }_{\text{fsb}}({\mu }_{\pi })\circ {\mu }_{\pi }\circ {\mu }_u$ , to consider the influence of ${\mu }_{\pi }$ on ${\Upsilon }_{\text{r}}(\Sigma )$ .

Theorem 3

For any schedule $\sigma \in \Sigma$ , task $\pi \in \sigma$

${\underset{\_}{\iota }}_{\sigma }(\pi )<{\iota }_{\sigma }(\pi )<{\overline{\iota }}_{\sigma }(\pi )\hspace{1em}\iff \hspace{1em}\pi \text{ is not cyclic}$

46

Proof

Prove $\neg \left({\underset{\_}{\iota }}_{\sigma }(\pi )<{\iota }_{\sigma }(\pi )<{\overline{\iota }}_{\sigma }(\pi )\right)\Rightarrow \pi \text{ is }cyclic$ . If $\neg \left({\underset{\_}{\iota }}_{\sigma }(\pi )<{\iota }_{\sigma }(\pi )<{\overline{\iota }}_{\sigma }(\pi )\right)$ , then one of the following conditions must hold

1. ${\underset{\_}{\iota }}_{\sigma }({\pi }^{\prime })={{\displaystyle \text{max}}}_{{\pi }^{\prime }\in {\widehat{\Pi }}_{\star \leftarrow }(\pi )}\hspace{0.17em}{\iota }_{\sigma }(\pi )\ge {\iota }_{\sigma }(\pi )$ . This means that there exists ${\pi }^{\prime }\in {\widehat{\Pi }}_{\star \leftarrow }(\pi )$ that satisfies ${\iota }_{\sigma }({\pi }^{\prime })\ge {\iota }_{\sigma }(\pi )$ . This can be further divided into following two cases:

2. ${\iota }_{\sigma }({\pi }^{\prime })>{\iota }_{\sigma }(\pi )$ . Thus ${\pi }^{\prime }\in {\Pi }_{⊳}(\pi )$ , that is, $\pi \stackrel{\text{s}}{{\displaystyle \to }}\hspace{0.17em}{\pi }^{\prime }$ . Hence $\pi {\prec }^{\star }{\pi }^{\prime }$ . Since ${\pi }^{\prime }\in {\widehat{\Pi }}_{\star \leftarrow }(\pi )$ , hence ${\pi }^{\prime }{\prec }^{\star }\pi$ . Hence π is cyclic.

${\overline{\iota }}_{\sigma }({\pi }^{\prime })={{\displaystyle \text{min}}}_{{\pi }^{\prime }\in {\widehat{\Pi }}_{\to \star }(\pi )}{\iota }_{\sigma }(\pi )\le {\iota }_{\sigma }(\pi )$ . This means that there exists ${\pi }^{\prime }\in {\widehat{\Pi }}_{\to \star }(\pi )$ that satisfies ${\iota }_{\sigma }({\pi }^{\prime })\le {\iota }_{\sigma }(\pi )$ . This can be further divided into following two cases:

${\iota }_{\sigma }({\pi }^{\prime })={\iota }_{\sigma }(\pi )$ . Thus $\pi ={\pi }^{\prime }$ . Since ${\pi }^{\prime }\in {\widehat{\Pi }}_{\to \star }(\pi )$ , thus ${\pi }^{\prime }{\succ }^{\star }\pi$ . Hence $\pi {\succ }^{\star }\pi$ . Hence obviously π is cyclic.

${\iota }_{\sigma }({\pi }^{\prime })<{\iota }_{\sigma }(\pi )$ . Thus ${\pi }^{\prime }\in {\Pi }_{⊲}(\pi )$ , that is, ${\pi }^{\prime }\stackrel{\text{s}}{{\displaystyle \to }}\hspace{0.17em}\pi$ . Hence $\pi {\succ }^{\star }{\pi }^{\prime }$ . Since ${\pi }^{\prime }\in {\widehat{\Pi }}_{\to \star }(\pi )$ , hence ${\pi }^{\prime }{\succ }^{\star }\pi$ . Hence π is cyclic.

Prove $\pi \text{ is cyclic}\Rightarrow \neg ({\underset{\_}{\iota }}_{\sigma }(\pi )<{\iota }_{\sigma }(\pi )<{\overline{\iota }}_{\sigma }(\pi ))$ . Assume π is cyclic. Then there exists ${\pi }^{\prime }\in \Pi$ that satisfies ${\pi }^{\prime }{\prec }^{\star }\pi \wedge {\pi }^{\prime }{\succ }^{\star }\pi$ . Hence $\pi {\prec }^{\star }\pi$ . Hence $\pi \in {\widehat{\Pi }}_{\star \leftarrow }(\pi )\wedge \pi \in {\widehat{\Pi }}_{\to \star }(\pi )$ . Hence ${\underset{\_}{\iota }}_{\sigma }(\pi )={{\displaystyle \text{max}}}_{{\pi }^{\prime }\in {\widehat{\Pi }}_{\star \leftarrow }(\pi )}{\iota }_{\sigma }({\pi }^{\prime })\ge {\iota }_{\sigma }(\pi )$ and ${\overline{\iota }}_{\sigma }(\pi )={{\displaystyle \text{min}}}_{{\pi }^{\prime }\in {\widehat{\Pi }}_{\to \star }(\pi )}{\iota }_{\sigma }({\pi }^{\prime })\le {\iota }_{\sigma }(\pi )$ . □

Also, as shown in line 10 and line 21, at both first and second levels, Algorithm 2 estimates mutual impact between Algorithm 1 and Algorithm 2 by invoking Algorithm 1, which is supposed to improve the effectiveness of both Algorithm 1 and Algorithm 2 when they are integrated. The necessity of this consideration is shown through experiment in the ‘Experiment II. Necessity of considering inter-robot resource delivery in task reallocation’ section.

Computational complexity

Assume the ReAllocate algorithm is executed in a centralised and sequential manner for entire MRS. For each $\pi \in \sigma \in \Sigma$ , in the worst case, it requires to attempt reinserting π for ${\displaystyle {\sum }_{\sigma \in \Sigma }}(|\sigma |+1)$ times. Therefore, the total number of reinsertion attempts is

${\displaystyle \sum _{\sigma \in \Sigma }}{\displaystyle \sum _{\pi \in \sigma }}{\displaystyle \sum _{{\sigma }^{\prime }\in \Sigma }}(|{\sigma }^{\prime }|+1)={\displaystyle \sum _{\sigma \in \Sigma }}|\sigma |\cdot \left({\displaystyle \sum _{\sigma \in \Sigma }}|\sigma |+|\Sigma |\right)$

47

Therefore, the worst-case complexity of the ReAllocate algorithm

$O\left({\displaystyle \sum _{\sigma \in \Sigma }}|\sigma |\cdot \left({\displaystyle \sum _{\sigma \in \Sigma }}|\sigma |+|\Sigma |\right)\right)$

48

When the CreateRendezvous algorithm is explicitly considered and also implemented in a centralised and sequential manner, the complexity of the ReAllocate algorithm can be represented as

$O\left({\displaystyle \sum _{\sigma \in \Sigma }}|\sigma |\cdot \left({\displaystyle \sum _{\sigma \in \Sigma }}|\sigma |+|\Sigma |\right)\cdot {\displaystyle \sum _{\sigma \in \Sigma }}|\sigma |\cdot |\Sigma |\cdot (|\Sigma |-1)/2\right)$

49

The complexity of Algorithm 2 can be reduced by realising both Algorithm 1 and Algorithm 2 in a distributed manner. The distributed realisation of Algorithm 1 and Algorithm 2 is beyond the scope of this article and will be discussed in our future research.

Experiments

This section uses several random experiments to demonstrate the effectiveness of our method in dealing with the problems stated in ‘Problem statement’ section. For simplicity, our experiments use a single-threaded program which centrally manages the feasibility maintenance and task reallocation of all robots and which simulates a two-dimensional environment on which the robots are able to move according to the planned speed and direction. Robots are assumed to be homogeneous, that is, each robot possesses all the necessary capabilities to perform all types of tasks. The maximum speed of each robot is set to be the same for all robots. Each robot uses $A^{\star }$ algorithm to plan the path between different locations in the two-dimensional space. When a robot reaches the location corresponding to a specific task, it will stay for a limited period of time at the location and perform the task, which will cost the robot certain amount of resources. Our experiment focus on simulating the resource consumption of each task rather than the detailed operations performed by the robot for the task.

The rest of this section is organised as below. ‘Effectiveness of inter-robot resource delivery for maintaining feasibility’ section shows the effectiveness of applying Algorithm 1 (i.e. CreateRendezvous) on maintaining feasibility of the MR schedules. ‘Effect of persistent task reallocation on inter-robot resource delivery’ section shows the effect of applying Algorithm 2 (i.e. ReAllocate) on the effectiveness of feasibility maintenance of Algorithm 1. Both the abovementioned sections assume that fixed stations are unavailable and that feasibility maintenance solely relies on the randomly initialised residual resources of robots and the inter-robot resource delivery. ‘Effectiveness of inter-robot resource delivery in scenarios with fixed resource stations’ section shows the effectiveness of inter-robot delivery in the scenarios when fixed stations are available but are distant from the task locations. With the exception of ‘Experiment I. Effect of single execution of Algorithm 1’ section, in all experiments, the tasks assigned to robots have randomly generated locations and resource demands/consumptions which all follow uniform distribution. When new tasks are assigned to the MRS, the precedence constraints between the new tasks and the tasks originally in the schedules are randomly generated.

Effectiveness of inter-robot resource delivery for maintaining feasibility

In this section, we present following two experiments which show that executing the Algorithm 1 (i.e. CreateRendezvous) can improve the feasibility $d_{\text{fsb}}(\Sigma )$ of the MR schedule Σ. (1) Given a static MRS, we examine the effect of Algorithm 1 on the structure of Σ, to show that the search frontier χ can be evenly pushed forward without introducing any cycles, which is crucial to ensuring the monotonic improvement of feasibility and the compliance with the inter-task constraints and deadlock-free requirement. (2) Given a dynamic MRS, which persistently executes tasks in Σ and accepts new tasks, we examine the effect of persistently executing Algorithm 1 on the feasibility and cost-efficiency of Σ.

Experiment I. Effect of single execution of Algorithm 1

We simulate the effect of a single execution of Algorithm 1 on the schedules Σ of a MRS consisting of three robots, corresponding to schedules ${\sigma }_1,{\sigma }_2,{\sigma }_3$ , respectively. We assume that (1) there is no fixed station in the environment; (2) each robot possesses certain (randomly initialised) amount of residual resources which are only capable of supporting part of the tasks in the schedule of the robot; (3) all the robots are involved in the process of feasibility maintenance using Algorithm 1, which is only executed for a single time; (4) Algorithm 2 is not used, and during the single execution of Algorithm 1, except for the insertion of rendezvouses which are used for inter-robot resource delivery, all the other tasks in the MR schedules Σ remain in their original sequence; (5) there are following constraints P and ϒ among the tasks, which restrains the order of the tasks being processed in Algorithm 1

$\begin{array}{l}P=\{〈{\pi }_1,{\pi }_3〉,〈{\pi }_1,{\pi }_4〉,〈{\pi }_2,{\pi }_4〉,〈{\pi }_2,{\pi }_5〉,〈{\pi }_3,{\pi }_6〉,〈{\pi }_3,{\pi }_7〉,\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{1em}\hspace{0.5em}〈{\pi }_4,{\pi }_8〉,〈{\pi }_5,{\pi }_9〉,〈{\pi }_6,{\pi }_{10}〉,〈{\pi }_7,{\pi }_{10}〉,〈{\pi }_8,{\pi }_{11}〉,〈{\pi }_9,{\pi }_{12}〉,\hfill \\ 〈{\pi }_{10},{\pi }_{13}〉,〈{\pi }_{11},{\pi }_{13}〉,〈{\pi }_{12},{\pi }_{13}〉\}\hfill \end{array}$

50

$\Upsilon =\left\{\{{\pi }_4,{\pi }_5\},\{{\pi }_7,{\pi }_8,{\pi }_{12}\}\right\}$

51

Table 2 shows the process of single execution of Algorithm 1 in terms of the effect of each inserted rendezvous (for inter-robot resource delivery) on the structure and performance indicators of Σ. Each row in Table 2 corresponds to the insertion of a resource-delivery rendezvous ${\upsilon }_{i,j}\in {\Upsilon }_{\text{r}}({\pi }_i)$ , where i is the identification number of the task ${\pi }_i$ that is supposed to use the resources provided by ${\upsilon }_{i,j}$ . Denote the SMO which inserts ${\upsilon }_{i,j}$ into Σ as μ. Table 2 also shows the following information related to the effect of inserting ${\upsilon }_{i,j}$ on Σ: (1) ${\iota }_{\mu }{d}_{\text{stf}}(\sigma ,{\pi }_i)$ shows the improvement to the degree of satisfaction $d_{\text{stf}}(\sigma ,{\pi }_i)$ of task ${\pi }_i$ after inserting ${\upsilon }_{i,j}$ ; (2) ${\iota }_{\mu }\parallel \Sigma \parallel$ is the increment to the cost $\parallel \Sigma \parallel$ after inserting ${\upsilon }_{i,j}$ ; (3) ${\iota }_{\mu }{d}_{\text{fsb}}(\Sigma )$ is the improvement to the degree of feasibility $d_{\text{fsb}}(\Sigma )$ after inserting ${\upsilon }_{i,j}$ ; (4) the current position of search frontier χ at each schedule σ, represented with the symbol ‘ $|$ ’, so that any task $\pi \in \sigma$ falling before (or after) ‘ $|$ ’ is feasible (or not).

Table 2.

Effects of single execution of Algorithm 1 on MR schedules.

${\upsilon }_{i,j}$	${\iota }_{\mu }{d}_{\text{stf}}(\sigma ,{\pi }_i)$	${\iota }_{\mu }\parallel \Sigma \parallel$	${\iota }_{\mu }{d}_{\text{fsb}}(\Sigma )$	Adapted MR schedules $\mu (\Sigma )$
				${\sigma }_1=〈|{\pi }_1,{\pi }_3,{\pi }_7,{\pi }_{10}〉$
				${\sigma }_2=〈|{\pi }_6,{\pi }_2,{\pi }_4,{\pi }_8,{\pi }_{13}〉$
				${\sigma }_3=〈|{\pi }_5,{\pi }_9,{\pi }_{12},{\pi }_{11}〉$
${\upsilon }_{1,1}$	0.8971	139.9122	0.0354	${\sigma }_1=〈{\pi }_{\text{c}\mathrm{,1,1}},|{\pi }_1,{\pi }_3,{\pi }_7,{\pi }_{10}〉$
				${\sigma }_2=〈{\pi }_{\text{p}\mathrm{,1,1}},|{\pi }_6,{\pi }_2,{\pi }_4,{\pi }_8,{\pi }_{13}〉$
				${\sigma }_3=〈|{\pi }_5,{\pi }_9,{\pi }_{12},{\pi }_{11}〉$
${\upsilon }_{1,2}$	1.0	120.0028	0.1582	${\sigma }_1=〈{\pi }_{\text{c}\mathrm{,1,1}},{\pi }_{\text{c}\mathrm{,1,2}},{\pi }_1,{\pi }_3,|{\pi }_7,{\pi }_{10}〉$
				${\sigma }_2=〈{\pi }_{\text{p}\mathrm{,1,1}},|{\pi }_6,{\pi }_2,{\pi }_4,{\pi }_8,{\pi }_{13}〉$
				${\sigma }_3=〈{\pi }_{\text{p}\mathrm{,1,2}},|{\pi }_5,{\pi }_9,{\pi }_{12},{\pi }_{11}〉$
${\upsilon }_{6,1}$	1.0	77.6236	0.1292	${\sigma }_1=〈{\pi }_{\text{c}\mathrm{,1,1}},{\pi }_{\text{c}\mathrm{,1,2}},{\pi }_1,{\pi }_3,{\pi }_{\text{p}\mathrm{,6,1}},|{\pi }_7,{\pi }_{10}〉$
				${\sigma }_2=〈{\pi }_{\text{p}\mathrm{,1,1}},{\pi }_{\text{c}\mathrm{,6,1}},{\pi }_6,{\pi }_2,{\pi }_4,|{\pi }_8,{\pi }_{13}〉$
				${\sigma }_3=〈{\pi }_{\text{p}\mathrm{,1,2}},|{\pi }_5,{\pi }_9,{\pi }_{12},{\pi }_{11}〉$
${\upsilon }_{5,1}$	1.0	8.78769	0.3472	${\sigma }_1=〈{\pi }_{\text{c}\mathrm{,1,1}},{\pi }_{\text{c}\mathrm{,1,2}},{\pi }_1,{\pi }_3,{\pi }_{\text{p}\mathrm{,6,1}},{\pi }_{\text{p}\mathrm{,5,1}},|{\pi }_7,{\pi }_{10}〉$
				${\sigma }_2=〈{\pi }_{\text{p}\mathrm{,1,1}},{\pi }_{\text{c}\mathrm{,6,1}},{\pi }_6,{\pi }_2,{\pi }_4,|{\pi }_8,{\pi }_{13}〉$
				${\sigma }_3=〈{\pi }_{\text{p}\mathrm{,1,2}},{\pi }_{\text{c}\mathrm{,5,1}},{\pi }_5,{\pi }_9,{\pi }_{12},|{\pi }_{11}〉$
${\upsilon }_{7,1}$	1.0	6.045	0.0873	${\sigma }_1=〈{\pi }_{\text{c}\mathrm{,1,1}},{\pi }_{\text{c}\mathrm{,1,2}},{\pi }_1,{\pi }_3,{\pi }_{\text{p}\mathrm{,6,1}},{\pi }_{\text{p}\mathrm{,5,1}},{\pi }_{\text{c}\mathrm{,7,1}},{\pi }_7,{\pi }_{10}〉$
				${\sigma }_2=〈{\pi }_{\text{p}\mathrm{,1,1}},{\pi }_{\text{c}\mathrm{,6,1}},{\pi }_6,{\pi }_2,{\pi }_4,|{\pi }_8,{\pi }_{13}〉$
				${\sigma }_3=〈{\pi }_{\text{p}\mathrm{,1,2}},{\pi }_{\text{c}\mathrm{,5,1}},{\pi }_5,{\pi }_9,{\pi }_{12},{\pi }_{\text{p}\mathrm{,7,1}},{\pi }_{11}〉$

MR: multi-robot.

As shown in Table 2: (1) two rendezvouses ${\upsilon }_{1,1}$ and ${\upsilon }_{1,2}$ are generated for satisfying ${\pi }_1$ ; one rendezvous ${\upsilon }_{6,1}$ , ${\upsilon }_{5,1}$ , ${\upsilon }_{7,1}$ is generated for satisfying ${\pi }_6$ , ${\pi }_5$ , ${\pi }_7$ respectively; (2) with the insertion of each rendezvous ${\upsilon }_{i,j}$ , the search frontier χ advances for one or more steps on the schedule which owns ${\pi }_i$ , without sacrificing the feasibility of other schedules; (3) with the insertion of ${\upsilon }_{i,j}$ , both $\parallel \Sigma \parallel$ and $d_{\text{fsb}}(\Sigma )$ increase, which means the improvement of feasibility is attained at the expense of increased cost (which mainly involves the travelling cost for inter-robot resource delivery). (4) Algorithm 1 doesn’t guarantee satisfying the resource requirements of all tasks; for example, ${\pi }_8$ remains infeasible after Algorithm 1 terminates, which indicates Algorithm 1 fails to find enough residual resources in the MRS to satisfy ${\pi }_8$ .

Experiment II. Effect of persistent execution of Algorithm 1

This part of experiment is further divided into two parts: (1) instantaneous effectiveness of Algorithm 1: As shown in Figure 6, we observe the instantaneous change of the performance of the MRS over time, with given initial setting. (2) Cumulative effectiveness of Algorithm 1: As shown in Figure 7, we repeat the experiment about instantaneous effectiveness for given initial settings under different parameters and observe the influence of these parameters on the cumulative effectiveness (which is measured by the average of the instantaneous values over time) of Algorithm 1.

Figure 6.

Effect of applying inter-robot resource delivery on improving the feasibility of the MR schedules; (instantaneous value, without using Algorithm 2). (a) $\Vert \Sigma \Vert$ ; (b) ${\Vert \Sigma \Vert }_{\text{v}}$ ; (c) d _fsb(Σ) and (d) N _v. MR: multi-robot.

Figure 7.

Effect of applying inter-robot resource delivery on improving the feasibility of the MR schedules; (time-average value, without using Algorithm 2). MR: multi-robot.

Figure 6 compares the case when Algorithm 1 is used, against the case without Algorithm 1, by showing the instantaneous values (and their change over time) under the two cases, respectively, of the following performance indicators of the MR schedules Σ: (1) $\parallel \Sigma \parallel$ , which is the cost of Σ, as defined by equation (15); (2) $\parallel \Sigma {\parallel }_{\text{v}}$ , which is the cost of the rendezvouses for inter-robot delivery, as defined by equation (18); (3) $d_{\text{fsb}}(\Sigma )$ , which is the degree of feasibility of Σ, as defined by equation (14); (4) $N_{\text{v}}=|{\Upsilon }_{\text{r}}(\Sigma )|$ , which is the total count of rendezvouses for inter-robot delivery. These indicators are used throughout the experiments in this article.

We simulate 15 robots initialised with randomly generated initial configuration, including (1) initial locations in the two-dimensional environment; (2) initial residual resources; (3) a sequence of tasks which will be assigned to the entire MRS in an extended period of time; (4) precedence constraints among the tasks. The same group of robots are simultaneously put under the two cases (with/without Algorithm 1), to evaluate the effectiveness of Algorithm 1 in improving the feasibility $d_{\text{fsb}}(\Sigma )$ .

As shown in Figure 6, Algorithm 1 is able to significantly improve the degree of feasibility $d_{\text{fsb}}(\Sigma ),$ while reducing the cost $\parallel \Sigma \parallel$ , despite introducing additional cost $\parallel \Sigma {\parallel }_{\text{v}}$ for inter-robot delivery. Although Algorithm 1 is not aimed to improve the cost-efficiency in the first place, its ability to reduce $\parallel \Sigma \parallel$ is because it makes many tasks which are originally unfeasible due to lack of resources become feasible, thereby significantly reducing the amount of accumulated tasks pending in the schedules Σ.

Figure 7 shows the distribution of the effectiveness of persistent execution of Algorithm 1 when following parameters are considered. (1) $N_{\text{rp,max}}/|\Sigma |$ is the amount of initial residual resource of each schedule $\sigma \in \Sigma$ , which reflects the initial resource distribution of the resources in the MRS; (2) $\Delta t_{\text{s}}$ is the rate of new tasks being periodically added to Σ, which reflects the influence of environmental changes on Σ. These parameters are taken, respectively, as the two axes of each diagram in Figure 7 and both range from 0 to 1000. We use $\overline{(\cdot )}$ to show the result of taking average of the time-variant value over the period of time $\left[0,T_{\text{max}}\right]$ (where $T_{\text{max}}=50,000$ in this experiment). Figure 7 (1-1) and Figure 7 (2-1) show, respectively, the (time-average) cost $\overline{\parallel \Sigma \parallel }$ and degree of feasibility $\overline{d_{\text{fsb}}(\Sigma )}$ when Algorithm 1 is not used and all robots only rely on their own residual resources. Figure 7 (1-2) and (2-2) show, respectively, $\overline{\parallel \Sigma \parallel }$ and $\overline{d_{\text{fsb}}(\Sigma )}$ when Algorithm 1 is used. Figure 7 (1-3) and (2-3) show respectively the ratio of improvement to $\overline{\parallel \Sigma \parallel }$ and $\overline{d_{\text{fsb}}(\Sigma )}$ caused by Algorithm 1, which compare the case with Algorithm 1 against the case without Algorithm 1 and are, respectively, defined as below

${\iota }_{\text{fsb}}\parallel \Sigma \parallel =\frac{{\overline{\parallel \Sigma \parallel }|}_{\overline{\text{fsb}}}+1}{{\overline{\parallel \Sigma \parallel }|}_{\text{fsb}}+1},{\iota }_{\text{fsb}}{d}_{\text{fsb}}(\Sigma )=\frac{{\overline{d_{\text{fsb}}(\Sigma )}|}_{\text{fsb}}+1}{{\overline{d_{\text{fsb}}(\Sigma )}|}_{\overline{\text{fsb}}}+1}$

52

where (1) fsb (or $\overline{\text{fsb}}$ ) respectively represents the case with (or without) using Algorithm 1; (2) both upper and lower parts of each fraction contain ‘ $+1$ ’ to smoothly deal with the case when the denominator of the fraction becomes 0.

As shown in Figure 7, both $\parallel \Sigma \parallel$ (compare Figure 7 (1-2) to Figure 7 (1-1)) and $d_{\text{fsb}}(\Sigma )$ (compare Figure 7 (2-2) to Figure 7 (2-1)) are improved significantly after Algorithm 1 is applied for acquiring resources, compared to the situation when robots only rely on their residual resources. This indicates that the persistent execution of Algorithm 1 can reduce $\overline{\parallel \Sigma \parallel }$ (i.e. the time-average of $\parallel \Sigma \parallel$ ) and improve $\overline{d_{\text{fsb}}(\Sigma )}$ (i.e. the time-average of $d_{\text{fsb}}(\Sigma )$ ) significantly. Algorithm 1 is capable of reducing $\overline{\parallel \Sigma \parallel }$ because: (1) when Algorithm 1 is not used, there are large amount of pending tasks accumulated in the schedules which cannot be timely executed since their resource demands are not satisfied; (2) when Algorithm 1 is used, these tasks can be quickly completed by the robots, largely reducing the amount of pending tasks, thereby reducing the cost of schedules $\parallel \Sigma \parallel$ . Algorithm 1 is capable of improving $\overline{d_{\text{fsb}}(\Sigma )}$ to 1 for most cases, except for the area close to the two axes of Figure 7 (2-2), which correspond to the situations with (1) very low per-robot resource $N_{\text{rp,max}}/|\Sigma |$ , which reduces the total amount of available resources for the MRS; or (2) very small task release interval $\Delta t_{\text{s}}$ , which may increase the total amount of demanded resources beyond the level which can be satisfied by the resources existing in the environment. In these areas, the cost $\parallel \Sigma \parallel$ is also significantly higher even when Algorithm 1 is used, as shown by Figure 7 (1-2), and the corresponding improvement ratio ${\iota }_{\text{fsb}}\parallel \Sigma \parallel$ also drops significantly, as shown by Figure 7 (1-3), due to the increasing amount of pending tasks in the schedules when they become infeasible.

Summary

This section validates the capability of CreateRendezvous algorithm to systematically create rendezvouses among robots for inter-robot resource delivery, thereby increasing $d_{\text{fsb}}(\Sigma )$ . It is also able to reduce the cost $\parallel \Sigma \parallel$ since it makes more tasks in Σ become feasible, thereby reducing the amount of pending tasks in Σ. The pending tasks will otherwise block the execution of Σ, causing tasks to accumulate and thereby increasing the anticipated cost $\parallel \Sigma \parallel$ . When $\Delta t_{\text{rls}}$ (the interval of releasing new tasks) decreases, the effectiveness of CreateRendezvous algorithm (as measured by ${\iota }_{\text{fsb}}\parallel \Sigma \parallel$ and ${\iota }_{\text{fsb}}{d}_{\text{fsb}}(\Sigma )$ ) will increase, due to the increasing amount of pending tasks.

Effect of persistent task reallocation on inter-robot resource delivery

This section uses several random experiments to show the effectiveness of Algorithm 2 (i.e. ReAllocate) can improve the cost-efficiency $\parallel \Sigma \parallel$ of the MR schedule Σ, as well as the way to integrate Algorithm 2 with Algorithm 1. ‘Experiment I. Effect of task reallocation (applied alone) on MR schedules’ section shows the effectiveness of executing Algorithm 2 (without Algorithm 1) on the performance indicators of Σ. ‘Experiment II. Necessity of considering inter-robot resource delivery in task reallocation’ section shows the necessity to explicitly anticipate the influence of Algorithm 1 in Algorithm 2 (see line 10 and line 22 of Figure 5). ‘Experiment III. Integrating task reallocation (Algorithm 2) with rendezvous generation (Algorithm 1)’ section shows the effectiveness of integrating Algorithm 2 with Algorithm 1 on improving average cost-efficiency and feasibility under different environmental parameters.

Experiment I. Effect of task reallocation (applied alone) on MR schedules

We first present an experiment which demonstrates the effect of Algorithm 2 (i.e. ReAllocate algorithm) on the performance indicators of the MR schedules Σ, without using Algorithm 1. We set $N_{\text{rp,max}}/|\Sigma |=50$ and $\Delta t_{\text{s}}=50$ and observe the change of $\parallel \Sigma \parallel$ and $d_{\text{fsb}}(\Sigma )$ over time. Figure 8 shows the result of this experiment. It can be observed from Figure 8(a) that Algorithm 2 is capable of significantly reduce the cost $\parallel \Sigma \parallel$ , especially when the count of tasks in Σ increases over time. However, as shown in Figure 8(b), Algorithm 2 is incapable of improving $d_{\text{fsb}}(\Sigma )$ . This is because the residual resource of each robot is quite limited, and with large amount of incoming tasks, even if the Algorithm 2 can improve the $d_{\text{fsb}}(\Sigma )$ by reallocating some tasks to the robots with more abundant residual resources, the space for improvement is quite confined. To improve $d_{\text{fsb}}(\Sigma )$ , we must increase the level of residual resource of each robot by some means.

Figure 8.

Effect of applying persistent task reallocation on performance indicators of Σ; (instantaneous value, using Algorithm 2 alone). (a) $\Vert \Sigma \Vert$ and (b) d _fsb(Σ).

Experiment II. Necessity of considering inter-robot resource delivery in task reallocation

We now use an experiment to show that to successfully integrate Algorithm 2 with Algorithm 1, it is necessary for Algorithm 2 to explicitly anticipate the influence of each reinsertion operation ${\mu }_u$ for each allocation bundle $u\in U$ on the rendezvous set ${\Upsilon }_{\text{r}}(\Sigma )={\displaystyle {\cup }_{\sigma \in \Sigma }}{\displaystyle {\cup }_{\pi \in \sigma }}{\Upsilon }_{\text{r}}(\pi )$ (as shown by Algorithm 2 lines 10–11, 14, 22–23, 27), rather than only on the current schedules Σ. Figure 9 shows the case when ${\Upsilon }_{\text{r}}(\Sigma )$ is not considered in Algorithm 2, which means the invocations to CreateRendezvous algorithm and the appearances of ${\mu }_{\text{fsb}}(\mu )$ in Algorithm 2 are all removed. Figure 10 shows the case when ${\Upsilon }_{\text{r}}(\Sigma )$ is explicitly considered in Algorithm 2, as the way it is shown in Figure 5. The experiments of both Figures 9 and 10 are conducted with the setting $N_{\text{rp,max}}/|\Sigma |=50$ and $\Delta t_{\text{s}}=50$ , and both compares the case with and without Algorithm 2, to show the effect of Algorithm 2 on different situations.

Figure 9.

Effect of applying persistent task reallocation on performance indicators of Σ; (instantaneous value, Algorithm 2 doesn’t consider ${\Upsilon }_{\text{r}}(\Sigma )$ ). (a) $\Vert \Sigma \Vert$ ; (b) ${\Vert \Sigma \Vert }_{\text{v}}$ ; (c) d _fsb(Σ) and (d) N _v.

Figure 10.

Effect of applying persistent task reallocation on performance indicators of Σ; (instantaneous value, Algorithm 2 considers ${\Upsilon }_{\text{r}}(\Sigma )$ ). (a) $\Vert \Sigma \Vert$ ; (b) ${\Vert \Sigma \Vert }_{\text{v}}$ ; (c) d _fsb(Σ) and (d) N _v.

As shown in Figure 7, when Algorithm 2 doesn’t consider ${\Upsilon }_{\text{r}}(\Sigma )$ , integrating Algorithm 2 with Algorithm 1 is counterproductive for all the performance indicators of Σ, even for the cost $\parallel \Sigma \parallel$ that is supposed to be improved by Algorithm 2. The reason of this phenomenon is explained as below. Denote the case with and without Algorithm 2 as respectively alc and $\overline{\text{alc}}$ and assume Algorithm 2 doesn’t consider ${\Upsilon }_{\text{r}}(\Sigma )$ . Assume initially both cases have the same MR schedules Σ. When Algorithm 2 is invoked, since Algorithm 2 doesn’t consider ${\Upsilon }_{\text{r}}(\Sigma )$ , it optimises $\parallel \Sigma \parallel$ (and supposedly also $d_{\text{fsb}}(\Sigma )$ for the current Σ) by adapting Σ into ${\Sigma }^{\prime }$ through task reallocation. However, ${\Sigma }^{\prime }$ may not be optimal after Algorithm 1 is invoked in the future, since Algorithm 1 will introduce ${\Upsilon }_{\text{r}}(\Sigma )$ , which will change the factors to be considered when computing $\parallel \Sigma \parallel$ and $d_{\text{fsb}}(\Sigma )$ . In addition, as shown by the experiment in ‘Experiment I. Effect of task reallocation (applied alone) on MR schedules’ section, Algorithm 2 has almost no capability of improving $d_{\text{fsb}}(\Sigma )$ when used alone. This makes the straightforward (without considering ${\Upsilon }_{\text{r}}(\Sigma )$ ) integration of Algorithm 2 with Algorithm 1 less likely to achieve local optimum for both $\parallel \Sigma \parallel$ and $d_{\text{fsb}}(\Sigma )$ . When Algorithm 1 is invoked in the future, since Algorithm 1 is only responsible of improving $d_{\text{fsb}}(\Sigma )$ at the expense of $\parallel \Sigma {\parallel }_{\text{v}}$ , it will further increase $\parallel \Sigma \parallel$ . The difference between $\text{alc}$ and $\overline{\text{alc}}$ cases will enlarge over time with more tasks being added to Σ and more invocations to Algorithm 2 are made in the alc case.

As shown in Figure 10, after Algorithm 2 explicitly considers ${\Upsilon }_{\text{r}}(\Sigma )$ , integrating Algorithm 2 with Algorithm 1 improves all the performance indicators of Σ significantly, given the same setting. Also note that Algorithm 2 also brings significant improvement to $d_{\text{fsb}}(\Sigma )$ , which is supposed only to be the responsibility of Algorithm 1. This results from the capability of Algorithm 2 to reallocate tasks to the robots with more sufficient residual resources, thereby improving $d_{\text{fsb}}(\Sigma )$ , reducing the count of unsatisfied tasks and the need to fetch resources for tasks. Therefore $\parallel \Sigma \parallel$ and $N_{\text{v}}$ are also reduced significantly.

Experiment III. Integrating task reallocation (Algorithm 2) with rendezvous generation (Algorithm 1)

Figure 10 only shows the effectiveness of Algorithm 2 in one particular setting of parameters. In this section, we present an experiment to evaluate the effectiveness of Algorithm 2 under a wider range of settings, when Algorithm 2 explicitly considers ${\Upsilon }_{\text{r}}(\Sigma )$ . Figure 10 already shows the improvement brought by integrating Algorithm 2 with Algorithm 1 in terms of instantaneous values of performance indicators. Figure 11 shows the distribution of effectiveness of Algorithm 2 in terms of the time-average of these values. Similar to ‘Experiment II. Effect of persistent execution of Algorithm 1’ section, this experiment considers the influences of the parameters $N_{\text{rp,max}}/|\Sigma |$ and $\Delta t_{\text{s}}$ with the same range of values. Figure 11 (1/2/3/4-1) shows, respectively, the time-average of the indicators $\parallel \Sigma \parallel$ , $\parallel \Sigma {\parallel }_{\text{v}}$ , $d_{\text{fsb}}(\Sigma )$ , $N_{\text{v}}$ when Algorithm 1 is used but Algorithm 2 is not used. Figure 11 (1/2/3/4-2) shows, respectively, the time-average of these indicators when both Algorithm 1 and Algorithm 2 are used. Figure 11 (1/2/3/4-3) shows respectively the ratio of improvement to the time-average of these indicators caused by Algorithm 2, which compares the case with Algorithm 2 against the case with only Algorithm 1, and are, respectively, defined as below

Figure 11.

Effect of applying persistent task reallocation on the effectiveness of inter-robot delivery; (time-average value, Algorithm 2 considers ${\Upsilon }_{\text{r}}(\Sigma )$ ).

Figure 12.

Effect of inter-robot resource delivery on performance indicators of Σ; (instantaneous value, using both Algorithm 1 and Algorithm 2). (a) $\Vert \Sigma \Vert$ ; (b) ${\Vert \Sigma \Vert }_{\text{v}}$ ; (c) d _fsb(Σ) and (d) N _v.

${\iota }_{\text{alc}}\parallel \Sigma \parallel =\frac{{\overline{\parallel \Sigma \parallel }|}_{\overline{\text{alc}}}+1}{{\overline{\parallel \Sigma \parallel }|}_{\text{alc}}+1},{\iota }_{\text{alc}}\parallel \Sigma {\parallel }_{\text{v}}=\frac{{\overline{\parallel \Sigma {\parallel }_{\text{v}}}|}_{\overline{\text{alc}}}+1}{{\overline{\parallel \Sigma {\parallel }_{\text{v}}}|}_{\text{alc}}+1}$

53

${\iota }_{\text{alc}}{d}_{\text{fsb}}(\Sigma )=\frac{{\overline{d_{\text{fsb}}(\Sigma )}|}_{\text{alc}}+1}{{\overline{d_{\text{fsb}}(\Sigma )}|}_{\overline{\text{alc}}}+1},{\iota }_{\text{alc}}{N}_{\text{v}}=\frac{{\overline{N_{\text{v}}}|}_{\overline{\text{alc}}}+1}{{\overline{N_{\text{v}}}|}_{\text{alc}}+1}$

54

where alc (or $\overline{\text{alc}}$ ) respectively represents the case with (or without) using Algorithm 2.

As shown in Figure 11, the time-average of all the performance indicators are improved to certain extent by integrating Algorithm 2 with Algorithm 1. Compared to other performance indicators, the improvement to $\overline{\parallel \Sigma \parallel }$ is most significant and apparent in most regions of entire domain, as shown by Figure 11 (1-3). The improvement ratios of all performance indicators increase significantly, when $\Delta t_{\text{s}}$ decreases, implying that the effectiveness of Algorithm 2 becomes more apparent when there are larger amount of tasks being assigned to the MRS. However, for the region where $N_{\text{rp,max}}/|\Sigma |$ is small, the cases with negative improvement ratios increase, implying that Algorithm 2 may become counterproductive when the total amount of resources becomes less sufficient.

Summary

This section validates the capability of Algorithm 2 (i.e. ReAllocate algorithm) to persistently maintain the cost-efficiency of MR schedule as measured by $\parallel \Sigma \parallel$ . When used alone without Algorithm 1 (i.e. CreateRendezvous algorithm), Algorithm 2 is able to dramatically improve the cost-efficiency of the MR schedules and the effectiveness increases when $\Delta t_{\text{rls}}$ increases. As shown in ‘Experiment II. necessity of considering inter-robot resource delivery in task reallocation’ section, for successful integration of Algorithm 2 and Algorithm 1, we need to explicitly anticipate the influence of Algorithm 1 (i.e. the ${\Upsilon }_{\text{r}}(\Sigma )$ ) on $\parallel \Sigma \parallel$ , otherwise the integration will be counterproductive. ‘Experiment III. Integrating task reallocation (Algorithm 2) with rendezvous generation (Algorithm 1)’ section shows the synergetic effectiveness of Algorithms 1 and 2 in which the effect of Algorithm 1 is considered in Algorithm 2. Applying Algorithm 2 in addition to Algorithm 1 can significantly reduce $\parallel \Sigma \parallel$ , with slight improvement to $d_{\text{fsb}}(\Sigma )$ . The effectiveness of Algorithm 2 increase when $\Delta t_{\text{s}}$ decreases, as a result of increasing amount of pending tasks.

Effectiveness of inter-robot resource delivery in scenarios with fixed resource stations

This section presents an experiment which shows the effectiveness of inter-robot delivery in maintaining the feasibility of MR schedules in an environment with fixed resource stations. We assume that the environment can be divided into two separate regions: (1) task region, which holds the working locations of all the tasks assigned to the MRS; (2) station region, which holds the locations of all the fixed stations which can provide resources to the MRS. It is assumed that all robots do not possess any initial residual resources and must fetch resources from the fixed stations. In addition to the previously introduced parameter $\Delta t_{\text{s}}$ , in this experiment, with regard to the spatial relation between task region and we consider the influence of the parameter $\parallel p_{\text{r}}-p_{\text{t}}\parallel ,$ which is the distance between (a) $p_{\text{t}}$ , that is, the centre of the task region; and (b) $p_{\text{r}}$ , that is, the centre of the station region. This parameter reflects the separateness between the task region and the station region. Both Algorithms 1 and 2 are used in this experiment.

This experiment is further divided into three parts: (1) instantaneous effectiveness of Algorithms 1 and 2: As shown in Figure 6, we observe the instantaneous change of the performance of the MRS over time, with given initial setting. (2) Cumulative effectiveness of Algorithm 1 and Algorithm 2 considering $\Delta t_{\text{s}}$ and $\parallel p_{\text{r}}-p_{\text{t}}\parallel$ : as shown in Figure 13. (3) Cumulative effectiveness of Algorithm 1 and Algorithm 2 considering $\Delta t_{\text{s}}$ and $N_{\text{rp,max}}/|{\Sigma }_{\text{r}}|$ , where $N_{\text{rp,max}}/|{\Sigma }_{\text{r}}|$ shows the amount of initial resources of each fixed station: as shown in Figure 14. Both Figures 13 and 14 are organised in a similar manner as Figure 11, and both requires repeating the experiment about instantaneous effectiveness for given initial settings under different parameters. We can observe from Figures 13 and 14 the influence of these parameters on the cumulative effectiveness (shown by the time-average of the instantaneous values) of Algorithm 1. In all these experiments, the amount of initial residual resource of each robot is set as 0, which means all resources must be initially acquired from the fixed stations.

Figure 13.

Effect of inter-robot resource delivery on the performance indicators of Σ under the scenario with fixed resource station, considering influence of $\parallel p_{\text{r}}-p_{\text{t}}\parallel$ and $\Delta t_{\text{s}}$ ; (time-average value, using both Algorithm 1 and Algorithm 2).

Figure 14.

Effect of inter-robot resource delivery on the performance indicators of Σ under the scenario with fixed resource station, considering influence of $N_{\text{rp,max}}/|{\Sigma }_{\text{r}}|$ and $\Delta t_{\text{s}}$ ; (time-average value, using both Algorithm 1 and Algorithm 2).

Figure 12 shows the effect of inter-robot delivery in reducing cost when fixed stations are distant from task locations. We set $\parallel p_{\text{r}}-p_{\text{t}}\parallel =100000$ , $\Delta t_{\text{s}}=50$ , $N_{\text{rp,max}}/|\Sigma |=50$ . As shown by Figure 12(a), (b) and (d), respectively, inter-robot delivery is able to reduce $\parallel \Sigma \parallel$ , $\parallel \Sigma {\parallel }_{\text{v}}$ , $N_{\text{v}}$ significantly. The improvement brought by inter-robot delivery to these performance indicators decrease over time, which implies that the residual resources in both fixed stations and robots are almost depleted; therefore when $t\to \infty$ , it makes no difference whether inter-robot delivery is used, because there would be nowhere from which resources can be acquired. As shown by Figure 12(c), inter-robot delivery will decrease $d_{\text{fsb}}(\Sigma )$ , which is because: (1) in the case with inter-robot delivery, the resource demands of any incoming tasks are more likely to be satisfied by the residual resources of the robots rather than fixed stations, while due to the existence of inter-robot delivery, these residual resources have been partially consumed by the robots, thus are only capable of supporting a smaller amount of incoming tasks; (2) in the case without inter-robot delivery, the resource demands of tasks exactly match the residual resources of the fixed stations, and their satisfaction depends solely on the latter, rather than on how many resources are supposed to be consumed by the robots.

Figure 13 shows the distribution of the effectiveness of entire approach when the parameters $\Delta t_{\text{s}}$ and $\parallel p_{\text{r}}-p_{\text{t}}\parallel$ are considered. Figure 13 (1/2/3/4-1) shows, respectively, the time-average values of the indicators $\parallel \Sigma \parallel$ , $\parallel \Sigma {\parallel }_{\text{v}}$ , $d_{\text{fsb}}(\Sigma )$ , $N_{\text{v}}$ when robots are only allowed to acquire resources from fixed stations. Figure 13 (1/2/3/4-2) shows, respectively, the values of these indicators when robots are allowed to acquire resources from fixed stations or through inter-robot resource delivery. Figure 13 (1/2/3/4-3) shows, respectively, the ratio of improvement to these indicators caused by introduction of inter-robot resource delivery, which compares the case with and without inter-robot resource delivery and are respectively defined as below

${\iota }_{\text{ird}}\parallel \Sigma \parallel =\frac{{\overline{\parallel \Sigma \parallel }|}_{\overline{\text{ird}}}+1}{{\overline{\parallel \Sigma \parallel }|}_{\text{ird}}+1},{\iota }_{\text{ird}}\parallel \Sigma {\parallel }_{\text{v}}\hspace{0.17em}=\frac{{\overline{\parallel \Sigma {\parallel }_{\text{v}}}|}_{\overline{\text{ird}}}+1}{{\overline{\parallel \Sigma {\parallel }_{\text{v}}}|}_{\text{ird}}+1}$

55

${\iota }_{\text{ird}}{d}_{\text{fsb}}(\Sigma )=\frac{{\overline{d_{\text{fsb}}(\Sigma )}|}_{\text{ird}}+1}{{\overline{d_{\text{fsb}}(\Sigma )}|}_{\overline{\text{ird}}}+1},{\iota }_{\text{ird}}{N}_{\text{v}}=\frac{{\overline{N_{\text{v}}}|}_{\overline{\text{ird}}}+1}{{\overline{N_{\text{v}}}|}_{\text{ird}}+1}$

56

where ird (or $\overline{\text{ird}}$ ), respectively, represents the case with (or without) inter-robot resource delivery.

As shown by Figure 13 (1, 2-3), the inter-robot delivery is capable of improve $\overline{\parallel \Sigma \parallel }$ and $\overline{\parallel \Sigma {\parallel }_{\text{v}}}$ significantly, and the respective improvement ratios increase when $\Delta t_{\text{s}}$ decreases and/or $\parallel p_{\text{r}}-p_{\text{t}}\parallel$ increases. The improvement to $\overline{\parallel \Sigma \parallel }$ is largely due to the improvement to $\overline{\parallel \Sigma {\parallel }_{\text{v}}}$ . The inter-robot delivery decreases $\overline{d_{\text{fsb}}(\Sigma )}$ for almost all parameter settings, except for the region where $\parallel p_{\text{r}}-p_{\text{t}}\parallel$ is small, where inter-robot delivery is almost the same as fetching from fixed stations, and the observed improvement largely results from the random initialisation rather than the effect of inter-robot delivery.

Figure 14 shows the distribution of the effectiveness of the approach when parameters $\Delta t_{\text{s}}$ and $N_{\text{rp,max}}/|{\Sigma }_{\text{r}}|$ are considered. The diagrams in Figure 14 are arranged in a similar manner as that of Figure 13. In Figure 14, we can also observe significant improvement to $\overline{\parallel \Sigma \parallel }$ , $\overline{\parallel \Sigma {\parallel }_{\text{v}}}$ , $\overline{N_{\text{v}}}$ and the decrement to $\overline{d_{\text{fsb}}(\Sigma )}$ , caused by inter-robot delivery. The improvement ratios of $\parallel \Sigma \parallel$ , $\parallel \Sigma {\parallel }_{\text{v}}$ , $N_{\text{v}}$ increase when $\Delta t_{\text{s}}$ decreases or $N_{\text{rp,max}}/|{\Sigma }_{\text{r}}|$ increases.

Summary

This experiment shows the effectiveness of allowing inter-robot delivery in reducing the cost $\parallel \Sigma \parallel$ , especially the resource delivery cost $\parallel \Sigma {\parallel }_{\text{v}}$ , when fixed stations are present and are distant from the locations of task execution. However, allowing inter-robot delivery also reduces to certain extent the average feasibility. When the distance between task locations and fixed stations are larger, the effectiveness of inter-robot delivery becomes more significant. The effectiveness of inter-robot delivery increase when $\Delta t_{\text{s}}$ decreases, as a result of increasing pending tasks.

Conclusion and future work

We propose a method for dynamically acquiring resources for MR schedules with inter-schedule dependencies and limited resources. We present an algorithm (Algorithm 1) that generates rendezvouses for delivering resources among robots, to persistently maintain the feasibility of the schedules. Algorithm 1 ensures that the feasibility of robots are improved monotonically, and that the rendezvouses for inter-robot delivery will not cause deadlocks among schedules. We present an algorithm (Algorithm 2) that reallocates the tasks among schedules to reduce the cost of schedules, considering the influence of inter-robot delivery. Our experiment shows effectiveness and limitations of the following aspects of our research: (1) Algorithm 1, for persistently and monotonically improving the degree of feasibility of schedules, without introducing deadlocks among schedules; (2) Algorithm 2, for persistently improving the cost-efficiency of the schedules, and the synergy of integrating Algorithm 2 with Algorithm 1; (3) inter-robot delivery, for improving the degree of feasibility and cost-efficiency of the schedules in such scenarios when fixed stations are distant from the locations of tasks.

The contribution of our research to MRTA domain is summarised as below: (1) we present a novel method of feasibility maintenance that uses inter-robot delivery to relieve the shortage of resources, which is apt for the cases when fixed resource stations are unavailable, depleted or distant from the task locations. (2) We consider two types of constraints among tasks, namely precedence constraints and rendezvous, which are useful in many real-world scenarios, investigate their influence on the inter-robot delivery and ensure the compliance with these constraints and prevent deadlocks. (3) We investigate the interplay between (i) feasibility maintenance based on inter-robot delivery and (ii) cost-efficiency maintenance based on task reallocation and enable Algorithm 2 to anticipate the influence of inter-robot delivery on cost-efficiency to relieve the conflict between feasibility and cost-efficiency.

With regard to the presented algorithms, we plan to reduce their computational complexity via parallelism. In addition, we plan to tackle following challenges: (1) the complex dynamics related to the consumption and production of resources during task execution and the interdependencies among different types of resources; (2) the influence of stochastic spatial distribution of tasks, resource demands and supplies, and resource stations in the environment on the effectiveness of inter-robot delivery; (3) considering the urgency of the tasks, so that the resource demands of more urgent tasks can be satisfied with higher priority, even at the expense of less urgent tasks.