Wireless Sensor Network, 2010, 2, 661-667
doi:10.4236/wsn.2010.29079 Published Online September 2010 (http://www.SciRP.org/journal/wsn)
Copyright © 2010 SciRes. WSN
The Safe Navigation of Partial Motion Planning Based on
“Cooperation” with Roadside Fixed Sensors in VANET
Rong Ding1,2, Xiaoguang Li1,2
1State Key Laboratory of Software Development Environment, Beihang University,
2School of Computer Science and Engineering, Beihang University
Beijing, China
E-mail: dingr@buaa.edu.cn, lixiaoguang@cse.buaa.edu.cn
Received July 3, 2010; revised August 5, 2010; accepted September 7, 2010
Abstract
In recent years, many methods of safe vehicle navigation and partial motion planning (PMP) have been pro-
posed in vehicular ad-hoc network (VANET) field. In order to improve the limitation of traditional PMP, this
paper presents a novel effective way to plan motion with cooperation of roadside fixed sensors (RFSs). With
their cooperation, the vehicles can get the surrounding information quickly and effectively, and give highly
accurate projections about the near future conditions on road. After proposing our algorithm, the worst case
is analyzed and methods are found to solve the problem. Finally we conduct one elemental contrast experiment,
driver situation awareness, with or without the “cooperation” of RFSs in highway scenarios. The result
shows that the vehicles can make a better PMP based on the forward conditions received from RFSs, and
extend the warning distance obviously when emergency happens.
Keywords: Partial Motion Planning, Safe Vehicle Navigation, Roadside Fixed Sensors, Cooperation
1. Introduction
It is a dream of human beings to achieve autonomous
mobile vehicles since the invention of cars. With the
rapid development of science and technology, and
through the persistent and unremitting efforts by scien-
tists, many novel tools which are equipped with modern
technologies are used in cars such as GPS navigators and
PSD sensors. By using those tools, unnecessary accidents
can be avoided and destination can be achieved easily as
well [1].
However, there is still a long way to make the dream
come true. The tools are only used to human in order to
make the driving safer, but it cannot take the place of
human’s driving so far. The 2007 DARPA Urban Chal-
lenge presented the fact that there are plenty of works to
do if achieving fully autonomous driving especially in
urban environment with the extremely complicated con-
ditions, such as traffic lights and pedestrians, and safe
navigation is also a huge problem.
In safe navigation field, reaching a goal and avoiding
collisions are two main purposes and the analysis is car-
ried out in detail [2]. So far, a proven method is the layer
structure. In that structure, the safe navigation architec-
ture can be divided into five layers as follows, mission
manager, route planning, partial motion planning (PMP),
low level components, and hardware layer [3]. Nowa-
days, with the GPS’s development, the research emphasis
has been changed to partial motion planning.
There are two main paradigms in partial motion plan-
ning [4]. They are the plans based on prior information
and real time information. And the latter seems to be
safer and more reliable. Several schemes have been pre-
sented firstly in mobile robots [5,6]. In real time model,
the systems are obliged to make a relatively correct deci-
sion within a restricted time. If not, the vehicles may be
in danger passively.
Nowadays, in vehicular ad-hoc networks (VANETs),
cars can be equipped with communication device so as to
exchange information about position, speed, traffic jams
or other road conditions. Safe navigation is one of the
VANETs applications. Vehicle to vehicle communica-
tions provide a new way of collision warning forwarding
and intersection collision warning.
This paper is organized as follows: Section 2 briefly
reviews the previous work and the limitation that is not
resolved completely. And in Section 3, an effective im-
provement is provided: the “cooperation” with RFSs,
662 R. DING ET AL.
with details of the algorithms to achieve “cooperation” in
Section 4. Then contrast experiments are carried out in
Section 5 and Section 6 concludes the paper.
2. Previous Work and the Limitation
2.1 Previous Work
In this section, we discuss the related work on safe navi-
gation of Partial Motion Planning.
On hazardous terrain, a fuzzy logic approach is ad-
vanced in [7]. In that paper, navigation strategy is com-
prised of three simple and independent behaviors:
seek-goal, traverse-terrain and avoid-obstacle. Those
three behaviors are combined through appropriate
weighting factors in order to generate the final steering
and speed commands. The weighting factors are pro-
duced by fuzzy logical rules that are taken the current
status into account. Also in [8], they employ fuzzy rea-
soning to allow for aggregation decisions based on a
flexible and extensible set of criteria. These criteria can
be application specific and enable a dynamic fragmenta-
tion of the road according to the applications’ require-
ments.
In order to acquire safe motion planning, Inevitable
Collision State (ICS) has been characterized by [9]. The
most important contribution of ICS is that it promotes a
dynamic relationship properly between collision states
and safety states. Thus we can guarantee stronger safety
and giving a safe partial motion planning.
In [4], ICS takes into account the dynamics of both the
system and the moving obstacles. The core of safety is-
sues is computing ICS-free partial motion in the shortest
period of time. The paper [4] presents a property in order
to reduce the complexity of the PMP algorithm, which
simplifies the safety checking of a trajectory. If one par-
tial trajectory is an ICS-free partial motion, the trajectory
is collision free.
Another safe navigation technology is using virtual
stick [10]. They propose a reliable method for navigating
the robot to the target point, and draw an environment
map using infrared sensors. However, it is difficult to dis-
tinguish distance information using only one-dimensional
image information. So they use a virtual stick that repre-
sents different distances with different colors to improve
the perception of the position and distance of the obsta-
cle.
2.2 Limitation
All above methods only concern the one-car situation
which is myopia. We cannot get enough information of
the driving environment only by sensors or measure in-
frastructure equipped on a single car, especially in the
complex and volatile urban scenarios. Each car needs to
be kept in contact with others nearby. However, the number
of cars is huge and they are all in motion. Those external
factors have made it more difficult to ensure the reliable
connections.
One significant reason of “partial” lies in the real-time
limitation in PMP. In an environment featuring moving
objects, you have to decide upon the further action with-
in limited time, otherwise you would take the risk of be-
ing hit by another moving object. Getting the conditions
of front road sections in time can short the PMP proc-
essing time.
In addition, a prior information updater does not exist.
Even if there was one, the prior information would not
update in time. Prior information would be collected by
single car with the whole system in a lack of sink, as a
result, cars would fail to send what they have already
collected and therefore could not acquire front road con-
dition.
3. An Effective Improved Method: the
“Cooperation” with RFSs
In this part, we propose a novel approach to solve prob-
lems mentioned above. We introduce “cooperation” with
RFSs into PMP. Figure 1 shows the structure of “coop-
eration”. Cars send and receive messages from RFSs,
and RFSs can transmit these messages to each other. The
latest technology is applied to enable every single car to
detect its own possible collision, but ignore the transmis-
sion among cars. In a word, messages are transmitted
from car to RFS, from RFS to car, and RFS to RFS. In
Section 4, the three types of messages will be expounded
in detail.
Traditional safe navigation of partial motion planning
is based on single cars. In their opinion, if one car man-
ages to do well in collision avoidance, the whole work
would be finished. However, that is very shortsighted.
One successful navigation even one successful partial
motion planning depends on the accuracy grade of
real-time information and front-road condition. In this
case, RFSs are used as sink, and they can aggregate
messages from cars and transmit warning messages or
other significant messages from each other. In this way,
as is shown in Figure 1, for example, Car5 can hardly
get known about the condition of Car1 by itself when
Car1 is collided, because Car3 has covered Car5’s sight.
But collision messages can be transmitted from RFS1 to
RFS2, and then to RFS3, and at the same time both RFS2
and RFS3 send warning messages to cars nearby. In this
way, Car5 manage to acquire the front condition.
Copyright © 2010 SciRes. WSN
R. DING ET AL.
663
4. Algorithms to Achieve “Cooperation”
In this section, we give an intimate design of three types
of messages mentioned in Section 3, then put forward
our novel algorithms in dynamic road scenarios, and at
the end advantages of this cooperative methods will be
summarized.
4.1 Design of Three Types of Messages
As is shown in Section 3, the three types of messages are
from car to RFS (C-R), from RFS to car (R-C), and RFS
to RFS (R-R). The basic message formats are shown in
Figure 2.
As is shown in Figure 2, there are three types in this
paper, 0 means C-R, 1 means R-C, and 2 means R-R.
Len means the length of data segment. CRC is cyclic
redundancy check, and it is used to check whether data
transmission is true or not.
C-R messages are the source knowledge of the system.
Cars can get information from sensors which are attached
to them. In this paper, attention is paid to the danger cars
may meet. Each C-R message’s source address is car’s
own ID, when moving into a new road section, cars will
receive RFS’s broadcast message. Immediately after cars
get RFS’s ID in source address of RFS’s broadcast mes-
sage, then cars begin to send C-R messages. Data seg-
ment of C-R messages contains the following informa-
tion: car’s velocity, acceleration, distance from forward
obstacle, and some flag bit for RFS’s judging safety,
such as danger flag, ICS flag and emergency flag.
Figure 1. The structure of “cooperation” with RFSs.
Figure 2. Basic message format.
R-C messages are always regarded as prior informa-
tion, as RFSs sends warning alarm or motion suggestions
based on conditions of front section. Therefore, source
address of R-C is RFS’s own ID, messages are sending
in flooding way thus any cars which is in this section can
get R-C messages. Therefore, destination address should
be defined as “1” sequence. Data segment of R-C mes-
sages consist of following information: forward section
cars (if in the middle of the road), forward intersection
queue length (if in urban scenarios), forward highway
exit queue length (if in highway scenarios). The most
important data is flags of warning alarm and motion
proposal. These flags are concerned of safety of drivers
and passengers’ lives and property.
R-R messages are the information exchanged between
each RFS on roadside, using cable transmissions in order
to make sure the reliability while transmitting. Both
source address and destination address are RFS’s ID. We
specially point out that source address is RFS’s own ID,
and destination address is upriver RFS’s ID. That is because
in traffic flow, if one car has passed the scene of accident,
that car has no relationship to this accident. Data segment of
R-R messages consist of following information: emergency
state and RFS’s ID of accident site (if has), numbers of
passing cars in last 10s.
Based on the elementary design of message formats
above, the algorithm of “cooperation” in dynamic scenarios
will be discussed next.
4.2 Algorithm of “Cooperation”
“Cooperation” can be used similarly between highway
scenarios and urban scenarios, although the two scenarios
are very different.
In highway scenarios, all the obstacles are cars, thus
the participators in the whole system are simpler and it is
easier to monitor data and administer them. However, we
cannot ignore the accidents happening on the highway.
The velocity of each car reaches 120 kilometers per hour,
that is to say, an ordinary car may run 10 meters or more
in the time of a blink of an eye. Without a reliable warn-
ing system, it is very dangerous for those following cars
while one car may suddenly have an accident. While in
urban scenarios, obstacles can be cars, motorcycles, bi-
cycles and pedestrians. Thus system must be very com-
plex and it is more difficult to monitor a very exact
real-time data. However, we should supply a reliable
service to decrease the number of accidents, and coopera-
tion with RFSs can provide all the cars around front road
conditions and cars can analyze messages they have re-
ceived and control their speed itself, and once they meet
an accident forward they can take measures immediately.
Copyright © 2010 SciRes. WSN
664 R. DING ET AL.
Figures 3(a) (b) (c) shows the brief flowcharts of algo-
rithm for the RFSs at the intersections or highway exit,
on the middle of the road and for the cars respectively.
As is shown in Figure 3(a), there is no prior RFS for
the sensors who are settled at the intersections or high-
way exit. So they can only send interaction or exit mes-
sages to cars nearby in flooding way, thus they can re-
ceiving C-R messages as feedbacks. Then analyze the
received message and judge whether there exists an
emergency flag. If so, then send emergency messages to
the cars nearby and send danger message to the next RFS;
if not, just record this C-R message in the buffer and
regularly (10s, e.g.) send road condition messages to next
RFS based on the information recorded last period of
time.
In Figure 3(b), we can observe that there are more as-
signments for those RFSs in the middle of roads. First
they have to listen to receive messages so as to get in-
formation from prior RFS and once they have received
R-R messages they can make a judgment whether danger
flag is included. If so, they send warning message to cars
nearby and send danger messages to next RFS in addi-
tion if original danger message is from prior RFS to
make sure danger messages can send at least three RFSs
to extend warning area. Their other assignments such as
receiving R-R messages exclude danger flag; receiving
C-R messages and dealing with C-R messages are same
as RFSs at the intersections or highway exit.
At last, we analyze Figure 3(c), which is cars’ behav-
ior. When drivers are driving into a new road section,
what they can do is driving steadily and safely. But they
have no idea of front road condition; as a result, they
have to receive information passively. In our algorithm,
just like a seasoned driver, cars receive messages from
RFS around, and when cars get R-C message, analyze it
and record RFS’s ID so as to make contact with the
nearest RFS, then check whether there exists emergency
flag, if so, brake the car immediately, and if just exists
warning flag, that means in the front section of the road,
there happens an accident, so decelerate the car immedi-
ately, and else just control car’s velocity as the case may
be. It is worth notice that once the car meets an accident,
an emergency brake should be carried out by the auto-
matic control immediately, send collision message at the
same time. Thus we can make sure the RFS can get road
condition and notice other cars in time, and then the car
have to wait for aids.
4.3. Worst Case
We must realize what the worst case is, and we should
make measures to overcome the trouble. In this system,
we enumerate three bad cases as follows, the failure of
RFS, the failure of Cars and substantial cars on one sec-
tion. In this part, we discuss the method to solve them.
Once the RFS lost efficacy and the supervision on the
road section may be missed. While one car runs into a
new section, and RFS of that section is right out of work,
it cannot get R-C messages and once it gets a traffic
accident, it cannot be helped to send emergency mes-
sages and as a result, “cooperation” does not work and
cars behind the traffic accident scene will not receive any
warning message.
(a) Brief flowchart for the RFSs at the intersections or highway
exit.
(b) Brief flowchart for the RFSs on the middle of the road.
Copyright © 2010 SciRes. WSN
R. DING ET AL.
665
(c) Brief flowchart for the cars.
Figure 3. Brief flowcharts of “Cooperation” with RFSs.
Also, it is the same to cars, once cars cannot send their
emergency messages or they cannot receive R-C mes-
sages from RFS, it will be very dangerous for either
those failure cars or cars behind them.
Another criticality factor of this system is vehicles’
number, we have to take into account that the bandwidth
and the considered RFS’s capability. While cars’ number
is very huge and thus bandwidth is not enough, and
emergency messages may be drop in RFS’s queue, which
means it is blind of RFS if traffic accident happens
around, and that case is not allowed absolutely.
And our solutions are listed as follows. First, we pre-
pare spare RFSs and Car sensors in order to eliminate the
error coursed by failures happen on sensors. We have to
take the cost if the whole system into account, if we pre-
pare too much sensors, it is a waste of money, so there is
a dynamic balance between safeties and costs. Here we
choose the scheme that each car has a spare sensor, and
every four RFSs have a spare sensor. Second, we use
priority queue to make sure emergency messages are not
dropped by RFS while the condition of communication is
in a dickey state. In [11], priority concept is brought
forward firstly in vehicle ad-hoc network field. And in
this system, we apply this comparatively mature idea,
and we give some improvement to satisfy the need of
safe navigation.
5. Contrast Experiments
In this section, we introduce our contrast experiments.
Firstly we introduce the experimental platform, and then
our contrast trial in highway scenarios will be shown in
the second part, at the end of the second part, we give
our analysis of this experiment.
5.1. Experimental platform
As is shown in Figure 4, we use HBEROBOCAR as our
experimental platform. Figure 4(a) shown the car and
Figure 4(b) shows the RFS. All the messages of this
system are transported by ATmegal128L just as Figure
4(b) shows. Our car equips some sensors, such as PSD
sensors and ultrasonic sensors so that it can detect for-
ward obstacles, and also it quips one ATmegal128L in-
terface so that it can communicate with RFSs while con-
necting with ATmegal128L node.
This car is 23cm long and 15cm wide, and 1:18 to the
true car. The highest speed of the car is 47cm/s. In this
experiment, we pay our attention to the different speed
after 60cm of the traffic accident happens and warning
distance between with and without RFSs.
5.2. Experiments in Highway Scenarios
We apply four cars and two RFSs to simulate the high-
way scenarios as is shown in Figure 5. Car1 is the first
car which would have an artificial accident thus we can
measure car2 to car4’s reaction time and stop distance.
(a) One experimental car with PSD sensors and ultrasonic sen-
sors.
(b) RFS sensor used for communication
Figure 4. HBE-ROBOCAR experimental platform.
Copyright © 2010 SciRes. WSN
666 R. DING ET AL.
Figure 5. The simulative scenarios of our contrast experi-
ments.
At First, we do not use RFSs and only four cars driv-
ing on the simulative scenarios. Suddenly the car runs
upfront meet an accident, and we measure each car’s
speed when car runs into the 60cm of the traffic accident
and warning distance when accident happens. We will
repeat for 20 times.
Then we add RFSs and with three RFSs and four cars,
then we let the first car to have an accident just like the
experiments above, then measure each car’s speed and
warning distance too. Also, we make the experiments for
20 times.
The results are shown in Figure 6 and consolidated
measured data are shown in Table 1.
As is shown in Figure 6 and Table 1 above, while
adopting “cooperation” with RFS strategy, each car’s
speed at 60cm after accident is much slower and the
warning distance is much wider than the case without
RFSs. Car2 is in front of Car3 and Car4, thus Car2’s
speed at 60cm after accident is a little higher than Car3
and Car4. However, we can clearly find that the per-
formance is improved obviously.
6. Conclusions and Future Work
In this paper, it is shown how to develop a novel safe
navigation algorithm based on “cooperation” with RFSs,
so as to improve the safety factor for the drivers while
driving cars. Our experimental results show our algo-
rithm effectively reduces the chain collision and extends
the range of divers’ situation awareness.
In the future, we focus our research priority on how to
create a novel transport protocol so as to overcome
(a) Speed of each car at 60cm after accident.
(b) Each car’s warning distance
Figure 6. The result of contrast experiments of with and
without RFSs.
Table 1. Average data of the contrast experiments.
cars Average data of measured
parameter
without
RFSs
with
RFSs
speed (60cm)(cm/s) 31.93 23.86
car2 warning distance(cm) 79.95 189.05
speed (60cm) (cm/s) 31.22 20.59
car3 warning distance(cm) 79.65 207.15
speed (60cm) (cm/s) 30.77 18.58
car4 warning distance(cm) 80.05 214.40
wicked condition such as very high speed, too many cars
and atrocious weather.
Acknowledgements
Supported by the Research Fund for the Doctoral Pro-
gram of Higher Education of China(RFDP), the fund of
the State Key Laboratory of Software Development En-
Copyright © 2010 SciRes. WSN
R. DING ET AL.
Copyright © 2010 SciRes. WSN
667
vironment (Grant No. SKLSDE-2009ZX-04) and the
National High-tech R&D Program of China (863 Pro-
gram) (Grant No. 2009AA043303, 2008AA12A216,
2009AA043305).
7. References
[1] G. Taylor, G. Blewitt, D. Steup, S. Corbett and A. Car,
“Road Reduction Filtering for GPS-GIS Navigation,”
Transactions in GIS, Vol. 5, No. 3, 2001, pp. 193-207.
[2] R. Siegwart and I. R. Nourbakhsh. “Introduction to Auto-
nomous Mobile Robots,” MIT Press, Massachusetts,
2004.
[3] K. Macek, D. Vasquez, T. Fraichard and R. Siegwart.
“Safe Vehicle Navigation in Dynamic Urban Scenarios,”
Proceeding of the 11th International IEEE Conference on
Intelligent Transportation Systems, Beijing, October 2008,
pp. 482-489.
[4] S. Petty and T. Fraichard. “Safe Motion Planning in Dy-
namic Environments,” Proceedings of the IEEE Interna-
tional Conference on Intelligent Robots and Systems,
Edmonton, 2005, pp. 2210-2215.
[5] P. Fiorini and Z. Shiller. “Motion Planning in Dynamic
Environments Using Velocity Obstacles,” International
Journal of Robotics Research, Vol. 17, No. 7, July 1998,
pp. 760-772.
[6] R. Simmons, “The Curvature Velocity Method for Local
Obstacle Avoidance,” International Conference on Ro-
botics and Automation, Minneapolis, April 1996, pp.
3375-3382.
[7] H. Seraji, A. Howard and E. Tunstel. “Safe Navigation on
Hazardous Terrain.” Proceedings of the 2001 IEEE In-
ternational Conference on Robotics & Automation, Seoul,
May 2001, pp. 3084-3091.
[8] S. Dietzel, B. Bako, E. Schoch and F. Kargl. “A Fuzzy
Logic Based Approach for Structure-free Aggregation in
Vehicular Ad-hoc Networks,” Proceedings of the 6th
ACM international workshop on Vehicular Internetwork-
ing, Beijing, September 2009, pp. 79-88.
[9] T. Fraichard and H. Asama, “Inevitable Collision States -
a Step towards Safer Robots?” Advanced Robotics, Vol.
18, No. 10, 2004, pp. 1001-1024.
[10] S. M. Jung, T. H. Song, J. H. Park, J. H. Park and J. W.
Jeon, “The Safe Navigation of Remote Mobile Robot
Using Virtual Stick,” 2008 IEEE International Confer-
ence on Industrial Technology, Chengdu, April 2008, pp.
1295-1734.
[11] T. M. Marc, D. Jiang and H. Hartenstein. “Broadcast
Reception Rates and Effects of Priority Access in
802.11-based Vehicular Ad-hoc Networks,” Proceedings
of the 1st ACM international workshop on Vehicular ad
hoc networks, Philadelphia, October 2004, pp. 10-18.