- Email: [email protected]

A performance-based structural policy for conflict-free routing of bi-directional automated guided vehicles Samia Maza *, Pierre Castagna Institut de Recherche en Communications et Cyberne´tique de Nantes (IRCCyN), UMR CNRS 6597, 1 rue de La Noe, BP 92101, 44321 Nantes Cedex 3, France Received 13 February 2005; accepted 31 March 2005 Available online 10 August 2005

Abstract Automated guided vehicles (AGVs) play an important role in flexible manufacturing systems. One of the key issues of using AGVs is the conflict-free routing especially when the AGV system is bi-directional. Two classes of routing algorithms have been proposed in the literature: Optimised pre-planning algorithms, and Real-time routing algorithms. Pre-planning algorithm present the advantage of producing optimal conflict-free routes, but do not deal with changing situations such as vehicle delays and failures. Real-time algorithms present the advantage of being reactive, but are non-optimal. In this paper, we propose to combine the advantages of both. We use a two-stage approach: In the first control stage, a pre-planning method to establish the fastest conflict-free routes for AGVs. In the second stage, conflicts are avoided in a real-time manner when needed. The objective of this last is the avoidance of deadlocks in presence of interruptions while maintaining the established AGVs’ routes. Two robust routing algorithms are presented. The efficiency of our approach is analysed using developed simulations. # 2005 Elsevier B.V. All rights reserved. Keywords: Automated guided vehicle; Bi-directional AGV system; Conflict; Routing; Robust control

1. Introduction Automated guided vehicles (AGVs) are advanced material handling devices used to transport goods and materials between workstations and storage areas of an automated manufacturing systems (AMS). * Corresponding author. Tel.: +33 2 40 37 69 78; fax: +33 2 40 37 69 30. E-mail addresses: [email protected] (S. Maza), [email protected] (P. Castagna).

An AGV system (AGVS) is a set of cooperative driver-less vehicles, used within the same manufacturing floor and coordinated by a centralized or distributed computer-based control system. The manufacturing floor is specified via a set of physical or virtual guide-paths. If the AGVs can only move according to one direction, the guide-paths or the AGVs are called unidirectional. Otherwise, if the AGVs are authorised to traverse a lane according to two opposite directions, the AGV system is said to be bi-directional.

0166-3615/$ – see front matter # 2005 Elsevier B.V. All rights reserved. doi:10.1016/j.compind.2005.03.003

720

S. Maza, P. Castagna / Computers in Industry 56 (2005) 719–733

Egbelu and Tanchoco [1] have shown in a simulation study that the bi-directional AGV model can considerably improve the performance of a manufacturing system. These advantages are balanced by an increased set of potential conflicts, and thus the need for a more complex control strategy. For a successful deployment of an AGVS, the following key issues should be addressed [2]: (a) the flow path design; (b) the determination of the AGVs fleet size; (c) the development of operational policies for job and AGV scheduling and dispatching; (d) the synthesis of conflict-free routing. We are interested in the last problem, i.e., establishing robust conflict-free routes for bi-directional AGVs, in the specific case when the AGV system is subject to contingencies. In this paper, we propose a novel strategy that has two important objectives. The first one is to deal with global AGV system’s performances, while the second one is to consider the disturbances in the AGV system. This paper is organised as follows. A literature review and a classification of the recent results dealing with the conflict-free routing of bi-directional AGVs are presented in Section 2. Section 3 provides a brief description of the conflict-free path planning method used in our control scheme and a critical study of that method. In Sections 4 and 5, we present a new approach to make this planning method more robust. Two different algorithms are presented. The first one allows deadlock and conflict avoidance in real-time while respecting the plans established by the preceding method. The second algorithm has the objective of improving the first one by doing a local AGV’s re-scheduling. A simulation study is presented in Section 6, where a comparison between the two algorithms is done. Finally, Section 7 is devoted to conclusions.

2. Literature review Our literature review focuses on papers that specifically deal with the routing problem of bidirectional AGVs. The research related to the traffic control in bi-directional AGVSs has not been often addressed in the literature until these last few years.

These methods can be classified into two categories: the predictive methods and the real-time or dynamic methods, also known as deadlock avoidance methods. 2.1. The predictive or pre-planning methods The main task of these approaches is to find a route for a vehicle from its current location to its desired destination. The AGV is scheduled to ensure a collision-free journey of it along the selected path while minimising the travel time. All the methods of this category have a common feature: the AGV’s path is pre-planned assuming that there will be no interruptions on route. These deadlock prevention approaches define off-line the rules for avoiding conflicts; the vehicles’ routes are planned to satisfy these rules and conditions. Kim and Tanchoco [3,4] propose a method for path planning, which takes routing decisions at each node of the AGV journey, on the basis of the vehicles’ displacement. This method is explained in Section 3. Krishnamurthy et al. [5] provide an approach for the combined problem of vehicles dispatching (AGVs’ tasks allocation) and the conflict-free routing. They use the integer programming formulation to minimize the total makespan. This minimization is done under a set of constraints modelling the conflict-free conditions. Langevin et al. [6] proposed an integrated approach for dispatching, conflict-free routing and scheduling of AGVs in a flexible manufacturing system. Their proposed algorithm is based on dynamic programming on a rolling time horizon, which considers the three preceding steps for an AGV system composed of two bidirectional AGVs and the formalised problem is solved optimally. Langevin et al. [7] developed a hybrid approach for dispatching and conflict-free routing of automated guided vehicles. Their proposed approach combines a constraint programming model for the assignment of requests to the vehicles with their actual pick-up or delivery times (in order to minimise the delays) and a mixed integer-programming model for routing without conflict. Rajotia et al. [8] propose a semi-dynamic time-window constraints routing strategy, whose principle is closely similar to the path planning method of Kim et al. Indeed, a set of reserved time-windows is placed on nodes indicating the sequential crossing of nodes by vehicles. Similarly, time-windows modelling the traffic-flow direction are

S. Maza, P. Castagna / Computers in Industry 56 (2005) 719–733

placed on the bi-directional arcs, which can only be crossed according to one direction at a time. Based on these time-windows, Dijkstra’s algorithm is applied to find the least congested fastest routes for vehicles. Thomas and Wenger [9] address the optimisation of multiple mobile robots’ trajectory in an industrial world. For each mobile robot, a shortest path is calculated first without considering other mobile robots. Then, the motion planning system generates velocity laws for each vehicle in order to avoid collisions. In Oboth et al. [10] the operational control factors such as the demand selection and assignment, the route planning, and the idle AGV positioning are addressed. The authors propose a route generation procedure called the sequential path generation (SPG) heuristic, similar to the methodology developed in Krishnamurthy et al. [5] while relaxing some of the limiting assumptions like equal and constant speeds. The predictive methods have multiple objective functions and constraints, and examine all the possible routes to minimize the travel time and avoid conflicts and traffic congestion. In fact, these methods use the complete information about the network in order to make the routing decisions. Thus, they can select the optimal path. The major drawback of such approaches is that they are open-loop control strategies: once a decision is made and a vehicle is on its way, if for some reason it fails to meet its scheduled arrivals or departures, then the conflict-free schedule becomes invalid. The real-time changes in the system state are not considered. 2.2. The real-time or deadlock avoidance methods Unlike the first category, the decisions are taken on line, considering the system state. The AGV’s path is not planned; the deadlocks are avoided by looking forward during the AGV’s travel. The guide-path is divided into disjoint zones, and different algorithms are proposed to control access of the AGVs to these zones. Reveliotis [2] models the AGVS as a resource allocation system (RAS) and provides an efficient method based on Banker’s algorithm (see [11]) to avoid deadlocks. A zone control technique is considered in Pia Fanti [12] and different algorithms to make the AGVs’ path assignments and move from one zone to another in real-time. Some theoretical results in the context of deadlock in AMSs are first

721

stated, and then applied in the AGVS’ context. Moorthy et al. [13] develop an efficient AGV deadlock prediction and avoidance method for a large scale AGVS. They propose two algorithms to detect cyclic deadlocks (a one-zone and two-zone step deadlock prediction). Their algorithms are computationally efficient and have been applied in an industrial environment with a complex layout and 80 AGVs. Ying-Chin [14] considers the problem of deadlocks and vehicle collision prevention in a single-loop guide-path, divided into zones. Each zone is served by at most one AGVat a time. The proposed strategy does not only prevent the collision of vehicles but also avoids the disadvantage of fixed-zone strategies, such as the load imbalance between vehicles. Ling and Wen-Jing [15] allow the simultaneous routing of two sets of vehicles into opposite directions on a guidepath comprised of two parallel lanes and bridges that connect these two lanes at the workstations. All of the pickup/delivery jobs are classified into two nonoverlapping groups based on the positions of their pickup and drop-off stations. Correspondingly, AGVs are divided into two arrays to serve each job group, and each array is routed on one lane to avoid conflicts. Taghaboni-Dutta and Tanchoco [16] proposed a dynamic approach for routing AGVs in a multiplelane unidirectional AGV system. The authors develop an algorithm for an incremental route planner for AGVs. The next node to be crossed by a vehicle is selected by the algorithm so that it minimises the travel time, which is estimated according to the traffic intensity on that node and its neighbouring nodes. These methods are closed-loop control strategies. They have the advantage of being more reactive to the system’s changes, and thus are very robust, since the decision made is for the next node or zone only. They are also less restrictive than the planning methods since the vehicles’ displacements are more flexible. The disadvantage of deadlock avoidance methods is that the system’s performance is not optimised a priori. In fact, the process of selecting the next node or zone to be crossed, disregards completely the optimality of the complete way used to reach the destination. The objective of the present paper is to jointly use these two types of methods, in order to get the benefits of both. We propose a strategy based on an efficient path-planning method supplemented by a real-time control module. This one is used to cover the deadlocks

722

S. Maza, P. Castagna / Computers in Industry 56 (2005) 719–733

Fig. 1. Illustrative example of nodes’ time reservation table.

that may happen when the system’s behaviour deviates from the predicted one. The strategy used in this approach consists in remaining close to the initial solution that optimises a performance criterion (here, the mission duration of an AGV).

3. The conflict-free shortest-time AGV path planning 3.1. Description of the method Kim and Tanchoco [3] proposed a strongly polynomial procedure to find the fastest conflict-free path to send an AGV from a source location to another one on the guide-path. This route does not disrupt the scheduled moves of the other AGVs. The procedure (called the conflict-free shortest time procedure or cfstp), is developed based on the Dijkstra’s algorithm. The workstations, docking stations and intersections of the guide-path are modelled by square areas (safety areas) of size at least equal to that of the vehicles. These areas are called nodes. A node is considered as a nonsharable resource, which can be allocated to only one AGV at a time. A table modelling the current traffic state, i.e., the entry and exit times of vehicles at each node, is then set up according to AGVs scheduled trips. Each AGV reserves some nodes on its path during an interval of time called reserved time-window. The free time-windows between the reserved ones are available for scheduling other vehicles’ crossing.

We illustrate the method in the example presented in (Fig. 1). The notations are as follows: rij is the jth reserved time-window associated to the node i, flk is the kth free time-window associated to the node 1. The example of Fig. 1 shows the routes of two AGVs: V1 according to nodes 5, 4 and 1 (the resulting time-reserved windows are respectively r51, r42 and r11 ), and V2 according to nodes 3 and 4 (i.e., the reserved time-windows r31 and r41 ). The AGV V3 is to be routed from the source node 6 to the destination node 2 while avoiding conflicts with V1 and V2 according to the preceding table. The cfstp is used to find the shortest path, between the source free time-window f21 to the destination free time-window f61, on a graph where the vertices are the free time-windows. The links of that graph model the reachability between these time-windows (Fig. 2). The ability to reach a time-window from another one is established by calling another algorithm called the reachability test procedure. For two free timewindows fnp and fmq , associated respectively to nodes n and m, the reachability test procedure makes the following reachability tests between them: 1. Check for space feasibility, i.e., the existence of a physical link relating m to n.

S. Maza, P. Castagna / Computers in Industry 56 (2005) 719–733

723

vehicles at n and m (Fig. 3). If this order is reversed, then a conflict may occur on [n, m].

Fig. 2. The conflict-free shortest path of V3 on the time-window graph based on table of Fig. 1.

2. Check for time feasibility, i.e., the node m is reachable from the node n within its free timewindow fmq. 3. Check for potential conflicts. There are two types of conflicts in lanes: the head-on conflict and the catching-up conflict. The conflicts between two AGVs on a lane [n, m] are detected by comparing the order of the time reservation node of these

The preceding condition is expressed as follows: for each link [n, m] and each couple of vehicles V1 and V2 having to cross the lane [n, m], let tn(V1) and tm(V1) (respectively tn(V2) and tm(V2)) be the arrival dates of the vehicle V1 (respectively V2) to the nodes n and m, respectively. D denotes the time for a vehicle to cross a node and is the same for all the AGVs. The head-on and catching-up conflicts between V1 and V2 are avoided if and only if (Fig. 4): tm ðV1 Þ þ D tm ðV2 Þ and

tn ðV1 Þ þ D tn ðV2 Þ (1)

or tm ðV2 Þ þ D tm ðV1 Þ and

tn ðV2 Þ þ D tn ðV1 Þ (2)

Fig. 3. The search for potential conflicts: (a) head-on conflict; (b) catching-up conflict.

Fig. 4. The necessary and sufficient condition for conflict avoidance: (a) head-on conflict avoidance; (b) catching-up conflict avoidance.

724

S. Maza, P. Castagna / Computers in Industry 56 (2005) 719–733

which means that the link [n, m] should be first crossed by V1 and then by V2 (Eq. (1)) or by V2 first and then V1 (Eq. (2)).

Our objective is to make this planning method insensitive to the system uncertainties, particularly those introducing short delays, and therefore more robust.

3.2. Discussion 4. The robust AGV routing The time-windows path planning method presented above is effective since it gives the fastest conflict-free path by considering the previously established plans. The cfstp has a polynomial computation complexity o(V4N2), where V is the fleet size and N is the number of nodes. Nevertheless, it has a major drawback: it is not robust since it is based on a deterministic timing of the vehicle’s travelling. The disturbances are random phenomena such as technical hitches, slowing down in front of unforeseen obstacles (for example human operators crossing the AGVs’ paths), breaking down of some vehicles, etc. As seen before, the cfstp algorithm calculates for each AGV the nodes to be visited together with their arrival times. When the system is subject to random events, these arrival dates will not be fulfilled, and a shift will be introduced between the predicted time-windows and the realized ones (see Fig. 5). If no action is undertaken, this will result in collisions. For example, consider the time reservation table for three vehicles V1–V3 after routing V3 as explained in the previous example (Fig. 1). Now, suppose that the vehicle V3 undergoes a delay on the link between nodes n4 and n1. The realized reserved time-window will be different from the predicted one (Fig. 5). It can be seen that if the other vehicles (i.e., V1 and V2) respect the established arrival dates to the nodes, a conflict may occur on node n4, since two AGVs (here V1 and V3) are trying to reserve this node at the same time.

As seen before, conflicts may occur if the scheduled arrival or departure dates are not fulfilled because of the unpredictable disturbances. To avoid this situation while keeping the scheduled routes, we add a second level of real-time control. The cfstp algorithm is used in the first control level, called the scheduling level, to establish the arrival dates to the nodes that ensure vehicles safety. According to these dates and for each node ‘‘i’’, an ordered list Oi of vehicles having to cross node ‘‘i’’ is established. The AGV of lower rank in this list (i.e., having the earliest arrival date) is said to be the more priority vehicle to cross the considered node. We have identified a simple property that provides a sufficient condition to avoid conflict. It is presented in the following theorem: Theorem 1. If the node’s crossing order of the AGVs, based on the conflict-free scheduled dates, is fulfilled, then the absence of conflict is guarantied even if the arrival dates are not. Proof of theorem 1. Let consider the case of head-on conflict to prove the theorem. Suppose that AGV U has been planned to enter the nodes n and m (and goes from n to m) at tn(U) and tm(U) respectively, and AGV V is planned to cross the nodes n and m (and goes from m to n) at tn(V) and tm(V), respectively, where tn ðUÞ þ D tn ðVÞ

and tm ðUÞ þ D tm ðVÞ

(3)

These predicted nodes’ arrival dates guarantee the absence of conflict (see Eqs. (1) and (2)). If the AGV U undergoes a delay, of a duration equal to t, to arrive to node n, then its effective arrival date to that node (noted ¯tn ðUÞ) will be different from the predicted one: ¯tn ðUÞ ¼ tn ðUÞ þ t

Fig. 5. An example of a conflict situation in presence of random phenomena.

and ¯tm ðUÞ ¼ tm ðUÞ þ t 0

(4)

where t0 = t + d and d is the delay that AGV U can also undergo when crossing the lane [n, m]. If the AGV V arrives at node m at the predicted date (i.e., ¯tm ðVÞ ¼ tm ðVÞ), maintaining its travel schedule

S. Maza, P. Castagna / Computers in Industry 56 (2005) 719–733

725

may cause a conflict since condition (3) which guarantees a conflict-free cross of the link [n, m] may be violated. If the AGV V is also delayed of t and t0 on the nodes n and m, respectively (in order to respect the predicted crossing order) then its effective arrival dates to nodes n and m are

here is to determine how the AGVs’ priorities can be modified on the predefined paths without inducing conflicts. We propose an algorithm for re-ordering the AGVs on their nodes. In the following, the late AGV is referred to as U and the AGV requesting a route adjustment is referred to as V. First, we define an unsafe state in our study.

¯tn ðVÞ ¼ tn ðVÞ þ t > tn ðVÞ and ¯tm ðVÞ ¼ tm ðVÞ þ t 0

Definition 1. An unsafe state is a state, which can generate a conflict, i.e., it satisfies the necessary condition for the occurrence of conflicts.

(5)

In the other side, if we add the same amount to each side of inequalities (3) we will have tm ðUÞ þ D þ t tm ðVÞ þ t and tm ðUÞ þ D þ t0 tm ðVÞ þ t0

(6)

From (4)–(6), we will have ¯tn ðUÞ þ D ¯tn ðVÞ

and ¯tm ðUÞ þ D ¯tm ðVÞ

Inequalities (7) guaranty the absence of conflict.

(7) &

The role of the real-time level is to check this crossing order by performing the following task: {At each arrival to the entry of node x, if the current vehicle is the first one in Ox, then it is the most priority AGV on that node and is authorised to cross x. Otherwise, it should wait in its current edge until it becomes the first AGV in Ox}. This algorithm has a complexity of o(1). 4.1. Discussion The proposed method is efficient and allows online collision avoidance, by delaying some AGVs following the late AGV. This is possible just by respecting the established nodes crossing order (or priorities). However, if a vehicle U undergoes a delay of significant duration, other operational vehicles will be delayed to respect the predicted order. Consequently, there may be a propagation of this delay.

5. The improved robust AGV routing by use of dynamic priorities The strict respect of the node’s crossing order implies fixed or static priorities for AGVs. This may lead to unnecessary delays. The question addressed

From Sections 3 and 4, the necessary condition for the occurrence of conflict between two AGVs on two nodes related by a link is an inverted priority on those nodes. These priorities will be qualified as conflicting priorities. 5.1. The improved robust routing by advancing the actual AGV ahead other vehicles The waste of time in waiting for the late AGV can be avoided by applying the following procedure: when AGV V arrives at a node N which is planned to be crossed by some other late AGV, U, we consider the possibility of granting V the highest priority on that node and other nodes on its track. This is done by checking if this action would lead to conflicts. We propose an algorithm RVRAA which gives the AGV V the highest priority for each node on the track [N, M] (when possible), where M is the node where V has priority and N is the node where RVRAA is called. This strategy applied to the example below (Fig. 6(a)) will lead to the node’s crossing order situation represented in Fig. 6(b). The RVRAA algorithm is based on the following theorem. Theorem 2. A vehicle V can inherit the greatest priority on the nodes of path [N, M] without inducing conflicting priorities, if and only if all the vehicles having to cross this path before V are outside the path [N, M]. Remark. In Theorem 2, it is understood that the path [N, M] is initially conflict free. Proof of theorem 2. To demonstrate the necessity of the preceding condition, we will show that if it is not

726

S. Maza, P. Castagna / Computers in Industry 56 (2005) 719–733

Fig. 6. Example of the use of the advance algorithm RVRAA: (a) the vehicles’ priorities before the re-ordering; (b) the vehicles’ priorities after the use of the RVRAA.

Fig. 7. Example of a re-ordering causing an unsafe state: (a) compatible priorities before the re-ordering; (b) conflict priorities after the reordering.

satisfied, then a conflict may occur on [N, M]. That is if one AGV with a higher priority than Von some node in the track [N, M] is between the nodes N and M, then the re-ordering will induce an unsafe state. Suppose that one AGV, say U, is on the link [n1, n2] where n1, n2 2 ]N, M] and is going toward the node n2. It means that U has a higher priority than V on nodes n1, n2 (Fig. 7(a)). Note in Fig. 6 that the lower vehicle in the vector has a higher priority. If vehicle V is placed ahead of vehicle U over the track [N, M], conflicting priorities may result on the link [n1, n2] (Fig. 7(b)). In fact, since U has already crossed n1, it is too late to change the node’s crossing order there. Consequently, a conflict may result if this action is done on the next node n2. The sufficiency of this condition can be easily proven. & 5.2. The robust vehicle’s routing ahead algorithm (RVRAA) Notations: N is the node where the robust routing procedure is called. It is the first common node between the actual vehicle V and the other late AGVs.

Vn(k) denotes the kth vehicle having to cross the node n. LV(i) denotes the ith link to be visited by AGV V. NV(i) denotes the ith node to be visited by AGV V. V denotes the AGV which initiates the RVRAA at the node N. P denotes the set of the predecessors of the vehicle V on the nodes belonging to the path [N, M[to be determined by the RVRAA. BEGIN A. *This part calculates the track [N, M[ and checks for the feasibility of the advance action of V on it* P = 1, Permission = 1. NV(j) is the node N where V is not the first AGV in ON (it will be noted n for simplicity). L = LV(i) is the link to be crossed by V immediately after the node n. WHILE Vn(1) 6¼ V (i.e., V has not priority on n) DO { p = p [ {Vx/Vx are predecessors of V on the node n} IF the link L or the node n are occupied by any vehicle in the set P THEN

S. Maza, P. Castagna / Computers in Industry 56 (2005) 719–733 The advance action of V is prohibited since a conflict may result Permission = 0, RETURN ELSE n = NV(j + 1) L = LV(i + 1) ENDIF} M = n is the node where V has the highest priority (i.e., VM(1) = V) B. **The advance action of the vehicle V over other AGVs on the track [N, M[** IF Permission = 1 THEN FOR all the nodes belonging to the path [N, M[, the vehicle V will be attributed the highest priority and will be placed at the first rank on their associated lists. ENDIF END

5.2.1. Additional explanation When an AGV Varrives at a node NV(j) where it has not priority, the RVRAA will be called. P is the set of vehicles having to cross NV(j) before V, i.e., vehicles having a higher priority than V. LV(i) denotes the next link to be visited by the vehicle V after crossing NV(j). If this link is actually used by any vehicle in P, vehicle V must wait in its position. Indeed, if V is advanced on the node NV(j), it may collide with the AGVoccupying its next link. However, if this link is unoccupied, we repeat the same procedure for the next node NV(j + 1) and link LV(i + 1) to be visited by V after NV(j + 1). This action is done until a node M where VM(1) = V is found, i.e., the node where V has the highest priority. Then, we can proceed to the update of each list Oi of nodes i 2 [N, M[. The actual vehicle V will be placed at the head of Oi in front of other vehicles, and thus, will inherit of the greatest priority on that path. If no such node M exists, i.e., from the actual node NV(j) to the destination node of V, all the nodes must be crossed first by the other vehicles then by V, hence the AGV V will not be advanced. It will wait at the entry of NV(j) until it becomes the most priority. Indeed, if D denotes

727

the destination node of V, placing V at the first position of OD, will disrupt other vehicles having to cross the node D especially if the vehicle V cannot be routed immediately after. Note that the advance action of the preceding algorithm is not only done on the node N that AGV V tries to cross immediately, but is extended to the path [N, M], otherwise, conflicting priorities may result. 5.3. The computational complexity Let NVn be the number of AGVs having to cross the node n (NVn is the length of the sequence On), h is the number of nodes in the guide-path, and n is the fleet size. The computational burden of RVRAA is dominated by step A, where the path [N, M] and set P are calculated. The calculation of the set P can be done in NVn steps. The number of times the outer-loop executes is equal to the maximum number of nodes DL to be visited by an AGV to reach its destination node. Thus, the algorithm has the complexity of o(NVnDL). 5.3.1. Estimation of NVn and DL in the worst case The maximum number of times that an AGV can cross a node is equal to n, when it makes n releases of the node n in front of other AGVs. The first AGV in the ordered list On can cross n times the node n, the second AGV (n 1) times, the third AGV (n 2), and so on, i.e., a node n can be crossed n(n 1)/2 in the worst case, so NVn n2. Notice that the worst situation is very singular and exceptional. If we consider that in one mission, an AGV can cross all the nodes of the guide-path (in the worst case) and knowing that it can cross one node n times, the maximum number of displacements in a mission is equal in the worst case to DL = hn. As a conclusion, the complexity of the RVRAA is equal to o(hn3).

6. The simulation study We have used the ARENA software to develop a template panel, which allows us to model the routing of bi-directional AGVs. This function is actually not included in the ARENA package. The template also allows the modelling of real AGVSs, subject to contingencies and the collision avoidance between AGVs is done using our hierarchical routing strategy.

728

S. Maza, P. Castagna / Computers in Industry 56 (2005) 719–733

Fig. 8. The description of the template panel for robust routing of bi-directional AGVs.

6.1. The description of the template panel for bidirectional AGVS Our template is composed of four objects families (see Fig. 8): (a) The ‘‘node object’’ family: It allows the definition of different types of nodes that can join from one to four links (Fig. 9). Each node is composed of one principal intersection (represented by a full black circle) and secondary intersections that delimit the node around the principal one. These intersections are

Fig. 9. The ‘‘node object’’.

used for a temporary stop of AGVs in order to avoid collisions. Each node has a waiting priority queue to hold a number of entities describing the vehicles having to cross that node. These entities are characterized by two attributes: the first one gives the AGV number, while the second one gives its priority (or its arrival date). The priorities are assigned based on the arrival dates of vehicles, i.e., the highest priority is allocated to the AGV with the shortest predicted arrival date. (b) The ‘‘link object’’ family: Each link makes a connection between two nodes and is bi-directional. This object allows the definition of the link length. (c) The ‘‘control centre object’’: The control centre integrates the logical model allowing the sequencing of missions and the conflict avoidance strategy. It allows also the dispatch of AGVs into their garages when their missions are impossible as explained below. A garage is defined as a terminal node connected to the rest of the network by a single link. A vehicle’s garage cannot be a destination node for other vehicles. We try to plan the

S. Maza, P. Castagna / Computers in Industry 56 (2005) 719–733

missions of all the free vehicles. A mission of an AGV can be impossible when this one is blocked by another AGV, which is on its way. Indeed, the cfstp algorithm of Kim and Tanchoco [3] considers only one AGV at a time and delivers an infinite reserved time-window for each AGV’s destination node. This can cause deadlocks. When an AGV is blocked, we try to schedule another free AGV and then, we try again to schedule the blocked one. This action is repeated until all the free vehicles are scheduled or become blocked. We can have a cyclic deadlock, when each free AGV has a destination occupied by another blocked AGV. In that case, the unscheduled AGVs are sent to their garages, to avoid occupying a node unnecessarily, and obstructing other AGVs. The ‘‘control centre object’’ allows the choice of the robust algorithm to be used by the ‘‘vehicle object’’, as well as the definition of the failures parameters.

729

The conflict free-path planning procedure (cfstp) and the robust algorithm RVRAA are programs written into VBA language (Visual Basic For Application1). (d) The ‘‘vehicle object’’: Each AGVof the fleet is described by an object ‘‘vehicle’’, which includes the logical model allowing the execution of elementary displacements (i.e., a move between two neighbouring nodes). The logical structure of this object is described in Fig. 10. When a transport mission is planned in the ‘‘control centre object’’, this object creates a set of entities describing the elementary displacements for the mission of the considered vehicle. These entities are accumulated in the queue of elementary displacements of the considered AGV (see bloc (1) of Fig. 10) and are characterized by two attributes. One attribute gives the node to be visited, the other one its corresponding entry time

Fig. 10. The structural logic of the ‘‘vehicle object’’.

730

S. Maza, P. Castagna / Computers in Industry 56 (2005) 719–733

calculated by the cfstp. Blocs 2–4 allow the move of AGV into the entry of the next node to be visited, and the wait of the AGV for the entry time. The robust procedures are used in bloc 5 to check for the possibility to enter a node. If so, the AGV proceed to the cross of that node to occupy it in its principal intersection (bloc 6). Then, the set of time-reserved windows is updated (bloc 7). The logical model of the ‘‘vehicle object’’ contains also the vehicle’s garages and the failures generator as described below. To check for the efficiency of the robust routing strategies proposed in this paper, a simulation model of a manufacturing system has been constructed with the ARENA package of Rockwell Software. 6.2. The description of the simulation model The manufacturing system used in simulation has a fleet of eight AGVs moving on a bi-directional guidepath, composed of 45 nodes and 60 links. A random missions generator delivers for each AGV, 100 missions to be realized. There are as many garages as the fleet size. They are defined as external nodes related to the guide-path by a single link. We construct two simulation models describing a perfect system and a system subject to contingencies. For the second model, we trigger vehicle’s breakdowns at random times. We use three parameters to describe the AGVs’ interruptions: (1) the mean time between failures MTBF, (2) the mean time to repair MTTR, and (3) the variability V on MTBF and MTTR. The time between failures, TBF, and the time to repair, TR, are characterised by a uniform distribution law as follows: TBF ¼ UniformððMTBF MTTRÞ ð1 VÞ; ðMTBF MTTRÞð1 þ VÞÞ and TR ¼ UniformðMTTRð1 VÞ; MTTRð1 þ VÞÞ Consequently, we impose a failure rate of average: t = MTTR/MTBF. Different simulations are done with various system parameters in order to compare the preceding algorithms and bring out the situations where the use of one algorithm is more appropriate than another.

6.3. The simulation results 6.3.1. The influence of the failure rate variations The simulations are conducted using six different failure rates. For a given failure rate value, a relevant way to compare the results of each algorithm is to carry out many replications (10 in our case), while measuring the makespan and the missions duration. Instead of comparing directly these amounts, we calculate their average and their confidence interval along these replications, and then we compare. The results obtained about the system’s makespan and AGVs’ missions duration are summed up in Table 1 and their associated bar charts are reported in Fig. 11. The gain on the total makespan (respectively the AGVs’ mission duration) realized with RVRAA increases according to the failure rate. For example, when t = 20%, the gain in the total makespan of the RVRAA is of 6.78%, and it is of 10% when t = 40%. This is due to the fact that the RVWA wastes much time waiting for the late AGVs in order to respect the nodes’ crossing order. However, the RVRAA makes a local re-scheduling each time a vehicle is late and whenever it is possible. 6.3.2. The influence of the MTBF variations The objective of this part is to study the influence of the failures’ characteristics on the performances realized by our algorithms. The failure rate has been fixed to 20%, and simulations are done for three different values of MTBF. We try to compare two cases of AGVS: one with many short failures and the other one with few long failures. The obtained results with their confidence indices are summarized in Table 2. Table 1 The simulation results The failure rate (%)

0 5 10 20 30 40

The average on the total makespan

The average on AGVs’ missions-duration

RVWA

RVRAA

RVWA

RVRAA

9115.4 9790.7 10737 14067 19305 27581

9115.4 9660.1 10518 13113 17737 24815

80 85.904 94.516 122.8 168.41 247.23

80 84.773 93.101 116.32 156.12 217.28

S. Maza, P. Castagna / Computers in Industry 56 (2005) 719–733

731

Fig. 11. The evolution of the performances ratios according to the failure rates: (a) the average of the total makespan; (b) the average of the AGV’s mission duration.

GT = 0.2% but with a small confidence index. In this last case, the RVWA gives better results. A first conclusion that can be drawn from these results is: the more the failures are long and spaced in time, better will be the results obtained by the RVRAA in comparison to RVWA. When the failures happen frequently and are of short duration, the preceding algorithms behave similarly. When the failures are frequent and short, they are mutually compensated, and the delays generated by the RVWA are less important. The second conclusion is that for a reliable enough AGVS with frequent and short failures (for example, an AGVS where there is great number of staff), the RVWA (whose complexity is equal to o(1)) can be used to avoid conflicts on line while maintaining the established routes.

In this table, NS means Non-Significant according their confidence interval, and Dm ðrvwaÞ Dm ðrvraaÞ ; Dm ðrvwaÞ DT ðrvwaÞ DT ðrvraaÞ GT ¼ DT ðrvwaÞ

Gm ¼

where Dm(X) is the mission duration and DT(X) is the total makespan realized with the algorithm X. The algorithms are compared by calculating the gain with a certain confidence index, as mentioned before. We can observe that the gain given by the RVRAA is proportional to the MTBF parameter. In fact, for example for MTBF = 300, we have GT = 3.8%, while for MTBF = 150, GT = 1.7%, and for MTBF = 75%, Table 2 Simulation results for t = 20% and various DIP Gain on the mission duration Gm (%) DIP = 300

Confidence index

DIP = 150

Gain on the makespan GT (%) DIP = 75

DIP = 300

DIP = 150

DIP = 75

3.1%

1.8%

0.2%

3.8%

1.7%

0.2%

0.99

0.99

NS

0.99

0.95

NS

Table 3 Simulation results for t = 20% and various fleet sizes n Gain on the mission duration Gm (%) n=8

Confidence index

n=5

Gain on the makespan GT (%) n=3

n=8

n=5

n=3

3.1%

2.4%

0.6%

3.8%

1.9%

0.9%

0.99

0.95

0.75

0.99

0.85

NS

732

S. Maza, P. Castagna / Computers in Industry 56 (2005) 719–733

6.3.3. The influence of the fleet size The simulations are conducted for a fixed failure rate of 20%, with three different fleet sizes. The results are given in Table 3. These results show that the gain obtained with RVRAA is as much important as the fleet size is. In fact, for example with eight AGVs, the gain on the makespan obtained by the RVRAA is of 3.1%, while it is only of 2.4% with five AGVs, and 0.6% with three AGVs. This result is predictable, since when there is a small number of AGVs on the guide-path, the probability of having common paths is little. Consequently, the reordering algorithm (RVRAA) is less useful. We also have the following remark: smaller is the fleet size, the success rate of RVRAA is more important. In fact, with three AGVs, the success rate of RVRAA is equal to 55%, while for five AGVs, it is equal to 33% and for eight AGVs it is equal to 25%. Indeed, there is more chances for the node M to exist when the fleet is small than when it is important, which implies a greater success rate of the algorithm.

7. Conclusion In this paper, a two-stage robust control for conflictfree routing of bi-directional AGVs has been presented. In order to combine the advantages of the planning and real-time methods, we use in the first stage an efficient method for path planning to establish the conflict-free fastest routes for AGVs. However, two algorithms called RVWA and RVRAA are used in the second stage to solve conflicts in real-time. Some theoretical results about conflict avoidance are given. The simulations carried out allowed us to study the efficiency of the preceding algorithms as well as the influence of certain parameters on the realized performances. By fixing all the parameters (guide-path, fleet size, and characteristics of failures) and varying the failure rate, we can conclude that the higher is the failure rate, the higher are the gains brought by RVRAA. We have also studied the influence of failure frequency on the efficiency of our algorithms. We concluded that for short and frequent failures, the two algorithms have the same behaviour, which means that it is more appropriate to use the simplest one, i.e., RVWA. Finally, when there is great number of AGVs, the use of the re-ordering algorithm is more justified,

since the obtained results are better than those of RVWA. Currently, we are working on another re-ordering algorithm, which penalises the late AGV by delaying it in front of some vehicles on some nodes, to allow them crossing these nodes [17]. This algorithm is more complicated than RVRAA but less restrictive, since there is no constraining condition concerned with the existence of the node M. The re-ordering will be possible even if such a node does not exist.

References [1] P.J. Egbelu, J.M.A. Tanchoco, Potentials for bi-directional guide-path for automated guided vehicle based systems, International Journal of Production Research 24 (5) (1986) 1075– 1097. [2] S.A. Reveliotis, Conflict resolution in AGV systems, IIE Transactions 32 (7) (2000) 647–659. [3] C.W. Kim, J.M.A. Tanchoco, Conflict-free shortest-time bidirectional AGV routing, International Journal of Production Research 29 (12) (1991) 2377–2391. [4] C.W. Kim, J.M.A. Tanchoco, Operational control of bi-directional AGV system, International Journal of Production Research 31 (9) (1993) 2123–2138. [5] N.N. Krishnamurthy, R. Batta, H. Karwan, Developing conflict-free routes for automated guided vehicles, Operations Research 41 (6) (1993) 1077–1090. [6] A. Langevin, D. Lauzon, D. Riopel, Dispatching, routing, and scheduling of two automated guided vehicles in a flexible manufacturing system, The International Journal of Flexible Manufacturing Systems 8 (1996) 247–262. [7] A. Langevin, A.I. Corre´ a, L.-M. Rousseau, Dispatching and conflict-free routing of automated guided vehicles: a hybrid approach combining constraint programming and mixed integer programming, Les cahiers du GERAD, 2004, G-2004-21. [8] S. Rajotia, K. Shanker, J.L. Batra, A semi-dynamic time-window constrained routeing strategy in an AGV system, International Journal of Production Research 36 (1) (1998) 35–50. [9] H. Thomas, P. Wenger, On planning velocities and trajectories for multiple mobile robots, in: Proceedings of the Sixth Topical Meeting on Robotics and Remote Systems, Monterey, CA, 1995. [10] C. Oboth, R. Batta, M. Karwan, Dynamic conflict-free routing of automated guided vehicles, International Journal of Production Research 37 (9) (1999) 2003–2030. [11] A. Silberschatz, J.L. Peterson, Operating system concepts, Addison Wesley, 1988. [12] M. Pia Fanti, Event-based controller to avoid deadlock and collisions in zone-control AGVS, International Journal of Production Research 40 (6) (2002) 1453–1478. [13] R.L. Moorthy, W. Hock-Guan, N. Wing-Cheong, T. ChungPiaw, Cyclic deadlock prediction and avoidance for zonecontrolled AGV system, International Journal of Production Economics 83 (3) (2003) 309–324.

S. Maza, P. Castagna / Computers in Industry 56 (2005) 719–733 [14] H. Ying-Chin, A dynamic-zone strategy for vehicle-collision prevention and load balancing in an AGV system with a singleloop guide-path, Computers in Industry 42 (3) (2000) 159–176. [15] Q. Ling, H. Wen-Jing, A bi-directional path layout for conflictfree routing of AGVs, International Journal of Production Research 39 (10) (2001) 2177–2195. [16] F. Taghaboni-Dutta, J.M.A. Tanchoco, Comparison of dynamic routing techniques for automated guided vehicle system, International Journal of Production Research 33 (10) (1995) 2653–2669. [17] S. Maza, P. Castagna, Sequence-based hierarchical conflictfree routing strategy of bi-directional automated guided vehicles, in: Proceedings of the 16th IFAC World Congress, July 2005, Czech Republic. Dr. Samia Maza is an assistant professor at the university of Nantes. She is a member of Institut de Recherche en Communications et Cyberne´ tique de Nantes, France. She holds an Automatic control engineer diploma from the national polytechnic school of Algiers (Algeria), and has defended her PhD thesis on ‘‘Robust Routing of a Fleet of Bi-directional AGVs’’ in 2003 at the University of

733

Nantes (France). Her current research interests include the modelling and control of complex discrete event systems and transfer systems and the simulation of manufacturing systems. Dr. Pierre Castagna is a professor at the University of Nantes, in industrial engineering. He is a member of Institut de Recherche en Communications et Cyberne´ tique de Nantes. After attending an initial education in mechanic and automatic, he worked on formalism for specification of simulation models, distributed simulation, discrete event simulation and transfer system design. In 2004, he defended the ‘‘Habilitation a` diriger des recherches’’ in Industrial Engineering at the University of Nantes. He has been a scientific manager of more than 30 research contracts (with AIRBUS, TRELLEBORG, SOCCATA, etc.).