Adaptive Task Completion System for Multiple Robots under Task Quantity Variation

Abstract

With the change of population structure, integrating the robotic systems into logistics, healthcare, caregiving, and search-and-rescue operations has become an inevitable trend. This research develops a multi-robot adaptive task allocation and path finding system to address dynamic pickup-and-delivery problem in complex environment, considering both robot capacity and heterogeneity in capabilities. In contrast to other techniques without considering the dynamic task allocation, the proposed IAACO algorithm that is built on a two-layer framework claims high-quality solutions in rapid response to unpredicted task quantity variation. The first layer integrates methods of maximum weight matching, Voronoi Diagram classification and local optimization, to compute real-time allocation results in response to dynamic task changes. The second layer occurs in the task execution process, during which the system simultaneously employs an adaptive ant colony optimization algorithm for further optimization. Additionally, to provide the cost estimation during task assignment for each robot, this work also introduces the multi-robot path finding solved by the modified space-time A $^{*}$ to the system. In simulations, it is shown that IAACO improves the makespan and the total path length by up to 36% and 21% respectively, compared to the baseline algorithms. Finally, the experimental results are also delivered to validate the feasibility of the proposed methodology.

Keywords

Multi-robot system autonomous mobile robots dynamic task allocation multi-agent path finding ant colony optimization

1. Introduction

1.1. Motivation

With the rapid changes in the global economy, labor shortages have become increasingly severe. As illustrated in Figure 1, the declining birth rates and shifts in ideology even exacerbate the problem of the changing population structure, which encourages the deployment of robotic systems into fields of logistics, healthcare, caregiving, and search-and-rescue activity. Fortunately, automated technologies offer an effective solution that reduces the dependency of business on manual labor while improving production efficiency and stability. These advances enable companies to meet the growing demand for labor and navigate the ever-changing market environment. Robots not only fill labor gaps to reduce production costs, but also become potential in emerging applications. For example, robots can perform high-risk tasks and rapidly navigate through hazardous terrains in operations of search and rescue.

Figure 1.

Changing Population Structure Over the World (United Nations, 2022).

1.2. Related Work

The multi-robot system (MRS) is a critical branch of automated technology, allowing collaborative efforts to complete larger and more complex tasks. In addition to common applications in factories and automated warehousing systems (Chen et al., 2021), the MRS is also deployed in various scenarios such as search and rescue systems (Chen et al., 2022; Ghassemi & Chowdhury, 2022), military (Oh et al., 2016), and restaurant services (Huang & Lu, 2017). However, in many real-world settings, the complexity and diversity of tasks require professional service of labor among robots. Thus, heterogeneous robot fleets are more capable of enhancing overall efficiency. Heterogeneity can primarily be categorized into two schemes (Patil et al., 2022): the structural scheme includes, but is not limited to, variations in motion constraints and velocity; the functional scheme is involved with differences in environmental sensing, maximum workload, task execution capabilities, etc.

Multi-robot task allocation (MRTA) and multi-agent path finding (MAPF) are two main topics in the MRS. MRTA can be formulated as a mixed integer linear programming (MILP) problem with the NP-hard feature (Nunes et al., 2017; Sariel-Talay et al., 2009). As system complexity increases, it becomes more challenging to prove or to find an optimal solution within limited time, so obtaining approximately optimal solutions often draws attraction.

Online MRTA methods are particularly effective in addressing uncertainties, as enabling rapid re-planning in response to dynamic changes. Among the foundational and practical approaches, the greedy search is well-known for the polynomial-time computational efficiency, even with non-deterministic solution quality and with merely near-optimal solutions (Aziz et al., 2021; Hussein & Khamis, 2013; Kong et al., 2019; Stanulovic et al., 2022). In general, the greedy-based algorithms have been proven to hold the polynomial-time efficiency for sub-optimal optimization in multi-robot task allocation (Aziz et al., 2021). Researches Hussein and Khamis (2013) and Stanulovic et al. (2022) also demonstrated that market-based and auction-based methods, essentially with greedy heuristics, are temporally efficient for solving real-time task allocation in multi-robot systems. Moreover, Kong et al. (2019) combined the greedy algorithm and particle swarm optimization to accelerate the optimization strategy of resource allocation for collaborative robots. In 2023, Ghassemi and Chowdhury (2022) introduced the BiG-MRTA method, which constructs a weighted bipartite graph using heuristic functions and solves the MRTA problem via maximum weight matching algorithm. The BiG-MRTA method addresses various features, including task deadlines and heterogeneity in the operational range and load capacity of each robot, but primarily targets on completing as many tasks as possible. In 2009, Choi et al. (2009) proposed Consensus-based Bundle Algorithm (CBBA), the most widely adopted decentralized approach, which divides the decision-making process into bidding and consensus phases. Robots initially plan greedily based on their situational awareness and resolve conflicts in task sequences through consensus strategies. The CBBA is proficient in converging to high-quality solutions using only local information and in holding a highly scalable framework. Extensions of the CBBA have been applied across multiple domains, including structurally heterogeneous unmanned underwater vehicle (UUV) swarms (Wu et al., 2022), functionally heterogeneous MRS for elderly care (Zhao et al., 2022), and multiple unmanned aerial vehicle (UAV) systems in search and rescue missions (Chen et al., 2022). However, once communication quality degrades, the performance of the aforementioned algorithms declines sharply, and many key metrics show significant deterioration in dynamic scenarios (Schneider et al., 2015).

On the other hand, offline methods aim to find higher-quality solutions, while consuming more computational cost. Among offline methods, metaheuristic optimization techniques have demonstrated robustness across various application scenarios, particularly in resource scheduling and task allocation problems, where they can yield better solutions (Wong & Chew, 2019). Common approaches include particle swarm optimization (Oh et al., 2016), genetic algorithms (Arif & Haider, 2022), simulated annealing (Barboza & Kniess, 2024), and ant colony optimization (ACO) (Chen et al., 2022; Kim & Lee, 2023; Wang et al., 2012). Compared to the aforementioned optimization methods, ACO offers the advantage of high scalability, utilizing a combination of graphical structures and pheromone mechanisms to quickly achieve near-optimal solutions. ACO has been widely applied to MRTA. In 2023, Kim and Lee (2023) integrated ACO into MRTA for polar environments, optimizing system performance through 3D path estimation. In 2022, Chen et al. (2022) utilized a multi-objective ACO algorithm to solve military problems, considering heterogeneity in capability, adaptability and safety. In recent years, the flourishing development of GPUs has propelled machine learning and deep learning methods to prominence (Paul et al., 2022). These approaches automatically extract features through multi-stage abstraction and thus can be suitable across a wide range of fields, even though improvements in generalization are still needed (Vivekanandan et al., 2023).

MAPF, also classified as an NP-Hard problem, is devoted to find conflict-free paths for multiple robots from start to goal positions. Common optimal solvers (Stern, 2019) include extensions of A*, increasing cost tree search, constraint programming algorithm, and conflict-based Search. Although guaranteeing optimal solutions, these methods require substantial computational resources. Depending on different scenarios, a trade-off between solution quality and calculation time may emerge. Priority planning (Silver, 2005) and push-and-swap algorithm (Luna & Bekris, 2011) have been widely adopted in practice due to their computational efficiency and straightforward implementation.

The cost estimation of MRTA is often involved in the paths of the robots, which results in a coupling relationship between MRTA and MAPF. It is essential to consider both simultaneously to achieve optimal solutions (Landry et al., 2013), which gives rise to the problem of Combined Task Assignment and Path Finding (CTAPF). To handle this problem, Henkel et al. (2019) developed task conflict-based search (TCBS) to provide an optimal solution. Brown et al. (2020) also constructed a four-stage stacked process integrating greedy algorithms, CBS, incremental priority search and A*, aiming to ensure system completeness. Chen et al. (2021) deemed marginal cost as a heuristic, which is combined with the priority-based path searching to tackle complex delivery problems in logistics environments. Ng et al. (2021) hybridized CBS, greedy algorithms and ACO to optimize the CTAPF problem with temporal constraints and task completion rewards, while handling dynamic and uncertain of robot movements in small-size scenarios. However, these algorithms are unsuitable for dynamic re-planning on large-scale problems, since requiring a large search space and suffering from the computational time that surges exponentially with the increasing number of tasks and robots.

1.3. Contributions

The contribution of this work is to develop an approach of multi-robot adaptive task allocation and path finding to address the dynamic CTAPF problem, in considerations of the pickup-and-delivery problem concerning capacity and heterogeneity of the robots. The designed framework is flexible and can incorporate other dynamic issues. However, in order to emphasizing the performance and the feasibility of the proposed framework, this work designates the term ”dynamic” as merely the change of task quantity. The proposed algorithm of task allocation combines instantaneous assignment for the fastest response and ACO for further optimization. Meanwhile, modified Space Time A* (STA*) (Silver, 2005) is implemented for the fastest estimation of path cost.

1.4. Organization

The following sections are listed as follows. Section “Problem formulation” defines the dynamic CTAPF problem and metrics. Section “Proposed solution” details the whole multi-robot task allocation and navigation system. Next, Section “Simulation and experimental results” demonstrates the simulations and experimental results. Finally, Section “Conclusion” concludes the work and specifies the future prospective.

2. Problem Formulation

Multi-agent pickup-and-delivery (MAPD) problems are often adopted to describe the problems of logistics, transportation and traffic planning. It can also be applied to restaurant services and supply delivery in search and rescue missions. The MAPD problem is dedicated to optimizing the arrangement of picking up and delivering goods across various locations. The key challenge lies in determining the optimal sequence of multiple points while minimizing the overall completion time. The task considered in this work includes two additional features:

Each robot can carry multiple but limited items at the same time, which allows the robot to flexibly choose either to continue or to waive pickup sub-tasks, and afterwards move directly to the position of the delivery task.

The fleet, consisting of a heterogeneous multi-robot system, requires consideration of whether a robot can execute a specific task.

In general, a mobile robot can be typically divided into two subsystems: the chassis and the task execution. The former helps the robot move to a designated destination, while the latter interacts with the environment to accomplish specific tasks or goals, such as gripping or moving objects. This work focuses on the path of the chassis and disregards the required time for the task execution, which means that the robot completes its own task once reaching the specified location. To enhance the system efficiency, the hardware adopts the omni-wheel robot, which offers higher degrees of freedom compared to the traditional differential drive. Hence, the robot can reach its target more quickly and avoid dynamic obstacles more flexibly. Compared to other omnidirectional options like Mecanum wheel or swerve drive, the employed omni-wheel robot is also advantageous in size.

2.1. Combined Task Allocation and Path Finding

In the CTAPF problem, a fleet $R = {r_{i} ∣ i = 1, 2, \dots, m}$ consists of $m$ robots, which need to collaboratively complete $n$ transportation tasks $P = {p_{j} ∣ j = 1, 2, \dots, n}$ . Each robot $r_{i}$ is characterized by three elements $⟨ o_{i}, c_{i}, a_{i} ⟩$ , where $i \in N$ and $i \leq m$ . Here, $o_{i}$ represents the initial 2D coordinates of the starting position of the robot. $c_{i} \in N$ , the task-capacity limit, represents the maximum number of items the robot can carry at any given time. And, the capability of the robot is denoted as $a_{i}$ . Similarly, each task $p_{j}$ is composed of $⟨ s_{j}, g_{j}, a_{j} ⟩$ , where $j \in N$ and $j \leq n$ . Here, $s_{j}$ and $g_{j}$ represent the pickup and delivery sub-tasks, respectively. $a_{j}$ is the type of robot capability required to complete the task. Both $a_{i}$ and $a_{j}$ belong to the set ${s u c k, g r i p, b o t h}$ . Based on these relationships, this research constructs a capability matrix $B \in N^{m \times n}$ , where $B = {b_{i, j}}$ with the element $b_{i, j} \in {0, 1}$ indicates whether the robot $r_{i}$ has the required capability ( $b_{i, j} = 1$ ) to perform task $p_{j}$ or not ( $b_{i, j} = 0$ ). Moreover, the path of each robot is defined as $q_{i} = (v_{1}^{i}, v_{2}^{i}, \dots, v_{k}^{i})$ , where $v_{1}^{i} = o_{i}$ and $k \in N$ is the total number of waypoints, which depends on the map size, map resolution and the paths of other robots. Then, the position of the robot $r_{i}$ at time $t$ can be written as $q_{i} [t]$ .

After the search, the system provides the allocated solution, which means the task sequence for each robot. The task sequence for the robot $r_{i}$ is $γ_{r_{i}} = μ_{r_{i}} ({s_{j}, g_{j} ∣ κ_{i, j} = 1, j = 1, 2, \dots, n})$ , where $μ_{r_{i}}$ is a permutation variable used to represent the order of sub-tasks assigned to the robot $r_{i}$ . $κ_{i, j} \in {0, 1}$ is an element of the allocation matrix $K \in N^{m \times n}$ . If $κ_{i, j} = 1$ , both $s_{j}$ and $g_{j}$ are performed by the robot $r_{i}$ . In the field of industrial scheduling, the makespan is often applied as the optimization objective function, which is defined as the time interval from the start of system operation to the completion of last task. Combining the aforementioned objectives, the problem in this research can be formulated as an NILP optimization:

{argmin}_{r_{i} \in R} (max ({PL (γ_{r_{1}}), \dots, PL (γ_{r_{i}})}))

(1)

subject to :

\begin{aligned} κ_{i j} & = b_{i j}, & \forall i \in {1, \dots, m}, \forall j \in {1, \dots, n} \\ L_{r_{i}} (t) & \leq c_{i}, & \forall r_{i} \in R, \forall i \in {1, \dots, m} \\ q_{i} [t] & \neq q_{e} [t], & i \neq e, \forall i, e \in {1, \dots, m}, \forall t \\ (q_{i} [t], q_{i} [t + 1]) & \neq (q_{e} [t + 1], q_{e} [t]), & i \neq e, \forall i, e \in {1, \dots, m}, \forall t \\ (q_{i} [t], q_{i} [t + 1]) & ⊥̸ (q_{e} [t], q_{e} [t + 1]), & i \neq e, \forall i, e \in {1, \dots, m}, \forall t \end{aligned}

(2)

where PL is the path length for the robot to complete its task sequence, which is equivalent to the spent time, assuming all robots move at a constant speed.

L_{r_{i}} (t)

represents the number of objects carried by the robot at time

t

⊥̸

is the symbol of non-intersection or non-perpendicular of two path. Equation 2 describes the constraint that the robot must meet its capability requirements to execute the task. Equation 3 states that at any given moment, the number of items carried by the robot cannot exceed its capacity. Equations 4-6 are designed to prevent three common types of conflicts among robots: vertex conflict, positional swap, and paths intersection, as illustrated in Figure 2.

Figure 2.

Conflict Types Among Omnidirectional Robots.

However, in single-objective optimization problems, multiple solutions often arise. To eliminate this impact, an additional objective function is introduced as a secondary criterion to optimize the task sequence of the robot with the second-longest completion time in this work.

2.2. Dynamic Condition

There exist many uncertainties in the real world. For example, robots suddenly break down or new resources become available. Unexpected events may also occur during movement, causing the cost of completing tasks to differ significantly from the estimates. These dynamics require CTAPF algorithms to perform re-planning, and the response time cannot be delayed; otherwise, the performance will be significantly compromised. To focus on delivery problems, this work defines the aspect of ”dynamic” as ”changes in the number of tasks”, which means that new tasks may join during operation and force the system to respond in real-time. In real-world scenarios, this could happen in logistics centers where fluctuations in order volume may affect system operation. Similarly in the rescue environment, the appearance of new individuals in need of rescue requires the system to adjust flexibly to complete tasks efficiently.

2.3. Performance Metrics

The primary performance metric is based on a task-oriented perspective, comparing the differences in makespan among the results of various algorithms. Since the robots do not move at a constant speed during the practical operations, the actual evaluation will adopt real time as the comparison standard, instead of path length used in Equation 1.

In addition, this work aims to discuss another important metric. The total energy consumption of the system is a critical issue worth exploring. Due to hardware limitation, it will be approximated by the combined path length of each robot, which is so called the total path length (TPL). This work simply assumes that the overall energy consumption is proportional to the total path length (TPL) of all robots. Under certain environmental assumptions, simultaneously optimizing the makespan and the TPL is categorized as the multi-objective optimization, which is not within the scope of this work.

This work focuses on dynamic problems and needs to evaluate the computational efficiency of the system. However, in dynamic scenarios, the number of remaining tasks to be processed varies with time, which leads to difficulty for the usage of unified comparison benchmarks. Therefore, the comparison will be handled using the calculation time (CT) across various static maps. CT is defined as the time elapsed from when the proposed algorithm is called to when the allocation sequence is computed.

3. Proposed Solution

The dynamic CTAPF solver applies a modified version of the STA $^{*}$ (Silver, 2005) as the method for multi-robot pathfinding, which provides cost estimation for task allocation. The STA $^{*}$ , an extension of the A $^{*}$ algorithm, is a priority-based planning method that extends the time dimension and uses a hash table to record planned paths to avoid conflicts. Resumable reverse A $^{*}$ is utilized to generate heuristic values and to reduce the computational load. In terms of the movement cost, the original method would choose the shortest path rather than the one that spends the minimal time. Therefore, the time consumed by each movement is introduced to adjust the approach and can prevent robots from simply waiting in place.

The framework of the dynamic task allocation algorithm proposed in this work, Instantaneous Allocation with Ant Colony Optimization (IAACO), is shown in Figure 3. It can be divided into two phases. When a dynamic event occurs, the instantaneous task allocation (MWMES), consisting of maximum weight matching and local optimization, is executed first to quickly obtain an acceptable solution. Subsequently, during robot operations, the adaptive ACO algorithm is responsible for simultaneously improving the quality of the solution. If no new task emerges and the optimizer has already begun, task information will be published to the robots based on the current best solution. Therefore, the proposed IAACO framework can operate effectively without extensive parameter optimization when applying the ACO algorithm. The iteration count and lookahead timestep are the only two parameters that are neccessarily adjusted according to the movement speed of the robot and the computation time per ACO generation.

Figure 3.

Flow Chart of the IAACO Optimization Process.

To ensure the system can continue monitoring dynamic changes in the environment while the optimization process is running, two threads are created to separate the two phases. Thread 1 works for receiving observation data and for issuing the current tasks to the corresponding standby robot; hence, the initial task assignment is quickly allocated when dynamic condition occurs. Thread 2, as an auxiliary thread, focuses on executing relatively time-consuming optimization algorithms.

3.1. Mwmes

The solution calculated by the instantaneous task allocation method provides the most immediate response to environmental changes and serves as the reference for updating the pheromone map in the ACO. The computation process primarily integrates the MWM, Voronoi Diagram and external swapping operation (EXSO), collectively named as MWMES.

MWMES can be simplified into three steps. Firstly, a Voronoi Diagram is constructed using the initial coordinates of the robots, and each task is categorized to the corresponding robot. Next, a bipartite graph is constructed for MWM. Each loop assigns $N$ tasks to $N$ robots, and then updates the nodes and the weights in the graph. This step is repeated until all tasks are allocated. Finally, a local search is conducted on the task sequence of each robot $r_{i}$ predicted to have the longest execution time. Tasks that are the closest to the initial position of $r_{i}$ and are categorized for another robot ( $r_{e}$ ) are reassigned to $r_{e}$ . Then, a greedy algorithm is executed individually for each robot. If the makespan improves, the new solution will be adopted. The process of each step will be detailed in the following paragraphs.

For the first step, the Voronoi Diagram is a type of geometric structure used to divide a plane into several regions. In this work, the initial coordinates of the robots are considered as seed points. As being all inside the same segmented area, the sub-tasks of a task will be assigned to the robot corresponding to that area, which implies a higher probability that the task will be executed by the assigned robot, as shown in Figure 4. However, if obstacles are present, the map can be regarded a three-dimensional space, and the actual cost of reaching a task point is no longer a straight-line distance. One of the features of the Voronoi Diagram addresses this issue, where any point within a region will have the shortest distance to its corresponding seed point. In this case, the heuristic values in STA $^{*}$ can be used for finding distances between tasks and robots.

Figure 4.

Results of the Two-Robot Scenario via Voronoi Diagram.

Step two constructs the task allocation problem as a bipartite graph, as shown in Figure 5. The left nodes $U_{i}$ and the right nodes $V_{j}$ represent robots and sub-tasks, respectively. The weight on each edge is defined as in equation 7, determined by the ratio of $b_{i, j}$ and the path length $d_{i, j}$ between two nodes.

w (U_{i}, V_{j}) = \frac{b_{i, j}}{d_{i, j}}

(7)

The Hungarian algorithm (Kuhn, 1955) is then employed to perform MWM, finding a set of edges that maximizes the total weight, with each vertex connected to at most one edge. Initially, the robot nodes are at their starting coordinates, and the right-side nodes only represent pickup sub-tasks. After each loop, the position information of the robot is updated to the location of the corresponding sub-task, and this sub-task node is then deleted. If the sub-task is a pickup task, a delivery node is added, and only one edge connects the robot that owns this task.

Figure 5.

Bipartite of the Two-Robot Scenario.

Once the results of the Voronoi Diagram classification and MWM are obtained, these two pieces of information can be integrated to implement the local optimization method proposed in Step three. When multiple tasks in $γ_{r_{i}}$ simultaneously mismatch between classification and allocation, the earlier tasks in the execution sequence are chosen for extraction, because subsequent optimizations will be made using the ACO. Here, it is vital that the near optimum mainly focuses on the choice for the execution sequence in a short-term period.

3.2. Adaptive ACO

ACO simulates the foraging behavior of virtual ants, where the route of each ant represents a potential solution to the problem. The quality of the solution is influenced by factors, such as the pheromone concentration and the optimization function. In the proposed framework, ACO performs optimization while the robots are operating. However, in complex or large-scale problems, it takes longer to converge, and by the time the search of the proposed algorithm is ended, it may not be clear whether some tasks have already been completed. This can lead to discrepancies between the task sequence produced by the solution and the actual situation. To address this problem, this research introduces a Lookahead Timestamp $l_{t}$ .

As shown in Figure 6, the red and blue dashed arrows represent the paths calculated by the previously mentioned MWMES respectively for two robots, while the cross symbols indicate the positions of the robots after $l_{t}$ units of time. ACO stands for optimizing the remaining tasks after this timestamp. In this way, ACO not only solves the aforementioned issue but also allows users to flexibly adjust performance base on the features of application environment.

Figure 6.

The Concept of Lookahead Timestep in the Two-Robot Scenario.

The flow chart of ACO is illustrated in Figure 7. The proposed algorithm firstly initializes the environment information and task status based on MWMES, constructs the ACO map, and then enters a nested loop. The searching process of each ant for a solution primarily includes choosing robot, state transitions, planning a single path, and updating the iteration best solution. The robot selection is based on finding the robot with the shortest estimated task execution time (distance) at present. Path planning is performed using STA $^{*}$ . Once the solutions for each iteration are calculated, the global best solution and the pheromone concentration on the ACO map are updated.

Figure 7.

Flow Chart to Solve the ACO in the CTAPF Problem.

The state transition refers to a situation that a robot moves from one node to the next one on the ACO map, where in other words, the next task is selected by the robot to execute. This process operates similarly to the greedy algorithm but incorporates pheromone influence and randomness. Firstly, the probability of transitioning from node $x$ to node $y$ is calculated (Wang et al., 2012):

Φ_{x, y} = \frac{(τ_{x, y})^{α} (η_{x, y})^{β}}{\sum_{z \in a l l o w e d} (τ_{x, z})^{α} (η_{x, z})^{β}}

(8)

Here,

τ

represents the pheromone value,

η

is the heuristic value, and

α

and

β

are parameters used to adjust the weights of these two factors.

allowed

refers to feasible nodes, i.e., the tasks that are still available to be executed. Then, the next node is determined using a roulette selection strategy, where randomness increases the possibility of exploration, while pheromone and heuristic value ensure exploitation.

$η$ is usually defined as the reciprocal of the path length, but when the map size changes and task density varies, the magnitudes of this value and pheromone concentration will differ, making parameter adjustment non-intuitive. Therefore, to prevent the performance of the proposed algorithm from being over dependent on trial-and-error parameters, this work scales the heuristic value through the proportional mapping, as formulated in Equation 9.

\begin{aligned} η_{x, y} = & (1 + \frac{n}{λ_{w} \cdot λ_{h}}) \cdot \\ (τ_{m i n} + \frac{(τ_{m a x} - τ_{m i n}) \cdot (\frac{d_{m a x}}{d_{x, y}} - 1)}{\frac{d_{m a x}}{d_{m i n}} - 1}) \end{aligned}

(9)

Here,

d_{m a x}

and

d_{m i n}

are the distances between the farthest tasks and between the closest tasks, respectively. And

τ_{m a x}

and

τ_{m i n}

are the upper and lower bounds of pheromone values, respectively. The number of tasks

n

and the map dimensions

λ_{w}

and

λ_{h}

are also considered.

Another important aspect of ACO is the process of pheromone updating during each iteration ( $it$ ), which is shown as Equation 10 and Equation 11 (Wang et al., 2012):

\begin{aligned} Δ τ_{x, y} (i t) = {\begin{matrix} Q / D_{b e s t} & , x, y \in Ω_{b e s t} \\ 0 & , o t h e r w i s e \end{matrix} \end{aligned}

(10)

\begin{aligned} τ_{x, y} (i t^{'}) = (1 - ρ) \cdot τ_{x, y} (i t) + Δ τ_{x, y} (i t) \end{aligned}

(11)

Where

i t^{'}

is the next iteration.

Ω_{b e s t}

represents the path traveled by the global best solution, i.e., the task allocation sequence.

D_{b e s t}

is the total path length of this solution, while

Q

is a weight parameter. The updating process consists of two stages: the first one is the evaporation occurs based on the parameter

ρ

, and the second one is involved with adding the new pheromone concentration

Δ τ_{x, y}

to edges.

When the map becomes larger, the total path length will naturally become longer, which indirectly causes the same $Q$ value to have different effects in various scenarios. If $Δ τ_{x, y}$ is smaller than the evaporation, the proposed algorithm may experience a reduction in pheromone influence, leading to stagnation near the minimum value and ultimately converging to a suboptimal local solution. This work claims that ACO can provide broader search capabilities, so a simple brute-force method is employed to dynamically adjust $Q$ . That is, if more than a half of the edges are updated and the pheromone concentration increases more than it decreases, the value of $Q$ is reduced. Conversely, if the concentration decreases more than it increases, $Q$ is multiplied with a factor greater than one.

4. Simulation and Experimental Results

When handling sequential tasks, the traditional centralized algorithms primarily aim to search the global optimal solution and rarely discuss re-planning. As a result, the traditional centralized algorithms are constrained by the computational speed and therefore are unable to effectively tackle dynamic problems in practice. To validate the dynamic performance of the proposed method, the Random Greedy (RG) is consequently employed as a comparison benchmark, due to its broad applicability and excellent computational efficiency. By introducing randomness, RG increases the diversity of solutions, avoiding the common pitfall of traditional greedy algorithms that get stuck in local optima. In each iteration, RG randomly rearranges the order in which robots choose tasks and adopts a heuristic to greedily assign the task with the lowest cost. STA $^{*}$ is then responsible for planning the path and updating the robot positions.

The aforementioned algorithms are all implemented in the Robot Operating System (ROS) and tested in the simulation environment. Table 1 and Appendix show the settings of the four maps designed for this research. Each map owns one static and two dynamic scenario assumptions. Table 2 provides the detailed settings of ACO parameters. The difference between two dynamic scenarios lies in the time when new tasks occur. In Scenario 2, dynamic tasks are spread out over different time periods. However, all tasks in Scenario 3 occur at a specific time, which increases the computational load. Among the four maps, only Map A features the homogeneous robot fleet, the others have the heterogeneous MRS. The map dimensions are represented in pixels (px), with a resolution of 0.2 m/px in both the simulation testbed and the real-world environment. The carrying capacity limit for each robot is set to 3, and the task count is doubled due to the two sub-tasks: pick-up and delivery. Given the inherent randomness of the system, each algorithm is executed 30 times in each scenario, and the mean, standard deviation, best, and worst solutions for each metric are recorded for comparison.

Table 1.
Settings of Four Maps in the Simulation Environment (A2 and B3 also for Experiments).

Map A Map B Map C Map D

Scenario A1 A2 A3 B1 B2 B3 C1 C2 C3 D1 D2 D3

Map Size 12 $\times$ 11 12 $\times$ 11 15 $\times$ 15 27 $\times$ 27

Number of robots 2 3 5 3

Number of tasks 52 102 152 302

Number of dynamic tasks 0 22 0 32 0 52 0 52

	Map A	Map B	Map C	Map D
Map Size	12 $\times$ 11	12 $\times$ 11	15 $\times$ 15	27 $\times$ 27
Number of robots	2	3	5	3
Number of tasks	5*2	10*2	15*2	30*2
Number of dynamic tasks	0	2*2	0	3*2	0	5*2	0	5*2

Table 2.

ACO Parameters.

Parameter	$N_{a n t}$	$ρ$	$α$	$β$
Definition	number of ants	evaporation rate	factor to influence	factor to influence
			pheromone concentration	heuristic value
Value	15	0.02	0.6	2.0
Parameter	$Q$	$τ_{i n i t}$	$τ_{m a x}$	$τ_{m i n}$
Definition	weight	initial pheromone	maximum pheromone	minimum pheromone
	total path length	concentration	concentration	concentration
Value	200	100	100	1

4.1. Simulation Results

Figure 8 shows the mean and standard deviation for the makespan of each algorithm in Map A. In the static Map A1, both MWMES and IAACO are able to find the optimal solution, with an average makespan of around 43 seconds. This is a significant improvement compared to the makespan 68 seconds which RG spends, with an average performance enhancement of 36%. However, in Maps A2 and A3, the performance of MWMES performance drops considerably. The reason is that MWM operates similarly to a prioritized greedy algorithm, and when the positions of the robots are unable to evenly divide the task points on the map, EXSO has more difficulty in optimizing. Nevertheless, further searching with adaptive ACO results in an average makespan improvement of 15% to 20% over RG.

Figure 8.

The Mean and Standard Deviation of Makespan by RG, MWMES and IAACO for Map A.

Figure 9 shows the mean and standard deviation for the TPL performance for each algorithm in Map A. Even though the map size is not large, the average value of RG is still more than 2 meters higher than the IAACO. Furthermore, the small standard deviation indicates that IAACO consistently converges to a more stable solution in all three scenarios of Map A, as well as achieving the optimal solution for these scenarios.

Figure 9.

The Mean and Standard Deviation of TPL by RG, MWMES and IAACO for Map A.

Figures 10 and 11 respectively show the mean and standard deviation for the makespan and TPL of each algorithm in Map B. Regardless of the metric or scenario, IAACO outperforms the other two algorithms, with makespan improvements of 27%, 14%, and 15% compares to RG across three scenarios, respectively. On the other hand, MWMES cannot be perfectly adapted to all conditions. However, the standard deviation of MWMES is generally better than the RG, which makes it a more stable reference for adaptive ACO optimization. MWMES is also designed to focus on whether the task sequence is appropriate in the short term.

Figure 10.

The Mean and Standard Deviation of Makespan by RG, MWMES and IAACO for Map B.

Figure 11.

The Mean and Standard Deviation of TPL by RG, MWMES and IAACO for Map B.

Map C is a map where tasks and robots are more densely distributed. Figure 12 shows the mean and standard deviation for the makespan. The performance of MWMES is similar to the RG, though the search of the latter is less stable, which, on the other hand, sometimes allows RG to escape its local optima. IAACO demonstrates improvements of 27%, 14%, and 15% across the three scenarios respectively, which can prove the powerful effect. Figure 13 shows the mean and standard deviation for the TPL. IAACO performs better in terms of makespan. However, in Map C1, the average TPL of IAACO is only similar to the MWMES. This is mainly because the single optimization objective in this work tends to ignore the paths of the other robots. In some conditions, TPL and makespan present a trade-off, which means that sacrificing total energy consumption may be necessary to improve operational efficiency.

Figure 12.

The Mean and Standard Deviation of Makespan by RG, MWMES and IAACO for Map C.

Figure 13.

The Mean and Standard Deviation of TPL by RG, MWMES and IAACO for Map C.

Map D is a map with a large number of tasks. Figure 14 shows the mean and standard deviation for the makespan, which again demonstrates the excellent performance of the method proposed in this research. Although MWMES works poorly on the D2 map, the solution still converges to a good result through the optimization of the adaptive ACO. IAACO shows makespan improvements of 14%, 12%, and 13% over RG, respectively in the three scenarios. Due to the sparse distribution of task points and the long distances between them, the degree of optimization is not as significant as in the previous maps. Figure 15 shows the mean and standard deviation for the TPL results. From the performance of MWMES in Map D1, it is clear that the makespan and TPL are not necessarily positively correlated.

Figure 14.

The Mean and Standard Deviation of Makespan by RG, MWMES and IAACO for Map D.

Figure 15.

The Mean and Standard Deviation of TPL for Map D.

Table 3 compares the average CT values of MWMES and RG across the four static maps. The similar values show that MWMES can indeed provide timely responses to the environment. The subsequent optimization time for adaptive ACO can be adjusted based on the user experiences and the characteristics of the environment. The combined statistics of the makespan and TPL metrics clearly demonstrate the effectiveness of the proposed IAACO framework.

Table 3.

Average CT in the Four Static Scenarios.

	Average CT (s)
	A1	B1	C1	D1
RG	0.0055	0.0073	0.0150	0.0476
MWMES	0.0083	0.0086	0.00169	0.0738

Both Map A and Map B hold the identical map size but different situations of obstacle existence. There are obstacles in Map A but not in Map B. The solution stability of RG performs better in some scenarios of Map B. But the RG performs the less stable makespan and TPL than the IAACO entirely in the scenarios of Map A, where the obstacles exist. It is shown that the instability of the decisions by the RG will be not avoided in the maps with obstacles. In contrast, the proposed IAACO yet behaves stably even in the maps with obstacles.

The number of robots in Map C is the largest among all maps. The simulation results of Map C indicate that the proposed IAACO wins the best performances for the makespan and TPL among all the methods, even though there exists higher randomness in massive decision combinations from all of the five robots. Moreover, the worst results of the proposed IAACO are still superior to the RG in both the metrics of the makespan and TPL.

Map D differs from Map C in holding the larger map, the larger number of tasks, and the less number of robots. Both maps C and D have no obstacle. By comparing the results of Maps C and D, the RG achieves the worse means of makespan and TPL but demonstrates slightly better stability than the IAACO in certain scenarios of Map D, which is similar to the circumstances in Map B. The reason is that the smaller number of robots in Map D than Map C causes the lower randomness in Map D than Map C by applying the RG. However, the worst makespan and TPL means of the IAACO even surpass the best solutions of the other two methods. Hence, it can be asserted that the IAACO accomplishes better results than the RG in Map D, where the map is the largest and the number of tasks is the hightest.

4.2. Experimental Setup and Results

Finally, the experiments were conducted in a real-world environment based on the total six settings of Maps A and B, and the experimental results verify the feasibility of proposed approach, which can handle dynamic scenarios where the number of tasks in the environment changes. The real-world experimental setup is demonstrated in Figure 16, and the system architecture of the proposed multi-robot framework is provided in Figure 17. Due to space limitation in practical experiments, there are merely partial experimental results that can be demonstrated in Figures 18 to 21.

Figure 16.

Experimental Environment with the Camera on the Ceiling and the Testbed on the Ground.

Figure 17.

System Architecture of the Tested Multi-Robot System.

Figure 18.

Execution Paths of the Tested Robots Based on the Settings of Map A2.

Figure 19.

Screenshots of the Real-World Experiment Based on the Settings of Map A2.

Figure 20.

Execution Paths of the Tested Robots Based on the Settings of Map B3.

Figure 21.

Screenshots of the Real-World Experiment Based on the Settings of Map B3.

Figures 18 and 19 demonstrate the experimental results under the task setting of Map A2, with the makespan of 51.62 seconds. Figures 20 and 21 present the experimental results under the task setting of Map B3, where the makespan is 51.44 seconds. The makespans of the experimental results in Maps A2 and B3 that are both longer than the simulation results. This phenomenon majorly results from the communication latency accumulated by each command executed by the corresponding robot and the time cost spent by the image processing.

5. Conclusion

This research proposes a dynamic CTAPF algorithm that applies MWM for real-time task allocation, combines Voronoi Diagram and EXSO for single optimization, and then employs adaptive ACO to continuously improve the solution quality during robot operation. To address the dynamic task allocation for pickup-and-delivery problems in complex environment, the modified STA* is used for the multi-robot collision-free path planning, being able to estimate the cost of task execution and to consider carrying capacity and heterogeneity of robots.

From the simulation results, it is proved that the proposed algorithm across 12 scenarios enhance the performance of the makespan and the TPL by up to 36% and 21% respectively, compared to the baseline algorithm of RG. In real-world experiments, the proposed IAACO framework is also validated under multiple scenario assumptions, confirming its capability for real-time responses. IAACO only experiences performance degradation when dealing with high-density maps, such as Map C, which is designed as a high-density environment in this work. As mentioned earlier, IAACO features a modular design. With advancements in hardware and software technologies, the ACO module can be computed in a parallel manner by CUDA GPUs or even replaced with other machine learning methods.

In practice, as the number of tasks and robots increases, the operational map size also tends to grow, which leads to longer travel distances per task execution. Hence, not only the ACO computation time increases, but also all of the robots travel longer distances in a large-scale map. For instance, in Map D, even though ACO computation takes approximately 9 seconds, the actual execution time of all robots is significantly much longer. In this way, total ACO computation time can be sliced into several small fragments that are shared at each travel period of all robots. Moreover, the proposed optimization framework can allow users to adjust the iteration count and lookahead timestep to balance the computation time and the overall optimization makespan. Consequently, in addition to the performed simulations and experiments, the proposed IAACO framework can be feasibly applied for the large-scale problems in the real world.

Supplemental Material

Footnotes

Acknowledgement

The authors would like to thank the partial support by Ministry of Sciences and Technology, TAIWAN, the project under the grant number NSTC 112-2221-E007-065.

ORCID iD

Weicheng Wang

Rongshun Chen

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Supplemental Material

All supplemental material mentioned in the text is available in the online version of the journal.

Appendix

This appendix presents all the 2D grid maps designed for this research. Figures A1 to A8 illustrate the distribution of robots and tasks across all scenarios. The map dimensions are measured in pixels, with a resolution of 0.2 m/px set for both simulation and experiments. Larger circular icons represent robots, distinguished by different colors according to their unique IDs. The green, gray, pink and brown icons indicate the tasks of static pickup, static delivery, dynamic pickup and dynamic delivery, respectively. Black square icons are illustrated for the obstacles. Figure A1.

The Setup of Map A1.

Figure A2.

The Setup of Maps A2 and A3.

Figure A3.

The Setup of Map B1.

Figure A4.

The Setup of Maps B2 and B3.

Figure A5.

The Setup of Map C1.

Figure A6.

The Setup of Maps C2 and C3.

Figure A7.

The Setup of Map D1.

Figure A8.

The Setup of Maps D2 and D3.

References

Arif

M. U.

Haider

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

Aziz

Chan

Cseh

Ramezani

Wang

(2021). Multi-robot task allocation-complexity and approximation. In Proceedings of the 20th International conference on autonomous agents and multiagent systems (pp. 133–141). International Foundation for Autonomous Agents and Multiagent Systems.

Barboza

V. G. R. L.

Kniess

(2024). Task allocation based on simulated annealing for edge industrial internet. In International conference on advanced information networking and applications (pp. 210–221). Springer.

Brown

Peltzer

Sehr

M. A.

, et al. (2020). Optimal sequential task assignment and path finding for multi-agent robotic assembly planning. In 2020 IEEE International conference on robotics and automation (ICRA) (pp. 441–447). IEEE.

Chen

Alonso-Mora

Bai

, et al. (2021). Integrated task assignment and path planning for capacitated multi-agent pickup and delivery. IEEE Robotics and Automation Letters, 6(3), 5816–5823.

Chen

Liu

W. L.

Zhong

(2022). An efficient multi-objective ant colony optimization for task allocation of heterogeneous unmanned aerial vehicles. Journal of Computational Science, 58, 101545.

Chen

Qing

, et al. (2022). Consensus-based bundle algorithm with local replanning for heterogeneous multi-UAV system in the time-sensitive and dynamic environment. The Journal of Supercomputing, 78(2), 1712–1740.

Choi

H. L.

Brunet

How

J. P.

(2009). Consensus-based decentralized auctions for robust task allocation. IEEE Transactions on Robotics, 25(4), 912–926.

Ghassemi

Chowdhury

(2022). Multi-robot task allocation in disaster response: Addressing dynamic tasks with deadlines and robots with range and payload constraints. Robotics and Autonomous Systems, 147, 103905.

10.

Henkel

Abbenseth

Toussaint

(2019). An optimal algorithm to solve the combined task allocation and path finding problem. In 2019 IEEE/RSJ International conference on intelligent robots and systems (IROS) (pp. 4140–4146). IEEE.

11.

Huang

G. S.

Y. J.

(2017). To build a smart unmanned restaurant with multi-mobile robots. In 2017 International automatic control conference (CACS) (pp. 1–6). IEEE.

12.

Hussein

Khamis

(2013). Market-based approach to multi-robot task allocation. In 2013 International conference on individual and collective behaviors in robotics (ICBR) (pp. 69–74). IEEE.

13.

Kim

Lee

(2023). Multi-robot task scheduling with ant colony optimization in antarctic environments. Sensors, 23(2), 751.

14.

Kong

Gao

Wang

Liu

(2019). Multi-robot task allocation strategy based on particle swarm optimization and greedy algorithm. In 2019 IEEE 8th Joint international information technology and artificial intelligence conference (ITAIC) (pp. 1643–1646). IEEE.

15.

Kuhn

H. W.

(1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2), 83–97.

16.

Landry

Henrion

Hömberg

, et al. (2013). Task assignment, sequencing and path-planning in robotic welding cells. In 2013 18th International conference on methods & models in automation & robotics (MMAR) (pp. 252–257). IEEE.

17.

Luna

Bekris

K. E.

(2011). Efficient and complete centralized multi-robot path planning. In 2011 IEEE/RSJ International conference on intelligent robots and systems (pp. 3268–3275). IEEE.

18.

C. Y.

Yeh

Y. W.

Wang

W. C.

, et al. (2021). Dynamic task allocation and pathfinding under precedence and temporal constraints. In 2021 International automatic control conference (CACS) (pp. 1–5). IEEE.

19.

Nunes

Manner

Mitiche

, et al. (2017). A taxonomy for task allocation problems with temporal and ordering constraints. Robotics and Autonomous Systems, 90, 55–70.

20.

Kim

Ahn

, et al. (2016). PSO-based optimal task allocation for cooperative timing missions. IFAC-PapersOnLine, 49(17), 314–319.

21.

Patil

Bae

Park

(2022). An algorithm for task allocation and planning for a heterogeneous multi-robot system to minimize the last task completion time. Sensors, 22(15), 5637.

22.

Paul

Ghassemi

Chowdhury

(2022). Learning scalable policies over graphs for multi-robot task allocation using capsule attention networks. In 2022 International conference on robotics and automation (ICRA) (pp. 8815–8822). IEEE.

23.

Sariel-Talay

Balch

T. R.

Erdogan

(2009). Multiple traveling robot problem: A solution based on dynamic task selection and robust execution. IEEE/ASME Transactions on Mechatronics, 14(2), 198–206.

24.

Schneider

Sklar

E. I.

Parsons

, et al. (2015). Auction-based task allocation for multi-robot teams in dynamic environments. In Towards autonomous robotic systems: 16th annual conference, TAROS 2015, Liverpool, UK, September 8-10, 2015, Proceedings 16 (pp. 246–257). Springer.

25.

Silver

(2005). Cooperative pathfinding. In Proceedings of the AAAI conference on artificial intelligence and interactive digital entertainment Vol. 1, (pp. 117–122). AAAI Press.

26.

Stanulovic

Mitton

Mezei

(2022). Routing with face traversal and auctions algorithms for task allocation in WSRN. Sensors, 21(18), 6149.

27.

Stern

(2019). Multi-agent path finding–an overview. In Artificial Intelligence: 5th RAAI Summer School, Dolgoprudny, Russia, July 4–7, 2019, Tutorial Lectures (pp. 96–115). Springer.

28.

United Nations (2022). World Population Prospects 2022: Summary of Results. Population Division.

29.

Vivekanandan

Wirth

Karlbauer

, et al. (2023). A reinforcement learning approach for scheduling problems with improved generalization through order swapping. Machine Learning and Knowledge Extraction, 5(2), 418–430.

30.

Wang

(2012). Multi-robot task allocation based on ant colony algorithm. Journal of Computing, 7(9), 2160–2167.

31.

Wong

W. K.

Chew

I. M.

(2019). A review on metaheuristic algorithms: recent trends, benchmarking and applications. In 2019 7th International conference on smart computing & communications (ICSCC) (pp. 1–5). IEEE.

32.

Gao

Yuan

, et al. (2022). A dynamic task allocation algorithm for heterogeneous UUV swarms. Sensors, 22(6), 2122.

33.

Zhao

Yang

Zhang

, et al. (2022). A task allocation approach of multi-heterogeneous robot system for elderly care. Machines, 10(8), 622.

	Map A			Map B			Map C			Map D
Scenario	A1	A2	A3	B1	B2	B3	C1	C2	C3	D1	D2	D3
Map Size	12 $\times$ 11			12 $\times$ 11			15 $\times$ 15			27 $\times$ 27
Number of robots	2			3			5			3
Number of tasks	5*2			10*2			15*2			30*2
Number of dynamic tasks	0	2*2		0	3*2		0	5*2		0	5*2