Can Google kill the Gruen transfer in time for Christmas?

Stuck between sock stores and sanger stalls? This tech could really help. avlxyz

Christmas is fast approaching and there’s a (very big) chance you’ve got some last-minute shopping to do. You won’t be the only one, and with shopping centres packed to capacity, it’s easy to get lost, even in a shopping centre you’re quite familiar with.

But just as a GPS device can help bushwalkers to navigate the wilderness, indoor positioning systems (IPS) can help shoppers navigate the deliberate confusion caused by shopping centres – a manipulation strategy known as the Gruen transfer. How will it work? See the videos below.

A recent post on the official Google blog announced the addition of indoor mapping to Google Maps for selected stores in the US and Japan. The feature is initially only available in Google Maps 6.0 on the Android mobile operating system, but other systems are sure to be included sooner or later.

Google is not alone in their endeavours. Communications multinational Nokia is also developing its own IPS and Scottish start-up, Sensewhere, is also trying its hand.

Traditionally, indoor positioning and navigation has been very challenging technologically because GPS cannot be used reliably indoors, if at all. Therefore, alternative technologies for indoor navigation have to be used.

These technologies can be classified into three categories:

  • Technologies based on pre-deployed signal transmission infrastructure, such as systems using infra-red or ultrasonic signals, ultra-wide-band or other similar systems.
  • Technologies based on “signals-of-opportunity” – that is, radio-frequency signals not intended for positioning, including WiFi, digital television, mobile telephony and FM radio.
  • Technologies not based on signals, including inertial navigation systems (INS) (using inbuilt accelerometers and gyroscopes), vision/camera systems, and others.

Deploying new IPS infrastructure is normally costly, but can lead to accurate positioning results – within one metre. A good example is Nokia’s Bluetooth indoor positioning system. To use this system, new antenna arrays will have to be installed throughout buildings such as shopping centres.

The antenna arrays are then used to measure the angle of arrival of signals transmitted by the Bluetooth-enabled mobile device. At that point, triangulation can be applied to calculate the location of the mobile device in 2D (or 3D in the case of multi-story shopping centres).

Since standard Bluetooth cannot be used as an IPS – it is too slow, for one thing – a new Bluetooth protocol was required and developed by Nokia. Nokia claims the positioning accuracy is about 30 centimetres, which is very good for indoor applications.

But the cost of this indoor positioning system is not clear, despite Nokia’s claims the system could be cheap. There is no doubt this system has its uses, as do ultra-wide-band, infrared and ultrasonic systems. But there’s still a long way to go before Nokia’s system finds its way into the marketplace.

Another option is to harness the radio-frequency signals around us which are used for other purposes. One of the most promising examples is WiFi – it is already widely used (in homes and public places) and available at very low cost. With a growing number of WiFi-enabled mobile devices in circulation as well, WiFi-based positioning systems make a whole lot of sense.

Unsurprisingly, Google and Apple are the biggest players in this field. You might remember the first generation of iPhone which was unveiled by Steve Jobs in 2007.

There was no GPS in the original iPhone; instead, localisation was based on WiFi, supported by a company called Skyhook.

WiFi was not originally designed for positioning, and the only useful information that can be measured is the strength of the wireless signal reaching the device. The techniques used for WiFi positioning are called “trilateration” and “fingerprinting”.

Trilateration requires the coordinates of access points and the distances between the user and the access points, based on the signal strength. Creating a nice signal-strength-to-range model is difficult and the model varies depending on the environment.

The basis of fingerprinting is to build a database containing signal strength measurements at a range of reference points. The location of the user can then be identified by comparing signal strength to data in the database. An accuracy of several metres can be expected.

The fingerprinting approach has been accepted as an effective method for indoor positioning, despite two major problems: the creation and maintenance of the database. Mapping signal strength is not trivial, not least because signals can be affected by simply moving furniture. This, in turn, decreases positioning accuracy.

That said, if access points are densely deployed, signal strength accuracy would not be too bad. In the worst scenario, a simple cell ID algorithm can use the location of the connected access point as a proxy for the user’s location.

When a WiFi device creates a connection to a WiFi access point, normally the signal strength received from that access point is the strongest one and the device must be close to that access point. Then the access point’s location can be used as the approximate location of the user.

This technique can also be used to map the signal strength of mobile telephony or FM radio signals. In these cases, the sparse transmitters make positioning results less accurate but a combination of systems can improve performance.

Several other technologies have the potential to make indoor positioning as easy as GPS outdoors and researchers are working hard to overcome the shortcomings of these technologies. Inertial navigation systems (INS) are self-contained – they calculate position using in-built gyroscopes and accelerometers – but the accumulation of errors is a killer problem.

Vision positioning systems require intensive calculation and a huge database of landmarks, but superfast internet connections and cloud computing might make this technology attractive in the near future.

At the moment, there is no single winner in indoor positioning given the intrinsic complexity of the indoor environment. New technologies are always being developed but to achieve ubiquitous positioning and navigation, integration of old and new technologies seems the most likely outcome.

Sadly, it could still be a while before we see indoor positioning on mobile devices in Australia. But it’s good to know developments are underway. If you get lost at a shopping centre in the meantime, you might just need to look for the nearest information desk – or get some apologies ready for your disappointed family members.