Show HN: FIND – an indoor positioning system for smartphones and laptops | Hacker News Reader

Show HN: FIND – an indoor positioning system for smartphones and laptops

github.com

183 pointsqrv3w72 comments

For those of you curious how it works, it's a parasitic radar system using the wireless APs of you/your neighbors to triangulate it's own position.

https://github.com/schollz/find/blob/master/FAQ.md#how-does-...

> it's a parasitic radar system

That's an accurate description, though I'd avoid the negative terminology. The system does derive its data from nearby WiFi routers, but it is in no way exploitative, like real parasites. WiFi scanning is something all smartphones do all the time, so this system merely tries harnessing it into something useful at the same time.

As for the technical side - this system uses a Naive Bayes estimator for the signal levels from mac addresses, as well as the presence of mac addresses it sees during scans. Before it can be used it needs to "learn" by visiting all the locations you want to identify. After learning it "tracks" by classifying the location used the Naive bayes estimators.

I've looked through the code to get a better understanding of this process, but I couldn't get my head around it. Could you give a more detailed description of this process?

Assuming your the same OrangeTux I talked to in the Gitter chat[1], here's my answers (from Gitter chat) for other who have questions:

> How do you compare the current fingerprint of a user with the one stored in database?

The fingerprints are used to generate priors. Basically a prior is the probability for encountering router X with signal strength Y in room Z. These are real probabilities. When I classify a location, it uses these probabilities and Bayes law to determine new "Bayes probability."

> How do you determine the probability for classification?

You are now referring to the probability on the dashboard (the webpage) I assume. Thanks for the question. This is inherently confusing, since really it is NOT a real probability so its a bit of a misnomer. Lets call them my "probability estimate." Technically speaking, the Bayes probabilities (real) are taken and normalized to the standard normal distribution. Then I determine the "probability estimates" by the proportion of the exponent of the standard normal normalized Bayes probabilities.

[1](https://gitter.im/schollz/find)

Parasitic is a technical term.

Passive might be a better term.

I thought it might. Never heard it until now!

As far as I understood, it's not using triangulation. It's using machine learning to classify wifi fingerprints.

To map the area. And then it uses signal strength to determine relative location.

no, its nothing like radar. it uses labels and signal strength.

https://en.wikipedia.org/wiki/Passive_radar

have you read what you linked? there are no reflections here, this is not SDR, just reading RSSI.

Yes. :)

Would you like to offer up another term for something that performs ranging with radio?

And how does this exclude it from being called radar?

radar is based primarily on time delays, secondarily on doppler shift, the signal intensity is not such a major factor since it varies a lot depending on the incidence angle of the target.

This would be a valuable addition to other methods of determining presence in building automation systems. What would it take/cost to build a tiny dedicated device that would wake up every, say, 5 seconds, analyze wifi signals (what's called the 'fingerprint' in this system if I understand correctly) and ping the server with that data? More concretely, would it be possible to build such a device for low prices (<50USD) with > say, a month, of battery life?

It would probably be best to use a microcontroller instead of a full cpu. I really like the Particle Photon. It costs $20 and is a joy to work with. It barely needs any power in sleep mode, and you can set it to wake up at scheduled intervals. Depending on the battery you use, a month of battery life shouldn't be an issue if it sleeps most of the time.

There are other microcontrollers with Wifi and similar capabilities that are even cheaper, like the ESP8266 at around $5, but I haven't worked with those before.

EDIT: I just saw you want it to wake up every five seconds --- in that case sleep won't help much and you'll need a big battery for a month of use, since wakeup and scanning for networks takes a few seconds. Waking up less often (eg. every 15min) would be more feasible, but it really depends on your intended use.

Home automation has always been my main goal. I've been working with some electronic devices as you mentioned. For those interested, Sparkfun has "The Thing": https://www.sparkfun.com/products/13231 which is a good way to get into the ESP8266. I've also tried using Raspberry Pis, which works pretty well but are still too big with the battery to go carry around a building. I'm hoping to try the Pi Zero in the future with a small LiPo battery.

This looks neat; the integrated Lipo charger is a welcome add-on.

Awesome, I wonder what this combined with some electronic automation can do. Eg, I walk into a room and lights turn on, i walk out, lights turn off (depending on time of the day etc).

Motion sensored room light has been available for at least 15-20 years.

This is billed as a replacement for motion sensors in home automation. Though it does beg the question, "what if someone moves their router?"

This is a great question.

A typical apartment or business has 10s to 100s of routers nowadays that your smartphone can "see" when it scans. Thus, the movement of a single router never really hinders the signal that much.

Still, I might try to add some bootstrapping to the software so that tracking locations can be used to "relearn" places to later test if the routers have been moving around.

Thank you for releasing this, this is a really valuable reference for a project I'm working on.

I've certainly seen urban areas with hundreds of routers around, but where I am it is more like 5.

Your welcome, glad it will help someone.

Certainly give it a try, I've heard that it works pretty well for ~5 routers for a couple of rooms in an apartment.

It adds a lot of complexity and point of failure for a system that I can install for 15 bucks from most hardware stores (with a solid track record).

Yes, but your detector creates more problems than it solves:

* pets set it off,

* it cannot differentiate between different objects in motion. So several people could be moving at the same time and it would only trigger as one event,

* it cannot detect people who are present but motionless (eg watching TV),

* it doesn't remember how many people are present in a room, so you could have 2 people watching TV then when 1 person leaves the detect would think the room is empty,

* it requires multiple detectors,

* detectors are generally visible, which some might find an eyesore (at least WiFi APs can be hidden a little more as fewer needed).

I'm not saying FIND is perfect either, but you have implied that your solution works just as well as FIND and stated that your solution is less complex; which is simply is not true. Your solution creates more problems than FIND and addressing them creates just as much complexity (as I detailed in my other post: https://news.ycombinator.com/item?id=11519159)

Motion detectors have a variety of usage, outdoor lighting, indoor room lighting, grocery store fridge lighting, etc. FIND is a bit more specialized because of the huge drawback of requiring each user to carry a specific device.

I can't use it at my work because we don't all have Android. I can't use it at home because my wife uses in iPhone. Cool idea but limited use compared to motion detectors.

Indeed, but that was never in dispute. FIND was never pitched to replace motion detection sensors to begin with. The argument was whether motion detectors are comparable to FIND for the specific specialised problem that FIND addresses to solve; not whether FIND can replace all the generalised purposes that motion detection is utilised.

My point was always that the two technologies aren't necessarily interchangeable and in an indirect way you're just saying the same thing with your counterargument.

The original comment was about turning lights on and off. You implied FIND is better than motion detectors at this ("your solution creates more problems than FIND..."). In most cases this is false, due to the negatives I outlined above.

I think the confusion here is there's two different use cases for turning lights on and off.

I have acknowledged in another post that motion detectors are advantageous if you're dealing with strangers and/or situations where there's lots of movement and/or lights that can be automatically timed out. eg public spaces halls, public restrooms, security lights, etc. But I don't think it's fair to lump these in the same category as "home automation".

Home automation is a little more of a complex problem as you need the lights in the room to not only turn on when someone enters, but also turn off when they leave. Motion detectors can spot someone moving in a room but they're not to great at detecting when people have left since it's the same sensor that would be triggered. They're also not great at detecting if people have entered a room and are still in the room if those people have stopped moving (eg they are watching TV) - since those people aren't triggering the motion detection. And lastly, motion detection isn't great at detecting the number of people in a room - which matters if you don't want the lights to turn off when someone leaves the room but other people are still in there and watching TV.

Motion detection solved some of the problems of home automation, but creates some problems as well. Which is why I said motion detection is just too simplistic of a solution for home automation despite it being a great solution for other types of automating lighting.

Granted you could place more sensors, network them up, and have a centralised unit logging movement. That would likely work. But then it quickly becomes as complex as the solutions we're trying to avoid.

However even if all these things were easily addressed, motion detection still has issues for me personally as I have two cats. This is the beauty of proper home automation systems: they give you the granularity to personalise things so pets don't set off the same triggers that people do. Or my two year old doesn't trigger the same automation that my wife and I do (eg unlocking the front door). This is where I think the future of home automation lies and is what really gets me excited.

So you're right that there is overlap between motion triggers lights and home automation; but the latter is intentionally a more complex problem by design.

I'm looking at building my own home automation, the PIR sensors are fairly heavy on power and in order to ping them fast enough I need a fairly large battery or hook up the sensor to electricity. If I can replace that with a device in my pocket it would be nice as I don't need extra sensors.

Ofcourse, the downside is if the device is not in my pocket the system has no way to know where I am and will keep the light on in the wrong room and keep me in the dark so it's not like it's a perfect solution.

There are PIR sensors that use no more than tens of microamps of power, and can send an interrupt signal to a microcontroller to wake it from deep sleep. An example is AMN41121 by Panasonic.

I love home automation but unfortunately can't think of any beneficial use-cases. This would require each person being tracked to have an android based device with wifi enabled and the app running.

I can't track my children, I can't track my wife's iPhone. I couldn't even track myself if I left my phone in the charger. It would be neat to track my positioning and run some statistics but I wouldn't say it's useful.

It shouldn't be difficult to assign a temporary trustworthiness score to a given AP that will change if it appears to be in a different location relative to other known APs to factor this in. If it's going to rely on APs not under the users control this will be necessary.

At least sixty years http://www.google.com/patents/US2655645

Yeah, but do any of those motion sensor systems detect if a person is still in the room but motionless? Eg if you're sat reading.

I ask because Ive had to wave my arms about far too often in public restrooms due to motion sensors deactivating the lights when spending too long on the toilet. Having that happen in my own home would be annoying enough to warrant the additional complexity of FIND (or ditch home automation entirely)

https://en.wikipedia.org/wiki/Passive_infrared_sensor

Yes, but those only detect movement[1]. They cannot differentiate between a motionless person and the rest of the room. Hence my point about the problem with motion detectors in a house given that most people often spend periods of time largely motionless.

There is a workaround to this problem, but it requires adding a networked "intelligence" to the detectors. You'd a detector at every entrance and every exit of every room. Then you'd need to network them up to a server (which defeats the advantage of motion sensors over FIND) and that would log the movement in and out of each room, incrementing the occupancy of the room as it goes along to ensure that lights are not deactivated when two people are in the room but only one exits. By the time you've installed dozens of sensors across the house, networked them, and installed a server, you might as well have just gone with FIND. Not only does FIND require less hardware, it can identify the specific individuals and isn't triggered by family pets (I certainly don't want my cats turning lights on during the night!)

So while you are right that other, simpler, technologies have been around for years, they're simply not good enough for the average home (it still remains to be seen if FIND is, but it's definitely better than motion sensors)

[1] As per the article you cited, details about how the detection on works for objects in motion: https://en.wikipedia.org/wiki/Passive_infrared_sensor#Operat...

Sure, but with this you've got less hardware involved in total, and more flexibility for programmed responses.

I guarantee my ISY-994i and my Insteon motion sensors give me considerably more flexibility than anything that would run on my phone. And that's even when Insteon sucks my will to live.

What is wrong with inertial navigation? Just need to mark a starting poing ( like, your house door ) and then just walk around and mark the places.

I've seen in the past some Android apps that do this, not sure now what's the situation.

EDIT: found some paper about it and how it worked: http://hkr.diva-portal.org/smash/get/diva2:475619/FULLTEXT02...

The problem is integration drift. I don't think it's really feasible to do inertial navigation with a smartphone.

The paper you linked is also discussing use of WiFi and Bluetooth.

Edit: here's a good overview: http://stackoverflow.com/a/7835988

If I had to guess I'd say most phones (esp. cheap Androids) have too shitty sensors for this to work reliably enough.

There was a startup in Berlin called 42 Reports that was built around this idea but for tracking people in shops and malls, word is it bombed owing to the technology just not being accurate enough, i think now they've pivoted and scraped an exit.

Isn't this why beacons and iBeacon are supposed to be the next big thing in retail? I've got a friend who just got hired to do sales in Asia for a beacon company. Apparently, they're blowing up (or trying to)?

They claim a typical accuracy of 10 square feet (< 1 square meter) which would be really really good. Even systems with beacons are not better.

Don't take my word for it, you should try it out!

It really depends on how many routers are in your area. For places in cities, there are tons and tons of routers so its very easy to get pretty good resolution. For places more remote, you might not see many routers and then you would be for more limited in your resolution.

Assuming you wanted to very precisely map a small area (50mx50m or so) to the maximum resolution possible, and you had a budget sufficient to buy and place 20 or so wifi routers, what sort of resolution could you get?

I'm looking at this for gaming applications. Don't need milimeter accuracy but +- 30cm would be good.

Well, since this turns wifi APs into beacons, it's not surprising to see comparable results.

Can some one explain me, why just not use bluetooth LE? I understand you need BLE beacons, but any other reason.

No, you don't need beacons here. It works using "fingerprints" (and machine learning) of nearby APs.

Right. Bluetooth beacons are a piece of hardware you would have to buy. Basically this tries to accomplish the same thing with just software. Here there is no hardware other than the server (which is provided) and a client computer (which you probably already own).

Cool project. I have tried using both wifi and IMU motion sensors for mapping indoor and it's not really that impressive yet. This is still a very hard problem to solve. Google seems to be working on it: https://www.google.com/atap/project-tango/

There have also been many other projects like http://wearnotch.com/

For now, External distance cameras (Kinect-like) seems to be the most accurate and usable method. Something like what these quadcopters use: https://www.youtube.com/watch?v=AiCFtmdrvHM

Thanks for the links! I haven't seen those.

I know that this already exists in many variations: https://github.com/schollz/find/blob/master/FAQ.md#doesnt-th...

Still, I've never seen one that is open-source that works pretty well, so I thought I'd put mine out there.

~10sq feet in resolution

Seems like that should be in the first 3 lines of the description, not near the end of the FAQ.

Very cool project.

Once finger printing has been done can that info be shared with other cell phones?

Yes according to the FAQ:

"The WiFi fingerprints are also the same across all devices so that learning using one device is guaranteed to work across all devices."

https://github.com/schollz/find/blob/master/FAQ.md#doesnt-th...

I don't see why you couldn't. You're just shipping serial numbers through the air at that point.

devices have different antennas, in different places and with different orientation.

A wifi antenna should always be vertically oriented because radio waves are polarized, and if you aren't in line with the polarization you'll lose gain.

What is the polarity of ipad antenna on your lap? :) Then you have multipath (reflections). This is why wifi cards had diversity switch and two antennas even before MIMO, and with 11n gained spatial diversity and beamforming.

random google result: http://www.theruckusroom.net/2011/06/a-polarizing-problem.ht...

It's accurate over 1 metre squared. I don't think the placement is too large of an issue.

mismatched polarisation can lead to over 20db of attenuation

Yes you can! Just share the "Group" name that you used for the fingerprinting.

Thinking about corporate applications...

Does it accommodate mobile APs on smart phones or personal hot spot devices? Seems those might confuse it in an enterprise setting.

Also, I would assume that the software will differentiate APs with the same SSID as in an enterprise situation and rely on MAC IDs. But just so I don't have to assume, can you confirm that it does?

> can you confirm that it does?

Yes, it will differentiate APs with the same SSID as it relies on MAC IDs. I use it at my university with no problem (which is an enterprise situation).

> Does it accommodate mobile APs on smart phones or personal hot spot devices?

It uses mobile hot spot information, however if the hot spots disappear it will not affect the results too badly, as long as there are some permanent AP fixtures. Anecdotally, I've used this system in airports (which house many personal hotspots) and it still has good recognition.

For this to replace motion sensors for home use, I think it'd have to run on an Android smartwatch, and one of the ones that's slim enough that you'll actually wear it all the time.

It still wouldn't work so well, though, for basic use cases like "turn on the dimmer lights to 40% if I enter the bathroom in the middle of the night".

That's an awesome idea! I'll look into that!

The closest to 'ideal' would probably be one of those fitness band form-factors that can be and is intended to be worn at all times, but I don't know if any of those can run general-purpose Android without having a terrible battery life.

There may be ways of making a client that doesn't need Android - like a simple WiFi chip that simply sends the information needed by the server. I'm currently looking into this!

Awesome. I tried creating something like this to help get around our very confusing corporate headquarters, but gave up. I will almost certainly use this now!

Reply on news.ycombinator.com