2021-01-13 09:48:25

Hello guys,
I guess some of you remember me. I developed an app (actually web app) to help blind users to navigate. After doing so I got an advices to make it as a native app, because web interface, impossibility to make app as a service and other glinches that creaped out, so I finally decided to make an native Android app as a navigation for the blind.
About 6 years ago I developed an app called Walk helper for blind as well and got no less than 10k downloads which is pritty impressive I can say, especially when it wasn't very good. It didn't have turn by turn features and could be used only for custome routes and since I lost it's sourcecode, I dropped that as well.
Now I intent to do it on my freetime so it could be a bit slow, but I already began to experiment with Mapquest, Open street maps, Google maps APIs. I don't know yet which way will I decide to go, however for example with Mapquest, I get turn-by-turn steps and already got lucky extracting / parsing them. So I have lat/ lon, names, distances... I already made calculations for cardinal directions (east, southwest etc.), clock directions, as well as by degrees of-course, so you would no the way you're heading to (relative directions) in your prefered manner. I guess just simple as turn right, or turn sharp left / slight left will be implemented as well, because there is almost same algorithm for all of them.
Now my biggest challenge:
I do have calculations of a distance from the current location to the next point that I need to approach, absolute direction in a glance of a true north, relative directions as well as I said, accuracy, movement speed, but I have no good algorithm of detecting when to asume that user reached the point so I should show him / her the next step. In the past that is what I was doing:
I calculated the distance between current location and the current step / point and threshold as for instance 10 meters, so if your distance to the current point is less than 10m, you got redirected to the next point. Also if your relative direction to the current point shows that point is behind you (something in range of 135 and 225 degrees) and now you're heading to the next step (in range of for instance 315 and 45 degrees), then you got redirected as well. I don't like this algorithm, because streets aren't always straight and routing services aren't always that friendly to add extra steps during the slight turns of a street when it does so. I can check an accuracy and modify threshold of a distance in terms of it, but I don't like that as well, because sometimes routing services give points that are in a middle of a street and actually you can not locate there and got redirected a lot later than that, or might not be redirected as well due to not straight streets.
I thaught of a bounding boxes which would help in termps of a shape of street, but routing services do not give that information for a single step, only for a wide of all route. Now I consider about the formula which calculates lat / lon by giving coordinates of a point, bearing and the distance to get where point would be. So my point is to add points each 10 meters from the current step towards next point and always mesure distance from current location to the virtually made points and mark them as user crosses by. Although it looks better than algorithms I mentioned before, but it still the distance which creeps especially near toll buildings or so.
I just need some thaughts when should I redirect user to the next step / point and how to check properly if user follows the route or not?

2021-01-13 18:22:24

No one has solved these problems.  If you do, you'll be the first.  These problems are why we don't just all grab Siri or whatever and have at it.

When you do this for a car, you can easily just say the radius is like 100 meters which is what the car GPS probably does, then trust the sighted driver to correct by looking for the right street sign.  You can also use the fact that cars move in predictable patterns and with relatively predictable velocities to figure out when they're going to hit the next point.  But you haven't even started talking about GPS accuracy yet, which is usually much too bad for fine detail when walking.  5 meters is the best case.  20 meters is what I've seen on average, with the occasional spike to 50 or 100.  Your app is basically always going to start directing people into the middle of the road at some point, and you can't work around it.

Put another way: there's a reason Blindsquare doesn't do a hell of a lot more than it does.

My Blog
Twitter: @ajhicks1992

2021-01-13 19:25:10

Camlorn is correct. Consumer grade GPS is rather inaccurate. Military GPS Is far more accurate, up to a Meer I've heard, But as a normal person you can't access it. We eventually might be able to as the original GPS we know now was only for military use, but don't hold your breath. You could use What Three Words. Which is a system that mapped 3 word phrases to a meter gridmap of the entire globe.

I don’t believe in fighting unnecessarily.  But if something is worth fighting for, then its always a fight worth winning.
check me out on Twitter and on GitHub

2021-01-13 20:07:36

@3
Unless you have a very good source, consumer vs military gps is a myth and you're making an inaccurate claim.  it is actually possible to get consumer-grade GPS accurate to roughly an inch (I can probably find that paper again) but it takes too much computing power and specialized hardware to be feasible for phones.  We use the same satellites and stuff now, as far as I know, and have since the early 2000s.

The real problem is that the atmosphere is in the way.  You get changes in the ionosphere, a cloud, different air pressure, different humidity, etc. and this changes the characteristics of the signal.  But that's for a thing where the entire point is you're estimating distances based off the signal whose characteristics just got changed, so doesn't end super well.

There's also issues with being near the poles.  Pretty sure that most/all of the gps satellites are near the equator as well because we want geosynchronous orbits, but has been a while since I looked into that aspect.

My Blog
Twitter: @ajhicks1992

2021-01-13 20:38:52

This is one of those points that is so stupid, but easy to overlook and still worth making. Data is important, too.

I actually know something about this subject because I've been writing my own GPS navigation app for a while now. Nothing released, because the last thing I need is some idiot to sue me for getting killed because it tells them that crossing a 4-lane highway is safe, or to ask me a bunch of questions about how to install Docker to run the importer.

But if you're getting directions from a routing service, you're probably getting point-to-point directions. You really need geospatial maps--as in, linestrings for roads so you can use point-to-line calculations to figure out what road someone is on. You also need context, and a *lot* of tuning. As pointed out, GPS readings can actually be pretty accurate. One optimization I've put into my code is for the app to not change what road it reports the person as being on until they're some distance, 50 meters or so, from the previous road. Otherwise, it'd assume I was on a new road as I stepped into the intersection. And technically it was right, it just wasn't particularly useful information to me, nor was it safe having my phone prattle at me every time I set foot on a cross street. smile There's no easy way to figure this stuff out in advance, either. You have to walk, and walk and walk and walk. And ride around in cars and buses. And regularly re-import your data to ensure that you've got the latest, because OSM isn't always as accurate as we might wish.

I'd suggest looking into a few projects. Look at spatialite for map storage. That'll get you an SQLite-based geospatial datastore which gives you all the complex queries you'd need. For import, look into ogr2ogr, which converts from just about any spatial/cartographic format into just about any other. Grab OSM data for your location in pbf format, convert it to a spatialite database, and learn how the queries work by reading through the tutorials and working in the command line tool.

Also, connectivity. About 10 years or so ago, when phones were less powerful and had just a few GB of storage, I built this as an online-only service. You may or may not be surprised at how quickly and easily connections drop, fail, etc. Streaming services work around this in a number of ways, but be prepared to spend lots of time debugging connection dropouts and such. It's really better to suck it up and go the offline route if you can teach yourself the relevant SQL.

I should probably open source this stuff someday, and slap a big fat old "get killed at your own risk" disclaimer on it, along with "if you can't build the importer Docker containers yourself then this isn't for you." So much work, though...

2021-01-13 21:21:13

@2, that's what I actually wanted to hear. You're right, it's easy for an app to detect when car will be at some point, because it moves way faster than the person and that increeses direction accuracy as well, as possibility to calculate pritty exact speed due to movement stability. Accuracy is real problem here, because as you already mentioned here, we usually get 10 to 20 meters due to various factors like buildings, weather conditions, clearity of the sky and better accuracy requires expensive and much powerful hardware. When accuracy jums drastically we can determine it, but that's only that. If it isn't stable, I guess there is less we can do, however we still use these navigation systems and perhaps there's at least something that's not been done and could be done in the terms of software to improve navigation experience, but sadly, I don't know what could it be. I see that we can not prevent an app from directing people towards the middle of a street, but in case of at least better navigation that could be more useful than Google maps if in case of the state of a problem, could at least determine when to redirect user to the next point for starters and consistently say where is the current point in relative direction. There are plenty of navigation apps for the blind that offer similar functionality, but they still can not pull it off, so sadly I guess you're correct.
@3, I don't get it how exactly What Three Words would do to help me out in making an algorithm I described?
@5, Yes, I know how to use docker, not a professionally, because we use docker-compose in the job and only thing I need to do with that is to start containers and work within the inner VM as a big project, on which smaller parts of a system are built, but anyway, it's another topic. Now in a matter of navigation, again, yes, I'm getting turn-by-turn directions. They don't give me the lines of streets, of course if they would, I would be happy about it, because at least I could make it better than that of an algorithm that's based only on radius and the relative direction which is not enouth as we all pointed out. I am not a stranger to SQL, this language is in everyday activity so I'll definately check it out and the resources you mentioned here could be quite useful. Yeah, perhaps it will not become a tool for wide usage because of a drawbacks we had gathered, although it will still be interesting to experiment and explore what I can do.

2021-01-13 21:41:05

yes, high accuracy (( 2 cm) consumer gps is possible, but you need access to base stations data , which can be free or paid, depending on the country:
https://novatel.com/an-introduction-to- … ematic-rtk
The cheapest receiver supporting this technology I could find is 200€. Worth it, I say, if the accuracy is really as good and stable as it says.

2021-01-13 21:44:29

@6
You know that Google and Siri both give walking directions nowadays, right?  It seems to me that what you want to build is already mostly built, at least to the limits of what GPS is going to let you do.

That said, there's a lot of demand for what would basically be blindsquare for Android by all accounts, so it wouldn't be useless or anything like that.  Hell, you could probably sell it.

@5
if you're worried about being sued then 2 hours with a competent lawyer should give you sufficient terms and conditions.  I'm not sure how that's a concern though, in the sense that if it just blatantly says "this app cannot replace O&M skills" or something every time it loads you're probably fine.

Obviously everything else you're saying applies though: there's a reason I yanked camlorn_audio, after all.

My Blog
Twitter: @ajhicks1992

2021-01-13 22:16:43

@8, Google and Siri give turn-by-turn directions in a terms of mapps app depending on a platform, nothing more. So it don't even says which way I am heading or what's the relative direction to the point I am approaching. I see pritty good apps on Play store that can be used for navigation, but features I like are scattered across different apps, at least on Android, because I am Android user. Had an Iphone few years ago, but decided to stick with Android for an easy development and bunch of other things, however, I can't find a proper app still. Dotwalker PRO was like an app I like, however as I understand it, Google maps API key is expired. Lazarilo does some job in terms of navigation, but I always need to stick to my screen to check my direction and something is wrong with other functions as well, because accuracy of direction change is horible, I tested with my own app that I started to make and it is much way responsive than what they have, so I am really amazed, also they have no compass feature which is really important no doubt. And Seeing assistant move gives turn by turn instructions by spredding points across the area without any names on them like point1, point2 and so on and so forth, detection of redirection to the next point is totaly based on distance nothing more, so I don't like it. I don't know anything better sad

2021-01-13 22:24:32

I mean. Something like Siri will say "head east on".  Maybe getting this as right as you want is very, very useful.  it just seems to me that right 75% of the time might as well be wrong 100% of the time because that still means you can't trust it.  Things like heading are only really useful in big fields or whatever; in a city, for example, you have to go out of your way to get where you want to be pretty much always.

When heading matters I drop my destination into Blindsquare and hit track and that does what you want for destination, but getting walking a line of points where the points are close enough together to be super useful isn't going to happen how you want.

My Blog
Twitter: @ajhicks1992

2021-01-13 22:29:57

We really need an anti Camlorn who is just as knowledgeable but doesn't treat people's feelings like a computer would.
His down to earth realism is very useful, but we could definitely use a positive counterpoint for the sake of balance around here.

2021-01-13 22:40:49

@10, Yes, that's the problem that in short distances gps begins to be even bigger crap and I can't think of any algorithm to at least know when to even redirect a person (I mean if algorithm isn't based only on distance and direction trust / mistrust). However heading in compass is another thing. If GPS doesnt drive nuts, then compass / magnetofield is totaly useful to get heading toward the point or as a cardinal one. I don't know how long it can be turned on before gets out of proper callibration, but in the terms of checking the direction it's good. Especially if you spin your device around and it vibrates / gives a feedback that you point towards the target, and for instance helps you to point at it by guiding you to turn device more to the left / right before we point correctly.
I even started to consider of using accelerometer and calculate the steps for some use, though don't yet figured out whether it will help or just complicate things up even more.

2021-01-13 22:41:04

What's wrong with what essentially boils down to "relax your requirements and you can have something that you can sell to people"?  People have been trying to crack this problem for a long time, every self-driving car startup for example.  The requirement has to be relaxed.  Doing as good as blindsquare gets you $20000+ if I had to estimate, if you wanted to go commercial.  That's pretty good and something blind people have been asking for for Android for years and years now.

But phones aren't going to walk you places for a long time, and certainly not without more hardware.

My Blog
Twitter: @ajhicks1992

2021-01-13 22:54:39

@13, I'll consider what you said here.
By chatting with you and getting your thaughts led me to another idea with redirection to the next point, but I guess I'll think of it more before trying to explain what I think, because I need to understand that formula more deeply and check if it can help at some certain cituations.

2021-01-14 00:06:04

Yeah, I think relaxing your requirements is a good idea here. If your goal is "don't direct someone to the middle of streets," you'll have a hard time with it. But if it's "give users as much information as they can get about their surroundings and rely on them for the smarts," you can actually do quite a lot.

For instance, while I can fairly reliably locate intersections, the "location" of the intersection seems to be the point where the individual road lines cross, rather than a circular shape encompassing the area. This is sufficient for telling someone that they're near an intersection, and even describing it in detail. But because that intersection is a single point, the distances at which you get intersection notifications can vary from almost on top of the intersection to 30-40 meters back based on the curvature of the member roads, and no amount of tuning thresholds will give you a 100% satisfactory solution. You have to just be OK with that, solve the problems you can, and embrace the limitations of your technology and available data.

There's actually a lot of data in OSM that most blindie GPS apps which use it just leave on the table, which I think is super unfortunate. For instance, there's lots of mapped river/stream data on OSM. Imagine a GPS navigation app that could tell you what river your kayak is on, with notifications about upcoming forks, or side streams you might explore. Likewise for trails in parks, sometimes even including landmarks like bridges and stairs. In some ways, relaxing requirements could actually be liberating, because if you stop trying to solve the problems you can't, you can focus more on interesting ones you might make headway on.