How about room mapping instead of trilateration?

[timon37]

The main problems with trilateration are:

1. there have to be as many proxies as there are areas to track
2. in practice proxy placement can't always be ideal and/or antenna gain can vary, causing areas to bleed over each other
3. there can't easily be any dead-space, e.g. a user being outside the home in the garden will get detected as being in a nearby room

Mapping could solve these

We'd do room calibration by walking around with a beacon e.g. into each corner of an area, capturing the RSSI to all proxies.
These points would effectively create a polygon corresponding to that area.
Doing this for each area would effectively create a map (in the proxy RSSI space).
And the beacon would be assigned a given location when it's within that polygon (likely with a bunch of heuristics fuzzing the edges).

Side benefits
Any overlap in the areas would quickly indicate problematic areas to the end user.
These could be handled by:

1. changing proxy placement or orientation (unfortunately requiring remapping)
2. prioritizing areas e.g. if it's better to be detected in one over another
3. manually adjusting the mapping

Any space between the areas most likely corresponds to wall attenuation.
We could allow marking which areas are touching, to eliminate these and always assign one or the other when a beacon ends up in between.

Challenges
The RSSI also depends on the beacon strength, so the math has to be normalized/relative.
In the sense that e.g. coordinates (50, 30, 10) from a strong beacon are the same as (5, 3, 1) from a weak beacon (grossly oversimplifying of course).

RSSI to far away proxies is likely going to be very variable, so there will have to be heuristics to either:

1. only use a few nearest proxies
2. have a wider margin of error depending on RSSI

The map effectively has as many dimensions as there are proxies, and various points will only have coordinates for some of them. This would make visualizing the data a bit difficult and may make debugging complex cases challenging.

In general there will likely have to be many heuristics to make this work well, which also implies many tunable parameters, which is both good and bad.

P.S.
I'm definitely willing to help with this, especially the math.
Unfortunately I'm not familiar with python, nor hass internals, so I'd be quite clumsy.
I'd expect the UI to be the main difficulty as this will involve a fair number of mapping interactions, visualization/debugging helpers.

[timon37]

P.P.S.
Despite the title this doesn't actually have to be done instead of trilateration.
It could just be an addition to solve problematic areas;)
Meaning that by default everything is as it currently is, and if there's a problematic area, then the user could map it.

[tbrasser]

I think both is needed in the end, trilateration to get x,y(,z) then map to floorplan to get area/room.

Or at least have proxy location x,y in floorplan instead of proxy=area 1-on-1 mapping.

[timon37]

Hmm I don't think you'll get reliable real-world space coordinates, hence why I said "in RSSI space".
The two are strongly correlated but not in a simple way.
If you could record a bunch of realworld x,y,z position accurately along with the corresponding RSSIs you could create the complex map from RSSI to realworld. But I feel like that's overcomplicating it for no real gain.

Just having the area's mapped into RSSI space (or whatever measure is used, sorry, I'm actually not sure) should make it fairly simple and hopefully good enough for the intended purpose.

Also keep in mind RSSI is not static, e.g. it'll strongly depend on whether a door is closed or open between two rooms. Or on where your beacon vs your body is e.g. phone in pocket with your body between it and the proxy will attenuate a lot vs holding a phone out. Besides no antenna is ever perfectly omnidirectional.
Point being that imho realworld positioning is going to be inaccurate enough to be useless (except maybe in large open spaces with proxies on the ceiling).

P.S. of course that's just imho, I could be wrong, hard to tell without trying everything;p

[timon37]

@agittins I started experimenting on a hackish proof-of-concept for this.
So I guess the main question is how open are you to such a thing?
Should I share it as a pull request and/or give more details?

Mathematically it's not all that different, what you have right now is kindof like a voronoi diagram, my suggestion is to instead allow mapping those regions arbitrarily. It'll still work best if there's a device in each area, and I doubt that'll change dramatically.

The main difference comes down to setup/tuning, in what I'm suggesting in configuration you'd select a beacon and area, click start, walk around with the beacon in that area, click save. Then do that for all areas you want to map.

[dekiesel]

I'd like to throw in my two cents.

I case room level accuracy is enough, and I think it is enough for the vast amount of people, then a neural network is a great candidate for a solution.

People can train the NN for each room and even "simulate" different conditions, like doors open, phone in hand or in pocket and so on.

The inputs for the NN are the beacons while, for starters, a single layer representing rooms would be worth a try.

[gheydon]

I am really for being able to map room would increase my accuracy massively.

As I see it the currently method assumes rooms are circular and the bluetooth detection point is in middle of the room. I have Shelley 1 and 2 PM behind all my wall switches as well as some other bluetooth proxies so some of my room I have multiple shelley's in the same location for multiple rooms (or even 1 single shelley 2 for 2 rooms) and in one place I have 2 shelley's in the corner of 3 rooms.

So being able to map a room based upon 2 or 3 points will make it so much more accurate. As it is now I can stand in the middle of my lounge room and not move and my location will jump between 2 or 3 rooms.

[agittins]

Sorry I just haven't had time to explain the situation here, life has been way too busy for me to get into it - despite attempting a few drafts over the last few weeks :-)

Suffice to say - Bermuda does not currently use trilateration at all, and as you'll see in a lot of places, it's next on the cards.

The current area detection is deliberately described as a "naive, simplistic nearest-area" match, and in no way a trilateration attempt.

I have set plans for the next phase, and there's plenty of writing about how I plan to do so. Sorry I don't have time right now to map it out but there's over a years' worth of discussion in the existing issues and threads that should help for now, and contribs are very welcome but there's significant context and discussion to get up to speed on to be able to get into the nitty gritty. One thing I seem to keep learning is that ideas are the easy bit, the implementations are hard :-)

[timon37]

@agittins No problem. I'll try to post my current hacks soon-ish. Python's not my thing and my editor was being a bit troublesome so sorry for what you'll see there;p
At the moment just consider it a curious experimental branch.

@gheydon Ok, you might be a good test-case for this:) I have too few proxies.
In general so far the data looks much worse than I hoped, so I doubt this'll ever work well with any less than 1 per area (though that depends on the use-case).
Anyway will you be up for lots of early testing?

@dekiesel Yeah, it's probably the most classic application for NN. Though at such small scale it's apparent that it's just curve fitting based on statistics. So calling it AI/NN/etc isn't necessary unless someone wants to find investors;)

[saket424]

@timon37 @agittins
Do you have a floor plan creation/visualization in mind to display the Bermuda location even if it iis roughly accurate?

https://github.com/ExperienceLovelace/ha-floorplan
https://github.com/createcandle/homeRoughEditor
https://github.com/ESPresense/Floorplan-Creator
https://espresense.com/companion/configuration/

[saket424]

@timon37
I have a few Shelly plugs acting as btproxies and Shelly blu buttons as ble emitters and I would love to try out your current hacks using them to roughly locate/classify where the button press happened . Count me in as a beta tester

My view is even a approximate location or region is better than nothing

[dekiesel]

@dekiesel Yeah, it's probably the most classic application for NN. Though at such small scale it's apparent that it's just curve fitting based on statistics. So calling it AI/NN/etc isn't necessary unless someone wants to find investors;)

That investor comment hit a bit too close to home :D

I still think it's the best choice since it's easy to scale to any number of beacons and it can get us basically as close as we want to the best fitting function.

But as @agittins said, ideas are cheap. I'm in the process of renovating and moving and it'll be some time until I have a setup that's right for testing neural networks as a possible solution.

[timon37]

@saket424 Personally I'm explicitly aiming to not need any "real coordinate map", and so far it seems unfeasible to have them (to me). But I've been surprised many times in life so who knows what others come up with.

@dekiesel Yeah, I've struggled with hand tuning mediocre heuristics often enough that I'm warming up to the idea quite quickly already:)

I hope late next week I should have enough time to make it such that it can be used besides bermuda without interfering with it. So you can test without screwing up your current setup.

In the meantime a spoiler screenshot of a debug graph:

And some example stats which show that e.g. 'corridor' in my case is basically undetectable with the sensor placement (and not so great heuristics) that I have.