Multi-metric prototype

[wangyoucao577]

Background

Based on discussion in #372, we might possible to add one more metric in OSRM, which might be used to store EV consumption in the future. Project-OSRM#3116 (comment) describes more idea that it can be used for.
Originally multi-metric means multiple metrics per profile(see Project-OSRM#4007), e.g., support both fastest and shortest queries in a single OSRM instance. But what we want to dicscuss here is more like another dimension of weight, something like duration. When we query a route or a table, it can be outputed along with weight and duration.

Goal

• Try to add one more end-to-end metric in OSRM(name it energy_consumption maybe), which can be queried via table service interface at the first step.
• A sample table response may looks like this

{
"code": "Ok",
"sources": [...],
"destinations": [...],
"durations": [...],
"distances": [...],
"energy_consumptions": [...]
}

Implementation ideas

• duration can be considered as the second metric compare with weight. What we want to add is the third one.
• The calculation in this prototype could be the same with duration so that we're able to verify correctness.
• We focus on MLD on this idea, don't want to touch CH for now.
• To support real energy consumption calculation, we also need some extra attributes(e.g., evalution) and extra data(e.g., speed table). However, this prototype is dedicated to estimate viability and effort in OSRM to have this idea, so we won't touch these extra parts.

Acceptance critiria/measurement

• same processing with duration that results same value with duration
• query performance should not be affected
• processing(osrm-extract, osrm-partition, osrm-customize) performance should not be significantly affected(might be affected a little? )
• how many files need to be modified?
• how many size increased on files?
• how many memory increased of osrm-routed?

Let's mainly discuss this topic here to prepare the prototype implementation.

[wangyoucao577]

New metric(energy consumption) calculation related changes

Per How OSRM Calculate Weight and Duration, there's a few places related on calculation of duration, most of them are in Lua.

Lua/C++ binding changes

• Add energy_consumption that can be set in process_way, similar with result.duration
  

  osrm-backend/include/extractor/extraction_way.hpp

  Line 105 in c9e9cc9

  double duration;

  
  

  osrm-backend/src/extractor/scripting_environment_lua.cpp

  Lines 341 to 342 in c9e9cc9

  	"duration",
  	&ExtractionWay::duration,

• Add energy_consumption that can be set in process_turn, similar with result.duration
  

  osrm-backend/include/extractor/extraction_turn.hpp

  Line 131 in c9e9cc9

  double duration;

  
  

  osrm-backend/src/extractor/scripting_environment_lua.cpp

  Lines 616 to 617 in c9e9cc9

  	"duration",
  	&ExtractionTurn::duration,

Lua changes

• Set result.energy_consumption = result.duration at the end of process_way
  

  osrm-backend/profiles/car.lua

  Line 453 in c9e9cc9

  end

• Set result.energy_consumption = result.duration at the end of process_turn
  

  osrm-backend/profiles/car.lua

  Line 491 in c9e9cc9

  end

C++ changes

• Calculate for node based edge
  Refer to Construct and Store Weight/Duration for NodeBasedEdge.

osrm-backend/src/extractor/extractor_callbacks.cpp

Lines 126 to 127 in a1e5061

	InternalExtractorEdge::DurationData forward_duration_data;
	InternalExtractorEdge::DurationData backward_duration_data;

osrm-backend/src/extractor/extractor_callbacks.cpp

Lines 432 to 433 in a1e5061

	external_memory.all_edges_list.push_back(InternalExtractorEdge(
	std::move(edge), forward_weight_data, forward_duration_data, {}));

osrm-backend/src/extractor/extraction_containers.cpp

Lines 396 to 399 in a1e5061

	auto &edge = edge_iterator->result;
	edge.weight = std::max<EdgeWeight>(1, std::round(segment.weight * weight_multiplier));
	edge.duration = std::max<EdgeWeight>(1, std::round(segment.duration * 10.));
	edge.distance = accurate_distance;

osrm-backend/src/extractor/graph_compressor.cpp

Line 253 in e86d937

node_duration_penalty = extraction_turn.duration * 10;

osrm-backend/src/extractor/graph_compressor.cpp

Lines 290 to 292 in e86d937

	// add duration of e2's to e1
	graph.GetEdgeData(forward_e1).duration += forward_duration2;
	graph.GetEdgeData(reverse_e1).duration += reverse_duration2;

osrm-backend/src/extractor/graph_compressor.cpp

Lines 298 to 306 in e86d937

	if (node_weight_penalty != INVALID_EDGE_WEIGHT &&
	node_duration_penalty != MAXIMAL_EDGE_DURATION)
	{
	graph.GetEdgeData(forward_e1).weight += node_weight_penalty;
	graph.GetEdgeData(reverse_e1).weight += node_weight_penalty;
	graph.GetEdgeData(forward_e1).duration += node_duration_penalty;
	graph.GetEdgeData(reverse_e1).duration += node_duration_penalty;
	// Note: no penalties for distances
	}

• When build edge-expanded edges
  Refer to Process Turn While Build GraphEdge.

osrm-backend/src/extractor/edge_based_graph_factory.cpp

Lines 650 to 672 in e86d937

	// turn penalties are limited to [-2^15, 2^15) which roughly translates to 54 minutes
	// and fits signed 16bit deci-seconds
	auto weight_penalty =
	boost::numeric_cast<TurnPenalty>(extracted_turn.weight * weight_multiplier);
	auto duration_penalty = boost::numeric_cast<TurnPenalty>(extracted_turn.duration * 10.);
	BOOST_ASSERT(SPECIAL_NODEID != nbe_to_ebn_mapping[node_based_edge_from]);
	BOOST_ASSERT(SPECIAL_NODEID != nbe_to_ebn_mapping[node_based_edge_to]);
	// auto turn_id = m_edge_based_edge_list.size();
	auto weight = boost::numeric_cast<EdgeWeight>(edge_data1.weight + weight_penalty);
	auto duration = boost::numeric_cast<EdgeWeight>(edge_data1.duration + duration_penalty);
	auto distance = boost::numeric_cast<EdgeDistance>(edge_data1.distance);
	EdgeBasedEdge edge_based_edge = {edge_based_node_from,
	edge_based_node_to,
	SPECIAL_NODEID, // This will be updated once the main
	// loop completes!
	weight,
	duration,
	distance,
	true,
	false};

[wangyoucao577]

Toolchain files changes & affection

After go through most of osrm-extract produced files, there're some files may be affected:

• .osrm
  One more EdgeEnergyConsumption need to be stored in /extractor/edges

• .osrm.geometry
  Two more forward_energy_consumptions and backward_energy_consumptions need to be added, similar with /common/segment_data/forward_durations/* and /common/segment_data/backward_durations/*

• .osrm.enw
  One more edge_based_node_energy_consumptions need to be added, similar with /extractor/edge_based_node_durations.

• .osrm.ebg
  One more EdgeEnergyConsumption need to be stored in /common/edge_based_edge_list

• .osrm.turn_energy_consumption_penalties
  Add this new file, similar with .osrm.turn_duration_penalties

osrm-partition produced files(.osrm.cells, .osrm.partition) won't be affected.

osrm-customize produced files:

• .osrm.cell_metrics
  One more /mld/metrics/routability/exclude/0/energy_consumptions need to be stored in /mld/metrics/routability/*, similar with /mld/metrics/routability/exclude/0/durations.

• .osrm.mldgr
  One more /mld/multilevelgraph/energy_consumptions need to be stored in /mld/multilevelgraph/, similar with /mld/multilevelgraph/node_durations.

In order to change these files, all read/write functions for these files need to be changed. Their corresponding data structures need to be changed also since we need to add more data in.

Refer to https://github.com/Telenav/open-source-spec/blob/master/osrm/doc/osrm-profile.md#na-mld, above affected files size is about 28.6 GB in 43 GB. Consider that the new metric increases 1/3 of total metric size, the increased file size might be 28.6 * 1/3 = 8.58 GB, and the final sizes is about 43 + 8.58 = 51.15 GB.
Memory increasing should be almost the same.

[wangyoucao577]

A known issue is that OSRM uses 100ms as unit to store weight/duration by integer type, see more in Project-OSRM#5400.
Ideally float type will be better than integer to store metrics. However, we may go with integer first to see whether it works.

[wangyoucao577]

Customization changes

• update metric

osrm-backend/src/updater/updater.cpp

Lines 258 to 260 in c9e9cc9

	auto new_duration = convertToDuration(value->speed, segment_length);
	auto new_weight =
	convertToWeight(fwd_weights_range[segment_offset], *value, segment_length);

osrm-backend/src/updater/updater.cpp

Lines 301 to 303 in c9e9cc9

	auto new_duration = convertToDuration(value->speed, segment_length);
	auto new_weight =
	convertToWeight(rev_weights_range[segment_offset], *value, segment_length);

osrm-backend/src/updater/updater.cpp

Lines 470 to 484 in c9e9cc9

	// original turn weight/duration values
	auto turn_weight_penalty = turn_weight_penalties[edge_index];
	auto turn_duration_penalty = turn_duration_penalties[edge_index];
	if (auto value = turn_penalty_lookup(osm_turn))
	{
	turn_duration_penalty =
	boost::numeric_cast<TurnPenalty>(std::round(value->duration * 10.));
	turn_weight_penalty = boost::numeric_cast<TurnPenalty>(std::round(
	std::isfinite(value->weight) ? value->weight * weight_multiplier
	: turn_duration_penalty * weight_multiplier / 10.));
	turn_duration_penalties[edge_index] = turn_duration_penalty;
	turn_weight_penalties[edge_index] = turn_weight_penalty;
	updated_turns.push_back(edge_index);

osrm-backend/src/updater/updater.cpp

Lines 607 to 614 in c9e9cc9

	[&] {
	extractor::files::readTurnWeightPenalty(
	config.GetPath(".osrm.turn_weight_penalties"), turn_weight_penalties);
	},
	[&] {
	extractor::files::readTurnDurationPenalty(
	config.GetPath(".osrm.turn_duration_penalties"), turn_duration_penalties);
	},

osrm-backend/src/updater/updater.cpp

Lines 703 to 707 in c9e9cc9

	using WeightAndDuration = std::tuple<EdgeWeight, EdgeWeight>;
	const auto compute_new_weight_and_duration =
	[&](const GeometryID geometry_id) -> WeightAndDuration {
	EdgeWeight new_weight = 0;
	EdgeWeight new_duration = 0;

osrm-backend/src/updater/updater.cpp

Lines 771 to 777 in c9e9cc9

	// Update the node-weight cache. This is the weight of the edge-based-node
	// only, it doesn't include the turn. We may visit the same node multiple times,
	// but we should always assign the same value here.
	BOOST_ASSERT(edge.source < node_weights.size());
	node_weights[edge.source] =
	node_weights[edge.source] & 0x80000000 ? new_weight | 0x80000000 : new_weight;
	node_durations[edge.source] = new_duration;

osrm-backend/src/updater/updater.cpp

Lines 788 to 790 in c9e9cc9

	// Get the turn penalty and update to the new value if required
	auto turn_weight_penalty = turn_weight_penalties[edge.data.turn_id];
	auto turn_duration_penalty = turn_duration_penalties[edge.data.turn_id];

• customize

osrm-backend/include/customizer/cell_customizer.hpp

Lines 71 to 84 in c9e9cc9

	const EdgeWeight weight = heap.GetKey(node);
	const EdgeDuration duration = heap.GetData(node).duration;
	const EdgeDistance distance = heap.GetData(node).distance;
	RelaxNode(graph,
	cells,
	allowed_nodes,
	metric,
	heap,
	level,
	node,
	weight,
	duration,
	distance);

osrm-backend/include/customizer/cell_customizer.hpp

Lines 89 to 109 in c9e9cc9

	// fill a map of destination nodes to placeholder pointers
	auto weights = cell.GetOutWeight(source);
	auto durations = cell.GetOutDuration(source);
	auto distances = cell.GetOutDistance(source);
	for (auto &destination : destinations)
	{
	BOOST_ASSERT(!weights.empty());
	BOOST_ASSERT(!durations.empty());
	BOOST_ASSERT(!distances.empty());
	const bool inserted = heap.WasInserted(destination);
	weights.front() = inserted ? heap.GetKey(destination) : INVALID_EDGE_WEIGHT;
	durations.front() =
	inserted ? heap.GetData(destination).duration : MAXIMAL_EDGE_DURATION;
	distances.front() =
	inserted ? heap.GetData(destination).distance : INVALID_EDGE_DISTANCE;
	weights.advance_begin(1);
	durations.advance_begin(1);
	distances.advance_begin(1);
	}

osrm-backend/include/customizer/cell_customizer.hpp

Lines 173 to 175 in c9e9cc9

	auto subcell_destination = subcell.GetDestinationNodes().begin();
	auto subcell_duration = subcell.GetOutDuration(node).begin();
	auto subcell_distance = subcell.GetOutDistance(node).begin();

osrm-backend/include/customizer/cell_customizer.hpp

Lines 224 to 226 in c9e9cc9

	const EdgeWeight to_weight = weight + data.weight;
	const EdgeDuration to_duration = duration + data.duration;
	const EdgeDistance to_distance = distance + data.distance;

[wangyoucao577]

Query(table) changes

• query with energy_consumption also

osrm-backend/src/engine/routing_algorithms/many_to_many_mld.cpp

Lines 211 to 213 in c9e9cc9

	std::vector<EdgeWeight> weights(phantom_indices.size(), INVALID_EDGE_WEIGHT);
	std::vector<EdgeDuration> durations(phantom_indices.size(), MAXIMAL_EDGE_DURATION);
	std::vector<EdgeDistance> distances_table(calculate_distance ? phantom_indices.size() : 0,

osrm-backend/src/engine/routing_algorithms/many_to_many_mld.cpp

Lines 217 to 219 in c9e9cc9

	// Collect destination (source) nodes into a map
	std::unordered_multimap<NodeID, std::tuple<std::size_t, EdgeWeight, EdgeDuration, EdgeDistance>>
	target_nodes_index;

osrm-backend/src/engine/routing_algorithms/many_to_many_mld.cpp

Lines 280 to 300 in c9e9cc9

	if (path_weight >= 0)
	{
	const auto path_duration = duration + target_duration;
	const auto path_distance = distance + target_distance;
	EdgeDistance nulldistance = 0;
	auto &current_distance =
	distances_table.empty() ? nulldistance : distances_table[index];
	if (std::tie(path_weight, path_duration, path_distance) <
	std::tie(weights[index], durations[index], current_distance))
	{
	weights[index] = path_weight;
	durations[index] = path_duration;
	current_distance = path_distance;
	middle_nodes_table[index] = node;
	}
	// Remove node from destinations list
	it = target_nodes_index.erase(it);
	}

osrm-backend/src/engine/routing_algorithms/many_to_many_mld.cpp

Lines 118 to 152 in c9e9cc9

	if (DIRECTION == FORWARD_DIRECTION)
	{ // Shortcuts in forward direction
	auto destination = cell.GetDestinationNodes().begin();
	auto shortcut_durations = cell.GetOutDuration(node);
	auto shortcut_distances = cell.GetOutDistance(node);
	for (auto shortcut_weight : cell.GetOutWeight(node))
	{
	BOOST_ASSERT(destination != cell.GetDestinationNodes().end());
	BOOST_ASSERT(!shortcut_durations.empty());
	BOOST_ASSERT(!shortcut_distances.empty());
	const NodeID to = *destination;
	if (shortcut_weight != INVALID_EDGE_WEIGHT && node != to)
	{
	const auto to_weight = weight + shortcut_weight;
	const auto to_duration = duration + shortcut_durations.front();
	const auto to_distance = distance + shortcut_distances.front();
	if (!query_heap.WasInserted(to))
	{
	query_heap.Insert(to, to_weight, {node, true, to_duration, to_distance});
	}
	else if (std::tie(to_weight, to_duration, to_distance, node) <
	std::tie(query_heap.GetKey(to),
	query_heap.GetData(to).duration,
	query_heap.GetData(to).distance,
	query_heap.GetData(to).parent))
	{
	query_heap.GetData(to) = {node, true, to_duration, to_distance};
	query_heap.DecreaseKey(to, to_weight);
	}
	}
	++destination;
	shortcut_durations.advance_begin(1);
	shortcut_distances.advance_begin(1);
	}

osrm-backend/src/engine/routing_algorithms/many_to_many_mld.cpp

Lines 412 to 414 in c9e9cc9

	const auto source_weight = query_heap.GetKey(node);
	const auto source_duration = query_heap.GetData(node).duration;
	const auto source_distance = query_heap.GetData(node).distance;

• make response
  Also need to add one more value energy_consumptions of parameter annotations

osrm-backend/include/engine/api/table_api.hpp

Lines 211 to 215 in c9e9cc9

	if (parameters.annotations & TableParameters::AnnotationsType::Duration)
	{
	response.values["durations"] =
	MakeDurationTable(tables.first, number_of_sources, number_of_destinations);
	}

[wangyoucao577]

Things have not been considered yet

• CH compatible
• flatbuffer support when make response
• services other than table(e.g., route, match, etc)
• the 100ms unit issue Multi-metric prototype #391 (comment)
• tests(unit test, cucumber feature test)
• with traffic update affection:
  • able to update energy consumption
  • osrm-datastore?
  • memory acceptable?
• how to calculate real energy consumption

[CodeBear801]

Great information, I feel we have a solid start @wangyoucao577

Here are some points from me before the discussion:

• What's the possibility of having multiple nodes support for EV based on OSRM?

  • Implement new lua file, use EV formula to replace existing cost formula
  • One node for one cost model

• Multiple Metric support for multiple cost model or multiple EnergyConsumption

  • the number of cost model is configurable, and their would be multiple arrays in each of file be modified

[wangyoucao577]

• What's the possibility of having multiple nodes support for EV based on OSRM?

  • Implement new lua file, use EV formula to replace existing cost formula
  • One node for one cost model

I think it's possible if the EV formula is selective(not full dynamic). But we need to do a little more rather than modify lua only:

• extract and store evalution
• process accelerate/decelerate similar when process turn (build edge-expanded edges)

• Multiple Metric support for multiple cost model or multiple EnergyConsumption

  • the number of cost model is configurable, and their would be multiple arrays in each of file be modified

Yes, we should consider it. Despite we may not use it in real case(one more metric will result 10GB more file/memory and slower re-customize) in short-term, we should keep the possibility.

[wangyoucao577]

Some notes after discussed with @CodeBear801 offline:

• We may need to calculate different energy consumption based on many different curves. OSRM is not good for it, and it's not a long-term goal of the multi-metric.
• The most important benefit of multi-metrc is that it's able to return the third demension energy_consumption with duration/distance together extermly fast. However, we may split it to several phases:
  • phase 1: set up a simple service that calculate table by OSRM and calculate energy_consumption by another service, then combine them together to provide the functionality.
  • phase 2: improve the 3 demension table query performance. multi-metric may be one of the possible solutions. Improve the performance of energy_consumption calculation may works too. The multi-metric may not the first way to go since it requires too many changes in OSRM internal.

For workload estimation of this prototype:

• prototype only(same calculation with duration): 4~6 weeks
• production level: half year at least

@CodeBear801 Please feel free to append if anything missed, and propose your idea of the workload estimation, as well as risk points if any. :)