Simulation and Field Testing of Multiple Vehicles Collision Avoidance Algorithms

Chaoyue Zu,Chao Yang,Jian Wang, Wenbin Gao,Dongpu Cao,Fei-Yue Wang,

Abstract—A global planning algorithm for intelligent vehicles is designed based on the A*algorithm,which provides intelligent vehicles with a global path towards their destinations.A distributed real-time multiple vehicle collision avoidance(MVCA)algorithm is proposed by extending the reciprocal n-body collision avoidance method.MVCA enables the intelligent vehicles to choose their destinations and control inputs independently,without needing to negotiate with each other or with the coordinator.Com pared to the centralized trajectory-planning algorithm, MVCA reduces computation costs and greatly improves the robustness of the system.Because the destination of each intelligent vehicle can be regarded as private,which can be protected by MVCA,at the same time MVCA can provide a real-time trajectory planning for intelligent vehicles.Therefore,MVCA can better improve the safety of intelligent vehicles.The simulation was conducted in MATLAB, including crossroads scene simulation and circular exchange position simulation.The results show that MVCA behaves safely and reliably.The effects of latency and packet loss on MVCA are also statistically investigated through theoretically formulating broadcasting process based on one-dimensional Markov chain.The results uncover that the tolerant delay should not exceed the half of deciding cycle of trajectory planning,and shortening the sending interval could alleviate the negative effects caused by the packet loss to an extent.The cases of short delay(<100 m s)and low packet loss(<5%)can bring little influence to those trajectory planning algorithms that only depend on V2V to sense the context, but the unpredictable collision may occur if the delay and packet loss are further worsened.The MVCA was also tested by a real intelligent vehicle,the test results prove the operability of MVCA.

I.INTRODUCTION

I NTELLIGENT vehicles are expected to solve problems associated with traffic congestion and fuel consumption through automatic driving.The trajectory planning algorithm is one of the core technologies to realize automatic driving.Environmental awareness is an important prerequisite for trajectory planning.Currently,it mainly relies on the recognition capabilities of autonomous sensors and cooperative sensors such as vehicle cameras,lidars,and V2X communications.The camera is mainly based on the feature that the outline of the vehicle is symmetrical,and the vehicle is detected by a camera,but the detection result of this method is easily affected by light,and it is not easy to obtain depth information.If the depth information of obstacles is needed,at least two cameras are needed to photograph obstacles at the same time to obtain a stereoscopic image that includes depth information.However,one of the great disadvantages of using the camera is that the obstacles cannot be perceived when there is insufficient illumination.Usually,the use of thermal imaging cameras at night is better.The lidar emits laser light to the surroundings and measures its return time to obtain distance information.Compared with the camera,the measurement distance is longer,the speed is faster,the error is smaller,and the resolution is higher.However,this method has a limited amount of information and is prone to false positives and missed detections.Vehicle-to-vehicle communication (V2V)technology allows vehicles to share status information (such as speed,position,and yaw angle)with each other, providing new technical means and data sources for environmental awareness.Current advanced heterogeneous vehicular networking technologies can also be employed to support pervasive connections between vehicles[1].And with the development of big data,the combination of internet of vehicle and big data will enhance internet of vehicle in terms of network characterization,performance analysis and protocol design [2],this is conducive to the development of intelligent vehicles.

European Telecommunications Standards Institute (ETSI)defines two environment-aware message standards:cooperative awareness message (CAM)[3]and decentralized environmental notification message (DENM)[4].The CAM periodically broadcasts messages(including position,direction,acceleration,etc.)to surrounding vehicles on the control channel.DENM is only sent under dangerous conditions,such as sudden braking.The definition of these messages takes into account the size of the information payload and the estimation of network congestion,which facilitates upper-layer applications such as trajectory planning.Taking a CAM message as an example,the timing of generating a CAM message satisfies one of the following conditions:The maximum time interval between CAM messages is 1 s;the minimum time between CAM messages is 0.1 s;the yaw angle of the vehicle varies by more than 4 degrees;the current position coordinate of the vehicle changes more than 5 m;the current speed of the vehicle changes by more than 1 m/s.It can be seen that CAM messages are very sensitive and accurate.The use of vehicleto-vehicle communication to perceive traffic flow has some unique advantages:first of all,communication increases the range of perception farther,and it can perceive the traffic flow outside the line of sight,which cannot be achieved by cameras or radars;second,the accuracy of state information shared by all vehicles is greatly improved,this is because all state information is collected by on-board sensors and then shared with other vehicles.Reference [5]has shown that the safety level of a vehicle platoon can really benefit from inter-vehicle communication even when the communication penetration rate is unsaturated.Compared with other techniques such as machine vision,the state accuracy is greatly improved;moreover,the cost of the communication device is much less than the cost of a 360-degree camera and lidar arranged around the vehicle.

The main contributions of this paper are as follows.1)A destination oriented global planning algorithm is designed for intelligent vehicles based on A?algorithm.2)A distributed real-time trajectory planning algorithm (multiple vehicle collision avoidance,MVCA)is proposed to enable multiple intelligent vehicles to avoid each other.The advantage of the algorithm is that it allows the intelligent vehicles to independently determine their destinations and control inputs without negotiating with each other.3)The algorithm is verified by MATLAB simulation,and based on inter-vehicle communication,the algorithm is simulated under the condition of large traffic flow.4)The impact of vehicle delay and packet loss on MVCA.It is found that the delay time should not exceed half of the cycle of the trajectory planning algorithm.In the case of a constant packet loss rate,by reducing the packet transmission interval,the negative impact of packet loss on trajectory planning can be mitigated to some extent.In the case of low delay(less than 100 ms)and low packet loss rate(less than 5%),delay and packet loss do not have a great impact on the trajectory planning using only the inter-vehicle communication,however,in the case of high delay and packet loss rate,intelligent vehicles may experience unpredictable collisions due to their inability to timely sense the latest traffic flow information.5)The MVCA was tested by a real intelligent vehicle.The intelligent vehicle runs according to the trajectory planned by the algorithm.The test results prove the operability of MVCA.Based on the above discussion,the remaining sections of this paper are carried out.

II.RELATED WORK

This section introduces commonly used types of trajectory planning algorithms and their advantages and disadvantages.It then compares the differences between existing methods and the MVCA.

A.Graph Search

If the degrees of freedom of the robot aren,then the robot should have ann-dimensional configuration space C-space,the secure part of the C-space to remove the obstacle is C-free,and a graph search[6]through the formation of a variety of curves connected to the entire C-free.When the appropriate curve is constructed in C-free,the whole C-free becomes a connected graph,and certain methods can be used to find the shortest safe path,such as Djikstra’s algorithm.However,the main disadvantage of the graph search method is that it is necessary to obtain the global information of the whole environment in advance.In addition,as the degrees of freedom of the robot increase,the time complexity of the construction map will rapidly increase.

B.Grid Method

The grid method [7] recursively decomposes the C-space into smaller grids,all of which are mutually connected and not duplicated.this method is very suitable for the computer to express the surrounding environment information,and is often used in conjunction with the graph search method.The grid method is divided into the exact grid method [8]and the approximate grid method [9].The exact grid method decomposes free space into multiple shapes of variable grids,all of which are combined exactly equal to the original Cspace.However,in order to perform the lossless division of the C-space,the exact grid method is often less efficient and difficult to realize.In order to reduce computation costs,the approximate grid method defines simple shapes as grid elements,usually rectangles or squares.The entire C-space is divided into multiple squares or rectangles,each of which is connected,fitting the actual environment with predefined simple shapes.Errors are inevitable and depend largely on the granularity of the gird subdivision.with the increase of the C-space,the number of grids increases exponentially,which is the main limitation of this method.

C. Artificial Potential Field

The artificial potential field method was first proposed by Khatib[10].The method treats the motion of a robot in the environment as moving in an artificial force field.The target will apply“gravity”to the robot,and the obstacle will produce a “repulsion”from the robot.Finally,the motion of the robot is controlled by the forces of gravity and repulsion.The target is assigned the minimum global potential energy,the obstacles are assigned higher potential energy,and the robot moves toward the lowest potential point (target)on the potential plane.There are many cases of trajectory planning using the artificial potential field method.Wolf and Burdick[11]proposed a series of potential field function components to help automatic or semi-automatic vehicles navigate on the expressway.The general potential field function consists of many independent potential field functions,including lanekeeping,speed preferences,vehicle avoidance,overtaking,etc.However,they lack consideration for vehicle kinematic constraints.Rossette and Gerdes completed the lanekeeping and vehicle-following functions using the artificial potential field method [12]?[14].Ge and Cui’s method[15]is based on the artificial potential field method,taking into account both the obstacle and the target in motion.The planner not only considers the position of the robot relative to the target and obstacle,but also the relative speed of the robot to the obstacle and target.The artificial potential field method is very attractive because of its simplicity and beauty in mathematics,but this method has the following limitations:

1) When two obstacles are very close,there may be situations when the robot cannot pass through the narrow channel,or there may be a wobble.If the target,robot,and obstacle are in a straight line,the robot may move back and forth in the straight line such that it cannot reach its destination.

2)If the obstacle is very close to the target point,it may be impossible to reach the destination because of the excessive repulsion force of the obstacle.

3)When there are numerous obstacles,the robot may be trapped at the local minimum point of the potential plane during the process of approaching the target,which will prevent the robot from ever reaching its destination.

D. Artificial Neural Network (ANN)

The artificial neural network (ANN)is a technique based on a nonlinear mapping system.The design principle is to set up many one-mapping relations between multiple inputs and outputs of the system.The greatest feature of ANN is that it has a so-called learning process,which is essentially an algorithm that helps the neural network find parameters to match the input and output.In general,these parameters are computed by recursive calculations of given inputs and outputs.This process will be repeated until better parameters are generated for a given set of data.The ANN includes a feedforward neural network and feedback neural network.In feedforward neural networks,each neuron starts from the input layer,accepts the previous level input,and then sends to the next layer until reaches the output layer.There is no feedback in the whole network.Each neuron in the feedback neural network feeds its own output signal back to the other neurons,and it needs to run for a period of time to achieve stability.A popular approach to training feedforward networks is to use reverse propagation.The state space of the neural network is the configuration space of the robot C-space.The destination will attract the robot,while the obstacle will partially reject it.

E.Genetic Algorithm

A genetic algorithm (GA)is a numerical optimization method inspired by natural selection and heredity.Genetic operations include the selection operator,crossover operator,and mutation operator.The selection operator selects the better individual from the group,and eliminates undesirable individuals.The better individual can be inherited by the next generation,or through the crossover operator to generate new individuals.The selection operation is based on fitness,and fitness represents the probability of the individual being selected in the population.The crossover operator is the reorganization of two existing individuals.The basis for crossing is the crossing rate;crossover operators can randomly exchange genes among individuals in a population,and combine beneficial genes together according to different encoding methods,including discrete reorganization,intermediate reorganization,and so on.The mutation operator first determines whether all individuals in the population change or not,based on prior probability of variation;then,the mutant individuals are randomly selected for position variation.The mutation operator endows the genetic algorithm with local random search ability.In addition,it is beneficial to maintain the diversity of the population to a certain extent in order to avoid premature convergence.The genetic algorithm starts from the set and the search surface is large,which is advantageous to global selection;at the same time,it has the characteristics of self-organization and self adaptation.But the disadvantages of GA are its premature convergence and low efficiency.

F.Comparison Analysis

Basically,the above algorithms for single intelligent vehicle avoidance can be modified for use with multiple intelligent vehicles.But considering the increase in the number of intelligent vehicles,it is necessary to make the whole system highly practical to ensure that multiple intelligent vehicles can avoid collision.At the same time,considering the human-centered intelligent,the application scope of intelligent algorithm in local planning has great limitations[16].For the graph search method,when there are multiple intelligent vehicles,the global information of the whole environment is changing,so path planning in a dynamic environment with moving obstacles is more difficult.In order to overcome the limitations of the grid method and the artificial potential field method,a series of improved algorithms are proposed [17]?[19], however,they do not yet have good real-time performance for the dynamic trajectory planning of multiple intelligent vehicles.Existing methods of multiple intelligent vehicles trajectory planning can be broadly divided into central and distributed.Compared with the central planning algorithm,the distributed algorithm can easily respond to unknown and dynamic environmental changes in real time.Moreover,it usually has higher reliability,extendibility,adaptability,and robustness.However,the solution may be suboptimal.Nevertheless,we believe that the distributed algorithm has wider application prospects.This is mainly because the central trajectory planning algorithm needs to assume that there is a highly computational central node for all intelligent vehicle planning trajectories.with the increase in the number of intelligent vehicles,the computational costs of the central node will increase rapidly.Moreover,there is a certain delay when the control command is sent from the central node to the robot,which undoubtedly brings real-time challenges.If the central node fails,all intelligent vehicles will cease to work.

Chen and Li[20]proposed a method for multiple robot cooperative planning trajectories.Compared with a single robot,the average energy consumption of multiple robot cooperative planning trajectories is much lower than that of the former.The method assumes that all robots form a group,where one robot represents the coordinator and the others act as members of the group.They communicate via wireless devices,and the coordinator is like a conductor who commands other members to reach the target.The contents of transmissions include each robot’s location,starting point,destination,and surrounding environment information.The coordinator receives the information and then decides which one to send to each member.The disadvantage of this method is that each member’s decision needs to be sent by the coordinator himself,and it is necessary to consider whether the decision information has the ability to meet real-time requirements.At the same time,the central coordination mechanism gives the system poor robustness.The amount of information exchanged by multiple robots in avoidance is also an important factor,although vehicle-to-vehicle communication provides convenience for the interaction of multiple intelligent vehicles.However,in order to avoid the frame collisions caused by competition channels,the amount of information exchanged between multiple intelligent vehicles still needs to be as small as possible.Information such as destinations is also private information and should not be sent to other people.

In summary,this paper attempts to design a distributed realtime trajectory planning algorithm for intelligent vehicles that exchanges as little information as possible.

III.PATH PLANNING METHOD

To ensure that multiple intelligent vehicles can avoid each other and arrive at their destinations,each intelligent vehicle needs to have global path planning and local path planning abilities.Global path planning enables the intelligent vehicle to find the global optimal path to the destination.Local path planning enables the intelligent vehicle to react to the surrounding traffic flow,thus avoiding other intelligent vehicles.In addition,the intelligent vehicle is a typical nonholonomic system,and the nonholonomic kinematical constraints of the intelligent vehicle need to be considered.In order to create an intelligent vehicle with real-time response ability,MVCA adopts the idea of rolling planning,which requires constant iteration in each cycleTTT1,TTT2,...,TTTk.Assume that each intelligent vehicle can accurately sense the current position and status information of other intelligent vehicles or obstacles.Then,within a cycleTk,each intelligent vehicle repeats the following actions in sequence:

1)Set your destination and get the speedvglobalyou want to take by the global planning algorithm.

2)Perceive the position information of other vehicles.

3)On the basis ofvglobal,the local planning algorithm is used to get the speedvlocalin order to avoid collision with other vehicles.

4)Calculate the amount of control and trajectory generated by the tracking speedvlocal.

In order to help readers understand the technical background of MVCA,this paper first introduces the tracking control problem based on a vehicle dynamics model and provides the digital simulation results.Then,the global and local planning algorithms are described in detail.Finally,the simulation results of trajectory tracking and avoidance algorithms for multiple intelligent vehicles are given at the crossroads and circular interchange.

A.Trajectory Tracking

1)Kinematic Trajectory Tracking of Intelligent Vehicle:Considering the nonholonomic system of an intelligent vehicle,a simple vehicle model is assumed,as shown in Fig.1.In order to facilitate the analysis,the vehicle is assumed to be circular,its radius isr,its front wheel is the steering wheel,and its rear wheel is the driving wheel.The distance between the front and rear axles isd,the yaw angle is expressed byθ,and the steering wheel angle is expressed byφ.

Fig.1.Vehicle model.

From Fig.1,we can see that the kinematic equation of the vehicle is

whereu1is the angular speed of the driving wheel,andu2is the angle change rate of the steering wheel.The two parameters can be passed to the controller as control quantity.The range of the yaw angleθis[0,2π],and the range of the wheel angleφis limited to(?π/2,π/2).

2)Trajectory Tracking of Intelligent Vehicle:Because the vehicle is a nonholonomic system,considering the kinematic characteristics of the vehicle,it is necessary to track thevlocalof the vehicle.By analyzing the tracking error,the amount of control required for actual tracking can be obtained.Based on a parametric polynomial method [21],this paper presents a strategy for intelligent vehicle tracking and analyzes the tracking error.This tracking algorithm can also apply to other trackers.

Murrayet al.[22],[23]showed that the kinematic constraints of the vehicle can be mapped to the chain system,and the vehicle trajectories can be represented by polynomials by means of chain transformations[24].A six-order polynomial[21]is used to represent a cluster of possible vehicle trajectories

Obtained from (1)

The traditional A?algorithm uses the grid method to segment the environment,and the starting coordinates and destination coordinates are denoted as point (x,y)in the two-dimensional plane.Considering the orientation of the intelligent vehicle at the end position and the starting position,we introduce the triple point (x,y,θ)as the representation of the starting point,destination,and orientation of the intelligent vehicle (i.e.,yaw angle),respectively.However,there is a problem with using the grid method to segment the 3D Cspace,that is,(x,y,θ)can only take certain predefined discrete values.If the granularity of segmentation is too fine,then this will lead to a large increase in time complexity.If the granularity of segmentation is too rough,then the actual best path cannot be found.By sampling ideas,collecting all the sample positions that the intelligent vehicle can achieve in the next cycle,and joining the OPEN instead of dividing the environment,the extended nodes of each layer of the A?algorithm are the possible tracking speeds of the intelligent vehicle,that is,the small fan-shaped region in front of the intelligent vehicle.

The point at which the A?algorithm extends each time is the line segment from the current node to the new leaf node.This line segment is actually the candidate tracking velocity,and this velocity is tracked using the tracking trajectory in Section III-A.If the tracking error causes the intelligent vehicle to collide with the obstacle,then the node is considered unreachable and is canceled from the OPEN table.However,considering the computational overhead,it is impossible to calculate the trajectory and tracking offset every time the node is extended.Thus,in order to calculate off line the maximum tracking offset at the current velocity,we need to determine whether the distance between the line segment,which is between the parent node and the new node,and the static obstacle is greater than the maximum tracking offset.

h(n)isdefined as the distance between any two positions of the extended node(x0,y0,θ0)and (xf,yf,θf(wàn)).As the traditional Euclidean distance cannot properly reflect the distance between the two triples,we use Dubins distance to computeh(n)in order to take full account of the nonholonomic constraints of intelligent vehicles.In order to use Dubins distance,we first need to calculate the maximum turning radius of intelligent vehicle wheredrepresents the wheelbase of the intelligent vehicle,δmaxrepresents the maximum front wheel angle of an intelligent vehicle.LetLstands for left turn,Rstands for right turn,andSstands for straight line operation.Then,only the following six combinations of the path may be the shortest possible paths[25]

Therefore,we only need to choose the shortest among the six trajectories.Fig.6 shows the Dubins distance between the starting position (0,1,0)and the end position (7,9,?π/4).It can be seen that even though the straight distances of the two position coordinates are close,the intelligent vehicle sometimes has to use a longer trajectory in order to complete the yaw and angle constraints of the start and end positions.Therefore,the advantage of using Dubins as a heuristic functionh(n)for the extended nodenis revealed:using the Dubins distance as the heuristic functionh(n)allows the global planner to consider not only the straight-line distance between two points,but also the kinematic constraints of the intelligent vehicle.When the improved A?algorithm searches the feasible path of the target,it returns the velocity of the extended nodes to that in the first layer of the A?algorithm because the nodes on the first layer represent the global speed that the intelligent vehicle should take immediately in the next cycle.Another task when selecting the global planner is that when the A?algorithm fails to find a feasible solution,this means that the destination is unreachable and the planner should request for another destination or make the intelligent vehicle stop and wait.

Fig.6.Dubins trajectory and distance.

C. Local Planning Algorithm

D.Simulation Experiment

1) Intelligent Vehicle Tracking Algorithm:The starting position of the intelligent vehicle is(x0,y0,θ0,φ0),and the target position is(xf,yf,θf(wàn),φf(shuō)).The maximum tracking errorterrormaxis defined as the maximum distance difference between the polynomial trajectoryyand the straight line connecting the two points(x0,y0)and (xf,yf)

In MVCA,the final state in which the intelligent vehicle tracks the new velocity always keeps the yaw angle consistent with the new velocity direction.Thus,for any new velocityv=(vx,vy),the target position of the intelligent vehicle can be calculated as

In Fig.13,the starting position of the intelligent vehicle is(0,0,0,0),and the end position is(x,y,arctan(y/x),0).(x,y)is located in a circular area as shown in the figure;it is obvious that the error is minimized when the intelligent vehicle tracks the velocity in a small fan-shaped area in front of it.In fact,because the choice of the new velocity is as close as possible to the original velocity,in the vast majority of cases,the new speed falls within the dark blue fan-shaped area.However,in order to ensure full collision avoidance,a maximum tracking error is added to the radius of each intelligent vehicle to ensure that it never collides.This value is set to 0.7 m.In Fig.13,the maximum value of the cross axis is 5,which means that within a cycle (0.6 s),the intelligent vehicle moves forward by no more than 5 m(30 km/h).For higher velocity requirements,this method can be used to calculate the corresponding tracking deviations from the maximum distance and then applied to the intelligent vehicle radius.

Fig.13.Maximum tracking error.

Because the ORCA algorithm itself is designed for the integrity of the robot,it is necessary to consider the possibility of planning the backward velocity in the new cycle.If we want the intelligent vehicle to avoid reversing,we can simply turn the circle in Fig.9 into a semicircle.Since the choice of new velocity is very close to the velocity of the original cycle,even if not to shield the backward velocity,no backward appeared in a large number of experiments.

2) Multiple Intelligent Vehicle Avoidance Algorithm:The experimental parameters areTstep=0.6 s,τ= 5 s,r=1.5 m,andterrormax=0.7 m.Figs.14 and 15 show the results of two representative experiments,one is a typical crossroad to automatically avoid,and the other is the case where all intelligent vehicles in a circular symmetrical distribution exchange positions.Because the maximum tracking error is added to the radius of each intelligent vehicle,on the premise of accurately perceiving the position and velocity of other intelligent vehicles,all intelligent vehicles will not collide.

A trajectory of the typical crossroads is shown in Fig.14.Snapshots of different times are given in the simulation experiments.Using the proposed MVCA,all vehicles are avoided in accordance with predefined behavior.No additional communication and central coordination mechanism are needed.The number of vehicles involved in avoidance can be arbitrary;in fact,becauseτ=5 s,not all vehicles are involved in each perceived avoidance trajectory calculation.Assuming that the distance between intelligent vehiclesBandAis greater than the sum of the maximum velocities allowed multiplied byτ,it is certain that they will not collide within 5 s.Also,as can be seen from Figs.14 and 15,the trajectory of the intelligent vehicle is smoother and more comfortable.The experimental results of the circular symmetrical distribution exchange positions are shown in Fig.15.The figure shows that the MVCA algorithm can safely ensure that multiple intelligent vehicles avoid each other and reach their destinations.Moreover,the trajectory of each intelligent vehicle is very smooth and conforms to the constraints of vehicle kinematics.with accurate perception of all obstacles and moving vehicles,the MVCA algorithm guarantees no collisions.

IV.SIMULATION EXPERIMENT BASED ON INTER-VEHICLE COMMUNICATION

A large number of experiments have been carried out to verify the security and reliability of the MVCA,but the result is based on a hypothesis that the external state information of all intelligent vehicles is accurately perceived.To satisfy this assumption,the inter-vehicle communication technology is introduced and the statistical relationship between the collision rate,network delay and packet loss rate is discussed.

A.Communication Modeling

This paper focuses on time-triggered periodic state broadcast CAM aware traffic flow.Not only communication safety of vehicles requires information to be delivered,but also the important safety information has strict requirements on time,and they should enjoy a higher priority.IEEE 802.11p uses the EDCA mechanism and defines four different access categories(AC),and the difference between each AC is that it has different media access parameter sets,such as AIFS and contention window.The AC with the minimum AIFS and contention window will have more opportunities to access the channel.The CAM information is sent through AC3 to ensure that it occupies an advantage in the internal competition mechanism of EDCA,therefore,the internal competition of CAM messages is ignored in the experiment,directly considering the external competition and assuming that the channel is saturated.CAM can be considered to be generated by each vehicle at the frequency of 10 Hz,and then broadcasts to the surrounding vehicles.All vehicles need to compete the channel transmission rights in the form of CSMA/CA.Since the broadcast does not have retransmission process,the broadcast message can be modeled using the one-dimensional Markov chain[27].As shown in Fig.16,the ellipse represents the state when the backoff counter is at a certain value.

Fig.14.Crossroads scene simulation.

Fig.15.Circular exchange position simulation.

Sirepresents the probability of the corresponding value of the backoff counter of the channel where the CAM is located,it is evident that

Fig.16.One-dimensional Markov chain model for back-off counters.

According to the state transition relationship shown in

B.Trajectory Prediction

Because the CAM package inevitably causes delay and packet loss,the perceived information is often lagging.If the MVCA is applied to a vehicle-to-vehicle communication environment,it is inevitable that the trajectory is predicted.Unlike previous estimation algorithms to eliminate uncertainty,the state reflected by CAM messages has a very high credibility.Because these state information is collected by the sensors of the vehicle itself,not by other vehicles,the reason for inaccurate information is mainly the time lag.In general,the CAM delay will not be long,even in the case of packet loss.It can be assumed that the rate of change of the vehicle’s speed and trajectory curvature is constant over a short period of time.Remember that a short period of time ist,the forward movement distance of the vehicle isS,and the rate of change of the yaw angle is ˙K(S)

C.Simulation Experiment

Table I shows the physical quantities involved in the simulation experiment.

TABLE I SIMULATION PARAMETERS

Two scenes were selected:an intersection where the vehicles were relatively even distributed (Fig.17)and an intersection with a relatively large oncoming traffic flow(Fig.18).The process of sending and receiving CAM messages is simulated by C++,and the delay and packet loss rate are obtained by the model in Section IV-A.As each intelligent vehicle begins to plan a local trajectory,it retrieves all CAM messages it has received and selects the latest CAM message.By comparing the CAM timestamptCAMwith the current global timetglobal,the delay timetlatencyof the CAM packet can be obtained according to(53)

Fig.18.The trajectory planning of the MVCA based on inter-vehicle communication at an intersection with a relatively large oncoming traffic flow.

The curvature and slope of the trajectory largely change during the early and middle periods of the tracking cycle,but the changes of the later tracking cycle are small,this makes the assumption of constant change in curvature very relevant to reality.And because the CAM message is very accurate,in addition to the MAC design for inter-vehicle communication,according to the experimental results,moderate packet loss and delay will not have a great impact on the trajectory planning.As shown in Figs.17 and 18,the intelligent vehicles have been able to avoid each other in the presence of delay and packet loss.

In order to further evaluate the impact of delay and packet loss on trajectory planning,adjust the delay up to 450 ms and the packet loss rate up to 30%.The experimental scene is a 200 m×200 m barrier-free environment.There are more than 60 intelligent vehicles in this environment.Their starting positions and end positions are randomly generated.The result obtained is the average value of multiple experiments.A random experiment scene is shown in Fig.19.

Fig.19.Experiment scene.

In Fig.20,the packet loss rate is calculated using an empirical model(45)?(47),and the cycle time of the algorithm MVCA is 0.6 s.It can be seen that it is accurate to assume that the change of the vehicle’s velocity and the change rate of trajectory curvature is constant in a short time domain.No collision occurs when the delay is less than 100 ms,when the delay increases to more than 300 ms,the number of collisions increases sharply.Taking Fig.21 as an example,suppose that the position of an intelligent vehicle is(0,0,π/6,0),and it is expected to arrive (10,0,0,0)after 0.6 s.The arrows in the figure indicate the corresponding state of the intelligent vehicle which receives the latest broadcast packet when the delay takes the corresponding value.It can be seen that the trajectory of the intelligent vehicle consists of two parts,each is located on the side of the speed vehicle wants to track.In most cases,the dividing line between these two parts is half of the algorithm MVCA cycle,that is 300 ms.It can be seen that the delay is between [300 ms,600 ms],and the closer to 600 ms,the vehicle’s broadcast state received is closer to the old state of the vehicle.The delay is between [0 ms,300 ms],and the closer to0 ms,the vehicle’s broadcast state received is closer to the new state of the vehicle.Therefore,the success rate for predicting with a delay in the range [0,300 ms]is higher than the former.Moreover,for the trajectory of Fig.21,if a packet with a delay greater than 300 ms is used,a more accurate estimate cannot be obtained.Because there will be greater changes in the rotational angle of the intelligent vehicle afterwards,this is the method that assumes that the curvature change rate of the track is constant cannot be predicted.The cycle time of the MVCA algorithm is 0.6 s,which may vary with different algorithms.However,too short cycle time will bring huge computing time,and too long cycle time will not guarantee that the intelligent vehicle can respond to the changing traffic flow in real time.Regardless of the value of the cycle period,any tracking algorithm needs some time to complete the follow-up of the required speed.Therefore,based on this,our conclusion is that the delay time should not exceed half of the cycle of the trajectory planning algorithm,because more than half of the delay of the broadcast message is closer to the state of the intelligent vehicle,and the utilization value is very low.

Fig.20.The effect of delay on the performance of MVCA algorithm.

Fig.21.The relationship between the delay and the state of the intelligent vehicle.

In Fig.22,the delay is calculated based on the model of Section IV-A and the number of intelligent vehicles,and the packet loss rate is used as a tunable parameter. When a vehicle’s broadcast is lost,other vehicles will think that the vehicle has lost packets instead of thinking that the vehicle does not exist,that is,using the latest CAM message that already exists in the vehicle to predict.It can be seen that as the packet loss rate continues to increase,the average number of collisions also increases.This is because packet loss affects other vehicles receiving the latest status data.It can also be seen from Fig.22 that in the case of a constant packet loss rate,by reducing the packet transmission interval,the adverse effect of packet loss can be mitigated to some extent.

Fig.22.The effect of packet interval and packet loss rate on MVCA algorithm.

The above experiments also show that even under high vehicle density,the IEEE 802.11p mechanism is capable of providing a low latency and packet loss rate environment for workshop security information sharing.In the case of low delay(less than 100 ms)and low packet loss rate (less than 5%),delay and packet loss do not have a great impact on the trajectory planning using only the inter-vehicle communication,however,in the case of high delay and packet loss rate,intelligent vehicles may experience unpredictable collisions due to their inability to timely sense the latest traffic flow information.Since trajectory planning based on intervehicle communication inevitably results in packet loss and prediction errors,therefore,it is difficult to develop a 100%collision avoidance algorithm.Therefore,in order to make the best use of the benefits of inter-vehicle communication,it is necessary to study sensing technologies about a variety of sensor information fusion (such as the combination of lidar and inter-vehicle communication).If the distance between the vehicles is very close,packet loss and delay will have a great impact on the safety performance, but this effect can be compensated by traditional sensors.If the distance between the two vehicles is very long,the effect of packet loss and delay will be negligible.At this time,the global nature of the trajectory planning does not require very accurate state information.The disadvantage of packet loss and delay is far less than the advantage of perceiving danger outside sight distance.

V.REAL VEHICLE TEST

MVCA can realize the collision avoidance of multiple intelligent vehicles,but this paper only carries out real vehicle test for a vehicle,and is not based on CAM communication perception.The intelligent vehicle (Fig.23)tested by the algorithm obtained the latitude and longitude information of the vehicle through the RT3002.The obstacle information in the moving direction of the vehicle was obtained through the Velodyne Lidar above the vehicle.The information on obstacles and the latitude and longitude of the vehicle were input into the algorithm.The corresponding target node was set at a certain distance,the algorithm generated the location coordinates and velocity at the next time,and the information was sent through the controller area network (CAN) bus to the control module,which performed the policy through this information,mainly to control the accelerator pedal and steering wheel angle.

Fig.23.The intelligent vehicle.

A.Offline Testing

In order to ensure the reliability of the algorithm,an offline test was conducted before testing on the vehicle.The main method of offline testing was to simulate the CAN signal input through the P-CAN,which will be used as the coordinate of the current position of the intelligent vehicle.Then,the target position coordinates were set.For obstacle information,a certain amount of data was first taken by the Velodyne Lidar and then run in an offline mode(Fig.24),and the obstacle took four vertex coordinates as input.The coordinates and velocities of the next cycle were generated through the P-CAN,and the data through MATLAB for plotting.The corresponding trajectory is shown in Fig.25,which includes avoidance of obstacles.

The starting coordinate is(?75,?55),the target coordinate is(65,60),and the four vertex coordinates of the obstacle obtained from offline data are(0,0),(0,2),(3,0),and (3,2).

B.The Result of Real Vehicle Test

In the intelligent vehicle technology system,accurate autonomous positioning plays a major role.The experimental intelligent vehicle obtains longitude latitude information through RT3002 and transfers it through the CAN bus.Because changes in the latitude and longitude are minimal when the vehicle is running,it is necessary to convert the latitude and longitude information into geodetic coordinates.In the following,the geodetic coordinates have been considered.Environment perception is an important prerequisite for trajectory planning.In the experiment,Velodyne was used as the basis of environmental perception.The obstacles in the experiment were shown through the Open CV visual library,and the obstruction appeared as a rectangle.In testing,target points were set at equal distances;when the distance between the current position and the target position was less than the set threshold,the target point was updated to the next target point,rolling operation.The position coordinates and speed were sent to the control module through the CAN bus,and the control module performed control.

Fig.24.Off-line test by Velodyne.

Fig.25.Avoidance trajectory.

Next,we chose a road in a school as the test section;the starting point and end point are shown in Fig.26.We also set the corresponding starting and ending information in the algorithm,and then obtained the obstacle information through environmental perception.We planned the location of the next time by algorithm,and sent it to the controller for execution control.

Through the test,we obtained the actual trajectory of the vehicle given by the MVCA algorithm as shown in Fig.27.We can see that the trajectory of the algorithm planning is the same as expected,which shows the effectiveness and operability of the algorithm.

As shown in Fig.28,the heading angle of the vehicle is given.

Fig.26.The test section.

Fig.27.The trajectories.

Fig.28.The heading angle.

Finally,as shown in Fig.29,several photos of the vehicle in the actual test are given.

V I.CONCLUSIONS

Fig.29.The vehicle in the actual test.

This paper presents the trajectory planning algorithm MVCA that enable multiple intelligent vehicles to avoid collision.In addition to the vehicle’s own CAM message,the algorithm does not need to exchange additional information with other vehicles,there is no central coordination mechanism and it can support a large number of intelligent vehicles to avoid safely.The algorithm was simulated by MATLAB,and the simulation results show that the MVCA algorithm is safe and effective.By modeling the delay of the car broadcast message CAM,it is proved that the MVCA can be applied to the avoidance of multiple intelligent vehicles under the inter-vehicle communication environment with less delay and packet loss,and evaluated the impact of other indicators such as packet transmission interval,packet loss rate and broadcast delay on MVCA algorithm.It is found that the delay time should not exceed half of the cycle of the trajectory planning algorithm.In the case of a constant packet loss rate,by reducing the packet transmission interval,the negative impact of packet loss on trajectory planning can be mitigated to some extent.In the case of low delay (less than 100 ms)and low packet loss rate (less than 5%),delay and packet loss do not have a great impact on the trajectory planning using only the inter-vehicle communication,however,in the case of high delay and packet loss rate,intelligent vehicles may experience unpredictable collisions due to their inability to timely sense the latest traffic flow information.The algorithm was also tested in a real vehicle,and the test results demonstrate the operability of the algorithm.

The next step is how to complete the perception fusion of multi-sensors(such as cameras,lidars,inter-vehicle communications,etc.),to better utilize the ability of inter-vehicle communications to obtain information from outside of sight distance,and design a global planner that can help intelligent vehicles avoid congestion,and based on the above to conduct the real vehicle test for multiple intelligent vehicles.