Traversal Engine

Status & scope

Module: lens/traversal/
Milestone: Phase 2 (complete)

Purpose

Multi-modal routing engine: road graphs (OSM), terrain meshes (DEM), ocean grids. A* with composite cost from lens layers. Produces Route artifacts with per-segment cost breakdown.

Public API

`build_graph_from_osm_xml(xml_path) → RoadGraph`

Parse Overpass API XML → directed weighted graph.
Edges have speed_kmh, distance_m, highway type, bridge/tunnel flags.

`build_graph_from_dem(dem, origin_lat, origin_lon, cell_size_m) → RoadGraph`

DEM raster → 8-connected terrain mesh. Tobler's hiking function for slope cost.
Land cover overlay: open, light_veg, dense_veg, water (impassable), urban, rock.

`build_ocean_graph(bbox, grid_resolution, vessel_speed) → RoadGraph`

Lat/lon grid over water. Wave, current, ice penalties.

`route(graph, origin, destination, cost_fn) → Route | None`

A* with haversine heuristic (default cost). Dijkstra fallback for custom cost_fn.

`isochrone(graph, origin, budget, cost_fn) → Isochrone | None`

Dijkstra BFS, cut at budget. Returns convex hull boundary.

`build_composite_cost(layers, cost_registry) → Callable`

Lens layers → composite cost function for the router.

`graph.nearest_node(lat, lon) → int | None`

Numpy-vectorized nearest node lookup.

Dataclasses

RoadGraph

_graph: rustworkx PyDiGraph
_node_map: dict[int, int] (external_id → rx_index)
Methods: add_node, add_edge, nearest_node, apply_vehicle_filter

EdgeData (frozen)

Field	Type	Default
distance_m	float	0.0
travel_time_s	float	0.0
highway	str	""
surface	str	""
speed_kmh	float	0.0
grade_pct	float	0.0
bridge	bool	False
tunnel	bool	False
max_weight_t	float	0.0
max_height_m	float	0.0
oneway	bool	False

Route (frozen)

Field	Type
segments	tuple[RouteSegment, ...]
total_distance_m	float
total_travel_time_s	float
total_cost	float
origin	tuple[float, float]
destination	tuple[float, float]
cost_breakdown	dict

VehicleProfile (frozen)

Field	Type	Default
name	str	"car"
weight_kg	float	2000
height_m	float	1.8
max_grade_pct	float	15.0
max_speed_kmh	float	120

Cost Models (6 registered)

Name	Function	Params
travel_time	edge.distance / speed	speed_factor
slope_penalty	exponential above grade threshold	max_grade, penalty_base
weather_impact	rain/wind/snow/vis multiplier	precipitation_mm, wind_speed_ms
constraint	0 or inf (hard block)	blocked_highways, require_surface
risk_as_cost	threat score × travel_time	risk_score, risk_multiplier
coverage_as_cost	penalty for poor comms coverage	coverage_pct, min_coverage

File Layout

lens/traversal/
  __init__.py
  graph.py           ← RoadGraph, EdgeData, OSM/grid builders
  router.py          ← A* route, isochrone, composite cost
  cost_models.py     ← 6 traversal cost functions
  vehicle.py         ← VehicleProfile, presets (car, heavy_truck, emergency)
  terrain.py         ← DEM → terrain mesh, Tobler's function
  ocean.py           ← Ocean grid, wave/current penalties
  surface.py         ← MobilitySurface (component.prism.mobility-surface)

Test References

tests/test_router.py — A* routing, composite cost
tests/test_graph.py — graph building, edge metadata
tests/test_isochrone.py — Dijkstra BFS
tests/test_vehicle.py — vehicle filtering
tests/test_traversal_costs.py — cost model functions
tests/test_surface.py — mobility surface (component.prism.mobility-surface)

DO NOT

Import platform services (ES, Cortex) — standalone only
Use osmnx for routing — it's a data loader, not a router
Build workflow engines — route() is a single pure computation

Depends on: component.prism.cost-primitives, component.prism.universal-lens-parser