Information Technology Reference
In-Depth Information
Several improvements of the original algorithm such as the A* algorithm as
well as special preprocessings of maps make it affordable to compute the optimal
answer to each query within a very short response time. For a fairly recent
analysis see [12].
Even small on-board-devices containing maps with more than 100000 junc-
tions get the answer within fractions of a minute. This is why traditional navi-
gation systems start computation only after the query is asked.
Nowadays, dynamic information referring to the current status of the road
network is also provided. The most popular method applied in nearly all de-
vices is a repeated update of information about trac conditions on highways
via Trac Message Channel: The updated information is plugged into the local
map of the on-board-device which recomputes the route for a target the vehicle
is currently heading to. Computationally, this is feasible only, because the dy-
namic information provided is very scarce in time and does not apply to all road
segments. Thus, recomputation does not occur very often. Since it is normally
used for highways only, the next junction ahead where the old and the new an-
swer may differ, is normally far away which leaves enough time for the complete
new computation.
However, the situation would be different if we admit real-time information
for all road segments of the network (not only highways) and if we also apply
dynamic routing for city navigation. Then a recomputation would not be feasible,
because the update would have been needed more frequently, and the driver
would have to react within seconds to a new situation. Furthermore, and this is
the most important argument, it is not feasible to transmit updates about each
road segment of the total road network every minute to each mobile device in
order to be integrated into on-board computation.
This suggests that future dynamic road navigation must be computed off-
board on a supercomputer (which may be a virtual one using cloud computing)
being provided with the most recent information about the status of all road
segments. For this scenario, the on-board navigation devices would not do the
actual computation anymore. Instead, it would rather transmit the queries of
the user to the supercomputer and receive the computed route from the super-
computer and display it to the driver. In fact, in the front end the driver would
not see any difference to present systems. In order to be fault-tolerant to mobile
transmission failures, the traditional functionality of the navigation device may
be applied as backup solution.
Smartphones using Google or other digital maps already comply to this off-
board principle. Google maps can already display the current trac situation
which is retrieved from the mobile cell-phone users. This can be achieved not
only for highways but also for city trac. However, Google apparently does not
integrate the dynamic information into the optimization algorithm: Google shows
several (usually 3) routes which are reasonable for normal trac conditions. For
these suggestions, Google also shows the current situation. But Google would not
include alternative routes when all routes suggested are disadvantageous under
current conditions. And even if Google did, the open question would be how the
 
Search WWH ::




Custom Search