GIScience for a driverless age

ABSTRACT

A driverless or autonomous vehicle requires significant support from information technology, both from central databases and from local sensors. The requirements for route guidance are in many ways more demanding than those of current guidance technologies, especially in the ‘last mile’ of a route. Significant extensions are needed for both street-centerline and point-of-interest databases. How these should be captured and structured present significant research challenges for GIScience. The societal and longer term impacts of such extensions are perhaps even more in need of focused research by the GIScience community.

KEYWORDS:

• GIScience
• route guidance
• driverless vehicles
• autonomous vehicles
• field robotics

Introduction

The DIME and TIGER programs of the US Bureau of the Census, developed to support the 1970 and 1980 censuses, respectively, resulted in the production of what are often termed street centerline (SCL) databases, that is representations of street and road networks as collections of linear edges connecting nodes. People closely connected with these programs saw an immediate opportunity for systems that would be carried in vehicles to support the driver’s wayfinding and navigation. Etak Inc., founded in 1983, began marketing its Etak Navigator in 1985, long before GPS became widely available for civilian applications. Location was initially established by the driver and maintained through the use of dead reckoning and map matching (https://en.wikipedia.org/wiki/Etak).

Today’s GPS-based navigation systems are in many ways direct descendants of the Etak Navigator, but many improvements have been made in addition to the introduction of GPS. So at this point in history, we might ask several significant GIScience questions:

1. What is the current state of geospatial technology in support of navigation by drivers?

2. What new geospatial databases and software will be needed to support navigation by driverless vehicles?

3. What benefits might such new databases and software have for driven vehicles?

4. What might be the long-term impacts of such developments?

The purpose of this largely speculative paper is to explore these questions and to identify significant research directions that might interest the GIScience community and might have significant social, technical and commercial value. In what follows, the focus is on vehicles that are truly driverless, that is the highest Level 5 of the J3016 standard (SAE International 2017).

There are many related technologies currently under development and many variations on the theme of the driverless vehicle. Vehicle-to-vehicle communications will allow a following vehicle to be largely driverless, since it will be able to depend on the lead vehicle for many if not most driver functions, including guidance. Vehicle-to-infrastructure communications will allow many forms of relevant information to pass between the vehicle and its surroundings, including such fixed infrastructure as traffic signals. While the sensors in a driverless vehicle will likely be able to detect the presence of pedestrians and cyclists, more advanced information about their intended actions would be especially useful to the vehicle and might be obtained by communicating information derived from their own guidance systems.

It is important to recognize that a huge amount of effort is currently being expended worldwide on these developments, much of it proprietary and with little open sharing of information. It would be easy, therefore, to argue that the academic GIScience community has little to offer or that its efforts should be focused on those aspects that are of little or no commercial interest. On the other hand, academics have a long-established tradition of reflection, of thinking ahead and ‘outside the box’ and of thinking about the broader implications of commercially motivated developments. Moreover, there are relevant developments in other disciplines that have received scant attention in GIScience.

The next section addresses the first question, with a review of progress to the present day and issues that continue to constrain the ability of drivers to navigate. This is followed by a discussion of the navigation requirements of driverless vehicles, and the new developments that will be required to satisfy them. The final section examines the long-term impacts of the driverless era through the lens of GIScience.

Progress to date

While it was the SCL databases such as DIME and TIGER that gave the route guidance industry its initial start, these databases were not initially designed to be navigable, that is, to represent features of critical interest to drivers, including one-way streets, turn restrictions and grade separations. Guidance that incorporates multiple travel modes, such as guidance for users of public transit, also requires the ability to capture certain hierarchical features of network links, such as multiple lanes and carriageways, and multiple rail tracks or platforms. By the late 1990s, the advent of object-oriented data modeling had allowed many such features to be represented and moved far beyond the simple topological networks of the 1970s. Figure 1 shows an example, the representation of transport links in the model developed by the University of California, Santa Barbara, in 2001 in collaboration with Esri as a component part of the Unetrans data model. How this model should be extended to address the needs of driverless vehicles is a significant research challenge.

Figure 1. The section of the Unetrans data model dealing with SCL information, expressed in Unified Modeling Language.

Support for navigation also requires functions for specifying trip origins and destinations. Point-of-interest (POI) databases have their origins in the gazetteers of officially recognized placenames that have been produced for decades by mapping agencies (Hill 2006), and in the georeferenced databases of businesses that began to appear in the late twentieth century, led by companies such as Dunn and Bradstreet. The locations of street addresses were initially obtained by linear interpolation using the block address ranges of the TIGER data, despite the nonlinear nature of much numbering, especially in rural areas. Today, one expects to receive a point location from queries as specific as a street address or business name, or as generalized as the name of a state or country, or an extended feature such as a river, and also expects route-guidance services to have implemented sophisticated capabilities for auto-correcting entries, and for making suitable suggestions when the user’s entries are ambiguous.

Today’s guidance systems also employ various devices for minimizing the effects of positional inaccuracy. GPS positioning has been enhanced in numerous ways, such as using signals from base stations. The problem of indoor positioning is being addressed, though to date, coverage is patchy at best. Positioning remains a problem in the vertical dimension, making it difficult to determine on which floor of a parking structure a vehicle is located, or whether the vehicle is on or under an overpass. Map matching and dead reckoning, essential parts of the Etak Navigator, are still employed to improve on location estimates from GPS and are especially important in tunnels or in areas of tall buildings or heavy tree cover where GPS loses its normal accuracy.

Turing (https://en.wikipedia.org/wiki/Turing_test) proposed what has become known as the Turing test: is it possible to detect whether the result of a request for information was provided by a human expert or a machine? On this basis, today’s route-guidance systems would clearly fail compared to wayfinders with expert knowledge of an area, such as cab drivers or drivers of delivery vehicles, since much of the information a local expert would have is not currently available in guidance systems. For example, guidance systems do not typically contain data about destinations with multiple entry points, or private driveways, both examples of data about the ‘last mile’ of a delivery. In effect, the driverless age will require that guidance systems pass the appropriate form of the Turing test: the behavior of a driverless vehicle should become indistinguishable from and perhaps improve on driving by human experts.

New requirements

Driverless vehicles are a form of field robot (Sturges 2014), akin to drones and other pilotless aircraft. A key component of field robotics is SLAM, for Simultaneous Localization and Mapping (Fernández-Madrigal and Claraco 2013), which reflects the requirement that a field robot must be capable both of determining its location and of sensing and representing the geospatial aspects of its immediate surroundings. In order to navigate, it must also be aware of its planned route from an origin to a destination. That route may also include stops to refuel and the delicate maneuvers required to park. It must detect and respond to numerous features along its route: for example, other vehicles, cyclists, pedestrians, traffic signals and signage. Some of these, such as the presence of traffic signals, may be recorded in databases or communicated to the vehicle, and in other cases, such as the presence of pedestrians, there may be features such as crosswalks that flag the likelihood that pedestrians will need to be avoided. Many such features are not recorded in existing route-guidance databases.

There are two distinct sources of geospatial data for a field robot. One is central in origin, served over the Internet or other wireless communication technology and possibly stored locally for use by the robot. The other is local in origin, acquired by the robot from its immediate surroundings. This same distinction between central and local also applies of course to today’s driven vehicles: local data are acquired through the driver’s senses, or increasingly through sensors installed in the vehicle, while central data are downloaded to the vehicle, in the form of map data, congestion data and guidance instructions that the server has obtained from map data using standard algorithms. The vehicle and driver may also be feeding data back to the central server, either automatically in the form of tracks (e.g. using Waze) or in the form of volunteered messages about updates and corrections to the central data. This feedback loop will clearly become more important in the driverless era, because the robot will be capable of acquiring data through its sensors that can be used to enhance, correct and update the central database.

Positional accuracy

All of the data used by today’s guidance systems are subject to positional errors, since it is impossible in principle to measure location perfectly. GPS errors may be minimized by map-matching or by filtering to reduce sudden spikes. SCL databases are also subject to errors, as are the locations provided in POI databases. It follows that a driverless vehicle operating with today’s databases may be uncertain about which lane it currently occupies, whether a lane change is necessary, which floor of a multistorey parking structure it currently occupies, how close it is to its planned destination or where it is in relation to a parking space or fuel pump. In the last two cases, positional errors of any more than 5 cm may be unacceptable.

What is important in most of these cases is not the absolute position provided by GPS and the databases, but the relative position provided by the vehicle’s own local sensors. GPS, map-matching and dead reckoning are sufficiently accurate to identify the street and to determine the vehicle’s approximate location along the street, while local sensors are able to position the vehicle within marked lanes, to guide the vehicle into a parking space and to locate the kerb cuts and fuel pumps of a gas station, all to 5 cm or better. Thus, it seems that no major improvement in positional accuracy will be needed in existing central databases.

Enhancements to POI databases

Several obvious enhancements to POI databases will be needed for the driverless age. Many features that are currently identified by a single point may in fact have many possible points of destination. For example, a hospital may have a general entrance, an emergency entrance and one or more loading docks. An extended feature such as a state or river, represented in today’s POI databases by a single representative point, may in reality have a myriad of possible destination points, any one of which might be the destination required for a specific trip. Research is needed to determine the best methods of capturing such destinations, representing their hierarchical relationships (e.g. Goodchild 2015), verifying their authenticity and inserting them into central databases and of identifying and selecting the correct destination point when the trip is initiated.

Enhancements to SCL databases

Current guidance systems assume that a vehicle or person will remain on a defined linear network. In reality, pedestrians, cyclists and even vehicles sometimes create new routes across open spaces. Trucks are not constrained to a linear network when navigating through container yards; and while airports mostly confine vehicles and aircraft to linear routes, exceptions are sometimes made. Will vehicles in a driverless age need to be entirely constrained to a linear network, and if so, how will it be possible to construct an optimized linear network that includes all possible routes from all possible origins to all possible destinations? How will driverless vehicles negotiate with each other when traveling in opposite directions on a single-lane road with no passing spaces?

Today’s SCLs are mostly constrained to public spaces. Yet, origins and destinations are sometimes separated from the public network by lengthy driveways or by areas such as parking lots or parking structures that are not entirely linearized. How should SCLs be extended to private spaces? Remote sensing is capable of mapping 2D spaces but not multistorey parking structures. How should private driveways be captured, given the implications for privacy, or must driverless trips end at the entrance to the driveway? Many of these issues relate to the ‘last mile’ (or ‘first mile’), the detail needed to navigate safely onto the established network.

Longer term impacts

Apart from the more technical questions of how to enhance and augment databases, it is the longer term impacts of the driverless era that arguably present the most interesting and challenging questions for GIScience and related disciplines. This section explores some of these questions, in the hope that readers will be motivated to explore them and to add their own.

First, we might ask about the impacts of significant numbers of driverless vehicles. Clearly, the experiments now being conducted on the streets of Phoenix and other cities are intended to demonstrate that small numbers of driverless vehicles can be accommodated on the established network without major disruption. But once the proportion exceeds a certain level, the disruptions will grow exponentially. To what extent will the behaviors of driverless vehicles emulate, or deviate from, the prevailing driving culture of the area? What will be the impacts on vehicles themselves, given that today’s automobiles have evolved with the human driver in mind? What will be the impact on the locations and design of fueling stations, or the design of parking lots? How will parking need to be redesigned when the proportion of passengers arrive to be dropped off rather than arrive to park? How will signage and lane markings be redesigned to be as easily detectable by driverless vehicles in all weather conditions as by drivers? In this regard, some readers may be aware of the research in the Soviet Union in the 1970s on the redesign of maps to be as easily and accurately read by machines as by humans (Shiriaev 1987).

If driverless vehicles are to be ‘floating’, that is to be available to all and to wait until summoned by a passenger, then their spatial distribution is critical. Just as methods of spatial optimization have been devised for ‘floating’ emergency vehicles, we might formulate specifications for the optimization problem of ‘floating’ driverless cars. What are the implications for parking areas? Will new parking areas be required, and how should they be located? Can we assume that the spatial distribution of destinations will match the spatial distribution of origins, or will driverless vehicles tend to accumulate over time in certain areas, just as the ‘floating’ bicycles that began appearing in US cities in the past year have gravitated to certain areas and land uses?

The current experiments involve too few driverless vehicles to impact levels of congestion, but what will be the long-term impacts on congestion once the proportion of vehicles reaches a significant level? To transport a single commuter in his or her owned vehicle from home to workplace requires one trip of that length, but when a ‘floating’ driverless vehicle is summoned, the total trip length and thus the level of congestion increases. On the other hand, the total number of vehicles in the system may decrease.

Drivers today have substantial freedom of choice over routes and departure times, and authorities have only limited ability to control traffic and reduce congestion: their powers extend, for example, to the timing of traffic signals, turn restrictions and high-occupancy lanes, and in some cities congestion pricing. But in a driverless age, the potential exists for much greater control, in the interests of increasing safety and of reducing pollution and congestion. Speed limits may be easier to enforce, and tolls and charges for road use may be easier to impose and collect. For example, charges can be related to the entire trip rather than to its use of roads, allowing active discouragement of long distance through trips in cities between outlying suburbs.

We might also speculate about the long-term impacts of driverless vehicles on land use. Will commuters be encouraged to take longer trips when it is possible to focus on work or entertainment rather than driving, and will this lead to an increase in urban sprawl rather than a densification? How will the structure of the city be affected by the many disruptions that are currently occurring in retailing and transportation?

Summary

Transportation exists to overcome the impediments of distance and as such is inherently geospatial. Over the past four decades, transportation technology has adopted and exploited many of the tools, algorithms and data that exist at the core of GIS. Today, the transportation industry is exploring and developing the technology that will eventually allow vehicles to drive themselves, and it seems obvious therefore that GIScience will have a significant role to play, in creating the knowledge on which these systems will operate and in reflecting on the more fundamental impacts of these developments.

Some of the questions raised by this paper fall clearly within the parameters of GIScience, but others may be more tangential, falling more into areas of application of GIScience, rather than augmentation of its fundamental knowledge. Nevertheless, I hope that this paper will have stimulated readers to think about the key research questions that these developments raise, and about the role that GIScience can play not only in pursuing researchable questions but also in preparing students to live and work in this new environment.

Disclosure statement

No potential conflict of interest was reported by the author.