[Update] Routing penalties

Moderator: Unholy

Re: [Update] Routing penalties

Postby aBshield » Fri Jan 22, 2016 5:59 am

So one area I'd like to see answered is road type penalties. PRs and PLRs are spelled out on the wiki and as you mention on your list. Where I have confusion is when ramps come up. Per the Limited_Access_Interchange_Style_Guide page (and I believe elsewhere):
Ramp segments have essentially no penalty, so they can be used to connect Freeways and Major Highways with each other without causing problems.

Perhaps I'm reading too much into this, but ramp segments having no penalty implies other segments do have a penalty. I'm assuming this would only be significant to mention if segments other than PRs and PLRs have transition penalties. I may be missing it, but I don't see this spelled out anywhere. (If it is, it should definitely be linked from this page for reference IMHO.) Are there penalties transitioning from primary streets to mH or mH to MH? Are they different? We'd almost need a matrix to properly display this.

On many of your other points in your list, how do we proceed? Is there an area we can mock up some scenarios to test? That would normally be my inclination, but I don't think anyone would appreciate a test case sitting in the middle of my editable area in NJ. Do we just need to wait for DEV to respond? I'm curious about many items on the list, but I'm not clear how we find the answers to some, even if we're willing to put in the effort.
aBshield
Waze Mentor
Waze Mentor
 
Posts: 308
Joined: Tue Aug 25, 2015 2:28 pm
Location: NJ, USA
Has thanked: 77 times
Been thanked: 44 times

Re: [Update] Routing penalties

Postby aBshield » Fri Jan 29, 2016 5:42 am

CBenson wrote:
aBshield wrote:Perhaps I'm reading too much into this, but ramp segments having no penalty implies other segments do have a penalty.

I think this is primarily related to pruning effects. Other segments are "pruned" in the middle of long routes. My understanding is that means they are penalized.

That is my understanding as well now from a discussion I had with one of the NJ SMs here. I don't really see pruning discussed on the wiki other than some quick mentions on some regional pages. I'm thinking it should be addressed on this page or at least link to another page with this information. As I said in the same previous thread, my current understanding is that conventional penalties and pruning both influence the routes ultimately presented to the Wazer, but do so rather differently. To me, the former is applied on a per-segment basis and usually involves explicit and strong penalties applied at specific locations (usually when leaving segments). Pruning isn't necessarily applied on the same per-segment and/or per-location basis, but it is influenced similarly by segment types or perhaps an average of segment types when deciding which routes to present to the Wazer.

Is there any merit to also discussing pruning under the heading of penalties and this wiki page, but distinguishing the two where appropriate as above? As a relatively new editor myself, I found pruning a bit mysterious given the lack of explicit information and especially since the established editor community lumps this concept in with general penalty concepts and terminology. I don't think this is an invalid way of looking at pruning, but I also feel the distinction is important for those that like to be under the hood. I think this only fits with the wiki being very detailed on plenty of other topics.
aBshield
Waze Mentor
Waze Mentor
 
Posts: 308
Joined: Tue Aug 25, 2015 2:28 pm
Location: NJ, USA
Has thanked: 77 times
Been thanked: 44 times

[Update] Routing penalties

Postby CBenson » Fri Jan 15, 2016 10:42 pm

The routing penalties page is overdue for an update as the information is outdated.

The first thing I would like to do is change the initial message box which states the page is in draft status. The box states that those who would like to make changes or have questions should post a message in this forum, which is specifically directed to the Detour Prevention Mechanisms. I propose to change the link to this new thread. Are there any objections?
Regional Coordinator: Mid-Atlantic, US
Verizon, Nexus 6, Android 6.0.1, Waze 4.7.0.902
CBenson
EmeritusChamps
EmeritusChamps
 
Posts: 10330
Joined: Wed Nov 03, 2010 9:13 pm
Location: Crownsville, MD, US
Has thanked: 1055 times
Been thanked: 2353 times

Re: [Update] Routing penalties

Postby CBenson » Sat Jan 16, 2016 5:21 pm

What do we know effects routing?

What factors in addition to those listed here do we know effect routing?
Regional Coordinator: Mid-Atlantic, US
Verizon, Nexus 6, Android 6.0.1, Waze 4.7.0.902
CBenson
EmeritusChamps
EmeritusChamps
 
Posts: 10330
Joined: Wed Nov 03, 2010 9:13 pm
Location: Crownsville, MD, US
Has thanked: 1055 times
Been thanked: 2353 times

Re: [Update] Routing penalties

Postby CBenson » Mon Jan 18, 2016 2:45 pm

I did update the construction box on the page to refer to this thread.
Regional Coordinator: Mid-Atlantic, US
Verizon, Nexus 6, Android 6.0.1, Waze 4.7.0.902
CBenson
EmeritusChamps
EmeritusChamps
 
Posts: 10330
Joined: Wed Nov 03, 2010 9:13 pm
Location: Crownsville, MD, US
Has thanked: 1055 times
Been thanked: 2353 times

Re: [Update] Routing penalties

Postby CBenson » Mon Jan 18, 2016 9:23 pm

Ok, I'd like to go down the list and confirm what we know. My first question is regard to TBSRs. Are they still a penalty? Are they applied per segment when applied to consecutive segments? How is the penalty applied if the destination is on the segment? Do we have any idea if various vehicle/time combinations are handled identically?
Regional Coordinator: Mid-Atlantic, US
Verizon, Nexus 6, Android 6.0.1, Waze 4.7.0.902
CBenson
EmeritusChamps
EmeritusChamps
 
Posts: 10330
Joined: Wed Nov 03, 2010 9:13 pm
Location: Crownsville, MD, US
Has thanked: 1055 times
Been thanked: 2353 times

Re: [Update] Routing penalties

Postby CBenson » Fri Jan 22, 2016 1:40 pm

aBshield wrote:Perhaps I'm reading too much into this, but ramp segments having no penalty implies other segments do have a penalty.

I think this is primarily related to pruning effects. Other segments are "pruned" in the middle of long routes. My understanding is that means they are penalized.

aBshield wrote:Do we just need to wait for DEV to respond? I'm curious about many items on the list, but I'm not clear how we find the answers to some, even if we're willing to put in the effort.

My first hope is to see if we can answers from the devs like the information Karen provided for hard turn restrictions.
Regional Coordinator: Mid-Atlantic, US
Verizon, Nexus 6, Android 6.0.1, Waze 4.7.0.902
CBenson
EmeritusChamps
EmeritusChamps
 
Posts: 10330
Joined: Wed Nov 03, 2010 9:13 pm
Location: Crownsville, MD, US
Has thanked: 1055 times
Been thanked: 2353 times

Re: [Update] Routing penalties

Postby CBenson » Wed Jan 27, 2016 2:28 pm

tonestertm wrote:TBSRs are a per-segment "exit" penalty.

So I would interpret a per-segment "exit" penalty to give different results than:
tonestertm wrote:I was able to discern this by attempting to route to various addresses and places along a multi-segment (consecutive) restriction, which I had placed. Destinations at any point along the first TBSR segment were reachable. Anything past the end junction of the first TBSR would not route any farther.

If its a penalty, even per segment, then it would seem to me that waze would route through multiple segments when there is no other way to get to the destination. As waze would not route past the end of a segment with a TBSR, I would call that an actually bar to routing (or whatever we think a hard turn restriction is now) that is applied at the exit junction of the segment.

tonestertm wrote:Another bit to add to the list might be to include when penalties are ignored (e.g. starting nav on a PLR, recalcs typically ignoring such things as U-turn penalties within the first segment or two, and so on). Not sure whether that should be a separate section, or integrated in to the description of each affected penalty.

Agreed, I would tend to think it should integrated into the description of each affected penalty.
Regional Coordinator: Mid-Atlantic, US
Verizon, Nexus 6, Android 6.0.1, Waze 4.7.0.902
CBenson
EmeritusChamps
EmeritusChamps
 
Posts: 10330
Joined: Wed Nov 03, 2010 9:13 pm
Location: Crownsville, MD, US
Has thanked: 1055 times
Been thanked: 2353 times

Re: [Update] Routing penalties

Postby CBenson » Fri Jan 29, 2016 2:19 pm

I agree that pruning should be discussed. I think it can be discussed under the heading of penalties. The questions are 1) how much information waze is willing to give the public and 2) how well any information we have can be understood by those of us with little background in pathfinding algorithms.

As one with little background in pathfinding algorithms, it seems to me the basic problem addressed by pruning is that it is too processor intensive to compute the cost for every path between points 1000 miles apart. Algorithms like A*, calculate for each node an estimate of the cost to reach the destination through that node by calculating the cost to reach the node from the origin and estimating the cost to reach the destination from the node. That way the algorithm can concentrate on the nodes that are more likely to be a part of the least cost path. But I'm assuming that using A* to calculate routes based on the waze map for points 1000 miles apart is still too processor intensive to be practical. Accordingly, waze has methods to reduce the processing required. These methods would sacrifice the chance of finding the optimal route to improve the processing speed to return a result. Presumably, some of the methods waze uses are aimed at reducing the number of nodes that need to be considered.

One method of reducing the number of nodes that would need be to considered would be for the algorithm to artificially inflate (penalize) the cost to reach the node where the node is far from the origin and destination and the road type leading into the node is low. This is my understanding of how pruning works. But I would welcome any input from those with a better understanding of pathfinding algorithms.

It seems to me that these "pruning penalties" could well be explicit and strong per-segment penalties. However, they would only be applied when both the cost from origin and estimated cost to destination are greater than some trigger value based on the road type (with freeway, ramp and possibly major highway segments never triggering the pruning penalty).
Regional Coordinator: Mid-Atlantic, US
Verizon, Nexus 6, Android 6.0.1, Waze 4.7.0.902
CBenson
EmeritusChamps
EmeritusChamps
 
Posts: 10330
Joined: Wed Nov 03, 2010 9:13 pm
Location: Crownsville, MD, US
Has thanked: 1055 times
Been thanked: 2353 times

Re: [Update] Routing penalties

Postby CBenson » Fri Jan 29, 2016 6:19 pm

I'd note that the article you link to notes that A* is a generalization of Dijkstra's algorithm. And the article I linked to states that Dijkstra's algorithm is a special case of A* where the estimated cost to reach the destination from the node is not used (=0). The A* wiki states that the advantage of using the cost estimate is that it makes the routine faster. So I would guess that waze does use some kind of cost estimate to the destination in its algorithm.

We should see whether waze will tell us more about how pruning is implemented. I can't find any examples currently, but I believe that I have seen some examples of routes using street segments in the middle of long routes. So my understanding is waze will consider some low level segments in the middle of long routes where there are not good highway alternatives, which would indicate that pruning is a penalty rather than an absolute failure to consider any low segment types.

However, the term long is relative and both approaches could be used. Waze does use terms like the "long routing server." So it seems possible to me that the basic waze routing algorithm may penalize low street types in that are x distance from the ends of the route, but for routes that get kicked to "long routing server" then maybe street types aren't considered at all for the most of the route.

I'm not sure how much of the details here matter to editing. Either way we need to understand that distant destinations need to be connected by freeways and major highways and that connections between freeways and highways in the middle of long routes should not be street type because the pruning routine does not favor low road types in the middle of long routes.
Regional Coordinator: Mid-Atlantic, US
Verizon, Nexus 6, Android 6.0.1, Waze 4.7.0.902
CBenson
EmeritusChamps
EmeritusChamps
 
Posts: 10330
Joined: Wed Nov 03, 2010 9:13 pm
Location: Crownsville, MD, US
Has thanked: 1055 times
Been thanked: 2353 times

Next

Return to Wiki Updates and Discussion

Who is online

Users browsing this forum: No registered users