Zichao XING,Xingkai WANG,Shuo WANG,Weimin WU?,Ruifen HU

State Key Laboratory of Industrial Control Technology,Institute of Cyber-Systems and Control,Zhejiang University,Hangzhou 310027,China

Abstract: Multi-mobile robot systems (MMRSs) are widely used for transportation in industrial scenes such as manufacturing and warehousing.In an MMRS,motion coordination is important as collisions and deadlocks may lead to losses or system stagnation.However,in some scenarios,robot sizes are different when loaded and unloaded,which means that the robots are variable-sized,making motion coordination more difficult.The methods based on zone control need to first divide the environment into disjoint zones,and then allocate the zones statically or dynamically for motion coordination.The zone-control-based methods are not accurate enough for variable-sized multi-mobile robots and reduce the efficiency of the system.This paper describes a motion coordination method based on glued nodes,which can dynamically avoid collisions and deadlocks according to the roadmap structure and the real-time paths of robots.Dynamic features make this method directly applicable to various scenarios,instead of dividing a roadmap into disjoint zones.The proposed method has been applied to many industrial projects,and this study is based on some manufacturing projects for experiments.Theoretical analysis and experimental results show that the proposed algorithm is effective and efficient.

Key words: Multi-mobile robot system;Collision avoidance;Deadlock avoidance;Glued nodes;Motion coordination

1 Introduction

Enterprises are paying more and more attention to production efficiency and production safety.As a widely used automated material handling system,the multi-mobile robot system(MMRS)plays an important role in manufacturing,warehousing(Krnjak et al.,2015),container terminal(Zhong et al.,2020),and other scenarios.A stable and efficient MMRS can reduce labor cost and improve production safety.An MMRS involves multiple technologies,such as task allocation,positioning,path planning,and motion coordination (de Ryck et al.,2020).Motion coordination includes collision and deadlock handling,which is an overwhelmingly significant issue in MMRSs.

The roads on which the robots can travel are usually planned in advance in industrial environments.These roads form a roadmap,in which an edge represents a road or part of a road,and a node represents an intersection or a point on a road.Unlike an abstract graph,a roadmap is a map of a real robot environment whose edges can be unidirectional or bidirectional and can be curved or straight.In such a roadmap,the nodes are allocated to robots in a certain way as resources to realize motion coordination among robots.However,the compact layout of some roadmaps results in two nodes not necessarily being collision-free for two robots.In particular,whether two nodes are collision-free for two robots depends on whether the robots are loaded.As shown in Fig.1a,R1andR2are not loaded and all nodes are collision-free.However,as can be seen in Fig.1b,whenR1andR2are loaded,they cannot pass throughV2andV5at the same time,which means thatV2andV5are not collision-free forR1andR2.Compact roadmaps present difficulties for motion coordination of multi-mobile robots.

Fig.1 Examples of the relationship between collisionfree nodes and robot loading: (a) all nodes are collision-free for R1 and R2;(b) V2 and V5 are not collision-free for R1 and R2

Motion coordination is focused mainly on collision avoidance and deadlock handling.When it comes to collision avoidance,there are generally two methods: coupling and decoupling methods.

The coupling method statically or dynamically plans collision-free paths or trajectories for robots.There are many methods that have been studied,such as graph theory (Yu and LaValle,2016),reciprocal collision avoidance(Alonso-Mora et al.,2013),state lattice(Draganjac et al.,2020),and cell decomposition(Zhang et al.,2007).

The other is decoupling that decouples path planning and motion coordination;that is,paths for robots are first planned with a certain goal (such as the shortest distance or shortest task time),and then collisions are avoided based on existing paths.This method is suitable for scenarios where the robot paths are fixed or the roadmaps have been planned,and it is necessary to ensure that only one robot can pass through a physical space at a time.The decoupling method is more suitable for application in industrial scenarios (de Ryck et al.,2020).Wang et al.(2015) set different initial delays for different robots to avoid collisions,but this kind of method is time-sensitive and not robust.Some methods based on zone control (Luo et al.,2020;Reveliotis,2020;Zhao et al.,2021) divide the environment into disjoint zones,and each zone can accommodate a robot,thus avoiding collisions.Luo et al.(2020) designed an optimal controller to prevent robots from any collision based on Petri nets.They converted the collision-free problem into admissible ones using an algorithm to significantly reduce the computational overhead.

Deadlock handling was originally studied in computer operating systems (Habermann,1969;Coffman et al.,1971).There are three major approaches for deadlock handling in MMRSs: deadlock detection and resolution,deadlock prevention,and deadlock avoidance(Coffman et al.,1971).

For the method of deadlock detection and resolution,robots are allowed to form deadlocks.Once the system detects a deadlock,the deadlock resolution strategy is applied to unlock the deadlock(Jager and Nebel,2001;Wu and Zhou,2007;Alonso-Mora et al.,2018).In Jager and Nebel (2001),the trajectory planner of each involved robot was successively requested to plan an alternative trajectory until the deadlock was resolved.This method is suitable for systems where the number of robots is small and deadlocks are rare.

Deadlock prevention is an offline method that applies some simple rules or designs to the controller before the system release to prevent the occurrence of deadlock(Chen et al.,2016;Xing KY et al.,2018).However,this method suffers from low efficiency and high complexity(Chen et al.,2016).

As an online method,deadlock avoidance has been widely studied.To avoid deadlocks,it is necessary to dynamically determine whether the robot’s next move will cause a deadlock and,if so,terminate the action of the robot.Moorthy et al.(2003)developed an efficient deadlock prediction and avoidance algorithm for an automated container port,which has a complex layout and involves close to 80 automated guided vehicles (AGVs).Yoo et al.(2005)presented a deadlock avoidance algorithm that uses the graph-theoretic approach for a robot system in flexible manufacturing.Fanti et al.(2015)proposed a decentralized coordination protocol based on the zone-control method;deadlocks and collisions can be avoided with a decentralized coordination protocol.Li et al.(2016)presented time-efficient traffic control for MMRSs based on a discrete-event zone-control model.All inter-vehicle collisions and system deadlocks can be avoided.Zhou et al.(2020) modeled robot motion through labeled transition systems and proposed a distributed algorithm to avoid deadlocks in such systems.Each robot has a predetermined and closed path to execute persistent motion.The method is based on fixed path scenarios,where all robots’paths are fixed.Zaj?ac and Ma?opolski(2021)distinguished unidirectional zones and deadlock-risk zones,and introduced a structural online control policy to avoid deadlocks among robots.Ma?opolski(2018)divided the layout of a transportation system into squares and proposed a method of collision and deadlock avoidance based on chains of reservations.

These collision and deadlock avoidance methods explicitly or implicitly divide the environment into zones,each of which can accommodate only one robot at a specific time.This allows an MMRS to be considered as a discrete event system,and collisions and deadlocks are regarded as resource conflicts.However,the division of zones increases the difficulty of method application,and the static characteristics of zones lead to imprecision and wasted space.

In our previous work(Xing ZC et al.,2022),we proposed the concept of glued nodes,based on which a basic collision and deadlock avoidance algorithm was proposed.Based on the concept of glued nodes,the system can dynamically determine the mutual influence between nodes based on the real-time sizes and paths of the robots.Due to the dynamic features,the glued nodes can be applied to a variety of complex MMRSs.This work improves the definition and properties of glued nodes and provides a more detailed analysis of collision and deadlock avoidance issues.The deadlock is divided into direct deadlock and impending deadlock,and the corresponding collision and deadlock avoidance algorithms are given.In addition,we conduct experiments based on multiple industrial scenarios to verify the performance of the algorithms.

The main contributions of this paper are as follows: (1) A concept of glued nodes is introduced and used to design a collision and deadlock avoidance algorithm;(2)The proposed collision and deadlock avoidance algorithm can be directly applied to an MMRS containing variable-sized robots and a roadmap with various structures;(3) The difference between direct deadlock and impending deadlock is analyzed,and a unified method to avoid them is provided;(4) A hybrid architecture is proposed,where the control center is responsible for allocating nodes,and the robots apply for nodes on demand.

2 System modeling and problem statement

This section discusses the MMRS model,gives definitions and descriptions of the glued nodes,and states the collision and deadlock avoidance problem.

2.1 Multi-mobile robot system

Let N={1,2,...,N}be the indices of robots andNbe the number of robots.Ri(i ∈N) denotes a robot in the MMRS.The roadmap in the system consists of a set of nodes and a set of edges,denoted asG=(V,E).Let M={1,2,...,M}be the indices of nodes inG.Vi(i ∈M) denotes a node inG.The edges in the roadmap are denoted asE ?(V,V),andEm,n=(Vm,Vn) denotes an edge fromVmtoVn.There may be two edges between two nodes,which meansEm,n≠En,m.A path ofRiis denoted asPi={V1,E1,2,...,Ek?1,k,Vk},consisting of a series of nodes and edges.As shown in Fig.2,the path ofR1isP1={V4,E4,3,V3,E3,7,V7}.

Fig.2 An example of the path of robot R1 (V 4 and V3 are authorized to R1)

There are many ways to generate paths for robots(Willms and Yang,2006;Guruji et al.,2016),but this is not the focus of this study.Once the path of a robot is planned,the robot will move along the path to the end node.However,all nodes are managed by the control center,and the robot can move only along the path to the nodes that are authorized by the control center.Fig.3 is the architecture of the MMRS.Each robot sends its path and position information to the control center in real time and applies for the nodes ahead at a specific frequency when it needs to move.The control center determines whether the nodes requested by a robot can be authorized according to the collision and deadlock avoidance algorithm.The control center ensures that the nodes authorized to the robot are collision-free and deadlock-free.Then,the robot can move along the path to these authorized nodes.

Fig.3 Architecture of the multi-mobile robot system

To better explain the interaction process between the robot and the control center,we give the definitions of occupied nodes and applying nodes:

Definition 1(Occupied nodes) The nodes for which a robotRihas obtained authorization from the control center are called occupied nodes,denoted as OVi.

Definition 2(Applying nodes) The nodes for which a robotRiapplies to the control center are called applying nodes,denoted as AVi.

The manner in which a robotRiapplies for nodes in this study is as follows: beforeRireaches the end node,once the distance from the robot to the last occupied node is less than LAi,the robot applies for new nodes within the length of LAialong the path.Those authorized applying nodes will become occupied nodes.The control law of LAiis shown in Eq.(1),in whichviis the real-time speed ofRi,aiis the braking acceleration ofRi,andγiis a fixed value.The first term of the right-hand side of Eq.(1)is the braking distance ofRi,and the second term is used to reduce the number of times of robot brakes.Once the robot reaches a new node,the previous node on the path is released,and the path information also changes at this time.

An example of the interaction process between the robots and the control center is shown in Fig.2.BecauseV4andV3are already authorized toR1,i.e.,OVi={V4,V3},R1can move the farthest toV3.However,to preventR1from slowing down,R1starts to apply forV7before it reachesV3according to its own kinematic model,i.e.,AVi={V7}.IfV7is not authorized toR1,thenR1will stop after reachingV3and wait for the new nodes to be authorized.OnceV7is authorized toR1,denoted as OVi={V4,V3,V7}(or OVi={V3,V7}) and AVi=?,R1can move along the path toV7.WhenR1reachesV3,V4will be released and the path ofR1changes toP1={V3,E3,7,V7}.A node cannot be authorized to other robots before it is released.

2.2 Glued nodes

A roadmap mentioned in this study is similar to a roadmap in the traffic road network.Nodes can be intersections of lanes,task points,or discrete points in the lanes.For example,in an MMRS of quick response(QR)code positioning,a straight road will be paved with multiple QR codes,and each QR code can be regarded as a node.The direction of the edge in the roadmap can be unidirectional or bidirectional,and the type can be a straight edge,a circular arc,a Bézier curve,and so on.Fig.4 is an example of a roadmap.

Fig.4 An example of a roadmap

After a robot obtains the authorized nodes,the process of the robot moving along the path to the authorized nodes is no longer controlled by the control center.Therefore,it is necessary to ensure that the robot can safely move to these nodes once the control center authorizes the nodes to the robot.However,the location of nodes and the types of edges in the roadmap may be diverse,which may lead to collisions among robots.

When two nodes are far enough apart,they are collision-free for two robots.As shown in Fig.5a,the path nodes of the two robots are collision-free,but that is not always the case.As shown in Fig.5b,robotsR1andR2are moving on the way toV2andV4,respectively.The distance betweenE1,2andE3,4is too small,causing the risk of collision if the robots continue to move.Similarly,in Fig.5c,there may be a collision whenR1moves onE1,2andR2rotates onV5.In Fig.5d,whenR1andR2rotate onV2andV5simultaneously,they will collide with each other.To solve this kind of problem,we define the concept of glued nodes:

Fig.5 Examples when two nodes are collision-free or not collision-free: (a) any two nodes are collisionfree;(b) there is a risk of collision between two robots in the moving process;(c) there is a risk of collision when a robot rotates and a robot moves;(d) there is a risk of collision between two robots during rotation

Definition 3(Node action) A node action ofRiis denoted as a quadruple,where the following concepts are defined:

(1)?Emis the preceding edge ofVminPi;

(2)is the angle when the robot reachesVmalong?Emor the angle of the robot ifVmis the first node ofPi;

(3)Vmis a node inG;

(4)is the angle at which the robot leavesVm.IfVmis the last node ofPi,then.

Definition 4(Action path) An action path ofRiis a set of node actions,denoted asPi=.

Node action describes the process of the robot moving from one node to another.As shown in Fig.2,V4is the first node of the path and has no preceding edge,such that?E4∈?and=〈?E,180?,V4,180?〉.E4,3is the preceding edge ofV3;afterR1moves alongE4,3toV3,R1will rotate 90?clockwise to continue toV7.So,=〈E4,3,180?,V3,90?〉.Similarly,=〈E3,7,90?,V7,90?〉.The action path ofR1isP1=.A robot without a path can be considered to have an action path that contains only the node where it is currently located.As an example,when robotRihas no path and its current node isVm,it can be considered thatPi=.In this way,idle and working robots have a unified way of expression.

Definition 5(Action area) When a robotRiperforms a node action,the area it sweeps is called the action area,denoted as.

Definition 6(Glued nodes)?m,n ∈M,?i,j ∈N,,thenVmandVnare a pair of glued nodes forRiandRj.

IfVmandVnare a pair of glued nodes forRiandRj,we define a flag;otherwise,GN=0.Obviously,when,.

The concept of glued nodes is dynamic;that is,the glued relationship between two nodes varies with different robot sizes and different paths.At first,the concept of glued nodes is related to the real-time robot paths.As shown in Figs.6a and 6b,ifV2is authorized toR1,because.However,as shown in Figs.6c and 6d,althoughR1still passes through nodeV2,.Furthermore,the concept of glued nodes is related to the robot sizes.As shown in Figs.6c and 6d,if the two robots are larger,there may be.In other words,the concept of glued nodes is related to the real-time sizes and paths of the robots,so it is dynamic.

2.3 Problem statement

When robots move,potential collisions can result in damage to the robots,and deadlocks may lead to system stagnation until the deadlock is resolved.Therefore,a collision and deadlock avoidance algorithm is necessary for MMRSs.

Fig.6 An example showing the characteristics of the glued nodes: (a) paths of the two robots contain a pair of glued nodes,GN=1;(b) areas swept by the two robots when executing and corresponding to (a);(c) paths of the two robots do not contain glued nodes;(d) areas swept by the two robots when executing and corresponding to (c)

The problem statement can be described as follows: Given an MMRS with a roadmap,find an effective controller to avoid collisions and deadlocks during the movement of robots.

Stable operation of MMRSs relies on various technologies,such as a navigation algorithm,communication technology,sensor technology,and motion control.This work focuses on motion coordination in MMRSs.For the convenience of study,we make some additional assumptions,but these assumptions do not detract from the contributions of our work: (1) The communication between robots and the control center is based on a wireless network,and there is no delay,error,or packet loss in the communication;(2) Each robot can always move along the planned path within an accepted derivation;(3)Taking into account the positioning accuracy,robots can stop only at nodes,and the robots are fault-free;(4) When an idle robot blocks a robot with a path,the idle robot will automatically plan a path that does not block the robot with a path.

3 Motion coordination

3.1 Collision avoidance

There is no doubt that whatever method is used to avoid collisions among robots,the essence is that multiple robots cannot appear in the same space simultaneously.In this subsection,we present the collision avoidance algorithm based on glued nodes.The main idea is that the control center decides whether to authorize a node to a robot according to whether the robot will collide with other robots during movement to the node.

Lemma 1If?Vm ∈OViand?Vn ∈OVj,such that GN=1,thenRiandRjare at risk of collision during movement.

ProofGN=1 means that whenRiandRjexecuteand,;i.e.,the swept areas will overlap.This may causeRiandRjto collide with each other.

Lemma 2If?Vm|Vm ∈OVi ∧Vm ∈OVj,RiandRjare at risk of collision.

ProofOnce a node is authorized to two robots,it means that the two robots can move to this node.Obviously,it is possible for the two robots to pass through this node simultaneously;i.e.,a collision occurs.

Note that Lemmas 1 and 2 are about possible collisions,not inevitable collisions.For example,even if a node is authorized to two robots at the same time,but if the robots do not pass the node simultaneously,there is no risk of collision between the robots.However,in an actual industrial environment,a robot’s movement process may be affected by human operations,faults,and so on,so the system cannot accurately estimate when the robot will arrive and leave a particular position.To ensure the robustness of the system,this study does not consider the time dimension.

Theorem 1?Vm ∈OViand?Vn ∈OVj,if OVi∩OVj=?and GN=0,thenRiandRjare collision-free.

ProofIf OVi∩OVj=?,then a node is not authorized to the two robots at the same time.RiandRjwill not collide with each other by passing through the same node at the same time.According to Definition 6,GN=0 means that the areas swept byRiandRjwhen performinganddo not overlap.In a word,regardless of whether OViand OVjcontain the same node,the robots will not collide with each other during the movement to the occupied nodes.

According to Theorem 1,the collision avoidance algorithm can be stated as shown in Algorithm 1.LetOmdenote nodeVmto which the robot is authorized.Om=RimeansVm ∈OVi,andOm ∈?means thatVmis not authorized to any robots.As shown in Algorithm 1,along the sequence of nodes in the path,the control center determines whether the applying nodes can be authorized to the robot one by one(line 4).An applying node cannot be authorized to the robot if the node has been authorized to another robot (lines 5–7).In addition,if the applying node and another node are a pair of glued nodes,and another node has been authorized to other robots,the applying node cannot be authorized to the robot(lines 11–13).Once a node cannot be authorized,other applying nodes no longer need to be calculated (lines 6 and 12).Line 19 returns the nodes that can be authorized toRi.LetNbe the number of robots,andHandLdenote the maximum numbers of the applying nodes and occupied nodes of the robot,respectively.The complexity of the algorithm isO(NHL).

Algorithm 1Collision avoidance: CA(Ri,AVi)

In the example shown in Fig.7,P1=,,OV1={V1,V2},OV2={V5},AV1={V3,V4,V8},and AV2={V4,V3,V7}.AV1∩AV2≠ ?means thatR1andR2apply for the same nodes.However,the robot to which the nodes are authorized can be judged by factors such as task priority and road congestion.This study uses a simple strategy which is first-apply first-occupy.Assuming thatR2applies to the control center for nodes earlier thanR1,according to Algorithm 1,V4can be authorized toR2,butV3cannot be authorized for the reason GN=1.Thus,the result is that onlyV4is authorized toR2.Note that this result will cause a deadlock betweenR1andR2.The detection and avoidance of deadlocks will be presented in Section 3.2.

Fig.7 An example of collision avoidance

3.2 Collision and deadlock avoidance

This subsection presents the analysis of the causes and categories of deadlocks,and designs collision and deadlock avoidance algorithms.

3.2.1 Direct deadlock

In Section 3.1,we propose an algorithm to avoid collisions among multiple robots.Each robot applies for nodes in the forward direction according to its kinematic model.If multiple robots block each other,deadlocks may occur.For example,in Fig.8a,,AV1=AV2={V3,V5},OV1={V2},and OV2={V4}.However,V3cannot be authorized toR1andR2because GN=1 and GN=1,meaning thatR1andR2wait for each other (i.e.,a deadlock occurs).In Fig.8b,AV1=OV2={V2},AV2=OV3={V4},AV3=OV4={V3},and AV4=OV1={V1}.The four robots cannot move because the next node in the path of each robot is occupied by another robot,and the circular wait leads to a deadlock.

Fig.8 Examples of deadlocks: (a) a deadlock of two robots;(b) a deadlock of four robots

Definition 7(Direct deadlock) There is a direct deadlock in an MMRS if multiple robots are in a circular wait.

Definition 8(Block)RiandRjare two robots in an MMRS,andVeis the last node in OVi.IfVeis not the last node ofPiandVmis the next node ofVeinPi,?Vn ∈OVj,ifVm=Vnor GN=1,thenRiis blocked byRj,denoted as(Ri →Rj).

Definition 9(Block circle)A block circle is a sequence of blocks,like〈(R1→ R2),(R2→R3),...,(Rn?1→Rn),(Rn →R1)〉.

A block means that new nodes cannot be authorized to a robot because the robot avoids collisions with other robots.For example,as shown in Fig.8a,V3is the next path node of the last node in OV1and OV2.;according to Definition 8,there are two blocks (R1→R2) and(R2→R1),and the two blocks generate a block circle〈(R1→R2)(R2→R1)〉.

Theorem 2If there are no conflict circles in the system,there will be no direct deadlocks in the system.

ProofAccording to the definitions of the block and the block circle,if there is no block circle among multiple robots,at least one robot can apply for a new node because of other robots.Therefore,there will be no circular wait among the robots;i.e.,there will be no direct deadlock among them.If there are no block circles among any number of robots,there are no direct deadlocks in the system.

Based on Theorem 2,the control center can detect whether the authorization of some nodes to a robot will cause a block circle,and prevent block circles from forming to avoid deadlocks.The combined collision and direct deadlock avoidance algorithm is shown in Algorithm 2.LetCbe all blocks in the system,andCwill be updated once a robot releases a node.ANs are those collision-free nodes that are returned by Algorithm 1(line 4).Lines 5–7 try to add the nodes in AN to the occupied nodes ofRi,and generate new blocks.If there are newly generated blocks,then they are added toC(lines 8 and 9).If there are block circles in the system(line 10),it means that authorizing this node may lead to deadlock.The algorithm does not need to continue the calculation.Lines 13 and 16 add nodes that do not cause collisions and deadlocks to DAN to be returned.

Algorithm 2Collision and direct deadlock avoidance: CDDA(Ri,AVi)

3.2.2 Impending deadlock

Algorithm 2 can avoid only direct deadlocks but cannot avoid impending deadlocks.Let us take Fig.7 as an example to illustrate the impending deadlock.WhenR2applies nodeV4,V4will be authorized toR2because it will not cause any collisions or direct deadlocks.V3cannot be authorized toR2because;i.e.,R2is blocked byR1.However,at this point,R1is not blocked byR2,and ifV3is authorized toR1,thenR1will move toV3,forming a direct deadlock.Even ifV3is not authorized toR1to avoid the deadlock,the result is that neitherR1norR2can continue to move.Therefore,a new deadlock occurs.In other words,whenV4is authorized toR2,R1andR2will inevitably form a deadlock.

Definition 10(Impending deadlock)There is currently no deadlock among multiple robots,but these robots will inevitably form a deadlock after taking a few steps.This phenomenon is called an impending deadlock.

Because there may be impending deadlocks in the system,deadlock avoidance requires not only avoiding direct deadlocks,but also avoiding impending deadlocks.

Definition 11(Conflict node)?i,j ∈N,?m,n ∈M,Vmis a conflict node forRiandRjif it meets one of the following conditions:

Definition 12(Conflict area)?i,j ∈N,the conflict area ofRiandRjis the set of all their conflict nodes,denoted asΦi,j.

In Fig.7,V2,V3,andV4are conflict nodes,and they compose a conflict areaΦ1,2={V2,V3,V4}.Let us analyze the impending deadlock according to the definition of the conflict area.Once two robots occupy the same conflict area,a deadlock will inevitably occur because the two robots will stop in this conflict area no matter how they move.There are similar laws for multiple robots,which will be discussed and proved below.

Definition 13(Conflict occupation)If OVi ∩Φi,j≠?,there is a conflict occupation ofRi,denoted asRi →Φi,j.

Definition 14(Conflict circle)A conflict circle is a sequence of conflict occupation,like〈R1→Φ1,2,R2→Φ2,3,...,Rn?1→Φn?1,n,Rn →Φn,1〉.

As shown in Fig.7,becauseV2has been authorized toR1,there is a conflict occupationR1→Φ1,2.IfV4is authorized toR2at the same time,there will be another conflict occupationR2→Φ2,1,and a conflict circle〈R1→Φ1,2,R2→Φ2,1〉occurs.

Lemma 3A block circle is a type of conflict circle.

ProofBased on the definition of the block,(Ri →Rj) meansVm=Vnor,Vm ∈PiandVn ∈Pj.IfVm=Vn,thenVm ∈PiandVm ∈Pj,which meets the first condition of Definition 11.meets the second conditions of Definition 11.Therefore,Vmis a conflict node,andVm ∈Φi,j.Then (Ri →Rj) can be transformed toRj → Φi,j.So,the block circle〈(R1→R2),(R2→R3),...,(Rn?1→Rn),(Rn →R1)〉can be transformed to〈R1→ Φ1,2,R2→Φ2,3,...,Rn?1→Φn?1,n,Rn →Φn,1〉.

Note that the conflict circle is generated based on the conflict areas formed by the remaining unfinished paths of robots instead of the complete static paths.The reason is that the nodes that a robot has gone through will be released.It will not cause any collisions or deadlocks,except for those glued nodes.Furthermore,based on the above definitions and theorems,this study describes the relationship between conflict circles and deadlocks,as stated in Theorem 3:

Theorem 3If there are no conflict circles in the system,there will be no deadlocks in the system.

ProofAccording to Lemma 3,there is no block circle if there is no conflict circle in the system.Furthermore,based on Theorem 2,there will be no direct deadlock without a block circle.Therefore,we can conclude that there will be no direct deadlock without a conflict circle.In addition,for impending deadlock,according to the definitions of conflict occupation and conflict circle,a conflict area is actually a common space swept by two robots when they move along their paths.Once a robot occupies the conflict area,it may induce another robot to avoid collisions and stop in the future.If multiple robots do not form a conflict circle,then at least one of these robots can move without being blocked by other robots.There will be no direct deadlocks among the robots in the future.Therefore,there are no impending deadlocks among the robots.The absence of a conflict circle means that no deadlock can be formed among any number of robots;that is,the system is free of deadlocks.

Now that the conditions for avoiding deadlock have been proved,we present the collision and deadlock avoidance algorithm as shown in Algorithm 3.Line 4 calls Algorithm 1 to obtain collision-free nodes,and then the algorithm judges whether these nodes are deadlock-free.Lines 5–20 search for the farthest node among these nodes that is not in conflict areas,and the robot can move to this node without deadlock,because if a node is not in a conflict area,a conflict occupation cannot be formed and there will be no conflict circle.Lines 21–30 judge whether the authorized nodes form a conflict circle,and only those nodes that do not form a conflict circle can be occupied by the robot.

In the worst case,all nodes are in conflict areas.Therefore,in lines 8 and 22,the complexity of judging whether a node is in a conflict area isO(M),in whichMis the number of nodes inG.The occupation relationship of the conflict areas among robots can form a directed graph,and the complexity of finding the circles in the directed graph isO(V+E) (Tarjan,1971).VandEare the numbers of nodes and edges in the graph,respectively (line 23).The complexity of the algorithm isO(HM(V+E)),whereHis the number of nodes in AN.

Fig.9 shows the collision and deadlock avoidance process of four robots.Initially,as shown

Algorithm 3Collision and deadlock avoidance:CDA(Ri,AVi)in Fig.9a,there are four conflict areas:Φ1,2={V4,V6},Φ2,3={V2},Φ3,4={V1,V5,V9},andΦ4,1={V3}.Suppose thatR3first applies for nodeV3and receives authorization.Subsequently,the application ofR2for nodeV6will not succeed,because onceV6is authorized toR2,a conflict circle〈R1→Φ1,4,R4→Φ4,3,R3→Φ3,2,R2→Φ2,1〉will be generated.Therefore,Algorithm 3 will preventV6from being authorized toR2,as shown in Fig.9b.Then,as shown in Figs.9c and 9d,R3continues to move forward,and the four robots will eventually reach their respective destinations.

Fig.9 An example of collision and deadlock avoidance for four robots: (a) conflict occupations (R3→Φ3,4),blocks (R3 →R4),glued nodes (GN=1,GN=1,GN=1);(b) conflict occupations (R3→Φ3,4, R4 →Φ4,1, R2 →Φ2,3),blocks (R3 →R4,R4 →R1),glued nodes (GN=1,GN=1);(c)conflict occupations (R1 →Φ1,2),blocks (R1 →R1);(d) no conflict occupations,no blocks,and no glued nodes

4 Experiment implementation and results

In this section,we describe multiple experiments to verify the effect of the proposed collision and deadlock avoidance algorithm.All experiments are realized with robot scheduling software and robot simulation software.The robot scheduling software has been applied in many real projects,with functions of task dispatch,path planning,collision and deadlock avoidance,and deadlock unlocking.All simulations run on a desktop running Windows 10,equipped with an Intel?Xeon?Platinum 8280L 2.6 GHz CPU and 64 GB of RAM.

4.1 Comparison of different collision and deadlock avoidance algorithms

To compare the performance of different collision and deadlock avoidance methods,we compare Algorithm 2 (collision and direct deadlock avoidance,CDDA) and Algorithm 3 (collision and deadlock avoidance,CDA)based on a simulation of a real industrial scene.

The experiments are based on an actual air conditioning production line containing eight mobile robots and 38 workstations,as shown in Fig.10.This scene contains two production lines,where the edges in the roadmap are all bidirectional,and the robots are constantly carrying out transportation tasks between workstations.Once a task is generated,the idle robot with the closest distance will be assigned to perform the task.

Fig.10 An experimental scene of an air conditioning production line with eight mobile robots

The parameters of robots in the simulation are shown in Table 1,wherevdenotes the maximum moving speed of robots,δdenotes the acceleration,θdenotes the braking deceleration,el and ew denote the length and width of the robots when they are not loaded respectively,and fl and fw denote the length and width of the robots when they are loaded respectively.γtakes a fixed value of 4 m.Because CDDA cannot avoid the impending deadlock,once a deadlock occurs,the software will call the deadlock unlocking method to resolve the deadlock.

Table 1 Experimental parameters of robots in the scene shown in Fig.10

The number of deadlock avoidances,the number of deadlock unlockings,and the average task time of these two algorithms are counted.Let K={1,2,...,K}be the indices of tasks,andKbe the number of tasks.TKi(i ∈K) denotes a task in the system.The average task time is calculated as

whereanddenote the start time and end time of TKi,respectively.

The experiments randomly generate 300 transportation tasks among the workstations,and the experimental results are shown in Table 2.Although the number of deadlock avoidances of CDDA is not much different from that of CDA,29 deadlocks are not successfully avoided.These deadlocks are caused by the existence of bidirectional roads,which causes the robots’ running paths to overlap,resulting in impending deadlocks.In addition,because CDDA cannot avoid impending deadlocks,even if direct deadlocks are avoided,the robots still cannot move forward.The process of unlocking the deadlock increases the time the robot takes to perform the task.It also proves that deadlock avoidance is more effi-cient than deadlock detection and resolution.

Table 2 Experimental results of CDDA and CDA

CDDA spends≥22.43%of the average task time compared to CDA,which is caused by numerous deadlocks being unlocked.Similar results can be drawn from Fig.11.Regardless of the number of tasks,the total task time of CDDA is much higher than that of CDA.So,CDA has better performance.

Fig.11 Relationship between the total task time and the number of tasks with the collision and deadlock avoidance (CDA) algorithm and collision and direct deadlock avoidance (CDDA) algorithm

To study the relationship between the number of deadlocks and the number of robots,we initially set up 300 tasks and count the number of deadlock avoidances with different numbers of robots.Using CDA,the experimental results are shown in Fig.12.It can be seen that when the number of robots increases,the number of deadlock avoidancesalso gradually increases.The increase in the number of robots leads to a rise in the possibility of overlapping paths,making it easier to trigger deadlock avoidance.In addition,there is no collision in all experiments,which means that the collision avoidance algorithm is effective.

Fig.12 Simulation results of the number of deadlock avoidances under different numbers of robots with the collision and deadlock avoidance (CDA) algorithm

4.2 Comparison with other methods

Methods based on zone control are classic and effective for motion coordination in MMRSs.The map of robots is composed of disjoint zones.Each robot has its own zone at every moment,so there will be no collisions among the robots.Deadlock avoidance is achieved by analyzing the sequence of zones that the robots’ paths contain.However,this method is a bit conservative.

For example,in a compact roadmap shown in Fig.13a,using the method in this study,when neither robot is loaded,there are no glued nodes,and both robots can pass normally.Only when the two robots are loaded,do the glued nodes make it impossible for the two robots to pass through at the same time (Fig.13b).However,based on the principle of zone control,there are three zones shown in Fig.13c.This means that the two robots cannot pass through this channel at the same time under any circumstance.

Fig.13 Experimental scene with a compact roadmap:(a) there are no glued nodes when the two robots are not loaded;(b) when the two robots are loaded,there are three pairs of glued nodes GN=1,GN=1,and GN=1;(c) based on the principle of zone control, V2, V3, V4, V7, V8,and V 9 belong to three zones

This study verifies the efficiency of CDA based on a casting production line scenario,where all robots are based on QR code positioning and navigation.Each QR code can be regarded as a node in the roadmap and all edges in the roadmap are bidirectional.As shown in Fig.14,there are 22 workstations,among which robots transport materials.The task of the robot is always to transport materials from one workstation to another.Each task consists of four subtasks: (1)move to a workstation,(2)load cargo,(3) move to another workstation with cargo,and(4)unload the cargo.Robots with no tasks will move to the robot stations and wait for new tasks.Whenever the battery level of a robot drops below a set value (15% in the experiments),the robot will move to a charge station to charge.The parameters of the robots are shown in Table 3.

Table 3 Experimental parameters of robots in the scene shown in Fig.14

Fig.14 An experimental scene of a casting production line

Each set of experiments is set up with 100 tasks,and each task is always assigned to the closest idle robot.The paths of the robots are generated using the A* algorithm with the shortest distance as the goal.We compare the CDA method with the methods in Ma?opolski (2018) (chains of reservations,COR)and Zaj?ac and Ma?opolski(2021)(structural on-line control policy,SOCP).We use the average task time,average robot waiting time,and total mileage of robots to evaluate the performance of different methods.The average task time is calculated using expression (2).The average waiting time is calculated as

wheredenotes the time at whichRjstops and waits while executing TKito avoid collisions and deadlocks.When TKiis not executed byRj,=0.The total mileage is calculated as

whereMi,jdenotes the mileage traveled byRjwhen it executes TKi.When TKiis not executed byRj,Mi,j=0.

Because the number of tasks remains unchanged in each experiment,the average task time reflects the efficiency of different methods.The total mileage represents the energy consumption of the robots.The experimental results with different numbers of robots are shown in Table 4.

Table 4 Experimental results of different methods

The experimental results are similar to those in Zaj?ac and Ma?opolski (2021),and COR and SOCP perform poorly in roadmaps where all edges are bidirectional.CDA is based on the real-time paths of robots to avoid deadlocks and is not affected by bidirectional edges.In terms of the average task time,as the number of robots increases,the advantages of CDA become more and more obvious,as shown in Fig.15.When the number of robots is 6,CDA consumes 34.09% and 41.01% less time than SOCP and COR,respectively.In terms of the total mileage,when using GN,the robot travels fewer miles (less energy consumption)than other methods.As shown in Figs.15 and 16,both the average task time and the average waiting time increase with the increase of the number of robots.This is because the more robots there are in the system,the more traffic congestion is created;thus,the robots are more likely to stop and wait to avoid collisions and deadlocks.

Fig.15 Experimental results of the average task time

5 Conclusions and future work

Fig.16 Experimental results of the average waiting time

This paper begins by describing the concept of glued nodes based on the roadmap.The concept of glued nodes is related to the real-time paths and sizes of robots,and is dynamic and more precise compared to zone-control method.

Then,we propose a hybrid control architecture,by which the robots and the control center interact using the application and authorization of nodes.Theories and methods of collision and deadlock avoidance are proposed based on the concept of glued nodes.We analyze the difference between direct deadlock and impending deadlock,and present collision and deadlock avoidance algorithms.

Finally,we verify the effectiveness of the proposed algorithms in several experiments based on multiple industrial scenarios.Compared with CDDA,CDA can effectively avoid deadlock and improve the efficiency of the system.Compared with the other zone-control methods,CDA shows superiority in terms of average task time,average waiting time,and total mileage.

The proposed method has some limitations,however.It must be calculated based on a roadmap,and it can be applied only online based on real-time robot data.

In the future,we will further study path planning and deadlock unlocking based on the concept of glued nodes.

Contributors

Zichao XING and Weimin WU designed the research.Zichao XING and Xingkai WANG processed the data.Zichao XING drafted the paper.Zichao XING,Xingkai WANG,and Shuo WANG performed the experiments.Ruifen HU helped organize the paper.Zichao XING and Weimin WU revised and finalized the paper.

Compliance with ethics guidelines

Zichao XING,Xingkai WANG,Shuo WANG,Weimin WU,and Ruifen HU declare that they have no conflict of interest.

Data availability

The data that support the findings of this study are available from the corresponding author upon reasonable request.