7 ms·
How Hyper built a 1M-accurate indoor GPS
- rstuart4133 1y agoVery, very impressive, if (intentionally?) a little vague on how you got to 1m accuracy given you WiFi only gives you 3m. I guess you must use the constraints on the directions a person can walk imposed by the shelves and other structures to give you orientation of the accelerometers. Which in turn means the person doing the ground truth mapping must walk down every aisle, and into every gap. That's not so difficult if your staff are doing it, but I bet you have trouble training the store staff gathering that data to do it well. Best of British.
- AndrewHart 1y agoThanks for the feedback. I wanted to keep it balanced to be accessible but also insightful. To answer your point: we have the digital map, can use that to understand obstacles etc in the space. In some of those larger stores you see in the visual, we typically survey the entire store within 2-3 hours, it's low-effort work, not a blocker.
- subhajeet2107 1y agoWhy do you need a human to do the initial mapping ? why can't you use a Roomba or a smaller hardware for this task
- tecleandor 1y agoIt's been said in one of the comments that the initial mapping by a human takes like 2-3 hours. Knowing the speed of a Roomba, I guess that it would take much more time to do it. And 'humans' are COTS devices available on any department store (sorry ;P).
- chiph 1y agoMany times these stores have floor cleaning machines - either robotic or driven by a human. An employee could zip-tie their sensor to it, let it do its cleaning trip around the store, and return to collect the data later. This would allow an employee to do several stores in a town in a single day. And potentially less chance of a workers-compensation claim being filed if they fall down while walking around looking at their device.
- 8n4vidtmkvmk 1y agoIIUC, the black dots have to be mapped by hand. I.e. the human has to drop pins on the map. A Roomba doesn't know where it is a-priori
- mastercheif 1y agoFYI only one of your videos is displaying in HDR on your homepage, making the others seem dim in comparison. It’s the Built for simple campus navigation video. I’d recommend converting it to SDR.
- grizzles 1y agoIn my view, you need to 'streetview' the world's shopping malls and make this a free app, the Hyper Browser. Add product search & reviews and drive traffic away from non-customer stores.
- ndriscoll 1y ago> They wanted to bring indoor maps and navigation to their retail stores... It turns out that this doesn’t just apply to retail. Every office, university campus, events venue, hotel, airport, warehouse, factory — basically everywhere indoors have some need to navigate people around, provide relevant information, and improve efficiency. You'd think they would add this information to openstreetmap then or at least put a map on their website (and put it in the public domain so others like OSM can add it to their maps). Or put it in the store so people can take a picture. I go into target and there are posters saying to install an app for maps. Put the map on the poster! > and they could pop up relevant promotions along the way Oh, right, they don't want to provide information. They want to track people and spam them.
- voidUpdate 1y agoI was with them until they said that it's going to give me ads while I'm walking around
- Den_VR 1y agoThe dream of augmented reality was brilliant until the obvious consequences were recognized
- imglorp 1y agoYou might think shoppers finding their product in a store quickly would delight customers and pay for itself quickly. But it seems instead of stores simply depending on the sale, they also now demand impulse purchases, which mean they want you wandering the store looking in multiple places for your quarry: the casino model. So if they delight a customer with direct route to the sale, they need to make up that windfall elsewhere?S So they fall back on surveil, profile, and market plus selling your profile to others? Is this is why we can't have nice things?
- rf15 1y agoFinding a product quickly is actually the opposite of what a store owner would want, because it means you are spending less time on looking at the other products. Yes I hate that attitude too.
- voidUpdate 1y agoHonestly, I've wanted a system for a while where shops can provide a map, and I can search for an item and it will show me where in the shop that item is. I don't think I've ever been in a shop big enough where I'd need satnav to tell me how to get there though, is that an American thing?
- Philip-J-Fry 1y agoTesco in the UK literally has this but only for staff. If you work for Tesco you can access any shop, view a map, view where stock is on a shelf, check stock numbers and expected delivery and all that stuff. Things that would absolutely be an amazing QOL improvement for any shopper. But they won't let you have it because they WANT you to bumble your way around a shop. They don't want you to know where things are. That's why they move shelves around seemingly at random.
- leoedin 1y agoI actually find this feature of supermarkets quite useful. Online shopping is far less discoverable - the end result is I forget things from my online shop quite often.
- voidUpdate 1y agoI find exceptionally annoying when I don't know if I need to look for my preferred moisturizer in "skincare" or "premium skincare" or some other section I've not seen yet (yes this is a common issue for me). If I could just load up their (horribly slow and memory heavy) website, go to the store locator and actually see where it is in the shop instead of "yeah we have it in stock, somewhere", that would be very useful
- Philip-J-Fry 1y agoFor me the end result is I buy random crap from the shop that I don't need. Sometimes it's good because it's new and I wanna try it, but sometimes it's just me being a pig. I don't forget anything because I have a list.
- 1y ago
- ckrapu 1y agoDo you think the basic physics and sensor tolerances would let you go to 10^-2 meters if the environment (e.g. wifi station placements, location of RF-interfering elements) was designed by you?
- zokier 1y agoIf you want high performance indoor positioning , look into 5G carrier phase positioning which claims cm-level accuracy. Fuse that with IMU and optical sensing and you certainly should get decent results
- skunkworker 1y agoI've personally used one of these before in a performance where you needed individual based tracking, the chips were active UWB radios and sensors were placed and calibrated around the stage, I believe it was < 10cm accuracy and quite an interesting sensation to walk with lights following you perfectly and quickly. https://kinexon.com/products/kinexon-rtls https://kinexon.com/products/kinexon-rtls was what was used.
- 0xbadcafebee 1y agoInterestingly, a version of this technology was built by a government contractor some years ago, because they too wanted to track people indoors. I don't think it used a smartphone though... I think an acquisition would be unfortunate. This could become really huge / useful to the world without being locked up as a private company's IP. Personally I would license it rather than sell it, as well as offering offline apps and limited SaaS. You don't need an established enterprise to sell it commercially; you just need a sexy product and some industry vets with contacts. If you do end up going that way, and need someone in IT Ops / DevOps / SysEng stuff to work on the "going enterprise with a billion users", give me a shout.
- dabumere 1y agoThis is very, very impressive. I have three questions. How do you know where you are within the store? Do you manually upload the floorplan? How does it know where all the items in the store are?
- mhb_eng 1y agoReally interesting. Feels like it would be a natural addition to a company like Brain (https://www.braincorp.com/ https://www.braincorp.com/) who is already using robots to regularly perform those kinds of survey missions and have an overlapping customer base.
- hhhc 1y agoThis looks really cool. Can you also handle multi floor plans? I think that indoor multi floor plans is the most difficult challenge in this area…
- mastermage 1y agoShinjuku Station has called they need this.
- TheRealNGenius 1y ago[dead]
- amelius 1y agoIf indoor is so inaccurate, how does Apple find AirTags then?
- Dachande663 1y agoApple use UWB[0] for nearby location sensing. [0] https://en.wikipedia.org/wiki/Apple_silicon#Apple_U1 https://en.wikipedia.org/wiki/Apple_silicon#Apple_U1
- SkyPuncher 1y agoMy understanding is they use bluetooth for coarse positioning (e.g. you're within 30 feet) then they use a special chip (ultra-wide band) for the precision location (within a foot or two). Of course, there's a good bit of magic within all of that to make it work seamlessly.
- amelius 1y agoSounds to me like it is not a difficult problem except for the fact that they want to make it work with existing smartphones (both iOS and Android).
- jspann 1y agoThis is a very cool project / startup! I'm curious, how do you get the ground truth data? Is that just you marking down where you are as you walk through the store?
- AndrewHart 1y agoThank you! I tried to keep it interesting but not get lost in rabbit holes. We have around 300 hours of ground-truth data now, in 1-second intervals, which we use for algorithm training and refinement. The same as performing a survey, our team marks their location on the map, then walks to the next location, and through post-processing we can correct any errors and interpolate the locations in between. You can see this process in the diagram with the large black dots, where the user marked their location.
- MobileVet 1y agoLove reading about these types of R&D efforts, especially when they are successful. I started in robotics in 01 and was present at some of the first commercial vSLAM efforts and materially contributed to a hardware solution utilizing IR beacons on the ceiling. We also looked at RF radio mapping at the time, but the computational power wasn't there. Great to see how far it has come and LOVE that it doesn't require infrastructure! I am curious how deeply you have had to study the impact of how busy the store is with your signal error? Considering that humans are bags of water which is quite detrimental to RF signals, my guess is that your error increases along with the density of people.
- dimatura 1y agoThe few examples they show do look pretty good for a wifi-based method, although who knows how cherry-picked they are. I wonder how much the "SLAM" part is contributing and how sensitive that is to the sensor quality on the phone. I would've assumed that they'd be using vision, which seems to be the method of choice for other companies like niantic. The ground-truth data part for vision would certainly be more onerous, though.
- cyanydeez 1y agoHe explains it fairly well if you understand how you'd go from wifi accuracy to SLAM. THE WIFI was providing 3m accuracy and the SLAM down to 1M. how much it provides is those two numbers. I'm sure the algorithms are complex but he points out that SLAM is corrected by the actual maps made by the self service app. So it's fairly easy to understand: the map provides a probability space, the wifi puts you within 3m and the SLAM is use to fill in the blanks with help from the probability space.
- londons_explore 1y agoHow fast do the WiFi signal strength maps get out of date? Just someone changing the angle of an antenna or shifting a pile of stock near the router has to have a pretty big impact on signal strength. And obviously a WiFi system upgrade where all the Mac addresses change must be a fairly big change and effectively gives a full service outage for all the users till you remap.
- AndrewHart 1y agoWe've had the solution live in stores for years without any issue. Our algorithms can clean up and filter out unreliable data, based on all of the other data we have, from other APs, from previous data etc.. If they re-fit the WiFi, which they might spend a month doing once every 5-10 years, it would need a re-survey, which could take 1-2 hours. But thankfully no new infrastructure.
- ChoGGi 1y agoI go on the home depot website, pick my store, and find the product. It tells me how many are in stock, aisle number, and bay number. No need for an app or walking advertisements.
- hoppingturtles 1y agoSo they're not using GPS at all. Got it.
- dang 1y ago"Please respond to the strongest plausible interpretation of what someone says, not a weaker one that's easier to criticize. Assume good faith." https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- jacobzweig 1y agoAwesome breakdown of the challenges of indoor navigation! One thing I was curious about... given that many modern phones now have UWB radios built in, was UWB ever considered as part of the solution stack? From what I understand UWB can get to sub meter accuracy, and I know it's used in several sports applications where precise tracking is really critical. Is the constraint more about infrastructure (installing anchors, device compatibility, power) or something else that made you lean towards WiFi + SLAM fusion instead?
- AndrewHart 1y agoGreat question. Partly on device compatibility, but mostly that we can achieve an amazing, reliable experience right now without those anchors. If we weren't getting the accuracy we needed from our current methods, we would have to look at alternatives like UWB and consider the trade-offs.
- Neywiny 1y agoHuge respect to anybody who ships a product, even software. I have yet to use any indoor navigation or even have that offered, but it would be nice. Question is, is SLAM the correct term? I thought mapping meant like the device doesn't have any prior knowledge of the environment and is, well, mapping it. This more feels like sensor fusion with a kalman filter.
- AndrewHart 1y agoThe motion tracking system used by ARKit/ARCore is called SLAM, combination of sensors + camera data if available.
- Neywiny 1y agoSure, but my point was that just because something uses the same inputs and gets a similar output doesn't mean the processing is the same. This is just localization. Which is still impressive. But I'm not understanding there being any mapping going on.
- asadm 1y agodoes this require a camera to work at that 1m accuracy?
- jimbobthrowawy 1y agoSo, a "Grocery Positioning System"? I wonder how much better this does than CCC's attempts at indoor navigation for their conferences. Those are usually pretty fun to read about.
- Waterluvian 1y agoHaving used this and other localization techniques for large indoor robot fleets over the past decade, the hard part seems to be reliability. It was relatively easy to get a sensor fusion solution to work but much harder to get it to work consistently. Drift is one issue but the other gremlins also cause problems with repeatability: initial localization errors (wrong aisle), electromagnetic environment change (wifi strength is not static), physical environment change (if using optical or lidar). I think this page is a nice intro to the wifi localization space and the website has an exciting tech startup vibe. But I think if you want to really capture the undivided attention of my peers: find a clear, compelling way to demonstrate that it’s robust and repeatable. For example, walk the same real-world space twice a day for a month, stitch together the tracks in a time lapse, and promise you haven’t cherry picked the results. Especially important is demonstrating this in areas with long, repetitive aisles (grocery stores, hardware stores, warehouses, etc.) That would go far! Good luck on being acquired!
- AnnaMere 1y agoHow could one calculate the GPS of the floors? Peoples at x, y (lat, lng) ain't the same when placed them in multiple floors?
- LarMachinarum 1y agowhen I read "1m-accurate indoor GPS", my first gut reaction was along the lines of "so what? Nowadays outdoor differential/rover GPS/GNSS has <2cm precision with RTK+dual band receivers, even for civil use… and indoor allows for yet way better parameter control than outdoors, so it should be possible to achieve at least that precision" (besides, it would allow for robots to get a sufficiently precise location for indoor navigation and to shelve wares) The thing is: that would require additional hardware though, whereas the relevant limiting criterion of the project presented in the article is obviously that it has to run with just the hardware provided by common mobile phones. Which is what makes the project interesting despite the comparatively lower precision.
- ENadyr 1y agoWhoa, 1m is really impressive! I've played around with stuff like https://github.com/dmsl/anyplace https://github.com/dmsl/anyplace for https://www.emfcamp.org/ https://www.emfcamp.org/ back in the day, but that was around 5m at best. Bet you a robotics startup will scoop it up!
- AndrewHart 1y agoThanks. Very interested in robotics so that'd be an ideal home, given the SLAM + sensors tech stack.
- mentar 1y agoHow does your system handle the massive variance in sensor quality (accelerometer, gyro, WiFi radio) between a high-end iPhone and a budget Android device? Does the 1m accuracy hold up across the board, or does it degrade gracefully? Getting this right seems critical for scaling to a 'billion people'
- numpad0 1y agoPeripheral chips aren't differentiated by user values like the end products that use them. You don't get more preciser sensors in high end phones. Everyone gets the same thing. You pay more only for more materials. Sensors that are actually a lot better than standard offerings would also be subject to and/ofs of ITAR or EAR or MTCR or local equivalents thereof, so progress in IMU appears to have been stagnating a bit due to that issue. Sony Semiconductor Solutions had a Arduino IDE compatible clustered IMU board that they say you can see rotation of Earth in data, they ended up selling it with scary warnings and without any of the cool stuffs.
- contingencies 1y agoThis is the correct answer. They're all the same. The notion that Apple has some kind of edge here is farcical.
- AlotOfReading 1y agoThere's a fair bit of quality difference between different chips and better chips have gotten cheaper. More importantly, default filtering quality has improved with more powerful uCs on the IMU package, which is what most cheap phone vendors are probably using. The ITAR stuff is way more fun though. It's great to read between the lines for the intended customer in the datasheet.
- thijson 1y agoThere's something called a Kalman filter: https://en.wikipedia.org/wiki/Kalman_filter https://en.wikipedia.org/wiki/Kalman_filter It can combine several inaccurate sources and output a result that is more accurate than any one of them. I was at an Amazon Fresh grocery store, and saw squares in the ceiling that look like QR codes. I guess that's how they are mapping the store.
- mifydev 1y agoCongrats on the launch, that looks dope! I'm curious, will this be able to run on an embedded robotics hardware?
- AndrewHart 1y agoYes - one of the limitations with mobile is engaging the camera/quality of the SLAM. With a robot, they're already using SLAM with strong tracking, and controlling the hardware stack means no device limitations (uncalibrated sensors, limited WiFi pings etc.)