Wednesday, 27 October 2010

How to make "Sat-nav" work inside a Tesco Store

If you have been reading in the media about my proposal to have a form of in-store "satellite navigation"-style location based awareness for Tesco Finder app users, I thought I would take you on a dive into the sort of research we're doing to see if we can make this work.

Now we don't do 'tech' for its own sake so let's examine the use cases:
  1. "As the customer, I wish to be guided to the product I am looking for in the store".
  2. "As the customer, I wish to be alerted by my phone whenever I am close to a product I have stored in my shopping list".
  3. "As the customer, I wish to be alerted by my phone whenever I am close to products on special offer that are similar to products in my shopping list".
  4. "As the customer, I want you to show me a map of the store layout, and on it show where both I am and where all the products in my shopping list are located".

Wow, we need some good data to satisfy these requests! Let's see what we have:
  1. We know where all grocery products are in every UK Tesco branch as long as it is bigger than an Express-sized format. This data is already provided to Tesco Finder users.
  2. We are already obtaining good aisle and shelf location spatial data from software that is used by Tesco merchandising teams that creates planograms. We haven't made this live yet but it's looking good. Tesco Finder would take this data and draw out all the aisles on the screen. We're making sure we describe the layout using as few characters of data as possible (I hope other app writers think as carefully about your data plan limit and keep the amount of data transferred down as much as all Tesco app authors do).
So we know every product that every Tesco branch stocks, and where it is laid out spatially in that branch. We know what products are on special offer and what the nature of that offer is. We just need to update the Tesco API server interface to make the spatial/map data available in as few characters as we can, and code a version of Tesco Finder to support the store map. That work is in progress, and we have found everything we need to make it work.


So "all" that is left now is to work out where the customer is, on a phone that loses the GPS signal as soon as they enter the Tesco branch. Hmmm...!

As you can imagine, all of our Tesco stores have wifi wireless network access points built into various parts of the building. These provide staff with the ability to enjoy network connectivity from their various handheld devices as they go about their tasks, so this is a critically important part of our in-store infrastructure.

Each access point has a unique identifier - a Media Access Control (MAC) address - which it supplies in every piece of signal data it transmits. We can tune into the wireless data chatter and read the MAC address without actually having to connect the phone to the access point. Indeed the phone doesn't have to transmit anything - just listen.

If we were to:
  1. Tell the phone (using the API) where the access points are on the store map and what their unique MAC addresses are, and
  2. Get the phone to measure the relative signal strengths of the wireless signals coming from these MAC addresses...
..then we could get the Tesco Finder app to work out where it thinks it is on the map.

Some fairly simple mathematical formulae is all that's required but given that a picture paints a thousand vector symbols, you can see how it would work in this diagram (click image for larger version):
I have colour-coded 6 access points so you can see how the phone might work out where it is in the store. Given that the lower signal strength is most likely to mean a more distant access point, and because the phone knows where all the access points are located, it can work out where it is.

Job done? Not quite... radio waves are a finicky phenomenon (I should know as I am a licensed radio amateur). From a radio point of view, Tesco sells a diabolic mix of products that reflect, refract and absorb signals. As the phone moves around, these three corrupters of signal purity will be in full force wrecking the ability of the app to work out where it is.

For example, walk down the aisle full of bottled waters and it is quite possible that nearer access points will become weaker than more distant ones as these stronger signals are absorbed more by the water. Walk down the baked bean aisle and those tins are reflecting signal like you wouldn't believe. These rarely affect the staff equipment since the system allows staff devices to roam quickly between access points. It's only us who needs to know about each particular access point. 

So now you know why this an R&D project. Tesco Finder needs to work out (probably through some sort of averaging) where it thinks it is in a way that is quick and accurate enough to be credible to the customer. If we crack this, it means that we can provide in-store "satnav" style help with zero change in the infrastructure. We're going to have a damn good go!

P.S. Once again can I point out to journalists that I am Head of R&D for Tesco.com (which just so happens to that part of Tesco pushing apps out in an R&D context). I am not Head of R&D for Tesco. Somebody else is!

14 comments:

  1. sounds pretty cool, i'd still say if you need an app to find products in a store then the store design is wrong, however given some of the large tesco stores are the size of a small village that becomes much harder!

    ReplyDelete
  2. I’m curious to know what kind of accuracy you’d get with just WiFi only positioning. Is the accuracy greater inside a large store than say outside? Also would this system be able to distinguish which floor a customer is on for those Tesco stores that have more than one floor?

    ReplyDelete
  3. Maybe you are chasing the wrong rabbit?

    http://lab.linkeddata.deri.ie/2010/deri-rooms.php

    RDF to floorplans as svg for smartphones.

    I believe you have rdf ...

    ReplyDelete
  4. It's interesting as this problem is relevant to museums and gallaries who want to use mobile devices to guide and to tell people what they are looking at!

    ReplyDelete
  5. Saad, first of all yes the Wifi triangulation should work as well in 3D space as it does in 2D space. I'll be designing for 3D space although in reality groceries are normally only sold "downstairs" on the main shop floor.

    As for wifi inside accuracy vs outside accuracy, I think it should be about the same. The access points tend to be mounted in the ceiling inside a Tesco store which tends mean more likelihood of line-of-sight access to the signals because they are coming down from above, so to speak.

    ReplyDelete
  6. PaulG - thanks, I'll look into this although my plan is to send the store plan data down to the phone in JSON format which has less 'scaffolding' around the data than XML/RDF.

    ReplyDelete
  7. Christopher - yes museums and galleries could use this method although don't think the accuracy is enough for your phone to work out accurately what painting you're standing in front of in order to trigger the correct commentary.

    ReplyDelete
  8. Darren - I think turn by turn descriptions to get to the product requires an accuracy we can'y provide. This is more about augmenting information Tesco Finder already provides today - "Aisle 23 on the left side counting 3 units along then the 4th shelf up from the floor".

    Customers could get "special offers around me" - I think that's a more useful use!

    ReplyDelete
  9. I meant the RDF of a product "HAS A" location (in a store)

    RDF derived from products I meant, though could be product groups I guess.

    ReplyDelete
  10. Nick, I'd expect that some sort of error correction algorithm should be able to filter out problems with signal absorption and reflection. Provided that you have more than 3 points of triangulation, as you suggest you do, the algorithm could discard the error data, yet still provide good results.

    ReplyDelete
  11. You could augment wifi triangulation by using the accelerometer and digital compass in many modern smartphones and a very low-tech option would be some QR/barcodes at strategic locations, like the store entrance, to act as 'start points'.

    ReplyDelete
  12. could the phone initialise itself at the entrance, as far as I can tell each phone, model/manufacture gives a unique interpretation variance of the signal, so initialising at the door and snapshoting the signals would give a more individual guide to position of the phone

    ReplyDelete
  13. Wifi signal strength is only available from a 'private api' on Apple iPhone. It'll have to be Android only unless Apple expose the API :-(

    ReplyDelete
  14. I think that this is wonderful news and long overdue. I only discovered this amazing site yesterday but a few days ago rang head office begging for a planogram of my local TESCO store. There is nothing more irritating that searching for items when you are in a tearing hurry and cannot locate a member of staff! Let us hope that Apple welcome this and take it as one of their Apps.

    ReplyDelete

As this blog grows in readership - and because it carries the Tesco brand - I have had to become more careful about the sort of comments that are acceptable. The good news is that I'm a champion of free speech so please be as praising or as critical as you wish! The only comments I DON'T allow through are:

1. Comments which criticise an individual other than myself, or are critical of an organisation other than Tesco. This is simply because they cannot defend themselves so is unfair and possibly libellous. Comments about some aspect of Tesco being better/worse than another equivalent organisation are allowed as long as you start by saying "in my personal opinion.." or "I think that...". ... followed by a "...because.." and some reasoned argument.

2. Comments which are totally unrelated to the context of the original article. If I have written about a mobile app and you start complaining about the price of potatoes then your comment isn't going stay for long!

3. Advertising / web links / spam.

4. Insulting / obscene messages.


Ok, rules done - now it's your go: