Decentralized management of intersections of automated guided vehicles

Decentralized management of intersections of automated guided vehicles

IFAC Conference on Manufacturing Modelling, IFAC Conference Manufacturing Modelling, IFAC Conference on Manufacturing Management and on Control IFAC C...

779KB Sizes 0 Downloads 19 Views

IFAC Conference on Manufacturing Modelling, IFAC Conference Manufacturing Modelling, IFAC Conference on Manufacturing Management and on Control IFAC Conference on Manufacturing Modelling, Modelling, Management and Control Available online at www.sciencedirect.com Management and Control June 28-30, 2016. Troyes, France Management and Control June 28-30, 2016. Troyes, France June June 28-30, 28-30, 2016. 2016. Troyes, Troyes, France France

ScienceDirect

IFAC-PapersOnLine 49-12 (2016) 497–502

Decentralized management of intersections Decentralized management of intersections Decentralized management of intersections Decentralized management of intersections of automated guided vehicles of automated guided vehicles of automated guided vehicles of automated guided vehicles

Alexandre Lombard ∗∗ Florent Perronnet ∗∗ ∗∗ ∗∗Florent Perronnet ∗∗ ∗ Alexandre Lombard ∗ Florent ∗∗ Alexandre Lombard Perronnet Abdeljalil Abbas-Turki Abdellah El Moudni Alexandre Lombard Perronnet ∗Florent ∗ ∗ Abdellah El Moudni ∗ Abdeljalil Abbas-Turki ∗ Abdellah El Moudni ∗ Abdeljalil Abbas-Turki Abdeljalil Abbas-Turki Abdellah El Moudni ∗ e de Technologie de Belfort-Montb´eliard ∗ IRTES-SeT, Universit´ ∗ IRTES-SeT, Universit´ e de Technologie de Belfort-Montb´ ∗ IRTES-SeT, Universit´ de Belfort-Montb´eeliard liard France de IRTES-SeT, Universit´eeBelfort, de Technologie Technologie Belfort, France de Belfort-Montb´eliard ∗∗ Belfort, France Belfort, France Belfort, France ∗∗ Voxelia, ∗∗ Voxelia, Belfort, France ∗∗ Voxelia, Belfort, France Voxelia, Belfort, France Abstract: The emerging topic of cooperative intersection management for vehicles has raised Abstract: The emerging topic of cooperative intersection management for vehicles has raised Abstract: The of management for vehicles has up new solutions for traffictopic control in order tointersection avoid collisions, deadlocks, and improve traffic Abstract: The emerging emerging topic of cooperative cooperative intersection management forand vehicles has raised raised up new solutions for traffic control in order to avoid collisions, deadlocks, improve traffic up new solutions for traffic control in order to avoid collisions, deadlocks, and improve traffic efficiency. The solutions developed for road traffic can easily be applied to automated guided up new solutions for traffic control for in order to avoid improve guided traffic efficiency. The solutions solutions developed road traffic traffic cancollisions, easily be bedeadlocks, applied to toand automated efficiency. developed for can applied guided vehicles toThe overcome the common drawbacks, and improve the be number of vehicles in a network. efficiency. The solutions developeddrawbacks, for road road traffic can easily easily applied to automated automated guided vehicles to overcome the common and improve the number of vehicles in a network. vehicles to the drawbacks, and the of network. In the context of a network of vehicles only regulated at intersections, we propose in anaaalgorithm vehicles to overcome overcome the common common drawbacks, and improve improve the number number we of vehicles vehicles in network. In the context of a network of vehicles only regulated at intersections, propose an algorithm In the context of a network of vehicles only regulated at intersections, we propose an algorithm in order to prevent deadlock at intersections in a network of automated guided vehicles. In the context of a network of vehicles only regulated at intersections, we propose an algorithm in order to prevent deadlock at intersections in aa network of automated guided vehicles. in in order order to to prevent prevent deadlock deadlock at at intersections intersections in in a network network of of automated automated guided guided vehicles. vehicles. © 2016, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved. Keywords: automated guided vehicles; cooperative intersection management; wireless Keywords: guided Keywords: automated automated guided vehicles; vehicles; cooperative cooperative intersection intersection management; management; wireless wireless communication; deadlock Keywords: automated guided vehicles; cooperative intersection management; wireless communication; deadlock communication; deadlock communication; deadlock 1. INTRODUCTION server in Dresner and Stone (2004) and de La Fortelle 1. server in Dresner and Stone (2004) and Fortelle 1. INTRODUCTION INTRODUCTION server inOther Dresner and Stone (2004) and de de La LaAdaptive Fortelle (2010).in works areStone based(2004) on Cooperative 1. INTRODUCTION server Dresner and and de La Fortelle (2010). Other works are based on Cooperative Adaptive (2010). Other works are based on Cooperative Adaptive Cruise Control at Intersections (CACCI). The server deOther works are based on Cooperative Adaptive In a network with a large number of automated guided (2010). Cruise Control at Intersections (CACCI). The server deCruise Control at Intersections (CACCI). The server In a network with a large number of automated guided tects conflicts and accordingly sends acceleration and deCruise Control at Intersections (CACCI). The server In network with large number of automated automated guided tects conflicts and accordingly sends acceleration and devehicles (AGV), traffic control is crucial to the system In aa network with aa large number of guided tects conflicts and accordingly accordingly sends acceleration and dedevehicles (AGV), traffic control is crucial to system celeration messages to vehicles sends in order to avoid collisions conflicts and acceleration and vehicles (AGV), traffic control is must crucialavoid to the the system tects performance. Thetraffic trafficcontrol controlis collisions, celeration messages to vehicles in order to avoid collisions vehicles (AGV), crucial to the system celeration messages to vehicles in order to avoid collisions performance. The traffic control must avoid collisions, in Zohdy and Rakha (2012) and Zohdy et al. (2012). Furmessages to vehicles in order et to avoid collisions performance. The traffic traffic control deadlocks/gridlocks and ensure thatmust everyavoid AGV collisions, can reach celeration Zohdy Rakha and Furperformance. The control in Zohdy aand and Rakha (2012) (2012) Protocol and Zohdy Zohdy et al. al.is (2012). (2012). Furdeadlocks/gridlocks and ensure ensure thatmust everyavoid AGV collisions, can reach reach in thermore Sequence-Based (SBP) proposed in in Zohdy and Rakha (2012) and Zohdy et al. (2012). Furdeadlocks/gridlocks and that every AGV can its destination, and for this purpose different solutions are thermore a Sequence-Based Protocol (SBP) is proposed in deadlocks/gridlocks and ensure that every AGV can reach thermore aet Sequence-Based Protocol that (SBP) is proposed proposed in its destination, and for this purpose different solutions are Perronnet al. (2013). It assumes the intersection thermore a Sequence-Based Protocol (SBP) is in its destination, and for this purpose different solutions are proposed: et al. (2013). assumes that its destination, and for this purpose different solutions are Perronnet Perronnet et as al. follows (2013).: It Iteither assumes that the the intersection intersection proposed: is controlled the intersection manager Perronnet et al. (2013). It assumes that the intersection proposed: is controlled as follows : either the intersection manager proposed: is controlled as follows : either the intersection manager • To avoid collisions, zone control with wireless trans- is or a decentralized negotiation explicitly determines the controlled as follows : either the intersection manager •• To avoid zone control with transaa decentralized negotiation explicitly determines the To avoidiscollisions, collisions, zone control withofwireless wireless trans- or or decentralized negotiation explicitly determines the mission the favorite traffic control most environsequence of vehicles in each conflict area. The sequence • To avoid collisions, zone control with wireless transa decentralized negotiation explicitly determines the mission is favorite traffic control control of of most most environ- or sequence of vehicles in conflict area. The sequence mission isitthe the favoritetotraffic sequence of which vehicles in each each conflict area. Theone sequence ments asis is simple install and expand. determinesof vehicle is conflict the first,area. which is the mission the favorite traffic control of most environenviron- sequence vehicles in each The sequence ments as it is simple to install and expand. determines which vehicle is the first, which one is the as deadlocks/gridlocks it is is simple simple to to install installinand and expand. determines which vehicle is is the the first, first, which which one one is is the the • ments To avoid the expand. network of AGV, determines second and so on. vehicle as it which •• ments To avoid deadlocks/gridlocks in the network of AGV, second and so on. To avoid deadlocks/gridlocks in the network of AGV, second and so on. the mainly used solutions are improved banker’s al• To avoid deadlocks/gridlocks in the network of AGV, so protocols on. the mainly used are banker’s al- second Thoughand these are designed for isolated intersecthe mainly used solutions solutions are improved improved banker’s algorithms (Lawley et al., 1998; Ezpeleta et al., 2002; these protocols are for isolated intersecthe mainly used solutions are improved banker’s al- Though Though these protocols are designed designed forglobal isolated intersecgorithms (Lawley et al., 1998; Ezpeleta et al., 2002; tion, they can be integrated in a more solution in Though these protocols are for isolated intersecgorithms (Lawley et al., 1998; Ezpeleta et al., 2002; Bobanac (Lawley and Bogdan, 2008), and the use of 2002; Petri tion, they can be integrateddesigned in a more global solution in gorithms et al., 1998; Ezpeleta et al., tion, they can be integrated in a more global solution ina Bobanac and Bogdan, 2008), and the use of Petri charge of managing (routing and gridlock prevention) tion, they can be integrated in a more global solution in Bobanac and Bogdan, 2008), and the use of Petri nets (Wu and Zhou, 2007), but they both suffer of (routing gridlock prevention) a Bobanac and Bogdan, 2007), 2008), and they the use of suffer Petri charge charge of managing managing (routing and and gridlock prevention) nets (Wu and fleet of vehicles, like Bocewicz et al.gridlock (2007) and Perronnetaa of managing (routing and prevention) nets (Wu and Zhou, Zhou, 2007), but but they both both suffer charge from (Wu drawbacks. The banker’s algorithm can elimifleet of vehicles, like Bocewicz et al. (2007) and Perronnet nets and Zhou, 2007), but they both suffer fleet of vehicles, like Bocewicz et al. (2007) and Perronnet from drawbacks. The banker’s algorithm can elimiet al.of(2014). For inetPerronnet et al.Perronnet (2014) a vehicles, likeinstance, Bocewiczin al. (2007)et and from drawbacks. Thesignificantly banker’s algorithm algorithm can elimieliminate valid solutions, compromising the fleet et al. For Perronnet aa from drawbacks. The banker’s can et al. (2014). (2014). For instance, instance, in gridlock Perronnet et al. al. (2014) (2014) nate valid solutions, significantly compromising the protocol is proposed to avoid (deadlock caused et al. (2014). For instance, in Perronnet et al. (2014) a nate valid solutions, significantly compromising the efficiency ofsolutions, the management, while Petri nets can protocol is proposed to avoid gridlock (deadlock caused nate valid significantly compromising the protocol is proposed proposed to avoid avoid intersections) gridlock (deadlock (deadlock caused efficiency of the management, while Petri nets can by the interaction of multiple in a network protocol is to gridlock caused efficiency of the management, while Petri nets can cause livelocks. Moreover the number of AGV in the the of intersections) in aa network network efficiency of theMoreover management, while Petri nets can by by the interaction interaction of multiple multiple intersections) in cause livelocks. the of in of intersections allowing more intersections) than one vehicle per zone the interaction of multiple in a per network cause livelocks. Moreover the number number of AGV AGV in the the by network with these solutions is limited: a resource of intersections allowing more than one vehicle zone cause livelocks. Moreover the number of AGV in the of intersections allowing more than one vehicle per zone network with these solutions is limited: a resource between intersections. This algorithm is based on the of intersections allowing more than one vehicle per zone network with these solutions is limited: a resource is an arcwith between two nodes and can only be held between intersections. This algorithm is based on the network thesetwo solutions is limited: a resource between intersections. This algorithm algorithm ishas based on the thea is an arc between nodes and can only be held principle of path reservation: a vehicle to follow between intersections. This is based on is an arc between two nodes and can only be held by an onearcAGV at a two time.nodes Otherand solutions relying on principle of path reservation: a vehicle has to follow a is between can only be held principle of itpath path reservation: vehicle hasauthorization to follow follow aa by one at Other relying on given path, asks reservation: the global server for the of aa vehicle has to by one AGV AGV deadlock at a a time. time. Other solutions solutions relying on principle siphon-based prevention are optimal but the given path, it asks the global server for the authorization by one AGV at a time. Other solutions relying on given path, it asks the global server for the authorization siphon-based deadlock prevention are optimal but the to follow this path, then the global server reserves given path, it asks the global server for the authorization siphon-based deadlock prevention are optimal but the the minimal siphon is a NP problem,are thus it cannot be to follow this path, then the global server reserves the the siphon-based deadlock prevention optimal but to follow this path, then the server reserves the minimal siphon is aa NP problem, thus it cannot be to path of thisthis vehicle and informs intersection servers. Then, follow path,and then the global global serverservers. reserves the minimal siphon is NP problem, thus it cannot be considered for real time applications. path of this vehicle informs intersection Then, minimal siphon is a NP problem, thus it cannot be path of this this vehicle and andofinforms informs intersection servers. Then, considered for real time applications. eventual intersections vehicles are locallyservers. managed by path of vehicle intersection Then, considered forrouting real time applications. • considered Conflict-freefor based solutions are also proeventual intersections of vehicles are locally managed by real time applications. eventual intersections of vehicles are locally managed by •• Conflict-free routing based solutions are also proone of the previously presented solution with respect to intersections of vehicles solution are locally managed by Conflict-free routing based(2012) solutions are also also proproposed in Nishirouting and Tanaka and Miyamoto and eventual one of the previously presented with respect to • Conflict-free based solutions are one of the previously presented solution with respect to posed in Nishi and Tanaka (2012) and Miyamoto and the constraints stated by the global protocol. one of the previously presented solution with respect to posed in Nishi they and Tanaka Tanaka (2012) and Miyamoto Miyamoto and the constraints stated by the global protocol. Inoue in (2016), prevent(2012) the intersection problem posed Nishi and and and the constraints stated by the global protocol. Inoue (2016), they prevent the intersection problem the constraints stated by the global protocol. Inoue (2016), they prevent the intersection problem but they require a centralized management, some These solutions are originally designed for road vehicles Inoue (2016), they prevent the intersectionand problem but they require aa centralized management, solutions are designed for vehicles but they requireare centralized management, and and some some These validthey solutions eliminated.management, These solutions aretooriginally originally designed for road road vehicles but require a centralized and some but cansolutions be applied AGV in order to increase the vehicles number These are originally designed for road valid solutions are eliminated. but can be applied to AGV in order to increase the number valid solutions are eliminated. but can be applied to AGV in order to increase the number valid solutions are eliminated. of AGV in a network, and improve the overall performance. but can be applied to AGV in order to increase the number Due to the recent development of cooperative intersec- of AGV in a network, and improve the overall performance. of AGV in in aainnetwork, network, and improve improve the overall overall performance. Due to development of intersecTherefore, the context of this paper, we assume a netAGV and the performance. Due to the the recent recent for development of cooperative cooperative intersection management road vehicles, new solutions have of Therefore, in the context of this paper, we assume aa netDue to the recent development of cooperative intersecTherefore, in the context of this paper, we assume nettion management for road vehicles, new solutions have work with a traffic control protocol in charge of the gridin the context ofprotocol this paper, we assume agridnettion management for traffic road vehicles, vehicles, new solutions have Therefore, emerged to improve efficiency with both colliwork with control in charge of tion management for road new solutions have work with aaa traffic traffic controlmore protocol inone charge of the the gridemerged to improve traffic efficiency with both collilock prevention allowing than vehicle between work with traffic control protocol in charge of the gridemerged to improve traffic efficiency with both collision and to deadlock One can with quoteboth the colliwell- lock prevention allowing more than one vehicle between emerged improveavoidance. traffic efficiency lock prevention allowing more thananone one vehicle between between sion and deadlock One can the welltwo intersections. We thenmore consider intersection in this prevention allowing than vehicle sion and deadlock avoidance. avoidance. One (RBP) can quote quote the wellknown Reservation-Based Protocol wherethe thewellve- lock two intersections. We then consider an intersection in this sion and deadlock avoidance. One can quote two intersections. We then consider an intersection in that this known Reservation-Based Protocol (RBP) where the venetwork with multiple unlocked vehicles, i.e. vehicles two intersections. We then consider an intersection in this known Reservation-Based Protocol (RBP) where the vehicle sends a reservation request of space and time to the network with multiple unlocked vehicles, i.e. vehicles that known Reservation-Based Protocol (RBP) where the venetwork with multiple unlocked vehicles, i.e. vehicles that hicle sends a reservation request of space and time to the hicle sends sends aa reservation reservation request request of of space space and and time time to to the the network with multiple unlocked vehicles, i.e. vehicles that hicle Copyright 2016 IFAC 497 Hosting by Elsevier Ltd. All rights reserved. 2405-8963 © 2016, IFAC (International Federation of Automatic Control) Copyright © 2016 IFAC 497 Copyright 2016 IFAC 497 Peer review© of International Federation of Automatic Copyright ©under 2016 responsibility IFAC 497Control. 10.1016/j.ifacol.2016.07.669

IFAC MIM 2016 498 June 28-30, 2016. Troyes, France

Alexandre Lombard et al. / IFAC-PapersOnLine 49-12 (2016) 497–502

can move without causing a gridlock. In order to avoid collisions between AGV, we assume that the intersection is regulated with an intersection server using a SBP and a first-in, first-out scheduling policy.

• Stop line: the nearest border of the box junction. For safety reason, the AGV has to stop by default before the stop line (default-deny principle).

According to the chosen protocol, the inconsistency of the presence list brings different risks. Deadlock and collision are then possibles. In the following we will consider a centralized architecture of SBP (C-SBP) named Transparent Intersection Manager (TIM) (Perronnet et al., 2013). In TIM vehicles synchronize their speeds according to the presence list received from the server. There are two advantages of C-SBP. The first one is the default-deny: if a vehicle is not able to establish a communication with the server, it has to brake before the box junction. The second one is that the results of C-SBP can easily be extended to RBP. However, due to potential communication problems (message losses), the sequence built according to the order of arrival of messages from the AGV can be different from the physical order of the vehicles, resulting in a deadlock situation. The scope of this paper is to propose a re-sequencing algorithm able to avoid the deadlock without introducing any risk of collision (3), even with an unreliable communication. In order to assess the proposed algorithm, simulations and intersections of robots are performed. This paper is organized as follows; first it presents the protocol TIM and the conditions of the problem. Then, the paper introduces the deadlock problem as well as the collision risk due to a bad re-sequencing. Therefore, it presents the re-sequencing algorithm and shows that the resulting sequence is collision-free. Before concluding, the paper discuss the results of simulations as well as the results of the cooperative intersection of robots. 2. PROBLEM STATEMENT 2.1 Brief presentation of the Transparent Intersection Manager Vehicles in TIM are able to observe the obstacles in the surrounding environment and to adapt their speed accordingly. AGV move autonomously if all obstacles are visible by the sensors. In order to enhance the intersection safety and throughput, a negotiation protocol based on wireless communication to synchronize the AGVs speed is proposed by TIM. Every AGV has to use wireless communication to inform an intersection server about its movement. More precisely, every AGV communicates its current position and speed as well as the desired destination and the remaining distance before the exit of the box junction. Accordingly, the intersection server broadcasts these data through an ordered presence list to all the AGV closed to the intersection. In the received presence list, the first vehicle has the highest priority and so on. Each AGV considers three kinds of obstacles: • Visible obstacles: mainly a precedent AGV in the same buffer lane. Visible obstacles are detected by the sensors without any message received from the server. • Virtual obstacles: conflicting AGV with higher priority. 498

Fig. 1. TIM

The three obstacles are presented in 1. For each obstacle, the AGV computes an acceleration. Hence, there are three computed accelerations: • ar to keep a safe distance from the visible obstacles. • ai to keep a safe distance from priority conflicting • as to allow a vehicle to stop in the case of a dangerous situation. The three accelerations contribute to determine the acceleration of the AGV as follows : • ai is determined as the minimum acceleration from all conflicting vehicles with a higher priority. • If the AGV has not received a presence list it has to stop before the box junction. In other words, the intersection map is known before requesting the presence list. • Vehicles are not allowed to overtake in the buffer zone of the intersection. • The speed synchronization is done near the junction box. Formally, the acceleration of each AGV is computed as a = min(ar , max(ai , as )) We draw the reader attention to the fact that only ai depends on the presence list sent by the server. The vehicle must know the intersection map before getting into the buffer zone. We highlight also the fact that, default deny (as ) is used when the vehicle has not yet received a presence list or when it is not in the presence list. It is also used when the vehicle is not able to keep a safe distance from the virtual obstacles.

IFAC MIM 2016 June 28-30, 2016. Troyes, France

Alexandre Lombard et al. / IFAC-PapersOnLine 49-12 (2016) 497–502

499

2.2 Considered assumptions TIM allows several strategies for synchronizing the speed of vehicles as well as many policies for ordering the presence list. In the reminder we consider the following assumptions: • The error on the position is below one meter. • With respect to the positioning accuracy, the positions received by the manager can refer to old positions of the vehicles, but never to a position that the vehicle has not reached yet. In other words, more than one meter error is due communication delays between the AGV and the intersection server. • ai is computed under the constraint that two conflicting vehicles cannot simultaneously access to the box junction. • When t → ∞, all present vehicles will be discovered at the good position. • The presence list is built according to ”first-come, first-served” (FCFS). 2.3 Loss of packets Using wireless communication, latency and loss of packets are common problems. And as the number of communicating AGV increases in a network, they become a major preoccupation. Therefore the order of arrival of vehicles at the intersection can differ from the order of arrival of the messages notifying their arrival. The default-deny allows better safety conditions with the intersection. Indeed, if an AGV is not able to communicate with other AGV through the intersection server, it has to stop before the box junction. As long as an AGV is not in the presence list sent by the server, it has to stop. However, in such a case the default deny can block the traffic (Lombard et al., 2015). More precisely, if one vehicle stops then all vehicles behind it in the same buffer zone will stop too. Furthermore all conflicting AGV with a lower priority will stop. The main raised issue is how to safely recover the traffic movement when a missed vehicle establishes a connection. As said before the focus is put on the FCFS policy. With this policy the first AGV arrived at the buffer zone will be the first allowed to cross the conflict area according to the presence list. When considering an instantaneous wireless communication, the order of arrival of vehicles is defined by the order of arrival of the messages emitted by the AGV toward the intersection server. Let us consider the example presented in 2. AGV are numbered according to the messages received by the server. One can note that 10 and 11 were initially missed. Because vehicle 10 is missed, only vehicles 1 and 4 are able to cross the intersection. If the intersection server and the AGV operate under normal conditions, the server will gradually discover the missed vehicles. When these vehicles will be discovered, the server will have to include them in the presence list. If vehicles are ordered according to the received message there is a deadlock. Indeed, there is a circular wait: 10  9  7  (6,5)  (3,4)  2  10 (i  j means that i is waiting for j to cross the intersection). Only AGV #1 499

Fig. 2. Two missed vehicles: The number associated to vehicles shows the order of the received messages by intersection server. and #4 are able to cross the intersection. If the AGV are ordered according to their arrival time, a collision may happen. Indeed, AGV #4 discovers a new virtual obstacle (#10) that has not been initially considered for keeping a safe distance. Moreover, if we consider that the AGV #11 has arrived before AGV #7, the latter has not adapted its speed to avoid collision with #11. Hence, the main raised issue is to reconsider the presence list with missed vehicles without deadlock and collision risks. 3. APPROACH FOR SAFE COOPERATIVE INTERSECTION MANAGEMENT To achieve the objective, in the following we will provide an algorithm that first prevents deadlock and then avoids collision. 3.1 Collision free First let us draw the reader attention to the fact that when a new vehicle is discovered, if it is not ordered correctly a collision may happen, whether or not a cycle is discovered. Indeed, let us consider the example given in 2. If only AGV #1, #2, #3 and #4 are present and if we discover vehicle #10, there is no circular wait, but there is a risk of collision between #10 and #4. This is also the case of vehicle 11 for which there is no cycle. In Qian et al. (2014), the authors introduced and proved the collision free condition. There is a collision risk if a vehicle discovers a new obstacle. From this condition we address a conflict vector of the new discovered vehicle with all present vehicles and we proceed as follows: • The new discovered vehicle is ordered after the last conflicting vehicle. • Each AGV in the same lane physically behind the new discovered AGV move back in the list until it is behind the vehicle physically in front.

IFAC MIM 2016 500 June 28-30, 2016. Troyes, France

function sizeof(s)

Alexandre Lombard et al. / IFAC-PapersOnLine 49-12 (2016) 497–502

 size of the collection s

function l(v)

 lane of the vehicle v

function d(v)

 distance of the vehicle v from the intersection

function s(v)

 position of the vehicle v in the sequence

function conflict(v1, v2) false otherwise

 true if v1 and v2 are in conflict,

procedure move(s, i, j)  move the element at position i in the sequence s to position j procedure insert(s, i, o)  insert the object o at position i in s procedure InsertionSequence(v) expectedP osition ← sizeof (sequence) for all v  in sequence do if l(v) = l(v  ) and d(v) < d(v  ) then expectedP osition ← min(expectedP osition, s(v  ) end if end for insertionP osition ← expectedP osition if expectedP osition = sizeof (sequence) then for i from expectedP osition to sizeof (sequence) − 1 do if conf lict(v, sequence[i]) then insertionP osition ← i end if end for moved, i ← 0 while i < insertionP osition − moved do if l(v) = l(sequence[i] then move(sequence, i, insertionPosition) moved ← moved + 1 else i←i+1 end if end while insertionP osition ← insertionP osition − moved end if insert(sequence, insertionPosition, v) end procedure

Fig. 3. Collision and deadlock free algorithm (CDF algorithm) The optimized algorithm called CDF is given in 3. The algorithm is collision free since there is no vehicle which will discover new obstacle. Indeed, first, the conflicting vehicles with the new discovered vehicle will all pass before. Second, the vehicles behind can only loose priority. It remains to show that it is deadlock free. 3.2 Recovering liveness There are four conditions to have a deadlock situation Coffman et al. (1971). If they are satisfied simultaneously, a deadlock takes place: • • • •

Fig. 4. Graph representation of the intersection: a- before receiving message from vehicle 10, b- after receiving message from vehicle 10 break the cycle by removing edges. However, only virtual obstacles can be reconsidered. Let G = (N, E) be a directed graph of dependency in which the set of nodes N = 1, 2, ..., N ∪ S represents the vehicles with the stop constraint and the set of directed edges E connects each node v to node v  if the vehicle v has to adapt its speed according to the obstacle v  . Hence, E = Er ∪ Ei ∪ Es according to the minimal acceleration used to cross the intersection. 4-a and 4- b show the graph before and after discovering vehicle 10, respectively. For the sake of readability, edges of real obstacles are removed in 4 if the order is respected by edges of virtual obstacles. One can note that in both situations there is no collision risk because vehicles are stopped, waiting for vehicle 10. In 4-b there are four cycles given in 5. The cycles can be broken by removing two edges of virtual constraints. There are four possible solutions: • • • •

10  9 and 10  8, 9  7 and 8  7, 7  5 and 7  6, 5  3 and 6  3.

From the CDF algorithm presented in 3, edges 5  3 and 6  3 are removed. The new sequence when vehicle 10 is discovered is 1 ≺ 4 ≺ 5 ≺ 6 ≺ 7 ≺ 8 ≺ 9 ≺ 10 ≺ 2 ≺ 3. When vehicle 11 is discovered, the new sequence will be 1 ≺ 4 ≺ 5 ≺ 6 ≺ 7 ≺ 9 ≺ 10 ≺ 2 ≺ 3 ≺ 11 ≺ 8

Mutual exclusion Hold and wait No preemption Circular wait

The three first conditions are inherent to the traffic. Hence, when there is a circular wait, a deadlock happens. The circular wait can be represented as a directed cycle in the graph of dependency. To recover liveness, we need to 500

Fig. 5. The four circular wait

IFAC MIM 2016 June 28-30, 2016. Troyes, France

Alexandre Lombard et al. / IFAC-PapersOnLine 49-12 (2016) 497–502

It can be shown that there is a circular wait if the two following conditions are satisfied: • The set S of vehicles physically behind the new discovered of vehicle in the same lane is nonempty • There is at least one vehicle in S which precedes a conflicting vehicle with the new discovered vehicle Then, since all vehicles physically behind the new discovered vehicle are ordered after, the link that exists with a conflicting vehicle is removed. Hence the cycle is interrupted.

501

observe a deadlock situation after 880 seconds for a loss rate of 70%, 380 seconds for a loss rate of 95%, and 38 seconds for a loss rate of 90%. Even if is not represented here, we have observed that a smaller amount of lost packets can also lead to a deadlock situation after enough time. These statements confirm our assumption that, even if in real conditions the risk is low, deadlock cannot be ignored.

4. TESTS AND RESULTS 4.1 Simulation framework Simulations have been realized to experiment this solution. They were realized in Java with a simple yet realistic AGV model, introducing inaccuracy and delays in the positioning system, in the front radar measure, and delays in the application of the acceleration and direction command. In order to test our deadlock solution, AGV are placed on an 8-shaped circuit where the crossing point is the intersection. The vehicles use the TIM protocol (Perronnet et al., 2013) in order to get the right-of-way at the intersection.

Fig. 7. Evacuation of vehicles without deadlock solution

Fig. 6. Illustration of the simulation circuit A communication rate has been fixed to 0.5s and different loss rates have been tested, in order to simulate the issues of a wireless communication. To represent the loss rate, when a message is sent (either by the vehicle or the intersection manager), it has a fixed probability to be ignored. The simulations have been realized using the loss rates 5%, 10%, 50%, 70%, 90% and 95%, with and without the deadlock prevention. The reader may note that these loss rates do not reproduce accurately the loss rates of a V2I communication, but are used to stress-test our solution in critical conditions (if you can do the big things, you can do the little things as well). Moreover the presentation of the number of vehicles evacuated is used to show the liveness or the deadlock situation of the intersection, but is not used here to evaluate the throughput of the intersection using TIM as it has already been studied in Perronnet et al. (2013).

Fig. 8. Evacuation of vehicles with deadlock prevention As it can be seen on 8, with deadlock prevention vehicles were sometime stopped at the intersection due to the loss of messages (if they do not receive the right-of-way from the manager, their default behavior is to stop), but they always ended up moving out of the intersection. Moreover, no collisions were detected: a hazardous situation is counted every time the distance between two vehicles is below one meter, this did not happen in our simulation.

4.2 Results 4.3 Tests with EV3 robots The following figures (7 and 8) represents the number of vehicles crossing the intersection of the circuit in function of the time for different loss rates. These measures have been made with six vehicles on the circuit. On 7, we can 501

Finally, to confirm the feasibility of the solution, and its collision-free property, real tests have been made using Lego EV3 robots. Our test bench is presented in 9.

IFAC MIM 2016 502 June 28-30, 2016. Troyes, France

Alexandre Lombard et al. / IFAC-PapersOnLine 49-12 (2016) 497–502

Fig. 9. EV3 intersection test bench Positioning of the robots was made using the odometry, the color sensor and the color marks on the ground, the front obstacle detection using the EV3 sonar and the network using Edimax Wi-Fi dongles. The intersection manager was an Android phone acting as a wireless access point for the robots. As expected, during first tests, nor collision neither deadlocks were observed, but the quality of the wireless connection was good (only five devices were using Wi-Fi and they were close to each other). A fake network disturbance has been introduced similar to the one used in simulations in order to stress-test our protocol. It consisted of a fixed probability that the intersection manager ignores a received message. It slowed down the performance of the intersection but collisions and deadlocks were not introduced. 5. CONCLUSION During our work to extend the tests on cooperative intersection management to three vehicles and more, we have faced deadlock situations. The purpose of this paper has been twofold. In a first part, it has been shown that the impact of vehicular communication issues (message delays and losses) can lead to a specific case of deadlock resulting of the interdependency between the right-of-way and the position of a vehicle in its lane. In a second part, a solution to prevent deadlocks has been presented, and it has been shown that the proposed solution will effectively prevent deadlock and will not provoke collisions. Finally, simulations and tests have been realized. They showed up that the presented kind of deadlock cannot be ignored, especially when the message loss rate increases. Moreover, it confirmed that the proposed solution prevents the risk of deadlock and do not provoke any collision. REFERENCES Bobanac, V. and Bogdan, S. (2008). Routing and scheduling in multi-agv systems based on dynamic banker algorithm. In Control and Automation, 2008 16th Mediterranean Conference on, 1168–1173. IEEE. Bocewicz, G., W´ ojcik, R., and Banaszak, Z. (2007). Design of admissible schedules for agv systems with constraints: A logic-algebraic approach. In Agent and Multi-Agent Systems: Technologies and Applications: First KES International Symposium, KES-AMSTA 2007, Wroclaw, Poland, May 31– June 1, 2007. Proceedings, 578–587. Coffman, E.G., Elphick, M., and Shoshani, A. (1971). System deadlocks. ACM Computing Surveys (CSUR), 3(2), 67–78. de La Fortelle, A. (2010). Analysis of reservation algorithms for cooperative planning at intersections. In 502

Intelligent Transportation Systems (ITSC), 2010 13th International IEEE Conference on, 445–449. Dresner, K. and Stone, P. (2004). Multiagent traffic management: A reservation-based intersection control mechanism. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems-Volume 2, 530–537. IEEE Computer Society. Ezpeleta, J., Tricas, F., Garc´ıa-Vall´es, F., and Colom, J.M. (2002). A banker’s solution for deadlock avoidance in fms with flexible routing and multiresource states. Robotics and Automation, IEEE Transactions on, 18(4), 621–625. Lawley, M., Reveliotis, S., and Ferreira, P. (1998). The application and evaluation of banker’s algorithm for deadlock-free buffer space allocation in flexible manufacturing systems. International Journal of Flexible Manufacturing Systems, 10(1), 73–100. Lombard, A., Perronnet, F., Abbas-Turki, A., El Moudni, A., and Bouyekhf, R. (2015). V2x for vehicle speed synchronization at intersections. In 22nd ITS World Congress, EU - ITS-2788, 5-9 October 2015, Bordeaux, France. ITS-WC. Miyamoto, T. and Inoue, K. (2016). Local and random searches for dispatch and conflict-free routing problem of capacitated {AGV} systems. Computers & Industrial Engineering, 91, 1 – 9. Nishi, T. and Tanaka, Y. (2012). Petri net decomposition approach for dispatching and conflict-free routing of bidirectional automated guided vehicle systems. Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, 42(5), 1230–1243. Perronnet, F., Abbas-Turki, A., and El Moudni, A. (2013). A sequenced-based protocol to manage autonomous vehicles at isolated intersections. In Intelligent Transportation Systems-(ITSC), 2013 16th International IEEE Conference on, 1811–1816. IEEE. Perronnet, F., Abbas-Turki, A., and El Moudni, A. (2014). Vehicle routing through deadlock-free policy for cooperative traffic control in a network of intersections: Reservation and congestion. In Intelligent Transportation Systems-(ITSC), 2014 17th International IEEE Conference on, 2233–2238. IEEE. Qian, X., Gregoire, J., Moutarde, F., and De La Fortelle, A. (2014). Priority-based coordination of autonomous and legacy vehicles at intersection. In Intelligent Transportation Systems (ITSC), 2014 IEEE 17th International Conference on, 1166–1171. IEEE. Wu, N. and Zhou, M. (2007). Shortest routing of bidirectional automated guided vehicles avoiding deadlock and blocking. Mechatronics, IEEE/ASME Transactions on, 12(1), 63–72. Zohdy, I.H., Kamalanathsharma, R.K., and Rakha, H. (2012). Intersection management for autonomous vehicles using icacc. In Intelligent Transportation Systems (ITSC), 2012 15th International IEEE Conference on, 1109–1114. IEEE. Zohdy, I.H. and Rakha, H. (2012). Game theory algorithm for intersection-based cooperative adaptive cruise control (cacc) systems. In Intelligent Transportation Systems (ITSC), 2012 15th International IEEE Conference on, 1097–1102. IEEE.