osrm-prepare never ends with very low speed

[frodrigo]

I setup a test profile (to compute shortest route). When I set a speed of 0.0001 osrm-prepare never finish the job.

The the profile content:

local find_access_tag = require("profiles/lib/access").find_access_tag

-- Begin of globals
barrier_whitelist = { ["cattle_grid"] = true, ["border_control"] = true, ["checkpoint"] = true, ["toll_booth"] = true, ["sally_port"] = true, ["gate"] = true, ["lift_gate"] = true, ["no"] = true, ["entrance"] = true, ["bollard"] = true }
access_tag_whitelist = { ["yes"] = true, ["motorcar"] = true, ["motor_vehicle"] = true, ["vehicle"] = true, ["permissive"] = true, ["designated"] = true, ["destination"] = true }
access_tag_blacklist = { ["no"] = true, ["agricultural"] = true, ["forestry"] = true, ["emergency"] = true, ["psv"] = true }
access_tag_restricted = { ["destination"] = true, ["delivery"] = true, ["private"] = true, ["pedestrian"] = true }
access_tags = { "motorcar", "motor_vehicle", "vehicle" }
access_tags_hierachy = { "motorcar", "motor_vehicle", "vehicle", "access" }
service_tag_restricted = { ["parking_aisle"] = true }
restriction_exception_tags = { "motorcar", "motor_vehicle", "vehicle" }

local speed = 0.0001

speed_profile = {
  ["motorway"] = speed,
  ["motorway_link"] = speed,
  ["trunk"] = speed,
  ["trunk_link"] = speed,
  ["primary"] = speed,
  ["primary_link"] = speed,
  ["secondary"] = speed,
  ["secondary_link"] = speed,
  ["tertiary"] = speed,
  ["tertiary_link"] = speed,
  ["unclassified"] = speed,
  ["residential"] = speed,
  ["living_street"] = speed,
  ["service"] = speed,
  ["pedestrian"] = speed,
  ["track"] = speed,
--  ["ferry"] = speed,
--  ["movable"] = speed,
--  ["shuttle_train"] = speed,
  ["default"] = speed
}

use_turn_restrictions           = true

local obey_oneway               = true
local ignore_areas              = true

--modes
local mode_normal = 1
local mode_ferry = 2
local mode_movable_bridge = 3

function get_exceptions(vector)
  for i,v in ipairs(restriction_exception_tags) do
    vector:Add(v)
  end
end

function node_function (node, result)
  -- parse access and barrier tags
  local access = find_access_tag(node, access_tags_hierachy)
  if access and access ~= "" then
    if access_tag_blacklist[access] then
      result.barrier = true
    end
  else
    local barrier = node:get_value_by_key("barrier")
    if barrier and "" ~= barrier then
      --  make an exception for rising bollard barriers
      local bollard = node:get_value_by_key("bollard")
      local rising_bollard = bollard and "rising" == bollard

      if not barrier_whitelist[barrier] and not rising_bollard then
        result.barrier = true
      end
    end
  end
end

function way_function (way, result)
  local highway = way:get_value_by_key("highway")
  local route = way:get_value_by_key("route")
  local bridge = way:get_value_by_key("bridge")

  if not ((highway and highway ~= "") or (route and route ~= "") or (bridge and bridge ~= "")) then
    return
  end

  -- we dont route over areas
  local area = way:get_value_by_key("area")
  if ignore_areas and area and "yes" == area then
    return
  end

  -- check if oneway tag is unsupported
  local oneway = way:get_value_by_key("oneway")
  if oneway and "reversible" == oneway then
    return
  end

  local impassable = way:get_value_by_key("impassable")
  if impassable and "yes" == impassable then
    return
  end

  local status = way:get_value_by_key("status")
  if status and "impassable" == status then
    return
  end

  -- Check if we are allowed to access the way
  local access = find_access_tag(way, access_tags_hierachy)
  if access_tag_blacklist[access] then
    return
  end

  -- handling ferries and piers
  local route_speed = speed_profile[route]
  if (route_speed and route_speed > 0) then
    highway = route
    local duration  = way:get_value_by_key("duration")
    if duration and durationIsValid(duration) then
      result.duration = 0
    end
    result.forward_mode = mode_ferry
    result.backward_mode = mode_ferry
    result.forward_speed = route_speed
    result.backward_speed = route_speed
  end

  -- handling movable bridges
  local bridge_speed = speed_profile[bridge]
  local capacity_car = way:get_value_by_key("capacity:car")
  if (bridge_speed and bridge_speed > 0) and (capacity_car ~= 0) then
    highway = bridge
    local duration  = way:get_value_by_key("duration")
    if duration and durationIsValid(duration) then
      result.duration = 0
    end
    result.forward_mode = mode_movable_bridge
    result.backward_mode = mode_movable_bridge
    result.forward_speed = bridge_speed
    result.backward_speed = bridge_speed
  end

  -- leave early of this way is not accessible
  if "" == highway then
    return
  end

  if result.forward_speed == -1 then
    result.forward_speed = speed
    result.backward_speed = speed
  end

  if -1 == result.forward_speed and -1 == result.backward_speed then
    return
  end

  -- parse the remaining tags
  local name = way:get_value_by_key("name")
  local ref = way:get_value_by_key("ref")
  local junction = way:get_value_by_key("junction")
  -- local barrier = way:get_value_by_key("barrier", "")
  -- local cycleway = way:get_value_by_key("cycleway", "")
  local service = way:get_value_by_key("service")

  -- Set the name that will be used for instructions
  local has_ref = ref and "" ~= ref
  local has_name = name and "" ~= name

  if has_name and has_ref then
    result.name = name .. " (" .. ref .. ")"
  elseif has_ref then
    result.name = ref
  elseif has_name then
    result.name = name
--  else
      --    result.name = highway  -- if no name exists, use way type
  end

  if junction and "roundabout" == junction then
    result.roundabout = true
  end

  -- Set access restriction flag if access is allowed under certain restrictions only
  if access ~= "" and access_tag_restricted[access] then
    result.is_access_restricted = true
  end

  -- Set access restriction flag if service is allowed under certain restrictions only
  if service and service ~= "" and service_tag_restricted[service] then
    result.is_access_restricted = true
  end

  -- Set direction according to tags on way
  if obey_oneway then
    if oneway == "-1" then
      result.forward_mode = 0
    elseif oneway == "yes" or
    oneway == "1" or
    oneway == "true" or
    junction == "roundabout" or
    (highway == "motorway_link" and oneway ~="no") or
    (highway == "motorway" and oneway ~= "no") then
      result.backward_mode = 0
    end
  end
end

[frodrigo]

The same profile with a speed=1 do the same result on France extract. Never ends.

[danpat]

Do you have a URL where I can download the same extract you're using? I am doing fixed-speed extract/prepare on a USA datafile with no problems with 4.8.1.

[frodrigo]

As as know speed = 0.0001 fails on Andorra and Luxembourg from geofabrik speed=1 fail on France from geofabrik.

[danpat]

What version of OSRM are you using? Can you copy/paste the output of osrm-extract and osrm-prepare ?

[frodrigo]

OSRM 4.8.1 on Ubuntu 14.04.2

fred@ubuntu-server:~/osrm-backend$ ./build/osrm-extract andorra-latest.osm.pbf 
[info] Input file: andorra-latest.osm.pbf
[info] Profile: profile.lua
[info] Threads: 2
[info] Using script profile.lua
[STXXL-MSG] STXXL v1.3.1 (release)
[STXXL-ERRMSG] Warning: no config file found.
[STXXL-ERRMSG] Using default disk configuration.
[STXXL-MSG] 1 disks are allocated, total space: 1000 MiB
[info] Parsing in progress..
[info] input file generated by Osmium (http://wiki.openstreetmap.org/wiki/Osmium)
[info] timestamp: 2015-09-27T21:23:01Z
[info] Using turn restrictions
[info] Found 3 exceptions to turn restrictions:
[info]   motorcar
[info]   motor_vehicle
[info]   vehicle
[info] Parsing finished after 0.357934 seconds
[info] Raw input contains 123876 nodes, 5747 ways, and 142 relations, and 0 unknown entities
[extractor] Sorting used nodes        ... ok, after 0.010759s
[extractor] Erasing duplicate nodes   ... ok, after 0.005772s
[extractor] Sorting all nodes         ... ok, after 0.021081s
[extractor] Building node id map      ... ok, after 0.015338s
[extractor] setting number of nodes   ... ok
[extractor] Confirming/Writing used nodes     ... ok, after 0.006386s
[info] Processed 70623 nodes
[extractor] Sorting edges by start    ... ok, after 0.03585s
[extractor] Setting start coords      ... ok, after 0.020006s
[extractor] Sorting edges by target   ... ok, after 0.033041s
[extractor] Computing edge weights    ... ok, after 0.055363s
[extractor] Sorting edges by renumbered start ... ok, after 0.026275s
[extractor] Writing used egdes       ... ok, after 0.004764s
[extractor] setting number of edges   ... ok
[info] Processed 71657 edges
[extractor] Sorting used ways         ... ok, after 0.005861s
[extractor] Sorting 17 restriction. by from... ok, after 0.005436s
[extractor] Fixing restriction starts ... ok, after 0.003737s
[extractor] Sorting restrictions. by to  ... ok, after 0.007261s
[extractor] Fixing restriction ends   ... ok, after 0.002283s
[info] usable restrictions: 17
[extractor] writing street name index ... ok, after 0.00049s
[info] extraction finished after 0.760565s
[info] To prepare the data for routing, run: ./osrm-prepare andorra-latest.osrm

[STXXL-ERRMSG] Removing disk file created from default configuration: /var/tmp/stxxl

fred@ubuntu-server:~/osrm-backend$ ./build/osrm-prepare andorra-latest.osrm
[info] Input file: andorra-latest.osrm
[info] Restrictions file: andorra-latest.osrm.restrictions
[info] Profile: profile.lua
[info] Threads: 2
[info] Generating edge-expanded graph representation
[info]  - 17 restrictions.
[info] Importing n = 70623 nodes 
[info]  - 2 bollard nodes, 0 traffic lights
[info]  and 71657 edges 
[info] Graph loaded ok and has 71657 edges
. 10% . 20% . 30% . 40% . 50% . 60% . 70% . 80% . 90% . 100%
[info] Node compression ratio: 0.0531555
[info] Edge compression ratio: 0.0668183
. 10% . 20% . 30% . 40% . 50% . 60% . 70% . 80% . 90% . 100%
[info] Generated 71657 nodes in edge-expanded graph
[info] generating edge-expanded edges
. 10% . 20% . 30% . 40% . 50% . 60% . 70% . 80% . 90% . 100%
[info] Generated 71657 edge based nodes
[info] Node-based graph contains 8515 edges
[info] Edge-expanded graph ...
[info]   contains 15498 edges
[info]   skips 16 turns, defined by 17 restrictions
[info]   skips 6643 U turns
[info]   skips 4 turns over barriers
[info] Timing statistics for edge-expanded graph:
[info] Renumbering edges: 0.000478s
[info] Generating nodes: 0.020419s
[info] Generating edges: 0.036728s
[info] building r-tree ...
[info] large component [4]=8425
[info] SCC run took: 0.00154662s
[info] constructing r-tree of 71657 edge elements build on-top of 70623 coordinates
[info] finished r-tree construction in 0.038825 seconds
[info] writing node map ...
[STXXL-MSG] STXXL v1.3.1 (release)
[STXXL-ERRMSG] Warning: no config file found.
[STXXL-ERRMSG] Using default disk configuration.
[STXXL-MSG] 1 disks are allocated, total space: 1000 MiB
merged 24 edges out of 30996
contractor finished initalization
initializing elimination PQ ...ok
preprocessing 8515 nodes .... 10% . 20% 

[TheMarex]

If you set the speed for edges very low, it will result in a duration of 0 (rounded to deci-seconds). Contractor make sure that every edge has at least duration 1, but on a graph with unit-weights I pretty sure that the contraction routine will just take ages. (there is no hierarchy in the network).

So this is actually working as expected, but I'm curious why you would do that?

[frodrigo]

With speed=1 it ends the prepare of Andorra but not on France. With speed of 100 it ends on France.

Maybe I misuse the profile or don't understand something. My goal it's to run an OSRM for shortest distance.

[TheMarex]

@frodrigo it is a rounding issue. If your speed is too low, small segments will get a duration of 0 because speed * length < 0.1 seconds.

[frodrigo]

Ok, I got the point. Thank you.