Re-costing A Path (#2425)

* sketch for the recosting * still fleshing out the interface * first pass of recosting * check more fields of the edge label and run all routes * lint * modify the way we set options on the request in gurka * typos * dont need reference param for tile * make recosting robust to multiple failure scenarios * disable logging again * add testing for request parsing * refactor storing cost information in pathinfo and tripleg.node proto so taht we have all the costing information available * stub out recosting * a horrid refactor of costing.. * add integration testing for recosting * all the costing info is added to all the nodes properly. just need json now * add serialization of recosting to json and compile all the things * lint * maneuver serialization was on wrong sub object * oops a couple more build errors * rename intersection duration to turn_duration, add turn_weight, duration and weight (for the edge leaving the intersection) * fix a long standing bug in bidirectional_astar wrt adding additional turn cost in the reverse edge lables * dont need this, its done * Rename sif/util to sif/recost per feedback. * use correct relative path for timezone info * lint * add json verification tests * rename options to costing_options and re-enable arrive by recost tests * add a failing test when historical traffic is present for recosting * use constrained time of day for non-time dependent costing (#2514) * use constrained time of day by default for any non-time dependent speed look up * didnt need this change * i didnt touch this code but somehow its linted differently.. * routes bench adapt to costing refactor * fix two small complaints Co-authored-by: Daniel Patterson <danpat@danpat.net>
valhalla · Aug 7, 2020 · de546d7 · de546d7
1 parent 2f490ca
commit de546d7
Show file tree

Hide file tree

Showing 136 changed files with 1,996 additions and 1,042 deletions.
diff --git a/bench/meili/mapmatch.cc b/bench/meili/mapmatch.cc
@@ -46,12 +46,13 @@ class OfflineMapmatchFixture : public benchmark::Fixture {
   void InitEngineConfig() {
     rapidjson::read_json(VALHALLA_SOURCE_DIR "bench/meili/config.json", config_);
     const rapidjson::Document doc;
-    ParseAutoCostOptions(doc, "/costing_options/auto", options_.add_costing_options());
+    valhalla::sif::ParseCostingOptions(doc, "/costing_options", options_);
+    options_.set_costing(valhalla::Costing::auto_);
   }
 
   void InitMapMatcher() {
     matcher_factory_ = std::make_shared<MapMatcherFactory>(config_);
-    mapmatcher_.reset(matcher_factory_->Create(valhalla::Costing::auto_, options_));
+    mapmatcher_.reset(matcher_factory_->Create(options_));
   }
 
 protected:

diff --git a/bench/thor/costmatrix.cc b/bench/thor/costmatrix.cc
@@ -16,12 +16,6 @@ using namespace valhalla;
 
 namespace {
 
-void create_costing_options(Options& options) {
-  const rapidjson::Document doc;
-  sif::ParseAutoCostOptions(doc, "/costing_options/auto", options.add_costing_options());
-  options.add_costing_options();
-}
-
 boost::property_tree::ptree json_to_pt(const std::string& json) {
   std::stringstream ss;
   ss << json;
@@ -87,10 +81,14 @@ static void BM_UtrechtCostMatrix(benchmark::State& state) {
   }
 
   Options options;
-  create_costing_options(options);
-  auto costs = sif::CreateAutoCost(Costing::auto_, options);
-
-  const auto projections = loki::Search(locations, reader, costs);
+  options.set_costing(Costing::auto_);
+  rapidjson::Document doc;
+  sif::ParseCostingOptions(doc, "/costing_options", options);
+  sif::TravelMode mode;
+  auto costs = sif::CostFactory().CreateModeCosting(options, mode);
+  auto cost = costs[static_cast<size_t>(mode)];
+
+  const auto projections = loki::Search(locations, reader, cost);
   if (projections.size() == 0) {
     throw std::runtime_error("Found no matching locations");
   }
@@ -106,8 +104,7 @@ static void BM_UtrechtCostMatrix(benchmark::State& state) {
 
   for (auto _ : state) {
     thor::CostMatrix matrix;
-    auto result =
-        matrix.SourceToTarget(sources, sources, reader, &costs, sif::TravelMode::kDrive, 100000.);
+    auto result = matrix.SourceToTarget(sources, sources, reader, costs, mode, 100000.);
     result_size += result.size();
   }
   state.counters["Routes"] = benchmark::Counter(size, benchmark::Counter::kIsIterationInvariantRate);

diff --git a/bench/thor/routes.cc b/bench/thor/routes.cc
@@ -18,9 +18,9 @@ using namespace valhalla;
 namespace {
 
 void create_costing_options(Options& options) {
-  const rapidjson::Document doc;
-  sif::ParseAutoCostOptions(doc, "/costing_options/auto", options.add_costing_options());
-  options.add_costing_options();
+  options.set_costing(Costing::auto_);
+  rapidjson::Document doc;
+  sif::ParseCostingOptions(doc, "/costing_options", options);
 }
 
 boost::property_tree::ptree json_to_pt(const std::string& json) {
@@ -124,7 +124,9 @@ static void BM_UtrechtBidirectionalAstar(benchmark::State& state) {
 
   Options options;
   create_costing_options(options);
-  auto costs = sif::CreateAutoCost(Costing::auto_, options);
+  sif::TravelMode mode;
+  auto costs = sif::CostFactory().CreateModeCosting(options, mode);
+  auto cost = costs[static_cast<size_t>(mode)];
 
   // A few locations around Utrecht. Origins and destinations are constructed
   // from these for the queries
@@ -138,7 +140,7 @@ static void BM_UtrechtBidirectionalAstar(benchmark::State& state) {
   locations.emplace_back(midgard::PointLL{5.110077, 52.062043});
   locations.emplace_back(midgard::PointLL{5.025595, 52.067372});
 
-  const auto projections = loki::Search(locations, *clean_reader, costs);
+  const auto projections = loki::Search(locations, *clean_reader, cost);
   if (projections.size() == 0) {
     throw std::runtime_error("Found no matching locations");
   }
@@ -174,7 +176,7 @@ static void BM_UtrechtBidirectionalAstar(benchmark::State& state) {
     thor::BidirectionalAStar astar;
     for (int i = 0; i < origins.size(); ++i) {
       // LOG_WARN("Running index "+std::to_string(i));
-      auto result = astar.GetBestPath(origins[i], destinations[i], *clean_reader, &costs,
+      auto result = astar.GetBestPath(origins[i], destinations[i], *clean_reader, costs,
                                       sif::TravelMode::kDrive);
       route_size += 1;
     }
@@ -253,7 +255,9 @@ static void BM_Sif_Allowed(benchmark::State& state) {
 
   Options options;
   create_costing_options(options);
-  auto costs = sif::CreateAutoCost(Costing::auto_, options);
+  sif::TravelMode mode;
+  auto costs = sif::CostFactory().CreateModeCosting(options, mode);
+  auto cost = costs[static_cast<size_t>(mode)];
 
   auto tile = clean_reader->GetGraphTile(baldr::GraphId(tgt_edge_id));
   if (tile == nullptr) {
@@ -275,7 +279,7 @@ static void BM_Sif_Allowed(benchmark::State& state) {
   int restriction_idx;
 
   for (auto _ : state) {
-    costs->Allowed(edge, pred, tile, tgt_edge_id, 0, 0, restriction_idx);
+    cost->Allowed(edge, pred, tile, tgt_edge_id, 0, 0, restriction_idx);
   }
 }
 

diff --git a/proto/options.proto b/proto/options.proto
@@ -48,6 +48,11 @@ enum Costing {
   none_ = 13;
 }
 
+message AvoidEdge {
+  optional uint64 id = 1;
+  optional float percent_along = 2;
+}
+
 message CostingOptions {
   optional float maneuver_penalty = 1;
   optional float destination_only_penalty = 2;
@@ -106,11 +111,11 @@ message CostingOptions {
   optional uint32 flow_mask = 55;
   optional float rail_ferry_cost = 56;
   optional float use_rail_ferry = 57;
-}
 
-message AvoidEdge {
-  optional uint64 id = 1;
-  optional float percent_along = 2;
+  // these are not specified directly by the user but they get filled in as the request is parsed and fulfilled
+  optional Costing costing = 90;
+  optional string name = 91;
+  repeated AvoidEdge avoid_edges = 92;                       // Avoid edges for any costing - derived from avoid_locations
 }
 
 message Options {
@@ -179,7 +184,7 @@ message Options {
   optional float turn_penalty_factor = 32;                                // The turn penalty factor associated with the supplied trace points
   optional FilterAction filter_action = 33;                               // The trace filter action - either exclude or include
   repeated string filter_attributes = 34;                                 // The filter list for trace attributes
-  repeated AvoidEdge avoid_edges = 35;                                    // Avoid edges for any costing - derived from avoid_locations
+
   optional float breakage_distance = 36;                                  // Map-matching breaking distance (distance between GPS trace points)
   optional bool use_timestamps = 37 [default = false];                    // Use timestamps to compute elapsed time for trace_route and trace_attributes
   optional ShapeFormat shape_format = 38 [default = polyline6];           // Shape format (defaults to polyline6 encoding)
@@ -190,4 +195,5 @@ message Options {
   optional uint32 height_precision = 43 [default = 0];                    // Number of digits precision for heights returned
   optional bool roundabout_exits = 44 [default = true];                   // Whether to announce roundabout exit maneuvers
   optional bool linear_references = 45;                                   // Include linear references for graph edges returned in certain responses.
+  repeated CostingOptions recostings = 46;                                // Costing options to use to recost a path after it has been found
 }
diff --git a/proto/trip.proto b/proto/trip.proto
@@ -229,6 +229,16 @@ message TripLeg {
     optional RoadClass road_class = 8;
   }
 
+  message Cost {
+    optional double seconds = 1;
+    optional double cost = 2;
+  }
+
+  message PathCost {
+    optional Cost elapsed_cost = 1;
+    optional Cost transition_cost = 2;
+  }
+
   message Node {
     enum Type {
       kStreetIntersection = 0;      // Regular intersection of 2 roads
@@ -247,15 +257,15 @@ message TripLeg {
 
     optional Edge edge = 1;
     repeated IntersectingEdge intersecting_edge = 2;
-    optional double elapsed_time = 3;        // seconds from start of leg
-    optional uint32 admin_index = 4;         // index into the admin list
-    optional Type type = 5;                  // The type of node
-    optional bool fork = 6;                  // Fork
-    optional TransitPlatformInfo transit_platform_info = 7;
-    optional TransitStationInfo transit_station_info = 8;
-    optional TransitEgressInfo transit_egress_info = 9;
-    optional string time_zone = 10;
-    optional double transition_time = 11;    // seconds spent transitioning through this node
+    optional uint32 admin_index = 3;         // index into the admin list
+    optional Type type = 4;                  // The type of node
+    optional bool fork = 5;                  // Fork
+    optional TransitPlatformInfo transit_platform_info = 6;
+    optional TransitStationInfo transit_station_info = 7;
+    optional TransitEgressInfo transit_egress_info = 10;
+    optional string time_zone = 11;
+    optional PathCost cost = 12;             // how much cost did it take at this node in the path
+    repeated PathCost recosts = 13;          // how much cost did it take at this node in the path for optional recostings
   }
 
   message Admin {

diff --git a/src/loki/reach.cc b/src/loki/reach.cc
@@ -183,7 +183,7 @@ directed_reach Reach::exact(const valhalla::baldr::DirectedEdge* edge,
   locations_.Mutable(0)->mutable_path_edges(0)->mutable_ll()->set_lat(ll.second);
 
   // fake up the costing array
-  std::shared_ptr<sif::DynamicCost> costings[static_cast<int>(sif::TravelMode::kMaxTravelMode)];
+  sif::mode_costing_t costings;
   costings[static_cast<int>(costing->travel_mode())] = costing;
 
   // expand in the forward direction

diff --git a/src/loki/worker.cc b/src/loki/worker.cc
@@ -98,6 +98,7 @@ void loki_worker_t::parse_costing(Api& api, bool allow_none) {
       auto avoid_locations = PathLocation::fromPBF(options.avoid_locations());
       auto results = loki::Search(avoid_locations, *reader, costing);
       std::unordered_set<uint64_t> avoids;
+      auto* co = options.mutable_costing_options(static_cast<uint8_t>(costing->travel_mode()));
       for (const auto& result : results) {
         for (const auto& edge : result.second.edges) {
           auto inserted = avoids.insert(edge.id);
@@ -106,7 +107,7 @@ void loki_worker_t::parse_costing(Api& api, bool allow_none) {
           // Also insert shortcut edge if one includes this edge
           if (inserted.second) {
             // Add edge and percent along to pbf
-            auto* avoid = options.add_avoid_edges();
+            auto* avoid = co->add_avoid_edges();
             avoid->set_id(edge.id);
             avoid->set_percent_along(edge.percent_along);
 
@@ -119,7 +120,7 @@ void loki_worker_t::parse_costing(Api& api, bool allow_none) {
                 avoids.insert(shortcut);
 
                 // Add to pbf (with 0 percent along)
-                auto* avoid = options.add_avoid_edges();
+                auto* avoid = co->add_avoid_edges();
                 avoid->set_id(shortcut);
                 avoid->set_percent_along(0);
               }
@@ -231,9 +232,6 @@ loki_worker_t::loki_worker_t(const boost::property_tree::ptree& config,
   max_best_paths = config.get<unsigned int>("service_limits.trace.max_best_paths");
   max_best_paths_shape = config.get<size_t>("service_limits.trace.max_best_paths_shape");
   max_alternates = config.get<unsigned int>("service_limits.max_alternates");
-
-  // Register standard edge/node costing methods
-  factory.RegisterStandardCostingModels();
 }
 
 void loki_worker_t::cleanup() {

diff --git a/src/meili/map_matcher.cc b/src/meili/map_matcher.cc
@@ -495,7 +495,7 @@ namespace meili {
 MapMatcher::MapMatcher(const boost::property_tree::ptree& config,
                        baldr::GraphReader& graphreader,
                        CandidateQuery& candidatequery,
-                       const sif::cost_ptr_t* mode_costing,
+                       const sif::mode_costing_t& mode_costing,
                        sif::TravelMode travelmode)
     : config_(config), graphreader_(graphreader), candidatequery_(candidatequery),
       mode_costing_(mode_costing), travelmode_(travelmode), interrupt_(nullptr), vs_(), ts_(vs_),

diff --git a/src/meili/map_matcher_factory.cc b/src/meili/map_matcher_factory.cc
@@ -34,17 +34,16 @@ MapMatcherFactory::MapMatcherFactory(const boost::property_tree::ptree& root,
   candidatequery_.reset(
       new CandidateGridQuery(*graphreader_, local_tile_size() / root.get<size_t>("meili.grid.size"),
                              local_tile_size() / root.get<size_t>("meili.grid.size")));
-  cost_factory_.RegisterStandardCostingModels();
 }
 
 MapMatcherFactory::~MapMatcherFactory() {
 }
 
-MapMatcher* MapMatcherFactory::Create(const Costing costing, const Options& options) {
+MapMatcher* MapMatcherFactory::Create(const Options& options) {
   // Merge any customizable options with the config defaults
   const auto& config = MergeConfig(options);
 
-  valhalla::sif::cost_ptr_t cost = cost_factory_.Create(costing, options);
+  valhalla::sif::cost_ptr_t cost = cost_factory_.Create(options);
   valhalla::sif::TravelMode mode = cost->travel_mode();
 
   mode_costing_[static_cast<uint32_t>(mode)] = cost;
@@ -53,10 +52,6 @@ MapMatcher* MapMatcherFactory::Create(const Costing costing, const Options& opti
   return new MapMatcher(config, *graphreader_, *candidatequery_, mode_costing_, mode);
 }
 
-MapMatcher* MapMatcherFactory::Create(const Options& options) {
-  return Create(options.costing(), options);
-}
-
 boost::property_tree::ptree MapMatcherFactory::MergeConfig(const Options& options) {
   // Copy the default child config
   auto config = config_.get_child("default");

diff --git a/src/meili/transition_cost_model.cc b/src/meili/transition_cost_model.cc
@@ -15,7 +15,7 @@ TransitionCostModel::TransitionCostModel(baldr::GraphReader& graphreader,
                                          const IViterbiSearch& vs,
                                          const TopKSearch& ts,
                                          const StateContainer& container,
-                                         const sif::cost_ptr_t* mode_costing,
+                                         const sif::mode_costing_t& mode_costing,
                                          const sif::TravelMode travelmode,
                                          float beta,
                                          float breakage_distance,
@@ -46,7 +46,7 @@ TransitionCostModel::TransitionCostModel(baldr::GraphReader& graphreader,
                                          const IViterbiSearch& vs,
                                          const TopKSearch& ts,
                                          const StateContainer& container,
-                                         const sif::cost_ptr_t* mode_costing,
+                                         const sif::mode_costing_t& mode_costing,
                                          const sif::TravelMode travelmode,
                                          const boost::property_tree::ptree& config)
     : TransitionCostModel(graphreader,

diff --git a/src/odin/directionsbuilder.cc b/src/odin/directionsbuilder.cc
@@ -397,7 +397,8 @@ void DirectionsBuilder::PopulateDirectionsLeg(const Options& options,
 
   // Populate summary
   trip_directions.mutable_summary()->set_length(etp->GetLength(options.units()));
-  trip_directions.mutable_summary()->set_time(etp->node(etp->GetLastNodeIndex()).elapsed_time());
+  trip_directions.mutable_summary()->set_time(
+      etp->node(etp->GetLastNodeIndex()).cost().elapsed_cost().seconds());
   auto mutable_bbox = trip_directions.mutable_summary()->mutable_bbox();
   mutable_bbox->mutable_min_ll()->set_lat(etp->bbox().min_ll().lat());
   mutable_bbox->mutable_min_ll()->set_lng(etp->bbox().min_ll().lng());

diff --git a/src/odin/maneuversbuilder.cc b/src/odin/maneuversbuilder.cc
@@ -1125,8 +1125,8 @@ void ManeuversBuilder::FinalizeManeuver(Maneuver& maneuver, int node_index) {
 
   // Set the time based on the delta of the elapsed time between the begin
   // and end nodes
-  maneuver.set_time(trip_path_->node(maneuver.end_node_index()).elapsed_time() -
-                    trip_path_->node(maneuver.begin_node_index()).elapsed_time());
+  maneuver.set_time(trip_path_->node(maneuver.end_node_index()).cost().elapsed_cost().seconds() -
+                    trip_path_->node(maneuver.begin_node_index()).cost().elapsed_cost().seconds());
 
   // if possible, set the turn degree and relative direction
   if (prev_edge) {

diff --git a/src/sif/CMakeLists.txt b/src/sif/CMakeLists.txt
@@ -10,7 +10,8 @@ set(sources
   pedestriancost.cc
   transitcost.cc
   truckcost.cc
-  dynamiccost.cc)
+  dynamiccost.cc
+  recost.cc)
 
 valhalla_module(NAME sif
   SOURCES ${sources}