Off-road Navigation System

Installation
Documentation
Usage

by Denis Kozub

• World discretization using visibility graphs
• O(nh log n) reduced visibility graph algorithm (see algorithm explanation)
• A* pathfinding without graph precomputing
• Hierarchical approach for graph building
• No projected crs, works in any part of the world
• Open source OpenStreetMap data (see OSM data explanation)
• Downloading OMS maps at runtime
• Saving and loading precomputed map data
• Multiprocessing and visualization tools support

Scope of application:

• Extending functionality of other routing engines
• Road and facilities design
• Rescue and military operations planning
• Route planning for hiking and tourism

Usage

IPython notebook

Downloading and processing data

There are two ways you can obtain OSM data in osm.pbf format:

• Download it yourself: parts of the world, cities, adjustable area (via mail), adjustable area (online), planet
• Let the program download it for you

If the map is downloaded, you can specify the filename and parse it:

from offroad_routing import VisibilityGraph

vgraph = VisibilityGraph()
filename = "../maps/kozlovo.osm.pbf"
bbox = [36.2, 56.5, 36.7, 56.7]
vgraph.compute_geometry(bbox=bbox, filename=filename)

Or, alternatively, you can only specify the bounding box, and the map will be downloaded automatically (curl & osmosis required):

bbox = [34, 59, 34.2, 59.1]
vgraph.compute_geometry(bbox=bbox)

Parsed data can be pruned with chosen or default parameters. If not specified, optimal parameters will be computed by the algorithm.

vgraph.prune_geometry(epsilon_polygon=0.003,
                      epsilon_polyline=0.001,
                      bbox_comp=10)

Computed data can also be saved in .h5 file to skip data processing the next time:

vgraph.save_geometry("../maps/user_area.h5")

Using precomputed data and building visibility graph

from offroad_routing import VisibilityGraph

vgraph = VisibilityGraph()
vgraph.load_geometry("../maps/user_area.h5")

Visibility graph can be built and visualized using osmnx:

import osmnx as ox

G = vgraph.build_graph(inside_percent=0, multiprocessing=False)
ox.plot_graph(G)

VisibilityGraph may also be used to find incident edges for a single point. This feature is used for pathfinding without graph building:

import matplotlib.pyplot as plt
import mplleaflet

start = ((34.02, 59.01), None, None, None, None)
incidents = vgraph.incident_vertices(start)

fig = plt.figure()
plt.scatter(start[0][0], start[0][1], color='r')
for p in incidents:
    plt.scatter(p[0][0], p[0][1], color='b')
mplleaflet.display(fig=fig)

Building routes

from offroad_routing import VisibilityGraph, AStar

vgraph = VisibilityGraph()
vgraph.load_geometry("../maps/user_area.h5")

pathfinder = AStar(vgraph)
path = pathfinder.find((34.02, 59.01), (34.12, 59.09), default_weight=10, heuristic_multiplier=10)

Path can be viewed in coordinate format:

print(path.path())

However, specialized tools can be used to save and visualize the path:

The following code saves the path to a gpx file and generates a link to view it online.

from offroad_routing import GpxTrack

track = GpxTrack(path)
track.write_file("track.gpx")
track.visualize()

You can check the route here.

Performance

Computational time for an extremely dense area of 800 km² is about 20 seconds with multiprocessing. Computational time for a much freer area or 120 km² is 1 second. Since A* pathfinding does not require building the whole graph, computational time is even lower: The last example (see above) took only 0.6 seconds, which is 40% faster than building a graph.