Sage Journals: Discover world-class research

Abstract

The use of mobile manipulators for transportation tasks has provided solutions to several flexibility problems in manufacturing systems. Mobile manipulators are mobile entities equipped with robotic arm for loading and unloading of parts and an Automated Guided Vehicle (AGV) for their transport. In order to increase further the flexibility of these systems, the mobile manipulators could be modular, where their two entities are able to work together or separately. The assignment of transportation operations to different smart entities working together is a complex problem, which has not been addressed sufficiently in the literature. This paper proposes a two-stage decision approach for transportation task assignment, which is based on auction mechanism and a coalition formation process modeled with integer linear programming. A real use case has been implemented to test the efficiency of the proposed method. The proposed approach gives promising results that are discussed.

Keywords

Task assignment modular mobile manipulators transportation tasks coalition formation integer linear programming auction

Introduction

The paradigm of mass production in factories was initiated by Henry Ford at the beginning of the 20th century on an assembly line. These lines have good yields, when it comes to producing the same part and when market demand for that semi-finished or finished-product is high.¹ The current market trends need more variable and customized product, which cannot be ensured by these traditional production lines. The integration of Flexible Manufacturing Systems (FMS) is a solution to cope with these changes.^2,3 The conveyor systems used for transportation tasks are no longer suitable for FMS, especially with the requirements of routing flexibility.⁴ Thus, in the Handling Material System (HMS), mobile manipulators are used to ensure transportation tasks to be able to execute a full transportation task composed at least by three elementary operations (loading products on mobile robot, transporting the product to destination and unloading product from the mobile robot).⁵ In order to increase the flexibility of such devices, the European project CoRoT proposes to develop a modular mobile manipulator composed of two intelligent elements (a robotic arm and a robotic mobile base) able to be separated and gathered in a short time. Several studies have focused on different problems related to the implementation of mobile manipulators in manufacturing systems,^6,7 optimize the robots fleet size using a multi-agent based simulator,⁸ seek to find the optimal size of robots and propose a multi-load strategy to increase the effectiveness of robots. The path planning is an important problem studied by several research work for single or multi robots systems. The selected path in complex systems affects directly the duration of the transportation,^4,5,8 is interested by the energy management of mobile robots and the optimisation of the charge station placement, knowing that the idle state can be considerable for this kind of device. Other researches focus on the assignment of tasks to manipulators.^9,10 All these works are considering the transportation task as global task without looking to the different operations composing it and the associated resources needed to execute them (AVG, arm, gripper and/or operator).

At the best of our knowledge, no research work has examined the execution of the transportation task using modular robotic systems or the fact that the task is executed by the coalition of several autonomous entities. In fact, the literature considers mobile manipulators with a simplified role (moving a product from point A to point B) by neglecting the arm role (Loading and unloading operations). This paper assumes that the transportation task is executed by a set of resources (AGVs, robotic arms and human operators) and seeks to optimize robot teams composition. It proposes a distributed decision process allowing to use effectively the smartness of mobile manipulators entities through the robots coalition formation.

The remainder of this paper is organised as follows. The second section gives an overview of the literature and reports the most relevant works in the fields of mobile manipulators, robots coalition approach and robotic tasks assignment. Then, Section 3 describes the proposed distributed decision approach and details the global and local decision models. A use case and its experimental results are presented in Section 4 to illustrate the effectiveness of the proposed approach. The last section gives the main conclusions and perspectives of this work.

Related works

Mobile manipulators

Mobile robots are autonomous entities able to move in a given space to displace products, tools or measurement devices from a source point A to a destination point B. Usually, they are connected and have several perception sensors used for localisation, safety and obstacle avoidance.¹¹ They are used in several fields such as manufacturing systems,^12,13 military operations,¹⁴ medical care systems, space exploration,¹⁵ etc. In the industrial field, these robots are called AGVs (Automatic Guided Vehicles). By equipping it with a robotic arm for loading and unloading operations, an AGV becomes a mobile manipulator.^5,11 The modularity criterion of mobile manipulators means that they can be divided into two categories (I and II).

Category I Mobile manipulators

In this case, the mobile base is linked physically to the robotic arm and the two entities are considered as a single entity.¹¹ Communication is done through a single controller that has several actuators (motors of the mobile robots and robotic arm). This configuration is quite widespread, especially when centralized supervision is adopted. This kind of architecture is efficient but limits the flexibility of the system because the two entities can work only together, that is, if one of them is implicated in a task, the other one is also implicated since they are physically dependent. Other distributed architectures are developed in order to overcome this problem, where the robots are considered as two distinct entities.¹⁶ In this case, the communication with the supervision system can be made separately or together through a specific controller dedicated to the synchronisation of the two robots. This architecture reduces the complexity and the amount of communication data of the supervision system.

Category II Mobile manipulators

In this case, the mobile base is physically separated from the arm and the two entities (mobile base and arm) are considered as two different autonomous entities, each of which has its own decision-making unit.¹⁷ This configuration is beneficial when the mobile base does not need the services of the arm, as in cases where loading/unloading operations are carried out by a human operator or another arm more efficient. The category II is necessary also when the arm needs the service of the mobile base to be transported in a given location where the arm has to perform a handling operation (pick and place).¹⁸ The communication with the supervision system is similar to the case where the robots are linked, but they are still considered as independent entities. The unique difference in this case is that the coalition can include more than two robots.

Robots coalition

A robotic coalition can be defined as a group of robots, combining their capacities in order to execute a task that each of them cannot execute lonely.¹⁹ Many research works have focused on robots coalition formation which is known as NP-Hard problem.²⁰ In Rauniyar and Muhuri,²¹ a multi-robot coalition problem is addressed and a centralized approach, based on genetic algorithm, is used to solve it. A central robot, which has knowledge about the other robots, leads the coordination between robots to perform tasks. However, the model remains generic since it does not specify the nature and the complexity of tasks. In Wu et al.,²² a hybrid approach for multi-robots coalition is used for delicate tasks (rescue missions or dangerous environment). The method aims to maximize the number of tasks completed by the coalition while minimizing the energy consumed. Another multi-robots coalition algorithm in the same application field (rescue missions) is shown in Mouradian et al.²³ Several constraints such as battery level, task capability requirements and location constraints are taken into account in the coalition formation. For example, based on the possible duration of a task, a minimum battery level can be required to integrate the group (or coalition). The number of robots that can be part of a given coalition is also limited. This limitation could be a disadvantage for other areas such as in industry, which may include tasks requiring the intervention of several resources in the same time. Thus, this constraint restricts the use of the approach in other application fields.

Robotic tasks assignment

Robotic tasks scheduling defines the responses to the questions “when,”“where” and “how” a robot must perform each task, including its routing.⁸ A high-level entity is generally in charge of the scheduling decisions in order to achieve and ensure the overall objective(s).²⁴ However, with the advent of autonomous entities able to execute high-level orders, the “how” question is treated locally at the bottom level (shop floor), in order to gain in flexibility and reactivity.²⁵ Two types of scheduling are used: (i) Offline scheduling, when all transportation tasks and parameters are known in advance; and (ii) Online/Dynamic scheduling, when transportation tasks to schedule come separately and the scheduling is dynamically adapted over time.^26,27 Several works were interested in tasks assignment of smart transport entities in an industrial environment. Nevertheless, most of that works limit transport entities to AGVs.^9,15 As a result, only the transportation operation is taking into account, the operations of loading and unloading are neglected. Rey et al.²⁸ categorized the assignment approaches into six groups which are summarized with their characteristics in Table 1.^29,30

Table 1.

Assignment approaches categories.

Approaches	Functions	Type	Concerned resources
Blackboard	Share information, job scheduling	Centralized	Machines, Transporters, Products
ContractNet	Auction, negociation	Distributed	Machines, Transporters
Dispatching and priority rules	Job scheduling	Centralized	Machines, Products
Potential Fields	Attraction and repulsion principle	Distributed	Machines, Transporters, Products
Pull algorithms(Kanban)	Production management, just in time	Centralized	Machines, Products
Stigmery mechanisms	Indirect communication, self-organization	Distributed	Machines, Transporters

The six approach categories are implemented using either Multi-Agent System (MAS),³¹ Holonic Manufacturing System (HMS)³² or Product Driven (PD).³³ Each approach is characterized by its Functions, its Type and its list of Concerned resources, which define the interaction between the resources.

Among the assignment approaches presented in Table 1, ContractNet and Potentials Fields are the most commonly used because they are more suitable to mobile manipulators tasks assignment. In fact, these approaches offer a possibility of direct communication between agents, a distributivity to take into account their intelligence and include transport resources (transporters) in their field. Hence, these two approaches are explained in more details hereafter.

Potential fields

Potential Fields approach consists in the emission of a field into an environment in order to attract elements of common interest (Attraction) or to repel in order to avoid each other (Repulsion).³⁴ In Weyns et al.,³⁵ an approach for assigning tasks to AGVs in a dynamic environment based on Potential Fields is proposed. Fields are emitted by transport agents and then idle AGVs are attracted by these fields. AGVs in turn emit repellent fields to avoid collisions when several AGVs are attracted by the same field. A priority index ranging from 1 to 10 is defined for each transportation task to better guide AGVs in selecting a task, when several fields are transmitted at the same time. In Zbib et al.,³⁶ another approach based on Potential Fields, in which each resource can offer one or more services, is proposed. Each service having its own potential field, the same resource can emit several potential fields corresponding to the services it is offering. The products are then attracted by the field corresponding to the service they need. Therefore, approaches based on potential fields make it possible to solve scheduling and routing problems simultaneously.³⁷ However, the field flow is proportional to the distance where the emitting source is located. That is why, these methods reach their limits in large warehouses or factories, especially if there are obstacles like walls, for example. In other terms, the use of these approaches in an efficient way requires a particular configuration of the environment (open and relatively small space).

ContractNet

Methods based on ContractNet approach are known to be effective in solving allocation problems.³⁷ In this type of approach, a manager agent announces a proposal for a job, contracts agents, evaluates their offers and then bids.³⁸ Then, the manager agent assigns the task and coordinates with the winner to perform the task. Three situations can arise in FMS:

(a) Contractors and managers are all resources trying to distribute the workload.³⁴

(b) Managers are parts offering tasks and contractors are bidding resources to get these jobs.³⁹

In Hernandez-Martinez et al.,⁴ an auction-based assignment method is presented, where AGVs bid to obtain the transport of a given product. The allocation is made based on the characteristics of each AGV in terms of location, capabilities and execution time. Other decision criteria can be defined for the choice of the AGV, such as power consumption, accuracy, and some characteristics related to the nature of the products. In this approach, tasks are allocated sequentially,³⁶ which needs a scheduling of tasks before the allocation process. The use of combinatorial bidding in Fauadi et al.⁹ allows to overcome this type of problem. Thus, a mobile entity can submit, at the same time, several bids to production tools, in order to win the tasks of transporting products they offer.

Distributed decision

An industrial transportation task can be defined as a set of three primary operations: Loading an object at source point A, moving this object to a destination point B and unloading this object. The assignment of transportation tasks to mobile manipulators can be done in several different ways. In the most common way, only the operation of moving the object is considered, whereas loading and unloading operations are not taken into account.^35,41 This can lead to inaccuracy in delivery time calculations. In this first one, the task allocation consists in finding an AGV able to perform the task according to various parameters, such as cost, time, distance, etc. Another approach, more complete but rarely used due to its complexity, takes into account all three operations for a better estimation of delivery times and associated costs.¹⁸ The assignment will then consist in determining the entity or the collection of entities able to perform the three operations. Three possibilities can be presented.

First, the supervisor finds, directly at its level, the best (optimal) coalition for the execution of a given task. This approach is totally centralized, which leads to a fast response of the system, a centralization of data, and a high control on bottom entities.²⁴ However, the flexibility of the system is highly reduced and the smartness of entities is underused.^42,43

The second possibility reduces supervisor’s workload by taking advantage of the autonomy of mobile manipulators.^25,44 In Pach,⁴⁵ this decentralized approach is experimented. The high-level entity defines the production plan through an Integer Linear Programming (ILP), and the bottom-level entities are in charge of assigning tasks to to resources based on Potential Fields approach. In this paper, our approach is based on a similar concept for the assignment of transportation tasks to a set of resources. As shown in Figure 1, the supervisor submits a task to all AGVs and each of them find and submit to the supervisor the coalition that best fits the task. Then, the supervisor chooses the best coalition received from the AGVs. The supervisor’s decision is global and is based on an auction process, while each AGV’s decision is local and is based based on an ILP. This two-stage mechanism makes the approach distributive since the decision is shared between the different entities of the workshop (supervisor and other low-level resources, AGVs).

Figure 1.

Transportation tasks assignment process.

Notations

Sets and indices

$V$ Set of AGVs able to initiate a coalition and make an offer for the transportation task proposed by the supervisor

$A$ Set of arms

$H$ Set of operators

$R^{v}$ Set of resources able to form a coalition with v, $R^{v} = {v} \cup A \cup H$

$K$ Set of tasks

$I^{k}$ Set of operations of task $k \in K$

v index of AGVs, each AGV is in charge of the local decision (coalition formation)

k Index of tasks, each task is composed of a set of operations

$l_{k}$ Number of operations in task k, that is, $l_{k} = | I^{k} |$

i Index of operations, $i \in \cup_{k} I^{k}$

r Index of resources, $r \in R^{v}$

$σ$ Index of stocks, that is, locations of input/output buffers of machines and where raw materials and finished products are stored

Parameters

$p_{r}$ Current position of resource r

$d_{σ, σ'}$ Distance between positions of stocks $σ$ and $σ'$

$s_{r}$ travel speed of mobile resource r

$e_{k}$ The end time of task k

$b_{r}$ The availability time of resource r (end time of the last operation in its buffer)

$t l_{r}$ Time required by the resource r to load or unload a product, with $r \in A \cup H$

$t t_{r, σ, σ'}$ The time required by the resource r to move from stock $σ$ to stock $σ'$ , with $t t_{r, σ, σ'} = \frac{d_{σ, σ'}}{s_{r}}$

$σ_{i, k}^{s}$ Index of the source stock of operation i of task k

$σ_{i, k}^{d}$ Index of the destination stock of operation i of task k

$τ_{r, i, k}$ = $t l_{r}$ if operation i of task k is a loading or unloading operation; $t t_{r, σ_{i, k}^{s}, σ_{i, k}^{d}}$ otherwise (transportation operation)

${td}_{k}^{v}$ Duration of task k within coalition v

$γ_{r}$ = 1 if the resource r is mobile; 0 otherwise

$ψ_{r, i, k}$ = 1 if the resource r is able to perform operation i of task k; 0 otherwise

$λ_{r, σ}$ = 1 if the resource r is located at $σ$ ; 0 otherwise

$δ_{r, i, k}$ Duration of operation i of task k by resource r

= $τ_{r, i, k}$ if $λ_{r, σ_{i, k}^{s}} = 1$ ; $γ_{r} . (τ_{r, i, k} + t t_{r, p_{r}, σ_{i, k}^{s}})$ otherwise

Decision variables

$Y_{r, i, k}$ = 1 if resource r is in charge of operation i of task k; 0 otherwise

$S_{k}^{v}$ Starting time of task k by the coalition formed by the AGV v

$W_{k}$ Winner of task k chosen by the supervisor in global decision model, $W_{k} \in V$

Global decision

The goal of the global decision is to ensure that the optimal coalition of robots is selected for each submitted transportation task. The global decision model is based on an auction process in which the supervisor, representing the high-level entity, submits a transportation task and receives bids from AGVs. As shown in Figure 2, the global decision entity selects and sends a task to AGVs in charge of coalition. The latters respond by proposing the coalition minimizing the task completion time through a local decision model based on an ILP. The selection of one winner by the global decision is done as formulated in equation (1). The winner is the AGV in charge of the coalition minimizing the delivery time of the task, which corresponds to the sum of the task duration ( ${td}_{k}^{v}$ ) and the starting time of the task ( $S_{k}^{v}$ ) within that coalition. A transportation task of a given product can actually start only when both resources in charge of loading and transporting operations are available.

W_{k} = \arg min_{v \in V} (S_{k}^{v} + {td}_{k}^{v}) \forall k \in K

(1)

Figure 2.

Auction process.

with $S_{k}^{v} = \max (\max_{r \in ℛ} Y_{r, 1, k} b_{r}; e_{k - 1})$

Once a winner is selected, the supervisor sends the information to the members of the winning coalition in order to update their buffers for the next tasks.

Local decision model formulation

The ILP-based local decision model is implemented on each AGV. It aims to find the best coalition of resources, while minimizing the completion time of the whole transportation task. A coalition is necessarily formed by: (i) one AGV in charge of carrying the product and leading the coalition; and (ii) one or two resources (for pick and place) in charge of product’s loading and unloading operations. The pick and place resources can be:

(i) One robotic arm joined to an AGV able to carry out both the loading and the unloading operations; or

(ii) Two different robotic arms (Each of them is either joined to another AGV or separated); or

(iii) One human operator able to carry out both the loading and the unloading operations; or

(iv) Two human operators (one for the loading operation and another for the unloading operation).

The number of possible coalitions for each AGV can be calculated using the expression below:

| C^{v} | = A_{| A |}^{1} + A_{| H |}^{1} + A_{| A |}^{2} + 2 \times A_{| A |}^{1} \times A_{| H |}^{1} + A_{| H |}^{2}

(2)

where |.| is the cardinality operator, $C^{v} = A^{2} \cup A \times H \cup H^{2}$ is the set of all possible coalitions for AGV v, $A_{n}^{k} = \frac{n!}{(n - k)!}$ is the number of ordered subsets (or arrangements) of k elements from a set of n elements, and $A$ and $H$ are the sets of robotic arms and human operators, respectively.

The number of possible coalitions for each AGV can be very large due to combinatorial explosion, hence the necessity of using efficient approximate algorithms allowing to partially explore the solutions’ space and then select the best one.⁴⁶

Assumptions

The following assumptions are considered to construct our model:

(A1) The workshop configuration is defined and cannot be changed. Assembling or disassembling a mobile manipulator (AGV + robotic arm) has already been done at the tactical decision-making level, that is, deciding these actions is not made at this level. However, even if a given robotic arm is already joined to an AGV, it might be part of a coalition that is led by another AGV.

(A2) Only AGVs are in charge of the coalition formation.

(A3) Each AGV can transport only one product at a time and has enough space to carry any type of product, even when equipped with a robotic arm.

(A4) Each AGV keeps the location where it executed the previous transportation task’s last operation (unloading operation) until starting the following transportation task, without hindering the movement of other AGVs at that location.

(A5) The robotic arms already joined to AGVs are considered as a mobile arms and have variable locations. The other arms are considered as immobile arms, which are assigned to specific locations that cannot be changed.

(A6) The operators can perform only pick and place operations and are considered as immobile arms, that is, assigned to specific locations.

(A7) Each robotic arm and each human operator has its/his own payload limit, that is, the maximum weight it/he can safely handle.

(A8) The picking and placing locations of products are known and correspond to the locations of different stocks raw materials’ stock(s), machines’ input and output buffers and finished products’ stock(s)). The machines’ input and output stocks are considered at the same location of the machine.

Mathematical formulation

The local problems of choosing the best coalition for each AGV, for each transportation task, can be mathematically represented by the following generic optimization problem.

For a given AGV v and a given transportation task k, the corresponding optimisation problem can be formulated as follows:

Minimize \sum_{i \in I^{k}} \sum_{r \in R^{v}} Y_{r, i, k} \times δ_{r, i, k}

(3)

\begin{matrix} Subjetct to \\ \sum_{r \in R^{v}} Y_{r, i, k} = 1 \forall i \in I^{k} \end{matrix}

(4)

\sum_{i \in I^{k}} \sum_{r \in R^{v}} Y_{r, i, k} \times ψ_{r, i, k} = l_{k}

(5)

\sum_{r \in R^{v}} Y_{r, i, k} (γ_{r} + λ_{r, i, k, σ}) \geq 1 \forall i \in I^{k}

(6)

\sum_{r \in R^{v}} Y_{r, i, k} \times δ_{r, i, k} - \sum_{r \in R^{v}} Y_{r, i, k} \times τ_{r, i, k} \geq 0 \forall i \in I^{k}

(7)

The objective function (3) minimizes the duration (completion time) of the transportation task of the current bidding and, consequently, the delivery time of the product. The constraint (4) ensures that each operation composing the task can have only one winner. The resources in charge of operations must meet the physical requirements, such as the function required (transport, pick, and place, etc.), and/or the type of end-effector, and/or the minimum payload, etc. For example, a given AGV might not be able to satisfy a pick and place function, but only a carrying function like all other AGVs. Moreover, human operators, like robotic arms, can only satisfy a pick and place function. This condition is expressed by equation (5). As shown in equation (6), to perform an operation, a resource must also be located at – or able to reach – the position where the operation takes place. The set of constraints represented by equation (7) ensures that immobile resources that are not located where a given operation i takes place ( $γ_{r} = 0$ and $λ_{r, σ_{i, k}^{s}} = 0$ ), can never be selected to perform that operation. In fact, when $δ_{r, i, k} = 0$ , equation (7) implies that $Y_{r, i, k} = 0$ because $τ_{r, i, k} > 0$ .

Research validation

Use case description

The Figure 3 describes a real workshop of LINEACT laboratory composed of four manual assembly workstations. The objective is to assemble tricycles and then transfer them to the finished-products stocking zone of the workshop. Thus, three AGVs (Two MiR100 and one Robotnik) are in charge of transferring products from different workstations. In order to assemble a tricycle, eight transportation tasks (task1,. . . , task8) have to be made. The first four tasks aim to supply the workstations ( $s_{1}, s_{2}, s_{3},, s_{4}$ ) by raw materials from the middle workstation ( $s_{0}$ ) , which represents the raw material stock. As shown in Table 2, a set of robotic arms (Universal robots UR5 and UR10) and human operators are also included in the experience. All the resources are characterized by:

(i) the maximum payload : maximum weight the resource can handle;

(ii) the type: mobile, or immobile;

(iii) the location: physical coordinates (time-varying for mobile resources);

(iv) the speed : moving rapidity for mobile resources (when changing location), or zero for immobile resources. The mobile arms take the speed of the AGVs to which they are attached.

(v) the processing time: the time needed by a resource to complete one handling operation (loading or unloading).

Figure 3.

The workshop layout, resources and transportation tasks of one tricycle assembly process.

Table 2.

Resources’ characteristics.

Resource	Maxpayload(Kg)	Location	Type	Speed( $m / s$ )	Processingtime (s)
AGV1	100	p0	Mobile	1.5	-
AGV2	100	p0	Mobile	1.2	-
AGV3	250	p0	Mobile	0.9	-
a1	10	s4	Immobile	0	8
a2	5	s1	Immobile	0	6
a3	5	s2	Immobile	0	7
a4	5	s3	Immobile	0	7
a5	5	p0	Mobile	1.2	6
a6	10	s5	Immobile	0	9
a7	10	p0	Mobile	0.9	9
h1	7	s1	Immobile	0	[6, 8]
h2	7	s2	Immobile	0	[6, 8]
h3	7	s0	Immobile	0	[6, 8]

Results

The local decision model, proposed in the previous section, has been developed under Python programming language. The problem is solved by an integer linear programming based approach using “Google OR-tools for Python” library. Table 3 summarizes the assignment of the eight tasks, by providing the requirements of each task, and the associated results of resources allocation. Thus, each AGV provides the best coalition, that minimizes the task duration, after resolving the corresponding ILP. The winner between the proposed coalitions is the one minimizing the task delivery time. Thus, a coalition can provide the lowest task duration without being the winner. This is the case for task 6 with the coalition proposed by AGV1, which provides the lowest task duration, but not the minimum delivery time. Thus, the task 6 is assigned to the coalition of AGV3 with h2 and a1. The selection of the minimum delivery time leads to a reduced makespan. In the assignment of some tasks (task 7 and task 8) the AGVs propose the same teams. This demonstrates the efficiency of the local decision model. The resources are chosen for their abilities to meet tasks requirements and also for their performances in terms of speed and/or processing time.

Table 3.

Result for an instance with eight tasks.

Task	Requirements		Best coalitions			Winner
Task	Path	Payload(kg)	Coalitions	Duration(s)	Delivery Time(s)	Winner
1	$s_{0} \to s_{1}$	4	h3, AGV1, a2	20.6	20.6	h3, AGV1, a2
			a5, AGV2, a2	22.8	22.8
			h3, AGV3, a2	26.4	26.4
2	$s_{0} \to s_{2}$	2	h3, AGV1, a3	26.3	47.0	a5, AGV2, a5
			a5, AGV2, a5	22.8	22.8
			h3, AGV3, a3	27.4	27.4
3	$s_{0} \to s_{3}$	3	h3, AGV1, a4	26.8	47.5	h3, AGV3, a4
			a5, AGV2, a5	28.6	51.5
			h3, AGV3, a4	27.9	34.0
4	$s_{0} \to s_{4}$	3	h3, AGV1, a1	27.3	50.0	h3, AGV1, a1
			a5, AGV2, a5	28.6	51.5
			h3, AGV3, a1	36.2	75.6
5	$s_{1} \to s_{3}$	5	a2, AGV1, a4	33.2	83.2	a2, AGV2, a5
			a2, AGV2, a5	28.6	51.5
			a2, AGV3, a7	35.5	64.4
6	$s_{2} \to s_{4}$	2.5	h1, AGV1, a1	27.3	77.3	h2, AGV3, a1
			a5, AGV2, a5	37.0	88.4
			h2, AGV3, a1	37.3	76.2
7	$s_{3} \to s_{4}$	7	a7, AGV1, a1	41.4	91.4	a7, AGV2, a1
			a7, AGV2, a1	36.4	88.0
			a7, AGV3, a1	39.2	115.2
8	$s_{4} \to s_{5}$	9.5	a1, AGV1, a6	20.3	108.3	a1, AGV1, a6
			a1, AGV2, a6	21.1	109.1
			a1, AGV3, a6	33.6	130.0

The minimum delivery times that determine the winners are bolded.

The coalitions formed by the AGVs with the associated times are presented in Figure 4. It is a Gantt chart illustrating the schedule of transportation tasks won by each AGV, while denoting on each task the resources selected for loading and unloading operations. Firstly, we observe that some resources belong to several coalitions at the same time. In fact, being part of one coalition does not prevent a resource from participating in another one, as long as the associated time periods do not overlap. For example, the operator h3 belongs to both coalitions, led by AGV1 and AGV3, that are in charge of task1 and task3, respectively. As it can be seen, h3 starts the loading operation of task3 only after finishing the loading operation of task1. Moreover, we can observe that a loading or unloading operation (colored in cyan and yellow, respectively) can have a large time duration ( $δ_{r, i, k}$ ) when the resource in charge of it has priorly to move to the operation location. Furthermore, Figure 4 shows the efficiency of the global decision model. Indeed, for parallel tasks, we notice that no resource executes two distinct operations at the same time even if they can belong to several coalitions at the same time.

Figure 4.

Coalitions in charge of tasks.

Based on the participation of robots in different coalitions, this approach, designed for operational decision-making level, can also be used for tactical decisions via simulation. Thus, the resources that do not participate in any coalition could be removed or reconfigured to be used for other tasks or applications in the factory. For instance, the operator h2 intervenes only once and the robotic arm a3 is not part of any winning coalition.

Clearly, the removal of inactive resources, such as a3, will not affect the system, whereas the removal of the resources which intervene at least once, such as h2, could impact the overall completion time. An experimental comparison provides the following completion times: $108.3 s$ and $109.1 s$ , respectively for the cases with and without including the resources h2 and a3. Thus, the removal of resources h3 and a2 affects very slightly the completion time of all tasks (a gap less than 1 s).

Regarding resources utilisation criterion, it is interesting to observe the number of deployed resources in a coalition to perform a task, as shown in Figure 5. This number, denoted by N, allows to check the correctness and, in some way, reflects the efficiency of chosen coalitions. In fact, N must always be greater than two for any task since it requires at least two entities: a pick and place resource and a transportation resource. The number N also indicates the manner the task is performed and the nature of the selected resources. When N is greater than 3, it implies that at least one resource within the coalition is uselessly included because it is physically joined to another resource that is actually used in the coalition. For example, for task2, N is equal to 2, which implies that the AGV leading the coalition is using the on-board arm for loading and unloading operations. On the opposite, the coalition formed for task7 mobilises 5 resources which are: a7 (for loading), AGV3 (joined to a7) AGV2 (for moving), a5 (joined to AGV2), and a1 (for unloading).

Figure 5.

Number of deployed resources per task.

We also simulated a production run of a batch of 10 tricycles, using the proposed transportation tasks assignment approach. Figure 6 shows the total distance travelled by the AGVs as a function of the number of tricycles assembled. Note that the assembly of a tricycle requires eight transportation tasks (c.f. Figure 3). We can observe that the distances travelled by the AGV1 and AGV2 are both significantly greater than the distance covered by the AGV3, especially as the number of assembled tricycle increases. Indeed, the first two AGVs win more tasks, as they have much smaller execution times due to their higher speeds ( $1.5$ and $1.2$ $m . s^{- 1}$ ). However, we notice that although AGV1 has a higher speed than AGV2, the latter covers a greater distance. Thanks to its integrated arm, AGV2 has the capacity to carry out all the operations composing transportation tasks. Hence, it can act lonely or within a coalition by acting either as a leader (for only one moving operation) or as a simple member (for only one loading or unloading operation). Therefore, Figure 6 allows us to analyse the activities of resources and to deduce the impacting criteria. Thus, resources with high performance (speed, payload) and full capacities (AGVs equipped with robotic arms will win more activities, which allows the workshop to function in an optimized way regarding the overall completion time criterion, which could, by the way, be at the expense of other performance criteria which are not considered here, such as quality, energy consumption, equipment life-cycle costs, etc.

Figure 6.

Distance travelled by AGVs for ten tricycles assembly.

Conclusion

This paper deals with the problem of task assignment for modular robots in flexible manufacturing systems. The modularity of mobile manipulators allows them to be more flexible, but makes their control and task assignment more complicated. By using the concept of resources coalition, we propose a two-stage decision-making process to solve the problem. In the first stage, an ILP-based local optimisation process allows the master resources (AGVs), at the bottom level, to select the best coalition that satisfies the required capabilities for each task. In the second stage, a set of robots (a coalition) is selected at the high-level for each task, based on an auction process, where the bids come from the bottom level. A realistic case study was used to test the proposed approach and the obtained results show its applicability and efficiency.

Our future works will focus on the introduction of dynamic reconfiguration (assembly and disassembly) of mobile manipulator entities (AGV and arm) in the proposed method. We project also to enrich our model by taking into account more realistic constraints and performance criteria, such as delivery due dates, quality, machines buffers capacities, robots batteries capacities, energy consumption, congestion, maintenance, etc. Finally, it will be worthwhile to consider how the approach can be adapted to face disturbances and render the manufacturing system more efficient and more resilient.

Footnotes

Acknowledgements

This research was made possible thanks to €2.6 million financial support from the European Regional Development Fund provided by the Interreg V France Channel England Programme in context of CoRoT Project.

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 author(s) received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

M’hammed Sahnoun

References

Koren

Shpitalni

. Design of reconfigurable manufacturing systems. J Manuf Syst 2010; 29(4): 130–141.

Sharma

Jain

. Effect of routing flexibility and sequencing rules on performance of stochastic flexible job shop manufacturing system with setup times: simulation approach. Proc IMechE, Part B: J Engineering Manufacture 2017; 231(2): 329–345.

Mittal

Khan

Romero

, et al. Smart manufacturing: characteristics, technologies and enabling factors. Proc IMechE, Part B: J Engineering Manufacture 2019; 233(5): 1342–1361.

Hernandez-Martinez

Foyo-Valdes

Puga-Velazquez

, et al. Hybrid architecture for coordination of agvs in fms. Int J Adv Rob Syst 2014; 11(3): 41.

Schneier

Bostelman

. Literature review of mobile robots for manufacturing. Maryland: US Department of Commerce, National Institute of Standards and Technology, 2015.

Outón

Villaverde

Herrero

, et al. Innovative mobile manipulator solution for modern flexible manufacturing processes. Sensors 2019; 19(24): 5414.

Sahnoun

Abdelaziz

, et al. Optimization of transportation collaborative robots fleet size in flexible manufacturing systems. In: 2019 8th International conference on modeling simulation and applied optimization (ICMSAO), Manama, Bahrain, 2019, pp.1–5. DOI: 10.1109/ICMSAO.2019.8880315.

Le-Anh

De Koster

. A review of design and control of automated guided vehicle systems. Eur J Oper Res 2006; 171(1): 1–23.

Fauadi

MHFBM

Murata

. Combinatorial auction method for decentralized task assignment of multiple-loading capacity agv based on intelligent agent architecture. In: 2011 Second international conference on innovations in bio-inspired computing and applications, Shenzhan, 2011, pp.207–211. DOI: 10.1109/IBICA.2011.56.

10.

Vivaldini

Rocha

Martarelli

, et al. Integrated tasks assignment and routing for the estimation of the optimal number of agvs. Int J Adv Manuf Technol 2016; 82(1–4): 719–736.

11.

Tanner

Kyriakopoulos

. Nonholonomic motion planning for mobile manipulators. In: Proceedings 2000 ICRA. Millennium conference. IEEE international conference on robotics and automation. Symposia proceedings (Cat. No. 00CH37065) San Francisco, CA, 2000, vol. 2, pp.1233–1238. DOI: 10.1109/ROBOT.2000.844767.

12.

Ramchurna

El Souria

Gaoa

, et al. An analysis of automation scenarios in an aerospace environmental testing facility. In: Advances in manufacturing technology XXXIII: proceedings of the 17th international conference on manufacturing research, incorporating the 34th national conference on manufacturing research, Queen’s University, Belfast, 10–12 September 2019, vol. 9, p.93. Amsterdam, Netherlands: IOS Press.

13.

Vis

. Survey of research in the design and control of automated guided vehicle systems. Eur J Oper Res 2006; 170(3): 677–709.

14.

Dallas

Jain

Dong

, et al. Online terrain estimation for autonomous vehicles on deformable terrains. J Terramechanics 2020; 91: 11–22.

15.

Halberstam

Navarro-Serment

Conescu

, et al. A robot supervision architecture for safe and efficient space exploration and operation. In: Earth & space 2006: engineering, construction, and operations in challenging environment, 2006, pp.2–8. Virginia: American Society of Civil Engineers.

16.

Dieber

Breiling

. Security considerations in modular mobile manipulation. In: 2019 Third IEEE international conference on robotic computing (IRC), Naples, Italy, 2019, pp.70–77. DOI: 10.1109/IRC.2019.00019.

17.

Hichri

Fauroux

Adouane

, et al. Design of cooperative mobile robots for co-manipulation and transportation tasks. Rob Comput Integr Manuf 2019; 57: 412–421.

18.

Goumeye

M’Hammed Sahnouna

Bensrhair

. Modular mobile manipulators task allocation auction-ased approach b. In: Advances in manufacturing technology XXXIII: proceedings of the 17th international conference on manufacturing research, incorporating the 34th national conference on manufacturing research, Queen’s University, Belfast, 10–12 September 2019, vol. 9, p. 99. Amsterdam, Netherlands: IOS Press.

19.

Smirnov

Sheremetov

Teslya

. Fuzzy cooperative games usage in smart contracts for dynamic robot coalition formation: approach and use case description. In: Proceedings of the 21st international conference on enterprise information systems, Heraklion, Crete, Greece, 3–5 May 2019, pp.361–370. Setúbal, Portugal: SciTePress.

20.

Sandholm

Larson

Andersson

, et al. Coalition structure generation with worst case guarantees. Artif Intell 1999; 111(1): 209–238.

21.

Rauniyar

Muhuri

. Multi-robot coalition formation problem: task allocation with adaptive immigrants based genetic algorithms. In: 2016 IEEE international conference on systems, man, and cybernetics (SMC), Budapest, 2016, pp.000137–000142. DOI: 10.1109/SMC.2016.7844232.

22.

Zeng

Meng

, et al. Gini coefficient-based task allocation for multi-robot systems with limited energy resources. IEEE/CAA J Autom Sin 2017; 5(1): 155–168.

23.

Mouradian

Sahoo

Glitho

, et al. A coalition formation algorithm for multi-robot task allocation in large-scale natural disasters. In: 2017 13th international wireless communications and mobile computing conference (IWCMC), Valencia, 2017, pp.1909–1914. DOI: 10.1109/IWCMC.2017.7986575.

24.

Duffie

Prabhu

. Real-time distributed scheduling of heterarchical manufacturing systems. J Manuf Syst 1994; 13(2): 94–107.

25.

Leitão

Restivo

. Adacor: a holonic architecture for agile and adaptive manufacturing control. Comput Ind 2006; 57(2): 121–130.

26.

Nouiri

Bekrar

Trentesaux

. An energy-efficient scheduling and rescheduling method for production and logistics systems. Int J Prod Res 2019; 58(11): 3263–3283.

27.

Zheng

Tang

Giret

, et al. A hormone regulation–based approach for distributed and on-line scheduling of machines and automated guided vehicles. Proc IMechE, Part B: J Engineering Manufacture 2018; 232(1): 99–113.

28.

Rey

Bonte

Prabhu

, et al. Reducing myopic behavior in fms control: a semi-heterarchical simulation–optimization approach. Simul Modell Pract Theor 2014; 46: 53–75.

29.

Dominic

Kaliyamoorthy

Kumar

. Efficient dispatching rules for dynamic job shop scheduling. Int J Adv Manuf Technol 2004; 24(1–2): 70–75.

30.

Dorigo

Birattari

Stutzle

. Ant colony optimization. IEEE Comput Intell Mag 2006; 1(4): 28–39.

31.

Palau

Dhada

Parlikad

. Multi-agent system architectures for collaborative prognostics. J Intell Manuf 2019; 30(8): 2999–3013.

32.

Derigent

Cardin

Trentesaux

. Industry 4.0: contributions of holonic manufacturing control architectures and future challenges. J Intell Manuf 2020. DOI: 10.1007/s10845-020-01532-x.

33.

Drozdov

Atmojo

Pang

, et al. Utilizing software design patterns in product-driven manufacturing system: a case study. In: Borangiu

Trentesaux

Leitáo

, et al. (eds) Service oriented, holonic and multi-agent manufacturing systems for industry of the future. SOHOMA 2019. Studies in computational intelligence, vol. 853. Cham: Springer, https://doi.org/10.1007/978-3-030-27477-1_23

34.

Trimouleta

El Zahera

Viazzia

, et al. Multi robot path planning approach for dynamic environnement. In: Advances in manufacturing technology XXXI: proceedings of the 15th international conference on manufacturing research, incorporating the 32nd national conference on manufacturing research, University of Greenwich, UK, 5–7 September 2017, vol. 6, p. 275. IOS Press.

35.

Weyns

Boucké

Holvoet

. Gradient field-based task assignment in an agv transportation system. In: Proceedings of the fifth international joint conference on autonomous agents and multiagent systems, May 2006, pp.842–849. New York, NY: ACM.

36.

Zbib

Pach

Sallez

, et al. Heterarchical production control in manufacturing systems using the potential fields concept. J Intell Manuf 2012; 23(5): 1649–1670.

37.

Trentesaux

. Distributed control of production systems. Eng Appl Artif Intell 2009; 22(7): 971–978.

38.

. Agent-based hierarchical planning and scheduling control in dynamically integrated manufacturing system. PhD Thesis, Exeter University, Exeter, 2011.

39.

Ottaway

Burns

. An adaptive production control system utilizing agent technology. Int J Prod Res 2000; 38(4): 721–737.

40.

Kim

Heragu

Graves

, et al. A hybrid scheduling and control system architecture for warehouse management. IEEE Trans Rob Autom 2003; 19(6): 991–1001.

41.

Angeloudis

Bell

. An uncertainty-aware agv assignment algorithm for automated container terminals. Transp Res Part E: Logist Transport Rev 2010; 46(3): 354–366.

42.

Peschl

. An architecture for flexible manufacturing systems based on task-driven agents. PhD Thesis, Thesis to Doctoral program–Faculty of Information Technology and Electrical Engineering, Oulu University, Finland, 2014.

43.

Eyers

. Control architectures for industrial additive manufacturing systems. Proc IMechE, Part B: J Engineering Manufacture 2018; 232(10): 1767–1777.

44.

Ding

Lei

Zhang

, et al. Analyzing the cyber-physical system–based autonomous collaborations among smart manufacturing resources in a smart shop floor. Proc IMechE, Part B: J Engineering Manufacture 2020; 234(3): 489–500.

45.

Pach

. ORCA: Architecture hybride pour le contrôle de la myopie dans le cadre du pilotage des Systèmes Flexibles de Production. PhD Thesis, Université de Valenciennes et du Hainaut-Cambresis, 2013.

46.

Chen

. Manufacturable mechanical part design with constrained topology optimization. Proc IMechE, Part B: J Engineering Manufacture 2012; 226(10): 1727–1735.

Modular mobile manipulators coalition formation through distributed transportation tasks allocation

Abstract

Keywords

Introduction

Related works

Mobile manipulators

Category I Mobile manipulators

Category II Mobile manipulators

Robots coalition

Robotic tasks assignment

Potential fields

ContractNet

Distributed decision

Notations

Sets and indices

Parameters

Decision variables

Global decision

Local decision model formulation

Assumptions

Mathematical formulation

Research validation

Use case description

Results

Conclusion

Footnotes

Acknowledgements

Declaration of conflicting interests

Funding

ORCID iD

References