1 of 40

Challenges of building a traffic simulation from OpenStreetMap

Dustin Carlino (dabreegster@gmail.com)

https://github.com/dabreegster/abstreet

October 6, 2019 (CUGOS Fall Fling)

2 of 40

Goal

  • Ideas
    • Scramble cycles downtown
    • Bus-only University Ave after new light rail station
    • Montlake/520 overhaul, especially during construction
    • Remove dangerous vehicle intersections along Burke Gilman
    • Bus-only lanes all along 23rd Ave, Madison, Eastlake…
    • Converting flatter residential streets into a dedicated bike network
  • Short-term changes -- paint and signs prototypes
  • Anybody can try out ideas
    • [1], [2], [3], [4]

3 of 40

Proposed solution

4 of 40

Process

5 of 40

This talk’s focus

  • Detailed map model for a traffic simulation
    • Geometry of individual lanes
    • Where do vehicles stop at intersections?
    • What turns are legal from each lane?
    • How much on- and off-street parking?
    • How are traffic signals timed?
    • What trips do people take on a typical day?
  • Public data sources
    • OpenStreetMap
    • GTFS
    • Puget Sound Regional Council
    • King County GIS (blockface, street signs, public garages)

6 of 40

Map construction in… 17 minutes?

Full details at https://github.com/dabreegster/abstreet/blob/master/docs/articles/map/article.md

7 of 40

Lane/intersection geometry

8 of 40

9 of 40

OSM ways -> roads

10 of 40

OSM ways -> roads

OSM metadata

“lanes” = “4”

“bicycle” = “designated”

“turn:lanes:backward” = “left|through”

Blockface polylines

“PARKING_CATEGORY” = “No Parking Allowed”

11 of 40

Center polyline -> parallel lane polylines

  • Cap how far away the miter intersection can be
  • Detect when angle between adjacent lines changes from original and shifted, swap points to correct

12 of 40

13 of 40

Intersection geometry

  • Road should meet intersection perpendicularly
  • Don’t cover new space
  • Disjointly partition all space into intersection and roads

14 of 40

Intersection geometry

  • Sort roads by “angle”
  • Intersect all shifted polylines with all others
  • Project perpendicular from the hit to the original yellow center line

15 of 40

Intersection geometry

  • Trim the center line back the most from all the hits

16 of 40

Intersection geometry

Final polygon comes from:

  • Endpoints of trimmed center line projected left/right
  • Adjacent pairs of original shifted polylines contribute hits

Edge cases:

  • Resulting points double back
  • Deduplicate epsilon-equal points

17 of 40

Short roads gone wrong

18 of 40

Short roads gone wrong

19 of 40

Short roads gone VERY wrong

20 of 40

Short roads gone VERY wrong

21 of 40

Manual fix

  • OSM editors?
  • Serializing fixes is tricky
    • Matching up OSM/synthetic IDs
    • Same fixes for many maps
    • Order matters (operational transforms?)

22 of 40

Clipping

23 of 40

Clipping

  • Osmosis doesn’t trim ways or areas
  • Trim roads that cross, mark the intersection as a special border
    • Sometimes a road dips in and out of the boundary
    • Ideally just adjust the bounding polygon a little
    • Split into incoming and outgoing road, make two synthetic intersections
  • Polygon intersection for areas
    • Gluing together OSM’s multipolygons for Lake Washington doesn’t always work
  • During trip generation, source / destination may be outside the map
    • Match to nearest border

24 of 40

Clipping

25 of 40

Clipping

26 of 40

Turns

  • Match incoming to outgoing lanes
  • Vehicles
    • Left, right, straight
    • LaneChangeLeft, LaneChangeRight
  • Pedestrians
    • Crosswalk
    • SharedSidewalkCorner

27 of 40

OSM per-lane restrictions

Only apply to the “ends” of OSM ways

28 of 40

OSM turn restriction relations

Collapsed down to ban / only relations, ignore time/vehicle/turn type restrictions

29 of 40

Traffic signals

30 of 40

Traffic signals

  • Every cycle 30s?!
  • One-ways, bike/bus lanes, >4 roads usually resort to bad assignment
  • Realistic data source?

31 of 40

32 of 40

Sidewalks

Sadly not using OSM sidewalks

  • Complicates the process of many physical intersections comprising one physical
  • Not consistently mapped through Seattle

33 of 40

Sidewalks

  • Bidirectional in the traffic sim layer
  • Crosswalks
  • Shared sidewalk corners

34 of 40

Parking blackholes

Ever been trying to park, but accidentally wind up on 520 and drive off the map?

35 of 40

Parking blackholes

Ever been trying to park, but accidentally wind up on 520 and drive off the map?

… Turns out the driving graph isn’t connected

Find strongly connected components, redirect “blackholed” lanes to nearest driving lane in the largest SCC, start searching for parking from there instead

36 of 40

37 of 40

wat

38 of 40

General tricks

  • Separate phases (don’t re-parse OSM every run)
  • Manual intervention is inevitable
    • Fixes must be version controlled, browseable
  • IDs for roads/intersections
    • Final form: compacted, contiguous array
    • RawMap: stable IDs as we delete/split/copy things
    • Cross-map IDs
      • V1: longitude, latitude
      • V2: OSM way ID, node 1 ID, node 2 ID
        • Synthetic objects mustn’t collide

39 of 40

Visual diffs

Misses semantic changes (different traffic signal defaults, legal turns)

40 of 40

Conclusion