M2-T5 — Roadmaps, Lanes and Semantic Maps

Learning objectives

After this lesson, you should be able to:

• Represent a building as a graph of places and lanes with lengths, speeds and directions.
• Compare the size and planning cost of a lane graph with a grid of the same building.
• Add speed zones, one-way lanes and keep-out areas, and say where each belongs.
• Say when a roadmap beats a grid, and why most systems use both.

The intuition

A metro map is a roadmap. It is not to scale; it records stations, the lines between them and the transfers. Its job is to answer “how do I get from here to there” quickly, and it can only answer for places and links someone put on it. For everything inside a station, you look around.

A robot roadmap works the same way. Nodes are places that matter (the lobby, a lift, a door, a charging dock), and lanes are the routes between them that are known to be traversable. Planning is a search on a graph of dozens of nodes instead of millions of cells. The grid is still needed for the last few metres, where the robot must dodge a person or a trolley.

The mathematics

The graph

A route is a sequence of nodes. Its cost is a sum over its edges, and the cost does not have to be length:

Attributes that carry meaning

Size and speed

A hospital floor of 120 m × 60 m on a 0.05 m grid has 2400 × 1200 = 2.88 million cells. The lane graph of the same floor might have 40 nodes and 90 lanes. A search on the graph is effectively instant and can be recomputed whenever a lane is blocked.

Where roadmaps are weak

A roadmap contains only routes someone placed on it. It does not know about a cart in a lane. A robot on a lane still needs a local costmap to see the cart, and a local planner that can leave the lane, within limits. The roadmap says where to go; the grid says whether it is safe right now.

A worked example

Fastest route, not shortest. Four places A (lobby), B (lift), C (pharmacy), D (ward). Lanes: A–B 12 m, B–C 18 m, A–C 35 m, C–D 9 m. The shortest A to D is A→B→C→D = 12 + 18 + 9 = 39 m. The direct A→C→D would be 35 + 9 = 44 m.

Now add speed limits. The lane A–B is a crowded public corridor limited to 0.5 m/s: 12 / 0.5 = 24 s. B–C is 1.0 m/s: 18 s. C–D is 0.5 m/s: 9 / 0.5 = 18 s. The route A→B→C→D takes 24 + 18 + 18 = 60 s. The direct lane A–C has a limit of 1.2 m/s: 35 / 1.2 = 29 s, then C–D 18 s, a total of 47 s. The longer route is the slower one once speeds are attached: 44 m in 47 s beats 39 m in 60 s. A planner that counts only metres sends the robot through the crowd.

Keep-out. The surgery wing lies beside the lane A–C. A keep-out region is better stored as an area than as a missing lane, because the local planner must also be forbidden from cutting through it when it dodges a person. In Nav2 this is done with a keep-out filter on the costmap or a speed filter for zones.

Engineering implications and limitations

Authoring is the hard part

A roadmap is drawn, not learned. Tools such as map editors and the nav graph format of Open-RMF let facilities teams place lanes and attributes. Keep the source file under version control and load it into the robot like any other map.

Roadmap plus grid

Typical systems plan the route on the roadmap, then plan each leg on the costmap with the local planner, so a blocked lane triggers a replan on the graph instead of a stall.

Semantics and safety

Labels such as “lift” or “door” trigger behaviours. A wrong label is a safety bug, so treat map edits like code changes and test the route set after every change (module 8).

Fleets

Lane graphs are what a fleet manager reasons over: reservations, one-way rules and deadlock avoidance are all easier on a graph with a few hundred edges than on a grid (module 8).

Common misconceptions

Engineering takeaways

1. A roadmap is a graph of places and lanes, with lengths, speeds, directions and zones as attributes.
2. It is orders of magnitude smaller than a grid of the same building, so global planning is almost free.
3. Edge cost should be time and risk, not only distance: the shortest route can be the slowest.
4. Keep-out and speed zones belong in the map, where every planner has to respect them.
5. Use the roadmap to decide where to go and the costmap to decide whether it is safe now.

References and further reading

Standard planning textbooks and the Open-RMF documentation.

• H. Choset, K. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki and S. Thrun, Principles of Robot Motion, MIT Press, 2005, chapter 5.
• S. LaValle, Planning Algorithms, Cambridge University Press, 2006, chapter 6.
• Open Robotics, “Open-RMF” documentation, “Traffic Editor and Navigation Graphs”, osrf.github.io/ros2multirobotbook.
• Nav2 documentation, “Keepout Filter” and “Speed Filter”, docs.nav2.org.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Last in this module: terrain and three-dimensional maps, for robots whose floor is not flat.

Related content

Nothing below is required to finish this lesson.

• Before
  M2-T4: Layered Costmaps

  Describe static, obstacle, inflation and social layers, and explain marking, clearing and why ghost obstacles appear.