Guillaume Demesure
email: guillaume.demesure@univ-lorraine.fr

Damien Trentesaux
email: damien.trentesaux@univ-valenciennes.fr

Michael Defoort
email: michael.defoort@univ-valenciennes.fr

Abdelghani Bekrar
email: abdelghani.bekrar@univ-valenciennes.fr

Hind Bril

Mohamed Djemaï
email: mohamed.djemai@univ-valenciennes.fr

André Thomas
email: andre.thomas@univ-lorraine.fr

Smartness versus Embeddability: a tradeo for the deployment of smart AGVs in industry

Keywords: Automated Guided Vehicles, exible manufacturing systems, smartness, embeddability

In order to deploy AGVs in industry, it is mandatory to consider the tradeo between the smartness and the embeddability. This paper aims to make the manufacturing research community more sensitive about this tradeo and its consequences. Nowadays, AGVs are widely chosen by manufacturers to implement exible material-handling systems which are necessary to cover the industrial requirements. However, many issues, presented in this paper, must be tackled to deploy these AGVs. A tradeooriented procedure is proposed by considering these issues in exible manufacturing system applications. Then, an approach is proposed to illustrate this procedure by providing simulation and experimental results. This approach is also used to roughly describe the smartness/embeddability tradeo.

Introduction

Day after day, the industrial requirements evolve and become stricter [START_REF] Trentesaux | Distributed control of production systems[END_REF], where reactivity in the short term and adaptability to the market in the long term become harder to obtain. This can lead the industrials to reconsider their manufacturing plants by applying new approaches to cover these requirements. In this context, exible manufacturing systems have several interests to consider automated guided vehicles (AGVs). Indeed, since the technological evolution in mechatronics, computer science and Information and Communication Technologies (ICT) allows improving the use of AGV while limiting their cost [START_REF] Ueda | Emergent synthesis approaches to biological manufacturing systems[END_REF], the scope of reactive behavior in the dynamic routing of AGVs is enlarged. In this paper, AGV-based exible manufacturing systems are considered where products must be completed according to 1 some manufacturing specications. The AGVs, used as product transportation systems, are assumed to navigate freely on the production oor.

The use of AGVs in manufacturing plants allows improving their exibility in terms of materialhandling or routing, aiming for greater responsiveness to industrial requirements. However, it needs considering several AGV aspects for an ecient functioning of their plants. For example, the embeddability and the feasibility of designers' approaches must be tackled before the AGV deployment in industry. The feasibility allows proving that an approach is technically feasible and economically protable. The embeddability [START_REF] Malinowski | Comparison of embedded system design for industrial applications[END_REF] refers to the capacity to embed enough communication, computational and energy devices in AGVs. Based on the holon paradigm, an AGV can be considered as a resource holon in a HMS since decisional capabilities are embedded [START_REF] Berger | Open control of FMS and its application to potential eld[END_REF]. The embeddability depends on the smartness level of their functions. Indeed, having a highlevel of smartness means that the embedded functions have the capacity to deal with complex situations. However, the AGVs may not have the capacity to apply them correctly in short time, leading to computational overload which impacts the feasibility. Conversely, because of limited available processing capabilities, the AGVs may only be able to deploy simple functions where their lack of smartness prevents them from dealing with complex situations and being used at their full potential. Thus, one can see the AGV tradeo between their smartness and their embeddability.

To deal with this tradeo, the manufacturing research community and the industrial one design their approach dierently. The industrial community deals more with the embeddability by designing simple embeddable functions with little attention being paid of the AGV smartness. Conversely, the manufacturing research community tends to design complex approaches by improving this smartness. However, the complexity to solve their smart approach is hardly compensated by the technical evolution. For example, the navigation is one of AGV functions which could be hard to embed. Indeed, the navigation tools are often complex since they need to be smart enough to prevent unexpected situations (e.g. deadlock [START_REF] Erol | A multi-agent based approach to dynamic scheduling of machines and AGVs in manufacturing systems[END_REF], conicts [START_REF] Demesure | Navigation scheme with prioritybased scheduling of agents: Application to AGV-based FMS[END_REF], local minima [START_REF] Berger | Open control of FMS and its application to potential eld[END_REF] ...). Therefore, this paper is focused on approaches which include a navigation function, especially due to its major impact on the tradeo.

Among the several navigation tools, motion planners are widely used [START_REF] Masehian | Classic and heuristic approaches in robot motion planning-a chronological review[END_REF], allowing the generation of collisionfree trajectories between two congurations. Since the AGV navigation is related to the production performances, mathematical programming seems to be an interesting tool [START_REF] Defoort | A motion planning framework with connectivity management for multiple cooperative robots[END_REF]. However, the motion planning problems are NP-Hard [START_REF] Canny | The complexity of robot motion planning[END_REF], leading to reduce the computational time with meta-heuristic algorithms [START_REF] Masehian | A multi-objective PSO-based algorithm for robot path planning[END_REF] or with discretization of the navigation area [START_REF] Thyagarajan | A motion control algorithm for steering an agv in an outdoor environment[END_REF]. Even if the navigation may prevent the AGV deployment in industry, some approaches have been proposed in indoor environments. The Kiva system [START_REF] Wurman | Coordinating hundreds of autonomous vehicles in warehouses[END_REF], which is currently used in Amazon warehouses [START_REF] Gilmour | Amazon warehouse, amazon adventure[END_REF], uses a standard implementation of A * algorithm to plan path. In [START_REF] Martínez-Barberá | Autonomous navigation of an automated guided vehicle in industrial environments[END_REF], the AGV navigation is solved using a D * algorithm coupled with other functions.

The main purpose of this paper is to make the designer of AGV-based exible manufacturing systems more sensitive about this existing tradeo. Based on a design for "x" paradigm [START_REF] Kuo | Design for manufacture and design for `x': concepts, applications, and perspectives[END_REF], designing for tradeo is more suitable than only considering the smartness or the embeddability. Hence, the designers of AGVbased exible manufacturing systems need to consider new approaches or reconsider their previous ones to deal with this tradeo. Therefore, this article can be viewed as a basis where the main issues are presented and are related to a procedure representing the several design and test steps. An illustrative example is provided by proposing an approach tested in simulation and experimentally environment. This example highlights the consequences of the smartness/embeddability tradeo.

The paper is organized as follows. Section 2 presents the main issues that designers may tackle using AGV functions. A design procedure, allowing to highlight the tradeo and consequences, is proposed in Section 3. The illustrative example with results and discussions are provided in Section 4.

Issues which may impact the tradeo

In order to deal with the mentioned tradeo, it is necessary to introduce the main issues that AGV may solve using smart functions. Firstly, collision-free trajectories between resources are required since AGVs navigate freely on the production oor. These trajectories (path) have to be feasible due to the physical behaviors and constraints. The disturbances and discrepancies must be taken into account to prevent deviation from the planned trajectory. Furthermore, all issues related to localization, mapping and actuators/sensors must be tackled. Moreover, communication devices are required to send information in short time between AGVs and with the higher level of control (e.g. resources, supervisor...). The energy is another issue to tackle since the battery has limited capacities. Indeed, the battery charge/discharge may change the decisions that AGVs make according to the task they have to perform.

Secondly, several other issues are related to the AGV environment since they navigate in a exible manufacturing system. For example, manufacturing disturbances such as machine breakdown may occur at any time which impacts the AGV decisions. As each AGV computes its own functions, the control architecture is fully or partially distributed. In spite of improving the reactivity, this architecture is more complex in structure and organization and may lead to myopic behaviors [START_REF] Trentesaux | Distributed control of production systems[END_REF]. To remove these drawbacks, the control architecture must be adapted (by including a supervisor for example) and the interactions between the dierent entities (dened in [START_REF] Trentesaux | Distributed control of production systems[END_REF]) must be tackled to prevent decision conicts [START_REF] Bader | Balancing centralised control with vehicle autonomy in agv systems for industrial acceptance[END_REF].

The last issues are related to the industrial environment and the AGV deployment. Human factors must be taken into account because human workers may impact the AGV-based exible manufacturing system. For example, hu-mans may work on some resources or AGVs for maintenance purpose. The humans must be able to understand the AGV behaviors as well as to take control of the system in case of failure. Therefore, safety functions, allowing to prevent collisions with humans, and AGV/human cooperation mechanisms must be embedded in the AGVs.

All the issues mentioned above are related to the smartness of AGVs. However, the embeddability issue may prevent them to improve their smartness. Hence, the number of functions that they cover may be limited, due to technically and/or economically reasons. It may lead to reconsider their functions (e.g. the number of functions and their role) in order to reach a good tradeo. This tradeo can be seen as a balance where the smartness and the embeddability, respectively depending on the AGV functions and their device capabilities, are on each side of the balance as shown in Fig. 1. One can see on this gure that improving the smartness increases the weight on the left side of the balance. To compensate, the embeddability has to be improved by adding some weights in the right side. However, it impacts the deployment cost since AGV with better capabilities are more expensive. Thus, this cost becomes an important issue since their deployment needs to be economically protable, allowing a good return on the investment. From these statements, the embeddability is limited by this cost, preventing the improvement on the smartness of AGV functions.

Proposed tradeooriented procedure

The design of AGV approaches in exible manufacturing system depends on production objectives and specications. To cover these requirements, the AGVs must tackle one or several issues by using embedded functions. To keep the AGV benets, it is often recommended to follow a design procedure while thinking about the next steps where some issues may occur. In Fig. 2, a tradeooriented procedure is proposed by providing several design steps and tests until the AGV deployment. Each step has its own role but may depend on other steps. The role of each step is described as follows: • AGV objective and assumption setup: In this step, the problem is set for each AGV by dening their objective. Furthermore, several assumptions can be proposed to make the problem simpler. During the next steps, these assumptions may be reconsidered to take more issues into account.

• AGV function assignment and architecture design: This step is used to dene the dierent functions of the AGV. The functions that AGV do not cover must be tackled by other entities (e.g. supervisor). Thus, the control architecture, where the interactions between the dierent entities are studied, must be designed to prevent conicts between them.

• Detailed design of AGV smart functions: The AGV functions, including the navigation one, are detailed in this step. If the tradeo between smartness and embeddability is not reached, some functions may be exchanged with the manufacturing high-level of control.

• AGV navigation algorithm design: After dening the functions, the navigation tools of AGVs must be designed such as the motion planner, the control strategy, the used algorithm (e.g. A * , metaheuristics, ...)

• Simulation and numerical results: These rst results allow showing a preview about the feasibility, the smartness and the performances of the designed approach. When the results lead to infeasibility, an in-depth analysis must be done. This analysis allows nding the step(s) at which modications are required. If the AGV smartness or the performances are not good enough, the functions both from the AGV and from other entities must be modied or improved.

• Feasibility tests of navigation algorithms: In this step, the navigation algorithms are experimentally tested to check if the trajectories, provided by the navigation tools, are feasible. If not, the AGV navigation algorithms must be improved by reconsidering the two previous steps.

• Embeddability tests of AGV functions: After coding and embedding all the AGV functions, the embeddability is checked. An experimental scenario must be designed to test the overall functions by letting the AGVs do their mission. If they do not have the capacity to do it, the smart functions of AGVs must be redesigned.

• Production tests on benchmark systems: When embeddability is checked, the AGV functions can be tested on higher instances. A full production scenario (e.g. benchmark [START_REF] Trentesaux | Benchmarking exible job-shop scheduling and control systems[END_REF]) is designed. However, some functions could be missing to cover other issues such as global optimization or energy. Thus, these functions need to be included in the AGVs or in the manufacturing high-level of control and previous steps must be tackled again.

• AGV deployment in industry: To carry out this step, the dierent issues related to the industrial environment must be tackled. It can lead to reconsider some assumptions, made to simplify the designed approach. Other systems, such as supervisor, have to be designed to take human factor into account. For example, user-guided interface can be used, allowing human workers to take control of the manufacturing plant or to understand the AGV behavior. Moreover, the cost must be evaluated, leading to reconsider previous steps to reduce the AGV deployment cost.

In order to reach a good tradeo, the idea is not to follow the procedure step by step but rather to follow a design for tradeo procedure, thinking about the AGV capability and the cost required to obtain these capabilities. Indeed, using the balance paradigm (i.e. Fig 1), some weights are positioned on each side of the balance. On one side, the weights correspond to the AGV functions, depending on their complexity. On the other side, the weights are related to the AGV computational capabilities where for example, one weight may correspond to one processor core. Heavier weight gives higher AGV capabilities but their cost are also higher. Therefore, to take the design for tradeo aspect into account, it should be suitable to deal with the AGV capabilities and their consequence it terms of cost before starting designing their smart functions. After dening these capabilities, the AGV functions could be design until the tradeo is respected. It can lead to reduce the function smartness or to remove some functions in AGVs. Hence, cooperation mechanisms [START_REF] Demesure | Cooperation mechanisms in multi-agent robotic systems and their use in distributed manufacturing control: Issues and literature review[END_REF] with other entities of the exible manufacturing system become useful to outweigh the AGV smartness according to their capabilities.

Illustrative example

To illustrate the proposed tradeooriented procedure, an example is proposed in this section where AGVs navigate on a manufacturing production oor. This illustrative example is tested by giving some simulation and experimental results. The steps of the procedure, in Fig. 2, are roughly described and the tradeo is discussed according to the provided AGV capabilities.

AGV design steps: In the proposed approach, the production objective is to complete several products, transported by AGVs. Each AGV transports only one product from a resource to another one until the product is completed. For each product, transported by one AGV, an operational sequence must be followed where operation are tackled one by one. For each operation, some production specications are provided to the AGV by the manufacturing operation and resource management (M.O.R.M.) level. These specications include a due date for which the operation must be completed and a set of resources at which the operation may be performed. Moreover, the resources have queuing capacities, assumed innite at rst, and AGVs in queue must wait to perform their operation when resource is unavailable (e.g. performing an operation of other AGV). The resource disturbances and the energy issues are not tackled to make the problem simpler.

Since the exible manufacturing system layout, the production objective and the dierent specications are given, the AGV design steps (i.e. left side of the procedure provided in Fig. 2) can be described. The AGV objective is both to compute the best resource and to generate a collisionfree trajectory towards this resource. The best resource is chosen by minimizing the time to complete the ongoing operation and depends on the transportation time, the waiting time and the processing time of the resource. Minimizing the completion time is equivalent to complete the operation at the soonest date. In terms of assumptions, all AGVs have the same physical behaviors where their velocity are bounded and they are supposed to know their position at any time as well as the position of the resource they are moving towards. They have a limited communication range and are called neighbors when they are able to communicate. Moreover, they are able to communicate with the higher level of control, to receive help or specications and transmit feedbacks about their conguration.

The dierent functions assigned to the AGV are mainly focused on their navigation. The motion planning function, combined with the scheduling one, allows selecting a resource at which the operation will be performed while generating a collisionfree trajectory towards this resource. The tracking strategy function is in charge of following the planned trajectory in spite of inherent discrepancies and disturbances. The control architecture, where all AGV functions are highlighted, is given in Fig. 3. The AGV may interact with a supervisor which allows helping their navigation by solving the conicts using performancebased priority negotiation. Moreover, it allows preventing their myopic behaviors since the AGVs only communicate with their neighbors. The supervisor has the role to solve the dierent conicts. At rst, it denes the arrival order of AGVs if they are moving towards the same resource. Furthermore, the AGV applies the scheduling function only if the supervisor allows it. The last supervisor function allows AGV to anticipate the collision by providing them some variable areas where big conict may occur. It allows AGV to avoid these areas before reaching them, reducing the complexity of the AGV motion planner since big conict areas are prevented. For the detailed design of AGV functions, the motion planner uses physical constraint (e.g. velocity bound) and temporal constraint (e.g. due date) to compute a collisionfree trajectory towards a selecting resource. This planner is applied gradually over time and is divided into two steps. The rst step, where the resource is chosen, is used as a global planner where AGVs must decide their intention by planning a presumed trajectory to avoid the conicts given by the supervisor. The second step is local since each AGV uses the presumed trajectories, both its own and its neighbors' ones, to compute its nal collisionfree trajectory. One can notice that each AGV only avoids its neighbors having higher priority. It means that the AGV with the highest priority does not need to avoid others.

In terms of algorithm design, mathematical programming is used for each part (global and local) of the motion planner since it is related to the manufacturing performances. For embeddability purpose, the solving algorithms have to provide the trajectories in short time since they are computed over time. To reduce the computational costs, a Particle Swarm Optimization (PSO) is used due to its relatively fast convergence and global search character [START_REF] Saska | Robot path planning using particle swarm optimization of ferguson splines[END_REF].

AGV test steps: Since the design steps have been given, the approach has to be tested to follow the procedure given in Fig. 2. To provide the simulation and numerical results, the AGV physical constraints are required. The AGVs are here represented by Lego Mindstorms robots where their maximum allowed velocity is 0.15m/s. Their communication range and safety distance are respectively set to 0.4m and 0.2m. The number of robots (called AGV i) is limited to 4 (i.e. i = 1, 2, 3, 4) and they navigate in a reduced area where three virtual resources (called R c , c = 1, 2, 3) are positioned (as shown in Fig. 4). The positions (x c , y c ) of resources R c are set to (1.85, 0.2), (1.9, 0.9) and (1.85, 0.65), respectively. For this scenario, the several AGV initial parameters can be found in Tab. 1. When the scenario starts, AGV 3 has the highest priority while AGV 4 has the lowest one.

For the simulation results of the proposed scenario, the AGV planned trajectories are provided in Fig. 4. One can see that AGV 3 does not avoid any other AGVs due to its highest priority. Conversely, AGVs 1 and 4 must adapt their trajectories to avoid others and AGV 2 needs to avoid AGV 3. The approach is feasible in simulation since the velocity and collision avoidance constraints are fullled according to Fig. 5. Moreover, Table 2 shows that the operations of products transported by AGVs are completed before the provided due dates. During the navigation, one can see that AGV 4 changes its chosen resource. It implies that AGV 1 has lower priority than AGV 4. Therefore, the AGV smartness is proved since they are able to apply their function in spite of their specications they have to fulll. Indeed, collisionfree trajectories are planned by the AGVs and the scheduling function is applied (AGV 4) to improve its product performances. Moreover, the supervisor allows them to prevent unsolvable conict arisen from myopic behaviors. The next step of the procedure is focused on the feasibility tests of navigation functions. Thus, the trajectories are tested by the Lego Mindstorms robots for this scenario. The feasibility of the trajectories is demonstrated experimentally as shown in the video1 where all explanations are provided. Chosen resource

R 3 R 1 R 2 R 3
To test the embeddability of AGVs, it is mandatory to consider the provided robots capabilities. These robots do not have the same capabilities as industrial AGVs, which are able to cover dierent functions [START_REF] Martínez-Barberá | Autonomous navigation of an automated guided vehicle in industrial environments[END_REF]. Thus, all of designed functions cannot be embedded in AGVs to prevent bad tradeos as shown Fig. 6(A) and (B). To reach a good tradeo, the AGV functions must be reduced to the tracking one (see Fig. 6(C)). It means that the combined motion planning/scheduling functions are computed by another entity, such as the supervisor, and then transmitting to the AGVs. Using the Lego Mindstorms robots, the production tests are hard to obtain since they do not have to capabilities to plan their own trajectory. Indeed, planning a trajectory gradually over time for each AGV is computationally expensive, preventing to deal with manufacturing uncertainties such as machine breakdown. To perform these production tests, reconsidering the used AGVs seems to be more appropriate. Therefore, the AGV capabilities have to be improved to use their functions at full potential while maintaining a good tradeo. Thus, the weights of the tradeo balance changes, as shown in Fig. 6(D), by proposing some expectations about the required AGV capabilities.

In order to deal with our proposed approach, the AGVs must be able to compute their own functions simultaneously. Thus, improving their capabilities is required by using multi-core processors for example. Using these processors, the computational time could be reduced and other tools, such as parallel metaheuristic [START_REF] Alba | Parallel metaheuristics: a new class of algorithms[END_REF], may be proposed to solve our motion planning problem. Indeed, since a resource must be selected, a trajectory for each resource could be computed in parallel. Moreover, the AGV capabilities must consider other simple functions such as the safety or energy ones which are not tackled in the proposed approach. Therefore, using multi-core processors is more suitable where each core can be represented as a weight in the embeddability side of the balance (i.e. Fig. 1). Nowadays, quadcore processors are easily embedded (e.g. in smart phones) and become less expensive than the last decades. Thus, their use as AGV device may be economically protable.

Conclusion

In this paper, a tradeo between smartness and embeddability is discussed for the use of AGVs in manufacturing plants. Several issues, which may be solved using AGV functions and have a possible inuence on this tradeo, are presented. The objective allows making the designers of AGVbased exible manufacturing systems more sensitive about this tradeo and its consequences. A tradeooriented procedure is advisable to balance the smartness according to the AGV functions and its capabilities. An illustrative example on an AGV-based exible manufacturing system is proposed where simulation and feasibility tests are provided to highlight the importance of this tradeo for the AGV deployment in industry. To quantify and ease the analysis of this tradeo, depending on company culture and methods, the designer could use some methods from the quality domain, like Value Analysis Method, Kano Model or Quality Function Deployment (QFD). Consequently, this rst work leads to many perspectives from i) methodological view: how to choose efcient AGVs depending of requirements and how adapt them to deals with organization or requirements changes and ii) domain applications view: the introduction of AGVs on manufacturing processes opens new ways to organize the shop oor. It could be interesting, for example, to evaluate which physical element associate to AGV: the product or the resource?

Fig. 1

 1 Fig. 1 Tradeo balance between smartness and embeddability

Fig. 2

 2 Fig. 2 Main steps of AGV design procedure until the deployment in industry

Fig. 3

 3 Fig. 3 Control and decision architecture of the illustrative example

Fig. 4 Fig. 5

 45 Fig. 4 Simulation of the illustrative example: AGV planned trajectories

Fig. 6

 6 Fig. 6 Tradeo balance for the proposed approach: (A) all AGV functions, (B) scheduling function removed, (C) tracking function only (D) all functions with better capabilities

Table 1

 1 Agent initial parameters of the proposed scenario

	Initial Operation Processing Resource
	position due date	time possibilities
	AGV 1 [0.1, 0.125] 76.1s	5.4s	{R 3 }
	AGV 2 [0.1, 0.625] 30.8s	4.3s	{R 1 }
	AGV 3 [0.1, 1.125] 23.8s	5s	{R 2 }
	AGV 4 [0.1, 1.625] 60.2	4.7s	{R 2 , R 3 }

Table 2

 2 Numerical results of the proposed scenario AGV 1 AGV 2 AGV 3 AGV 4 Initial chosen resource R 3

		R 1	R 2	R 2
	Final time	25.44s 17.76s 13.14s 21.02s
	Completion time	31.12s 22.07s 18.14s 25.72s

Available at: https://www.youtube.com/watch?v=KUY7cBRx9vI&feature=youtu.be