Sage Journals: Discover world-class research

Abstract

The practicality allied with technological and logistical advances led customers increasingly to join e-commerce. This phenomenon was even more expanded during the COVID-19 pandemic. Because of the growing demand for logistic services, warehouses must adapt and seek faster and more efficient processes. A means to achieve that is to use mobile robots in transportation-related tasks. However, their effectiveness is only achieved if the system has an efficient work distributor. This research developed a centralized coordination architecture using the island model genetic algorithm for multi-robot logistic task allocation. The coordination receives, allocates, and monitors tasks performed by robots with different payload capacities and average speeds. The architecture was developed upon the robotic operating system. Thus, any robot with a robotic operating system-based internal system can work under the coordination of this architecture. On the results, the task scheduler, developed in previous work, had the evaluation complemented. The scheduler based on the island model genetic algorithm allocates more tasks than the standard genetic algorithm when using the same heuristic. Regarding coordination architecture, the system successfully managed a group of robots in a simulated environment. It also detected and notified failures during task execution. Therefore, this system provides a complete task scheduling, allocation, and monitoring solution.

Keywords

Multi-robot system logistics task allocation optimization

Introduction

E-commerce is the fastest-growing retail market because of its practicality.¹ This growth has expanded even further because of the COVID-19 pandemic, as people prefer to maintain social distancing by avoiding public places and crowded areas. Consequently, the online market has become an even more attractive platform for purchasing. Additionally, the increasing use of e-commerce platforms has been boosting the growth of the logistics industry.

The logistics industry has been quickly growing, $\sim$ 40% per year, and human labor typically predominates in the sector.² In addition, the distribution of a person’s work time picking orders might include: finding the location and going to pickup locations, extracting items from the storage location, organizing order items, packing orders, and documenting the picking transactions.³ Notably, finding and traveling to a location can take up to 70% of working time.³ Therefore, warehouse efficiency is directly affected by searching and transporting products.

Parallel to the growth in the logistics sector, the field of mobile robotics has been attracting significant attention from researchers in recent years. Robots with navigation skills, known as mobile robots, can replace humans in various scenarios due to their locomotion abilities. Already developed applications of mobile robots include⁴: surveillance, planetary exploration, patrolling, reconnaissance, industrial automation, museum guides, personal services, intervention in extreme environments, and transportation.

The continuous growth of e-commerce demands logistic processes that are increasingly reliable and efficient. Mobile robots emerge as an excellent solution to enhance logistic tasks and reduce costs. They are less susceptible to failures when compared to humans and can work for uninterrupted hours, limited only by their battery levels. Additionally, using environment models, mobile robots can quickly determine the location of goods and navigate autonomously to retrieve them.

A typical multi-supplier automated warehouse has product procurement, storage, and delivery stages.⁵ In the procurement stage, once goods arrive in the warehouse, the order integrity and damages are verified. Also, if these products arrive on oversized pallets, they may be broken down into smaller amounts and then tagged with radio frequency identification. After identification, the products are stored in racks. These racks are distributed over extensive areas and must be handled efficiently. When a delivery order is received, the products are collected and bundled. Typically, a centralized coordinator determines the number of robot pickers and deadlines to procure products from the warehouse. Then, the goods can be packed, shipped, and the order fulfilled.

To perform pickup and delivery within an automated warehouse, the multi-robot system beyond the robots must have some coordination system. The system receives several orders and turns them into logistic tasks. Then, the tasks have to be allocated to robots capable of successfully performing them. The allocation process typically involves mechanisms of auction or optimization.⁶ The multi-robot task allocation (MRTA) process can be defined as allocating $T$ tasks to $R$ robots, minimizing the cost of the task executions while fulfilling constraints. Besides that, task allocation requires information about tasks, robots, and the environment. The coordination system must gather all this information to allocate tasks. After the allocation, the coordination also has to monitor the task executions, detect failures that might occur, send new tasks to robots, and coordinate recharge battery shifts.

Depending on the application requirements, the MRTA can have different characteristics regarding how tasks are performed and how robots perform tasks. Gerkey and Matarić⁷ proposed a taxonomy to classify MRTA problems as follows:

In single-task (ST) robots problems, each robot performs one task at a time. In contrast, multi-task (MT) robots can execute tasks simultaneously.

In single-robot (SR) tasks problems, each task requires exactly one robot to execute it. However, in issues with multi-robot (MR) tasks, multiple robots may need to be applied.

Instantaneous assignment (IA) means that tasks are allocated without planning for future allocations. Whereas in the time-extended assignment (TA), future allocations can be planned using information about robots, tasks, and the environment.

Several approaches can solve MRTA problems. Among them are market-based and optimization-based techniques. The traditional market-based approach is the auction, and among optimization-based approaches are genetic algorithm (GA), particle swarm optimization, and ant colony optimization.^6,8 The GA is one of the most powerful meta-heuristics because it explores three key ideas: using a population of solutions as a space search, recombining two or more solutions through crossover operators to generate new and potentially better solutions, and the population’s active diversity improvement to maintain pressure in exploration.⁹ In some cases, the vast search space requires additional concepts to enhance solution diversity and, consequently, exploration effectiveness. The island model genetic algorithm (IMGA) is an example. In this GA’s improvement, islands with their population and genetic operators (e.g. crossover, mutation, and elitism) allow migration of solutions to improve the genetic variability, leading the algorithm to solve more complex problems.

The approach proposed in this article complements the work previously started by Cechinel et al.¹⁰ and solves MRTA problems with ST robots, SR tasks, and TAs using an IMGA. The present work developed a centralized architecture to coordinate a group of robots executing logistic tasks. This architecture uses the task scheduler proposed in the previous paper, which defines the ordering of the tasks and the robot responsible for each one.

Contributions

Simple and efficient centralized coordination approach for heterogeneous mobile robots with different payloads, energy consumption, and average speed.

A coordination system that schedules and allocates tasks using the system proposed by Cechinel et al.¹⁰ which optimizes the total load transported by the team of robots and battery consumption. This is achieved while considering constraints on task deadlines, robot payload capacity, and battery level, which were previously unseen in state-of-the-art systems.

Combining the coordination architecture with the scheduler guarantees robots will satisfy battery constraints and deadlines of tasks. However, unforeseen events might occur, and the proposed coordination system can detect and notify the system’s user about failures.

Aggregating the coordination architecture to the scheduler allows the system to operate in an online manner, which would not be possible using only the scheduler proposed by Cechinel et al.¹⁰

The set of features encompassed in this work contributes to dealing with complex logistic tasks more efficiently and reliably.

Related work

Developing a MR system includes modeling robots, tasks, and the environment. Robots and the coordination system use these models to exchange information to minimize task execution costs and fulfill constraints. Following are described issues that authors consider in their approaches regarding models of robots, tasks, cost function, and environment.

In robot modeling, task allocation parameters are utilized to predict task feasibility further than control and cinematic issues. In some approaches, speed can be constant during navigation,^11,12 but others can use current and expected speed combined with position.¹³ The battery consumption must have constraints once each task must be performed by a robot with enough battery to complete it.^14,15,11 A discharge factor is normally employed based on the distance or time to estimate the battery consumption.¹¹ Also, the system could use multiple discharge factors depending on status such as waiting, navigation (without payload), and task execution.¹³ Additionally, a minimum energy threshold can be defined. Thus, when a robot finishes a task, it goes to a recharging station if its battery level reaches the threshold.¹⁵

Logistic tasks can be modeled as simple pickup and delivery^16,12 or be composed of multiple locations.¹⁵ In some scenarios, it would be interesting to have deadlines to complete tasks¹¹ or constrain the payload loading time.¹² Besides that, the time and energy required to complete a task can be estimated and measured during execution.¹³ Thus, the system self-evaluates and improves its predictions. When the multi-robot system has robots with different payload sizes, it is important to represent the minimum payload required to perform the task.¹²

When using AMRs, a MR logistic system can adopt grid maps, a widespread technique, as environment representation,^16,15,11,17 but reinforcement learning is an alternative if it is impossible to get a priori map. Thus, the robot can learn the paths on-demand while navigating the environment.¹⁷ Besides that, the system must store coordinates of locations such as product racks, packing stations, and recharge stations to compose tasks.^16,15,11,12 Some environments will have shapes more complex than others. A complexity coefficient of the environment can be applied to estimate battery consumption more precisely.¹⁵

The fitness function for GAs, or the bid for auctions, represents the cost to perform a task. The cost representation may be simple relations of distances^18,16,19 or multi-criteria considering variables such as time, distance, energy, and resources needed to accomplish a task.^14,13 Besides that, the system may aim to minimize battery consumption globally and for each robot.¹⁵ In addition, besides minimizing the cost related to task execution, the system can perform work balancing between robots.^17,20 Finally, when humans work together with robots, performing similar tasks, it is interesting that robots perform tasks with heavier payloads, leaving lighter tasks to humans.¹²

Several approaches have been proposed for MR logistic task allocation in the last few years. However, two techniques stand out as primary choices among researchers, the GA^{14,18,16,15,17} and auction.^13,19,17 Other techniques, such as constraint programming¹¹ and simulated annealing,¹² also were used for the same porpoise. It is worth highlighting a diversified set of approaches to MR task allocation. Rossi et al.²¹ presented a list of algorithms used for this purpose, such as artificial potential functions, state machines, behavior composition, and density-based control, among other centralized and decentralized optimization algorithms.

Badreldin et al.⁶ conducted a comparative analysis between marked-based and optimization-based approaches in task allocation. Considering the comparison between the auction and GA approaches, the study results revealed the GA approach exhibited superior scalability compared to the auction approach. However, the auction approach showed a higher capability in assigning tasks to robots based on their specialized skills or capabilities. In task allocation scenarios with strict deadlines, both techniques yielded similar outcomes. Lastly, when the parameters of tasks or robots were subject to stringent constraints during the optimization, where parameter values and their constraints necessitated minimal or no discrepancies, the GA approach encountered challenges in achieving a solution convergence.

Multi-robotic systems must have a coordination system allowing agents to collaborate in conducting tasks or sharing resources.²² This process allocates/schedules tasks and ensures that each robot executes them safely. Coordinating multi-robotic systems has several challenges, such as operating in dynamic and unpredictable environments, inconsistent information, unreliable and limited communication, human interaction, and system component failures.²³ The coordination system usually adopts a centralized or distributed architecture.

The centralized approach uses a single agent to coordinate the robot team. The central agent receives the tasks, requests information from the robots and the environment, and then determines how to distribute the tasks and monitor their execution. This agent can obtain optimal or close to optimal task allocation/scheduling results using all available information about agents, environment, and tasks. However, the system has a central control module, and its failure might lead to global failure. The system can be inefficient for large groups of robots because of the high demand for communication and the difficulty in detecting environmental changes. Therefore, this approach best manages small/medium groups of robots and environments where global information is easily collected.

Distributed coordination systems are fast, flexible to change, and robust to failure. However, agents only have local information about the environment and other agents. Therefore, the system might obtain suboptimal solutions that need to meet optimization requirements. Rarely do applications that use this approach deal with complex tasks or efficiency requirements. However, these approaches can select the robot most able to perform a task easily. In this approach, agents communicate with each other and, based on their local knowledge, determine which task or tasks each one will perform.

Highlights on similarities and differences

Regarding robot modeling, we adopted constant average speed during navigation. However, our method updates the robot’s average speed according to the time spent during task execution. We also considered the battery constraints, thus ensuring that each task must be performed by a robot with enough battery to complete it. Our system computes battery discharge considering the time spent on the duties. Besides that, each robot has its own battery threshold to define when recharging.

We modeled the logistic tasks as simple pickup and delivery. Although each task has its deadline, the payload loading time is defined as a robot’s constant. Our system uses parameters from the robot modeling to estimate the feasibility of the tasks, which is a common approach in the related works. Each task has its payload represented as a number of units, and a task must have at least one unit of payload.

We adopted a grid map to represent the environment for the navigation system. The map is built a priory. We also use graphs to represent it in the optimization. The graph is based on the coordinates of locations, such as product racks, packing stations, and recharge stations. However, we do not make complex distinctions between environments.

Badreldin et al.⁶ found that GA is not good with task allocation optimization subject to stringent constraints. In this scenario, the space search is often vast, and the available solutions are limited. Therefore, it is necessary to enhance the GA’s exploration ability. The IMGA does that by having several islands with independent populations and genetic operators, which allows the migration of individuals among islands. This technique improves genetic variability, thus allowing the GA to deal with more stringent constraints.

The related works have shown that approaches considered payload constraints, battery level consumption, and task completion deadlines. However, the battery consumption is not directly minimized in the cost function. Typically, speed or time are minimized, and the authors claim that energy consumption also will be minimized. However, if the logistic system has robots with discharge factors significantly different, these approaches may not be ideal. It was also noticed that constraints on task deadline, robot payload capacity, and battery level are not treated together. Combining these restrictions with measuring robots’ minimum average speed allows for allocating tasks more precisely. Cechinel et al.¹⁰ implemented a scheduler considering all these restrictions, simultaneously minimizing battery consumption and meeting task deadlines. Their scheduler also uses the IMGA, which enables efficient management of scenarios with stringent constraints. This article complements their work by proposing a centralized coordination architecture that receives, schedules, and allocates tasks using their scheduler, sends them to the robots, and monitors the execution of the tasks.

Approach

The architecture’s general operation is divided into four elements: users, database, coordinator, and robots. Following, each one of these elements will be discussed. Figure 1 shows a scheme of components that interact with each other. Each arrow means that the pointed component can receive data from the pointer one. For instance, each robot in the group of robots can read data from the database. On the other hand, the Coordinator can receive and send data to the database.

Figure 1.

Scheme of the general functioning of the proposed architecture. Robots with green symbols are free. Robots with list symbols are busy.

The system registers and follows up on information regarding the environment, robots, and tasks in the user view. For instance, the environment has locations that can be visited, robots have average speed and their position in the environment, and tasks can be a set of locations with a status and conclusion time.

The database, as usual, stores information about all architecture components. Information regarding robots and tasks is updated on demand because the coordinator uses this information to perform the task allocation process. The coordinator and database can run on different machines without losing functionality.

The coordinator searches in the database from time to time to assign or cancel tasks. If there are tasks to be assigned, the coordinator searches for available robots. A robot is available if it is properly working and not performing a task. To do so, it sends a broadcast message to all robots in the system. After that, free robots will respond with their data that can be used in the task allocation process. This information is saved in the database by the coordinator. Then, the system tries to assign the set of tasks for the group of free robots using its task allocator. The coordinator is also responsible for checking robots’ failures. It is done by sending periodic checking messages to the robots. When the coordinator detects a failure in a robot or task, the user is notified to take contingency measures.

When a MR system robot is initialized, all its robotic operating system (ROS) packages are first started. After that, it requests current values from parameters that represent it. These parameters can change between initialization because the robot can receive an upgrade. Subsequently, the robot becomes available to perform tasks. Before performing an assigned task, the robot checks if it knows all locations in the task and, if necessary, requests the database for the missing information. During task execution, the robot shares information on which part of the task was already performed and its conclusion status. Besides that, the robot also emits alerts to failures and when it goes to charge its battery. Finally, when the robot finishes its tasks, it will notify the coordinator and navigate to its parking station.

Assumptions and limitations

Before going further with the modeling and other architecture’s components, we present the following assumptions and limitations:

The system performs tasks in an indoor environment. The environment must be previously mapped. Its locations for picking up, delivering, and recharging the battery must be identified.

The robot needs only to reach a recharge station to start recharging its battery.

There is an efficient communication means between the coordinator and the robots.

The robots only communicate with the coordinator. They see each other as simply obstacles.

The coordination system only detects failures: $-$

The user defines what to do with tasks unscheduled during the scheduling process.

-

If a robot fails during a pickup step, the user must decide whether the task will be reassigned in the following scheduling process.

-

If a robot fails during a delivery step, the robot will remain stationary, and the user must physically check the robot and perform contingency actions, which include deciding whether the task will be reassigned in the following scheduling process.

The scheduler needs a multicore processor to be efficient. However, having more than 36 cores might be unnecessary because the system runs parallel with a maximum of 36 islands.

Modeling

The system’s modeling is divided into environment, robots, tasks, and restrictions. Also, it presents the entity-relationship model of the database used in the system. Below is the list of symbols used in the modeling (Tables 1 to 4).

Table 1.

List of symbols related to environment modeling.

Symbol	Description
$L$	Set of locations
$P$	Set of parking stations
$l$	An specific location
$l . i d^{l} \in N$	Identifier
$l . d s c^{l}$	Descriptions (e.g. shelf B)
$l . p \in {true, \,false}$	Is parking station
$l . x \in R$	Coordinate $x$ on robots’ global map
$l . y \in R$	Coordinate $y$ on robots’ global map
$l . θ \in R$	$θ$ angle in relation to the $x$ -axis on robots’ map representation

Table 2.

List of symbols related to robot modeling.

Symbol	Description
$R$	Set of robots
$R^{a}$	Set of robots available to receive task
$R^{b}$	Set of robots busy performing tasks
$R^{r}$	Set of robots recharging battery
$R^{m}$	Set of malfunctioning robots
$r$	An specific robot
Robot’s fixed attributes
$r . i d^{r} \in N$	Identifier
$r . d s c^{r}$	Description (e.g. R2D2)
$r . m p \in N *$	Maximum payload
$r . b d f \in R_{+}$	Battery discharge factor ( $\frac{%}{s}$ )
$r . d b t \in R_{+}$	Discharged battery threshold
$r . p m t \in N *$	Payload maximum loading/unloading time
Robot’s variable attributes
$r . s t t^{r}$	State
$r . r s \in P$	Identifier of recharging station
$r . c l \in L$	Current location
$r . r b \in R_{+} \leq 100$	Remaining battery
$r . m a s \in R_{+}$	Minimum average speed (m/s)

Table 3.

List of symbols related to task modeling.

Symbol	Description
$T$	Set of tasks
$T^{w a}$	Set of tasks waiting to be allocated
$T^{a}$	Set of allocated tasks
$T^{e}$	Set of tasks in execution
$T^{c}$	Set of successfully completed tasks
$T^{f}$	Set of tasks with failure
$t$	An specific task
Task’s fixed attributes
$t . i d^{t} \in N$	Identifier
$t . d s c^{t}$	Description (e.g. COD2810)
$t . l^{p} \in L$	Pickup location
$t . l^{d} \in L$	Delivery location
$t . d l n \in R_{+} > 0$	Deadline in seconds
$t . a l t \in N *$	Amount of load to be transported
Task’s variable attributes
$s t t^{t}$	State
$r^{r s p} \in R^{a} \cup R^{b} \cup \emptyset$	Responsible robot
$s n \in N$	Sequence number in the job execution queue from the robot $r^{r s p}$

Table 4.

List of symbols related to restriction.

Symbol	Description
$Q (r)$	Task queue for a robot $r$
$δ (t)$	Estimated time to the robot $r$ perform the task $t$
$d (a, b)$	Distance between locations $a$ and $b$
$ϵ (t)$	The energy consumption required to perform the task $t$ estimated considering the robot $r$

Environment

The modeling of the environment is composed of the coordinator’s view and the robots’ view. The coordinator’s environment is a complete graph, and the robot’s environment is a grid map. A complete graph optimizes the distance calculation between locations in the task allocation process. Thus, the task allocator consults an adjacency matrix, which represents the complete graph, to get distances used to estimate time and energy spent during task execution. Figure 2 shows an example of a complete graph representing an environment. This hypothetical environment has four locations, and the distance between these locations are the numbers over the graph edges.

Figure 2.

Example of the complete graph.

The coordinator’s view must be formalized because it is used in task allocation. The environment, or set of locations $L$ , is composed of locations $l$ . Besides that, a location $l$ can be part of $P$ , a subset from $L$ , representing robot parking stations.

l \in L

(1)

P \subseteq L

(2)

Equation (3) represents a location

l

with identification and positioning parameters.

l = (i d^{l}, d s c^{l}, p, x, y, θ)

(3)

where

$i d^{l} \in N$ : identifier;

$d s c^{l}$ : descriptions (e.g. Shelf B);

$p \in {true, \,false}$ : is parking station;

$x \in R$ : coordinate $x$ on robots’ global map;

$y \in R$ : coordinate $y$ on robots’ global map;

$θ \in R$ : $θ$ angle in relation to the $x$ axis on robots’ map representation.

Because of the simplicity and effectiveness of ROS packages for mapping, localization, path-planning, and navigation, using grid maps, they were used to represent the environment in the robots. Besides that, it is necessary to estimate distances between locations during task allocation, which is done using global path-planning algorithms for grid maps. The global path planner receives the environment’s grid map as input, which has all fixed obstacles. Then, the system uses the path found by the path planner to compute the path length between each location. A path is a list of coordinates called waypoints. The system calculates the distance between each waypoint using the Pythagorean theorem. The sum of the waypoints’ distances represents the path length. Considering that the environment’s physical characteristics (e.g. shelves and parking stations) do not change over time, this process runs only once. Therefore, the database keeps the distances between each location. If a user adds a new location to the environment, it is necessary to compute the distance from each previously saved location to this location and contrariwise.

Robot

A robot $r$ belongs to the group of robots $R$ . According to its state, a robot can be part of the following groups: available to receive tasks $R^{a}$ , busy performing tasks $R^{b}$ , recharging battery $R^{r}$ , or malfunctioning robot $R^{m}$ .

r \in R

(4)

R^{a} \subseteq R

(5)

R^{b} \subseteq R

(6)

\begin{aligned} R^{m} \subseteq R \\ R = R^{a} \cup R^{b} \cup R^{r} \cup R^{m} \end{aligned}

(7)

where\ R^{a} \cap R^{b} \cap R^{r} \cap R^{m} = \emptyset

(8)

The tuple that forms equation (9) represents the robot

r

. The attributes in this tuple were divided into fixed and variable. Fixed attributes represent robots’ characteristics that do not change. The variable attributes are modified constantly during system operation.

r = (i d^{r}, d s c^{r}, m p, b d f, d b t, p m t, s t t^{r}, r s, c l, r b, m a s)

(9)

Following, fixed and variable attributes are presented with their descriptions.

Fixed attributes: $-$

$i d^{r} \in N$ : identifier;

-

$d s c^{r}$ : description (e.g. R2D2);

-

$m p \in N *$ : maximum payload;

-

$b d f \in R_{+}$ : battery discharge factor ( $\frac{%}{s}$ );

-

$d b t \in R_{+}$ : discharged battery threshold;

-

$p m t \in N *$ : payload maximum loading/unloading time.

Variable attributes: $-$

$s t t^{r}$ : state: $*$

$A$ : available;

*

$B$ : busy;

*

$F$ : failure;

*

$R$ : recharging battery;

-

$r s \in P$ : identifier of recharging station;

-

$c l \in L$ : current location;

-

$r b \in R_{+} \leq 100$ : remaining battery;

-

$m a s \in R_{+}$ : minimum average speed (m/s).

This work claims to schedule and allocate tasks to heterogeneous robots. In the present work, heterogeneous robots are robots with different maximum payload (

m p

), battery discharge factor (

b d f

), and payload maximum loading/unloading time (

p m t

). These attributes are directly related to real robots’ size and capabilities.

Some of the presented attributes deserve additional consideration. The $m p$ does not have unity because it can be adapted to different magnitudes, for instance, an amount of $k g$ or a type of box. The attribute $r s$ is variable because the coordinator can change the robot’s parking station if this is pertinent. If the robot’s system fails, the user or coordinator can track which part of the task was performed using the $c l$ . Then, it can estimate the current location of the robot. The system maintains a finite list of locations, with $c l$ indicating the last visited location by the robot from this list. As a result, the coordination system is unaware of the robot’s real-time location. Nevertheless, users can retrieve this information from ROS’s localization system. Besides that, aiming to ensure that allocated tasks can match time restrictions by its responsible robot, the system uses the worst case of average speed during a previous task execution ( $m a s$ ) to estimate the task execution time taken by a robot.

Task

The tasks have the same representation for both the coordinator and the robots. A task $t$ is part of the set of tasks $T$ . Every task initially composes the tasks waiting to be allocated $T^{w a}$ . Then, after the allocation process, it is sent to the responsible robot and becomes part of the allocated tasks group $T^{a}$ . Following, when a robot starts to execute the task, it joins the tasks in execution $T^{e}$ . Finally, if the task is finished successfully, it becomes part of the completed tasks $T^{c}$ . If there exists a problem in the allocation, in the receipt by the robot, or in its execution, the task becomes part of the tasks with failure $T^{f}$ . The mentioned sets are formalized in equations (10) to (16).

t \in T

(10)

T^{w a} \subseteq T

(11)

T^{a} \subseteq T

(12)

T^{e} \subseteq T

(13)

T^{c} \subseteq T

(14)

\begin{aligned} T^{f} \subseteq T \\ T = T^{w a} \cup T^{a} \cup T^{e} \cup T^{c} \cup T^{f} \end{aligned}

(15)

where\ T^{w a} \cap T^{a} \cap T^{e} \cap T^{c} \cap T^{f} = \emptyset

(16)

Equation (17) models a task. As in robot modeling, a task has fixed and variable attributes. Fixed attributes represent the task itself. In contrast, variable parameters are used during coordination and execution.

t = (i d^{t}, d s c^{t}, l^{p}, l^{d}, d l n, a l t, s t t^{t}, r^{r s p}, s n)

(17)

Fixed attributes: $-$

$i d^{t} \in N$ : identifier;

-

$d s c^{t}$ : description (e.g. COD2810);

-

$l^{p} \in L$ : pickup location;

-

$l^{d} \in L$ : delivery location;

-

$d l n \in R_{+} > 0$ : deadline in seconds;

-

$a l t \in N *$ : amount of load to be transported.

Variable attributes: $-$

$s t t^{t}$ : state: $*$

$W A$ : waiting allocation;

*

$A$ : allocated;

*

$P P$ : performing pickup;

*

$P D$ : performing delivery;

*

$C$ : completed;

*

$F$ : failure;

-

$r^{r s p} \in R^{a} \cup R^{b} \cup \emptyset$ : responsible robot;

-

$s n \in N$ : sequence number in the job execution queue from the robot $r^{r s p}$ .

The attribute

d l n

can have the most proper unit of measurement to the scenario where the system is being used. In this work, it was chosen as seconds. Considering a system that works 24 hours per day, or 86,400 seconds,

0 < d l n < 86.400

. Therefore, if the deadline for a task is 11:36,

d l n

will equal 41,760.

Restrictions

Before defining the system’s constraints, it is necessary to define the task queue and the necessary time and energy to perform a task. Equation (18) formalizes the task queue for a robot $r$ . The robot $r$ will perform tasks following the tasks’ sequence number in this queue.

Q (r) = {t : t \in T, t . s t t = A, t . r^{r s p} . i d^{r} = r . i d^{r}}

(18)

Equation (19) defines the time for a robot

r

to perform the task

t

. The superscript term

δ^{i} (t)

, in the

c l

, denotes the prevision of

c l

when the robot starts the task execution. The parameter

c l

is a prevision because the scheduler considers that the robot’s location at the beginning of a task is the end of the previous one or the robot’s initial position. Also,

d (l, l)

represents the distances between locations.

δ (t) = \frac{d (t . r^{r s p} . c l^{δ^{i} (t)}, t . l^{p}) + d (t . l^{p}, t . l^{d})}{t . r^{r s p} . v m} + 2 \cdot t . r^{r s p} . p m t

(19)

The system considers that robots have a linear battery discharge rate based on time. Therefore, the energy consumption required to perform a task

t

can be estimated using equation (20).

ϵ (t) = δ (t) \cdot t . r^{r s p} . b d f

(20)

Equation (21) formalizes the deadline of a task t. The term

δ^{i} (t)

denotes the estimation in seconds of the task’s starting time. For instance, if the task starts at 6 p.m., then

δ^{i} (t) = 18 \cdot 60 \cdot 60 = 64, 800

\forall t | t \notin T^{f} : δ^{i} (t) + δ (t) \leq t . d l n

(21)

Besides meeting deadlines, all tasks allocated to a robot must be compatible with the robot’s payload capacity. Equation (22) defines the payload capacity constraint.

\forall t, r | t \in Q (r) : t . a l t \leq t . r^{r s p} . m p

(22)

The last restriction, equation (23), regards a battery level constraint. Tasks must be allocated to robots with sufficient battery levels for their execution. The superscript term

δ^{i} (t)

represents the estimation of BR at the estimated task’s starting time.

\begin{aligned} \forall t, r | t \in Q (r) : & ϵ (t) \leq r^{r s p} . r b^{δ^{i} (t)} - r^{r s p} . d b t \\ r^{r s p} . r b^{δ^{i} (t)} \geq r^{r s p} . d b t \end{aligned}

(23)

Database

The system’s database is an important part of the approach. The system can recover from unexpected coordination failures using the database. For instance, a coordination backup server can retrieve the system’s status before the failure. Then, it can continue following the execution of tasks and checking the robots’ status. Therefore, as the approach is centralized, the system is expected to have backup servers for coordination and a database in a real application.

Figure 3 shows the entity-relationship diagram of the system’s database. The database design considered the models of environment, tasks, and robots. Besides the system’s models, the database stores parameters used during task scheduling and coordination in the $s e t t i n g s$ table. The lines in the figure represent the relationship between the tables. Dashed lines mean that a table gives one of its attributes as an attribute to another. Fixed lines mean that one table gives one of its attributes to another table, and that table will use it as its key. See more information about this type of diagram in chapter three of the book.²⁴

Figure 3.

Entity-relationship model of the system’s database.

In addition to the $s e t t i n g s$ table, extra columns were added to represent tasks’ start and completion time in the $t a s k$ table. These data can be used to refine deadlines for similar tasks in the future. Also, it can be used for statistical purposes, for instance, helping to define sets of tasks performed quicker than others.

The meanings of the columns in the $s e t t i n g s$ table are explained below:

$i d_s e t u p$ : setup identifier;

$t a s k_p o o l_s i z e$ : max number of tasks in each scheduling;

$r o b o t_p o o l_s i z e$ : max number of robots in each scheduling;

$t a s k_t i m e_i n t e r v a l$ : time interval between tasks’ status verification;

$r o b o t_t i m e_i n t e r v a l$ : time interval between robots’ status verification;

$g a_t i m e_i n t e r v a l$ : time interval between scheduling;

$g a_i t e r a t i o n s$ : number of iterations in the IMGA;

$g a_s u b_i t e r a t i o n s$ : the number of sub-iterations in the IMGA. It is the maximum number of generations evaluated at each iteration by each island;

$g a_p o p u l a t i o n$ : population size on each island;

$g a_t i m e_l i m i t$ : maximum processing time to the scheduling process find a solution;

$g a_n o_c h a n g e_l i m i t$ : maximum number of iterations without improvement in the best individual. The maximum number of sub-iterations without improvement is calculated proportionally to this;

$g a_e l i t i s m$ : elitism percentage;

$g a_m u t a t i o n$ : mutation percentage;

$g a_m i g r a t i o n$ : migration percentage.

Coordination

The coordination system handles task scheduling, task allocation, task execution follow-up, and robot monitoring. The coordination system uses five components to perform its activities: task, robot and location controller, task scheduler, and general controller. Figure 4 shows the interconnections between internal and external coordination components.

Figure 4.

Components of the coordination system in blue are the coordination system’s internal components.

The general controller initializes the system and allows information exchange between controllers. When the system starts, the general controller puts the threads of controllers to run. These threads check robot status, verify tasks to schedule or cancel, and follow-up on task execution.

The task controller periodically search tasks in the database to be scheduled or canceled. The efficiency of the task scheduler is affected by the number of tasks and robots in the scheduling. Therefore, there are inferior and superior limits to the number of tasks and robots in the scheduling. Thus, the scheduler works in its best range of the number of tasks and robots. The task controller maintains a list of tasks in execution for task monitoring. Each task on the list has a countdown timer that marks the expected time for the next status update. If the system receives a delayed status update, the countdown timer for the robot’s following tasks remains the same. However, in this case, the robot probably is late in its duties. Consequently, it will have less time to complete its remaining tasks. This situation might result in a future failure of one or more of the robot’s following tasks. If the coordinator does not receive a task status update before the timer stops, the coordinator sends a message to check the responsible robot. Then, if the robot does not respond, the coordinator declares failure in the task. If the failure comes from the pickup stage, the user is notified, and the task can return to the task pool. However, if the failure comes from the delivery stage, then the user is notified and must perform all needed contingency actions. Tasks can also fail in unexpected situations, such as an obstructed path or missed deadline. In these cases, the robot sends a failure notification to the coordinator.

The robot controller monitors the status of robots in the system. At the beginning of the allocation process, this controller searches for free robots. Then, the free robots answer with a message containing data used in the allocation. Besides that, the robot controller has a list containing all the system’s robots. It also has a countdown timer that marks the expected time for the next status update. An update to a robot can be a change in a task that it is performing, a request to recharge the battery or a response to the robot verification message. If the controller does not receive an update on a robot’s status, it sends a verification to the robot. Then, if it does not receive a response, the robot’s status is changed to failure. In this case, all tasks in the robot execution queue are again inserted into the allocation waiting list. The robot’s monitoring is redundancy in failure detection. While the task controller monitors each task in execution, the robot controller monitors robots and, consequently, all tasks allocated to each robot. Therefore, if the system does not receive an update from a robot, all tasks allocated to the robot are declared as failed. It also allows the detection of failures during battery recharge since the robots need to respond to periodic update requests. If a robot does not respond to them, the system detects a failure and notifies the user.

The location controller maintains the list of locations and the distance table used during the task allocation process. Locations can be removed or added at any time. Therefore, the distance table must follow these changes. Thus, when necessary, the location controller uses the global path planner to compute distances between locations.

The task scheduler is the only one that does not interact with external components. To allocate tasks, first, it receives a list of tasks to be allocated from the task controller, a list of free robots from the robot controller, and the distance table from the location controller. Then, using this information runs the optimization process using IMGA. After the optimization, the task scheduler provides a list of scheduled tasks and, eventually, a list of non-scheduled tasks. This list defines the execution order of the tasks and also the robot responsible for each one of them. The user receives notifications about non-allocated tasks to decide when to allocate them again.

Messages

The system uses three types of messages to coordinate: communication, robot data, and task queue. A communication message has type and data fields. Some messages of communication have request and response stages. Table 5 shows the data field’s communication messages and potential values.

Table 5.

Communication messages with type code and potential values in the data field.

Description	Type	Data in request	Data in response
Robot verification	0	Empty	Robot id
Search for free robots	1	Empty	Not applicable
Recharge battery	2	Robot id	Location id
Cancel task	3	Task id	Task id
Performing pickup	4	Task id	Not applicable
Performing delivery	5	Task id	Not applicable
Task completed	6	Task id	Not applicable
Task failed	7	Task id	Not applicable

Below are described the scenarios where each of the communication message types is used:

Type 0: Used by task and robot controllers to verify if a robot is still working. When a robot receives this message, it responds with the same message containing its identifier in the data field.

Type 1: A message sent by the robot controller to find free robots. Free robots respond with a robot data message.

Type 2: A robot sends this message to the coordinator when it needs to recharge the battery. If there are specific locations to recharge batteries, the coordinator sends a response with a location identifier.

Type 3: The coordinator sends this message to the robot when a user requires to cancel a task. When the robot receives this message, it sends an echo to confirm the cancellation.

Types 4 to 7: Message sent by the robot to the coordinator in the pickup step (4) and delivery step (5), when it finishes a task (6), or when it fails to execute a task (7).

When a robot receives a message of type 1 (search for free robots), if the robot is free, the robot returns information to be used during task allocation. Table 6 shows a message with robot data.

Table 6.

Example of the robot data message.

Robot id	28
Minimum average speed (m/s)	0.43
Current location id	12
Battery level (%)	78.6
Status (label)	A

The last type of message is the task queue. It is a vector of tasks, where the sequence in which tasks appear on the vector is the sequence in which the robot must perform the tasks. The scheduling system can receive tasks with the same pickup and delivery location. Nothing prevents these tasks from appearing in the same task queue message. Table 7 exemplifies a task queue message.

Table 7.

Example of task queue message.

Task id	1	6	4
Pickup location id	18	1	5
Delivery location id	1	4	12
Deadline (s)	39.600	39.900	40.380

Internal robot system

The internal robot system allows communication with the coordinator, performing tasks, and navigation. Figure 5 shows the components of the system: navigation stack, general controller, and controllers of task, robot, and location.

Figure 5.

Interconnection diagram of the internal robot system. In blue and gray are the parts developed in this work. In white is the robotic operating system (ROS) navigation stack.

The system uses a hybrid control paradigm, where the global path planner is deliberative and the local is reactive. Also, the system’s modules are of the functional class. Therefore, the modules have well-defined functions that combined result in more complex functionalities. Besides that, the sensors can be accessed by any system’s module using the respective sensor topic. Thus, the system has reactive communication with the environment.

The robots in the system use ROS to perform navigation. Therefore, the general controller sends destination coordinates to the ROS’s navigation stack. Then, the ROS manages path planning, motion control, and obstacle avoidance, thus ensuring safe navigation between pickup and delivery locations. ROS can use several path-planning and localization algorithms to perform the navigation. In this work, it was chosen the most popular algorithms in the ROS community. Dijkstra for global path-planning, dynamic-window approach (DWA) for local path-planning, and adaptive Monte Carlo localization (AMCL).

Since the coordinator’s task scheduler does not consider robot collision avoidance or access to shared locations, the local path planner deals indirectly with part of the coordination process. For instance, when two robots need to pass through the same corridor, their local path planner will avoid a collision. Besides that, more than one robot can try to access the same location simultaneously. In this situation, the robot that is parked will continue its loading/unloading process. The robot that wants to reach the location sees the other robot as an obstacle. Since it cannot reach the location, it will wait for the path to become clean from a safe distance configured in the DWA algorithm. This situation might cause the executing task to miss its deadline.

The task controller maintains the list of tasks to be executed. Therefore, it adds or removes tasks in the robot’s task queue $T_{q} (r)$ following requests coming from the coordinator. When a robot starts to perform a task, the task is removed from the task queue and forwarded to the general controller. Then, the general controller manages the navigation and communication required to complete the task.

Managing robots’ proprioceptive information is the responsibility of the robot controller. It keeps updated information about the battery level, minimum average speed, current location, and the parking to recharge the battery. At the end of each task, is computed the average speed, and if necessary, the controller updates the minimum average speed. At the initialization of the system, the robot controller reads the robot’s minimum average speed, battery discharge factor, battery threshold, payload maximum loading/unloading time, and parking station from the database. Also, before performing a task, it verifies if the robot can perform it, considering the time and battery required. One may point out that the battery threshold may reach a level where the robot can’t perform any tasks. In this case, the robot will keep consuming the battery even if parked. Thus, eventually, it will reach the threshold required to recharge the battery. Note that the system can receive several chunks of tasks. Therefore, the system will probably receive a task that this particular robot can perform.

The system allows inserting and removing new locations at any time. Therefore, the distance table has to be updated along with these modifications. Constantly requiring this information in the database would be costly. Thus, the location controller updates its list of locations and distance table when the robot needs to navigate to an unknown location or parking station.

The communication between robots and coordination uses ROS topics. Also, the communication module is integrated into the general controller. Thus, when new messages arrive, the general controller interacts with the other controllers and answers the coordinator.

Following is a working overview of the internal robot system. First, the general controller receives a task queue through the communication module. Then it forwards the tasks to the task controller. Since the robot has tasks in its task queue, the general controller requests to the task controller the next task to be performed. Then, the general controller partitions the task into pickup and delivery. If a location is unknown, the location controller updates the list of locations and the distance table. After that, the robot controller checks if the robot can finish the task. Then, the general controller sends the coordinates of the pickup location to the ROS and informs the coordination about performing the task. When the robot arrives at the pickup location, the general controller notifies the coordinator and then informs it about performing the delivery. Finally, when the robot finishes the task, it notifies the coordination about the conclusion. In failure in one stage or the need to recharge the battery, the system notifies the coordinator that will take care of the contingency actions.

Task scheduler

This work uses the IMGA to allocate a task set to the system’s group of heterogeneous robots. In the traditional GA, the population of chromosomes goes through selection, crossover, and mutation, aiming to optimize a fitness function. Differently, the population is divided among islands in the IMGA. Each island implements a traditional GA with its own population. All populations have the same size and are generated randomly at the beginning of the optimization. Also, the islands can have different selection methods, crossover, and mutation. Thus, the system can benefit from the characteristics of different genetic operators during the search for a solution. The crossover operation can occur freely between individuals belonging to the same island. However, the crossover between individuals from different islands is prohibited. Also, periodically occurs individuals’ migration between islands to improve genetic variability. One benefit of the IMGA is the capacity to explore more than one region in the search space and improve genetic variability because of migration.²⁵ However, the migration can also impair the time performance because of its complexity.

The task scheduler used in this work was proposed by Cechinel et al.¹⁰ This method was designed to use the IMGA to allocate tasks with deadlines in MR systems. The robots can have different payload and speed capacities. Also, the system schedules tasks optimizing robots’ energy consumption and battery level usage.

Figure 6 shows the elements of the IMGA in the approach. After receiving a list of tasks and robots from the general controller, the manager forwards this information to the islands, and randomly initializes each population. Then, the iteration loop begins with each island launched as a thread.

Figure 6.

Scheme of the island model genetic algorithm used in this work.

Each island aims to allocate the tasks performing a traditional GA optimization in an iteration. The islands bound the optimization with sub-iterations (generations of the traditional GA), sub-iterations without improvement in the population, and a global maximum time limit. When all islands finish their execution in an iteration, the manager verifies if a result was found. Then, the manager returns the result to the general controller, which sends it to the robots. Otherwise, the best individuals migrate between islands, and a new iteration begins. Eventually, when the system reaches the maximum number of iterations or time limit, the system might not have found a result where all tasks were allocated. In this case, the manager returns the solution found to the general controller and informs the non-allocated tasks. The found solutions use the message type task queue (see Table 7). Typically, the system will generate one task queue for each robot given as input for the algorithm. The robots must perform the tasks in the sequence they appear in the solution.

Parameters related to the task scheduler such as elitism, mutation, migration, and others, are listed in the database as $g a_s o m e t h i n g$ . Note that elitism, mutation, and migration are given in percentage. This means that in each iteration, these processes will always occur in a percentage of each population.

For more details about chromosome representation, crossover, mutation, and migration, see Cechinel et al.¹⁰ The paper explains the details of the implementation and justifies some choices of genetic operators.

Results and discussion

This article proposes a system that uses heterogeneous robots to perform logistic tasks. The approach uses the task scheduler proposed by Cechinel et al.¹⁰ The previous work showed that nine islands performed better in allocating tasks than the others. Therefore, to complete the previous publication, the “Scheduler comparison” subsection compares the scheduler using 36 islands with a reduced version using just nine islands and the traditional genetic algorithm. After that, the “Simulation results” subsection evaluates the behavior of the proposed logistic system in a simulated environment. All experiments were conducted on a computer equipped with an i7-7700 CPU, 16 GB of RAM.

Scheduler comparison

This experiment aims to compare the scheduler’s performance. The experiment varied the number of tasks and robots participating in the allocation. A random group of tasks and robots were created for each repetition ensuring that the group of tasks could be performed by the robots. The experiment used the parameters obtained in the parameters’ definition experiments by Cechinel et al.¹⁰ The parameters used are described in the sequel:

Number of repetitions: 1000;

Number of iterations: 30;

Number of sub-iterations: 50;

Elitism: 5%;

Mutation: 25%;

Population on each island: 10 times the number of tasks;

Migration: 5%;

Stop criteria (islands): number of generations (sub-iterations), complete solution found, and 25 generations without improvement in the fitness function;

Stop criteria (manager): number of iterations, complete solution found, and time performing optimization greater than $90$ s.

We used the following performance criteria:

Percentage of complete solutions (PCSs): the percentage of repetitions that all tasks were allocated. $-$

Example: considering 1000 repetitions and 998 of them with all tasks scheduled.

-

$P C S = 100 \cdot \frac{998}{1000} = 99.8 %$ .

Average rate of tasks allocated (ARTA): the average rate of tasks allocated considering all repetitions. $-$

Example: Considering two repetitions and ten tasks. In repetition one, nine tasks were scheduled. In repetition two, eight tasks were scheduled.

-

$A R T A = 100 * \frac{(9 / 10) + (8 / 10)}{2} = 85 % .$

Average time to allocate tasks (ATATs): the average time to perform the optimization process.

Figure 7 compares the percentage of complete solutions found by the three versions of the scheduler. The scheduler using 36 islands stood out as the best option. It found more complete solutions than nine islands and the traditional GA version. Therefore, the participation of all islands, which improves genetic variability, positively affects the capacity to find solutions.

Figure 7.

Percentage of complete solutions.

Based on Figure 8, it can be seen that all three versions have an elevated average percentage of allocated tasks. However, in practical applications, when a task scheduling fails, the task goes through one or more scheduling attempts. Also, the lower the percentage of complete solutions found, the greater the feedback of tasks to the queue of tasks waiting for allocation. Thus, even using only nine islands, the IMGA has better results than the traditional GA.

Figure 8.

Average percentage of allocated tasks.

The last analyzed aspect, shown in Figure 9, was the average time to find a complete solution. Although the version with 36 islands finds more complete solutions and allocates more tasks on average, it also demands significantly more time. As the computer used in the experiment has only four cores, the islands could not be executed completely in parallel. However, even with this limitation, the approach using only nine islands finds solutions in less time than the traditional GA.

Figure 9.

Average time to allocate tasks.

Increasing the number of cores, the IMGA with 36 islands could achieve time results similar to the one with nine islands. The experiment was conducted using a computer with four cores. Considering that all islands have the same running time and the system is not preemptive. Although this is not completely true because the system is preemptive, and the islands have slight variations in the running time, it is a fair approximation to make the following analysis. When using nine islands, the system behavior is to run four islands two times and then the remaining island. Therefore, the running time is equivalent to having three islands running in a single-core processor. When using 36 islands, the system behavior is to run four islands nine times. Therefore, it is like having nine islands running in a single-core system. Thus, if the system with 36 islands runs in 12 cores, it would be equivalent to three islands in a single core, which would probably make the running time similar to nine islands in a four-core system. In conclusion, with 12 cores, the IMGA with 36 islands could provide better solutions with running time similar to the nine islands IMGA running in a four-core machine.

Simulation results

This section explores the experiments in a simulated environment. Figure 10 shows the environment created in the gazebo simulator to evaluate the system. This environment has $\sim$ 1500 m $^{2}$ , eight parking stations, five delivery locations, and 192 pickup locations. Figure 11 illustrates the grid map of the environment. The locations used in the experiments are signed with colorized rectangles on this map. A video showing one of the experiment’s repetitions in this environment is available at https://youtu.be/cwRdfiKpCDM.

Figure 10.

Simulation in the Gazebo simulator. In green, the parking lots. In orange are the delivery locations. In yellow are the shelves that represent pickup locations.

Figure 11.

Grid map with locations marking. In red, the robot’s identifier is parked at that location. In green are the pickup locations. In blue are the delivery locations.

Table 8 shows parameters from the five robots used in the experiment. There are two robots with low payload capacity, two with medium, and one with high capacity. Analogously, there are two robots with low battery consumption, two with medium, and one with high battery consumption. Besides that, all robots have the same initial minimum average speed. To simplify the simulation, the robots simulate the pickup and delivery waiting for $p m t$ seconds in front of the locations.

Table 8.

Initial robots’ data used in the simulations.

id	mp	rb	bdf	dbt	mas	pmt	rs	cl
0	2	27	0.02	10	0.25	2	0	0
1	2	21	0.02	10	0.25	2	4	4
2	5	43	0.05	10	0.25	5	2	2
3	5	76	0.05	10	0.25	5	6	6
4	10	63	0.1	10	0.25	10	3	3

Table 9 lists the tasks executed in the experiment. These tasks were created for the robot $0$ being responsible for performing tasks with id $0$ to $3$ . Robot $1$ to handle tasks with id $4$ to $6$ . Robot $2$ to handle tasks with id $7$ to $9$ . Robot $3$ to handle tasks with id $10$ to $12$ , and robot $4$ to handle tasks with id $13$ to $14$ . Although it was a sequence design, the tasks were allocated as defined by the scheduler. Also, the column $d l n$ , which represents the deadline, considers the system’s starting time as $0$ .

Table 9.

List of tasks to be allocated in the simulations.

id	alt	dln	$l^{p}$	$l^{d}$
0	2	344	80	8
1	2	589	114	8
2	2	752	144	8
3	2	829	178	8
4	2	356	71	12
5	2	433	200	12
6	2	513	202	12
7	5	355	84	9
8	5	547	149	9
9	5	656	181	9
10	5	247	163	11
11	5	789	35	11
12	5	1307	38	11
13	10	254	189	10
14	10	521	128	10

The experiment was repeated 10 times with the same groups of tasks and robots. The system returned to its initial condition, except for the minimum average speed, at each repetition. The experiment aimed to validate the system’s operation. Therefore, the system should allocate all tasks to the expected robots and coordinate the task execution while detecting failures.

All tasks were allocated in each repetition of the experiment. However, on the second and fifth repetitions, one task failed in execution, tasks 1 and 9, respectively. Both failures occurred because a delivery robot blocked the robot from trying to arrive at a pickup location. Consequently, the task being performed missed its deadline. This kind of failure happens because the robots see each other as obstacles that block the way. Figure 12 shows the effect of the failure in the second and fifth repetitions. There is an increase in total time to complete the tasks because the robot tried to perform the task for a while before informing the coordinator about the failure.

Figure 12.

Time spent to perform all tasks.

Figure 13 shows the evolution of the minimum average speed in the repetitions. The minimum average speed is a parameter that must have its initial value cautiously defined. The robots can update the value each time they complete a task. If the new value is much smaller than the initial and other robots have values significantly bigger, the robot can be under-used in the next allocations. This situation may occur because, from the task scheduler’s perspective, this robot takes longer to complete tasks when compared to other robots, impacting its ability to meet deadlines. In the 10th iteration of the experiment, robot $4$ was assigned a task originally intended for robot $0$ . One possible explanation for this behavior from the scheduler could be the influence of the minimum average speed.

Figure 13.

Variation of minimum average speed by the robot.

Figure 14 shows the sum of the battery levels consumed to complete all tasks. Because of this, the values are above 100%. The fifth, sixth, and 10th executions had the biggest battery consumption. This result is justified in Figures 15 and 16, which shows the robots’ tasks list, their execution sequence, and the battery spent performing each one. Figure 16 can be compared with Figure 15, which graphically illustrates the design scenario. This figure can be compared with Figure 15, which shows the design scenario graphically. Robots $2$ and $3$ have a medium energy consumption rate, and robot $4$ has the highest consumption rate in the system. Therefore, it is expected that when these robots perform more tasks than expected, the battery consumption increases when compared to the design scenario in Figure 15. For instance, in the sixth repetition, although robot $4$ performs one extra task and robot $3$ one less, the energy consumption increases because robot $4$ has a bigger discharge factor. In the tenth repetition, this effect repeats; the robot $4$ performs a task that should be performed by the robot $0$ , and the energy consumption increases.

Figure 14.

Total amount of battery spent.

Figure 15.

Design scenario for robots’ tasks list, their execution sequence, and the battery spent performing each one.

Figure 16.

Robots’ tasks list, their execution sequence, and the battery spent performing each one. Tasks shaded in red failed to be executed.

Conclusion

Mobile robotics has been an ascending research area. This area has several research fields: modeling and control, autonomous navigation, mapping, human–machine interaction, MR cooperation, intelligent decision-making systems, and task allocation/scheduling. Mobile robots can perform repetitive tasks that are sometimes unhealthy, which helps prevent human injuries. Logistic tasks are repetitive and have high aggregated value. Thus, industries have already been using this technology. However, developing a complete logistic system is complex and can involve all fields mentioned above.

This work aimed to contribute to MR task allocation and coordination for logistic systems. An IMGA was used for task scheduling in this research. The scheduler was proposed in previous work and incorporated into the coordination architecture proposed in this article. The system’s centralized coordination allows for allocating and monitoring tasks and detecting failures during task execution.

The proposed approach was evaluated regarding the scheduler and the coordination. First, the evaluation of the task scheduler by Cechinel et al.¹⁰ was complemented. The article compared the scheduler with the traditional GA and a version using only nine islands. The scheduler using 36 islands had better results in both cases, except for the time performance. However, analyzing the results, it is possible to conclude that using a computer with a larger number of cores, the complete version probably would have the best result in all aspects.

Due to computational limitations, the system was simulated using five robots and fifteen tasks. In this scenario, the coordinator could allocate and monitor tasks and detect failures in their execution. During the experiments, two task failures failed, both related to the robots’ internal system. The robots could not arrive at the pickup location, resulting in a task failure. Once the robots see each other as obstacles, the navigation system has to generate a failure of navigation when it cannot arrive at a location. Despite these two flaws during task execution, the robots successfully performed the rest of the tasks.

Some limitations were discovered during the experiments. Therefore, we propose the following future work:

Module for robots detection and communication: Two tasks failed because the robots’ internal system detected other robots in the environment as obstacles. Therefore, a communication module between robots could be developed so that they can decide whether to wait for the other robot to leave the location or if the location is obstructed by an obstacle, causing the task to fail.

Coordination decentralization: As the task allocation/scheduling system executes 36 islands in parallel, these islands could be executed on idle robots within the system. This could reduce computation time since each island would be the responsibility of a different computer, decreasing the competition for resources during optimization execution. Additionally, with a decentralized coordination system, the database could become a hybrid, partially integrated into the robots’ internal systems. This would allow statistical information about the robot and its tasks to be stored in a local database. Task monitoring could also be performed by idle robots instead of a centralized agent.

Failure recovery: The system is capable of detecting failures in the execution of tasks and robots, but it is not able to recover from them, which is currently the responsibility of the system’s user. In this context, a failure recovery module can be developed to automatically reallocate failed tasks.

Flow and latency evaluation: The system managed a medium-scale group of robots. However, it was not evaluated how much it demands from the network in which it is inserted. It would be interesting to define the maximum number of robots and tasks that can be managed simultaneously. These questions can be answered through network throughput and latency evaluation, combined with a benchmark evaluation of the capacity to detect task failures in situations with a large number of robots.

Additional information

The source code and experiment data of this work are available in the GitHub repository: https://github.com/alankc/IMGA-System

Footnotes

Acknowledgements

The authors are grateful for the financial support granted by CNPq to this research at the Program of Post-Graduation in Automation and Systems Engineering of the Federal University of Santa Catarina. This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior—Brasil (CAPES)—Finance Code 001.

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.

Funding

The authors disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: The authors are grateful for the financial support granted by CNPq to this research at the Program of Post-Graduation in Automation and Systems Engineering of the Federal University of Santa Catarina. This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001.

ORCID iD

Alan Kunz Cechinel

References

Taher

. E-commerce: advantages and limitations. Int J Acad Res Account Financ Manag Sci 2021; 11: 153–165. DOI: 10.6007/ijarafms/v11-i1/8987.

Yan

. Automated guided vehicle: the direction of intelligent logistics. In: 2018 IEEE international conference on service operations and logistics, and informatics (SOLI) pp. 250–255.

Edward Frazelle

. Supply chain strategy: the logistics of supply chain management. New York: McGraw-Hill Education, 2002. ISBN 9780071375993.

Rubio

Valero

Llopis-Albert

. A review of mobile robots: concepts, methods, theoretical framework, and applications. Int J Adv Robot Syst 2019; 16: 1–22. DOI: 10.1177/1729881419839596.

Kattepur

. Workflow composition and analysis in industry 4.0 warehouse automation. IET Collab Intell Manuf 2019; 1: 78–89.

Badreldin

Hussein

Khamis

. A comparative study between optimization and market-based approaches to multi-robot task allocation. Adv Artif Intell 2013; 2013: 1–11. DOI: 10.1155/2013/256524.

Gerkey

Matarić

. A formal analysis and taxonomy of task allocation in multi-robot systems. Int J Rob Res 2004; 23: 939–954.

Seenu

Kuppan Chetty

Ramya

et al. Review on state-of-the-art dynamic task allocation strategies for multiple-robot systems. Ind Rob: Int J Rob Res App 2020; 47: 929–942.

Whitley

. Next generation genetic algorithms: a user’s guide and tutorial. In: International series in operations research & management science. Springer International Publishing, 2019, pp.245–274. DOI: 10.1007/978-3-319-91086-4_8.

10.

Cechinel

De Pieri

Fernandes Perez

et al. Multi-robot task allocation using island model genetic algorithm. IFAC-PapersOnLine 2021; 54: 558–563. 17th IFAC Symposium on Information Control Problems in Manufacturing INCOM 2021.

11.

Booth

KEC

Mohamed

Rajaratnam

et al. Robots in retirement homes: person search and task planning for a group of residents by a team of assistive robots. IEEE Intell Syst 2017; 32: 14–21.

12.

Liu

Wang

Chen

et al. An incidental delivery based method for resolving multirobot pairwised transportation problems. IEEE Trans Intell Transp Syst 2016; 17: 1852–1866.

13.

Panfil

Moczulski

. Control system of the inspection robots group applying auctions and multi-criteria analysis for task allocation. In: Bouma H, Carlysle-Davies F, Stokes RJ et al. (eds) Counterterrorism, crime fighting, forensics, and surveillance technologies. vol. 10441. International Society for Optics and Photonics, SPIE, pp.185–208. DOI: 10.1117/12.2278247.

14.

Martin

Frejo

JRD

García

et al. Multi-robot task allocation problem with multiple nonlinear criteria using branch and bound and genetic algorithms. Intell Ser Rob 2021; 14: 707–727.

15.

Wang

Zhang

. A novel scheduling method for automated guided vehicles in workshop environments. Int J Adv Rob Syst 2019; 16: 1729881419844152.

16.

Harun

Ibrahim

. A genetic algorithm based task scheduling system for logistics service robots. Bull Electr Eng Inform 2019; 8: 206–213. DOI: 10.11591/eei.v8i1.1437.

17.

Dou

Chen

Yang

. Genetic scheduling and reinforcement learning in multirobot systems for intelligent warehouses. Math Probl Eng 2015; 2015: 1–10. DOI: 10.1155/2015/597956.

18.

Soleimanpour-Moghadam

Nezamabadi-Pour

. Discrete genetic algorithm for solving task allocation of multi-robot systems. In: 2020 4th Conference on swarm intelligence and evolutionary computation (CSIEC) pp.006–009. DOI: 10.1109/CSIEC49655.2020.9237316.

19.

Öztürk

Kuzucuoğlu

. A multi-robot coordination approach for autonomous runway foreign object Debris (FOD) clearance. Rob Auton Syst 2016; 75: 244–259.

20.

Zhou

Shi

Wang

et al. A balanced heuristic mechanism for multirobot task allocation of intelligent warehouses. Math Probl Eng 2014; 2014: 1–10. DOI: 10.1155/2014/380480.

21.

Rossi

Bandyopadhyay

Wolf

et al. Review of multi-agent algorithms for collective behavior: a structural taxonomy. IFAC-PapersOnLine 2018; 51: 112–117. IFAC Workshop on Networked & Autonomous Air & Space Systems NAASS 2018.

22.

Koubaa

Bennaceur

Chaari

et al. Chapter general background on multi-robot task allocation. In: Robot path planning and cooperation: foundations, algorithms and experimentations. Cham: Springer International Publishing, 2018, pp.129–144. ISBN 978-3-319-77042-0, DOI: 10.1007/978-3-319-77042-0_6.

23.

Dias

Zlot

Kalra

et al. Market-based multirobot coordination: a survey and analysis. Proc IEEE 2006; 94: 1257–1270.

24.

McLaughlin

. MySQL workbench: data modeling & development. New York, Chicago, San Francisco, Lisbon, London, Madrid, Mexico City, Milan, New Delhi, San Juan, Seoul, Singapore, Sydney, and Toronto: McGraw-Hill Education, 2013.

25.

Whitley

Rana

Heckendorn

. The island model genetic algorithm: on separability, population size and convergence. J Comput Inf Technol 1999; 7: 33–47.

Centralized multi-robot logistic system: An approach using the island model genetic algorithm as task scheduler

Abstract

Keywords

Introduction

Contributions

Related work

Highlights on similarities and differences

Approach

Assumptions and limitations

Modeling

Environment

Robot

Task

Restrictions

Database

Coordination

Messages

Internal robot system

Task scheduler

Results and discussion

Scheduler comparison

Simulation results

Conclusion

Additional information

Footnotes

Acknowledgements

Declaration of conflicting interests

Funding

ORCID iD

References