Weighted pathfinding influenced by arbitrary dimension

3 posts / 0 new
Last post
eddieoffermann
Weighted pathfinding influenced by arbitrary dimension

Complex challenge, so please bear with me:

General challenge:
I have an application that's meant to associate an additional dimension with particular route-segments or to create another type of weighted pathfinding. Let's call that dimension "Wildcard." Wildcard would be weighted against the other considerations like traffic, distance, etc., and could be given its own configurable overall weight versus other dimensions, similar to the way factors like travel time and distance are often balanced against each other in pathfinding.

Wildcard would be a return value from a machine learning algorithm. It's essentially a range of 0-1 or -1 to 1, indicating avoidance or attractance based on the criteria evaluated by the algorithm. Exactly how we communicate that value can be flexible to meet the needs and capabilities of the underlying pathfinding algorithms. They could be specific to roads, they could be geofenced regions, they could be points on an evenly-spaced grid, etc.

Wildcard "weight" would be an indicator of how much preference we want to apply to Wildcard values in the pathfinding calculation. It could be a multiplier applied to the Wildcard values or delivered separately to the API.

Ideally, this value could be populated to the pathfinding engine directly and used in the original calculation. I’m not aware of any APIs that currently allow this - though it seems like mostly a problem of how to communicate that extra piece of data to the algorithm, not so much a shortcoming of the algorithms themselves which are already attracted or repelled by attributes of the dataset.

MapQuest-specific:
For APIs  (like Mapquest’s) that permit requesting multiple paths with an acceptable temporal variance, Wildcard values could be used to filter those results to provide only the most desirable ones to the end user. That's not ideal, but it's definitely my backup plan.

Similarly MapQuest’s API has the “mustAvoidLinkIDs” and “tryAvoidLinkIDs” - which could suggest a set of companion behaviors like “tryAttractLinkIDs”. That would be potentially useful to me.

Route Control Points are potentially very similar to what I want - though I'd want to be able to provide a fairly granular heatmap (say at a .1 or .2 km frequency) and I'm not sure how much that would throw off Pathfinding. The goal wouldn't be to create incredibly circuitous routes - we don't actually want to prefer points over actually getting to the destination - but the goal is actually to implement an additional tradeoff between diligently seeking the shortest, fastest route according to the data available in favor of other criteria defined in the learning algorithm that generates the Wildcard values.

So what's my question?
My instinct right now is to create a fairly dense (.1km) mesh of Route Control Points spread across a region between a start and end point and just see what happens - but would love it if someone can give me an indication of whether that's going to completely wreck the wayfinding algorithm or not. For testing purposes, I'll be able to provide influencer datasets while we collect real world data to train the model. We don't know what the outcome will be, but we can guess what it will look like.

Additionally, if there are other options I'm not aware of - or that may be on the roadmap but not yet implemented - that would be helpful as well as I try to select the dataset and API we use for the actual mapping and wayfinding behavior.


MQBrianCoakley
It sounds like route control
It sounds like route control points are the way to go. While this will influence the route, how much it is wrecked depends on the points, the route, and what you believe wrecked is. The only way to determine if it will fit the bill would be to test it. There are no other route options available other than what is already documented in the user guide.

eddieoffermann
Thanks - route control's

Thanks - route control's probably it. In my case "wrecked" would be a route that became *too* circuitous. The goal is to create a path that no current wayfinding solution would suggest on its own - that's perhaps a little farther, maybe takes a bit longer, but matches another set of needs better. Ideally, even if it goes a bit out of its way, it doesn't loop back on itself or make a city-wide weaving path.

I have an algorithm for distributing my influencer data to make it more or less sparse - it's probably time to build a prototype and start fiddling with the knobs until I get results that I like. Thanks!