購(gòu)買(mǎi)設(shè)計(jì)請(qǐng)充值后下載，，資源目錄下的文件所見(jiàn)即所得，都可以點(diǎn)開(kāi)預(yù)覽，，資料完整，充值下載可得到資源目錄里的所有文件。。?！咀ⅰ浚篸wg后綴為CAD圖紙，doc,docx為WORD文檔，原稿無(wú)水印，可編輯。。。具體請(qǐng)見(jiàn)文件預(yù)覽，有不明白之處，可咨詢QQ:12401814
6
> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) <
This paragraph of the first footnote will contain the date on which you submitted your paper for review. It will also contain support information, including sponsor and financial support acknowledgment. For example, “This work was supported in part by the U.S. Department of Commerce under Grant BS123456”.
The next few paragraphs should contain the authors’ current affiliations, including current address and e-mail. For example, F. A. Author is with the National Institute of Standards and Technology, Boulder, CO 80305 USA (e-mail: author@ boulder.nist.gov).
S. B. Author, Jr., was with Rice University, Houston, TX 77005 USA. He is now with the Department of Physics, Colorado State University, Fort Collins, CO 80523 USA (e-mail: author@lamar.colostate.edu).
T. C. Author is with the Electrical Engineering Department, University of Colorado, Boulder, CO 80309 USA, on leave from the National Research Institute for Metals, Tsukuba, Japan (e-mail: author@nrim.go.jp).
Song Guo-Hao,Huang Jin-Ying,Lan Yan-Ting
(School of Mechanical and Power Engineering, North University of China Taiyuan,030051)
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 vehicles’ 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 vehicles’ shortest path, reduced the vehicles’ path length, shortened the driving time, reduced the computation?amount of the control system, improved the?enforcement?of the vehicle?execution system, reduced the execution error, had a good selectivity?of the optimal path.
Index Terms—Intelligent Vehicles, path planning,Dubins path, the shortest path.
I. INTRODUCTION
P
ATH planning is used in many fields, such as: military unmanned aircraft, space exploration robot, intelligent vehicle, 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 driving 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 driving and make the vehicle bypass obstacles autonomously. Path planning algorithm should have precision, occupy less memory, meet the requirements of real-time, and have no obvious delay problems during the implementation[4-5]. In addition, in order to make the driving path optimal and improve the driving efficiency, it is necessary to shorten the driving length of the vehicle.
There are many related research of path 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 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 field method. This algorithm could be applied to obstacle avoidance stages in intelligent car path planning, solved the problem about the vehicle easily trapped in local minimum in the traditional artificial potential field method in path planning, had certain real-time performance. But it is limited by the influence of the sensor performance and its function scope is small, and it is easily affected by the external environment. Jiaojie Li et al[8]. proposed the coordinated obstacle avoidance algorithm. This algorithm applied the first-order kinetics and second order kinetics in the process of driving to conduct no-speed monitoring and bypass the obstacles. But it handled all obstacles as static treatment, and do not have flexibility. It may happens that two cars avoid obstacles at the same time but nowhere to avoid.
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 driving 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.
II. The Choice of Paths
The 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 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 vehicles driven from the starting point P0 to the ending point P2 as R (q), which can be approximately shown as follows:
(1)
In it, R (q) is the produced path, q is one of the parameters of path, which indicates the length 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.
The detailed description is as follows:
(2)
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.
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:
(3)
The control principle diagram is shown below:
Fig.1. The control principle diagram
The kinematics characteristics and the current state of the kinematics model in the path planning under the two degrees of freedom can be expressed as
(4)
In the above formulas, v is the vehicle speed, θ is the horizontal angle, ω is the vehicle rotation angular velocity.
The path constraint condition is one of the important factors that must be considered when driving. The 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. , 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 can be expressed as
(5)
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 tangent 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. It can be seen that the last path contains the first two path. This paper studies the CLC path, namely the vehicle path to start turning, go straight, termination turning. To build the corresponding coordinate system of the CLC three Dubins path, coordinate system is ,,, respectively. Each basic coordinates are defined as .In it, t is the unit tangent vector parallel to the velocity vector, and n is the unit normal vector vertical to t. Fig.2 is the CLC path geometry figure:
Fig.2. the CLC path geometry figure
The length of the vector and is expressed as the initial 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 follows:
, (6)
, (7)
, (8)
In the above formulas, is initial turning curvature, is terminal turning curvature, and is the length of the straight line driving.
The transformation of relations of the vehicle velocity vector in the coordinates is:
(9)
In it, R(θ) is the rotation matrix from the initial coordinate system transforming to the terminate coordinate system.
Thus, the total rotation angle can be expressed as
(10)
And because the connect vector is vertical with ,, then:
(11)
is ’s base vector. is the angle corresponding to the starting arc.
System define the position of the vehicle under different coordinate system. Define the relative position of starting point and end point under the starting coordinates. Defined of the path , expressed as the following type:
, (12)
Express?the position vector using the sum of vectors under the starting coordinates:
(13)
Equation on the left means vector between the start arc center to terminate arc center, thus:
(14)
d is the distance between the two arc center.
In order to reduce the workload of the system when processing data, to make the system complete the choice of the driving 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 system is necessary. It can be expressed as follows:
(15)
Then equation (14) in conversion coordinates can be represented as:
(16)
Due to the rotation matrix , thus:
(17)
namely：
(18)
Obviously, if the path is feasible, then
(19)
By equation (17) and equation (18), we can get:
(20)
And because of the transformation matrix :
(21)
We can get:
(22)
In it:
(23)
The end angle is obtained by the known equation (10), expressed as follows:
(24)
So, the total length of a vehicle’s CLC routes is as follows:
(25)
Vehicles choose the shortest path, means min(L) for the vehicle driving route from the calculated path with feasibility through the comparison.
And when vehicle driving from the coordinate system to the coordinate system , the relations that exist in the coordinate system is:
(26)
According to the equation (26), 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.
III. Obstacle avoidance control system
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 shortest 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:
(27)
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 .
Then, the ith obstacle’s shortest distance vector relative to the vehicle is as follows:
(28)
In it,is the linear distance between vehicle and the 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.
Therefore, 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 ,.
Fig.3. encounter more obstacles schematic diagram
When solving multiple obstacles meeting problem, we usually need to construct the Lyapunov function to determine the stability of the function used[10]:
(29)
In it,is the angle difference between 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 vehicle turning left or right to avoid obstacles, respectively.
Then under the condition of the vehicle meeting with multiple obstacles, the vehicle's angular speed in the driving speed direction can be expressed as:
(30)
In it,,.
The formula can also be expressed as the algorithm of vehicle’s obstacle avoidance system.We can get,
(31)
In it,
(32)
In the driving process, the control system 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 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:TABLE I
Vehicle decision table
Presence of obstacles
The decision results
0
0
0
None
Go straight
0
0
1
Obstacles on the right
degrees to the left
0
1
0
Obstacles in the middle
degrees to the right
0
1
1
No obstacle on the left
degrees to the left
1
0
0
Obstacles on the left
degrees to the right
1
0
1
No obstacle in the middle and the vehicle can pass
Go straight
1
0
1
No obstacle in the middle and the vehicle cannot pass
Stop or degrees to the right
1
1
0
No obstacle on the right
degrees to the right
1
1
1
Obstacles ahead
Stop or degrees to the right
IV. The experimental simulation
A. Setting Up the Simulation System
Vehicle control system implement path planning according to the Dubins path and the algorithm uses Matlab software for simulation. The first 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]; Then test the system’s following situation using the classical PID control.
Taking the vehicle's steering gear as the controlled object, fig.4 is the response control block diagram to the input signal:
Fig.4. vehicle following response control diagram
According to the control scheme figure, we can get the block diagram as follows:
Fig.5. vehicle following response control block diagram
B. The Results of Simulation And Analysis
In the process of driving, the vehicle determine the target direction firstly, then bypass the 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 Dubins algorithm, while blue for the comparison algorithm driving path.
We design the typical road conditions shown in fig.6, which field with various typical rectangular obstacles including "-" 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, which 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 make optimal path choice under the condition of safety.
Fig.6. the vehicle’s driving path simulation diagram under typical road condition
Fig.7. the vehicle’s driving path simulation diagram under complex road condition
TABLE II
The simulation results of typical road conditions
Dubins path planning algorithm
Compared algorithm
Driving time(s)
2.9
3.5
The length of driving(m)
18.6
21.7
The simulation results show that 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 bypassing obstacles. Compared with other algorithms, Dubins path planning algorithm can finish the experiment better.TABLE III
The simulation results of complex road conditions
Dubins path planning algorithm
Compared algorithm
Driving time(s)
4.4
5.4
The length of driving(m)
28.4
35.7
(a)
(b)
Fig.8. Contrast figure about vehicle’s real driving route and planning route
Fig.8 reflects the following situation that actual vehicle driving route follow controller-designed route. It can be 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 reduce with the driving conditions becoming stable gradually. It has high reliability.
V. Conclusion
Now under the trend of intelligent vehicle, path planning has been studied by 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 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 Dubins path planning algorithm can calculate the shortest path, and have good selectivity of the optimal path. Vehicle with this algorithm has higher execution and lower error rate.
References
[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.
[2] ZHU Da-qi, YAN Ming-zhong.Survey on technology of mobile robot path planning[J]. Control and Decision, 2010,07:961-967.
[3] GAO Qiang，SONG Yu，LV Dong－h(huán)ao，CHEN Sha－sha. Simulation On Path Planning for Multiple Mobile Ｒobot[J]. Computer Simulation, 2014,07:325-329.
[4] Giordano, Paolo Robuffo; Vendittelli, Marilena.Shortest Paths to Obstacles for a Polygonal Dubins Car[J]. IEEE TRANSACTIONS ON ROBOTICS,2009,10:1184-1191.
[5] Ketan Savla, , Emilio Frazzoli, Francesco Bullo. Traveling Salesperson Problems for the Dubins Vehicle[J]. IEEE TRANSACTIONS ON AUTOMATIC CONTROL,2008,08:1378-1391.
[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,05:763-767.
[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（Natural Science）, 2014,09:1236-1239.
[8] Jiaojie Li, Wei Zhang, Housheng Su. Coordinated obstacle avoidance with reduced interaction[J]. Neurocomputing,2014,09:233-245.
[9] Ross P. Anderson, Dejan Milutinovi′c. A Stochastic Approach to Dubins Vehicle Tracking Problems[J]. IEEE TRANSACTIONS ON AUTOMATIC CONTROL,2014,10:2081-2086.
[10] Antonios Tsourdos,Brian White,Madhavan Shanmugavel. Cooperative Path Planning of Unmanned Aerial Vehicles [M].BeiJing: National Defend Industry Press,2013.