Publication Date: 2020-01-08

Approval Date: 2019-11-22

Submission Date: 2019-09-08

Reference number of this document: OGC 19-041r3

Reference URL for this document: http://www.opengis.net/doc/PER/routing-pilot-er

Category: OGC Public Engineering Report

Editor: Sam Meek, Theo Brown, Clemens Portele

Title: OGC® Routing Pilot ER

OGC Public Engineering Report

COPYRIGHT

Copyright © 2019 Open Geospatial Consortium. To obtain additional rights of use, visit http://www.opengeospatial.org/

WARNING

This document is not an OGC Standard. This document is an OGC Public Engineering Report created as a deliverable in an OGC Interoperability Initiative and is not an official position of the OGC membership. It is distributed for review and comment. It is subject to change without notice and may not be referred to as an OGC Standard. Further, any OGC Public Engineering Report should not be referenced as required or mandatory technology in procurements. However, the discussions in this document could very well lead to the definition of an OGC Standard.

LICENSE AGREEMENT

Permission is hereby granted by the Open Geospatial Consortium, ("Licensor"), free of charge and subject to the terms set forth below, to any person obtaining a copy of this Intellectual Property and any associated documentation, to deal in the Intellectual Property without restriction (except as set forth below), including without limitation the rights to implement, use, copy, modify, merge, publish, distribute, and/or sublicense copies of the Intellectual Property, and to permit persons to whom the Intellectual Property is furnished to do so, provided that all copyright notices on the intellectual property are retained intact and that each person to whom the Intellectual Property is furnished agrees to the terms of this Agreement.

If you modify the Intellectual Property, all copies of the modified Intellectual Property must include, in addition to the above copyright notice, a notice that the Intellectual Property includes modifications that have not been approved or adopted by LICENSOR.

THIS LICENSE IS A COPYRIGHT LICENSE ONLY, AND DOES NOT CONVEY ANY RIGHTS UNDER ANY PATENTS THAT MAY BE IN FORCE ANYWHERE IN THE WORLD. THE INTELLECTUAL PROPERTY IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND NONINFRINGEMENT OF THIRD PARTY RIGHTS. THE COPYRIGHT HOLDER OR HOLDERS INCLUDED IN THIS NOTICE DO NOT WARRANT THAT THE FUNCTIONS CONTAINED IN THE INTELLECTUAL PROPERTY WILL MEET YOUR REQUIREMENTS OR THAT THE OPERATION OF THE INTELLECTUAL PROPERTY WILL BE UNINTERRUPTED OR ERROR FREE. ANY USE OF THE INTELLECTUAL PROPERTY SHALL BE MADE ENTIRELY AT THE USER’S OWN RISK. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR ANY CONTRIBUTOR OF INTELLECTUAL PROPERTY RIGHTS TO THE INTELLECTUAL PROPERTY BE LIABLE FOR ANY CLAIM, OR ANY DIRECT, SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING FROM ANY ALLEGED INFRINGEMENT OR ANY LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR UNDER ANY OTHER LEGAL THEORY, ARISING OUT OF OR IN CONNECTION WITH THE IMPLEMENTATION, USE, COMMERCIALIZATION OR PERFORMANCE OF THIS INTELLECTUAL PROPERTY.

This license is effective until terminated. You may terminate it at any time by destroying the Intellectual Property together with all copies in any form. The license will also terminate if you fail to comply with any term or condition of this Agreement. Except as provided in the following sentence, no such termination of this license shall require the termination of any third party end-user sublicense to the Intellectual Property which is in force as of the date of notice of such termination. In addition, should the Intellectual Property, or the operation of the Intellectual Property, infringe, or in LICENSOR’s sole opinion be likely to infringe, any patent, copyright, trademark or other right of a third party, you agree that LICENSOR, in its sole discretion, may terminate this license without any compensation or liability to you, your licensees or any other party. You agree upon termination of any kind to destroy or cause to be destroyed the Intellectual Property together with all copies in any form, whether held by you or by any third party.

Except as contained in this notice, the name of LICENSOR or of any other holder of a copyright in all or part of the Intellectual Property shall not be used in advertising or otherwise to promote the sale, use or other dealings in this Intellectual Property without prior written authorization of LICENSOR or such copyright holder. LICENSOR is and shall at all times be the sole entity that may authorize you or any third party to use certification marks, trademarks or other special designations to indicate compliance with any LICENSOR standards or specifications.

This Agreement is governed by the laws of the Commonwealth of Massachusetts. The application to this Agreement of the United Nations Convention on Contracts for the International Sale of Goods is hereby expressly excluded. In the event any provision of this Agreement shall be deemed unenforceable, void or invalid, such provision shall be modified so as to make it valid and enforceable, and as so modified the entire Agreement shall remain in full force and effect. No decision, action or inaction by LICENSOR shall be construed to be a waiver of any rights or remedies available to it.

None of the Intellectual Property or underlying information or technology may be downloaded or otherwise exported or reexported in violation of U.S. export laws and regulations. In addition, you are responsible for complying with any local laws in your jurisdiction which may impact your right to import, export or use the Intellectual Property, and you represent that you have complied with any regulations or registration procedures required by applicable law to make this license enforceable.

Table of Contents

1. Subject

The goal of this OGC Routing Pilot Engineering Report (ER) is to document the proof of concept of an Application Programming Interface (API) conforming to a profile of the draft OGC API - Processes specification that allows implementation of vector routing across one or more routing engines. The components implemented in the OGC Open Routing API Pilot 2019 included two clients, interfacing with three implementations of the draft OGC API - Processes specification that in turn communicated with three routing engines. This work resulted in the definition of a proposed common interface and data exchange model supported by all components for requesting, generating and returning routes.

routes
Figure 1. Route Examples

2. Executive Summary

This document describes the implementations to support the OGC Open Routing API Pilot 2019. The purpose of the work was to utilize new and emerging OGC standards to support routing applications in denied, degraded, intermittent or low bandwidth (DDIL) environments as these are of particular importance to the sponsor. A secondary requirement was to define and implement an exchange model for routing information. The requirements for this model were: That the model uses GeoJSON and that it was lightweight enough to support exchange in DDIL environments. Contextually, DDIL has been a concern within the OGC for a number of years. This Pilot was a further exploration of strategies to support the environment.

The DDIL environment requirement was expressed as three scenarios:

  • Online - where the client has full connectivity with the server components.

  • Offline - the client has no connectivity and will not have connectivity.

  • Intermittent - one of the clients has connectivity, but the rest do not.

The scenarios created requirements for the component operations. The online scenario required interoperability between all clients, all OGC APIs, all routing engines (HERE, Skymantics and Ecere) that utilize all datasets. The Offline scenario required all components to be co-located in order to maintain functionality whilst removing the reliance on connectivity. This resulted in a sub-set of options made available to the user. The intermittent scenario required a single client to have access to online routing capabilities and the route be shared among the clients using the Pilot routing exchange model encapsulated in a GeoPackage. The components utilized in the Pilot include:

  • Web clients:

    • Ecere

    • GIS-FCU

    • Skymantics

  • Desktop client:

    • Helyx SIS - QGIS

  • 3D client

    • Helyx SIS - Cesium

  • OGC API - Processing instances

    • 52 Degrees North

    • Helyx SIS

    • Skymantics

    • GIS-FCU

  • Routing engines:

    • HERE

    • Skymantics

    • Ecere

    • OSRM

  • Datasets for routing:

    • HERE

    • NSG

    • OSM

The experiments involved components from different participants, combining the client capabilities with a variety of processing services end-points implementing the Open Routing API (Ecere, Skymantics, Helyx, 52° North and GIS-FCU), three different routing engines used for computing the routes (Ecere, Skymantics and HERE), and different source data for the roads network used by those calculations (OpenStreetMap, HERE and NSG). The interoperability between the clients, OGC APIs, routing engines and data sources has shown that the new OGC APIs are fit for purpose in DDIL environments given the sponsor scenarios. Additionally, the distribution of routing data between the clients in the intermittent scenario provided a mechanism for utilizing networks in sub-optimal connectivity scenarios, it is likely that this approach to architecture and development can be followed in future innovation endeavors.

The outputs of the Pilot consisted of several components with multiple implementations of each type of component. The component types included; clients for web and desktop use cases, routing engines to do the routing work, datasets to support the routing engines and OGC APIs to mediate the communication between the clients and the routing engines in a standardized manner. The data exchange was performed using the Routing Exchange Model, which is a lightweight version of GeoJSON and described fully in Annex A.

The Pilot included an exploration of transport mechanisms for data over the web. Typical requests to web services are either synchronous or asynchronous. The synchronous request was useful for small routes as they can be generated and the routes returned in a timely manner without causing the client or server to visibly lock. The asynchronous methods included:

  • Polling - checking the server at a defined interval to see whether a result has been generated.

  • Callback - providing the server with a URL on the client side to post the result to.

  • Server Sent Events (SSE) - a one-way web socket approach.

The different methods are available in the QGIS client as selectable parameters for demonstration and performance testing purposes.

The OGC API is an emerging standard and at time of writing more of a set of practices. The approach adopted in this Pilot was to implement conformance classes, these are then used to build the clients automatically to expose the features of the API, in this case, the routing engines. It is recommended that this approach to APIs be adopted across the OGC suite as it provides an efficient method of delivering interoperable capability without having to heavily specify clients.

Future work for the Pilot includes development of the OGC interfaces to support further routing constraints such as elevation, restricted maneuvers, speed limits, street hierarchies and transportation methods. Uplifting the routing engines would enable further testing with eventual convergence on real-world requirements. Additionally, OGC APIs should be explored further by understanding API efficiency, structure and potential bottlenecks.

2.1. Document contributor contact points

All questions regarding this document should be directed to the editor or the contributors:

Contacts

Name Organization Role

Sam Meek

Helyx SIS

Editor

Theo Brown

Helyx SIS

Editor

Clemens Portele

interactive instruments GmbH

Editor

Christian Autermann

52°North GmbH

Contributor

Ricky Lin

GIS.FCU

Contributor

Nacho Correas

Skymantics

Contributor

Josh Lieberman

Open Geospatial Consortium

Contributor

Donovan Dall

Helyx SIS

Contributor

Jérôme Jacovella-St-Louis

Ecere

Contributor

2.2. Foreword

Attention is drawn to the possibility that some of the elements of this document may be the subject of patent rights. The Open Geospatial Consortium shall not be held responsible for identifying any or all such patent rights.

Recipients of this document are requested to submit, with their comments, notification of any relevant patent claims or other intellectual property rights of which they may be aware that might be infringed by any implementation of the standard set forth in this document, and to provide supporting documentation.

3. References

The following normative documents are referenced in this document.

4. Terms and definitions

For the purposes of this report, the definitions specified in Clause 4 of the OWS Common Implementation Standard OGC 06-121r9 shall apply. In addition, the following terms and definitions apply.

● application programming interface

standard set of documented and supported functions and procedures that expose the capabilities or data of an operating system, application or service to other applications (adapted from ISO/IEC TR 13066-2:2016)

● feature

abstraction of real-world phenomena (source: ISO 19101-1:2014)

● OpenAPI definition | OpenAPI document

a document (or set of documents) that defines or describes an API and conforms to the OpenAPI Specification [derived from the OpenAPI Specification]

● Web API

API using an architectural style that is founded on the technologies of the Web [derived from the W3C Data on the Web Best Practices]

Note
 Best Practice 24: Use Web Standards as the foundation of APIs in the W3C Data on the Web Best Practices provides more detail.

4.1. Abbreviated terms

  • API Application Programming Interface

  • GML Geography Markup Language

  • HATEOAS Hypermedia As The Engine Of Application State

  • JSON JavaScript Object Notation

  • WFS Web Feature Service

  • WPS Web Processing Service

  • REST Representational State Transfer

5. Overview

Section 6 introduces the motivation for conducting the Pilot. It describes in brief the ongoing OGC discussion regarding the modernization of OGC web interfaces and how this has been accounted for during the pilot. This section also discusses the requirements set by the sponsors in the form of three scenarios.

Section 7 discusses the overarching architecture of the pilot, taking into account the interactions between the various components. The delivery of the sponsor requirements is explained and the commonalities across the various pilot implementations is also outlined.

Section 8 contains the details of each participant implementation, providing insight into the specific design of implementations, the challenges encountered across the pilot and examples of how to implement the API and exchange model.

Section 9 documents the Technology Integration Experiments.

Section 10 discusses recommendations generated during the pilot.

Section 11 contains the conclusions of the pilot work.

Annex A Details the Routing Exchange Model developed during the Pilot.

6. Background

This OGC Engineering Report (ER) describes the work done in the OGC Open Routing API Pilot 2019. The two major concepts in this Pilot, routing capabilities and OGC API approaches, have been previously explored in depth by a number of OGC endeavors. The purpose of this section is to draw upon this previous work to provide a context for the OGC Routing API Pilot 2019.

The previous work for this ER includes, but is not limited to work described in the following documents:

Next generation APIs:

  • 18-045 OGC Testbed-14: Next Generation Web APIs - WFS 3.0 Engineering Report - At the time of writing this report represents the most current documented approach to the OGC API.

  • 18-021 OGC Testbed-14: Next Generation APIs - Complex Feature Handling Engineering Report - Although the Routing Pilot does not deal with complex features, this report is useful for understanding the modular approach of the OGC API, specifically the topic of extensions to the API.

Routing Capabilities:

  • 16-029r1 Testbed-12 GeoPackage Routing and Symbology Engineering Report - This report provides insight into how a routing GeoPackage may be used in a mobile application, providing context for the browser and desktop clients documented in this ER.

  • 07-074 OpenGIS Location Service (OpenLS) Implementation Specification: Core Services – An OGC standard consisting of the composite set of basic services comprising the OpenLS Platform.

  • 08-028r7 OpenGIS Location Services (OpenLS): Part 6 - Navigation Service (1.0.0) - the corresponding navigation capability for the OpenLS Interface Standard.

6.1. The OGC API - Processes specification

Note
 Prior to the OGC API – Processes naming convention, the specification was referred to as WPS 3.0. The official name of the specification is now OGC API – Processes. This ER therefore, at times, acceptably refers to implementations of OGC API – Processes as WPS.

  • 18-036 OGC Testbed-14: WPS-T Engineering Report - Provides useful insight into some of the more recent WPS 2.0 work, as context for moving the processing capability to an OGC API.

The recent advances to the Web Feature Service (WFS) and Web Processing Service (WPS) standards to support a modern API approach have been significant. This work draws upon elements of the OpenAPI specification and Representational State Transfer (REST) principles to provide a modular building block approach to web interfaces. It is an ongoing process to reach a consensus in the OGC for the next generation standards. The emerging OGC API – Processes draft specification (which is based on WPS) should support a routing capability that conforms to this modular approach. While this routing work was being carried out, Testbed-15 was running in parallel. There was some overlap between both work efforts and coordination between these efforts enabled a joined-up approach by sharing interim findings.

The OGC API – Processes draft specification adopts a resource-based approach, which is along the same lines as the OGC API – Features specification (formerly named WFS 3.0) except it is focused on processing services. The OGC API – Processes draft specification has not yet been approved as a standard and is some way from ratification, therefore implementations in this Pilot were experimental and contributed to the discourse on OGC APIs. A point of contention at time of writing was the structure and nature of OGC APIs for processing - the concept of OGC API is superseding WPS as OGC’s processing API. There were broadly two schools of thought regarding OGC API architecture and design:

  1. A very lightweight raw OpenAPI version of processes, for example in this Pilot "/routes/"

  2. A somewhat lightweight version of OpenAPI that conforms broadly to WPS2.0 calls, for example "/processes/<processName>/jobs"

A convention of this ER is that these two options are referred to Option 1 and Option 2 throughout the text. This is a reflection of the naming conventions from the Pilot work. It is suggested that these options are named formally in a TC working group should the TC choose to standardize both approaches.

One argument for choosing Option 1 and essentially dropping the WPS construct is that unlike the other OGC services such as WFS, WCS and others, there is nothing inherently geospatial about WPS and it has always been a somewhat artificial construct. This is likely to be an on-going discussion and was not resolved by the end of the Pilot. Therefore, the clients and WPS implementations supported both options as a demonstration exercise.

6.2. Overview of Pilot architecture

The Pilot architecture comprised of two clients, three implementations of OGC API - Processes profiles, and three routing engines. These combine to make a variety of interoperable, end-to-end routing capabilities. All clients interface with all implementations of the OGC API, which in turn interface with all routing engines. Therefore, every client has the ability to select any combination of OGC API implementations and routing engines.

The supplied source datasets from OpenStreetMap (OSM), HERE and the US National System for Geospatial Intelligence (NSG) were converted to GeoPackages and used by the technical components as inputs into the routing engines. The WPS Routing API ER (a sister document to this ER) documents the technical discussions and findings relating to all API considerations, which is not covered in this scope of this ER. The Route Exchange Model Annex details the GeoJSON encoding used to transfer content between the technical components of the Pilot architecture. At this time, there was no conceptual model for route exchange, although such conceptual models could be created as part of a future pilot or as work within the working groups of the Technical Committee (TC).

The Pilot considered three specific use cases aimed at tackling real-life routing challenges. These three use cases assume the possibility of DDIL environments and the need to support a variety of route choices. This environment lends itself to three distinct scenarios, online, offline, or hybrid, where a client has connectivity to get capability and data, but it is lost over time.

7. Pilot Technical Architecture

The Pilot architecture includes a variety of implementations all supporting the Routing API and the Routing Exchange Model. The Routing API is discussed in brief here, further detail can be found in the WPS Routing API ER [1]. In addition, the Routing Exchange Model is outlined, for further detail refer to Annex A Routing Exchange Model.

7.1. Scenarios

The Pilot architecture consisted of three scenarios influenced by the DDIL environment use cases. These were:

  • Online - fully connected with stability

  • Intermittent - unreliable connection.

  • Offline - no connectivity

7.1.1. Online Scenario

In the Online Scenario, the operator uses one of the clients to request a route from any of the implementations of OGC API - Processes profiles. The chosen profile implementation then passes this request on to one of the routing engines using the routing exchange model. The engine is tasked to complete a route using a variety of parameters that are described later in this document.

Once computed by one of the engines the route is returned to the profile implementation using the exchange model. This profile implementation then passes the route back to the client to be visualized and shared by the operator.

The Online Scenario components must support the ability to choose which OGC API - Processes profile to use, which routing engine to use and which routing algorithm to use. In addition, the ability to allow extra criteria must be supported, such as maximum height of vehicle, obstructions or areas to avoid, and arrival or depart time. Finally, the choice of the fastest route or shortest route should also be available.

The online scenario is where the components in the Pilot have consistent connections between them and out to the wider internet.

Online Scenario Component Diagram
Figure 2. Online Scenario Architecture

Figure 2 describes the architecture in the online scenario. Essentially there are three virtual subsystems (that is, individual components not co-located performing the same function) that can communicate with all of the components within the upstream and downstream virtual subsystems. For example, the Ecere client was able to configure and execute the HERE routing engine via the Helyx OGC API.

This architecture uses the Routing API established as part of this pilot for all request and response handling between the client and OGC API Process Profiles.

7.1.2. Intermittent Scenario

The intermittent scenario is where the components have connectivity, but it is not necessarily:

  • Consistent

  • Stable

  • Reliable

  • High-speed

Therefore, the network cannot be relied upon to provide connectivity on demand and compensation actions are likely when connectivity is not available. Intermittent connectivity is unpredictable and it maybe that in the real-world, decisions are made to treat intermittent connectivity as no connectivity, as it is the only sensible course of action, especially if the scenario involves threat to life.

In the Routing Pilot API, the intermittent scenario was described as a situation where only one of the clients had access to a routing engine. Therefore, the connected client had the ability to create routes, but none of the other clients did. Additionally, there were situations where the clients are able to communicate with each other via some other means (Bluetooth or some other peer-to-peer communication, for example). This scenario could also be a situation where a client had connectivity to a routing engine, but has lost it due to other reasons.

The solution proposed to address intermittent connectivity is to enable the clients to share pre-defined routes, that is, the routing operation has been completed when a connection to the routing engine was established, but has now been lost. Route sharing between clients is facilitated by the JSON encoded Route Exchange Model, described in the annexes.

7.1.3. Offline Scenario

The third scenario assumed that there was no connectivity outside of a device’s local network, this could be a desktop computer, mobile device or a mesh. In the real-world the scenario is modeling an instance where there is no connectivity and there is not going to be any connectivity for the duration of an operation. To mitigate the lack of connectivity, the routing engines, the WPS and the clients are packaged on the same machine. Therefore, the routing engine implementers made the routing engine available for installation on the client machine.

In the Offline scenario the operator uses the routing functionality provided by the client to create a route. The operator then shares this route with other clients using the route exchange model. To enable the required functionality, all of the capability has to be tightly coupled in a single location. Practically, this involves installing all of the components on the same machine to remove communication dependencies with the wider network.

7.2. Client Execution Patterns

There are several clients that execute the OGC APIs to task the routing engines. The description of each of these clients is covered in the relevant components section. This section describes the generic client-server communication patterns that are utilized by the clients, these were:

  • Synchronous

  • Asynchronous

  • Callback

  • Server-sent events (SSE)

7.2.1. Synchronous

The synchronous interaction pattern is typical of short-running processes. The client configures the routing engine parameters and sends the execute request, the client then holds the connection open to the server until it receives a response. This model is simple and efficient for small requests and responses, but it can cause time out exceptions and cause the client to hang until a response or time out is received.

Synchronous sequence
Figure 3. Synchronous Client execution pattern

7.2.2. Asynchronous Polling

Asynchronous execution is when the client sends an execution command to the server, but does not wait for a result. There are then several options for checking whether the result has been generated. In this client, the method of checking for a result is called polling, that is, checking back with the server at a defined time for a result. This is slightly more efficient that synchronous as it releases the thread post execution request. However, it can be inefficient as the client is constantly checking the server and the server has to respond each time, which can affect network and computational performance.

Asynchronous polling sequence
Figure 4. Asynchronous Polling Client execution pattern

7.2.3. Callback

Callback has a slightly different approach to asynchronous as the client sets up a miniserver in the background upon opening. This server stays active whilst the client is active and the client provides the miniserver address to the OGC API endpoint. The OGC API then uses a POST request to send the result to the miniserver. This has the advantage of removing the requirement to polling, but it does make the client a little more heavyweight as there is a second server involved. This approach is particularly relevant to many Desktop clients that rely on threading such as QGIS. The miniserver is started on a separate thread to stop machine lockup.

Callback QGIS sequence
Figure 5. Callback execution pattern

7.2.4. Server-sent Events

SSE is a compromise between synchronous and asynchronous as it utilizes both approaches in its cycle. When the client creates a POST request to execute the routing engine through the OGC API, it also creates an SSE request. The routing engine produces the route and then sends a handshake to the client using the SSE endpoint, the data are then streamed to the client.

SSE QGIS Sequence
Figure 6. SSE execution pattern

7.3. API Pattern Options

The design of the API for Routing is discussed at length in the WPS Routing API ER, however, the design of the API has ramifications for design of servers, clients and the appropriate architecture pattern for the different options. The two options are broadly as follows:

  1. Option 1 - Using Routes as a resource.

  2. Option 2 - Including a WPS facade in the API path.

Option 1 is the most simplistic and does not require any artificial inclusion of prefixes in the paths. The OpenAPI standard has the vocabulary to define processes, and unlike WFS, which has a lot of geospatial specific guidance, WPS has always been designed to provide processing capability regardless of any geospatial constraints.

Option 2 respects the current WPS 2.0 path parameters and includes a /processes/ prefix to indicate it is a WPS. Including the WPS pattern as part of the OGC API for processing enables continuity between the old WPS and the new WPS, however it introduces complexity and rigidity.

A wider discussion regarding the API pattern design and its relevance to WPS is to understand where data requests end and processing begins. When a user requests a dataset using WFS and parameters are applied to the request, then some data processing has to take place to fulfill the request. For example, when a user requests a dataset subset bounded by coordinates, then the operation on the server goes beyond simply returning the dataset as is and processing takes place. However, this is not considered a processing service and the line between data return and processing services is not well defined. For the Pilot, anything that created a new resource was considered a processing service, however this is a mutable claim, as one could simply create a new resource with a dataset subset.

For the scope of this ER all APIs support at least one of these Options in order to allow for the Scenarios to be tested.

For further information on the APIs used during this Pilot see the OGC Routing API ER [1].

7.4. Input Datasets

The input data used by the Routing Engines to produce the routes is key to the routing capability efforts. Not only does this determine the structure of the routes produced, but also how they are displayed by the clients using the Routing Exchange Model.

The three datasets used are listed below, with a brief description of each. These datasets are discussed in more detail in the Routing Engine implementation sections.

  • NSG: The National System for Geospatial Intelligence (NSG) Entity Catalog (NEC) specifies an NSG-wide semantic model for geospatial data. This semantic model includes: feature information concepts with their allowed geometric representations and related constraints, attributes with their domain types, associations with their roles, and accompanying metadata. The NEC specifies the domain data model for feature-based geospatial intelligence that determines the common semantic content of the NSG despite varying physical realizations across DoD/IC systems (i.e., regardless of whether geospatial features are represented as an image, a multi-dimensional grid of values, or a set of one or more vector shapes). Derivative models like Topographic Data Store (TDS) and US Army’s Ground-Warfighter Geospatial Data Model (GGDM) identify specific content of the NEC that shall be obligatory for geospatial intelligence producers using this specification, and specifies the conditions under which this geospatial intelligence shall be collected by producers for use in net-centric data exchange with other NSG participants. The data sample provided in this pilot is a provisional NEC-based Model for military focused routing. This dataset is a profiled approach to the NEC that extracts key pieces of information conducive to military focused routing which includes Military Load classification, Overhead Clearances. It consists 3 core components, Nodes, Edges, and Network with an auxiliary association table liking NAS features with the edges of the graph. Nodes model the origin and terminus of each relationship (Edge) and NAS entities are associated to create a contextual or subject based network for analysis. These relationships are modelled through the node/edge graph structure and can be associated with geophysical phenomena such transportation entities or abstract relationships such as political, social, and economic matters. For this pilot, the NAS transportation entities Road, Bridge, and Tunnel were associated to the edges and provide the cost components of the graph. The baseline network was abstracted from OpenStreetMap data of Washington, D.C. However, the attributes in this sample are assigned for Test and Evaluation use only and do not represent actual geophysical phenomena in some cases (e.g. LC1-4) are grossly inaccurate. This data is fabricated to provide a controlled set of information to generate specific routes. The area is:

    {"type":"Polygon","coordinates":[[[-77.1176857,38.7924115],[-77.1176857,38.9952444],[-76.8773984,38.9952444],[-76.8773984,38.7924115],[-77.1176857,38.7924115]]]}

  • OSM: The OpenStreetMap (OSM) project is an initiative that provides user-generated street maps for the entire world. OSM follows a peer-production and peer-review model similar to that adopted by Wikipedia. The project aims to create map data that is available for anyone to use or edit for free. As a crowd-sourcing initiative, OSM comes with varying levels of data quality and as such has been the subject of several studies reviewing the quality of its data.

  • HERE: NAVSTREETS is a commercial data product by HERE that provides road network data that includes functional classifications of roads, and geographic representations of features such as airports, aircraft roads, cemeteries, golf courses, hospitals, military bases, parks, national monuments, pedestrian zones, shopping centers, sports complexes, undefined traffic areas, university/colleges, and woodlands. NAVSTREETS provides users with information such as access to expressway ramps, connectivity of roadways, one-way streets, turn restrictions, construction projects, and lane dividers.

8. Pilot Component Implementations

This section describes the implementations from each of the vendors involved in the Pilot. It is split into clients, WPSs and routing engines.

8.1. Client Implementations

8.1.1. Helyx QGIS Client

8.1.1.1. Design Considerations

The client is a desktop based QGIS plugin to support network routing. The goal was to provide the ability to easily compute and display new routes, fetch existing routes and share routes with other clients in line with the sponsor requirements. These routes are converted to QGIS layers for display and to allow users to input them into native QGIS functions, the data exchange was performed using the Route Exchange Model and the exchange format was GeoPackage.

QGIS was also chosen due to its extensive plugin customization and by request of the sponsor. The majority of this plugin capability uses PyQT, a python module for developing interactive interfaces. Once the PyQT capabilities were evaluated it was clear that this combination of PyQT and QGIS would provide the necessary functionality to produce the desired interface.

The design of the UI is broken down into five QGIS windows. The initial window (see Figure 7) allows the user to choose an API landing page URL to utilize. In order to account for both Option 1 and Option 2 of the Routing API this window provides the ability to choose which option to use when requesting routes.

The initial window also allows the user to choose offline routing or to open the sharing window. The offline routing option supports the Offline Routing Scenario described in previous sections.

QGIS Plugin OpeningWindow
Figure 7. QGIS Plugin Opening Window

If Option 1 or Option 2 are chosen, then a corresponding window is displayed depending on the choice.

The Option 1 choice opens a comprehensive input window (see Figure 8) for the user to input route options and request a route.

QGIS Plugin Option1InputWindow
Figure 8. QGIS Plugin Option 1 Input Window

The Option 2 choice opens a window displaying all processes exposed at the API’s processing endpoint (see Figure 9). The user then selects a process, sees the description and choose to continue with the chosen process.

QGIS Plugin Option2ProcessesWindow
Figure 9. QGIS Plugin Option 2 Processes Window

The previous step opens a third window which is dynamically constructed to provide the input options and request options for the chosen process (see Figure 10).

QGIS Plugin Option2InputWindow
Figure 10. QGIS Plugin Option 2 Input Window

Both the Opening window and the Option 1 Input window provide the ability to open the Sharing Window (see Figure 11). Once the sharing window is opened the user can select layers in the QGIS panel or GeoJSON files to share. The routes can be shared by sending them directly to other clients using the QGIS plugin or exported as a GeoPackage for offline sharing.

QGIS Plugin SharingWindow
Figure 11. QGIS Plugin Sharing Window

This design provides the core functionality to create and visualize routes. It is expected that any extensions could easily be added by including an additional window, for example to create/edit routes manually.

In addition, the design ensures the functionality for Option 1 and Option 2 are distinct from one another, meaning the two capabilities could be de-coupled in the future if required.

8.1.1.2. Encountered Challenges and Solutions

The following challenges were encountered during the development of the client. Some of these challenges are implementation specific whilst others relate directly to the Routing Exchange Model and Routing API.

8.1.1.2.1. Multi-Threading to Support Asynchronous Requests

The Routing API exposes a number of endpoints to support asynchronous requests. These endpoints allow the client to request a route via a post request and later fetch the created route. The basic method for this asynchronous request is polling, where the client requests a route and uses the returned Location header to find the resource. This resource endpoint is then polled until a finished status is returned by the resource endpoint. In contrast the more efficient webhook (user defined HTTP callbacks) asynchronous method requires the client to provide a client-side subscriber URL in their route request. This URL is then used by the WPS to return the route once complete; the WPS sends the route data to the subscriber URL once the route is finished. This means only two requests are made, one Post request from the client to the server and one Post request from the server to the client. This is in contrast to polling where requests are made from the client to the server at regular intervals until the server reports a status change (or times out).

In order for QGIS to handle webhook functionality and expose a subscriber URL to the WPS, a server is required to run in the background of the application. This proved to be a challenge as QGIS runs on the main thread on the machine, meaning any other process, such as a server, running on the same thread causes QGIS to crash.

The solution to this challenge is to launch a separate thread at the point the Option 1 Input window opens in QGIS. The server is then started on this second thread and waits for any Post requests from APIs which have been sent subscriber URLs. The second thread is stopped when the QGIS plugin window is closed, meaning the cleanup for the thread has to be robust enough to allow the widget to be opened and closed repeatedly without conflicting threads being created.

8.1.1.2.2. Conformance classes and Dynamic GUIs

The Routing API provides a list of conformance classes via a conformance endpoint allowing clients to identify what functionality the API supports. Option 1 of the API exposes a route definition schema and Option 2 exposes the standard WPS process input definitions. Both of these approaches list all potential inputs to the route request. Out-of-Band information is required to know what functionality each conformance class relates to and therefore, which inputs are supported by the API. Given this conformance class and input definition dichotomy, two differing methods were devised for client creation. This is intended to show the benefits and constraints of the two API elements when creating clients.

The first approach focuses on supporting Option 1 of the API and relies on out of band knowledge of the conformance classes. If a conformance class exists, such as obstruction, then the client exposes input capability to send an obstruction as part of the routing request. The client cannot programmatically determine this input information from the conformance class, out-of-band knowledge is used to decide what sort of input to expose for each conformance class.

The second approach focuses on supporting Option 2 of the API and relies purely upon the input parameter definitions exposed by the process endpoint, which requires no out-of-band information. The client programmatically parses the input definitions and exposes appropriate inputs for the user.

The first approach exposes an easy-to-use client with obvious inputs and appropriate support for all request types, such as callback support and synchronous support. However, the first approach has proven to be inflexible when new conformance classes are introduced, as the client then requires an update to support this new functionality.

The second approach exposes a flexible dynamic front end which can account for additional inputs provided they conform to the Option 2 API schema. However, as the client parses the inputs in order, and displays them as they are parsed the order of the inputs, the resultant Graphical User Interface (GUI) can appear illogical to the user. Additionally, the API lists all possible inputs, not specifically the inputs supported by the various routing engines. Therefore, the user can send an input which is listed in the input list, such as an obstruction, which may not be supported by the routing engine. This makes for a quick-to-implement and flexible GUI interface useful for exploring conformant APIs, but which may supply unavailable options and therefore invalid requests.

The ideal approach is a combination of the two; conformance classes to define extensions to the API, where each class link returns a subset of JSON input definitions. The client creator can then decide, using out-of-band information, to order and define the display of each set of conformance class inputs. This allows for the dynamic creation of client elements, such as the input elements for the conformance class obstruction.

8.1.1.2.3. QGIS and Heterogeneous Feature Collections

The Routing Exchange Model uses the GeoJSON Feature Collection schema to return the start, end and segment nodes as well as the overview line, that is, the unsegmented route from start to finish. These are all stored as MultiPoint, Point and LineString types in a single Feature Collection. QGIS does not programmatically support Feature Collections containing more than one type of feature (sometimes called complex features, although there are plugins available to support GML application schemas).

Therefore, the client solution receives the single Feature Collection from the API and stores this original Feature Collection on file, to be shared later on. The contents of this JSON file is then copied and separated out into a Node Feature Collection JSON file and an Overview Feature Collection JSON file. These are then all loaded into the QGIS map project to be visualized. This satisfies the requirement of the client needing to load the Route Exchange Model GeoJSON data directly. When added to the QGIS Layer List the two layers are grouped inside a group layer. This group layer provides the mechanism by which to select an entire route when using the sharing window.

8.1.1.3. Final Component Description

The QGIS Plugin supports an assumed user workflow; initially the user opens the plugin initial window Figure 7 and decides whether they wish to interact with an API or conduct offline routing or sharing. The sharing button opens the sharing window, the Offline Routing button opens the Offline Routing window, which leverages the routing engines, including the Open Source Routing Machine and the Ecere Routing Engine. If the user wishes to use an online routing API then the landing page URL is specified in the text input box. Following these steps the user can either choose to use the Option 1 API and click the 'Get Routing options' button or the Option 2 API and click the Get WPS options.

Once the Option 1 Get Routing Options button is clicked the plugin conducts the following steps:

  • The landing page is requested along with the routes endpoint to return any existing routes. If the landing page cannot be reached, then the window does not open, and an error is returned to the user.

  • The conformance endpoint is checked. All conformance classes are returned, and corresponding functionality is flagged to be enabled in the input window based on which conformance classes are listed.

  • A python server is launched on a separate machine thread to support callback requests (see Multi-Threading to Support Asynchronous Requests)

  • The Input Window for Option 1 is displayed (see Figure 8), including populated drop down lists to reflect available inputs, and a list of existing routes which can be fetched from the server.

The user then chooses the start and endpoint of their desired route by clicking in the map view using the Start Point and End Point input check boxes. During the Pilot, no address geocoding was implemented as it was out of scope. From here the user can choose to accept the faults or they can alter the other inputs to reflect their requirements. In the case of the obstruction input, when the user clicks the Obstructions button the current selected layer in the QGIS layer list is validated and chosen for input.

The method by which a route is requested is available in the drop-down list adjacent to the FIND ROUTE icon. This lists the supported options, based on the APIs conformance classes, which the user can choose to request a route. The default is polling Figure 4, other optional inputs include the API supported sync Figure 3 and callback Figure 5, as well as an additional method SSE (Server Send Events) Figure 6.

Once the user is content with their inputs they can click 'FIND ROUTE' to request the route via the proposed OGC Routing API. The plugin then conducts the following steps:

  • The request is constructed, and serialized into JSON. Any polygon layers chosen for the Obstruction input are converted from QGIS layers to GeoJSON MultiPolygons.

  • If the user chose the poll, sync or SSE method then the requested route is returned using the corresponding method.

  • If the user chose the callback method for the request then the subscriber URL is included in the request, which is the URL of the python server on the second thread. This URL tells the API server where to send the route once it has finished computing. Once the route is computed the API then POSTs the route back to the subscriber URL. The python server receives the route and passes it back to the main thread.

When received, the plugin converts the route from a GeoJSON Feature Collection to QGIS Vector Layers (see QGIS and Heterogeneous Feature Collections), adds the Vector layers in a group to the layer list and displays them on the map.

If the user instead chooses to click the Option 2 Get WPS options button the plugin conducts the following steps:

  • The landing page is requested along with the processes endpoint to return all existing process. If the landing page cannot be reached, then the window does not open and an error is returned to the user.

  • The Processes window is displayed listing all available processes found at the processes endpoint along with a description for each (see Figure 9).

The user then chooses the 'Compute routes' process and clicks 'Choose Process'. The plugin then conducts the following steps:

  • A GET request is sent to the Compute Routes process link, which returns back the Compute Routes process page, including a list of all supported inputs.

  • For each input, an input class is constructed at runtime for the QGIS GUI and a request property is established in a request object.

  • Once all inputs are processed all the input classes are exposed to the user in the Option 2 Input window (see Figure 10).

The user then chooses the start and endpoint of their desired route by clicking in the map view using the way points checkbox. If the API supports other inputs the corresponding input elements can be changed by the user in the GUI to reflect their requirements.

Once the user is content with their inputs they can click 'POST to Process' to request the route from the OGC Routing API. The plugin then conducts the following steps:

  • The inputs are stored in their corresponding request property in the request object, which was created in when input window was initialized.

  • The request object is then converted to JSON and sent using HTTP POST to the API server to request a route.

  • The requested route is returned using the polling method.

When received, the plugin converts the route from a GeoJSON Feature Collection to QGIS Vector Layers (see QGIS and Heterogeneous Feature Collections), adds the Vector layers in a group to the layer list and displays them on the map.

The display of routes is customizable. At present the route and node features reference two styles on disk which the user can choose to update or change. Below in Figure 12 can be seen the full QGIS application, with the plugin loaded. In this image the route used as part of the TIE tests can be seen between the National Cathedral and the Washington Monument.

The corresponding inputs used to create the route can be seen in the plugin input box on the right hand side. The Nodes are represented by red points and the edges by red lines.