--- Log opened Thu May 31 00:00:53 2018
00:53 -!- mvglasow [~mvglasow@dslb-088-067-239-043.088.067.pools.vodafone-ip.de] has joined #navit
00:53 #navit: < mvglasow> Hi folks
02:53 -!- mvglasow [~mvglasow@dslb-088-067-239-043.088.067.pools.vodafone-ip.de] has quit [Ping timeout: 240 seconds]
03:06 -!- mvglasow [~mvglasow@ipservice-092-217-015-116.092.217.pools.vodafone-ip.de] has joined #navit
03:17 #navit: <+jkoan> Hi mvglasow
03:17 #navit: <+jkoan> What's the progress on traffic? :)
03:33 -!- mvglasow [~mvglasow@ipservice-092-217-015-116.092.217.pools.vodafone-ip.de] has quit [Quit: Leaving]
03:41 -!- aerostitch [~aerostitc@c-67-164-55-119.hsd1.ca.comcast.net] has quit [Quit: Leaving]
04:43 -!- xenos1984 [~xenos1984@2001:bb8:2002:200:6651:6ff:fe53:a120] has joined #navit
04:43 -!- mode/#navit [+v xenos1984] by ChanServ
05:55 -!- naggety [~naggety@115.red-2-142-64.dynamicip.rima-tde.net] has joined #navit
08:17 #navit: <@KaZeR> hey naggety ! good to see you!
08:18 #navit: < naggety> hi KaZeR!
08:27 -!- Mineque [~mineque@62-210-136-72.rev.poneytelecom.eu] has quit [Quit: The Lounge - https://thelounge.github.io]
08:29 -!- Mineque [~mineque@62-210-136-72.rev.poneytelecom.eu] has joined #navit
08:36 -!- Mineque [~mineque@62-210-136-72.rev.poneytelecom.eu] has quit [Quit: The Lounge - https://thelounge.github.io]
08:39 -!- Mineque [~mineque@62-210-136-72.rev.poneytelecom.eu] has joined #navit
08:42 -!- Mineque [~mineque@62-210-136-72.rev.poneytelecom.eu] has quit [Client Quit]
08:44 -!- Mineque [~mineque@62-210-136-72.rev.poneytelecom.eu] has joined #navit
08:49 -!- Mineque [~mineque@62-210-136-72.rev.poneytelecom.eu] has quit [Quit: The Lounge - https://thelounge.github.io]
08:52 -!- Mineque [~mineque@62-210-136-72.rev.poneytelecom.eu] has joined #navit
09:37 #navit: < naggety> KaZeR: what did you find about removed strings from some languages? Was it OK?
13:53 -!- noradtux [~noradtux@2a04:4540:8c04:4b01:982a:e0b0:885c:fddc] has quit [Ping timeout: 245 seconds]
13:58 -!- naggety [~naggety@115.red-2-142-64.dynamicip.rima-tde.net] has quit [Quit: Konversation terminated!]
13:58 -!- noradtux [~noradtux@port-73408.pppoe.wtnet.de] has joined #navit
14:30 -!- xenos1984 [~xenos1984@2001:bb8:2002:200:6651:6ff:fe53:a120] has quit [Quit: Leaving.]
14:48 -!- xenos1984 [~xenos1984@22-164-191-90.dyn.estpak.ee] has joined #navit
14:48 -!- mode/#navit [+v xenos1984] by ChanServ
15:07 -!- mvglasow [~mvglasow@ipservice-092-217-015-116.092.217.pools.vodafone-ip.de] has joined #navit
15:08 #navit: < mvglasow> hi folks
15:32 #navit: <+jkoan> Hi Kazer and mvglasow
15:32 #navit: < mvglasow> hi jkoan
15:33 #navit: < mvglasow> to answer your earlier question: a few things are in place, but I am really stuck on one thing
15:33 #navit: < mvglasow> namely, rerouting if a traffic feed causes segment costs to change
15:34 #navit: < mvglasow> are you somewhat familiar with the routing algorithm?
16:03 -!- aerostitch [~aerostitc@VEVO-LLC.bar2.SanFrancisco1.Level3.net] has joined #navit
17:15 #navit: <+jkoan> mvglasow: no,sorry, dont know anything from the code
17:18 #navit: < mvglasow> too bad, but maybe someone else here is familiar with the Dijkstra routing algorithm
17:18 #navit: < mvglasow> anyone interested is invited to take a look here:
17:18 #navit: < mvglasow> https://github.com/mvglasow/navit/issues/2
17:18 #navit: < mvglasow> or here: https://cs.stackexchange.com/questions/92568/lpa-implementation-keeps-looping
17:19 #navit: < mvglasow> basically, I've implemented LPA* to do partial route recalculation when segment costs change
17:19 #navit: < mvglasow> but it isn't working as expected, it keeps looping over the same points, over and over again
17:19 #navit: < mvglasow> I’ve tried a lot of things, but to no avail
17:21 #navit: <+jkoan> no i cant help with this, sorry
17:21 #navit: < mvglasow> well, if anyone else feels competent to help here, feel free to come forward
17:22 #navit: <+jkoan> may i ask whats the benefit of LPA* over Dijkstra? 
17:23 #navit: < mvglasow> LPA* is essentially an evolution of A* (which, in turn, is an evolution of Dijkstra)
17:24 #navit: < mvglasow> with Dijkstra, you need the route graph and all costs from the start
17:24 #navit: < mvglasow> and if sonething changes, you need to start over from scratch
17:24 #navit: <+jkoan> so better math and faster?
17:24 #navit: < mvglasow> which gets inconvenient if you have a long route
17:25 #navit: < mvglasow> LPA* can handle situations in which only some segments’ cost has changed
17:25 #navit: < mvglasow> and recalculates only the affected portions of the route graph
17:25 #navit: < mvglasow> so in theory it should be faster when processing a traffic update
17:26 #navit: <+jkoan> sounds nice
17:27 #navit: < mvglasow> in theory, yes - practice is a bitch, though :-)
18:55 #navit: <+jkoan> I watched some videos and read some Wikipedia enteries. And A* really looks faster, and more efficient than Dijkstra. Did you also know negative cons to A* or is is "always" better?
18:57 #navit: <+jkoan> Also, do you know if the current routing algorithm does multi tasking? And would that increase the performance much? ^^ I am noch good enough in math, but it's really interesting
19:03 #navit: < mvglasow> I ran some tests with A* a while back, and it turns out that for Navit, it is in fact slower...
19:03 #navit: < mvglasow> ...the performance gain of A* is its heuristic...
19:04 #navit: < mvglasow> ...which means it'll focus on the nodes which are closer to the "other end" of the route
19:05 #navit: < mvglasow> With standard Dijkstra, the route graph is flooded in a somewhat circular shape around the destination
19:05 #navit: < mvglasow> With A*, it's more of a spindle shape, with the tip pointing to the current position
19:06 #navit: < mvglasow> That means it takes fewer node expansions to reach the start
19:06 #navit: < mvglasow> at the expense of having to calculate the heuristic for each node
19:07 #navit: < mvglasow> Navit builds the route graph using a set of rectangles around destination, start and both
19:08 #navit: < mvglasow> thus giving us many of the benefits of A*
19:08 #navit: < mvglasow> at the expense of potentially missing a cheaper path that happens to lie outside the rectangle
19:09 #navit: < mvglasow> which already preempts much of the performance savings of A*
19:10 #navit: < mvglasow> but we'd still have the additional burden of calculating heuristics
19:13 #navit: < mvglasow> making it slower when considering everything
19:20 -!- aerostitch [~aerostitc@VEVO-LLC.bar2.SanFrancisco1.Level3.net] has quit [Ping timeout: 276 seconds]
19:23 -!- aerostitch [~aerostitc@VEVO-LLC.bar2.SanFrancisco1.Level3.net] has joined #navit
19:42 #navit: <+jkoan> So the calcu of the heuristic is the problem? Could we somehow optimize this to improve the general performance of A* in navit?
19:42 -!- aerostitch [~aerostitc@VEVO-LLC.bar2.SanFrancisco1.Level3.net] has quit [Ping timeout: 240 seconds]
19:43 #navit: < mvglasow> Well. I used a crude heuristic, assuming as-the-crow-flies distance and a speed of 250 km/h
19:44 #navit: < mvglasow> In order to be admissible, a heuristic has to be guaranteed to never exceed the actual cost
19:44 #navit: < mvglasow> So taking shortest possible distance and maximum possible speed would work for us
19:45 #navit: < mvglasow> As a refinement, one could sift through the current vehicleprofile, scan for the highest speed assumed for any kind of way, and use that
19:46 #navit: < mvglasow> This would give a better heuristic and thus better performance, as we would evaluate fewer nodes we'd end up not needing
19:46 #navit: < mvglasow> Alternatively...
19:46 #navit: < mvglasow> ...we could ditch the separation between building and flooding the route graph
19:47 #navit: < mvglasow> use LPA* with a proper heuristic (highest speed assumed in vehicleprofile)
19:47 #navit: < mvglasow> and whenever we expand a node, retrieve all connecting segments from the map
19:48 -!- aerostitch [~aerostitc@VEVO-LLC.bar2.SanFrancisco1.Level3.net] has joined #navit
19:48 #navit: < mvglasow> so we'd build the route graph as we flood it
19:49 #navit: < mvglasow> which would still leave us with the burden of the heuristic
19:49 #navit: < mvglasow> and recalculations (if we deviate from the route) might become more expensive to do
19:49 #navit: < mvglasow> but initial calculation would potentially be faster
19:50 #navit: < mvglasow> and we'd be guaranteed not to miss any valid routes
19:50 #navit: < mvglasow> however, that requires getting LPA* to work first
19:55 #navit: <+jkoan> A hat about something like a temporary reroute and calculate a complete new route in the background? This would be good for the user since he could drive by and also got the best route as well. Or did this would not work so good since the target is moving (seen from the algorithm starting point, the destination)?
20:04 #navit: < mvglasow> Might be an option of all else fails. A useful by-product would be the ability to re-route in the background e.g. if the driver leaves the route, and keep the previous route displayed until the new one is complete.
20:04 #navit: < mvglasow> ^if all else fails
20:05 #navit: < mvglasow> though I can't tell at this point if and how Navit can handle multiple routes
20:05 #navit: < mvglasow> as for your earlier question on multithreading:
20:06 #navit: < mvglasow> the routing algorithm itself is not multi-threaded, and most parts of Navit seem to be single-threaded as well (which is suboptimal)
20:07 #navit: < mvglasow> Some parts of routing can run in an idle loop, running a few iterations, then processing events from the foreground, then running another couple of iterations and so on
20:08 #navit: < mvglasow> Currently most loops "yield" based on number of iterations
20:08 #navit: < mvglasow> though it would probably be better to do that based on time elapsed
20:09 #navit: < mvglasow> maybe one could turn that into a true multi-threaded implementation (on platforms which support it)
20:09 #navit: < mvglasow> but that would require properly synchronizing access to all data structures shared between threads
20:10 #navit: < mvglasow> since Navit (apparently) wasn't consistently designed with this in mind, adding this after the fact is unpredictable
20:11 #navit: < mvglasow> we may be lucky and find some things can be easily spun off into their own threads
20:11 #navit: < mvglasow> or we may not
20:18 #navit: <+jkoan> Sounds complicated indeed
22:20 -!- xenos1984 [~xenos1984@22-164-191-90.dyn.estpak.ee] has quit [Quit: Leaving.]
23:26 -!- Horwitz [~mich1@p200300800E002A00022268FFFE64E7C4.dip0.t-ipconnect.de] has quit [Ping timeout: 256 seconds]
23:39 -!- Horwitz [~mich1@p200300800E001600022268FFFE64E7C4.dip0.t-ipconnect.de] has joined #navit
23:39 -!- mode/#navit [+o Horwitz] by ChanServ
23:42 -!- aerostitch [~aerostitc@VEVO-LLC.bar2.SanFrancisco1.Level3.net] has quit [Remote host closed the connection]
--- Log closed Fri Jun 01 00:00:54 2018