On course for accuracy
Map-matching algorithms are being developed to improve satellite location systems
A UK team plans to develop more accurate satellite
location technology that could improve
SatNav systems and help future road charging
schemes operate efficiently.
Researchers at Loughborough University are
investigating map-matching algorithms that integrate
locational satellite data with the spatial
road network data to identify the physical position
of the vehicle on the road in a variety of
environments. They will focus particularly on
algorithms for dense urban areas.
‘A navigation device like a TomTom normally
receives latitude and longitude data from a satellite,
which is then superimposed on to an
electronic map data inside it,’ said Dr
Mohammed Quddus at Loughborough.
‘If you superimpose electronic map data with
satellite data, you will find there is an error or mismatch
between them, so the data from the
satellite does not fall exactly on the road network.
In urban areas, when the satellite signals
are blocked due to high buildings and trees, the
error increases up to 100m.’
Map-matching algorithms reduce the error by
reading the error sources in the satellite and electronic
data, then matching the two datasets to
estimate the most likely road on which a vehicle
is travelling. The researchers hope to make a
prototype device by 2011 that will contain the
new algorithms and comprise off-the-shelf products,
including a satellite data system such as
GPS and a gyroscope to give local position data.
Quddus said most map-matching algorithms
have been developed for rural areas, where open
spaces mean that satellite signals are less likely
to be blocked. While some have been designed
for urban areas, no-one has addressed the algorithms
necessary for built-up areas because of
problems such as tall buildings and complex
road layouts, including four-lane junctions.
However, the researchers aim to integrate a
number of algorithms from which a suitable one
can be selected depending on the environment
(gauged from information such as building
height) rather than come up with one algorithm
for all situations.
‘This project will identify a set of representative
map-matching algorithms. It would not be
wise to use a single algorithm. There is no point
in using complicated mathematical algorithms
that work in urban areas in a rural area where a
simple map-matching algorithm would work
fine,’ said Quddus.
The best existing map-matching algorithm
has an error margin of 10m. The Loughborough
researchers want to reduce this even further to
provide lane-level accuracy — that is an accu-
FOR THE LATEST NEWS GO TO www.theengineer.co.uk
racy of two to three metres. This would be generally
useful, but especially useful for what the
researchers refer to as ‘liability applications’.
‘Liability applications means things like road
user charging,’ said Quddus.
‘The government is considering replacing
road tax and petrol duty with distance-based
road user charging. If you are driving on a road
which is parallel to the motorway, and the motorway
is charging £1.50 a mile and the parallel road
maybe 50p per mile, if the algorithm wrongly
identifies a particular link, the bill will be incorrect
to the users.’
In addition to improving accuracy, the
researchers will address the reliability of information
provided by the algorithm to the driver.
‘We are developing a technique that can also
give you a reliability indicator on a zero to 100
scale. That means if the scale shows 100, the
positioning information is the most reliable
information. If it is below, let’s say, 20, the user
should not believe this information as there
may be something wrong with the system, the
FutuRe
of automotive technology
SatNavs get smarter: the new system wil use map-matching algorithms to aid navigation
the EnGIneeR 21 APRIL–4 MAY 2008 9
satellite or the electronic road network data,’
said Quddus.
As a future extension of the project, the
researchers would also consider increasing the
accuracy to less than one metre. This would be
useful in the development of autonomous vehicles,
as well as improve the capabilities of
collision-avoidance systems and adaptive cruise
control in modern cars.
Meanwhile, sensors in cars with collisionavoidance
systems, such as gyroscopes and
wheel sensors, will help the researchers in their
project. They are looking to calibrate vehiclebased
sensors with the satellite sensor to help
its prototype navigation device maintain continuous
positioning information, for example,
if satellite data is lost because the vehicle is
travelling in a tunnel.
The project is being supported by technical
and business consultant Helios Technology,
which will provide expertise on how to implement
the eventual product.
Anh Nguyen
To view a Ceros magazine you need to have JavaScript enabled in your browser and have the flash player 8 or higher installed. To install the latest flash player, click the icon above, install the flash plugin and then click here to refresh this page.