外文翻譯--基于dubins路徑的智能車輛路徑規(guī)劃算法研究 英文版

1、<p>　　s’ path planning algorithm based on the Dubins Path</p><p>　　Song Guo-Hao,Huang Jin-Ying,Lan Yan-Ting</p><p>　　(School of Mechanical and Power Engineering, North University of China T

2、aiyuan,030051)</p><p>　　Abstract—The path planning is one of the core issues of intelligent vehicles. All paths can be decomposed into Dubins path. This paper did sectional research into the intelligent vehi

3、cles’ travel path under the idea of Dubins path and carried out tests on the execution performance of the algorithm using PID control strategy. Researches showed that this algorithm could calculate the veh

4、icles’ shortest path, reduced the vehicles’ path length, shortened the driving time, reduced the computation amo</p><p>　　Index Terms—Intelligent Vehicles, path planning,Dubins path, the shortest path.

5、</p><p>　　INTRODUCTION</p><p><b>　　P</b></p><p>　　ATH planning is used in many fields, such as: military unmanned aircraft, space exploration robot, intelligent vehicle,

6、 surveillance and reconnaissance and so on[1-3]. Path planning is a hot area of research in the field of modern vehicle, which needs to consider many factors, such as: constraints from vehicle itself, constraints of driv

7、ing environment and other issues. In the planning of driving route, we should plan out of the scope of vehicle as far as possible under the premise of safe drivi</p><p>　　There are many related research of p

8、ath planning. Such as the Tentacle Algorithm proposed by Zhang Minghuan, et al[6]. This algorithm planned the route that the vehicle will driving at first, let the vehicle driving according to the planned 16 * 81 usable

9、routes. In this way, the vehicle could save a lot of reaction time, but it was not able to handle mutation, and the research background was too idealistic. Wang Kai, et. al[7]. proposed the improved-artificial potential

10、field method. This algor</p><p>　　This paper did research into the intelligent vehicle’ travel path under the idea of Dubins path. This algorithm can well decide out of the optimal path when drivin

11、g on the road and can solve the problem of the obstacle avoidance between many obstacles. This algorithm has good real-time performance and small delay. </p><p>　　The Choice of Paths</p><p>　　Th

12、e main purpose of path planning is to seek a safe and fast driving route, and make the vehicle driving to the end. Generally speaking, vehicles driving in the area of the known or partially known areas, which means areas

13、 with some static obstacles. Now, we use P(x,y,θ,v,a) as driving states,(x,y) as driving position. Parameters in (θ,v,a) respectively represent driving deviation angle, speed and acceleration. If we put the path of the v

14、ehicles driven from the starting point P0 to the ending po</p><p><b>　　(1)</b></p><p>　　In it, R (q) is the produced path, q is one of the parameters of path, which indicates the len

15、gth variable in the path (0≤q≤s)) or angle variable in the path (0≤q≤θ).The specific value of q depends on the driving condition.</p><p>　　The detailed description is as follows:</p><p><b>

16、;　　(2)</b></p><p>　　When the vehicle meeting with obstacles in the driving process, we can make the vehicle bypass obstacles by changing parameters of control system(θ, v, a) timely.</p><p&g

17、t;　　The vehicle is constrained by other constraint condition in the driving process, except to the known obstacles, such as: the minimum time, the minimum path. Use ψ as constraint condition, the path can be expressed as

18、:</p><p><b>　　(3)</b></p><p>　　The control principle diagram is shown below:</p><p>　　Fig.1. The control principle diagram</p><p>　　The kinematics charact

19、eristics and the current state of the kinematics model in the path planning under the two degrees of freedom can be expressed as</p><p><b>　　(4)</b></p><p>　　In the above formulas, v

20、 is the vehicle speed, θ is the horizontal angle, ω is the vehicle rotation angular velocity.</p><p>　　The path constraint condition is one of the important factors that must be considered when driving. The

21、two important constraint conditions of vehicle path planning is the feasibility and safety. The problem of avoiding car collision in the process of driving can be expressed as ,. , is the position of the vehicle itself

22、. , is the position of the obstacles the vehicle monitoring. , is the safe distance of the horizontal and vertical, respectively. The constraint issues of the path planning ca</p><p><b>　　(5)</b>

23、;</p><p>　　What we hope is the vehicle can steer around obstacles and eventually return to the original orbit. The path of the vehicle can be simplified as Dubins path: a circular path (C path) or two tangen

24、t arc path (CC path) or two arc through a common tangent line connection path (CLC). This is the shortest path between the two points Dubins prove[9], C is arc section, L is the line segment tangent to the arc segment. I

25、t can be seen that the last path contains the first two path. This paper studies the</p><p>　　Fig.2. the CLC path geometry figure</p><p>　　The length of the vector and is expressed as the ini

26、tial and terminal turning radius, and the plus or minus of it not only represents vehicles turning to the left or right, but also determines the plus or minus of the movement curvature Q . Each vector are defined as foll

27、ows:</p><p>　　, (6)</p><p>　　, (7)</p><p>　　, (8)</p><p>　　In the above formulas, is initial turning curvatur

28、e, is terminal turning curvature, and is the length of the straight line driving.</p><p>　　The transformation of relations of the vehicle velocity vector in the coordinates is: </p><p><b&g

29、t;　　(9)</b></p><p>　　In it, R(θ) is the rotation matrix from the initial coordinate system transforming to the terminate coordinate system.</p><p>　　Thus, the total rotation angle can be

30、expressed as</p><p><b>　　(10)</b></p><p>　　And because the connect vector is vertical with ,, then:</p><p><b>　　(11)</b></p><p>　　is ’s base ve

31、ctor. is the angle corresponding to the starting arc.</p><p>　　System define the position of the vehicle under different coordinate system. Define the relative position of starting point and end point unde

32、r the starting coordinates. Defined of the path , expressed as the following type:</p><p>　　, (12)</p><p>　　Express the position vector using the sum of vectors under t

33、he starting coordinates:</p><p><b>　　(13)</b></p><p>　　Equation on the left means vector between the start arc center to terminate arc center, thus:</p><p><b>　　(1

34、4)</b></p><p>　　d is the distance between the two arc center.</p><p>　　In order to reduce the workload of the system when processing data, to make the system complete the choice of the dri

35、ving path efficiently and reduce the error rate calculation, to make the whole operation processed under the same coordinate system, expressing the connection vector ,, of each coordinate system under the same coordinate

36、 system is necessary. It can be expressed as follows:</p><p><b>　　(15)</b></p><p><b>　　(16)</b></p><p><b>　　, thus:</b></p><p><b

37、>　　(17)</b></p><p><b>　　namely：</b></p><p><b>　　(18)</b></p><p>　　Obviously, if the path is feasible, then</p><p><b>　　(19)</b

38、></p><p>　　By equation (17) and equation (18), we can get:</p><p><b>　　(20)</b></p><p>　　And because of the transformation matrix :</p><p><b>　　(21

39、)</b></p><p>　　We can get:</p><p><b>　　(22)</b></p><p><b>　　In it:</b></p><p><b>　　(23)</b></p><p>　　The end angl

40、e is obtained by the known equation (10), expressed as follows:</p><p><b>　　(24)</b></p><p>　　So, the total length of a vehicle’s CLC routes is as follows:</p><p><b&

41、gt;　　(25)</b></p><p>　　Vehicles choose the shortest path, means min(L) for the vehicle driving route from the calculated path with feasibility through the comparison.</p><p>　　And when veh

42、icle driving from the coordinate system to the coordinate system , the relations that exist in the coordinate system is:</p><p><b>　　(26)</b></p><p>　　According to the equation (26)

43、, the vehicle can be expressed using the same coordinate in the driving process through the coordinate transformation. In it, matrix B is homogeneous transformation coordinate matrix.</p><p>　　Obstacle avoid

44、ance control system</p><p>　　From fig.3,we can illustrates that the vehicle may come across multiple obstacles in the process of driving. To solve these problems, the first need to do is determine the shorte

45、st distance between the vehicle and the obstacles, as well as the vehicle’s relative speed based on the Dubins shortest path algorithm. The representation of relative speed can be given by the following formula:<

46、/p><p><b>　　(27)</b></p><p>　　In it,is the speed of the vehicle, is the speed of the ith obstacle, is the relative speed of the ith obstacle relative to the vehicle’s speed .</p>

47、<p>　　Then, the ith obstacle’s shortest distance vector relative to the vehicle is as follows:</p><p><b>　　(28)</b></p><p>　　In it,is the linear distance between vehicle and th

48、e ith obstacle, is the angle between the direction of the speed of the vehicle and that of the ith obstacle, and is the shortest distance between the vehicle and the ith obstacle when they met.</p><p>　　Ther

49、efore, to ensure the safety and driving of driving vehicles, it is needed to adjust the direction of the vehicle’s speed according to the monitoring situation, which can make greater than the vehicle’s safe distance ,.&l

50、t;/p><p>　　Fig.3. encounter more obstacles schematic diagram</p><p><b>　　[10]:</b></p><p><b>　　(29)</b></p><p>　　In it,is the angle difference bet

51、ween the direction of vehicle’s driving speed and the expect driving speed, that is, the angle difference between the direction of vehicle’s speed; ,are the vehicle’s safe driving speed direction angle produced by the ve

52、hicle turning left or right to avoid obstacles, respectively.</p><p>　　Then under the condition of the vehicle meeting with multiple obstacles, the vehicle's angular speed in the driving speed direction

53、can be expressed as:</p><p><b>　　(30)</b></p><p><b>　　In it,,.</b></p><p>　　The formula can also be expressed as the algorithm of vehicle’s obstacle avoidanc

54、e system.We can get,</p><p><b>　　(31)</b></p><p><b>　　In it,</b></p><p><b>　　(32)</b></p><p>　　In the driving process, the control s

55、ystem take control according to the message from the monitoring device, and the monitoring value is expressed by .Its output is the high level 1 indicates that there is obstacle ahead; Its output is low level 0 means no

56、obstacle ahead. And ,,indicates the monitoring values from the vehicle’s left, middle and right three directions respectively. Then the vehicle decision table is as follows:</p><p>　　The experimental simula

57、tion</p><p>　　Setting Up the Simulation System </p><p>　　Vehicle control system implement path planning according to the Dubins path and the algorithm uses Matlab software for simulation. The fi

58、rst to do is design road. In order to make the road conditions similar to real road conditions as close as possible, we take 15m * 15m rectangular area, and compared with the improved artificial potential field method[7]

59、; Then test the system’s following situation using the classical PID control.</p><p>　　Taking the vehicle's steering gear as the controlled object, fig.4 is the response control block diagram to the inpu

60、t signal:</p><p>　　Fig.4. vehicle following response control diagram</p><p>　　According to the control scheme figure, we can get the block diagram as follows:</p><p>　　Fig.5. vehi

61、cle following response control block diagram</p><p>　　The Results of Simulation And Analysis</p><p>　　In the process of driving, the vehicle determine the target direction firstly, then bypass t

62、he monitoring obstacles through turning or going straight, and update the vehicle’s location coordinates in real time in the whole process. Simulation results are as follows. In it: black indicates the driving path using

63、 Dubins algorithm, while blue for the comparison algorithm driving path.</p><p>　　We design the typical road conditions shown in fig.6, which field with various typical rectangular obstacles including "

64、-" glyph and "U" shape obstacles, to test vehicle’s driving path under typical road condition and to validate the feasibility of Dubins path planning algorithm. There are random obstacles set in fig.7, whi

65、ch is designed to inspect vehicle’s driving path under complex road condition. It can be seen from the two diagrams that the vehicle can adjust position effectively and can ma</p><p>　　Fig.6. the vehicle’s

66、driving path simulation diagram under typical road condition</p><p>　　Fig.7. the vehicle’s driving path simulation diagram under complex road condition</p><p>　　The simulation results show that

67、 the Dubins path planning algorithm can choose the shortest path, shorten the driving time, and avoid traditional defect of driving into local optimum. Vehicles can return to the corresponding initial path after bypassin

68、g obstacles. Compared with other algorithms, Dubins path planning algorithm can finish the experiment better.</p><p><b>　　(a)</b></p><p><b>　　(b)</b></p><p>

69、　　Fig.8. Contrast figure about vehicle’s real driving route and planning route </p><p>　　Fig.8 reflects the following situation that actual vehicle driving route follow controller-designed route. It can be

70、seen from figure(a) that the vehicle has a good execution to the controller-designed route, and the executive deviation is within 0.5 meters; Figure (b) tell us that the execution error is within 4%, and will continue to

71、 reduce with the driving conditions becoming stable gradually. It has high reliability.</p><p>　　Conclusion</p><p>　　Now under the trend of intelligent vehicle, path planning has been studied by

72、 more and more people. This paper planes the vehicle path under the Dubins path thought, completes the simulation experiment. And compared with other algorithms, this algorithm is simple and feasible. Under the theory of

73、 the algorithm, we have designed the vehicle path of two kinds of different complex road conditions, meeting the driving requirements of the complex road conditions. Comparison results show that the Dubi</p><p

74、>　　References</p><p>　　[1] WU You-qian, PEI Hai-long.Trajectory planning for unmanned helicopter based on Dubins curves[J]. Computer Engineering and Design,2011,04:1423-1429+1448.</p><p>　　[2

75、] ZHU Da-qi, YAN Ming-zhong.Survey on technology of mobile robot path planning[J]. Control and Decision, 2010,07:961-967.</p><p>　　[3] GAO Qiang，SONG Yu，LV Dong－h(huán)ao，CHEN Sha－sha. Simulation On Path Planning

76、for Multiple Mobile Ｒobot[J]. Computer Simulation, 2014,07:325-329.</p><p>　　[4] Giordano, Paolo Robuffo; Vendittelli, Marilena.Shortest Paths to Obstacles for a Polygonal Dubins Car[J]. IEEE TRANSACTIONS ON

77、 ROBOTICS,2009,10:1184-1191.</p><p>　　[5] Ketan Savla, , Emilio Frazzoli, Francesco Bullo. Traveling Salesperson Problems for the Dubins Vehicle[J]. IEEE TRANSACTIONS ON AUTOMATIC CONTROL,2008,08:1378-1391.&

78、lt;/p><p>　　[6] Zhang Minghuan，Zhang Ke. A Better Obstacle Detection Method Based on Tentacle Algorithm of Obstacle Avoidance for Intelligent Vehicle[J]. Journal of Northwestern Polytechnical University, 2012,0

79、5:763-767.</p><p>　　[7] WANG Kai, SONG Xingxiu, ZHANG Yiwen. Path planning for avoiding obstacles of autonomous vehicle using improved-artificial potential field[J]. Journal of Liaoning Technical University（

80、Natural Science）, 2014,09:1236-1239.</p><p>　　[8] Jiaojie Li, Wei Zhang, Housheng Su. Coordinated obstacle avoidance with reduced interaction[J]. Neurocomputing,2014,09:233-245.</p><p>　　[9] Ros

81、s P. Anderson, Dejan Milutinovi´c. A Stochastic Approach to Dubins Vehicle Tracking Problems[J]. IEEE TRANSACTIONS ON AUTOMATIC CONTROL,2014,10:2081-2086.</p><p>　　[10] Antonios Tsourdos,Brian White,Mad