Autonomous Vehicle Routing at rideOS
By Bill Chen, Engineer, rideOS
Problem: Why Waze or Google Maps can’t navigate a robot
Why does routing need to be re-invented for autonomous vehicles? Why can’t an autonomous vehicle just use Waze? Current mapping and navigation tools have UIs that are designed for a human to read and hear. This can be overcome by using an API, but, more fundamentally, the routes these tools provide for humans simply won’t work for robots.
Here’s an example of a typical route a human driver might take:
If an autonomous vehicle were to take this route, it might face a myriad of problems, depending on its technical competencies:
A router for autonomous vehicles needs to route around their limitations. For example, while human drivers can make eye contact and gesture to yield right of way, some AVs cannot safely perform unprotected left turns. Other AVs cannot autonomously drive through roads with lane closures or where an officer is directing traffic. Still other AVs may have impaired vision during certain sun angles or weather conditions and so are unable to consistently determine traffic light states.
On average, most of us who drive have comparable driving capabilities (that’s why we take a test!). However, the capabilities of AVs can vary quite a lot. An AV router needs to be flexible enough to take these varying limitations into account.
Reinventing Routing for Millions of Autonomous Vehicles
Before diving into our approach to routing, it’s useful to differentiate what we’ve introduced as routing vs. path planning for autonomous vehicles. The two are actually quite similar: they both examine the vehicle position and surroundings and provide a route/plan. However, the path planner also takes other inputs into account such as the prediction of nearby objects and their trajectories, as well as the perception of the state of traffic lights, etc. The output plan is consumed by a vehicle controller, which converts the high-level plan into lower-level signals for steering and acceleration.
In contrast, a router (sometimes referred to as a global or high-level planner) examines a larger area surrounding the vehicle (usually at a block or city-level). This allows the router to find optimal paths through the city, taking into account traffic conditions and the vehicle’s capabilities. These optimal paths are useful for a not only a single vehicle, but a fleet, enabling for fleet plans that reduce congestion or minimize total fleet costs.
The path planner and the router oftentimes work together, with the former providing tactical, local plans (should the vehicle stay in the lane or make a change?) and the latter providing strategic, global plans (will there be traffic in 5 miles?) for a fleet of vehicles.
At rideOS, we currently focus on routing at scale.
Routing can be thought of as finding a path from an origin to a destination. To compute this optimal path, the routing engine relies on 3 components: a graph, its weights, and algorithms to traverse the graph. The graph is a planar topology that represents the traversable space. For human routing, this graph is directly correlated to the road network, with edges and nodes representing road segments and intersections, respectively. With AVs, the graph corresponds to individual lanes on the road, which allows us to accurately account for the cost of changing lanes throughout the route (like, for example, taking an exit on the left immediately after merging onto a highway). With lane-level graphs, we can also cost lanes differently depending on the amount of traffic in each lane.
Unfortunately, even with just a road representation (i.e., no lanes), the graph is very large — the planet-wide OSM build currently contains on the order of 4 billion unique nodes. To ameliorate data explosion, we leverage multiple graph representations, including multiple levels of details, partitioning into sub-graphs, and computing additional metadata such as distance to landmarks.
In order to find a shortest path, each graph edge must have an associated weight, which represents the cost of traversal. For human-based routing, the cost of an edge is the time it takes a vehicle to travel over it. Usually the cost is a scalar value, but it can also have multiple costs (e.g. time and distance) and/or confidence probabilities. Pareto/multi-value optimization has been used to solve multi-cost functions and stochastic routing has been used to handle costs with uncertainty. For time-dependent routing problems, the costs themselves can change over time and require a different approach to solve optimally.
We’ve designed our routing engine to take cost functions as inputs so that the resulting route can flexibly change to the fastest route (in time), shortest route (in distance), a route that minimizes disengagements, or any number of combinations.
The first algorithms created to find shortest path on non-negatively weighted graphs were Dijkstra’s and the Bellman-Ford algorithm. Unfortunately, these approaches don’t scale well with even city-sized road graphs. Recent advances have focused on applying these fundamental graph exploration algorithms in clever ways to scale to real-world graph sizes. One straightforward improvement is to apply Dijkstra’s from both the origin and the destination node and employ clever termination conditions to the frontiers of both searches to reduce the size of the search space.
The A* search algorithm is another popular technique that guides Dijkstra’s search using a heuristic cost that acts as a lower bound for the optimal cost. Conventionally, A* uses a priority queue where the priority of a node x is the sum of its current cost d(s, x) and its heuristic cost h(x). This helps deprioritize nodes with prohibitively high costs. A typical lower bound for the shortest time cost is the haversine distance from a node to the destination, divided by a maximum car speed. One can think of A* as a generalization of Dijkstra’s naive routing algorithm with a zero-cost heuristic (i.e., h(x)=0 for all x).
Finding tighter lower bounds makes A* even more selective and, hence, faster. The “A*, Landmarks, and Triangle Equality” algorithm pre-computes shortest path costs from each node in the graph to a set of nodes called landmarks, and exploits the triangle inequality to precompute even tighter lower bounds for A*.
The area of routing is an amazing confluence of multiple disciplines:
- Computer science
- Data science
- Backend engineering
- GIS domain expertise
Here at rideOS, we are fortunate enough to have hired some of the best in these industries to help us build out next-generation routing, for fleets of self driving vehicles. If working on these problems this sounds interesting, check us at https://rideos.ai/careers!
