Saturday, May 23, 2015

The new generation of maps.

Maps are cool.  They are beautiful, functional, informative and artistic.  They are many different things to many different people.  While acknowledging that, my interest here is in maps that can support automated vehicles and transportation in general.  In some ways this is a limitation over previous maps, they lack the artistic beauty of many different forms, and certainly the evocative “here be dragons” in the blank spots.  In other ways this is much larger than most people’s conceptions of maps.  I retain the spatial components, that is everything is linked to a latitude and longitude, but I do not limit this map to a purely physical description of the world, rather it is a representation of how vehicles move through the world and what they sense at each particular location and pose.  It contains a history of the vehicles that have come before, and knowledge of the dynamic and transient behaviors of vehicles all within an environment that a machine can understand.  A different sort of aesthetic.

Probe based mapping.

Autonomous vehicles require maps based on probe data.  This is partially because they include content that can only be available from probes (i.e. content that cannot be observed from a mapping van or aerial photograph) and also because probes are the only way to get sufficient timeliness and accuracy from the mapping system.  Within the past few years there has arisen a general consensus that map should be augmented with probe data in order to get traffic information and the like.  In all cases these maps originally built from specialized collection equipment.  I believe this is a mistake because building a map by this method requires the deployment of that specialized collection equipment to every spot to be mapped.  This is a very severe constraint, especially if one is trying to map the minor roads in a rural region, which is often the region were roads are not standard and there are large numbers of fatal accidents, precisely the areas we want to address with map-based vehicle safety applications.  Furthermore, the single pass of the collection vehicle is prone to errors.  They can be sensor errors, human errors by the driver of the collection asset or anywhere in the processing chain, or simply random errors that conspire to introduce faults exceeding any tolerance threshold.
These problems are overcome by the statistical nature of probe based mapping.  Many probes are needed, and the data must be collected into a processing engine.  These are the sorts of problems that technology is overcoming in every field, mapping will be no different.
One of the major advantages of probe based mapping is that the data is statistical in nature and therefore amenable to traditional error analysis techniques.  The error on any measurement in a probe-based map can be quantified and provided with the data, allowing the application designer to choose suitable data for their process.  In addition, any deviation from normal can be quantified in terms of the probability of that deviation allowing quantitative assessment of changes in the map.

The core of the map.

Existing maps rely on roads is a fundamental element.  Lanes and other attributes are then derived from the road centerline.  For automated driving applications the road is an abstraction, what really matters is the lane.  This should be the core element of the map.  A lane can be defined in terms of a desired path for a large number of vehicles.  Lanes have a centerline, they have directionality, they may have a width and other attributes.  Even far in the future, when road markings may not be visible to humans, Helene will still be an important concept, that is an agreed-upon path for vehicles with a common origin and destination.  Given the proximity of vehicles and the potential time to collision relative to any response time of the vehicle I cannot imagine a situation where paths will not need to be defined in agreed-upon among vehicles.  The lanes may be very short-lived and possibly quite dynamic, changing direction and width based on the needs of local users, but without lanes, every vehicle is in a free-for-all and free, efficient movement will not be possible given the number of potential adverse interactions in a crowded environment.
In simulations of human movements through crowds lanes form dynamically and can last a considerable amount of time[1].  With slow-moving, and relatively robust, entities defining lanes on the fly is an acceptable approach, it is highly unlikely to work in a vehicle environment.  It certainly may be the case that lanes are defined in some collective manner and disseminated among the participants.  Even today, lane directionality is often determined by participants, say on a one lane bridge.  In the future, lanes may exist only virtually, defined as needed for the vehicles in task at hand, but the lane must be agreed upon by all of the participants.
A lane describes motivated movement with the expectation that there are no conflicts with other vehicles in that lane.  In general, one can make very accurate predictions that if a vehicle is in a lane now, it will be in that same lane a few seconds in the future.  This is the fundamental structure of the roadway and must be at the core of any representation that is useful for automated vehicles.
A road then, is some collection of lanes.  In general, cars can change between adjacent lanes traveling in the same direction.  Lanes traveling in the opposite direction may be used for passing (a short term change in the direction of travel).  Adjacent lanes are also generally subject to the same speed limit and traffic controls (stop signs etc.), but there are certainly exceptions.  In general I find that the definition of a road is fairly ambiguous.  A road centerline may or may not correspond to a lane centerline, and may not even correspond to a drivable path.  These problems are alleviated if the geometric entity is the lane and the road level attributes merely describes the relationships between lanes, that is the ability to transition from one lane to the other.  The road may also provide a convenient entity for the recording of certain attributes, such as speed limit, but fundamentally these belong to a lane.
Another relevant concept is that of the surface.  This, as the name implies, is the drivable surface on which vehicles may move.  A surface may be subdivided into lanes which are the primary interest of vehicles, and some of the surface may not be associated with a lane.  Under normal conditions of vehicle would stay within a lane however, there are many emergency situations where a vehicle must move outside of the lanes in knowing the extent of the drivable surface is useful for any application taking control in this situation.




[1] http://gamma.cs.unc.edu/lookahead/,   “Hybrid Long-Range Collision Avoidance
for Crowd Simulation”,  IEEE Transactions on Visualization and Computer Graphics (TVCG) 2014