Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Use distance threshold in hierarchy limits for bidir-astar #3156

Merged
merged 8 commits into from
Jun 25, 2021
Merged

Use distance threshold in hierarchy limits for bidir-astar #3156

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
8 commits
Select commit Hold shift + click to select a range
cee6b86
Use 'distance' threshold in hierarchy limits for bidir-astar
genadz Jun 14, 2021
fbd8f24
Update changelog
genadz Jun 17, 2021
5c537dd
Merge branch 'master' into kgv_inc_hi_limits
genadz Jun 17, 2021
3f672a1
Avoid unnecessary distance calculation if hierarchy limits are disabled
genadz Jun 21, 2021
b7c2f94
Merge branch 'master' into kgv_inc_hi_limits
genadz Jun 21, 2021
3796635
Merge branch 'master' into kgv_inc_hi_limits
genadz Jun 23, 2021
fcebc3e
Merge branch 'master' into kgv_inc_hi_limits
genadz Jun 24, 2021
3f5df10
Merge branch 'master' into kgv_inc_hi_limits
genadz Jun 25, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Next Next commit
Use 'distance' threshold in hierarchy limits for bidir-astar
  • Loading branch information
@genadz
genadz committed Jun 17, 2021
commit cee6b86c410df6e1bba14d601588bd79413f6156
2 changes: 1 addition & 1 deletion run_route_scripts/run_with_server.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -85,7 +85,7 @@ def make_request(post_body):
parser.add_argument('--output-dir', type=str, help='The directory in which to place the result of each request')
parser.add_argument('--concurrency', type=int, help='The number of processes to use to make requests', default=multiprocessing.cpu_count())
parser.add_argument('--format', type=str, help='Supports csv, json, raw and null output formats', default='csv')
parser.add_argument('--headers', type=str, help='Additional http headers to send with the requests. Follows the http header spec, eg. some-header-name: some-header-value', action='append', nargs='*')
parser.add_argument('--headers', type=str, help='Additional http headers to send with the requests. Follows the http header spec, eg. some-header-name: some-header-value', action='append', nargs='*', default=[])
Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

this script failed if --headers parameter wasn't specified. adding default value fixes it

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

strange! i swore i tested that... thank you for cleaning it up!

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@mandeepsandhu this is where you saw that

parsed_args = parser.parse_args()

# make the output directory
Expand Down
43 changes: 31 additions & 12 deletions src/thor/bidirectional_astar.cc
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -163,7 +163,7 @@ inline bool BidirectionalAStar::ExpandInner(baldr::GraphReader& graphreader,
// that level. If using a shortcut, set the shortcuts mask. Skip if this is a regular
// edge superseded by a shortcut.
if (meta.edge->is_shortcut()) {
if (hierarchy_limits[meta.edge_id.level() + 1].StopExpanding()) {
if (hierarchy_limits[meta.edge_id.level() + 1].StopExpanding(pred.distance())) {
shortcuts |= meta.edge->shortcut();
} else {
return false;
Expand Down Expand Up @@ -272,11 +272,9 @@ inline bool BidirectionalAStar::ExpandInner(baldr::GraphReader& graphreader,

// Find the sort cost (with A* heuristic) using the lat,lng at the
// end node of the directed edge.
float dist = 0.0f;
float sortcost =
newcost.cost + (FORWARD
? astarheuristic_forward_.Get(t2->get_node_ll(meta.edge->endnode()), dist)
: astarheuristic_reverse_.Get(t2->get_node_ll(meta.edge->endnode()), dist));
newcost.cost + (FORWARD ? astarheuristic_forward_.Get(t2->get_node_ll(meta.edge->endnode()))
: astarheuristic_reverse_.Get(t2->get_node_ll(meta.edge->endnode())));

// not_thru_pruning_ is only set to false on the 2nd pass in route_action.
bool thru = not_thru_pruning_ ? (pred.not_thru_pruning() || !meta.edge->not_thru()) : false;
Expand All @@ -285,6 +283,8 @@ inline bool BidirectionalAStar::ExpandInner(baldr::GraphReader& graphreader,
uint32_t idx = 0;
if (FORWARD) {
idx = edgelabels_forward_.size();
// Calculate distance from the origin. It will be used by hierarchy limits
const auto dist = astarheuristic_reverse_.GetDistance(t2->get_node_ll(meta.edge->endnode()));
edgelabels_forward_.emplace_back(pred_idx, meta.edge_id, opp_edge_id, meta.edge, newcost,
sortcost, dist, mode_, transition_cost, thru,
(pred.closure_pruning() || !costing_->IsClosed(meta.edge, tile)),
Expand All @@ -294,6 +294,8 @@ inline bool BidirectionalAStar::ExpandInner(baldr::GraphReader& graphreader,
adjacencylist_forward_.add(idx);
} else {
idx = edgelabels_reverse_.size();
// Calculate distance from the destination. It will be used by hierarchy limits
const auto dist = astarheuristic_forward_.GetDistance(t2->get_node_ll(meta.edge->endnode()));
edgelabels_reverse_.emplace_back(pred_idx, meta.edge_id, opp_edge_id, meta.edge, newcost,
sortcost, dist, mode_, transition_cost, thru,
(pred.closure_pruning() || !costing_->IsClosed(meta.edge, tile)),
Expand Down Expand Up @@ -390,7 +392,8 @@ bool BidirectionalAStar::Expand(baldr::GraphReader& graphreader,
// if this is a downward transition (ups are always allowed) AND we are no longer allowed OR
// we cant get the tile at that level (local extracts could have this problem) THEN bail
graph_tile_ptr trans_tile = nullptr;
if ((!trans->up() && hierarchy_limits[trans->endnode().level()].StopExpanding()) ||
if ((!trans->up() &&
hierarchy_limits[trans->endnode().level()].StopExpanding(pred.distance())) ||
!(trans_tile = graphreader.GetGraphTile(trans->endnode()))) {
continue;
}
Expand Down Expand Up @@ -480,6 +483,9 @@ BidirectionalAStar::GetBestPath(valhalla::Location& origin,
SetOrigin(graphreader, origin, forward_time_info);
SetDestination(graphreader, destination, reverse_time_info);

// Update hierarchy limits
ModifyHierarchyLimits();

// Find shortest path. Switch between a forward direction and a reverse
// direction search based on the current costs. Alternating like this
// prevents one tree from expanding much more quickly (if in a sparser
Expand Down Expand Up @@ -620,7 +626,7 @@ BidirectionalAStar::GetBestPath(valhalla::Location& origin,
// Prune path if predecessor is not a through edge or if the maximum
// number of upward transitions has been exceeded on this hierarchy level.
if ((fwd_pred.not_thru() && fwd_pred.not_thru_pruning()) ||
hierarchy_limits_forward_[fwd_pred.endnode().level()].StopExpanding()) {
hierarchy_limits_forward_[fwd_pred.endnode().level()].StopExpanding(fwd_pred.distance())) {
continue;
}

Expand All @@ -639,7 +645,7 @@ BidirectionalAStar::GetBestPath(valhalla::Location& origin,

// Prune path if predecessor is not a through edge
if ((rev_pred.not_thru() && rev_pred.not_thru_pruning()) ||
hierarchy_limits_reverse_[rev_pred.endnode().level()].StopExpanding()) {
hierarchy_limits_reverse_[rev_pred.endnode().level()].StopExpanding(rev_pred.distance())) {
continue;
}

Expand Down Expand Up @@ -846,13 +852,16 @@ void BidirectionalAStar::SetOrigin(GraphReader& graphreader,
// We assume the slowest speed you could travel to cover that distance to start/end the route
// TODO: assumes 1m/s which is a maximum penalty this could vary per costing model
cost.cost += edge.distance();
float dist = astarheuristic_forward_.GetDistance(nodeinfo->latlng(endtile->header()->base_ll()));
float sortcost = cost.cost + astarheuristic_forward_.Get(dist);
float sortcost =
cost.cost + astarheuristic_forward_.Get(nodeinfo->latlng(endtile->header()->base_ll()));

// Add EdgeLabel to the adjacency list. Set the predecessor edge index
// to invalid to indicate the origin of the path.
uint32_t idx = edgelabels_forward_.size();
edgestatus_forward_.Set(edgeid, EdgeSet::kTemporary, idx, tile);
// Calculate distance from the origin. It will be used by hierarchy limits
const auto dist =
astarheuristic_reverse_.GetDistance(nodeinfo->latlng(endtile->header()->base_ll()));
edgelabels_forward_.emplace_back(kInvalidLabel, edgeid, directededge, cost, sortcost, dist, mode_,
-1, !(costing_->IsClosed(directededge, tile)),
static_cast<bool>(flow_sources & kDefaultFlowMask),
Expand Down Expand Up @@ -932,14 +941,16 @@ void BidirectionalAStar::SetDestination(GraphReader& graphreader,
// We assume the slowest speed you could travel to cover that distance to start/end the route
// TODO: assumes 1m/s which is a maximum penalty this could vary per costing model
cost.cost += edge.distance();
float dist = astarheuristic_reverse_.GetDistance(tile->get_node_ll(opp_dir_edge->endnode()));
float sortcost = cost.cost + astarheuristic_reverse_.Get(dist);
float sortcost =
cost.cost + astarheuristic_reverse_.Get(tile->get_node_ll(opp_dir_edge->endnode()));

// Add EdgeLabel to the adjacency list. Set the predecessor edge index
// to invalid to indicate the origin of the path. Make sure the opposing
// edge (edgeid) is set.
uint32_t idx = edgelabels_reverse_.size();
edgestatus_reverse_.Set(opp_edge_id, EdgeSet::kTemporary, idx, opp_tile);
// Calculate distance from the destination. It will be used by hierarchy limits
const auto dist = astarheuristic_forward_.GetDistance(tile->get_node_ll(opp_dir_edge->endnode()));
edgelabels_reverse_.emplace_back(kInvalidLabel, opp_edge_id, edgeid, opp_dir_edge, cost, sortcost,
dist, mode_, c, !opp_dir_edge->not_thru(),
!(costing_->IsClosed(directededge, tile)),
Expand Down Expand Up @@ -1138,6 +1149,14 @@ std::vector<std::vector<PathInfo>> BidirectionalAStar::FormPath(GraphReader& gra
return paths;
}

void BidirectionalAStar::ModifyHierarchyLimits() {
// Distance threshold optimized for unidirectional search. For bidirectional case
// they can be lowered.
// Decrease distance thresholds only for arterial roads for now
hierarchy_limits_forward_[1].expansion_within_dist /= 5.f;
hierarchy_limits_reverse_[1].expansion_within_dist /= 5.f;
Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

current default hierarchy limit for arterial roads is 100km; it's very costly for performance. This code decreases it to 20km making performance drop more or less reasonable

Copy link
Member

@kevinkreiser kevinkreiser Jun 17, 2021 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

i guess we have to do a big round of RAD to see what kind of changes we get though. I could imagine many routes will change because of this especially in rural areas where now you have to find an upward transition within 20km.

with respect to the performance difference how many routes are run with a retry and relaxed limits vs master? i wonder if we would have more retries with this change

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

i guess we have to do a big round of RAD to see what kind of changes we get though. I could imagine many routes will change because of this especially in rural areas where now you have to find an upward transition within 20km.

agree about RAD. I'm working on it right now

with respect to the performance difference how many routes are run with a retry and relaxed limits vs master? i wonder if we would have more retries with this change

interesting note. I will check it

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@kevinkreiser about retries: it's approximately the same: 296 (master) vs 292 (branch)

}

bool IsBridgingEdgeRestricted(GraphReader& graphreader,
std::vector<sif::BDEdgeLabel>& edge_labels_fwd,
std::vector<sif::BDEdgeLabel>& edge_labels_rev,
Expand Down
2 changes: 2 additions & 0 deletions valhalla/sif/edgelabel.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -187,6 +187,8 @@ class EdgeLabel {

/**
* Get the distance to the destination.
* In case of bidirectional search it may represent the distance to the start point:
* origin for the forward search and destination for the reverse search.
* @return Returns the distance in meters.
*/
float distance() const {
Expand Down
5 changes: 3 additions & 2 deletions valhalla/sif/hierarchylimits.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -18,8 +18,9 @@ constexpr float kMaxDistance = std::numeric_limits<float>::max();
// destination.
constexpr uint32_t kDefaultMaxUpTransitions[] = {0, 400, 100, 0, 0, 0, 0, 0};

// Default distances within which expansion is always allowed
// (per level). Used only for A*.
// Default distances within which expansion is always allowed (per level). It's optimized
// for unidirectional search and can be modified by the path algorithm in case of
// bidirectional search.
constexpr float kDefaultExpansionWithinDist[] = {kMaxDistance, 100000.0f, 5000.0f, 0.0f,
0.0f, 0.0f, 0.0f, 0.0f};
} // namespace
Expand Down
5 changes: 5 additions & 0 deletions valhalla/thor/bidirectional_astar.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -240,6 +240,11 @@ class BidirectionalAStar : public PathAlgorithm {
const valhalla::Location& dest,
const baldr::TimeInfo& time_info,
const bool invariant);

/**
* Modify default (optimized for unidirectional search) hierarchy limits.
*/
void ModifyHierarchyLimits();
};

// This function checks if the path formed by the two expanding trees
Expand Down