Shortest Time Path Planning Based On Timed Petri Nets

As an important part of social production and life,road traffic is a prerequisite for the steady development of urban people’s daily life,and also a vital part of social progress.With the continuous development of economic life,urban traffic is facing increasingly fierce conflicts.On the one hand,the demand of urbanization process is increasing in urban development;on the other hand,the problems of road congestion and environmental pollution caused by the increase of vehicle density in large and medium-sized cities have become the key to the healthy development of society factor.Therefore,the research of path planning has very important theoretical and practical significance.In order to meet the efficiency of algorithm calculation in the process of vehicle driving,the shortest time path should be calculated by real-time recalculation using the information received by the vehicle.The classical shortest time path algorithm has its limitations,for example,when the road scenario is complex,the real-time calculation of path planning will result in poor performance,and different parameters will lead to different results.In order to solve these problems,this thesis uses the timed Petri nets to model the urban traffic path,uses the change of the token number in the resource place to represent the congestion degree of the urban traffic path,uses the simple modeling method to represent the complex urban traffic,and proposes two shortest time path planning algorithms based on the reachability graph and the timed Petri nets structure,combining the traffic congestion information returned in real-time,find a shortest time path for every vehicle.As a powerful mathematical tool,timed Petri nets model is widely used in the modeling,analysis and control of transportation.It can be used to analyze the performance of the system and solve the realtime path planning problems.In this thesis,we focus on the shortest time path planning based on timed Petri nets:1.The local urban traffic path is modeled by the timed Petri nets,and the places are regarded as the road paths.The time-delay factor in the place is the travel time through the path,and the tokens in the place are regarded as the vehicles on the road.The transiton enabled represents the selection path,and the change of the token number in the resource place represents the congestion degree of the road.2.Calculate the reachibility graph according to the model,starting from the reachibility graph,this thesis optimizes the heuristic search function of A* algorithm,search and calculate the shortest time path of the vehicle,return the path information in real time with the number of tokens in the resource place,use the appropriate congestion viscosity factor,dynamically change the travel time,and finally select a path from the initial position to the target position for the target vehicle.The shortest time sequence of timed Petri nets is obtained.The feasibility and effectiveness of the algorithm are verified by an example.3.Based on the Petri nets model,starting from the timed Petri nets structure,the heuristic search function is used to plan the path of each vehicle.Then the vehicle is completely distributed on the Petri nets,and the shortest path is found.Finally,the model is transformed into the form of graph,and the simulation of an example is realized by MATLAB programming to verify the correctness of the algorithm.