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

* Use 'distance' threshold in hierarchy limits for bidir-astar * Update changelog * Avoid unnecessary distance calculation if hierarchy limits are disabled
valhalla · Jun 25, 2021 · 7a9c864 · 7a9c864
1 parent 4832256
commit 7a9c864
Show file tree

Hide file tree

Showing 7 changed files with 52 additions and 8 deletions.
diff --git a/CHANGELOG.md b/CHANGELOG.md
@@ -12,6 +12,7 @@
    * FIXED: Missing fork maneuver [#3134](https://github.com/valhalla/valhalla/pull/3134)
    * FIXED: Update turn channel logic to call out specific turn at the end of the turn channel if needed [#3140](https://github.com/valhalla/valhalla/pull/3140)
    * FIXED: Fixed cost thresholds for TimeDistanceMatrix. [#3131](https://github.com/valhalla/valhalla/pull/3131)
+   * FIXED: Use distance threshold in hierarchy limits for bidirectional astar to expand more important lower level roads [#3156](https://github.com/valhalla/valhalla/pull/3156)
 
 * **Enhancement**
    * CHANGED: Refactor base costing options parsing to handle more common stuff in a one place [#3125](https://github.com/valhalla/valhalla/pull/3125)

diff --git a/run_route_scripts/run_with_server.py b/run_route_scripts/run_with_server.py
@@ -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=[])
   parsed_args = parser.parse_args()
 
   # make the output directory

diff --git a/src/sif/hierarchylimits.cc b/src/sif/hierarchylimits.cc
@@ -3,5 +3,5 @@
 using namespace valhalla::sif;
 
 bool HierarchyLimits::StopExpanding(const float dist) const {
-  return (dist > expansion_within_dist && up_transition_count > max_up_transitions);
+  return (up_transition_count > max_up_transitions && dist > expansion_within_dist);
 }
diff --git a/src/thor/bidirectional_astar.cc b/src/thor/bidirectional_astar.cc
@@ -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;
@@ -285,6 +285,11 @@ inline bool BidirectionalAStar::ExpandInner(baldr::GraphReader& graphreader,
   uint32_t idx = 0;
   if (FORWARD) {
     idx = edgelabels_forward_.size();
+    if (hierarchy_limits_forward_[meta.edge_id.level()].max_up_transitions != kUnlimitedTransitions) {
+      // Override distance to the destination with a distance from the origin.
+      // It will be used by hierarchy limits
+      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)),
@@ -294,6 +299,11 @@ inline bool BidirectionalAStar::ExpandInner(baldr::GraphReader& graphreader,
     adjacencylist_forward_.add(idx);
   } else {
     idx = edgelabels_reverse_.size();
+    if (hierarchy_limits_reverse_[meta.edge_id.level()].max_up_transitions != kUnlimitedTransitions) {
+      // Override distance to the origin with a distance from the destination.
+      // It will be used by hierarchy limits
+      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)),
@@ -390,7 +400,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;
       }
@@ -480,6 +491,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
@@ -620,7 +634,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;
       }
 
@@ -639,7 +653,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;
       }
 
@@ -853,6 +867,11 @@ void BidirectionalAStar::SetOrigin(GraphReader& graphreader,
     // to invalid to indicate the origin of the path.
     uint32_t idx = edgelabels_forward_.size();
     edgestatus_forward_.Set(edgeid, EdgeSet::kTemporary, idx, tile);
+    if (hierarchy_limits_forward_[edgeid.level()].max_up_transitions != kUnlimitedTransitions) {
+      // Override distance to the destination with a distance from the origin.
+      // It will be used by hierarchy limits
+      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),
@@ -940,6 +959,11 @@ void BidirectionalAStar::SetDestination(GraphReader& graphreader,
     // edge (edgeid) is set.
     uint32_t idx = edgelabels_reverse_.size();
     edgestatus_reverse_.Set(opp_edge_id, EdgeSet::kTemporary, idx, opp_tile);
+    if (hierarchy_limits_reverse_[opp_edge_id.level()].max_up_transitions != kUnlimitedTransitions) {
+      // Override distance to the origin with a distance from the destination.
+      // It will be used by hierarchy limits
+      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)),
@@ -1138,6 +1162,17 @@ 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
+  if (hierarchy_limits_forward_[1].max_up_transitions != kUnlimitedTransitions)
+    hierarchy_limits_forward_[1].expansion_within_dist /= 5.f;
+
+  if (hierarchy_limits_reverse_[1].max_up_transitions != kUnlimitedTransitions)
+    hierarchy_limits_reverse_[1].expansion_within_dist /= 5.f;
+}
+
 bool IsBridgingEdgeRestricted(GraphReader& graphreader,
                               std::vector<sif::BDEdgeLabel>& edge_labels_fwd,
                               std::vector<sif::BDEdgeLabel>& edge_labels_rev,

diff --git a/valhalla/sif/edgelabel.h b/valhalla/sif/edgelabel.h
@@ -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 {

diff --git a/valhalla/sif/hierarchylimits.h b/valhalla/sif/hierarchylimits.h
@@ -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

diff --git a/valhalla/thor/bidirectional_astar.h b/valhalla/thor/bidirectional_astar.h
@@ -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